这是大三小学期的时候做的，不知不觉快 3 年了，转过来留个纪念。
发信人: Xer (小x｜SL小分队), 信区: Linux
标 题: [分享][操作系统小学期]模拟文件系统
发信站: 北邮人论坛 (Sat Sep 5 21:41:41 2009), 站内
============
写在前面的话
============
这个程序是我的操作系统小学期做的文件管理部分，磁盘布局是抄minix的，但是内存数据结构是自己想的(越往下写越感觉自己设计的不对)。从8月24号到熄灯前的那段时间基本是每天晚上2点上床7点起床，其它时间除了吃饭上厕所基本就是在查资料写代码，整个疯狂的程序员。既然抄了GPL的东西，就遵循GPL的规定开源了。
数据结构跟vfs的出入挺大，所以写出来的东西不是很好，大牛们轻拍~
====
简介
====
文件系统用一个文件模拟，默认大小是32M(由ofs.h中的OFS_SIZE定义)，默认块大小为4K(由ofs.h中的PAGE_SIZE定义)。程序由ANSI C写成，可以在Windows和Linux上运行。
模拟文件系统总共分六大部分，分别是引导块(MBR)，超级块(super block)，索引节点位图(inode bitmap)，数据块位图(data block bitmap)，索引节点表(inode table)和数据区(data area)。各个部分的大致情况如下图所示：
+-------------+
| MBR | 0 --> 1k 预留块，未作处理
| |
+-------------+
| super | 0 --> 1k 用来记录系统重要信息，如文件系统大小，可引用inode，
| block | 空闲数据块，创建时间等，具体见 struct ofs_super_block。
+-------------+
| . |
| . | 0 --> 2k 预设块大小是4k，所以这里没使用
| . |
+-------------+
| inode | 2 --> 根据inode table的大小决定，这个块创建顺序是2
| bitmap |
+-------------+
| data block | 3 --> 由除了1和2的数据块块数决定，创建顺序是3
| bitmap |
+-------------+
| inode | 1 --> 创建顺序为1，inode数量默认为磁盘总数据块数的1/3，所以
| table | 这个块大小是inode的数量*每个inode的大小。
+-------------+
| data | 4 --> 剩下的部分全都归数据使用。
| area |
| . |
| . |
| . |
+-------------+
整个程序分成3层，分别是应用程序(在cmd.h中定义)，系统调用(在syscall.h中定义)，文件系统接口(在ofs.h中定义)：
----------------
应用程序
----------------
系统调用
----------------
虚拟文件系统(缺)
----------------
具体文件系统
----------------
................
在文件系统部分中又分为3部分：虚拟文件系统(vfs)，内存组织方式和磁盘组织方式。内存组织方式是磁盘组织方式的延伸。本来想加上vfs的，但是由于时间关系没实现。没有vfs的一个直接后果就是有些操作本来是由vfs完成的，但是现在却要放到系统调用层，或者放到与具体文件系统相关的地方去实现，这样就为以后的扩展带来了问题。对一些参数的合法性判断不知道该放到什么地方，有些数据结构是为了符合vfs的接口而凑出来的(例如struct file)，有些函数的实现形式很奇怪，因为毕竟是模拟文件系统，没有操作系统的支持，有些操作很像真正的调用那样实现。
可用的命令：cd ls create ln mkdir rmdir mv truncate pwd read write rm fsinfo help
========
数据结构
========
-------------------
超级块(super block)
-------------------
在 ofs.h 中定义：
/* super block的磁盘数据，大小为 128 字节 */
struct ofs_super_block {
__u16 s_magic; /* 文件系统签名，用于决定文件系统类型 */
__u16 s_inode_size; /* inode 大小，单位是字节(Byte) */
__u16 s_block_size; /* 数据块大小，单位字节(Byte) */
__u8 s_mount_nr; /* 被挂载的次数 */
__u8 s_version; /* 文件系统版本 */
__u64 s_size; /* 文件系统所在分区大小 */
__u64 s_mkfs_time; /* 创建时间 */
__u64 s_mount_time; /* 最后一次挂载的时间 */
__u64 s_mtime; /* 最后一次修改的时间 */
__u64 s_itable_offset; /* inode 表距离分区起始位置的偏移量 */
__u64 s_data_offset; /* 数据区离分区起始位置的偏移量 */
__u64 s_inodes; /* inode 的数量 */
__u64 s_blocks; /* 数据块的数量 */
__u16 s_imap_blocks; /* inode bitmap 所占的块数 */
__u16 s_bmap_blocks; /* data bitmap 所占的块数 */
__u64 s_free_inodes; /* 可用的 inode 数量 */
__u64 s_free_blocks; /* 可用的数据块数 */
__u8 s_uuid[16]; /* 唯一标识 */
char s_name[16]; /* 分区名称 */
__u32 s_padding; /* 填充 */
};
这里对基本的数据结构进行了typedef，主要是为了对齐的时候方便一点：
typedef unsigned char __u8;
typedef unsigned short int __u16;
typedef unsigned int __u32;
typedef unsigned long long int __u64;
typedef signed char __s8;
typedef signed short int __s16;
typedef signed int __s32;
typedef signed long long int __s64;
因为是模拟，所以就不分大小端了。
---------------
索引节点(inode)
---------------
在 ofs.h 中定义：
/* 根节点号 */
#define OFS_ROOT_INO 1
/* 直接索引块数量 */
#define OFS_DIR_BLOCKS 9
/* 间接索引块位置 */
#define OFS_IDX_BLOCK OFS_DIR_BLOCKS
/* inode中的索引数 */
#define OFS_BLOCKS_NR (OFS_IDX_BLOCK+1)
/* inode的磁盘数据结构，每个inode的大小是128 字节 */
struct ofs_inode {
__u16 i_version; /* inode 的版本号 */
__u16 i_mode; /* 文件类型和访问权限 */
__u32 i_uid; /* 所有者 id */
__u32 i_gid; /* 组 id */
__u32 i_links; /* 引用数 */
__u64 i_size; /* 文件大小，单位是字节 */
__u64 i_atime; /* 最后访问时间 */
__u64 i_mtime; /* 最后修改时间 */
__u64 i_ctime; /* 创建时间 */
__u64 i_block[OFS_BLOCKS_NR]; /* 数据保存的位置，最后一块是间接块，
其他的都是直接块，按照块大小4k来
算，最大的文件是2M+36K */
};
/* inode的内存数据结构 */
struct inode {
__u64 i_ino; /* inode number */
unsigned int i_dents; /* 如果该inode是目录就记录该目录下的文件数目，
这个是为了创建文件的时候防止超过目录大小限制
而增加的 */
unsigned char i_flags; /* 是否需要写回磁盘(dirty) */
struct ofs_inode *i_ip; /* 磁盘上的inode数据结构 */
struct dentry *i_sub_de; /* 子目录项，是一个循环双链表，如果inode是普通
文件这个就为空。在vfs中这个功能好像是属于
dentry的，后来的实现证明这样组织有很大问题，
这个是造成struct file严重变形的元凶之一。 */
};
--------------
目录项(dentry)
--------------
在 ofs.h 中定义：
/* dentry的磁盘数据结构，每个dentry的大小是 128 字节 */
#define OFS_MAX_NAME_LEN 119
struct ofs_dentry {
__u64 d_ino; /* inode number */
char d_name[OFS_MAX_NAME_LEN+1]; /* 目录项名字 */
};
/* dentry的内存数据结构 */
struct dentry {
__u64 d_ino; /* 对应的inode号 */
/* 因为读到内存后无法得知目录项在磁盘的位置，所以增设了这个记录位置
的项 */
struct {
unsigned int no; /* 在目录文件内的哪个数据块 */
unsigned int off; /* 在数据块内的偏移量 */
} d_pos;
unsigned char d_flags; /* 是否需要写回磁盘(dirty) */
struct inode *d_inode; /* 相关的inode */
struct inode *d_parent; /* 父目录inode */
struct dentry *d_prev,*d_next; /* 同一父目录下的目录项，一个
循环双链表，头结点由父目录
inode的i_sub_de指向 */
char d_name[OFS_MAX_NAME_LEN+1]; /* 名字 */
};
被删除了的dentry在磁盘中的inode number为0，并且这个块不会出现在内存中。当需要在目录新建文件时可以重新使用这些项。至于查找方法在后面说明。
---------------------
文件相关(struct file)
---------------------
真不想把这个写出来。这段介绍的作用也跟这个结构体在这个程序的作用一样，只是为了完整性……
在ofs.h中定义：
/* 伪 "struct file" */
struct file {
struct dentry *f_dentry; /* 与文件相关的目录项 */
void *f_ptr; /* 遍历目录时使用的指针，主要供readdir()使用。
都是数据结构设计得不好才有这个东东 */
__u64 f_pos; /* 如果是普通文件，就表示偏移量；如果是目录……
不想说了，看ofs_readdir()的实现吧，我面壁
去了…… */
};
------------
位图(bitmap)
------------
就是一长串01。只有3个操作：(1)查找第一个不为0的位置；(2)把该位置为1；(3)把该位清零。
查找的方法很土，每次按一个字节处理。如果小于255就说明在这8位中有0，再用一个for循环找到不为零的位置然后返回偏移量。置1和清零的方法就是根据给出的偏移量直接跳到该偏移量所在字节的前一个字节，然后移位处理即可。
格式化文件系统时并没有对inode table和数据区进行填充操作，只是把inode bitmap和data block bitmap都清零。分配inode或者数据块的时候从左往右找到第一个不为0的位，然后置1，返回偏移量，就是inode number或者block number。
--------
全局变量
--------
因为不想全局变量满天飞，所以将各种缓冲区都放在struct fs_info中。但是还是有漏网之鱼，就是指向当前目录的inode指针，这也是这个程序之中唯一一个真正意义上的全局变量。
在ofs.h中定义：
struct fs_info {
FILE *dev; /* 指向打开的用来模拟这个文件系统的文件指针
名字起得还不错~ */
struct ofs_super_block *sb; /* 超级块 */
unsigned char *imap; /* inode bitmap */
unsigned char *bmap; /* data block bitmap */
struct inode *root; /* 根节点 */
struct rbtree icache; /* 读入内存的根结点都放在这棵红黑树中 */
struct dentry *dcache; /* 没使用的dentry项的一个单链表，优点
是实现简单，不过很后悔没有用块缓冲 */
/* int sync_ival; */ /* 定时更新，没实现 */
};
这些缓冲区由ofs_mount()初始化，由ofs_umount()最后更新到磁盘并释放空间。
============
内存组织方式
============
ofs_mount()函数初始化struct fs_info的各个项，并且把根结点放到红黑树中。当需要查找目录时先调用ofs_read_entry()从磁盘上读取所有的目录项并且按顺序链接成一个双链表。注意一定要按顺序，这个关系到磁盘上被删除的块可以重用并且更新的时候可以把同一个块需要更新的目录项都写到缓冲区中再写回磁盘。
磁盘上的inode出现在内存中有两种途径：新建一个文件时由ofs_alloc_inode()创建一个新的inode并插到红黑树中，还有使用ofs_lookup()查找到某个目录项后把该目录项的相关inode读到内存，这个也插入到红黑树中。这样inode的管理就很清楚了，就是创建和删除都要经过红黑树，查找的结果也是指向红黑树中的inode。这个好处就是保证了inode的信息是实时的，最后umount只要在删除树的时候释放树的每个结点就可以了。
目录项出现在内存中也有两种方式：新建一个目录项时由ofs_add_entry()插入到相应inode的以i_sub_de为头结点的循环链表中，或者由ofs_read_entry()读到相应inode的i_sub_de中。这样目录项的更新和释放就由它的父目录inode决定了：当一个目录项存在时，它的父目录inode必存在；但反之不一定，这个好像正好跟内核相反。当删除红黑树里的某个inode的时候要把该inode的子目录都释放掉。这样，当一个目录项存在时，它的d_inode和d_parent都不会为空。
当要往某个目录下增加一个文件时，先根据块号查询。如果在同一块内并且两者的偏移量相差大于sizeof(struct ofs_dentry)，就说明这两个目录项之间至少有一个可用的目录项(前面已经说过，被删除的目录项不会出现在内存中)；如果在不同的块内，并且另一块的起始偏移量大于0，就说明在另一块的起始位置至少有一个可用的目录项；如果另一块的起始偏移量为0但是前一块的偏移量小于block_size-sizeof(struct ofs_dentry)，就说明在前一块的末尾至少有一个可用的目录项；还有其它的情况就不详细说了，参考ofs_add_entry()。这样做虽然可以重复利用目录项，但是每一次都得查找，特别是像这个程序中的目录项组织方式，当一个目录下有很多文件时效率将会非常低。
删除一个文件时，要把磁盘里的目录项inode number清零以便以后使用，并且把被删除的目录项从其父目录的子目录双链表中移到全局变量struct fs_info中的dcache链表中。以后要创建目录项时先到这个链表中看有没有可用的项，没有的话再申请。
==========
接口和功能
==========
已经实现了的接口和功能如下(接口并不是都和vfs相应的函数功能或形式相同)：
/* 根据名字找到对应的inode */
int vfs_namei(struct fs_info *fsi,char *path,struct dentry *de);
/* super operations */
/* mount: 初始化fs_info结构 */
struct fs_info* ofs_mount(const char*);
/* umount: 更新磁盘文件信息并且释放内存 */
void ofs_umount(struct fs_info*);
/* 将超级块内容写回磁盘 */
void ofs_write_super(struct fs_info *fsi);
/* 分配一个新的inode并且初始化 */
struct inode* ofs_alloc_inode(struct fs_info *fsi);
/* 释放内存中的inode */
void ofs_destroy_inode(struct fs_info *fsi,struct inode *inode);
/* 从磁盘中删除给定的inode */
void ofs_delete_inode(struct fs_info *fsi,struct inode *inode);
/* 把磁盘上inode的内容读到内存中 */
void ofs_read_inode(struct fs_info *fsi,struct inode *inode);
/* 把inode的内容写回磁盘 */
void ofs_write_inode(struct fs_info *fsi,struct inode *inode,int wait);
/* inode operations */
/* 在dir中查找给定名字的dentry，如果找到就返回，找不到返回NULL */
struct dentry* ofs_lookup(struct fs_info *fsi,struct inode *dir,
struct dentry *de);
/* 在dir中创建一个新文件，名字由de给定 */
int ofs_create(struct fs_info *fsi,struct inode *dir,
struct dentry *de,int mode);
/* 在dir中创建一个指向old_de的inode的 硬 链接 */
int ofs_link(struct fs_info *fsi,struct dentry *old_de,
struct inode *dir,struct dentry *de);
/* 在dir中删除一个名字由de指定的目录项 */
int ofs_unlink(struct fs_info *fsi,struct inode *dir,
struct dentry *de);
/* 把文件大小变为newsize。如果newsize大于原来的文件，扩充部分填充0 */
int ofs_truncate(struct fs_info *fsi,struct inode *inode,
unsigned long long newsize);
/* 在dir中创建一个名字由de指定的目录 */
int ofs_mkdir(struct fs_info *fsi,struct inode *dir,
struct dentry *de,int mode);
/* 在dir中删除一个名字由de指定的 空 目录 */
int ofs_rmdir(struct fs_info *fsi,struct inode *dir,
struct dentry *de);
/* 将old_dir下的old_de移到new_dir下，并且新名字为new_de */
int ofs_rename(struct fs_info *fsi,
struct inode *old_dir,struct dentry *old_de,
struct inode *new_dir,struct dentry *new_de);
/* file operations */
/* 从文件filp偏移为offset的位置开始读取count字节到buf中 */
unsigned long long ofs_read(struct fs_info *fsi,struct file *filp,
char *buf,unsigned long long count,unsigned long long *offset);
/* 从filp的偏移为offset的位置开始写入buf中的count字节 */
unsigned long long ofs_write(struct fs_info *fsi,struct file *filp,
char *buf,unsigned long long count,unsigned long long *offset);
typedef int (*filldir_t)(void *dirent,const char *name,int namelen,
__u64 offset,__u64 ino,unsigned dentry_type);
/* 每次读取一个目录到dirent中，使用filldir_t的格式填充 */
int ofs_readdir(struct fs_info *fsi,struct file *filp,void *dirent,
filldir_t filldir);
更多接口见ofs.h。应用程序和系统调用的内容分别见cmd.*和syscall.*。
============
写在后面的话
============
从什么都不懂的时候就开始在这混，得到版上各种大牛的帮助，在这衷心地说声谢谢，当然还有自己也在不断地努力。最后希望大家都能从linux中得到收获。
--
十指互扣 一生相守
斡旋天地 补缀乾坤
※ 来源:·北邮人论坛 forum.byr.edu.cn·[FROM: 2001:da8:215:8516:21b:38ff:fe2f:*]