骆远辉 2017202013 李金涛 2017202008
本次实验的分工 :
块的组织结构 和 inode的组织结构由两人共同设计
此外还有一些轮子, 以及重要函数的写法, 是两个人都实现, 然后互相review, 所以算作两人都完成了
具体函数的实现:
其中绿色是李金涛实现的, 灰色是骆远辉实现的.
另外: mkfs是李金涛实现的, open, release, opendir, releasedir全部空缺
==两人的报告是一样的==
本次实验各个函数间 逻辑耦合程度较高, 轮子接口共用较多, 详细的分工见下面的实现细节.
如果分开写报告重复程度很高, 故采取写在同一份报告, 注明该部分实现者的方式区分
本次实验的github项目: https://github.com/Losk-x/fslab
注: 合作编程是通过vscode的live share来写的, commit的代码贡献者不代表相应的代码实现者
#define BLOCK_SIZE 4096
#define BLOCK_NUM 65536
#define DISK_SIZE (BLOCK_SIZE*BLOCK_NUM)
相应需求：
- 至少250MB的真实可用空间
- 至少支持32768个文件及目录
- 只需支持单个文件最大8MB，如果有能力可以支持更大的单文件大小（存在额外测试点）。
- 只需支持文件名最大长度为24字符，且同一目录下不存在名称相同的文件或目录。
$$have: \block\ id\ 65536 = 64 * 1024 = 64K\ storage\ size\block\ size\ 4096 B = 4 KB\ storage\ size \total\ size = 256 MB \need:\250M \ or \ 32768 * 8 \ MB = 256 \ MB \ blocks\ total\ size\manage\ block: 0 - 6MB \manage\ block: super\ block+map\ block+inode\ block \super\ block = 1\ blk \free\ block= \frac{252M}{4K} = 63K \free\ block\ bitmap = \frac{63K}{84K} = 2\ blk\inode\ bitmap = \frac{32768}{84K} = 1\ blk\ (wrong\ calc)\\ inode\ block = 32768 \alpha\ B = 32\alpha\ KB = 8*\alpha\ blk\ ,\ \alpha = 72 \ (wrong\ calc)\ inode\ per\ block = \frac{4096}{72} \approx 56 \ inode\ block = \frac{32768}{56} \approx 586\ manage\ blk = 586+1+2+1 = 590 \manage\ blk\ size = 590*4K \approx 2.3M$$
File System Map(similar to VSFS):
Super block \ inode map \ free data block map \
inode block \ data block
(i = sizeof(inode)) = 72
+-------+--------+--------+-----------+------------------+
| S:1db | im:1db | dm:2db | inode:8*i | data blocks |
+-------+--------+--------+-----------+------------------+
Total Size: 256MB
Manage Size: 2.3MB
Data Size: 250MB
Other Size: 3.7MB
注:
db = data block, 即占用多少个块
S = super block
im = inode bmap
dm = free data block bitmap
inode = inode block
需要支持文件最大为8MB，即为
用块偏移地址表示block pinter的地址：
struct stat {
mode_t st_mode; //文件对应的模式
nlink_t st_nlink = 1;//文件的链接数
uid_t st_uid = getuid(); //文件所有者
gid_t st_gid = getgid(); //文件所有者的组
off_t st_size; //文件字节数
time_t st_atime;//被访问的时间
time_t st_mtime;//被修改的时间
time_t st_ctime;//状态改变时间
};
在inode中~~st_nlink,st_uid,st_gid~~不用储存. 原因是只需支持单用户单线程访问，不必考虑权限问题；并且没有link()
除了指针外, 还得有个变量来记录各个指针使用了多少, 即direct pointer使用了多少, indirect pointer使用了多少等
采用了pointer_bmap, 即 bitmap = [cbbaaaa] 的形式, 其中c代表double indirect pointer的使用情况, b 代表 indirect pointer, c代表 direct pointer.
(后续发现, 我们保证了所有文件的连续性, 可以直接通过size来计算出各类指针用了多少, 但最开始设计时, 以为目录的data block是可以不连续的, 后面会有关于这个问题的讨论)
struct Inode {
mode_t mode;
off_t size;
time_t atime;
time_t mtime;
time_t ctime;
unsigned char pointer_bmap;
unsigned short dir_pointer[12];
unsigned short ind_pointer[2];
unsigned short doub_ind_pointer;
};
//下文中的"指针" 即表示通过offset来表示块的编号的指示方法==指针的顺序==: 先按顺序写dir_pointer中的块, 再写ind_pointer指向两个指针块中顺序存储的指针指向的块, 最后是doub_ind_pointer中顺序的块.
共同实现的细节, 返回值均用来返回ErrorFlag, 处理错误情况, 其余通过指针传参来解决
下面是一些轮子及实现细节.
两人共同实现
int get_inode(const char* path,struct Inode ** inode);
int get_inode_idir(const char* filename, int dir_inode_num); // get inode in directory
int get_inode_iblk(int inode_num, struct Inode** inode); // get inode in inode_block
int free_inode_blk_buffer(int inode_num,struct Inode** inode) //free inode_block's bufferget_inode 即通过文件路径, 得到相应的inode,
其中inode相应的block, 通过堆中的内存暂时储存, 故需要一个free_inode_blk_buffer函数
主要由李金涛实现
int bitmap_opt(int mode, int num, int bmap_num); //free or alloc num of bmap_num
int imap_opt(int mode, int inode_num);
int bmap_cnt(int bmap_num);
//num 即相应的inode或者是block的编号, bmap_num即bmap的块的编号bmap_cnt 是数bmap中'0' bit的个数, 对应未分配的部分
主要由李金涛实现部分
int get_fblk_num(); //获取 free_data_block 的数量
int find_fblk(int num, unsigned short *fblk_list);
//获取num个free_block, 其"指针"存在fblk_list中, 已修改free_data_block_bmap
int inode_ptr_add(int inode_num, int ptr_num, unsigned short *ptr_list);
//将ptr_list中的"指针"填入inode的pointer中
int indoe_ptr_del(int inode_num, int start_ptr_num);
//将start_ptr_num(第一个要删除的指针号,即数据储存的block中的顺序编号)之后的指针全部free
int rm_file_in_parent_dir(const char *child_file_path);
//在父目录的数据块中删除文件的项
int write_to_blk(unsigned short* blk_ptr,size_t len,void* buffer,size_t size,off_t offset);
//将buffer中的数据,写入blk_ptr指向的块中骆远辉实现部分
int alloc_blk(int inode_num,size_t append_size,unsigned short* blk_ptr,size_t *len,off_t *offset);
//为inode_num的inode分配append_size所需的块, append_size需要填充的存储在blk_ptr中 (也有可能不需要分配)
//配合write_to_blk来写入数据文件夹中填充的项为
struct DirPair{
int inode_num; // == -1 by default (if not a name)
char name[NAME_MAX_LEN+1];
};此处需要指出, 我们指向数据块的"指针", 的offset是相对数据块的开始block_num的offset, 而非相对于0的
所以(unsigned short)-1指向的数据块是不存在的. (计算可得, 通过(unsigned short)-1 来表示空的表项.
最开始, 我们删除文件项的方法, 是在目录的数据块中, 找到相应的表项, 将其inode_num置为-1即可. 初始化将整个块 memset(buffer,-1,BLOCK_SIZE);, 插入新的项通过first fit策略插入即可.
但是, 我们采用了另一个删除文件项的方法, 即找到需删除的表项后, 将目录末尾最后一个表项覆盖写到删除表项的位置, 以保证目录的数据连续性. 这是为了:
- 统一抽象接口, 保证了目录数据的连续性之后, 可以目录看做一般文件 (其内容必连续) 抽象上统一后可以统一接口实现
- 原方法再append添加表项时, 需分配新的块, 此时需要通过目录的size来判断文件末尾的位置, 但由于目录数据未必连续, 所以无法通过size来判定目录的末尾, 处理比较麻烦.
综上, 我们保证目录数据的连续性, 删除时: 将最后一个表项覆盖写入需删除表项的位置; 插入时: APPEND插入到文件末尾.
由于indirect pointer和double indirect pointer是的指针存在块中, 读取和写入时需要逐层次的写入.这种层级写入实际上是机械化的重复, 带来了很大不便.
我们将indirect pointer和double indirect pointer和direct pointer统一抽象为 pointer数组, 即unsigned short ptr_list[] (有时也称为blk_ptr), 读取和写入时统一往这个数组中写入即可.
(读取部分的代码写的比较早, 而且读文件夹和读文件的细节( 文件夹需要调用filler )不完全一致, 所以并未采用统一的抽象)
相应配套的接口
int alloc_blk(int inode_num,size_t append_size,unsigned short* blk_ptr,size_t *len,off_t *offset);
int write_to_blk(unsigned short* blk_ptr,size_t len,void* buffer,size_t size,off_t offset);通过alloc_blk来分配新的块, 通过write_to_blk来写入到这些块中
创建文件和创建目录的很多操作是共通的, 故统一实现:
int mkfile (const char *path,int is_dir);值得一提的是, mkfile中目录和普通文件的区别, 不仅仅是mode的区别. 目录需要初始化时即分配一个空的块, 而文件不用, 因为目录初始化后即需要支持cd操作.
删除文件和删除目录的操作也大多共通, 统一实现:
int rmfile(const char* path);并且出于rename的需要, 将从父目录中删除文件对应的表项这一操作独立出来
int rm_file_in_parent_dir(const char *child_file_path);rename对应的mv函数, 实际上与该文件的数据毫无关系, 本质是在旧路径的父目录数据块中删除一个表项, 再在新路径的父目录数据块中新增一个新name的表项.
-
师兄给的
#define DIRMODE S_IFDIR|0755和#define REGMODE S_IFREG|0644并不安全, 运算时优先级会有错应改为
#define DIRMODE (S_IFDIR|0755)和#define REGMODE (S_IFREG|0644)另外 宏定义的名字曾经不太清晰, 比如一个块中含"指针"的最大值 曾经是
#define PTR_PBLK但会有歧义, 后改为#define PTR_MAX_PBLK另外,
INODE_BASE和INODE_BMAP_BASE在代码补全时容易出现混淆错误, 后者应该替换为BMAP_INODE_BASE -
一开始有个致命的问题是 以为修改了
disk_read(block_id,buffer)中buffer就可以落盘, 但实际上还得disk_write(block_id,buffer)另外, 指针传参时, 我们封装的
get_inode(const char*,struct Inode**)第二处是struct Inode*, 简单的以为传指针就可以修改了, 但实际上在外部也是struct Inode*, 并且未对此封装, 导致外部的struct Inode*实际上未修改由于多层的封装, 返回了指向局部变量的指针,
fs_*调用的get_inode调用了get_inode_iblk函数, 但没有传入一个供disk_read的buffer, 导致返回的指针指向的buffer, 实际上是get_inode_iblk中的一个局部变量, 后采用动态分配内存的方法处理了对
void*的理解,disk_read()时以为传入一个指针即可, 实际上disk_read()是需要已分配内存的buffer的指针来填充数据, 所以不能只传一个未分配内存的指针. -
具体落实到read, write的问题见上面部分"实现细节", 其余问题见反思总结的优缺点.
-
对应tutorial中的==在完成一个操作时，要考虑如果出现错误，应该如何回到这步操作进行之前的状态==
实际上就是对各操作原子性的要求, 即要么操作成功, 要么和从未操作的状态相同.
想要保证原子性, 应该将disk_write的更新置于文件的末尾, 统一更新.
- 相对上次合作: 这次有版本控制, 有共享编程 的环境, 合作效率更高了
- 注释的改进: 函数的说明更加详细丰富规范, 且对错误的指出和warning有很多的细节
- 双份实现, 互相review: 保证了重要功能的正确实现, 以及两人都掌握了解实现细节
- 抽象设计: 这次实验实现前, 我们有统一的讨论, 需求分析, 逻辑抽象等
- 逻辑先行的编程习惯: 本次实现逻辑很复杂, 后面采用的编程方式是, 先通过注释写清楚思路细节, 然后再填充的方法, 保证了大思路和逻辑的连贯性, 也有相应的注释
- 鲁棒性及错误处理: 本次辅助函数统一的返回值都是错误的errorflag, 并根据返回值有相应的输出提示和错误处理. 虽然增加了代码量, 但减轻了调试难度
- 广泛使用宏定义: 除了
#define DEBUG来统一管理调试信息外, 对各种常量都通过宏定义来处理了
-
实现时间过长: 由于近期ddl较多, 整体代码写的断断续续的, 战线拉的过长, 甚至导致了对自己写的轮子接口的遗忘和混淆, 从而产生了许多调用自己轮子产生的错误
-
错误以及bug的原因未及时归纳总结: 很多bug前面注意到了, 但后面却又犯了, 或者一方注意到了, 另外一方犯了, 下次合作时应记一个编程实现的错误备忘录, 每次开始写之前先过一边轮子的接口和备忘录, 以减少实现上反复出现的错误.
-
错误处理的冗余和无效: 有时候错误处理是统一的, 但由于我们没封装好 (或者是disk_read和disk_write这种没有在更上层封装错误处理) 而导致代码冗余情况很多(全是printf), 另外输出的错误提示, 因为偷懒不够详细, 从而无法指示出错的位置.
-
复制粘贴的错误: 本次实现时经常性的复制粘贴代码, 复制粘贴微调后有很多错, 如: 复制了一段二重循环, 通过return退出, 草率的替换成break.等, 而且如果复制的源代码出错了, 导致修改复杂. 这反映了我们对小函数抽象的不重视, 导致了代码冗余.
-
变量命名: 一开始有些变量命名过于简单且无意义, 后来因为要review代码而改正 而且统一了几处命名. 但还是会有混淆的, 比如通过 num来表示编号, 但也有些是通过num来表示数量, 后面改成cnt来表示数量. 下次应该对变量的命名做一个统一的参照表. 而且用id来表示编号会更好, 减少num这种歧义词
-
DEBUG效率低: 由于本次实验的特殊性, debug主要通过输出调试, 但输出调试时对各个block的细节看的也不是很好, 下次应该写好辅助的调试函数来输出block的信息细节以更好的可视化