共计 6843 个字符,预计需要花费 18 分钟才能阅读完成。
寒假日常
凌晨,Douyiya 被短促的脚步声吵醒了,室友 狒狒 因为要加入电子设计大赛,所以早早起床拾掇明天所要用到的材料。简略寒暄两句之后,他便急匆匆地走出了寝室。Douyiya 起身观望,又是再相熟不过的场景: 老马 通宵未归, 阿狗 和 龙哥 还在睡梦中。想到 Nanami 和 Nanase 因为天气太过酷热而回家避暑,Douyiya 也只能微微叹了口气,“又是无聊的一天呀!”随后就约着在计算机爱好者社团结识的敌人 Ling,一块去图书馆分享最近学习的感悟。
Douyiya 的汇报
Ling 是一个谈话语速慢慢悠悠,但思维十分麻利,并且涉猎宽泛的技术大佬,所以 Douyiya 也十分喜爱向她求教问题。两人碰面之后互道了早安,随后便找了一个宁静的地位坐了下来。“最近浏览了 ext2 文件系统的源码,想跟你分享一下,顺便帮我看看有没有了解上的谬误。”Douyiya 笑眯眯地说到。“我之前读过这些代码,你间接开始讲吧。” Douyiya 点了拍板:
咱们能够认为操作系统治理着一棵微小的 文件树
,无论是目录文件,还是一般文件,都是树上的一个节点。如果用户指定的是文件的绝对路径,操作系统会从根节点逐级查找,直到定位指标文件;如果是相对路径,则从当前目录下开始查找。所以,目录文件必须要蕴含一些信息,用来示意出它的子文件到底有哪些。ext2 文件系统的设计如下:
/*
* Structure of a directory entry
*/
#define EXT2FS_MAXNAMLEN 255
struct ext2fs_direct {
uint32_t e2d_ino; /* inode number of entry */
uint16_t e2d_reclen; /* length of this record */
uint16_t e2d_namlen; /* length of string in e2d_name */
char e2d_name[EXT2FS_MAXNAMLEN];/* name with length<=EXT2FS_MAXNAMLEN */
};
/*
* The new version of the directory entry. Since EXT2 structures are
* stored in intel byte order, and the name_len field could never be
* bigger than 255 chars, it's safe to reclaim the extra byte for the
* file_type field.
*/
struct ext2fs_direct_2 {
uint32_t e2d_ino; /* inode number of entry */
uint16_t e2d_reclen; /* length of this record */
uint8_t e2d_namlen; /* length of string in e2d_name */
uint8_t e2d_type; /* file type */
char e2d_name[EXT2FS_MAXNAMLEN]; /* name with
* length<=EXT2FS_MAXNAMLEN */
};
e2d_ino
: 文件对应的惟一 inode numbere2d_name
: 寄存文件名的字符数组,最大不超过 255 bytese2d_namlen
: 文件名的长度e2d_type
: 文件类型,比方一般文件、设施文件、目录、链接文件等等-
e2d_reclen
: 与文件名的长度无关,sizeof(uint64_t) + e2d_namelen
该构造体对应两种状态,在磁盘上和在内存中,操作系统首先须要将数据从磁盘读入内存,应用实现之后再回写到磁盘当中。出于节俭空间的思考,在磁盘上给它调配的存储区域大小是
e2d_reclen
,在内存中间接调配sizeof(struct ext2fs_direct_2)
大小的空间
目录也是文件,操作系统会给它调配 inode 和磁盘块。所以咱们只须要将所有目录子文件 对应的 struct ext2fs_direct_2 作为 entry 放到其磁盘块当中,查找的时候通过某种办法遍历这些 entry,就能够晓得该目录下存在哪些子文件。如下图所示:
因为每个文件的名称长度不可能完全一致,所以磁盘块上的每个 entry 所占用空间的大小也是不同的。上图示意的是 entry 的线性排布形式,所以遍历就是从头开始,一个接一个向后解析。然而随着子文件数量的增长,这种办法所破费的工夫会越来越长,影响文件查找效率。为了解决这个问题,开发者们在 ext2 中引入了 hashtree
查找机制。目前还没具体钻研,当前再来填坑。。。
每一个 file entry,可能会在开端还会蕴含一个 struct ext2fs_direct_tail
(并不一定会存在,须要在 ext2 挂载前使能)
struct ext2fs_direct_tail {
uint32_t e2dt_reserved_zero1; /* pretend to be unused */
uint16_t e2dt_rec_len; /* 12 - 固定 12 字节大小 */
uint8_t e2dt_reserved_zero2; /* zero name length */
uint8_t e2dt_reserved_ft; /* 0xDE, fake file type */
uint32_t e2dt_checksum; /* crc32c(uuid+inum+dirblock) */
};
这个构造体是做什么用的呢?其实就是为了对磁盘块中的数据进行校验。数据在磁盘和内容之间流动的时候,可能会存在一些异样操作导致数据损坏。这时操作系统就能够计算 file entry 的 crc32 并与读取出的字段进行比照。如果统一,则能够证实数据没有被损坏。
理论调试中没有用使能该属性,仅仅是从代码逻辑揣测 checksum 对应的是磁盘块中的 entry,而不是整个磁盘块。如果有应用到还是理论验证一下为好
目录并不是变化无穷的,可能在用户应用的过程中会呈现频繁的文件创建和删除,磁盘块中的 file entry 也会随之申请和开释。那操作系统如何确定磁盘块中是否蕴含有足够的空间用于寄存新创建的 file entry?这就波及到另外一个数据结构 struct ext2fs_searchslot
enum slotstatus {
NONE,
COMPACT,
FOUND
};
struct ext2fs_searchslot {
enum slotstatus slotstatus;
doff_t slotoffset; /* offset of area with free space */
int slotsize; /* size of area at slotoffset */
int slotfreespace; /* amount of space free in slot */
int slotneeded; /* sizeof the entry we are seeking */
};
操作系统会利用 struct inode 中的
int32_t i_count; /* Size of free slot in directory. */
doff_t i_endoff; /* End of useful stuff in directory. */
doff_t i_diroff; /* Offset in dir, where we found last entry. */
doff_t i_offset; /* Offset of free space in directory. */
几个字段,查找合乎新创建 file entry 要求的可用空间,并将根本信息保留在 struct ext2fs_searchslot 返回给文件系统下层调用函数,这样就获取到了一个可用的“slot”。
用户有时候会对文件的拜访权限有一些非凡的需要,失常状况下就是设置文件的 owner / group / other 的可读可写可执行等等,更非凡一点就是 SUID / SGID 等。但如果用于想要对某个具体的用户设置更加非凡的拜访权限,那么这种形式就难以胜任了。所以,针对这样的需要,ext2 文件系统就引入了文件的 扩大属性
机制。设计思维就是为文件独自调配一个或者多个磁盘块,并按照 POSIX 中的一些通用办法将某个文件特有的属性信息放到里边。操作系统在解决文件操作时,就会同时查看根本属性和扩大属性,判断该用户时候是否能够拜访此文件。
/*
* Ext4 extent tail with csum
*/
struct ext4_extent_tail {uint32_t et_checksum; /* crc32c(uuid+inum+extent_block) */
};
/*
* Ext4 file system extent on disk.
*/
struct ext4_extent {
uint32_t e_blk; /* first logical block */
uint16_t e_len; /* number of blocks */
uint16_t e_start_hi; /* high 16 bits of physical block */
uint32_t e_start_lo; /* low 32 bits of physical block */
};
/*
* Extent index on disk.
*/
struct ext4_extent_index {
uint32_t ei_blk; /* indexes logical blocks */
uint32_t ei_leaf_lo; /* points to physical block of the
* next level */
uint16_t ei_leaf_hi; /* high 16 bits of physical block */
uint16_t ei_unused;
};
/*
* Extent tree header.
*/
struct ext4_extent_header {
uint16_t eh_magic; /* magic number: 0xf30a */
uint16_t eh_ecount; /* number of valid entries */
uint16_t eh_max; /* capacity of store in entries */
uint16_t eh_depth; /* the depth of extent tree */
uint32_t eh_gen; /* generation of extent tree */
};
/*
* Save cached extent.
*/
struct ext4_extent_cache {
daddr_t ec_start; /* extent start */
uint32_t ec_blk; /* logical block */
uint32_t ec_len;
uint32_t ec_type;
};
/*
* Save path to some extent.
*/
struct ext4_extent_path {
int index_count;
uint16_t ep_depth;
uint64_t ep_blk;
char *ep_data;
struct ext4_extent *ep_ext;
struct ext4_extent_index *ep_index;
struct ext4_extent_header *ep_header;
};
而后扩大属性中最常见的就是 访问控制链表
(ACL,Access Control List)。咱们能够认为它是扩大属性的子集,会对文件拜访属性进行更加粗疏的设置
struct ext2_acl_entry {
int16_t ae_tag;
int16_t ae_perm;
int32_t ae_id;
};
struct ext2_acl_entry_short {
int16_t ae_tag;
int16_t ae_perm;
};
struct ext2_acl_header {int32_t a_version;};
因为自己在新设计的文件系统中没有应用到文件的扩大属性(操作系统自身只有一个特权用户),所以这部分代码并没有在实践中进行测验。小伙伴们如果用到了,也是要亲自调试一下的。有问题也能够留言,一起探讨,相互提高
咱们平时应用的过程中个别不会设置过多的额定属性,所以调配给文件用来寄存扩大属性的磁盘块基本上一个就够了,这些属性 entry 就能够在磁盘块中以线性形式排布,上述数局部据构造就用不到了。如果真呈现了一个文件须要蕴含特地多扩大属性的状况,那文件系统就会以 二叉均衡搜寻树
对它们进行排布和调配磁盘块。(细节还没去钻研,当前有工夫再来填坑 …)
上图只是简略示意图,具体还是要参考 ext2fs disk layout
看完上述这些数据结构之后,咱们就要思考它们在磁盘中到底是如何散布的。现有设计如下:
能够看到,整个磁盘如同是逻辑上被分成了许多局部。这里就要引入 ext2 文件系统中另外一个重要设计,块组
。目前机械磁盘对于数据的拜访还是通过扭转磁头地位的形式实现的,此过程必然会或多或少的破费一些工夫。那就要想方法把这种工夫上的节约降到最低。现实状况就是文件数据是齐全间断存储的,这样只有从数据起始地位间断读取磁盘块即可。尽管不能齐全实现上述情景,但能够将同一个文件的数据存储在间隔尽可能近的、程序排布的磁盘块中。开发者同时联合了磁盘的硬件个性,就在 ext2 文件系统中增加了块组构造,将整个磁盘分为多个组进行治理,为的就是让操作系统可能以最高效率实现对文件的拜访。
/* ext2 file system block group descriptor */
struct ext2_gd {
uint32_t ext2bgd_b_bitmap; /* blocks bitmap block */
uint32_t ext2bgd_i_bitmap; /* inodes bitmap block */
uint32_t ext2bgd_i_tables; /* inodes table block */
uint16_t ext2bgd_nbfree; /* number of free blocks */
uint16_t ext2bgd_nifree; /* number of free inodes */
uint16_t ext2bgd_ndirs; /* number of directories */
uint16_t ext4bgd_flags; /* block group flags */
uint32_t ext4bgd_x_bitmap; /* snapshot exclusion bitmap loc. */
uint16_t ext4bgd_b_bmap_csum; /* block bitmap checksum */
uint16_t ext4bgd_i_bmap_csum; /* inode bitmap checksum */
uint16_t ext4bgd_i_unused; /* unused inode count */
uint16_t ext4bgd_csum; /* group descriptor checksum */
uint32_t ext4bgd_b_bitmap_hi; /* high bits of blocks bitmap block */
uint32_t ext4bgd_i_bitmap_hi; /* high bits of inodes bitmap block */
uint32_t ext4bgd_i_tables_hi; /* high bits of inodes table block */
uint16_t ext4bgd_nbfree_hi; /* high bits of number of free blocks */
uint16_t ext4bgd_nifree_hi; /* high bits of number of free inodes */
uint16_t ext4bgd_ndirs_hi; /* high bits of number of directories */
uint16_t ext4bgd_i_unused_hi; /* high bits of unused inode count */
uint32_t ext4bgd_x_bitmap_hi; /* high bits of snapshot exclusion */
uint16_t ext4bgd_b_bmap_csum_hi;/* high bits of block bitmap checksum */
uint16_t ext4bgd_i_bmap_csum_hi;/* high bits of inode bitmap checksum */
uint32_t ext4bgd_reserved;
};
块组跟超级快的内容十分相似,只不过超级快是治理整个磁盘,而块组只是治理以后组。所以,文件系统给文件调配磁盘块时,会优先思考以后块组中存在的闲暇块。如果被全副占用,才会去其余块组中寻找可用块。
未完待续
Ling 听完了 Douyiya 的解说,连连拍板:“基本上没什么大问题。不过目前只是看了这些吗,函数的代码有没有看?”“昂,,还没有,最近花了点工夫练习钢琴,杰伦的《晴天》,哈哈哈!”
Ling 听完笑着说道:“不错不错!那我感觉你前面能够先读 inode 和磁盘块调配相干实现代码,这两局部是文件系统最根底的性能之一。”Douyiya 笑着答复到:“好,我晓得了。”