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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183 | # More on File system implementation
- Recap - purpose of a FS:
1. Translate name+offset to disks blocks
2. Keep track of free space
## Implementation
- Storage (i.e., disk, disk image, memory) organized into blocks
- Block = 4096 bytes = 4 KB
- Example: 32 blocks = 128 KB disk
- Need to store:
1. file contents
2. file information (metadata): owner, group, access rights, timestamps, size, where the file is stored
3. where things are: directory structure
4. where is the free space
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|S|b|i|I|I|I|I|I|D|D|D|D|D|D|D|D|D|D|D|D|D|D|D|D|D|D|D|D|D|D|D|D|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
0 7 15 23 31
- D: data blocks
- I: inode blocks
- S: superblock
- F: free space management struct
- free space management
- array of true/false (true = free, false = taken)
- e.g., free[10] gives me whether block 10 is free or not
- we effectively have an array of bits
- to manage 32 blocks: we only need 32 / 8 bytes = 4 bytes
- Inode table
- stores an array of inodes (inode entries)
- each entry: owner (user/group), access mode, timestamps, refcount, blocks occupied by contents
- Directory: map from filenames to inode numbers
- has its own inode entry (like a file, just marked as a dir)
- stores information about entries in its data block
file1 23
info.txt 42
documents/ 3
### Create a new FS
1. Start populating the Superblock
2. Write the initial bitmaps
3. Allocate blocks for inode table (say, 5 blocks)
4. Create the root directory `/`
a) allocate root dir inode entry => 0
b) allocate root dir block for directory entries => 8
c) populate block no. 8 with
. 0
### Create a file
`echo "hello" > /hello.txt`
- `open("/hello", O_CREAT | ..., 0644)`
- `write("/hello", "hello", 5)`
- `close("/hello")`
1. Grab a free inode => 1
2. Grab a free block => 9
3. Check permissions for root dir / whether file exists
4. Write "hello" to block 9 at offset 0
5. Populate the inode
6. Write the directory entry in block 8
. 0
hello.txt 1
### Create a directory
`mkdir /home`
1. Check permissions for root dir / whether directory exists
2. Grab a new inode entry => 2
3. Grab a new data block => 10 (for entries)
4. Write directory into the data block
. 2
.. 0
5. Populate inode
6. Add entry to `/` (block 8)
. 0
hello.txt 1
home 2
### Create a file bigger than one block in another dir
`echo "...loooong text..." > /home/big.txt`
- size 5096B
- look for `home` in `/`, look for `big.txt` in `home`
1. Grab inode 0 (for `/`), check permissions, look for data block (8)
2. Read block 8, find inode for `home` (2)
3. Read inode for `home`, check permissions, look for data block (10)
4. Read block 10, find inode for `big.txt`, if doesn't exists create...
5. Allocate inode => 3
6. Allocate 2 blocks => 11, 12
7. Write first 4096B into block 11
8. Write remaining 1000B into block 12
9. Populate the inode
10. Add directory entry to block 10
. 2
.. 0
big.txt 3
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|S|b|i|I|I|I|I|I|/|h|g|g| | | | | | | | | | | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
0 7 15 23 31
Legend:
- S - superblock
- b - block bitmap
- i - inode bitmap
- I - inode table block containing several inodes
- / - root directory data block
- h - hello.txt data block
- g - big.txt data block
Bitmaps:
7
b: 0000000001000111111...
i: 0000111111111111111...
### Delete `/hello.txt`
`rm /hello.txt`
1. Get the root inode (0)
2. Check permission, find data block => 8
3. Read block 8 to get entries, find `hello.txt`, get inode => 1
4. Read inode 1, check permissions: user can modify and is a file
5. Remove from directory: remove from block 8
6. Dealloc data block (mark it as free)
7. Dealloc inode (mark it as free)
Inodes:
0:
own: ferd/users
acc: 040755
siz: ??
ts: ...
ref: 1
bl: [8, -, -, -]
1: (this one got deleted in the last step)
own: ferd/users
acc: 010644
siz: 5
ts: ...
ref: 0
bl: [9, -, -, -]
2:
own: ferd/users
acc: 040755
siz: ??
ts: ...
ref: 2
bl: [10, -, -, -]
2:
own: ferd/uses
acc: 010644
siz: 5096
ts: ...
ref: 1
bl: [11, 12, -, -]
|