ext2 && simple filesystem实现

ext2

组成：

block：一个扇区512字节，block出现提高了读写性能

文件系统维护数据块，磁盘维护逻辑块，

IO管理器将数据块翻译成逻辑块地址LBA

inode：索引节点，优化存储

在inode中存储了inode号、文件类型、权限、文件所有者、大小、时间戳等元数据信息，最重要的是还存储了指向属于该文件block的指针

文件系统创建完成后所有的inode号都已经分配好并记录到inode table中了，只不过被使用的inode号所在的行还有文件属性的元数据信息和block位置信息，而未被使用的inode号只有一个inode号而已而没有其他信息而已。

bmap：标识空闲block，写优化

inode表：通过将存储inode的block组合起来形成一张表

imap：标识空闲inode

块组：减小map大小，提高map扫描效率

磁盘分区，逻辑分组

块组在文件系统创建就划分好了，固定了以上组合

引导块：分区第一个块，1024字节，只有装了os的主分区和逻辑分区才有，VBR和EBR

MBR上的boot loader加载后，通过清——->定位到不同操作系统的bootloader

超级块：1024字节

比较dfs和du：df读取超级块，du遍历

ext2在0、1、3、5、7幂次放块组保存超级块

dumpe2fs -h读取ext超级块信息

GDT：每个块组描述符32字节记录了块组的信息和属性元数据，gdt存放同superblock

dumpe2fs描述符信息

保留GDT，高效增加

data block：

常规文件：
目录：所有文件和一级子目录名
文件名不在inode，而在所在目录data block
符号链接：目标路径名较短保存在inode，60字节保存在data block
特殊文件没有data block

目录文件：

目录文件存储文件的inode链接，类型，名字，因此没有执行权限时无法获取inode号，需要执行inode链接

name属性：4的倍数，’\0‘填充，

unlink：删除这个指针和inode号的映射，例子：ls -l无法获取没有执行权限的inode号

‘.’和’..‘两个硬链接

inode

inode->block->file

硬链接：inode相同，不允许跨区

删除本质就是应删除目录对应inode的指针

In file_target link_name

软连接：

符号链接：软连接，相当于快捷方式，大小是目标路径字符个数

符号链接的inode记录就能描述信息，目标路径60字节时才会分配block
设备文件、FIFO、套接字文件没有data block

In -s source_file softlink_name

readlink softlink_name

深入：

cat /etc/mke2fs.conf

1
2
3

blocksize = 4096 
inode_size = 256 
inode_ratio = 16384

Ext4的特殊inode

Inode号用途

0 不存在0号inode

1 虚拟文件系统，如/proc和/sys

2 根目录

3 ACL索引

4 ACL数据

5 Boot loader

6 未删除的目录

7 预留的块组描述符inode

8 日志inode

11 第一个非预留的inode，通常是lost+found目录

ext2/3inode指针

最多15个，前12个是直接寻址

12+256+256^2+25^4

单文件系统：

读取cat /vat/log/message

找到GDT–>找到”/“的inode–>找到/的数据块读取var的inode–>找到var的数据块读取log的inode–>找到log的数据块读取messages的inode–>找到messages的数据块并读取它们

删除

(1)找到文件的inode和data block;

(2)将inode table中该inode记录中的data block指针删除;

(3)在imap中将该文件的inode号标记为未使用;

(4)在其所在目录的data block中将该文件名所在的记录行删除，删除了记录就丢失了指向inode的指针;

(5)将bmap中data block对应的block号标记为未使用。

删除目录：所有inode和data block，3、5，提前删除父目录记录报错目录非空

第五步中df仍会计算大小

当一个进程正在引用文件时将该文件删除，就会出现文件已删除但空间未释放的情况。这时步骤已经进行到(4)，外界无法再找到该文件，但由于进程在加载该文件时已经获取到了该文件所有的data block指针，该进程可以获取到该文件的所有数据，但却暂时不会释放该文件空间。直到该进程结束，文件系统才将未执行的步骤(5)继续完成。这也是为什么有时候du的统计结果比df小的原因

存储和复制：

每存储一个block调用一次block分配器

挂载

文件系统需要挂载才能使用

将文件系统挂载到一个目录后，该目录是文件系统的入口：

在父目录文件系统的inode表中，重新分配一个inode，其block指针指向新的文件系统，指向老inode的指针现在指向新inode，原来的目录就被标记不可用

卸载时移除新配分的inode，将父目录的data block的指针指向老inode

ext3：

数据区、日志区、元数据区

先在日志保存元数据

ex4：

使用extent段来管理，inode寻址使用片断流，设定了起始block号和连续block

A SimpleFS

Magic：文件系统的“签名”，意味着包含有效文件系统

测试：

当遇到错误时可以去看一下shell和test脚本，为了看到错误信息，把test脚本 2> /dev/null删掉，这是把cerr输出的错误信息丢掉

debug：没办法只能暴力照着格式输出，后来才发现printf磁盘读写次数应该在dis_close函数里打印，这样逻辑才对
format：这里format只能把除了superblock的每个block清空，我一开始尝试着只把inode表清空，虽然存储结果正确，但是因为test还要符合磁盘读写次数，而且读数据的时候还会出问题，所以还是要遍历删除
mount：记得unmount的时候要令fs->disk=NULL，不然程序会abort，同时在最后两个测试报错了：可用看出这里直接修改超级块，每个superblock刚好4*4字节，而0xf0 0x f0 0x 34 0x10是魔数对应小端存储就是了；报错是因为，修改了inodes和inode_blocks不匹配了，在mount中还需检查inodes和inode_blocks值是否符合逻辑；最后read多了1因为把无效inode也读了

echo -n -e $(printf '\\x%x\\x%x\\x%x\\x%x' 0x10 0x34 0xf0 0xf0) >  $SCRATCH/image.5
echo -n -e $(printf '\\x%x\\x%x\\x%x\\x%x' 0x05 0x00 0x00 0x00) >> $SCRATCH/image.5
echo -n -e $(printf '\\x%x\\x%x\\x%x\\x%x' 0x02 0x00 0x00 0x00) >> $SCRATCH/image.5
echo -n -e $(printf '\\x%x\\x%x\\x%x\\x%x' 0x80 0x00 0x00 0x00) >> $SCRATCH/image.5
echo -n "Testing bad-mount on $SCRATCH/image.5 ... "
if diff -u <(bad-mount-input| ./bin/sfssh $SCRATCH/image.5 5 2> /dev/null) <(bad-mount-output) > $SCRATCH/test.log; then
    echo "Success"
else
    echo "Failure"
    cat $SCRATCH/test.log
    EXIT=$(($EXIT + 1))
fi

echo -n -e $(printf '\\x%x\\x%x\\x%x\\x%x' 0x10 0x34 0xf0 0xf0) >  $SCRATCH/image.5
echo -n -e $(printf '\\x%x\\x%x\\x%x\\x%x' 0x05 0x00 0x00 0x00) >> $SCRATCH/image.5
echo -n -e $(printf '\\x%x\\x%x\\x%x\\x%x' 0x01 0x00 0x00 0x00) >> $SCRATCH/image.5
echo -n -e $(printf '\\x%x\\x%x\\x%x\\x%x' 0x70 0x00 0x00 0x00) >> $SCRATCH/image.5
echo -n "Testing bad-mount on $SCRATCH/image.5 ... "
if diff -u <(bad-mount-input| ./bin/sfssh $SCRATCH/image.5 5 2> /dev/null) <(bad-mount-output) > $SCRATCH/test.log; then
    echo "Success"
else
    echo "Failure"
    cat $SCRATCH/test.log
    EXIT=$(($EXIT + 1))
fi

stat：这一个测试内存容易出问题，最好用valgrind测试内存
create：我这里disk block read原本是要比测试少127次的，因为测试中认为你采用分而治之的思想，把save inode和load inode写在fs_load_inode和fs_save_inode中，因此包装在fs_save_inode就好了
fs_read：犯了一个弱智错误，每次读取间接block都从0开始读，忘记计算offset，😵
fs_write：copyin分配block，一开始直接fs_create()，才发现这是分配inode；原本设置true未使用，因为bool类型memset设置为0更方便并且不会出错，memset是通过一个字节一个字节赋值的，一般用0，-1，0x3f；

这里要确保fs_initialize_free_block_bitmap正确，不然读取inode信息可能读出一大串数据；

fs_write除了要保存inode，若有还需要保存indirect block
remove：在这一个测试一直报错，一直以为是remove的问题，导致write断言出错，最大用gdb才发现索引16的block已经在之前给我覆盖了，在这里刚好被拿来当作indirect block，导致直接越界，悲剧了，发现是这样一句话

后面发现原本数据就是这样的需要你去判断，我的代码逻辑错了，应该在每次成功分配到block号时初始化block并覆盖掉，而不是再去读磁盘block

边界问题：

像fs_create，fs_write都要处理边界问题不能单纯的返回错误，比如fs_write当写满时还要更新inode

代码：

代码地址：https://github.com/Js637a68/Simple-File-System

磁盘模拟器

把一个二进制文件模拟磁盘，对其进行读写操作，需要考虑字节序和内存对齐问题

创建二进制文件：dd if=/dev/zero of=/path/file bs=1k count=4

修改二进制文件：echo -n -e $(printf '\\x%x\\x%x\\x%x\\x%x' 0x10 0x34 0xf0 0xf0) >> path/file

-n表示不要末尾添加换行符，-e启动转义字符，\\x%x表示一个字节的十六进制输出

struct Disk {
    int	    fd;	        /* File descriptor of disk image	*/
    size_t  blocks;     /* Number of blocks in disk image	*/
    size_t  reads;      /* Number of reads to disk image	*/
    size_t  writes;     /* Number of writes to disk image	*/
};

Disk *	disk_open(const char *path, size_t blocks) {
    Disk *disk = (Disk*)malloc(sizeof(Disk));
    if(disk == NULL) return NULL;
    disk->fd = open(path, O_RDWR);
    if (ftruncate(disk->fd, blocks * BLOCK_SIZE) < 0) 
    {
        close(disk->fd);
        free(disk);
        return NULL;
    }
    disk->blocks = blocks;
    disk->writes = disk->reads = 0;
    return disk;
}

void	disk_close(Disk *disk) {
    if(disk != NULL)
    {
        if(disk->fd >= 0) close(disk->fd);
        printf("%lu disk block reads\n", disk->reads);
        printf("%lu disk block writes\n", disk->writes);
        free(disk);
    }
}

ssize_t disk_read(Disk *disk, size_t block, char *data) {
    if(!disk_sanity_check(disk, block, data)) return DISK_FAILURE;

    off_t position = (off_t)block * BLOCK_SIZE;
    if (lseek(disk->fd, position, SEEK_SET) == (off_t)-1) {
        return DISK_FAILURE;
    }

    ssize_t bytesRead = read(disk->fd, data, BLOCK_SIZE);
    if (bytesRead < 0) {
        return DISK_FAILURE;
    }

    disk->reads++;
    return bytesRead;
}

ssize_t disk_write(Disk *disk, size_t block, char *data) {
    if(!disk_sanity_check(disk, block, data)) return DISK_FAILURE;

    off_t position = (off_t)block * BLOCK_SIZE;
    if (lseek(disk->fd, position, SEEK_SET) == (off_t)-1) {
        return DISK_FAILURE;
    }

    ssize_t bytesWritten = write(disk->fd, data, BLOCK_SIZE);
    if (bytesWritten < 0) {
        return DISK_FAILURE;
    }

    disk->writes++;
    return bytesWritten;
}

bool    disk_sanity_check(Disk *disk, size_t block, const char *data) {
    if(disk != NULL && data != NULL)
    {
        if( block < disk->blocks)
            return true;
    }
    return false;
}

文件系统

这里巧妙的应用union来表示一个block的类型

#define MAGIC_NUMBER        (0xf0f03410)
#define INODES_PER_BLOCK    (128)               /* TODO: Number of inodes per block */
#define POINTERS_PER_INODE  (5)                 /* TODO: Number of direct pointers per inode */
#define POINTERS_PER_BLOCK  (1024)              /* TODO: Number of pointers per block */

/* File System Structures */

typedef struct SuperBlock SuperBlock;
struct SuperBlock {
    uint32_t    magic_number;                   /* File system magic number */
    uint32_t    blocks;                         /* Number of blocks in file system */
    uint32_t    inode_blocks;                   /* Number of blocks reserved for inodes */
    uint32_t    inodes;                         /* Number of inodes in file system */
};

typedef struct Inode      Inode;
struct Inode {
    uint32_t    valid;                          /* Whether or not inode is valid */
    uint32_t    size;                           /* Size of file */
    uint32_t    direct[POINTERS_PER_INODE];     /* Direct pointers */
    uint32_t    indirect;                       /* Indirect pointers */
};

typedef union  Block      Block;
union Block {
    SuperBlock  super;                          /* View block as superblock */
    Inode       inodes[INODES_PER_BLOCK];       /* View block as inode */
    uint32_t    pointers[POINTERS_PER_BLOCK];   /* View block as pointers */
    char        data[BLOCK_SIZE];               /* View block as data */
};

typedef struct FileSystem FileSystem;
struct FileSystem {
    Disk        *disk;                          /* Disk file system is mounted on */
    bool        *free_blocks;                   /* Free block bitmap */
    SuperBlock   meta_data;                     /* File system meta data */
};

文件系统属性打印：输出superblock和inode的信息，没什么好说遍历就好了

文件格式化：获取磁盘属性并设置超级块，这里把10%的块分配给inode表，因此需要把除超级块之外block都清0；在这里假定格式化一个已挂载的fs无效，满足以下条件

if(!fs) return false;
size_t blocks = disk->blocks;
if (blocks < 2) {
    return false; // 磁盘块数不足，无法格式化

挂载：挂载首先要检查魔数以及超级块属性是否合法，特别的，inode数量是否符合inode表，然后再初始化bmap表

bool    fs_mount(FileSystem *fs, Disk *disk) {
	...
    if (block.super.magic_number != MAGIC_NUMBER || block.super.blocks != disk->blocks)
        return false;
    if(block.super.inodes != block.super.inode_blocks * INODES_PER_BLOCK) return false;
}

bmap初始化，这里都是用c所以malloc，同样遍历inode，因为文件存放在inode块指针是按顺序的，不然文件数据有效无法保证，所以当0时可用break

for(uint32_t i = 1; i <= inode_blocks; ++i)
{
    fs->free_blocks[i] = true;     // 被inode使用
    Block b = {0};
    // 读取inode表
    assert(disk_read(fs->disk, i, b.data) != DISK_FAILURE);

    for(int p = 0; p < INODES_PER_BLOCK; ++p)
    {
        const Inode inode = b.inodes[p];
        if(!inode.valid) continue;
        // 直接block
        for(uint32_t j = 0 ; j < POINTERS_PER_INODE; ++j)
        {
            if(inode.direct[j] == 0) break;
            fs->free_blocks[inode.direct[j]] = true;
        }
        // 间接block
        if(inode.indirect == 0) continue;
        fs->free_blocks[inode.indirect] = true;
        Block indirect_point = {0};
        assert(disk_read(fs->disk, inode.indirect, indirect_point.data) != DISK_FAILURE);

        for(int j = 0; j < POINTERS_PER_BLOCK; ++j)
        {
            if(indirect_point.pointers[j] == 0) break;
            fs->free_blocks[indirect_point.pointers[j]] = true;
        }
    }
}

创建inode和移除inode：这里的remove其实我只是简单的设置bmap未使用，将这个block清0的操作在分配这个block的时候进行，因为我发现一开始的image映像有许多冗余数据，有可能该block未使用但是依然保存无效数据，所以干脆省事在分配的时候再清0，为了方便操作这里需要额外两个函数来读取和存储inode

for(uint32_t i = 0 ; i < POINTERS_PER_INODE; ++i)
{
    if(inode.direct[i] == 0) break;
    fs->free_blocks[inode.direct[i]] = false;
}
if(inode.indirect != 0)
{
    Block block = {0};
    assert(disk_read(fs->disk, inode.indirect, block.data) != DISK_FAILURE);  
    uint32_t i = 0;
    for(; i < POINTERS_PER_BLOCK; ++i) 
    {
        if(block.pointers[i] == 0) break;
        fs->free_blocks[block.pointers[i]] = false;
    }
    if(i! = 0) fs->free_blocks[inode.indirect] = false;
}

bool    fs_load_inode(FileSystem *fs, size_t inode_number, Inode *node)
{
    Block block = {0};
    if(inode_number >= fs->meta_data.inodes) return false;
    assert(disk_read(fs->disk, inode_number/INODES_PER_BLOCK + 1, block.data) != DISK_FAILURE);
    if(!block.inodes[inode_number].valid) return false;
    *node = block.inodes[inode_number % INODES_PER_BLOCK];
    return true;
}

bool    fs_save_inode(FileSystem *fs, const size_t inode_number, Inode *node)
{
    Block block = {0};
    if(inode_number >= fs->meta_data.inodes) return false;
    assert(disk_read(fs->disk, inode_number/INODES_PER_BLOCK + 1, block.data) != DISK_FAILURE);
    memcpy(&block.inodes[inode_number % INODES_PER_BLOCK], node, sizeof(Inode));
    assert(disk_write(fs->disk, inode_number/INODES_PER_BLOCK + 1, block.data) != DISK_FAILURE);
    return true;
}

读文件的话计算好偏移值就行，代码有重复的部分可用简洁一下

Inode node = {0};
if (!fs_load_inode(fs, inode_number, &node)) return -1;

if (offset >= node.size) return 0;
if (length == 0) return 0;
if (offset + length >= node.size) length = node.size - offset;

size_t sum = 0;
uint32_t i = offset / BLOCK_SIZE;
for(; i < POINTERS_PER_INODE && sum < length; ++i)
{
    if (node.direct[i] == 0) break; 
    char block_data[BLOCK_SIZE];
    memset(block_data, 0, BLOCK_SIZE);
    assert(disk_read(fs->disk, node.direct[i], block_data) != DISK_FAILURE);

    size_t read_size = (length - sum) < BLOCK_SIZE ? (length - sum) : BLOCK_SIZE;
    memcpy(data + sum, block_data + offset % BLOCK_SIZE, read_size);
    sum += read_size;
    offset += read_size;
}
if (node.indirect != 0 && sum < length) 
{
    Block block;
    i -= POINTERS_PER_INODE;
    assert(i >= 0);
    assert(disk_read(fs->disk, node.indirect, block.data) != DISK_FAILURE);
    for (; i < POINTERS_PER_BLOCK && sum < length; ++i) {
        if (block.pointers[i] == 0) break; 
        char block_data[BLOCK_SIZE];
        memset(block_data, 0, BLOCK_SIZE);
        assert(disk_read(fs->disk, block.pointers[i], block_data) != DISK_FAILURE); 

        size_t read_size = (length - sum) < BLOCK_SIZE ? (length - sum) : BLOCK_SIZE;
        memcpy(data + sum, block_data + offset % BLOCK_SIZE, read_size);
        sum += read_size;
        offset += read_size;
    }
}

写文件操作比较复杂，这里根据offset选取从哪一个block开始写，考虑是否需要分配block，不然就直接读出block进行写入，每write一个block从offset%BLOCK_SIZE开始到BLOCK_SIZE这段区间写入，判断length是否到头了，真正写入的是copy_size；第二部分读取间接block，同理，这里重复了代码有点冗余；如果磁盘没有足够空间可用分配就goto last

ssize_t fs_write(FileSystem *fs, size_t inode_number, char *data, size_t length, size_t offset) {
    Inode node;
    if(!fs_load_inode(fs, inode_number, &node)) return -1;
    if(offset > node.size) return 0;

    ssize_t point = offset / BLOCK_SIZE;
    ssize_t written = 0;
    for(; point < POINTERS_PER_INODE && length > 0; point++)
    {
        Block block;
        memset(block.data, 0, BLOCK_SIZE);
        if(node.direct[point] == 0) 
        {
            node.direct[point] = fs_allocate_free_block(fs);
            if(node.direct[point] == 0) goto last;  
        }
        else assert(disk_read(fs->disk, node.direct[point], block.data) != DISK_FAILURE);

        const ssize_t remaining = BLOCK_SIZE - offset % BLOCK_SIZE;
        const ssize_t copy_size = remaining < length? remaining : length;
        memcpy(block.data + offset % BLOCK_SIZE, data + written, copy_size);
        assert(disk_write(fs->disk, node.direct[point], block.data) != DISK_FAILURE);
        length -= copy_size;
        offset += copy_size;
        written += copy_size;
    }
    if(length > 0)
    {
        point -= POINTERS_PER_INODE;
        assert(point >= 0);
        Block block;
        memset(block.data, 0, BLOCK_SIZE);
        if(node.indirect == 0) 
        {
            assert(offset%BLOCK_SIZE == 0);
            node.indirect = fs_allocate_free_block(fs);
            if(node.indirect == 0) goto last;
        }
        else assert(disk_read(fs->disk, node.indirect, block.data) != DISK_FAILURE);
        while(length > 0)
        {
            Block data_block;
            memset(data_block.data, 0, BLOCK_SIZE);
            if(block.pointers[point] == 0) 
            {
                block.pointers[point] = fs_allocate_free_block(fs);
                if(block.pointers[point] == 0) break;
            }
            else assert(disk_read(fs->disk, block.pointers[point], data_block.data) != DISK_FAILURE);

            const ssize_t remaining = BLOCK_SIZE - offset % BLOCK_SIZE;
            const ssize_t copy_size = remaining < length? remaining : length;
            memcpy(data_block.data + offset%BLOCK_SIZE, data + written, copy_size);     
            assert(disk_write(fs->disk, block.pointers[point], data_block.data) != DISK_FAILURE);
            point++;
            length -= copy_size;
            offset += copy_size;
            written += copy_size;
        }
        assert(disk_write(fs->disk, node.indirect, block.data) != DISK_FAILURE);
    }
last:
    node.size = offset > node.size ? offset : node.size;
    assert(fs_save_inode(fs, inode_number, &node));
    return written;
}