<0x01> 任务说明
缓冲区高速缓存
可扩展大小的文件
子目录
同步
<0x02> 代码实现
缓冲区高速缓存
首先我们要确定下我们要缓存什么东西
pintos中，文件在硬盘中按块存储，块大小512字节
每个块有一个块号，可以用这个块号访问到硬盘中的数据块
那我们的缓存其实是让系统先别去读写硬盘
先在缓冲中读写，然后在合适的时机再写入到硬盘中
为什么这么做呢，软件运行过程中可能会对同一个文件多次读写
如果访问硬盘的话每次都要等硬盘响应，效率不行
如果是缓存的话，访问的就是内存了，快多了
首先先声明一个缓存对象与缓存本身
struct cache_buffer
{
char data[BLOCK_SECTOR_SIZE];
};
static struct cache_buffer cache[NUM_SECTORS]; // cache本身
// 缓存块类型
struct cache_entry
{
block_sector_t sector; // 硬盘块号
size_t index; // 缓存标号
struct condition queue; // 对于多线程读写的同步控制
struct hash_elem elem; // 使用hash数据结构
bool dirty; // 有无修改
};
对于这个数据结构，我们采用控制块与数据块分离的方式
这样方便内存对齐
（cache_buffer的东西放在cache_entry里面也是可以的）
这里采用的缓存算法是clock算法，并带有两个标识位
使用pintos自带的bitmap类型表示所有64个块的标识符
（一样，这个东西放在cache_entry也是可以的）
然后考虑检索效率，使用hashmap作为检索结构
如果使用list，虽然也可以通过遍历的方式检索
但考虑到缓存时常可能没缓存到需要的块，这时候需要遍历整个链表，效率不高
整体声明如下
struct cache_buffer
{
char data[BLOCK_SECTOR_SIZE];
};
static size_t clock_index; // clock算法的index
static struct cache_buffer cache[NUM_SECTORS]; // cache本身
static struct cache_entry *entries[NUM_SECTORS]; // 缓存的数据结构列表
static struct bitmap *refbits; // 是否被访问
static struct bitmap *usebits; // 是否被修改
static struct hash cache_hashmap; // cache的hashmap
static struct lock cache_lock; // cache锁
static struct condition cache_cond; // 如果所有的缓存块都有使用就阻塞
下面是clock算法的实现
// 寻找是否在缓存中，如果没有，就用clock算法替换一块
static bool cache_find_entry(block_sector_t sector, struct cache_entry **entry)
{
struct cache_entry *e = malloc(sizeof(struct cache_entry));
e->sector = sector;
// 如果所有的缓存块都在等
while (bitmap_all(usebits, 0, NUM_SECTORS))
{
cond_wait(&cache_cond, &cache_lock);
}
struct hash_elem *found = hash_insert(&cache_hashmap, &e->elem);
if (found == NULL)
{
// clock算法循环
while (bitmap_test(refbits, clock_index) || bitmap_test(usebits, clock_index))
{
bitmap_reset(refbits, clock_index);
clock_index = (clock_index + 1) % NUM_SECTORS;
}
// 释放旧块
struct cache_entry *old_entry = entries[clock_index];
if (old_entry != NULL)
{
block_write(fs_device, old_entry->sector, &cache[old_entry->index]);
hash_delete(&cache_hashmap, &old_entry->elem);
free(old_entry);
}
// 构建新块
cond_init(&e->queue);
e->dirty = false;
e->index = clock_index;
entries[e->index] = e;
clock_index = (clock_index + 1) % NUM_SECTORS;
}
else
{
free(e);
e = hash_entry(found, struct cache_entry, elem);
while (bitmap_test(usebits, e->index))
{
cond_wait(&e->queue, &cache_lock);
}
}
// 标记新块被使用
bitmap_mark(usebits, e->index);
*entry = e;
return (found != NULL);
}
然后是同步相关的问题（后面就不写了）
可以看到上面的代码已经包含了所有缓存块都使用的情况和单独缓存块使用的情况
对于所有缓存块都使用的情况，那么线程就必须等待有缓存块释放
对于单个缓存块使用的情况，其实等同于单个硬盘快被多个线程使用
这时候也是等待
在buffer_cache_release中，会释放对应的锁
最后是需要定期得清理缓存，这里直接新建一个线程，差不多隔1.5秒执行一次
（我这里设定TIMER_FREQ为1000）
所谓清理就是把缓存中使用过得，有数据就写到硬盘里
thread_create("cache-sync", PRI_MAX, cache_write_thread_func, NULL);
// 刷新所有的缓存块
void buffer_cache_flush(void)
{
lock_acquire(&cache_lock);
for (size_t i = 0; i < NUM_SECTORS; i++)
{
// 同步缓存中脏块的更改
if (entries[i] != NULL && entries[i]->dirty && !bitmap_test(usebits, i))
{
block_write(fs_device, entries[i]->sector, &cache[i]);
entries[i]->dirty = false;
}
}
lock_release(&cache_lock);
}
// 清理缓存块的线程函数
void cache_write_thread_func(void *aux UNUSED)
{
while (true)
{
timer_sleep(1500);
buffer_cache_flush();
}
}
然后别忘了在filesys_done里面最后保存一次缓存数据
void filesys_done(void)
{
// 关闭前强制同步下缓存的内容
buffer_cache_flush();
free_map_close();
}
其他的代码都是简单的转换和处理，这里就不写明了
具体代码看仓库吧
可扩展的文件大小
首先我们看到inode_disk的部分
这个是硬盘数据块的抽象
struct inode_disk
{
block_sector_t start; /* First data sector. */
off_t length; /* File size in bytes. */
unsigned magic; /* Magic number. */
uint32_t unused[125]; /* Not used. */
};
可以看到就一个数据起始点，然后一个文件大小，剩下的都没啥用
通过学习操作系统
我们知道，现代操作系统的文件系统喜欢搞什么直接引用块，间接引用块之类的
这就是我们要实现的东西
首先我们先把这个类改造成这样
struct inode_disk
{
block_sector_t parent_dir; // 指向父目录（不是这步的东西）
bool is_dir; // 是否为路径（不是这步的东西）
off_t length; // 文件大小，字节
block_sector_t direct[122]; // 直接寻址块
block_sector_t indirect; // 一层间接
block_sector_t doubly_indirect; // 二层间接
unsigned magic; /* Magic number. */
};
这里需要注意，block_sector_t部分不能超过126个单元
因为硬盘的扇区是512字节，block_sector_t是4字节
off_t也是4字节，然后神秘magic数字也是4字节
这样的话刚好512字节
然后声明下这两个类型，作为一次间接和二次间接
struct indirect_block
{
block_sector_t direct[128];
};
struct doubly_indirect_block
{
block_sector_t indirect_block[128];
};
后面就是想办法分配和回收这些东西了
这里别的就不讲了，主要讲文件大小扩展的事情
// 扩展下文件长度
static bool extend_inode_length(struct inode_disk *inode, off_t length)
{
ASSERT(inode != NULL);
ASSERT(length <= MAX_LENGTH);
if (length == inode->length)
{
return true;
}
ASSERT(length > inode->length);
size_t origin = bytes_to_sectors(inode->length);
size_t need = bytes_to_sectors(length);
// 不需要分配新块的情况
if (origin == need)
{
inode->length = length;
return true;
}
lock_acquire(&free_map_lock);
// 是否剩余空间够用
if (free_map_available_space() < need - origin)
{
lock_release(&free_map_lock);
return false;
}
// 初始化一层引用
if (origin <= NUM_DIRECT && NUM_DIRECT < need)
{
free_map_allocate(1, &inode->indirect);
block_write_zero(inode->indirect);
}
// 初始化二层引用
if (origin <= NUM_DIRECT_PLUS_INDIRECT && NUM_DIRECT_PLUS_INDIRECT < need)
{
free_map_allocate(1, &inode->doubly_indirect);
block_write_zero(inode->doubly_indirect);
}
// 分配所有需要的节点
bool success = inode_map_sectors_allocate(inode, origin, need);
lock_release(&free_map_lock);
inode->length = length;
return success;
}
分配一次引用和二次引用关键是计算需要多少块，然后什么范围需要一次引用或二次引用
这里就不讲了
子目录
目录的本身也是一种文件数据块
前面可扩展大小文件也看到类型声明里面就有相关的代码
目录本身其实也可以看作是一个文件
只不过这个文件保存的就是目录名字
这部分的工作主要在filesys中完成
有了前面的实现，其实这步主要是一些逻辑部分
这里只举两个例子，因为别的也差不多，看源代码吧
下面是文件创建的代码
bool filesys_create(const char *name, off_t initial_size)
{
// 打开当前线程的工作路径
struct dir *dir = dir_open_cwd(name);
struct inode *inode = NULL;
const char **name_cp = &name;
while (true)
{
if (!dir_is_valid(dir))
{
return false;
}
char part[NAME_MAX + 1];
// 获取下一个目录名
int status = get_next_part(part, name_cp);
if (status < 1)
{
return false;
}
// 创建文件
if (**name_cp == '\0')
{
block_sector_t inode_sector = 0;
bool success = (free_map_allocate(1, &inode_sector) &&
inode_create_with_dir_info(inode_sector, initial_size, get_dir_inumber(dir), false) &&
dir_add(dir, part, inode_sector));
if (!success && inode_sector != 0)
{
free_map_release(inode_sector, 1);
}
dir_close(dir);
return success;
}
// 打开下一级目录
dir_lookup(dir, part, &inode);
dir_close(dir);
dir = dir_open(inode);
}
return false;
}
这个是切换工作路径的代码
block_sector_t filesys_chdir(const char *path_name)
{
// 空返回
if (path_name == NULL || ('\0' == path_name[0]))
{
return 0;
}
// 如果要返回上一级
if (!strcmp(path_name, ".."))
{
return inode_get_parent_dir(inode_open(thread_current()->cwd));
}
const char **name_cp = &path_name;
struct dir *dir = dir_open_cwd(path_name);
while (true)
{
struct inode *inode = NULL;
char part[NAME_MAX + 1];
// 获取下一级目录
get_next_part(part, name_cp);
if (dir != NULL)
{
dir_lookup(dir, part, &inode);
}
dir_close(dir);
// 如果已经找到最后
if (**name_cp == '\0')
{
if (inode == NULL)
{
return 0;
}
return inode_get_inumber(inode);
}
if (inode == NULL)
{
return 0;
}
dir = dir_open(inode);
if (dir == NULL)
{
return 0;
}
}
return 0;
}
系统调用chdir是调用这个代码
剩下的部分也都是这样，用已经实现的结构写逻辑就可以了
然后记得写系统调用那边的实现就可以了
<0x03> 测试相关
如果跟我一样没写相关的PATH，那么就要改下make.var