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 | # 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 free space
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|S|b|b|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 - where file contents are stored
- I: inode blocks - where metadata is stored
- f: free space information
- S: superblock - disk metadata
- free space information: usually tracked as an array of size= number of blocks
- the array is an array of _bits_ (rather than booleans/ints)
- 1 means free / 0 means taken (allocated)
- /home/ferd/docs/info.txt
- directories:
- i-node (entry) - metadata about directory
- data block - contents of the directory
- storing /:
- allocate inode 0: conventional entry for root dir
- store the creation date, owner, access rights, etc.
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|S|i|b|I|_|_|_|_|R|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
0 7 15 23 31
- allocate a data block for the root directory
- directory: maps filenames (also directory names) to inode numbers
- the first entry in a directory is '.' which points to the inode of the directory itself
root directory:
. 0
- for a new filestystem: allocate and inode for the root dir
- and allocate a datablock containing a reference to the root dir
- mark the blocks as taken in the block bitmap
- mark the inode entry for / as taken in the inode bitmap
- `open("/data.txt", O_CREAT | ..., 0644)`
- create directory entry for data.txt
- create an inode entry for the new file
- allocate a data block for the new file
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|S|i|b|I|_|_|_|_|R|_|h|f|t|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
0 7 15 23 31
0. check whether the directories along the path exist and whether the user has the appropriate access rights for them
1. create an inode entry for the new file
- allocate inode => 1
- populate inode with info
user: ferd
created: (current date and time)
access mode: 0644
group: users
blocks:
2. create directory entry in /
- grab inode 0
- find the data block => 8
- check if file exists, if doesn't create a new inode entry
. 0
data.txt 1
3. allocate a data block
- grab the first available data block => 8
- update inode entry with block: 8
user: ferd
created: (current date and time)
access mode: 0644
group: users
blocks: 8
4. If writing data
- find the data block, write the data at the appropriate offset
- `mkdir /home`
1. grab an inode => 2 (mark it as allocated)
2. fill it in with the metadata (user, access, timestamps, ...)
3. add to root directory entry (in block 7)
home 2
4. grab a free data block => 9 (mark it as allocated)
- store
. 2
- `mkdir /home/ferd`
1. grab an inode => 3, populate
2. grab a data block, insert entry for .
3. add entry to data block 9
- `echo hello > /home/ferd/hello.txt`
- create a new file in /home/ferd, and write string "hello" into it
1. check that space is available
2. `/`: go to inode 0, check that user has access, find its data block
3. find `home` in `/`: take its inode (2), check that user has access, go to its data block
4. find `ferd` in `home`: take `ferd`'s inode, check that current user has access, go to its data block
5. grab a free inode entry => 4, populate
6. grab a free block => 12 (t)
7. write block number to inode
8. add directory entry to `ferd`
. 3
hello.txt 4
9. write "hello" to block 12 at offset 0
- `rm /data.txt`
1. find entry in `/`
2. remove the `data.txt` entry from `/`'s directory
3. go to `data.txt`'s inode
4. mark its block 9 as free
5. mark the inode 1 as free
- `cat 5kofdata.txt > /home/ferd/hello.txt`
1. ... traverse /, home, ferd to find the inode for hello.txt
2. check whether we have enough data blocks
3. allocate additional block => 9
4. write first 4K into block 12
5. write remaining 1K into block 9
6. update the inode with `blocks: 12, 9`
- my inode entry can store at most 4 block numbers (pointers)
- say that a block no. takes 4 bytes
- I want to be able to support arbitrarily large files, but optimize for small ones
- dedicate one block no. as an indirect pointer
- data block will point to other block numbers
- with 4 bytes per bloc no, this gives me 1024 blocks
- gives me a max file size of ~4MB
|