fs_tools.txt

测试工具：
	目标：
		针对一个文件，在文件上构建符合格式的文件系统；初始化其目录结构，将指定的外部文件（普通文件）复制到指定目录下；如果初始时需要创建设备文件，也一并创建。
		能够检查文件超级块信息，指定目录、文件信息。
	程序中使用一个公共的文件描述符、超级块结构表示当前正在操作的文件系统；
	建立一个内存i结点的结构，针对i结点的操作可在该结构上进行，其定义如下：
		fd，当前正在操作的文件的文件描述符；
		sb，指向当前正在操作的公共的超级块；
		i结点号，表示该结构对应的磁盘i结点；
		磁盘i结点内容副本；
	
	构建文件系统的工作包括：
		创建一个空的、符合格式的文件系统，该文件系统中仅有一个根目录；
		将外部文件依次放入根目录下，名字保持一致；
	另外需要检查接口，用于检查文件系统中指定目录/文件的信息：
		如果是目录，则输出该目录相关信息（目录项等）；
		如果是文件，则输出该文件相关信息（文件内容等）；
		
	构建测试文件系统的过程：
		调用函数，创建一个空的、符合格式的文件系统；
		为根目录分配i结点（必须是0号i结点）；
		构造根目录i结点对应的内存inode结构；
		添加"."和".."这两个目录项到根目录中；
		将inode结构内容写入文件系统；
		
		针对每一个外部文件
			调用函数，创建一个长度为0的i结点文件；
			调用函数，在根目录中添加一个目录项，使其指向上述创建的i结点文件，其名字和该外部文件的名字相同；
			调用函数，复制外部文件内容，写入上述创建的文件中；
			
	检查工具的目标：
		用法：./cmd fs_img [-d path] [-f path]
		当仅指定fs_img这个参数时，按如下方式输出其超级块信息：
			disk inode bitmap起始位置，所占块数；
			block bitmap起始位置，所占块数；
			disk inode起始位置，所占块数，disk； inode总数，已使用个数，剩余个数，列出被使用了的i结点号并打印i结点信息（元数据）；
			block起始位置，block 总数，已使用个数，剩余个数，列出被使用了的block号；
		-d选项：以目录项形式输出path指定目录的目录内容；
		-f选项：以十六进制形式输出path指定文件（普通文件）的内容；
	
	所需要的接口：
		创建一个空的、符合格式的文件系统：
			输入：dd建立的文件名（用作磁盘，文件内容全部清零），要求长度是512字节倍数
			输出：在指定文件上构造出文件系统，该文件系统能充分利用文件中的空间
			假设文件长度为disk_size字节，可构成disk_size/512个块；
			一个磁盘i结点最少需要关联1个block，最多关联141个block；设定一个磁盘i结点平均关联64个block，若有n磁盘i结点，则需64*n个block，以此可得等式：
				2 + n/(8*512) + (64*n)/(8*512) + n*sizeof(disk_inode)/512 + 64*n = disk_size/512
				2*8*512 + n + 64*n + 8*n*sizeof(disk_inode) + 64*n*8*512 = disk_size*8
				n=(disk_size*8-2*8*512)/(1 + 64 + 8*sizeof(disk_inode) + 512*512)
			
			令“可用于分配的磁盘i结点总数”为n；
			如果n/(8*512)为整数
				令“disk inode bitmap所占块数”为n/(8*512)
			否则
				令“disk inode bitmap所占块数”为n/(8*512)+1
			如果(64*n)/(8*512)为整数
				令“block bitmap所占块数”为(64*n)/(8*512)
			否则
				令“block bitmap所占块数”为(64*n)/(8*512)+1
			如果n*sizeof(disk_inode)/512为整数
				disk inode所占用的块数为n*sizeof(disk_inode)/512
			否则
				disk inode所占用的块数为n*sizeof(disk_inode)/512 + 1
			先令“可用于分配的block总数”为(disk_size/512 - 2 - disk inode bitmap所占块数 - block bitmap所占块数 - disk inode所占用的块数)
			如果“可用于分配的block总数” 大于 “block bitmap所占块数”*512*8
				假设“多出的block数”为上述两者相减
				对““多出来的block数”/(512*8)”向上取整
				令“可用于分配的block总数”减去上述向上取整后的值为新的“可用于分配的block总数”
				令“block bitmap所占块数”加上上述向上取整后的值为新的“block bitmap所占块数”
			
			将上述参数写入超级块；
			根据上述参数初始化两个bitmap；
			预分配0号block，因为0号block保留；
		
		读取超级块（文件描述符fd，超级块指针）：
		分配数据块，返回数据块编号，失败返回_NAVL_BLK_NUM_（文件描述符fd，超级块指针）：
		释放数据块，成功返回0，失败返回-1（文件描述符fd，超级块指针，块编号）：
		清零数据块（文件描述符fd，超级块指针，块编号）：
		
		按照扇区号对文件进行读写：
		从磁盘i结点特定偏移处读取指定数量字节到缓冲区中，返回实际读取字节数（内存i结点指针ip、缓冲区首地址dst、偏移量off、字节数n）：
			if off > ip->size or off+n < off
				return -1
			if off + n > ip->size
				n = ip->size - off
			m = n
			
			for(; n > 0; n -= min, off += min, dst += min)
				raw_read(ip->fd, bmap(ip, off/BLOCK_SIZE), buf, BLOCK_SIZE)
				min = min(n, BLOCK_SIZE - off%BLOCK_SIZE)
				memmov(dst, buf + off%BLOCK_SIZE, min)
			return m
			
			注意：
				在磁盘i结点结构定义中size成员为无符号的，但实际受限于设计，最大文件仅为70KB，这里返回值使用有符号类型（为能区别错误值），但仍能满足使用，使用时需要注意。
				设备类型的i结点会如同普通文件/目录类型的i节点一样被操作。
		将缓冲区中的指定数量字节写入磁盘i结点特定偏移处，返回实际写入字节数（内存i结点指针ip、缓冲区首地址src、偏移量off、字节数n）：
			if off > MAX_SIZE or off+n < off
				return -1
			if off + n > MAX_SIZE
				return -1
			m = n
			for(; n > 0; n -= min, off += min, src += min)
				snum = bmap(ip, off/BLOCK_SIZE)
				raw_read(ip->fd, snum, buf, BLOCK_SIZE)
				min = min(n, BLOCK_SIZE - off%BLOCK_SIZE)
				memmov(buf + off%BLOCK_SIZE, src, min)
				raw_write(ip->fd, snum, buf, BLOCK_SIZE)
			if n > 0 && ip.size < off //要发生实际的写入且写入后off超出了当前文件大小才对当前文件大小进行更新。
				ip.size = off
				调用函数更新inode结构内容到磁盘；
			return m
			
			注意：
				当写入出错时（比如off/n有误、写入数据会超出最大文件大小）返回-1。
				在磁盘i结点结构定义中size成员为无符号的，但实际受限于设计，最大文件仅为70KB，这里返回值使用有符号类型（为能区别错误值），但仍能满足使用，使用时需要注意。
				设备类型的i结点会如同普通文件/目录类型的i节点一样被操作。
		
		
		获取一个与指定i结点关联的内存i结点结构（i结点编号）：【need】
			从堆中分配一个结构；
			填写其i结点编号、文件描述符、超级块指针；
			返回其指针；
			
			注意：返回的内存i结点结构中没有有效数据，需要读取一次
		
		寻找第一个空闲的磁盘i结点，返回一个与该i结点对应的内存i结点结构指针：【modified】
			定位到disk inode bitmap的位置；
			从头遍历该bitmap
				如果发现一个空闲bit
					置位并写回其所处的block；
					调用函数，获取一个与该i结点编号对应的内存i结点结构；
					返回上述这个结构的指针；
			返回NULL；
		读取磁盘i结点到内存i结点结构中，成功返回0，失败返回-1（内存i结点指针）：
			定位到对应磁盘i结点所在的block；
			复制其内容到内存i结点结构中，若失败返回-1；
			返回0：
		将内存i结点中磁盘i结点内容副本写入磁盘对应位置（内存i结点指针）：
			定位到对应磁盘i结点所在的block；
			写入内容到对应位置，若失败返回-1；
			返回0；
		
		查找i结点所关联的第n个block，如果不存在则分配新的清零过的block并建立必要的映射，然后返回其扇区编号，n从0计算（内存i结点指针，n）：
			假设bnum为对应block的编号；
			
			如果n在直接索引范围内
				令bnum为n对应的索引；
				如果bnum无效
					调用函数分配一个清空过的block，并将其记录在地址数组中n对应的位置；
					令bnum为刚刚分配的block号；
					调用函数将i结点内容更新到磁盘；
				返回bnum对应的扇区编号；
			此时说明n不在直接索引范围内；
			令n为n减去最大直接索引个数（12）后的值，即n为间接索引块中的位置偏移；
			如果n在间接索引范围内
				如果间接索引块的索引无效
					调用函数分配一个清空过的block，并将其记录在地址数组中间接索引块对应的位置；
					调用函数将i结点内容更新到磁盘；
				读取间接索引块；
				令bnum为n对应的索引；
				如果bnum无效
					调用函数分配一个清空过的block，并将其记录在间接索引块中n对应的位置；
					令bnum为刚刚分配的block号；
					写回间接索引块；
				返回bnum对应的扇区编号；
				
			此时说明n超出了最大索引范围，返回0；
			
			注意：执行过程中失败（比如无法分配空闲块）则会返回0。
		
		在指定目录文件中查询目录项，成功查询返回0，如果存在同名目录项则将其对应i结点的内存i结点指针写入pp，否则返回-1，不设置pp（内存i结点指针ip，目录项名name，指向内存i结点结构指针的指针pp）：
			从头遍历目录文件，如果读取失败返回-1
				如果目录项为空
					跳过；
				比较目录名；
				如果相同
					调用函数，获取一个对应的内存i结点结构；
					将该结构指针写入pp；
					退出遍历；
			返回0；
			
			注意：该函数没有检查参数是否引用一个目录文件，返回的内存i结点结构中没有有效数据。
		在指定目录文件中添加目录项，成功返回0，失败返回-1（内存i结点指针，目录项名，i结点编号）：
			如果这不是一个目录文件
				返回-1；
			在指定目录下查找待添加的目录项名；
			如果已经存在同名目录项
				返回-1；
			从头遍历指定目录文件，每次读取一个目录项，记录这个目录项的偏移到off中
				如果目录项为空
					退出遍历；
			构建待添加的目录项；
			调用函数，将该目录项写入指定目录文件的偏移off处；
			返回0；
		在指定目录下创建一个长度为0的i结点文件，返回该i结点文件的内存i结点指针（内存i结点指针ip，文件类型type，目录项名name）：
			如果这不是一个目录文件
				返回NULL；
			调用函数，检查指定目录ip下是否有name这个目录项
			是
				返回NULL；
			调用函数，分配一个i结点，并获得一个与该i结点关联的内存i结点结构new_ip；
			设置new_ip.type为type；
			设置new_ip.link_number为1；
			设置new_ip.size为0；
			设置new_ip.addrs中全部元素为0（0号block保留）；
			设置new_ip.major/minor全为0；
			
			如果new_ip.type为目录
				调用函数，在new_ip中添加"."和".."这两个目录项；
				将new_ip.link_number加1；
				将ip.link_number加1；
				调用函数，写回ip；
			调用函数，在ip中添加目录项，使其指向new_ip，并命名为name；
			调用函数，写回new_ip；
			
			返回new_ip；
			注意：该函数能够创建目录文件、普通文件、设备文件，新创建的目录文件默认仅具有"."和".."这两个目录项，对于设备文件，并未设置其major/minor号，需调用者进一步处理；
		
		解析路径，操作成功返回0，解析成功将会把该路径指定对象的内存i结点结构指针或者其父目录对应的内存i结点结构指针写入ipp中，如果是针对其父目录，并且name不为NULL的话则还将该路径指定对象的名字复制到name中；操作失败返回-1（路径path，解析到父目录停止stop_at_parent，最后一个元素名字name，ipp）：
				获取文件系统中根目录对应的内存i结点结构指针ip；
				循环调用函数解析path中的元素并复制到elem中，解析完毕则退出循环
					读取ip对应i结点；
					如果ip并不是目录
						丢弃ip这个引用；
						返回0；
					如果指定stop_at_parent，且elem已经是最后一个元素
						如果name不为NULL，将elem复制到name中；
						将ip写入ipp中；
						返回0；
					调用函数在ip中查找名为elem的目录项；
					如果不存在
						丢弃ip这个引用；
						返回0；
					丢弃ip这个引用；
					令ip指向elem对应目录项的内存i结点结构；
				
				如果指定stop_at_parent（此时说明是在解析"/"的父目录）
					丢弃ip这个引用；
					返回0；
				
				读取ip对应i结点；
				如果path中最后一个元素以'/'结尾，说明path指定对象应该是目录
					如果ip并不是目录
						丢弃ip这个引用；
						返回0；
				将ip写入ipp中；
				返回0；
				
				注意：
				对"/"路径查找其父目录，会返回NULL，以防止'/'出现在目录项名中；
				如果仅查找路径指定对象的父目录，则不检查路径指定对象是否存在；
				返回的内存i结点结构中存在有效数据；
				所有path均视为绝对路径；
		
		打印磁盘i结点信息：
			输出磁盘i结点元数据、所表示的资源内容（普通文件、目录内容）
		检查文件系统；
			输出如下信息：
				disk inode bitmap起始位置，所占块数；
				block bitmap起始位置，所占块数；
				disk inode起始位置，所占块数，disk； inode总数，已使用个数，剩余个数，列出被使用了的i结点号并打印i结点信息；
				block起始位置，block 总数，已使用个数，剩余个数，列出被使用了的block号；
				
	文件的组织结构：
		fs.h：提供相关结构定义
		mkfs.c：提供构建文件系统的函数实现
		fsck.c：提供文件系统检查函数的实现
		lib.c/lib.h：提供模拟磁盘操作函数以及读取超级块的实现和接口声明
		block.c/block.h：分配、释放数据块函数的实现和接口声明
		inode.c/inode.h：i结点操作函数的实现和接口声明
		path.c/path.h: 目录文件的操作接口和声明
		file.c/file.h：创建i结点文件和声明