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