sbin/fsck/SMM.doc/3.t

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