简单Linux文件系统数据结构设计


简介

简易Linux文件系统的实现,在现有机器硬盘上开辟100M的硬盘空间,作为设定的硬盘空间。设定块大小固定为1KB,用位图法管理iNode节点和空闲块。
需要实现的命令:

  • 展示路径(ls)
  • 改变目录(cd)
  • 创建目录
  • 删除目录
  • 创建文件
  • 删除文件
  • 预览文件
  • 复制文件(从主机或者模拟盘双向复制)

命令行中的命令命名并未完全按照Linux的来,不过基本没有影响。
实现分为2块:

  1. SimDisk最简版
  2. 多shell+SimDisk

关键数据结构

数据在硬盘上存放顺序
超级块(1024K)
iNode表
iNode位图
块位图
剩余数据块

iNode

class iNode
{
public:
    unsigned int ino;//i节点号
    unsigned short i_mode;//文件模式16位,前4位表示文件类型,后12位表示权限
    unsigned long i_size;//文件大小,单位字节
    unsigned long i_time;//文件创建时间
    unsigned long i_mtime;//文件最后修改时间
    unsigned long i_atime;//文件最后一次访问时间
    unsigned long i_blocks;//文件所占块数
    unsigned short i_uid;//所属用户
    unsigned short i_gid;//所属用户组
    unsigned int i_zone[13];//块指针
    unsigned short i_count;//引用计数
    unsigned short i_nlink;//与该节点建立链接的文件数(硬链接数)
    iNode();
    iNode(unsigned int no, unsigned long size, unsigned long block,vector<unsigned int> zone);
    ~iNode();
    void printInfo();
};

以上是我的iNode类对应的头文件代码,是从Linux的iNode结构中精简了部分得出,需要讲解的也就i_mode,i_mode是一个16位的变量,其中前4位用于表示路径或文件等,后面12位用于表示用户权限(rwxrwxrwx),分为3组每组共4位,第一组是所属用户的权限,第二组是同用户组权限,第三组是其他用户的权限。

SuperBlock

超级块的信息如下

//超级块数据结构
#include "iNode.h"
class superBlock
{
public:
    unsigned short inode_num;//i节点数目
    unsigned short inode_remain;//i节点剩余数目
    unsigned int block_num;//磁盘块数
    unsigned int block_remain;//磁盘块剩余数目
    unsigned int inode_table;//iNode表的存放偏移位置
    unsigned int inodemap_pos;//iNode节点位图空闲位图偏移位置
    unsigned int bitmap_pos;//空闲块位图偏移位置
    unsigned short blockSize;//块大小
    unsigned short blockSize_bit;//块大小占用位数
    unsigned long long maxBytes;//文件最大大小
    unsigned int first_data_block;//第一个数据块偏移位置
    unsigned int first_data_block_no;//第一个数据块号
    superBlock();
    ~superBlock();
    void printInfo();
    int init();//初始化新的superBlock
};

超级块存放的是文件系统的内容信息,需要经常更新的也只有inode_remain和block_remain的数目即可
在init函数中写死了iNode数目,init函数如下

int superBlock::init()
{
    this->blockSize = 1024;//块大小,字节
    this->inode_num = 10240;//i节点数目
    this->inode_remain = 10240;//i节点剩余数目
    this->block_num = 1024 * 100;//磁盘块数
    this->block_remain = 1024 * 100; //磁盘块剩余数
    this->inode_table = this->blockSize*1;
    this->inodemap_pos = ceil((this->inode_table + inode_num*sizeof(iNode)) / blockSize) * blockSize;//空闲iNode位图偏移位置
    this->bitmap_pos = ceil((inodemap_pos + inode_num/8)/blockSize)*blockSize;//空闲块位图偏移位置
    this->first_data_block = ceil(ceil(bitmap_pos + block_num / 8) / blockSize) * blockSize;//第一个数据块的位置
    this->first_data_block_no = ceil(first_data_block/blockSize)+1;//第一个数据块的号码
    this->blockSize_bit = 10;//块大小占用位数
    this->maxBytes = 1024*1024*10;//文件最大大小
    this->block_remain -= first_data_block_no;//去掉保留块
    return 1;
}

Dentry

Dentry是在内存中维护的内容,不写入硬盘,通过Dentry的父指针和子链表可以很方便的实现路径查找。

//内存中维护的目录项
class dentry
{
public:
    string fileName;
    string pathName;
    iNode inode;
    vector<unsigned int> block_list;//iNode对应的内容block_list
    vector<dentry*> child_list;
    dentry * parent;
    bool is_dir();//判断是否是目录
    void setParent(dentry *);//设置父亲节点
    void addChild(dentry *);//添加子节点
    void removeChild(dentry *s);//删除子节点
    void setSubDentry(vector<dentry *> list);//设置字目录
    void showDentry(vector<string> users);//显示目录
    void showItself(const vector<string> &users, string coverName="");//展示自己的dentry信息
    string getPathName();//获取路径名称
    vector<dir> getDirList();//将dentry转为dir
    dentry();
    dentry(string fileName,iNode inode);
    ~dentry();
};

总控制类

总控制类中有各类函数的声明和实现,对各种结构进行操作

#include "stdafx.h"
#include "superBlock.h"
#include "iNode.h"
#include "dentry.h"
#include "User.h"
#include <Windows.h>
#include <map>
#include "toolkit.h"

class FileSystem
{
public:
    const static int FOLDER_TYPE = 1;//文件夹类型
    const static int FILE_TYPE = 2;//文件类型
    const static int READ_ACCESS = 4;//读权限
    const static int WRITE_ACCESS = 2;//写权限
    const static int EXEC_ACCESS = 1;//执行权限
    const static int ACCESS_DENY = -100;//权限不足
    HANDLE hMapFile;//消息共享内存
    HANDLE usrMapFile;//用户token共享内存
    static const string fileName;//磁盘所在的文件名
    User currUser;//当前用户名字
    vector<User> userLists;//用户列表
    map<string,int> loginUserLists;//登录的用户列表
    superBlock s_block;//超级块
    iNode root;//根节点
    dentry root_dentry;//根目录
    dentry *curr_dentry;//工作目录,即当前目录
    int serve();//服务
    int parseCmd(string cmd);//解析命令
    void outputPrompt();//解析命令输出提示符
    FileSystem();
    ~FileSystem();
private:
    fstream fileDisk;//磁盘的文件流
    int init_root_dentry();//初始化根目录
    int init_user();//初始化用户
    int save_user();//保存用户
    int alloc_inode(unsigned long size,iNode &node,bool is_dentry = false);//申请iNode节点,size为字节
    int alloc_blocks(int num, vector<unsigned int> &list);
    int destroy_inode(int id);//销毁iNode节点
    int destroy_block(int id);//销毁block
    int withdraw_node(iNode node);//删除文件后的收回文件对应的节点和块
    int read_inode(int ino, iNode &node);//读取iNode节点信息
    int write_inode(iNode &node);//更新iNode信息
    int clearBlockContent(vector<unsigned int> list);//清空块内容
    int auth(string username, string pwd);//登录认证操作
    int generate_token(int u_id);//生成认证token,用于每次校验
    int get_shell_user();//获取当前的shell的用户,返回的是userlists中的下标
    int copy(string from, string to);
    int newfile(string name, unsigned long size=0);//创建文件
    int mkdir(string name);//创建文件夹
    int rd(string filename, bool force=false);//删除文件夹
    int del(string filename);//删除文件
    int cat(string filename);//读取文件并显示
    int cd(string filename);//切换工作目录
    int ls(string filename="");//展示目录
    int chmod(string filename, int i_mode);//修改文件权限
    vector<string> getUsers();//获取用户列表
    //用名称寻找目录或文件,指针引用,因为可能要修改地址,type默认寻找文件夹
    int findDentryWithName(string name, dentry *&p_dentry, int type = FOLDER_TYPE);
    //寻找目录或文件,指针引用,因为可能要修改地址,type默认寻找文件夹
    int findDentry(vector<string> list, dentry *&p_dentry, char firstChar, int type = FOLDER_TYPE);
    int InitDentry(dentry& p_dentry);//初始化dentry项
    int SaveDentry(dentry& p_dentry);//初始化dentry项
    template<typename T> int seekAndGet(unsigned long pos, T &item);//定位指针并读取
    template<typename T> int seekAndSave(unsigned long pos, T &item);//定位指针并存储
    int readBlockIds(iNode inode, vector<unsigned int> &blocks_list);//读取对应iNode的内容块,不包含间接块
    bool checkAccess(int access_type, iNode node);//检查权限,需要的权限access_type用rwx的整数表示
};