pintos-pro4-filesystem-设计报告

Project4FileSystem作者：西安电子科技大学王永刚QQ:3575434202014.2.7文件系统是操作系统的五大功能模块之一，主要实现操作系统对程序、数据、设备等的管理。一、当前pintos文件系统的功能当前pintos文件系统已经实现了基本的文件创建删除功能。文件是固定大小，连续存放的。(1)文件在磁盘的存储方式：每个文件都有一个disk_inode存放在磁盘的一个扇区上，其结构如下：structinode_disk{block_sector_tstart;//文件数据每一个起始块off_tlength;//文件长度。unsignedmagic;//uint32_tunused[125];};现在pintos文件是连续的，而且在创建时指定其大小后，再不能改变大小。由起始扇区和文件大小就能找到所有文件数据。目录也是一个文件，只是其内容中都存放如下结构：structdir_entry{Block_sector_tinode_sector;//文件inode_disk所在扇区。Charname[NAME_MAX+1];Boolin_use;};(2)磁盘空闲空间管理方式。空闲空间是用位图来表示的。其中位图也是一个文件，其diskinode存放在Sector0.位图文件大小显然与磁盘大小有关，用一个位表示一个扇区是否被分配，一个扇区512字节，一个扇区作为一个物理块，创建一个2M的磁盘，有1024*1024*2/512bit=4096bit=4096/8=512Byte。(3)文件系统初始化过程：在init.c:main()函数中调用了filesys_init();1.在filesys_init()中，初始化了bitmap,而且对磁盘进行了格式化。其中格式化就是创建了两个文件，一个用来管理空闲块的位置图文件，一个是根目录文件。2.Filesys_init()中调用了free_map_init(),在free_map_init()中调用bitmap_create()创建了位图，大小依据磁盘大小。而且标记了01两个扇区为已经分配，作为free_map_file的disk_inode空间和根目录文件的disk_inode空间。此时free_map只是在内存中。3.Filesys_init()中又调用了do_format()在do_format()中：调用了free_map_create()，创建了free_map_file,即一个文件，其disk_inode已经在上面分配了，再分配文件大小即可，这是由调用inode_create函数来实现的。创建这个文件时显然需要分配磁盘空闲块，就从在内存中的free_map位图中分配就可以。文件创建好了之后，打开文件，把内存中的位图free_map写到磁盘上，这是调用bitmap_write()实现的，本质还是用file_write()实现的。File_write()是通过inode_write_at()写磁盘的。在do_format()中还创建根目录文件，ROOT_DIR_SECTOR已经标记了，分配文件所需要的空间就行了。4.Filesys_init()调用了free_map_open()把free_map读入内存。其实就是打开上面创建的free_map文件，读数据入内存。直到系统关闭时才将free_map写回到磁盘上。首先在内存中建立了磁盘的位图，标记了根目录和free_map本身的disk_inode结构扇区。上面的内存free_map一建立就保证创建文件时可以分配磁盘空间了。而inode_create()中就需要调用free_map_allocate()来获取空闲物理块。如果不格式化，则以前必然格式化过，直接读入free_map就行。(4)目录创建过程。Pintos原来已经实现了创建目录的功能，但是只创建根目录，而且根目录只能包含16个文件，即16个dir_entry结构。目录本质也是一个文件，根目录是特殊的文件，在filesys.h中有宏定义：#defineROOT_DIR_SECTOR1.在ROOT_DIR_SECTOR中，也就是第1个扇区中存放了根目录的disk_inode.上面已经提到了，在格式化时创建了根目录。(5)文件打开过程。调用filesys_open().每个打开的文件在内在都维护了一个唯一的数据结构inode(为了与disk_inode区别，这个叫memoryinode).以下是memoryinode结构：Structinode{Structlist_elemelem;Block_sector_tsector;Intopen_cnt;Boolremoved;Intdeny_write_cnt;Structinode_diskdata;};打开一个文件显然就是在内存中创建一个inode结构，其中structinode_diskdata保存了该文件对应的磁盘中的inode.如果此文件已经打开了，则只需要增加open_cnt的值，不用再创建一个inode.这些inode通过一个链表链结到一起的，在filesys_init()中初始化了这个链表。具体过程：调用filesys_open(constcharfilename);首先打开根目录，然后在根目录中依据filename查找文件。如果找到了，也就是找到了此文件对应的structdir_entry结构，里面记录了文件disk_inode,disk_inode中记录文件数据起始位置和文件大小，这就可以读写文件了。当然，还需要建立文件对应的memoryinode.其中data就是此文件的disk_inode.通过filesys_open()只能得到文件的inode.如果此文件是普通文件，则调用fileopen(inode)把inode包装成structfile结构;如果是目录就调用dir_open把inode包装成structdir.Structfile结构如下：Structfile{Structinode*inode;Off_tpos;Booldeny_write;};(6)文件的创建过程.创建一个文件要有文件名和文件大小，每一个文件在磁盘中都有一个structdisk_inode结构，每个文件和目录都要在一个目录下，在目录文件中，structdir_entry中记录了每个该目录下的文件的文件名，以及每个文件disk_inode所在扇区号。具体是通过调用filesys_create(constchar*name,off_tinitial_size)实现的.首先调用structdir*dir=dir_open_root()打开根目录。以下structdir结构。Structdir{Structinode*inode;Off_tpos｝;本质就是一个文件，读写目录与读写普通文件没有区别。然后调用free_map_allocate分配一个扇区sector作为新文件的disk_inode.再调用inode_create(sector,initial_size)分配文件所需要磁盘空间，分配的空间是连续的扇区。最后创建一个structdir_entry结构，把文件名和其sector填入其中，在目录中找一个位置放入就可以了。(7)文件的读写。调用filesys_open()打开文件，这就得到了structfile结构，如下：些结构记录了当前文件指针位置pos。File_read()file_write()分配是通过inode_read_at()和inode_write_at()实现的。二、对disk_inode的改进当前pintos文件系统限制很大。文件需要连续存储，这会导致大量磁盘碎片。文件大小固定，不能动态增长文件，只有一个目录。这里主要把连续存储方式改为了linux中三级索引结构，而且可以动态增长文件，可以创建子目录。三级索引结构：012345678910111213140—11是直接块，存入文件数据块扇区号。12是一级索引13是二级索引14是三级索引如果一个物理块是512字节每个物理块中用四字节直接块：12*512=6K一级索引：128*512=64K二级索引：128*128*512=8M三级索引：128*128*128*512=1GB总大小1GB8M72K通过修改structdisk_inode结构来实现三级索引结构。修改过的disk_inodeStructinode_disk{Off_tlength;//文件长度Uint32_tblocks[BLOCK_NUM];//三级索引区Unsignedisdir;//此文件是不是目录Unsignedmagic;Uint32_tunused[110];};修改inode_create()Inode_read_at()Inode_write_at()三个函数即可。空闲磁盘块依然用位图管理。可以用free_map_allocate()获得一个空闲物理块。用free_map_release()来释放物理块。只用写文件才有可能增长一个文件的大小。读写文件一般是给出.1.改变了disk_inode,自然要从inode_create开始入手。代码见附录。因为要区分目录和普通文件，所以对原来的inode_create进行了扩展，改为了boolinode_create_ex(block_sector_tsector,off_tlength,uint32_tisdir);增加了isdir参数。重新定义了一个函数：boolinode_create(block_sector_tsector,off_tlength){512128512128512128Data……512128512128data512128datareturninode_create_ex(sector,length,0);}用这个来代替原来的inode_create。Inode_create执行时文件的disk_inode已经分配了，只需要分配文件数据空间，这里并不从free_map中分配空间,只是简单的把索引初始化为0。新创建的文件内容应为全0，所以调用了inode_write_at()来把文件内容写为全0;在写的过程中如果发现空间未分配，则会分配。2.读写文件读写文件时会给出文件指针偏移offset和要读写的大小。需要根据offset来确定要读写的扇区，通过上面的公式可以计算出扇区号。计算代码见附录。定义如下结构：structPosInfo{uint16_tlev;//索引级别uint32_toff;//数据扇区内部偏移uint32_tsn[4];//sn[i]表示i级索引块的扇区号uint32_tnp[4];//np[i]表示i级索引块的偏移.};根据offset可以计算出offset在几级索引中----lev最后的数据块中的偏移-------off举例：如果offset=215364size=865buff=…要从文件215364字节处读取865字节到buff中。经计算：Lev=2Sn[0]=0blocks[15]Np[0]=13Sn[1]=0Np[1]=2Sn[2]=0Np[2]=24由np[0]=13可以通过读取扇区blocks[np[0]]到缓冲区arr[512]中去此时arr[]中就是一级索引块Arr[np[1]]就是二级索引块的扇区号，由此又可以把二级索引块读入到arr[]中。此时arr[]就是二级索引块，Arr[np[2]]就是文件数据块的扇区号了，把数据块读入到arr[]中就可以对数据进行读写了。这个扇区读写完毕之后，offset也向后移动了x字节，这时又需要重新确定structPosInfo结构。注意：写的时候，如果最后offset已经大小了文件长度，则认为扩展了文件长度，修改disk_inode中的文件长度。这就实现了文件的动态增长。3.inode删除0…11121314需要收回文件空间，显然有了structPosInfo结构，收回空间不是难事儿。代码见附录。三、多级目录的建立现有目录只是根