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
|
journal
-------
signature
journal version
date/time ?
ext2 fs UUID
fs blocks
new size
blah
blah
endianity?
no journal (op. complete)
-------------------------
type (0)
inode journal
-------------
type (1)
'lastinode' field
|from inode (if 0, then end)
|to inode
|#references
|references
reference:
block #
offset
block journal
-------------
type (2)
new # of blocks
|from block (if 0, then end)
|to block
|ref block #
|ref offset
inode table move journal
------------------------
type (3)
group
stage we're in (0=moving from 'from' to 'via' 1=moving from 'via' to 'to')
# of blocks (redundant)
from block
via block
to block
when moving inodes
------------------
0. write journal (write the header last)
1. copy all inodes
2. update references
3. zero out old inodes (needed for ext2)
4. mark journal invalid
of course, update the bitmaps somewhere.
source and destination sets are disjoint of course.
where did it crash?
0. if there is no header, it crashed during step 0. nothing wrong. continue with 0.
or, it crashed after step 4. in that case: mark journal invalid. read an inode
to find out.
1. for each journal entry, see if the 'dest' inode is zero. if not all 'dest' inodes
are nonzero, _and_ none of the references have been updated it crashed between
0 and 1. just continue with step 1.
1. if some of the 'dest' inodes are nonzero and none of the references have been
updated it crashed during 1.
2. if all 'dest' inodes are nonzero but none of the references have been updated,
it crashed between 1 and 2. continue with step 2.
3. if all 'dest' inodes are nonzero and some of the references have been updated,
it crashed during step 2. just continue with step 2 (update the references
that have not been updated yet).
4. if all 'dest' inodes are nonzero and all of the references have been updated,
it crashed between step 2 and 3. just continue with step 3 (zeroing out the
inodes that are nonzero).
5. if all 'dest' inoeds are nonzero and some of the 'src' inodes are nonzero and all
references have been updated, it crashed during step 3. continue with step
3.
6. if all 'dest' inodes are nonzero and all of the 'src' inodes are zero and all
references have been updated, it crashed between 3 and 4. continue with step
4.
STEP HEADER SRC INODES DST INODES REFERENCES
no all occupied all zero none updated
0 no all occupied all zero none updated
yes all occupied all zero none updated
1 yes all occupied some occupied none updated
yes all occupied all occupied none updated
2 yes all occupied all occupied some updated
yes all occupied all occupied all updated
3 yes some zero all occupied all updated
yes all zero all occupied all updated
4 no all zero all occupied all updated
Blocks might be multiple HW sectors. So what if it crashes while writing the
header block? Write journal length and MD5 into header?
pull metadata or not?
when moving blocks
------------------
0. write journal
1. copy blocks
2. update references
3. mark journal invalid
0. if no header, crash during 0. continue with 0.
1. if no references have been updated, crash during 1. continue with 1.
2. if some references have been updated, crash during 2. continue with 2.
3. if all references have been updated, crash during 3. continue with 3.
Q: "But a reference might be moved itself too!"
A: "Yes, that's why we relocate the triply indirect blocks first, and then
the doubly indirect ones, then the singly indirect ones, and then the
ordinary ones. Go figure."
What a nasty remark! "Go figure." Well, if you haven't figured out
yet you can ask me about it. :-)
when moving metadata
--------------------
first find a place on the fs as big as the metadata.
1. search for a group which has enough blocks free.
if found: find enough contiguous free space, or else cluster the free space
if not found: move some blocks
2. move the metadata there
3. move it back
0. write header ("we're going to move it here and then back")
1. copy the metadata
2. update the gd ptr
3. update the header ("we moved it")
4. copy it back
5. update the gd ptr
6. invalidate the header
|
