实现一个文件系统

偶然看到sysplay（印度科学研究院的一家伙的blog，实现了一个用户态的文件系统 File Systems: The Semester Project，做个笔记。

说已经存在了很多的文件系统，但是没有最好的。每个文件系统都是针对特定的场景。

而了解系统最好的办法不是看文档，而是看代码。

所以产生了这个模拟文件系统(simula-ting file system file) 项目。该项目是用户态的一个文件系统。

Part 1：

通过文件模拟一个块设备，并格式化成定义的文件系统格式

首先要了解问价系统的概念，一个基本的文件系统包含两个重要的结构体：

超级块(supper block)和文件条目（file entry)

 1 #ifndef SFS_DS_H
 2 #define SFS_DS_H
 3 
 4 #define SIMULA_FS_TYPE 0x13090D15 /* Magic Number for our file system */
 5 #define SIMULA_FS_BLOCK_SIZE 512 /* in bytes */
 6 #define SIMULA_FS_ENTRY_SIZE 64 /* in bytes */
 7 #define SIMULA_FS_DATA_BLOCK_CNT ((SIMULA_FS_ENTRY_SIZE - (16 + 3 * 4)) / 4)
 8 
 9 #define SIMULA_DEFAULT_FILE ".sfsf"
10 
11 typedef unsigned int uint4_t;
12 
13 typedef struct sfs_super_block
14 {
15     uint4_t type; /* Magic number to identify the file system */
16     uint4_t block_size; /* Unit of allocation */
17     uint4_t partition_size; /* in blocks */
18     uint4_t entry_size; /* in bytes */ 
19     uint4_t entry_table_size; /* in blocks */
20     uint4_t entry_table_block_start; /* in blocks */
21     uint4_t entry_count; /* Total entries in the file system */
22     uint4_t data_block_start; /* in blocks */
23     uint4_t reserved[SIMULA_FS_BLOCK_SIZE / 4 - 8];
24 } sfs_super_block_t; /* Making it of SIMULA_FS_BLOCK_SIZE */
25 
26 typedef struct sfs_file_entry
27 {
28     char name[16];
29     uint4_t size; /* in bytes */
30     uint4_t timestamp; /* Seconds since Epoch */
31     uint4_t perms; /* Permissions for user */
32     uint4_t blocks[SIMULA_FS_DATA_BLOCK_CNT];
33 } sfs_file_entry_t;
34 
35 #endif

执行一下代码创建sfs_ds.h

cat << EOF |  sed -e "s/\	/	/" | tee sfs_ds.h
#ifndef SFS_DS_H
#define SFS_DS_H

#define SIMULA_FS_TYPE 0x13090D15 /* Magic Number for our file system */
#define SIMULA_FS_BLOCK_SIZE 512 /* in bytes */
#define SIMULA_FS_ENTRY_SIZE 64 /* in bytes */
#define SIMULA_FS_DATA_BLOCK_CNT ((SIMULA_FS_ENTRY_SIZE - (16 + 3 * 4)) / 4)

#define SIMULA_DEFAULT_FILE ".sfsf"

typedef unsigned int uint4_t;

typedef struct sfs_super_block
{
	uint4_t type; /* Magic number to identify the file system */
	uint4_t block_size; /* Unit of allocation */
	uint4_t partition_size; /* in blocks */
	uint4_t entry_size; /* in bytes */ 
	uint4_t entry_table_size; /* in blocks */
	uint4_t entry_table_block_start; /* in blocks */
	uint4_t entry_count; /* Total entries in the file system */
	uint4_t data_block_start; /* in blocks */
	uint4_t reserved[SIMULA_FS_BLOCK_SIZE / 4 - 8];
} sfs_super_block_t; /* Making it of SIMULA_FS_BLOCK_SIZE */

typedef struct sfs_file_entry
{
	char name[16];
	uint4_t size; /* in bytes */
	uint4_t timestamp; /* Seconds since Epoch */
	uint4_t perms; /* Permissions for user */
	uint4_t blocks[SIMULA_FS_DATA_BLOCK_CNT];
} sfs_file_entry_t;

#endif
EOF

View Code

这里面有很多冗余字段，都是可以通过其他字段可以计算得知。

代码实现 format_sfs.c

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <sys/types.h>
 4 #include <sys/stat.h>
 5 #include <fcntl.h>
 6 #include <unistd.h>
 7 
 8 #include "sfs_ds.h"
 9 
10 #define SFS_ENTRY_RATIO 0.10 /* 10% of all blocks */
11 #define SFS_ENTRY_TABLE_BLOCK_START 1
12 
13 sfs_super_block_t sb =
14 {
15     .type = SIMULA_FS_TYPE,
16     .block_size = SIMULA_FS_BLOCK_SIZE,
17     .entry_size = SIMULA_FS_ENTRY_SIZE,
18     .entry_table_block_start = SFS_ENTRY_TABLE_BLOCK_START
19 };
20 sfs_file_entry_t fe; /* All 0's */
21 
22 void write_super_block(int sfs_handle, sfs_super_block_t *sb)
23 {
24     write(sfs_handle, sb, sizeof(sfs_super_block_t));
25 }
26 void clear_file_entries(int sfs_handle, sfs_super_block_t *sb)
27 {
28     int i;
29 
30     for (i = 0; i < sb->entry_count; i++)
31     {
32         write(sfs_handle, &fe, sizeof(fe));
33     }
34 }
35 void mark_data_blocks(int sfs_handle, sfs_super_block_t *sb)
36 {
37     char c = 0;
38 
39     lseek(sfs_handle, sb->partition_size * sb->block_size - 1, SEEK_SET);
40     write(sfs_handle, &c, 1); /* To make the file size to partition size */
41 }
42 
43 int main(int argc, char *argv[])
44 {
45     int sfs_handle;
46 
47     if (argc != 2)
48     {
49         fprintf(stderr, "Usage: %s <partition size in 512-byte blocks>
",
50             argv[0]);
51         return 1;
52     }
53     sb.partition_size = atoi(argv[1]);
54     sb.entry_table_size = sb.partition_size * SFS_ENTRY_RATIO;
55     sb.entry_count = sb.entry_table_size * sb.block_size / sb.entry_size;
56     sb.data_block_start = SFS_ENTRY_TABLE_BLOCK_START + sb.entry_table_size;
57 
58     sfs_handle = creat(SIMULA_DEFAULT_FILE,
59         S_IRUSR | S_IWUSR | S_IRGRP | S_IROTH);
60     if (sfs_handle == -1)
61     {
62         perror("No permissions to format");
63         return 2;
64     }
65     write_super_block(sfs_handle, &sb);
66     clear_file_entries(sfs_handle, &sb);
67     mark_data_blocks(sfs_handle, &sb);
68     close(sfs_handle);
69     return 0;
70 }

执行一下代码创建format_sfs.c

cat << EOF |  sed -e "s/\	/	/g" | tee format_sfs.c
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>

#include "sfs_ds.h"

#define SFS_ENTRY_RATIO 0.10 /* 10% of all blocks */
#define SFS_ENTRY_TABLE_BLOCK_START 1

sfs_super_block_t sb =
{
	.type = SIMULA_FS_TYPE,
	.block_size = SIMULA_FS_BLOCK_SIZE,
	.entry_size = SIMULA_FS_ENTRY_SIZE,
	.entry_table_block_start = SFS_ENTRY_TABLE_BLOCK_START
};
sfs_file_entry_t fe; /* All 0's */

void write_super_block(int sfs_handle, sfs_super_block_t *sb)
{
	write(sfs_handle, sb, sizeof(sfs_super_block_t));
}
void clear_file_entries(int sfs_handle, sfs_super_block_t *sb)
{
	int i;

	for (i = 0; i < sb->entry_count; i++)
	{
		write(sfs_handle, &fe, sizeof(fe));
	}
}
void mark_data_blocks(int sfs_handle, sfs_super_block_t *sb)
{
	char c = 0;

	lseek(sfs_handle, sb->partition_size * sb->block_size - 1, SEEK_SET);
	write(sfs_handle, &c, 1); /* To make the file size to partition size */
}

int main(int argc, char *argv[])
{
	int sfs_handle;

	if (argc != 2)
	{
		fprintf(stderr, "Usage: %s <partition size in 512-byte blocks>
",
			argv[0]);
		return 1;
	}
	sb.partition_size = atoi(argv[1]);
	sb.entry_table_size = sb.partition_size * SFS_ENTRY_RATIO;
	sb.entry_count = sb.entry_table_size * sb.block_size / sb.entry_size;
	sb.data_block_start = SFS_ENTRY_TABLE_BLOCK_START + sb.entry_table_size;

	sfs_handle = creat(SIMULA_DEFAULT_FILE,
		S_IRUSR | S_IWUSR | S_IRGRP | S_IROTH);
	if (sfs_handle == -1)
	{
		perror("No permissions to format");
		return 2;
	}
	write_super_block(sfs_handle, &sb);
	clear_file_entries(sfs_handle, &sb);
	mark_data_blocks(sfs_handle, &sb);
	close(sfs_handle);
	return 0;
}
EOF

View Code

采用gcc模拟mkfs，生成一个.sfsf

gcc format_sfs.c -o format_sfs
./format_sfs 1024 # Partition size in blocks of 512-bytes
ls -al # List the .sfsf created with a size of 512 KiBytes

Part 2：

工具browse_sfs.c，显示文件系统的信息

quit – 退出
list – 显示文件
create <filename> – 创建文件
remove <filename> – 删除文件

  1 #include <stdio.h>
  2 #include <sys/types.h>
  3 #include <sys/stat.h>
  4 #include <fcntl.h>
  5 #include <unistd.h>
  6 #include <string.h>
  7 #include <time.h>
  8 
  9 #include "sfs_ds.h"
 10 
 11 sfs_super_block_t sb;
 12 
 13 void sfs_list(int sfs_handle)
 14 {
 15     int i;
 16     sfs_file_entry_t fe;
 17 
 18     lseek(sfs_handle, sb.entry_table_block_start * sb.block_size, SEEK_SET);
 19     for (i = 0; i < sb.entry_count; i++)
 20     {
 21         read(sfs_handle, &fe, sizeof(sfs_file_entry_t));
 22         if (!fe.name[0]) continue;
 23         printf("%-15s  %10d bytes  %c%c%c  %s",
 24             fe.name, fe.size,
 25             fe.perms & 04 ? 'r' : '-',
 26             fe.perms & 02 ? 'w' : '-',
 27             fe.perms & 01 ? 'x' : '-',
 28             ctime((time_t *)&fe.timestamp)
 29             );
 30     }
 31 }
 32 void sfs_create(int sfs_handle, char *fn)
 33 {
 34     int i;
 35     sfs_file_entry_t fe;
 36 
 37     lseek(sfs_handle, sb.entry_table_block_start * sb.block_size, SEEK_SET);
 38     for (i = 0; i < sb.entry_count; i++)
 39     {
 40         read(sfs_handle, &fe, sizeof(sfs_file_entry_t));
 41         if (!fe.name[0]) break;
 42         if (strcmp(fe.name, fn) == 0)
 43         {
 44             printf("File %s already exists
", fn);
 45             return;
 46         }
 47     }
 48     if (i == sb.entry_count)
 49     {
 50         printf("No entries left for : %s
", fn);
 51         return;
 52     }
 53 
 54     lseek(sfs_handle, -(off_t)(sb.entry_size), SEEK_CUR);
 55 
 56     strncpy(fe.name, fn, 15);
 57     fe.name[15] = 0;
 58     fe.size = 0;
 59     fe.timestamp = time(NULL);
 60     fe.perms = 07;
 61     for (i = 0; i < SIMULA_FS_DATA_BLOCK_CNT; i++)
 62     {
 63         fe.blocks[i] = 0;
 64     }
 65 
 66     write(sfs_handle, &fe, sizeof(sfs_file_entry_t));
 67 }
 68 void sfs_remove(int sfs_handle, char *fn)
 69 {
 70     int i;
 71     sfs_file_entry_t fe;
 72 
 73     lseek(sfs_handle, sb.entry_table_block_start * sb.block_size, SEEK_SET);
 74     for (i = 0; i < sb.entry_count; i++)
 75     {
 76         read(sfs_handle, &fe, sizeof(sfs_file_entry_t));
 77         if (!fe.name[0]) continue;
 78         if (strcmp(fe.name, fn) == 0) break;
 79     }
 80     if (i == sb.entry_count)
 81     {
 82         printf("File %s doesn't exist
", fn);
 83         return;
 84     }
 85 
 86     lseek(sfs_handle, -(off_t)(sb.entry_size), SEEK_CUR);
 87 
 88     memset(&fe, 0, sizeof(sfs_file_entry_t));
 89     write(sfs_handle, &fe, sizeof(sfs_file_entry_t));
 90 }
 91 
 92 void browse_sfs(int sfs_handle)
 93 {
 94     int done;
 95     char cmd[256], *fn;
 96     int ret;
 97 
 98     done = 0;
 99 
100     printf("Welcome to SFS Browsing Shell v1.0

");
101     printf("Block size     : %d bytes
", sb.block_size);
102     printf("Partition size : %d blocks
", sb.partition_size);
103     printf("File entry size: %d bytes
", sb.entry_size);
104     printf("Entry tbl size : %d blocks
", sb.entry_table_size);
105     printf("Entry count    : %d
", sb.entry_count);
106     printf("
");
107     while (!done)
108     {
109         printf(" $> ");
110         ret = scanf("%[^
]", cmd);
111         if (ret < 0)
112         {
113             done = 1;
114             printf("
");
115             continue;
116         }
117         else
118         {
119             getchar();
120             if (ret == 0) continue;
121         }
122         if (strcmp(cmd, "?") == 0)
123         {
124             printf("Supported commands:
");
125             printf("	?	quit	list	create	remove
");
126             continue;
127         }
128         else if (strcmp(cmd, "quit") == 0)
129         {
130             done = 1;
131             continue;
132         }
133         else if (strcmp(cmd, "list") == 0)
134         {
135             sfs_list(sfs_handle);
136             continue;
137         }
138         else if (strncmp(cmd, "create", 6) == 0)
139         {
140             if (cmd[6] == ' ')
141             {
142                 fn = cmd + 7;
143                 while (*fn == ' ') fn++;
144                 if (*fn != '') // (char) 0 145                 {
146                     sfs_create(sfs_handle, fn);
147                     continue;
148                 }
149             }
150         }
151         else if (strncmp(cmd, "remove", 6) == 0)
152         {
153             if (cmd[6] == ' ')
154             {
155                 fn = cmd + 7;
156                 while (*fn == ' ') fn++;
157                 if (*fn != '') // (char) 0
158                 {
159                     sfs_remove(sfs_handle, fn);
160                     continue;
161                 }
162             }
163         }
164         printf("Unknown/Incorrect command: %s
", cmd);
165         printf("Supported commands:
");
166         printf("	?	quit	list	create <file>	remove <file>
");
167     }
168 }
169 
170 int main(int argc, char *argv[])
171 {
172     char *sfs_file = SIMULA_DEFAULT_FILE;
173     int sfs_handle;
174 
175     if (argc > 2)
176     {
177         fprintf(stderr, "Incorrect invocation. Possibilities are:
");
178         fprintf(stderr,
179             "	%s /* Picks up %s as the default partition_file */
",
180             argv[0], SIMULA_DEFAULT_FILE);
181         fprintf(stderr, "	%s [ partition_file ]
", argv[0]);
182         return 1;
183     }
184     if (argc == 2)
185     {
186         sfs_file = argv[1];
187     }
188     sfs_handle = open(sfs_file, O_RDWR);
189     if (sfs_handle == -1)
190     {
191         fprintf(stderr, "Unable to browse SFS over %s
", sfs_file);
192         return 2;
193     }
194     read(sfs_handle, &sb, sizeof(sfs_super_block_t));
195     if (sb.type != SIMULA_FS_TYPE)
196     {
197         fprintf(stderr, "Invalid SFS detected. Giving up.
");
198         close(sfs_handle);
199         return 3;
200     }
201     browse_sfs(sfs_handle);
202     close(sfs_handle);
203     return 0;
204 }

通过以下命令创建 browse_sfs.c

cat << EOF |  sed -e "s/\	/	/g" | tee browse_sfs.c
#include <stdio.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <string.h>
#include <time.h>

#include "sfs_ds.h"

sfs_super_block_t sb;

void sfs_list(int sfs_handle)
{
	int i;
	sfs_file_entry_t fe;

	lseek(sfs_handle, sb.entry_table_block_start * sb.block_size, SEEK_SET);
	for (i = 0; i < sb.entry_count; i++)
	{
		read(sfs_handle, &fe, sizeof(sfs_file_entry_t));
		if (!fe.name[0]) continue;
		printf("%-15s  %10d bytes  %c%c%c  %s",
			fe.name, fe.size,
			fe.perms & 04 ? 'r' : '-',
			fe.perms & 02 ? 'w' : '-',
			fe.perms & 01 ? 'x' : '-',
			ctime((time_t *)&fe.timestamp)
			);
	}
}
void sfs_create(int sfs_handle, char *fn)
{
	int i;
	sfs_file_entry_t fe;

	lseek(sfs_handle, sb.entry_table_block_start * sb.block_size, SEEK_SET);
	for (i = 0; i < sb.entry_count; i++)
	{
		read(sfs_handle, &fe, sizeof(sfs_file_entry_t));
		if (!fe.name[0]) break;
		if (strcmp(fe.name, fn) == 0)
		{
			printf("File %s already exists
", fn);
			return;
		}
	}
	if (i == sb.entry_count)
	{
		printf("No entries left for : %s
", fn);
		return;
	}

	lseek(sfs_handle, -(off_t)(sb.entry_size), SEEK_CUR);

	strncpy(fe.name, fn, 15);
	fe.name[15] = 0;
	fe.size = 0;
	fe.timestamp = time(NULL);
	fe.perms = 07;
	for (i = 0; i < SIMULA_FS_DATA_BLOCK_CNT; i++)
	{
		fe.blocks[i] = 0;
	}

	write(sfs_handle, &fe, sizeof(sfs_file_entry_t));
}
void sfs_remove(int sfs_handle, char *fn)
{
	int i;
	sfs_file_entry_t fe;

	lseek(sfs_handle, sb.entry_table_block_start * sb.block_size, SEEK_SET);
	for (i = 0; i < sb.entry_count; i++)
	{
		read(sfs_handle, &fe, sizeof(sfs_file_entry_t));
		if (!fe.name[0]) continue;
		if (strcmp(fe.name, fn) == 0) break;
	}
	if (i == sb.entry_count)
	{
		printf("File %s doesn't exist
", fn);
		return;
	}

	lseek(sfs_handle, -(off_t)(sb.entry_size), SEEK_CUR);

	memset(&fe, 0, sizeof(sfs_file_entry_t));
	write(sfs_handle, &fe, sizeof(sfs_file_entry_t));
}

void browse_sfs(int sfs_handle)
{
	int done;
	char cmd[256], *fn;
	int ret;

	done = 0;

	printf("Welcome to SFS Browsing Shell v1.0

");
	printf("Block size	 : %d bytes
", sb.block_size);
	printf("Partition size : %d blocks
", sb.partition_size);
	printf("File entry size: %d bytes
", sb.entry_size);
	printf("Entry tbl size : %d blocks
", sb.entry_table_size);
	printf("Entry count	: %d
", sb.entry_count);
	printf("
");
	while (!done)
	{
		printf(" $> ");
		ret = scanf("%[^
]", cmd);
		if (ret < 0)
		{
			done = 1;
			printf("
");
			continue;
		}
		else
		{
			getchar();
			if (ret == 0) continue;
		}
		if (strcmp(cmd, "?") == 0)
		{
			printf("Supported commands:
");
			printf("	?	quit	list	create	remove
");
			continue;
		}
		else if (strcmp(cmd, "quit") == 0)
		{
			done = 1;
			continue;
		}
		else if (strcmp(cmd, "list") == 0)
		{
			sfs_list(sfs_handle);
			continue;
		}
		else if (strncmp(cmd, "create", 6) == 0)
		{
			if (cmd[6] == ' ')
			{
				fn = cmd + 7;
				while (*fn == ' ') fn++;
				if (*fn != '') // (char) 0 
				{
					sfs_create(sfs_handle, fn);
					continue;
				}
			}
		}
		else if (strncmp(cmd, "remove", 6) == 0)
		{
			if (cmd[6] == ' ')
			{
				fn = cmd + 7;
				while (*fn == ' ') fn++;
				if (*fn != '') // (char) 0 
				{
					sfs_remove(sfs_handle, fn);
					continue;
				}
			}
		}
		printf("Unknown/Incorrect command: %s
", cmd);
		printf("Supported commands:
");
		printf("	?	quit	list	create <file>	remove <file>
");
	}
}

int main(int argc, char *argv[])
{
	char *sfs_file = SIMULA_DEFAULT_FILE;
	int sfs_handle;

	if (argc > 2)
	{
		fprintf(stderr, "Incorrect invocation. Possibilities are:
");
		fprintf(stderr,
			"	%s /* Picks up %s as the default partition_file */
",
			argv[0], SIMULA_DEFAULT_FILE);
		fprintf(stderr, "	%s [ partition_file ]
", argv[0]);
		return 1;
	}
	if (argc == 2)
	{
		sfs_file = argv[1];
	}
	sfs_handle = open(sfs_file, O_RDWR);
	if (sfs_handle == -1)
	{
		fprintf(stderr, "Unable to browse SFS over %s
", sfs_file);
		return 2;
	}
	read(sfs_handle, &sb, sizeof(sfs_super_block_t));
	if (sb.type != SIMULA_FS_TYPE)
	{
		fprintf(stderr, "Invalid SFS detected. Giving up.
");
		close(sfs_handle);
		return 3;
	}
	browse_sfs(sfs_handle);
	close(sfs_handle);
	return 0;
}
EOF

View Code

执行

gcc browse_sfs.c -o browse_sfs
sudo apt install rlwrap  -y
rlwrap ./browse_sfs

will get the result

$ rlwrap ./browse_sfs
Welcome to SFS Browsing Shell v1.0

Block size       : 512 bytes
Partition size : 1024 blocks
File entry size: 64 bytes
Entry tbl size : 102 blocks
Entry count     : 816

 $> list
 $> create aaaa
 $> create bbbb
 $> list
aaaa                      0 bytes  rwx  Thu Jun 24 14:48:20 2973
bbbb                      0 bytes  rwx  Thu Jun 24 14:48:26 2973
 $> ?
Supported commands:
        ?       quit    list    create  remove