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