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

Author Avatar
CIC Mar 09, 2018
### 简介 简易Linux文件系统的实现，在现有机器硬盘上开辟100M的硬盘空间，作为设定的硬盘空间。设定块大小固定为1KB，用位图法管理iNode节点和空闲块。 需要实现的命令： - 展示路径(ls) - 改变目录(cd) - 创建目录 - 删除目录 - 创建文件 - 删除文件 - 预览文件 - 复制文件（从主机或者模拟盘双向复制）

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

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

关键数据结构

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

iNode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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

超级块的信息如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//超级块数据结构
#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函数如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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的父指针和子链表可以很方便的实现路径查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//内存中维护的目录项
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();
};

总控制类

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

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
#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的整数表示
};