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