Commit | Line | Data |
---|---|---|
3edcb7c8 KB |
1 | .\" Copyright (c) 1982 The Regents of the University of California. |
2 | .\" All rights reserved. | |
a38b2411 | 3 | .\" |
3edcb7c8 KB |
4 | .\" %sccs.include.redist.roff% |
5 | .\" | |
b7956604 | 6 | .\" @(#)3.t 4.5 (Berkeley) %G% |
a38b2411 KM |
7 | .\" |
8 | .ds RH Fixing corrupted file systems | |
9 | .NH | |
10 | Fixing corrupted file systems | |
11 | .PP | |
12 | A file system | |
13 | can become corrupted in several ways. | |
14 | The most common of these ways are | |
15 | improper shutdown procedures | |
16 | and hardware failures. | |
17 | .PP | |
18 | File systems may become corrupted during an | |
19 | .I "unclean halt" . | |
20 | This happens when proper shutdown | |
21 | procedures are not observed, | |
22 | physically write-protecting a mounted file system, | |
23 | or a mounted file system is taken off-line. | |
24 | The most common operator procedural failure is forgetting to | |
25 | .I sync | |
26 | the system before halting the CPU. | |
27 | .PP | |
28 | File systems may become further corrupted if proper startup | |
29 | procedures are not observed, e.g., | |
30 | not checking a file system for inconsistencies, | |
31 | and not repairing inconsistencies. | |
32 | Allowing a corrupted file system to be used (and, thus, to be modified | |
33 | further) can be disastrous. | |
34 | .PP | |
35 | Any piece of hardware can fail at any time. | |
36 | Failures | |
37 | can be as subtle as a bad block | |
38 | on a disk pack, or as blatant as a non-functional disk-controller. | |
39 | .NH 2 | |
40 | Detecting and correcting corruption | |
41 | .PP | |
42 | Normally | |
43 | .I fsck | |
44 | is run non-interactively. | |
45 | In this mode it will only fix | |
46 | corruptions that are expected to occur from an unclean halt. | |
47 | These actions are a proper subset of the actions that | |
48 | .I fsck | |
49 | will take when it is running interactively. | |
50 | Throughout this paper we assume that | |
51 | .I fsck | |
52 | is being run interactively, | |
53 | and all possible errors can be encountered. | |
54 | When an inconsistency is discovered in this mode, | |
55 | .I fsck | |
56 | reports the inconsistency for the operator to | |
57 | chose a corrective action. | |
58 | .PP | |
59 | A quiescent\(dd | |
60 | .FS | |
61 | \(dd I.e., unmounted and not being written on. | |
62 | .FE | |
63 | file system may be checked for structural integrity | |
64 | by performing consistency checks on the | |
65 | redundant data intrinsic to a file system. | |
66 | The redundant data is either read from | |
67 | the file system, | |
68 | or computed from other known values. | |
69 | The file system | |
70 | .B must | |
71 | be in a quiescent state when | |
72 | .I fsck | |
73 | is run, | |
74 | since | |
75 | .I fsck | |
76 | is a multi-pass program. | |
77 | .PP | |
78 | In the following sections, | |
79 | we discuss methods to discover inconsistencies | |
80 | and possible corrective actions | |
81 | for the cylinder group blocks, the inodes, the indirect blocks, and | |
82 | the data blocks containing directory entries. | |
83 | .NH 2 | |
84 | Super-block checking | |
85 | .PP | |
86 | The most commonly corrupted item in a file system | |
87 | is the summary information | |
88 | associated with the super-block. | |
89 | The summary information is prone to corruption | |
90 | because it is modified with every change to the file | |
91 | system's blocks or inodes, | |
92 | and is usually corrupted | |
93 | after an unclean halt. | |
94 | .PP | |
95 | The super-block is checked for inconsistencies | |
96 | involving file-system size, number of inodes, | |
97 | free-block count, and the free-inode count. | |
98 | The file-system size must be larger than the | |
99 | number of blocks used by the super-block | |
100 | and the number of blocks used by the list of inodes. | |
101 | The file-system size and layout information | |
102 | are the most critical pieces of information for | |
103 | .I fsck . | |
104 | While there is no way to actually check these sizes, | |
105 | since they are statically determined by | |
106 | .I newfs , | |
107 | .I fsck | |
108 | can check that these sizes are within reasonable bounds. | |
109 | All other file system checks require that these sizes be correct. | |
110 | If | |
111 | .I fsck | |
112 | detects corruption in the static parameters of the default super-block, | |
113 | .I fsck | |
114 | requests the operator to specify the location of an alternate super-block. | |
115 | .NH 2 | |
116 | Free block checking | |
117 | .PP | |
118 | .I Fsck | |
119 | checks that all the blocks | |
120 | marked as free in the cylinder group block maps | |
121 | are not claimed by any files. | |
122 | When all the blocks have been initially accounted for, | |
123 | .I fsck | |
124 | checks that | |
125 | the number of free blocks | |
126 | plus the number of blocks claimed by the inodes | |
127 | equals the total number of blocks in the file system. | |
128 | .PP | |
129 | If anything is wrong with the block allocation maps, | |
130 | .I fsck | |
131 | will rebuild them, | |
132 | based on the list it has computed of allocated blocks. | |
133 | .PP | |
134 | The summary information associated with the super-block | |
135 | counts the total number of free blocks within the file system. | |
136 | .I Fsck | |
137 | compares this count to the | |
138 | number of free blocks it found within the file system. | |
139 | If the two counts do not agree, then | |
140 | .I fsck | |
141 | replaces the incorrect count in the summary information | |
142 | by the actual free-block count. | |
143 | .PP | |
144 | The summary information | |
145 | counts the total number of free inodes within the file system. | |
146 | .I Fsck | |
147 | compares this count to the number | |
148 | of free inodes it found within the file system. | |
149 | If the two counts do not agree, then | |
150 | .I fsck | |
151 | replaces the incorrect count in the | |
152 | summary information by the actual free-inode count. | |
153 | .NH 2 | |
154 | Checking the inode state | |
155 | .PP | |
156 | An individual inode is not as likely to be corrupted as | |
157 | the allocation information. | |
158 | However, because of the great number of active inodes, | |
159 | a few of the inodes are usually corrupted. | |
160 | .PP | |
161 | The list of inodes in the file system | |
162 | is checked sequentially starting with inode 2 | |
163 | (inode 0 marks unused inodes; | |
164 | inode 1 is saved for future generations) | |
165 | and progressing through the last inode in the file system. | |
166 | The state of each inode is checked for | |
167 | inconsistencies involving format and type, | |
168 | link count, | |
169 | duplicate blocks, | |
170 | bad blocks, | |
171 | and inode size. | |
172 | .PP | |
173 | Each inode contains a mode word. | |
174 | This mode word describes the type and state of the inode. | |
175 | Inodes must be one of six types: | |
176 | regular inode, directory inode, symbolic link inode, | |
177 | special block inode, special character inode, or socket inode. | |
178 | Inodes may be found in one of three allocation states: | |
179 | unallocated, allocated, and neither unallocated nor allocated. | |
180 | This last state suggests an incorrectly formated inode. | |
181 | An inode can get in this state if | |
182 | bad data is written into the inode list. | |
183 | The only possible corrective action is for | |
184 | .I fsck | |
185 | is to clear the inode. | |
186 | .NH 2 | |
187 | Inode links | |
188 | .PP | |
189 | Each inode counts the | |
190 | total number of directory entries | |
191 | linked to the inode. | |
192 | .I Fsck | |
193 | verifies the link count of each inode | |
194 | by starting at the root of the file system, | |
195 | and descending through the directory structure. | |
196 | The actual link count for each inode | |
197 | is calculated during the descent. | |
198 | .PP | |
199 | If the stored link count is non-zero and the actual | |
200 | link count is zero, | |
201 | then no directory entry appears for the inode. | |
202 | If this happens, | |
203 | .I fsck | |
204 | will place the disconnected file in the | |
205 | .I lost+found | |
206 | directory. | |
207 | If the stored and actual link counts are non-zero and unequal, | |
208 | a directory entry may have been added or removed without the inode being | |
209 | updated. | |
210 | If this happens, | |
211 | .I fsck | |
212 | replaces the incorrect stored link count by the actual link count. | |
213 | .PP | |
214 | Each inode contains a list, | |
215 | or pointers to | |
216 | lists (indirect blocks), | |
217 | of all the blocks claimed by the inode. | |
218 | Since indirect blocks are owned by an inode, | |
219 | inconsistencies in indirect blocks directly | |
220 | affect the inode that owns it. | |
221 | .PP | |
222 | .I Fsck | |
223 | compares each block number claimed by an inode | |
224 | against a list of already allocated blocks. | |
225 | If another inode already claims a block number, | |
226 | then the block number is added to a list of | |
227 | .I "duplicate blocks" . | |
228 | Otherwise, the list of allocated blocks | |
229 | is updated to include the block number. | |
230 | .PP | |
231 | If there are any duplicate blocks, | |
232 | .I fsck | |
233 | will perform a partial second | |
234 | pass over the inode list | |
235 | to find the inode of the duplicated block. | |
236 | The second pass is needed, | |
237 | since without examining the files associated with | |
238 | these inodes for correct content, | |
239 | not enough information is available | |
240 | to determine which inode is corrupted and should be cleared. | |
241 | If this condition does arise | |
242 | (only hardware failure will cause it), | |
243 | then the inode with the earliest | |
244 | modify time is usually incorrect, | |
245 | and should be cleared. | |
246 | If this happens, | |
247 | .I fsck | |
248 | prompts the operator to clear both inodes. | |
249 | The operator must decide which one should be kept | |
250 | and which one should be cleared. | |
251 | .PP | |
252 | .I Fsck | |
253 | checks the range of each block number claimed by an inode. | |
254 | If the block number is | |
255 | lower than the first data block in the file system, | |
256 | or greater than the last data block, | |
257 | then the block number is a | |
258 | .I "bad block number" . | |
259 | Many bad blocks in an inode are usually caused by | |
260 | an indirect block that was not written to the file system, | |
261 | a condition which can only occur if there has been a hardware failure. | |
262 | If an inode contains bad block numbers, | |
263 | .I fsck | |
264 | prompts the operator to clear it. | |
265 | .NH 2 | |
266 | Inode data size | |
267 | .PP | |
268 | Each inode contains a count of the number of data blocks | |
269 | that it contains. | |
270 | The number of actual data blocks | |
271 | is the sum of the allocated data blocks | |
272 | and the indirect blocks. | |
273 | .I Fsck | |
274 | computes the actual number of data blocks | |
275 | and compares that block count against | |
276 | the actual number of blocks the inode claims. | |
277 | If an inode contains an incorrect count | |
278 | .I fsck | |
279 | prompts the operator to fix it. | |
280 | .PP | |
281 | Each inode contains a thirty-two bit size field. | |
282 | The size is the number of data bytes | |
283 | in the file associated with the inode. | |
284 | The consistency of the byte size field is roughly checked | |
285 | by computing from the size field the maximum number of blocks | |
286 | that should be associated with the inode, | |
287 | and comparing that expected block count against | |
288 | the actual number of blocks the inode claims. | |
289 | .NH 2 | |
290 | Checking the data associated with an inode | |
291 | .PP | |
292 | An inode can directly or indirectly | |
293 | reference three kinds of data blocks. | |
294 | All referenced blocks must be the same kind. | |
295 | The three types of data blocks are: | |
296 | plain data blocks, symbolic link data blocks, and directory data blocks. | |
297 | Plain data blocks | |
298 | contain the information stored in a file; | |
299 | symbolic link data blocks | |
300 | contain the path name stored in a link. | |
301 | Directory data blocks contain directory entries. | |
302 | .I Fsck | |
303 | can only check the validity of directory data blocks. | |
304 | .PP | |
305 | Each directory data block is checked for | |
306 | several types of inconsistencies. | |
307 | These inconsistencies include | |
308 | directory inode numbers pointing to unallocated inodes, | |
309 | directory inode numbers that are greater than | |
310 | the number of inodes in the file system, | |
311 | incorrect directory inode numbers for ``\fB.\fP'' and ``\fB..\fP'', | |
312 | and directories that are not attached to the file system. | |
313 | If the inode number in a directory data block | |
314 | references an unallocated inode, | |
315 | then | |
316 | .I fsck | |
317 | will remove that directory entry. | |
318 | Again, | |
319 | this condition can only arise when there has been a hardware failure. | |
320 | .PP | |
321 | If a directory entry inode number references | |
322 | outside the inode list, then | |
323 | .I fsck | |
324 | will remove that directory entry. | |
325 | This condition occurs if bad data is written into a directory data block. | |
326 | .PP | |
327 | The directory inode number entry for ``\fB.\fP'' | |
328 | must be the first entry in the directory data block. | |
329 | The inode number for ``\fB.\fP'' | |
330 | must reference itself; | |
331 | e.g., it must equal the inode number | |
332 | for the directory data block. | |
333 | The directory inode number entry | |
334 | for ``\fB..\fP'' must be | |
335 | the second entry in the directory data block. | |
336 | Its value must equal the inode number for the | |
337 | parent of the directory entry | |
338 | (or the inode number of the directory | |
339 | data block if the directory is the | |
340 | root directory). | |
341 | If the directory inode numbers are | |
342 | incorrect, | |
343 | .I fsck | |
344 | will replace them with the correct values. | |
145bc69d KM |
345 | If there are multiple hard links to a directory, |
346 | the first one encountered is considered the real parent | |
347 | to which ``\fB..\fP'' should point; | |
b7956604 | 348 | \fIfsck\fP recommends deletion for the subsequently discovered names. |
a38b2411 KM |
349 | .NH 2 |
350 | File system connectivity | |
351 | .PP | |
352 | .I Fsck | |
353 | checks the general connectivity of the file system. | |
354 | If directories are not linked into the file system, then | |
355 | .I fsck | |
356 | links the directory back into the file system in the | |
357 | .I lost+found | |
358 | directory. | |
359 | This condition only occurs when there has been a hardware failure. | |
6a1194d8 | 360 | .ds RH "References" |
a38b2411 KM |
361 | .SH |
362 | \s+2Acknowledgements\s0 | |
363 | .PP | |
364 | I thank Bill Joy, Sam Leffler, Robert Elz and Dennis Ritchie | |
365 | for their suggestions and help in implementing the new file system. | |
366 | Thanks also to Robert Henry for his editorial input to | |
367 | get this document together. | |
368 | Finally we thank our sponsors, | |
369 | the National Science Foundation under grant MCS80-05144, | |
370 | and the Defense Advance Research Projects Agency (DoD) under | |
371 | Arpa Order No. 4031 monitored by Naval Electronic System Command under | |
372 | Contract No. N00039-82-C-0235. (Kirk McKusick, July 1983) | |
373 | .PP | |
374 | I would like to thank Larry A. Wehr for advice that lead | |
375 | to the first version of | |
376 | .I fsck | |
377 | and Rick B. Brandt for adapting | |
378 | .I fsck | |
379 | to | |
380 | UNIX/TS. (T. Kowalski, July 1979) | |
381 | .sp 2 | |
382 | .SH | |
383 | \s+2References\s0 | |
384 | .LP | |
385 | .IP [Dolotta78] 20 | |
386 | Dolotta, T. A., and Olsson, S. B. eds., | |
6a1194d8 KM |
387 | .I "UNIX User's Manual, Edition 1.1\^" , |
388 | January 1978. | |
a38b2411 KM |
389 | .IP [Joy83] 20 |
390 | Joy, W., Cooper, E., Fabry, R., Leffler, S., McKusick, M., and Mosher, D. | |
6a1194d8 KM |
391 | 4.2BSD System Manual, |
392 | .I "University of California at Berkeley" , | |
393 | .I "Computer Systems Research Group Technical Report" | |
394 | #4, 1982. | |
395 | .IP [McKusick84] 20 | |
a38b2411 | 396 | McKusick, M., Joy, W., Leffler, S., and Fabry, R. |
6a1194d8 KM |
397 | A Fast File System for UNIX, |
398 | \fIACM Transactions on Computer Systems 2\fP, 3. | |
399 | pp. 181-197, August 1984. | |
a38b2411 KM |
400 | .IP [Ritchie78] 20 |
401 | Ritchie, D. M., and Thompson, K., | |
402 | The UNIX Time-Sharing System, | |
403 | .I "The Bell System Technical Journal" | |
404 | .B 57 , | |
405 | 6 (July-August 1978, Part 2), pp. 1905-29. | |
406 | .IP [Thompson78] 20 | |
407 | Thompson, K., | |
408 | UNIX Implementation, | |
409 | .I "The Bell System Technical Journal\^" | |
410 | .B 57 , | |
411 | 6 (July-August 1978, Part 2), pp. 1931-46. | |
412 | .ds RH Appendix A \- Fsck Error Conditions | |
413 | .bp |