ECS 150 – Project 3
Prof. Joël Porquet-Lupine
UC Davis – 2020/2021
Copyright © 2017-2021 Joël Porquet-Lupine – CC BY-NC-SA 4.0 International License
1 / 34
Goal
Implement support for a very simple filesystem: ECS150-FS API for applications to read/write files from/to this filesystem
/* Mounting filesystem */
int fs_mount(const char *diskname); int fs_umount(void);
int fs_info(void);
/* Creating files */
int fs_create(const char *filename); int fs_delete(const char *filename); int fs_ls(void);
/* Opening files */
int fs_open(const char *filename); int fs_close(int fd);
int fs_stat(int fd);
int fs_lseek(int fd, size_t offset);
/* Modifying files */
int fs_write(int fd, void *buf, size_t count); int fs_read(int fd, void *buf, size_t count);
2 / 34
Big picture: reality
User-space Kernel-space
Library interface (open(), read(), write())
Syscall interface
(sys_open, sys_read, sys_write)
Virtual File System (VFS)
Block-based FS
Ext2/3/4 VFAT
Hardware
Problems
Block interface (block_read(), block_write())
Hardware interface (memory-mapped registers)
Vast majority the filesystem management is in kernel mode! Need an actual physical disk…
Application
C Standard Library (Libc)
Block device driver
Disk
3 / 34
Simplication
Emulating a disk with a file
A disk, or a partition on a disk, merely represents contiguous binary data storage How can we easily emulate any size of contiguous data?…
With a file!
$ dd if=/dev/zero of=emulated_disk_space bs=4K count=8192 # 8192 * 4K = 32M $ ls -l emulated_disk_space
-rw-r–r– 1 joel joel 32M 2017-03-01 13:52 emulated_disk_space
$ xxd emulated_disk_space
00000000: 0000 0000 0000 0000 0000 0000 0000 0000 ……………. 00000010: 0000 0000 0000 0000 0000 0000 0000 0000 ……………. 00000020: 0000 0000 0000 0000 0000 0000 0000 0000 ……………. 00000030: 0000 0000 0000 0000 0000 0000 0000 0000 ……………. 00000040: 0000 0000 0000 0000 0000 0000 0000 0000 ……………. 00000050: 0000 0000 0000 0000 0000 0000 0000 0000 ……………. 00000060: 0000 0000 0000 0000 0000 0000 0000 0000 ……………. 00000070: 0000 0000 0000 0000 0000 0000 0000 0000 ……………. 00000080: 0000 0000 0000 0000 0000 0000 0000 0000 ……………. 00000090: 0000 0000 0000 0000 0000 0000 0000 0000 ……………. …
01fffff0: 0000 0000 0000 0000 0000 0000 0000 0000 …………….
4 / 34
Simplication
Replacing the disk
User-space Kernel-space
Library interface (open(), read(), write())
Syscall interface
(sys_open, sys_read, sys_write)
Application
C Standard Library (Libc)
Virtual File System (VFS)
Block-based FS
Ext2/3/4 VFAT
Block device driver
File
Disk
Block interface (block_read(), block_write())
Hardware
Emulation of a disk
Hardware interface
open(), read(), write()
(memory-mapped registers)
5 / 34
Simplication
Accessing a file by blocks
#define BLOCK_SIZE 4096 static int fd;
/* Open virtual disk */
int block_open(char *disk_filename) {
fd = open(disk_filename, O_RDWR);
}
/* Read block at @block_nr into @buf */
int block_read(size_t block_nr, void *buf) {
lseek(fd, block_nr * BLOCK_SIZE);
read(fd, buf, BLOCK_SIZE);
}
/* Write block at @block_nr with @buf’s contents */
int block_write(size_t block_nr, void *buf) {
lseek(fd, block_nr * BLOCK_SIZE);
write(fd, buf, BLOCK_SIZE);
}
6 / 34
Simplication
Replacing the block device driver
User-space Kernel-space
Library interface (open(), read(), write())
Syscall interface
(sys_open, sys_read, sys_write)
Application
C Standard Library (Libc)
Virtual File System (VFS)
Block-based FS
Ext2/3/4 VFAT
Hardware interface blocBkl_ocokpientne(rf)a,ce
(memory-mapped registers)
block_read(), block_write()
(block_read(), block_write())
Block file access
Block device driver
disk.[ch]
Hardware
Emulation of a disk
Hardware interface
open(), read(), write()
(memory-mapped registers)
File
Disk
7 / 34
Simplication
Replacing the libc/vfs/fs drivers
User-space Kernel-space
Syscall interface
(sys_open, sys_read, sys_write)
C Standard Library (Libc)
File system layer
(ECS150-FS specific)
Virtual File System (VFS)
fs.[ch]
Block-based FS
Ext2/3/4 VFAT
Hardware interface blocBkl_ocokpientne(rf)a,ce
(memory-mapped registers)
block_read(), block_write()
(block_read(), block_write())
Block layer
Block device driver
disk.[ch]
Hardware
Emulation of a disk
That’s the project!
8 / 34
Application
Hardware interface
open(), read(), write()
(memory-mapped registers)
File
Disk
fs_open(), fs_read()
Library interface
(opefsn_()w, rreiated(),,wfsrit_es()e) ek(),
…
ECS150-FS
Layout
Disk is divided into blocks
Each block is 4096 bytes Blocks are of different types
Super Block
FAT #0
FAT cont’ed
FAT end
Root Directory
Data Block #0
Data Block #1
Data Block #n
Example
Example with filesystem embedding 8192 data blocks:
Amount of data blocks: 8192
Number of blocks for FAT: (8192 * 2) / 4096 = 4 Total amount of blocks: 1 + 4 + 1 + 8192 = 8198 Root directory block index: 5
Data block start index: 6
$ ./fs_make.x disk.fs 8192
Creating virtual disk ‘disk.fs’ with ‘8192’ data blocks
9 / 34
ECS150-FS
Superblock
Very first block of the disk
Contains information about filesystem
High-level layout
Offset
Length (bytes)
Description
0x00
8
Signature (must be equal to “ECS150FS”)
0x08
2
Total amount of blocks of virtual disk
0x0A
2
Root directory block index
0x0C
2
Data block start index
0x0E
2
Amount of data blocks
0x10
1
Number of blocks for FAT
0x11
4079
Unused/Padding
10 / 34
ECS150-FS
Superblock At byte level
0x0000
0x0004
0x0008 0x000C
FAT blocks
0x04
0x0 0x1 0x2 0x3
$ ./fs_make.x disk.fs 8192 …
$ xxd -c 4 -g 1 disk.fs | head 00000000: 45 43 53 31 ECS1
ECS1 00000004: 35 30 46 53 50FS
Signature
00000008: 06 20 05 00 . ..
0000000c: 06 00 00 20 …
00000010: 04 00 00 00 ….
50FS 00000014: 00 00 00 00 …. 00000018: 00 00 00 00 ….
total blocks
0x06 0x20
data blk idx
0x06 0x00
root dir idx
0x05 0x00
total data blks
0x00 0x20 xxx xxx
xxx xxx
0000001c: 00 00 00 00 ….
00000020: 00 00 00 00 ….
00000024: 00 00 00 00 ….
…
$
0x0010 … 0xFFFC
xxx
xxx xxx
11 / 34
ECS150-FS
Superblock
Filesystem driver will need to read superblock and interpret it
C data structure
Key points:
The integer types must match exactly those of the specification It must represent the entirety of the block, padding included!
struct superblock{ ???
};
12 / 34
Digression
Integer types
Is always 8 bits?
char
Is
Is always 32 bits? Etc.
C specifications
short int
always 16 bits?
int
Type
Specification
char
“Smallest addressable unit of the machine that can contain basic character set”
short
“Capable of containing at least the [−32767, +32767] range; thus, it is at least 16 bits in size.”
int
“Capable of containing at least the [−32767, +32767] range; thus, it is at least 16 bits in size.”
long
“Capable of containing at least the [−2147483647, +2147483647] range; thus, it is at least 32 bits in size.”
Only guarantees minimum ranges…
13 / 34
Digression
Integer types
Specified-width integers
Use integer types that have exact widths (since C99):
#include
/* Signed version */
int8_t
int16_t
int32_t
/* Unsigned version */
uint8_t
uint16_t
uint32_t
14 / 34
Digression
Reading data structures from a file (or buffer)
Reading data from a file (or whatever blob of data), for which I know the layout. It can easily be type-casted into a structure instance.
0x0 0x1 0x2 0x3
struct mystruct {
int32_t a;
int16_t b;
int16_t c;
int32_t padding[2];
}; // 16 bytes
fd = open(“file”, O_RDWR); …
char buf[16];
read(bd, buf, 16);
struct mystruct *s = buf; printf(“s->a = %d\n”, s->a);
s->a = 0;
write(bd, buf, 16);
0x0000
0x0004
0x0008
0x000C
/* or simply */
a bc
padding
struct mystruct obj; read(bd, &obj, sizeof(obj));
printf(“obj.a = %d\n”, obj.a);
obj.a = 0;
write(bd, &obj, sizeof(obj));
15 / 34
ECS150-FS
Layout FAT
Big array of 16-bit entries: linked-list of data blocks composing a file
2048 entries per FAT block
Spans multiple blocks if more than 2048 data blocks to manage Three possible values for each entry:
0: corresponding data block is available : last data block of a file
: index of next data block
Super Block
FAT #0
FAT cont’ed
FAT end
Root Directory
Data Block #0
Data Block #1
Data Block #n
FAT_EOC
!=0 && !=FAT_EOC
16 / 34
ECS150-FS
Layout
Root directory
Single block
32-byte entry per file 128 entries total
Super Block
FAT #0
FAT cont’ed
FAT end
Root Directory
Data Block #0
Data Block #1
Data Block #n
Offset
Length (bytes)
Description
0x00
16
Filename (including NULL character)
0x10
4
Size of the file (in bytes)
0x14
2
Index of the first data block
0x16
10
Unused/Padding
17 / 34
ECS150-FS
Example: big file, small file, empty file
Root directory
<"test1", 22000, 2>,
<"test2", 5000, 1>,
<"test3", 0, FAT_EOC> …
FAT Data blocks
00 11 22 33 4 FAT_EOC 4 55 66 77 8 FAT_EOC 8 99
10 10
(test2, block #0)
(test1, block #0)
(test1, block #1)
(test2, block #1)
(test1, block #2)
(test1, block #3)
(test1, block #4)
(test1, block #5)
4
3
5
6
7
8
0
0
18 / 34
Implementation
Phase 1: Volume mounting
fs_mount():
Open the virtual disk
Read the metadata (superblock, fat, root directory)
fs_umount():
Close virtual disk (make sure that virtual disk is up-to-date)
fs_info():
Show information about volume
19 / 34
Implementation
Phase 2: File creation/deletion
fs_create(): Create a new file
Initially, size is 0 and pointer to first data block is FAT_EOC fs_delete():
Delete an existing file
Free allocated data blocks, if any fs_ls():
List all the existing files
20 / 34
Implementation
Phase 3: File descriptor operations
fs_open():
Initialize and return file descriptor
32 file descriptors max
Can open same file multiple times Contains file’s offset (initially 0)
fs_close():
Close file descriptor
fs_seek():
Move file’s offset
fs_stat():
Return file’s size
None of these functions should change the filesystem…
21 / 34
Implementation
Phase 4: File reading/writing
Most complicated phase (don’t keep it for the last day!)
fs_read():
Read a certain number of bytes from a file
fs_write():
Write a certain number of bytes to a file Extend file if necessary
22 / 34