文章目录
  1. 1. 缘起
  2. 2. MINIX FS简介
  3. 3. 准备工作
  4. 4. 磁盘布局
  5. 5. Block cache
  6. 6. 初始化
  7. 7. 文件读取
  8. 8. 路径
  9. 9. 总结
  10. 10. References

files

缘起

前一段时间听airtrack说他在写文件系统,写起来很麻烦,“一个mkfs工具就快1000行代码了”。很早之前就看到他在写内核,貌似是15年上半年就开始,虽然节奏比较慢,但是非常持之以恒,写到了16年。而我就没什么耐心,实现了一些基本功能之后就没什么兴趣了,实在是惭愧。

听他那么一说,于是决定也写一个文件系统试试,找了找资料,好像也不是很难的样子。遂决定从MINIX入手,写一个玩具版的FS。

MINIX FS简介

MINIX文件系统是MINIX操作系统原生的文件系统。说到MINIX,它是 Andrew S. Tanenbaum在80年代写的一个用于教学的操作系统,采用了微内核,模仿了Unix系统,但是代码比较clean,可读性也会比较好。由于是用于教学,MINIX文件系统只实现了一些基本的功能,因此比较精简。再后来Linus开发Linux0.11的时候,也是参照这个文件系统来实现的。不过Linux跟MINIX很大的一个区别就是内核架构,Linux是宏内核,MINIX是微内核。

MINIX采用了索引式分配,实现了树形目录结构,对磁盘有一个缓冲层,支持管道等功能。

准备工作

为了实现文件系统,我们首先需要一个磁盘,来承载这个文件系统。我这里使用了qemu虚拟机,它支持磁盘镜像的挂载,所以我们现在需要做的就是创建一个磁盘镜像,把它格式化成MINIX 文件系统。

1
2
dd if=/dev/zero of=hdd.img bs=1M count=10
mkfs.minix -i 128 hdd.img

这就搞定了,用dd创建一个10MB的磁盘镜像,然后用mkfs个格式化一下。那个-i参数是指定inode的数量,当然还有其他一些参数也可以设定。

接着就是挂载,也是轻而易举:

1
qemu  -kernel ./Sprite -hda hdd.img

我这里直接用-kernel来挂载了我的内核(Sprite),就不用把这个内核写到软盘镜像或者硬盘镜像还要安装grub什么的。

磁盘镜像的事情已经搞定,接下来就是磁盘驱动。这部分代码不在我们的讨论范畴之内,只是简单看一下磁盘的读写接口:

1
2
int ide_read_secs(uint32_t secno, void* dst, uint32_t nsecs);
int ide_write_secs(uint32_t secon, const void* src, uint32_t nsecs);

ide_read_secs就是读磁盘,secno是扇区号(准确地讲是LBA地址),从0开始,dst就不用说了,nsecs是读的扇区数量。磁盘驱动通常会有一次读写的扇区数量限制,不过我在这里已经把这部分处理写到驱动里了,所以这里的nsecs理论上讲可以是非常大,没有什么限制。

从这个接口也可以看出,磁盘读写都是以扇区为单位,通常大小是512byte。地址空间也可以当做是线性的地址空间,这个地址最终会映射到磁道、扇区、簇什么的。所以所谓文件系统,就是对这么一个空间的管理,看起来跟写一个内存分配器很像?

磁盘布局

首先来看一下MINIX FS的磁盘布局:
fs layout

  • bootblock: 引导块,包括系统的引导代码,和分区表。跟我们没关系
  • superblock:超级块,每个磁盘分区都会有超级块,记录了文件系统的元数据。顺便说一句,每个磁盘分区都可以安装不同的文件系统,所以一个文件系统的管理范围通常就是一个分区。
  • inode bitmap:用来记录inode的分配情况
  • zone bitmap:用来记录文件区域的分配情况
  • inodes:存放inode
  • file data blocks: 存放真正的文件数据

首先什么是block?在这里它不仅是一个概念上的称呼,还是一个计量单位,通常是1KB。所以boot block、super block它们占据的空间都是1KB。我们可以认为block就是MINIX FS磁盘管理的最小单位了。

除了block之外,还有一个单位是zone,它的存在是为了提高磁盘IO性能。对于机械硬盘来说,通常认为一次读很多数据,比多次读小的数据要来得快,因为涉及到磁头的移动什么的。因此在磁盘空间分配的时候,就把分配的单位定为zone,可以是1个block,4个block等等。不过把最小分配单位增大也有坏处,就是会增加内部碎片,一个1byte的文件至少要占据一个zone的空间,是比较浪费的。所以为了权衡性能和空间利用率,设置了一个不大不小的zone。mkfs设置的默认zone大小和block一致,都是1KB。

inode,在MINIX FS中直接存放在特定的区域。inode记录了文件的元数据,由于是采用索引分配,所以它基本记录了文件的大小,数据位置,修改时间,权限等等信息。每个inode对应一个文件,不过这里的文件指的是广义的文件,出了regular file之外,还包括目录。也就是说,MINIX FS中目录其实就是一种特殊的文件。熟悉Linux的同学应该还知道link,那么link是怎么实现的呢,如果是hard link,其实就是另外一个inode,指向了目标文件的数据,换言之就是两个inode指向了同一个文件。

OK,基本结构就是这样,下面看一下结构体的定义:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
struct d_inode {
uint16_t mode; // file type and RWX mode
uint16_t uid; // user ID
uint32_t size; // file size
uint32_t mtime; // modify time since 1970
uint8_t gid; // group id
uint8_t num_links; // hard link number
uint16_t zone[9]; // zone[0] ~ zone[6] direct pointer, zone[7] points to first level index
// table, zone[8] second level.
} __attribute__((packed));

/**
* in memory inode
*/

struct m_inode {
uint16_t mode;
uint16_t uid;
uint32_t size;
uint32_t mtime;
uint8_t gid;
uint8_t num_links;
uint16_t zone[9];

task_struct* wait;
uint32_t atime;
uint32_t ctime;
uint16_t dev;
uint16_t num;
uint16_t count;
uint8_t lock;
uint8_t dir;
uint8_t pipe;
uint8_t mount;
uint8_t seek;
uint8_t update;
} __attribute__((packed));

struct super_block {
uint16_t num_inodes;
uint16_t num_zones;
uint16_t num_imap_blocks;
uint16_t num_zmap_blocks;
uint16_t first_data_zone;
uint16_t log_zone_size;
uint32_t max_size;
uint16_t magic;
/* These are only in memory */
uint16_t dev;
m_inode* isup;
m_inode* imount;
uint32_t time;
task_struct* wait;
uint8_t lock;
uint8_t rd_only;
uint8_t dirt;
} __attribute__((packed));

struct d_super_block {
uint16_t num_inodes;
uint16_t num_zones;
uint16_t num_imap_blocks;
uint16_t num_zmap_blocks;
uint16_t first_data_zone;
uint16_t log_zone_size;
uint32_t max_size;
uint16_t magic;
} __attribute__((packed));

struct dir_entry {
uint16_t inode;
char name[kNameLen];
} __attribute__((packed));

这里的superblock和inode定义都有两种,一个是磁盘中的,一个在内存中。在磁盘中的结构我们不能修改,不过在内存中的其实可以根据需要修改。

Block cache

按理说接下来要做的就是把这些磁盘中的数据载入内存,但是还要等等,在此之前我们需要先实现缓冲区。

block cache是为了提高文件系统系统的性能。这个block cache事实上起到了两个作用,一是buffer,二是cache。首先是buffer,由于磁盘一次至少读一个扇区,所以我们读数据的时候需要一个缓冲区,把一个扇区的数据读到缓冲区里,再进行操作;而这个缓冲区的内存由block cache统一管理,所以我们可以重用缓冲区,来实现缓存。比如说一个线程读了某一个扇区,另一个线程再来读,就不用再去磁盘读取了,可以从缓存里来拿。

缓冲区的大小是一个block,定义如下:

1
2
3
4
5
struct block_buffer {
uint8_t data[kBlockSize]; /* block data */
uint8_t count; /* users using this block */
uint8_t lock; /* 0 - ok, 1 -locked */
};

我这里把很多东西都删了,跟Linux 0.11的写法有些出入。由于data是在结构体的开头,所以我们如果拿到block_buffer的指针,可以直接当做buffer来用,不用再buff->data,省了一点麻烦。

至于缓存的实现,就有很大的发挥空间。我实现了一个LRU,大致接口如下:

1
2
3
4
5
6
7
8
9
10
11
template <class T, size_t N>
class LRUCache {
public:
using uncache_callback = void (*)(size_t, T*);

void SetUncacheHandler(uncache_callback cb);

T* Alloc(size_t key);

T* Get(size_t key);
};

Alloc是分配一个缓存,返回指针;Get则是拿缓存,如果miss返回nullptr;至于SetUncacheHandler,是设置当缓存失效时的一个回调,通常来说如果要取消一个缓存,要先把内存的数据写到磁盘里,这里的回调就是这个意思。

缓冲区和缓存都有了,接下来就是把它们封装到一起:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
LRUCache<block_buffer, 307> g_block_cache;

block_buffer* get_block(uint32_t bno) {
auto buff = g_block_cache.Get(bno);
if (!buff) {
buff = g_block_cache.Alloc(bno);
}
return buff;
}

block_buffer* read_block(uint32_t bno) {
// the data in cache is always uptodate, so we could directly return it
auto buff = g_block_cache.Get(bno);
if (!buff) {
buff = g_block_cache.Alloc(bno);
ide_read_secs(block_to_sector(bno), buff, block_to_sector(1));
}
return buff;
}

bool write_block(uint32_t bno) {
if (auto buff = g_block_cache.Get(bno)) {
ide_write_secs(block_to_sector(bno), buff, block_to_sector(1));
return true;
}
return false;
}

read不用说,而write之前需要先用get获取缓冲区,把数据写到缓冲区里,然后write一下。有了这个接口之后,我们就可以读写磁盘数据了。

初始化

FS的初始化就是要把这些磁盘中的数据读入内存,包括super block, inode bitmap, zone bitmap, inodes。说来也简单,在内存中定义好这些结构,然后读入一下就好了。

这些数据定义成全局变量:

1
2
3
4
5
extern super_block g_super_block;           
extern LRUCache<block_buffer, 307> g_block_cache;
extern m_inode g_inode_table[kNumInodes];
extern bitmap<128> g_imap;
extern bitmap<10240> g_zmap;

读入的话,会有一点小问题,因为磁盘是按块读,不连续的,而这些数据内存都是连续的,要如何对接呢?所以我写了一个高级的接口,用来读多个block:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <class Input, class Output>
bool read_blocks(size_t start_bno, void* dst, size_t count, size_t size) {
auto block = reinterpret_cast<Input*>(read_block(start_bno));
auto src = block;
auto dst_ = reinterpret_cast<Output*>(dst);

for (int i = 0; i < count; i++, dst_++, src++) {
if ((uint8_t*)src >= (uint8_t*)block + kBlockSize) {
src = block = reinterpret_cast<Input*>(read_block(++start_bno));
if (!src) return false;
}
memcpy(dst_, src, size);
}
return true;
}

这个函数实现了读取磁盘上的结构到内存里:start_bno,起始的block地址;dst,目标地址;count,结构体的数量;size,每个结构体要拷贝的大小。模版参数都需要手动指定,不使用自动推导,Input是磁盘中的结构体类型,Output是内存中的结构体类型,之所以会有两个,是因为很多时候同一个数据我们希望拷贝到内存中可以附加其他一些信息,也就是说结构体会不一致。

例如,要读取所有的inode到内存,只要这样:

1
2
3
int block_start = 2 + g_super_block.num_imap_blocks + g_super_block.num_zmap_blocks;
read_blocks<d_inode, m_inode>(block_start, g_inode_table + 1, g_super_block.num_inodes,
sizeof(d_inode));

这里磁盘中的inode和内存里的就不一样,分别是d_inode和m_inode,每次拷贝的数据是d_inode的大小,而inode的数量是g_super_block.num_inodes

其他数据的载入也是与此类似:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// init super block
memcpy(&g_super_block, read_block(kSuperBlockBNO), sizeof(g_super_block));
// init block cache
g_block_cache.SetUncacheCallback(&uncache);
// init inode table
int block_start = 2 + g_super_block.num_imap_blocks + g_super_block.num_zmap_blocks;
read_blocks<d_inode, m_inode>(block_start, g_inode_table + 1, g_super_block.num_inodes,
sizeof(d_inode));
// init bitmap
int imap_start = 2;
read_blocks<uint8_t, uint8_t>(imap_start, g_imap.data_, g_super_block.num_inodes / 8,
sizeof(uint8_t));
int zmap_start = 2 + g_super_block.num_imap_blocks;
read_blocks<uint8_t, uint8_t>(zmap_start, g_zmap.data_, g_super_block.num_zones / 8,
sizeof(uint8_t));

到这里,基本实现了文件系统元数据的读取,接下来要做的,就是如何读一个文件。

文件读取

在索引式文件系统中,文件的数据不一定是连续的。文件会被分为很多小的zone,分布在磁盘的各个位置,这个也称为fragmentation。这种技术很常用,在内存管理中也用到了这样的技术。

这些位置记录在inode中,用2byte记录一个zone的位置,如果只是直接记录地址,那么也就是2byte => 1KB,那么每个inode要用多少大小来记录呢?如果太小,导致文件的大小也会被限制,如果花比较大的空间来记录位置,那么对小文件来说它可能只需要1个zone,那就太浪费了。所以这里采用了多级索引的技术,跟虚拟内存分页的多级页表非常像。

inode

这里使用两级的索引表,所以文件最大是7 + 512 + 512×512个zone。由于多级索引,所以文件的数据也是不连续,对读取造成了一些小困难,我们为文件读取封装一个跟好用的接口:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
block_buffer* read_zone(const m_inode* inode, uint32_t zone) {
if (zone < 7) {
return read_block(inode->zone[zone]);
} else if (zone < 7 + 512) {
zone -= 7;
auto zones = reinterpret_cast<uint16_t*>(read_block(inode->zone[7]));
return read_block(zones[zone]);
} else {
zone -= 7 + 512;
auto zone_table = reinterpret_cast<uint16_t*>(read_block(inode->zone[8]));
auto zones = reinterpret_cast<uint16_t*>(read_block(zone_table[zone / 512]));
return read_block(zones[zone % 512]);
}
}

分了三级,第一级直接读取,第二级先读索引表,然后读数据。于是乎,我们可以尝试着读一个文件了。

由于现在磁盘中还没有文件,我们可以读一下根目录的数据(它的inode 编号是1):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
printk("files in /\nname\tsize\ttype\n");
auto dir = &g_inode_table[kRootINO];
int zone_cnt = 0;
auto zone = reinterpret_cast<dir_entry*>(read_zone(dir, zone_cnt));
auto entry = zone;
int num_entries = dir->size / sizeof(dir_entry);

for (int i = 0; i < num_entries; i++, ++entry) {
if ((uint8_t*)entry >= (uint8_t*)zone + kZoneSize) {
zone = entry = reinterpret_cast<dir_entry*>(read_zone(dir, ++zone_cnt));
}
auto node = g_inode_table + entry->inode;
printk("%s\t%d\t%s\n", entry->name, node->size,
is_directory(node->mode) ? "dir" : "file");
}

于是乎得到了这样的结果:

结果

根目录下有两个文件,. 和 ..,应该不陌生吧?

路径

接下来我们要实现目录和路径。先在镜像中创建一个目录,以及一个文件。

1
2
3
4
sudo mount hdd.img /mnt/kernel
mkdir /mnt/kernel/test
echo "helloworld" > /mnt/kernel/test/test.txt
sudo umount /mnt/kernel

以及相关的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
template <class Fn>
m_inode* traverse_dir(const m_inode* dir, Fn cb) {
if (!is_directory(dir->mode)) return nullptr;

int zone_cnt = 0;
auto zone = reinterpret_cast<dir_entry*>(read_zone(dir, zone_cnt));
auto entry = zone;
int num_entries = dir->size / sizeof(dir_entry);

for (int i = 0; i < num_entries; i++, ++entry) {
if ((uint8_t*)entry >= (uint8_t*)zone + kZoneSize) {
zone = entry = reinterpret_cast<dir_entry*>(read_zone(dir, ++zone_cnt));
}
if (cb(entry)) return g_inode_table + entry->inode;
}
return nullptr;
}

/**
* Find an entry in a dir, it could be a directory or a regular file.
*/

m_inode* find_entry(const m_inode* dir, const char* name) {
if (!is_directory(dir->mode)) return nullptr;

return traverse_dir(dir, [name](dir_entry* entry) { return strcmp(entry->name, name) == 0; });
}

/**
* Find the inode for the specific name
*/

m_inode* namei(const char* path) {
assert(path[0] == '/', "path must start with /");
m_inode* inode = g_inode_table + kRootINO;
const char* delim = path;

while (true) {
path = delim + 1;
delim = strfind(path, '/');
inode = find_entry(inode, path);
if (!*delim) // reach the last entry
break;
}
return inode;
}

traver_dir用来遍历目录,在此基础上实现了文件查找和路径的解析。路径解析写的比较简陋,只能从根目录开始,也没有什么鲁棒性,不过基本够用了。

所以,可以借此来读一个文件了:

1
2
3
4
if (auto node = namei("/test/test.txt")) {
auto contents = reinterpret_cast<char*>(read_zone(node, 0));
printk("size: %d; contents of test.txt: %s\n", node->size, contents);
}

轻松愉快。

总结

很遗憾,到这里就没有了,接下来其实还有很大的发挥空间,不过因为我要期末考试了,就先写到这里了。

References

文章目录
  1. 1. 缘起
  2. 2. MINIX FS简介
  3. 3. 准备工作
  4. 4. 磁盘布局
  5. 5. Block cache
  6. 6. 初始化
  7. 7. 文件读取
  8. 8. 路径
  9. 9. 总结
  10. 10. References