实验4补充材料：辅助函数与宏定义速查¶

定位

本文是实验4：语义文件系统的补充材料，列出 kernel/fs/fat16fs.c 和 kernel/fs/bptree.c 中你需要实现的部分代码中可能会用到的宏定义、结构体字段和辅助函数。

建议同学们先阅读实验 4 的实验要求与 FAT16 文件系统简介，了解本操作系统实现的文件系统与文件属性系统后，在实现时对照此文档使用。如果你在阅读时发现有名词看不懂或者有歧义，可以在实验要求与 FAT16 文件系统简介中先行查询，如果仍有困惑，请直接反馈给助教。

标题中标有 需要实现 的函数是同学们需要先自行实现然后再在其他函数中调用的；标题中标有 Bonus 需要实现 的函数属于 B+ 树 Bonus。

1. 基础结构¶

1.1 `struct dirent`¶

即文件目录项，位置：kernel/include/file.h，定义如下：

struct dirent {
    uchar name[11];
    uchar attr;
    uchar ntres;
    uchar crt_time_tenth;
    ushort crt_time;
    ushort crt_date;
    ushort last_acc_date;
    ushort first_cluster_hi;
    ushort wrt_time;
    ushort wrt_date;
    ushort first_cluster_lo;
    uint file_size;
} __attribute__((packed));

重要字段：

name[11]：FAT16 8.3 短文件名，前 8 字节为主文件名，后 3 字节为扩展名。
attr：属性位，标志该文件是只读的、隐藏的、普通文件或目录等信息。
first_cluster_hi、first_cluster_lo：首簇号的高 16 位和低 16 位。
file_size：普通文件的有效字节长度；目录固定为 0。

1.2 `struct inode`¶

即文件在内存中的索引结点，位置：kernel/include/file.h

重要字段：

ip->dev：设备号，读写文件数据扇区时传给 bread()。
ip->type：上层 inode 类型，常见值为 T_FILE 和 T_DIR。
ip->size：普通文件为有效字节数；目录为该目录可以使用的字节长度。
ip->addrs[0]：FAT16 文件或子目录的首簇号。
ip->addrs[1]：该 inode 对应标准目录项所在扇区号。
ip->addrs[2]：该 inode 对应标准目录项在扇区内的字节偏移。

1.3 `struct fat16_slot`¶

即 FAT16 文件槽，也是在内存中的，磁盘上没有这个结构，位置：kernel/fs/fat16fs.c

struct fat16_slot {
    struct dirent entry;
    uint sector;
    uint offset;
    uint index;
};

字段：

entry：该槽位中的 FAT16 32B 目录项内容。
sector：该目录项所在扇区号。
offset：该目录项在扇区内的字节偏移。
index：该目录项在所在目录中的按目录项索引，即如果它是第 0 个目录项则该字段为 0。

2. 重要宏定义¶

2.1 磁盘块与 FAT16 区域¶

名称	位置	含义
`BSIZE`	`kernel/include/buf.h`	磁盘块大小，当前为 512 字节
`FAT16_DIR_ENTRY_SIZE`	`kernel/fs/fat16fs.c`	FAT16 目录项大小，固定为 32 字节
`FAT16_ROOT_INUM`	`kernel/fs/fat16fs.c`	FAT16 根目录的内存 inode 编号
`FAT16_ENTRIES_PER_SECTOR`	`kernel/fs/fat16fs.c`	每个扇区包含的目录项数量

2.2 FAT 表与簇链¶

名称	位置	含义
`FAT16_CLUSTER_FREE`	`kernel/fs/fat16fs.c`	FAT 表项值 `0x0000`，表示空闲簇
`FAT16_CLUSTER_MIN`	`kernel/fs/fat16fs.c`	第一个有效数据簇号，固定为 2
`FAT16_CLUSTER_EOC`	`kernel/fs/fat16fs.c`	EOC 范围起点，大于等于该值表示簇链结束
`FAT16_CLUSTER_END`	`kernel/fs/fat16fs.c`	本实验写入 FAT 表时使用的链尾值

2.3 目录项属性与空槽标记¶

名称	位置	含义
`FAT16_ATTR_DIRECTORY`	`kernel/fs/fat16fs.c`	`attr` 中的目录标记
`FAT16_ATTR_KW`	`kernel/fs/fat16fs.c`	本实验关键词伪目录项使用的属性值
`FAT16_NAME_FREE`	`kernel/fs/fat16fs.c`	`name[0] == 0x00`，表示该槽位未使用，并且按 FAT 约定后续槽位也未使用
`FAT16_NAME_DELETED`	`kernel/fs/fat16fs.c`	`name[0] == 0xe5`，表示该槽位曾经使用过、现在已删除，可复用

注意事项：

删除文件时应标记为 FAT16_NAME_DELETED，不能把中间项改成 FAT16_NAME_FREE 后又在它后面保留有效项，因此在扫描时遇到 FAT16_NAME_FREE 即可停止。

2.4 关键词伪目录项¶

名称	位置	含义
`FAT16_KW_MAX_ENTRIES`	`kernel/fs/fat16fs.c`	单个文件最多允许使用的关键词伪目录项数量
`FAT16_KW_BYTES_PER_ENTRY`	`kernel/fs/fat16fs.c`	每个关键词伪目录项可存放的关键词数据字节数
`FAT16_KW_MAX_BYTES`	`kernel/fs/fat16fs.c`	单个文件关键词字符串最大字节数

3. 磁盘 I/O 与内存拷贝¶

3.1 `struct buf`¶

即用来保存磁盘块上数据的结构，位置：kernel/include/buf.h

重要字段：

bp->data：长度为 BSIZE 的块数据。

注意事项：

使用完必须调用 brelse()。

3.2 `bread()`¶

函数原型：

struct buf *bread(uint dev, uint blockno);

参数：

dev：设备号。在当前实现下 meta.dev 和 ip->dev 总是一样的。
blockno：磁盘块号，也就是扇区号。

返回值：

返回已锁定的 struct buf *。

3.3 `bwrite()`¶

函数原型：

void bwrite(struct buf *b);

参数：

b：由 bread() 返回且仍然持锁的 buffer。

注意事项：

修改 FAT 表、目录项、文件数据后，都要调用 bwrite() 才会持久化到磁盘。

3.4 `brelse()`¶

函数原型：

void brelse(struct buf *b);

参数：

b：由 bread() 返回且仍然持锁的 buffer。

3.5 `memmove()` 与 `memset()`¶

函数原型：

void *memmove(void *dst, const void *src, uint n);
void *memset(void *dst, int c, uint n);

参数：

dst：目标地址。
src：源地址。
c：填充值。
n：字节数。

返回值：

返回 dst。

4. FAT16 辅助函数¶

4.1 `get16()` 与 `get32()`¶

用于获取内存数据的十进制值，位置：kernel/fs/fat16fs.c

函数原型：

static ushort get16(const uchar *p);
static uint get32(const uchar *p);

参数：

p：指向小端序字节序列的内存地址。

返回值：

get16() 返回 2 字节整数。
get32() 返回 4 字节整数。

4.2 `fat16_cluster_first_sector()`（需要实现）¶

函数原型：

static uint fat16_cluster_first_sector(uint cluster);

参数：

cluster：数据簇号。

返回值：

返回该簇在磁盘上的第一个扇区号。

4.3 `fat16_read_fat()`（需要实现）¶

函数原型：

static uint fat16_read_fat(uint cluster);

参数：

cluster：FAT 表项索引。

返回值：

返回 FAT[cluster] 的 16 位值。

4.4 `fat16_read_entry()`¶

用于读某位置的目录项，函数原型：

static void fat16_read_entry(uint sector, uint offset, struct dirent *entry);

参数：

sector：目录项所在扇区。
offset：目录项在扇区内的字节偏移。
entry：输出参数，写入读出的 32B 目录项。

4.5 `fat16_slot_by_index()`（需要实现根目录分支）¶

根据目录项在 dp（即 directory pointer，标明这个inode是目录）目录下的索引，设置内存中的 FAT16 slot，包括扇区号、扇区内偏移与目录项结构体，函数原型：

static int fat16_slot_by_index(struct inode *dp, uint index, struct fat16_slot *slot);

参数：

dp：目录 inode。
index：目录项索引，从 0 开始。
slot：FAT16 目录项在内存中的槽位。

返回值：

成功返回 0。
越界或定位失败返回 -1。

4.6 `fat16_fat_value_is_eoc()`、`fat16_cluster_inuse()`¶

函数原型：

static int fat16_fat_value_is_eoc(uint fat_value);
static int fat16_cluster_inuse(uint cluster);

参数：

fat_value：FAT 表项值。
cluster：簇号。

返回值：

fat16_fat_value_is_eoc() 在表项表示链尾时返回非 0。
fat16_cluster_inuse() 在簇号是数据簇时返回非 0。

4.7 `fat16_alloc_cluster()` 与 `fat16_write_fat()`¶

函数原型：

static int fat16_alloc_cluster(uint *out);
static void fat16_write_fat(uint cluster, uint value);

参数：

out：成功分配新簇时写入新簇号。
cluster：簇号，即要写入的 FAT 表项索引。
value：要写入的 FAT 表项值。

返回值：

fat16_alloc_cluster() 成功返回 0，无空闲簇时返回 -1。

注意事项：

写路径扩展簇链时，通常先 fat16_alloc_cluster(&new_cluster)，再 fat16_write_fat(current_cluster, new_cluster)。

4.8 `fat16_cluster_for_offset()`（需要实现）¶

根据文件内偏移 off，读取该 off 对应的簇或者将文件的簇扩展到能容纳该 off 的大小，函数原型：

static int fat16_cluster_for_offset(struct inode *ip, uint off, int alloc, uint *cluster_out);

参数：

ip：普通文件 inode。
off：文件内字节偏移。
alloc：是否允许分配新簇。
cluster_out：输出参数，写入 off 所在簇号。

返回值：

成功返回 0。
读到不存在的簇、分配失败或簇链非法时返回 -1。

注意事项：

读路径调用时 alloc == 0，不能扩展簇链。
写路径调用时 alloc != 0，可以在遇到链尾时追加新簇。

5. 文件属性系统辅助函数¶

5.1 `fat16_dirent_is_keyword()`¶

函数原型：

static int fat16_dirent_is_keyword(const struct dirent *entry);

参数：

entry：要检查的 FAT16 目录项。

返回值：

是关键词伪目录项时返回非 0，否则返回 0.

5.2 `fat16_keyword_count_before()`（需要实现）¶

函数原型：

static int fat16_keyword_count_before(struct inode *dp, uint std_index);

参数：

dp：文件所在目录 inode。
std_index：标准文件目录项索引。

返回值：

返回标准文件目录项前面连续的关键词伪目录项数量。

5.3 `fat16_kw_get_data_byte()`¶

函数原型：

static uchar fat16_kw_get_data_byte(const struct dirent *entry, int pos);

参数：

entry：关键词伪目录项。
pos：关键词数据区内偏移，范围为 [0, FAT16_KW_BYTES_PER_ENTRY)。

返回值：

返回该位置保存的关键词数据字节。
pos 非法时返回 0。

5.4 `fat16_read_keywords_before()`（需要实现）¶

函数原型：

static int fat16_read_keywords_before(struct inode *dp, uint std_index, char *buf, int max);

参数：

dp：文件所在目录 inode。
std_index：标准文件目录项索引。
buf：输出缓冲区。
max：输出缓冲区容量。

返回值：

成功返回写入 buf 的关键词字节数，不包括结尾 \0。
无关键词时返回 0。
伪目录项格式错误或缓冲区不足时返回 -1。

注意事项：

输出 buf 以 \0 结尾。

5.5 `fat16_slot_available_for_run()`¶

用于检查目录下某处 32B 的连续空间是否能用来组成新的关键词伪目录项序列，函数原型：

static int fat16_slot_available_for_run(struct inode *dp, uint index,
                                        uint old_start, uint old_count);

参数：

dp：目录 inode。
index：待检查的目录项索引。
old_start：当前文件目录项旧连续范围起点。
old_count：当前文件目录项旧连续范围长度。

返回值：

槽位可用于新的连续范围时返回非 0，否则返回 0.

注意事项：

更新关键词时，旧范围内的关键词目录项将标记为删除，因此旧范围内的关键词目录项可以视为可复用。

5.6 `fat16_dir_slot_count()` 与 `fat16_grow_dir()`¶

函数原型：

static uint fat16_dir_slot_count(struct inode *dp);
static int fat16_grow_dir(struct inode *dp);

参数：

返回值：

fat16_dir_slot_count() 返回该目录当前可容纳的 32B 目录项数量。
fat16_grow_dir() 成功扩展子目录时返回 0，失败返回 -1。

注意事项：

根目录大小固定，不能通过 fat16_grow_dir() 增长。

5.7 `fat16_find_free_run()`（需要实现）¶

用于为设置关键词时找到一个连续的目录项序列，函数原型：

static int fat16_find_free_run(struct inode *dp, uint need, uint old_start, uint old_count,
                               struct fat16_slot *first_slot, uint *first_index);

参数：

dp：目标目录 inode。
need：需要的连续槽位数量。
old_start：旧连续范围起点。
old_count：旧连续范围长度。
first_slot：输出参数，成功时写入连续范围第一个槽位。
first_index：输出参数，成功时写入连续范围起始索引。

返回值：

找到连续范围时返回 0。
找不到或目录不能增长时返回 -1。

注意事项：

关键词伪目录项和标准文件目录项必须连续，不能用零散空槽拼接。
如果普通子目录空间不足，可以增长目录后重新扫描；根目录不能增长。

5.8 `fat16_mark_range_deleted_except()`¶

用于删除除保留范围外的旧范围内关键词伪目录项，函数原型：

static void fat16_mark_range_deleted_except(struct inode *dp, uint start, uint count,
                                            uint keep_start, uint keep_count);

参数：

dp：目录 inode。
start：要删除的旧范围起点。
count：旧范围长度。
keep_start：保留范围起点。
keep_count：保留范围长度。

5.9 `fat16_write_keywords_at()`¶

函数原型：

static int fat16_write_keywords_at(struct inode *dp, uint start, const char *keywords, int nentry);

参数：

dp：目录 inode。
start：第一条关键词伪目录项索引。
keywords：关键词字符串。
nentry：要写入的关键词伪目录项数量。

返回值：

成功返回 0。
参数非法或写入失败返回 -1。

5.10 `fat16_slot_inum()` 与 `fat16_find_loaded()`¶

函数原型：

static uint fat16_slot_inum(uint sector, uint offset);
static struct inode *fat16_find_loaded(uint inum);

参数：

sector、offset：标准目录项的新旧磁盘位置。
inum：由 fat16_slot_inum() 计算出的 inode 编号。

返回值：

fat16_slot_inum() 返回与目录项位置对应的 inode 编号。
fat16_find_loaded() 找到已加载 inode 时返回其指针，否则返回 0。

注意事项：

移动标准文件目录项后，已加载 inode 的 inum、addrs[1]、addrs[2] 也要同步修改。

5.11 `fat16_kw_index_update_file()`¶

用于在修改目录项布局后同步更新驻于内存的 B+ 树索引，函数原型：

static void fat16_kw_index_update_file(uint old_sector, uint old_offset,
                                       uint new_sector, uint new_offset,
                                       const char *path,
                                       const char *old_keywords,
                                       const char *new_keywords);

参数：

old_sector、old_offset：旧标准目录项位置。
new_sector、new_offset：新标准目录项位置。
path：文件路径。
old_keywords：旧关键词字符串。
new_keywords：新关键词字符串。

6. B+ 树¶

6.1 B+ 树宏和结构¶

名称	位置	含义
`BPTREE_MAX_KEYS`	`kernel/include/bptree.h`	单个 B+ 树节点最多容纳的键数
`BPTREE_VALUES_PER_CHUNK`	`kernel/include/bptree.h`	B+ 树存储的值块链表中每个值块最多容纳的值数量
`struct bptree_values`	`kernel/include/bptree.h`	一个关键词对应的值块链表
`struct bptree_value_chunk`	`kernel/include/bptree.h`	值链表的节点，称为值块，每个块中有多个值

注意事项：

本实验中 B+ 树的值是 struct fat16_kw_index_file *。
key 参数是长度为 len 的 token（注意这里的 token 可以理解为一个词）片段。

6.2 `bptree_keycmp_token()`¶

函数原型：

static int bptree_keycmp_token(const char *key, const char *token, int len);

参数：

key：B+ 树中保存的字符串。
token：待比较关键词片段。
len：token 的长度。

返回值：

小于 0：key < token。
等于 0：二者相等。
大于 0：key > token。

6.3 `bptree_strdup_key()`¶

用于在 B+ 树管理的内存中分配一块地址给新的键并将键值设为 key，函数原型：

static char *bptree_strdup_key(struct bptree *tree, const char *key, int len);

参数：

tree：目标 B+ 树。
key：关键词片段起始地址。
len：关键词长度。

返回值：

成功返回新复制的 key。
分配失败返回 0。

6.4 `bptree_values_add()`¶

为目标值块链表加入一条新记录 value。

函数原型：

static int bptree_values_add(struct bptree *tree, struct bptree_values *values, void *value);

参数：

tree：目标 B+ 树。
values：目标值块链表。
value：要加入的文件记录指针。

返回值：

成功返回 0。
参数非法或分配失败返回 -1。

6.5 `bptree_split_leaf()`（Bonus 需要实现）¶

用于分裂一个叶子结点，函数原型：

static int bptree_split_leaf(struct bptree *tree, struct bptree_node *node,
                             char **promoted, struct bptree_node **right);

参数：

tree：目标 B+ 树。
node：溢出的叶子节点。
promoted：输出参数，写入复制到父节点的 key。
right：输出参数，写入新右叶子节点。

返回值：

成功返回 0。
分配失败返回 -1。

6.6 `bptree_split_internal()`（Bonus 需要实现）¶

用于分裂一个内部结点，函数原型：

static int bptree_split_internal(struct bptree *tree, struct bptree_node *node,
                                 char **promoted, struct bptree_node **right);

参数：

tree：目标 B+ 树。
node：溢出的内部节点。
promoted：输出参数，写入提升到父节点的分隔 key。
right：输出参数，写入新右内部节点。

返回值：

成功返回 0。
分配失败返回 -1。

6.7 `bptree_insert_rec()`（Bonus 需要实现）¶

用于为键 key 插入值 value，函数原型：

static int bptree_insert_rec(struct bptree *tree, struct bptree_node *node,
                             const char *key, int len, void *value,
                             char **promoted, struct bptree_node **right);

参数：

tree：目标 B+ 树。
node：当前递归节点。
key：关键词片段。
len：关键词长度。
value：文件记录指针。
promoted：输出参数，当前节点分裂时写入提升 key，否则写入 0。
right：输出参数，当前节点分裂时写入右节点，否则写入 0。

返回值：

成功返回 0。
插入失败返回 -1。

实验4补充材料：辅助函数与宏定义速查¶

1. 基础结构¶

1.1 struct dirent¶

1.2 struct inode¶

1.3 struct fat16_slot¶

2. 重要宏定义¶

2.1 磁盘块与 FAT16 区域¶

2.2 FAT 表与簇链¶

2.3 目录项属性与空槽标记¶

2.4 关键词伪目录项¶

3. 磁盘 I/O 与内存拷贝¶

3.1 struct buf¶

3.2 bread()¶

3.3 bwrite()¶

3.4 brelse()¶

3.5 memmove() 与 memset()¶

4. FAT16 辅助函数¶

4.1 get16() 与 get32()¶

4.2 fat16_cluster_first_sector()（需要实现）¶

4.3 fat16_read_fat()（需要实现）¶

4.4 fat16_read_entry()¶

4.5 fat16_slot_by_index()（需要实现根目录分支）¶

4.6 fat16_fat_value_is_eoc()、fat16_cluster_inuse()¶

4.7 fat16_alloc_cluster() 与 fat16_write_fat()¶

4.8 fat16_cluster_for_offset()（需要实现）¶

5. 文件属性系统辅助函数¶

5.1 fat16_dirent_is_keyword()¶

5.2 fat16_keyword_count_before()（需要实现）¶

5.3 fat16_kw_get_data_byte()¶

5.4 fat16_read_keywords_before()（需要实现）¶

5.5 fat16_slot_available_for_run()¶

5.6 fat16_dir_slot_count() 与 fat16_grow_dir()¶

5.7 fat16_find_free_run()（需要实现）¶

5.8 fat16_mark_range_deleted_except()¶

5.9 fat16_write_keywords_at()¶

5.10 fat16_slot_inum() 与 fat16_find_loaded()¶

5.11 fat16_kw_index_update_file()¶

6. B+ 树¶

6.1 B+ 树宏和结构¶

6.2 bptree_keycmp_token()¶

6.3 bptree_strdup_key()¶

6.4 bptree_values_add()¶

6.5 bptree_split_leaf()（Bonus 需要实现）¶

6.6 bptree_split_internal()（Bonus 需要实现）¶

6.7 bptree_insert_rec()（Bonus 需要实现）¶

1.1 `struct dirent`¶

1.2 `struct inode`¶

1.3 `struct fat16_slot`¶

3.1 `struct buf`¶

3.2 `bread()`¶

3.3 `bwrite()`¶

3.4 `brelse()`¶

3.5 `memmove()` 与 `memset()`¶

4.1 `get16()` 与 `get32()`¶

4.2 `fat16_cluster_first_sector()`（需要实现）¶

4.3 `fat16_read_fat()`（需要实现）¶

4.4 `fat16_read_entry()`¶

4.5 `fat16_slot_by_index()`（需要实现根目录分支）¶

4.6 `fat16_fat_value_is_eoc()`、`fat16_cluster_inuse()`¶

4.7 `fat16_alloc_cluster()` 与 `fat16_write_fat()`¶

4.8 `fat16_cluster_for_offset()`（需要实现）¶

5.1 `fat16_dirent_is_keyword()`¶

5.2 `fat16_keyword_count_before()`（需要实现）¶

5.3 `fat16_kw_get_data_byte()`¶

5.4 `fat16_read_keywords_before()`（需要实现）¶

5.5 `fat16_slot_available_for_run()`¶

5.6 `fat16_dir_slot_count()` 与 `fat16_grow_dir()`¶

5.7 `fat16_find_free_run()`（需要实现）¶

5.8 `fat16_mark_range_deleted_except()`¶

5.9 `fat16_write_keywords_at()`¶

5.10 `fat16_slot_inum()` 与 `fat16_find_loaded()`¶

5.11 `fat16_kw_index_update_file()`¶

6.2 `bptree_keycmp_token()`¶

6.3 `bptree_strdup_key()`¶

6.4 `bptree_values_add()`¶

6.5 `bptree_split_leaf()`（Bonus 需要实现）¶

6.6 `bptree_split_internal()`（Bonus 需要实现）¶

6.7 `bptree_insert_rec()`（Bonus 需要实现）¶