pass5.c revision 143235
1/* 2 * Copyright (c) 1980, 1986, 1993 3 * The Regents of the University of California. All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 4. Neither the name of the University nor the names of its contributors 14 * may be used to endorse or promote products derived from this software 15 * without specific prior written permission. 16 * 17 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 27 * SUCH DAMAGE. 28 */ 29 30#if 0 31#ifndef lint 32static const char sccsid[] = "@(#)pass5.c 8.9 (Berkeley) 4/28/95"; 33#endif /* not lint */ 34#endif 35#include <sys/cdefs.h> 36__FBSDID("$FreeBSD: head/sbin/fsck_ffs/pass5.c 143235 2005-03-07 08:42:49Z delphij $"); 37 38#include <sys/param.h> 39#include <sys/sysctl.h> 40 41#include <ufs/ufs/dinode.h> 42#include <ufs/ffs/fs.h> 43 44#include <err.h> 45#include <inttypes.h> 46#include <limits.h> 47#include <string.h> 48 49#include "fsck.h" 50 51static void check_maps(u_char *, u_char *, int, int, const char *, int *, int, int); 52 53void 54pass5(void) 55{ 56 int c, i, j, blk, frags, basesize, mapsize; 57 int inomapsize, blkmapsize; 58 struct fs *fs = &sblock; 59 struct cg *cg = &cgrp; 60 ufs2_daddr_t d, dbase, dmax; 61 int excessdirs, rewritecg = 0; 62 struct csum *cs; 63 struct csum_total cstotal; 64 struct inodesc idesc[3]; 65 char buf[MAXBSIZE]; 66 struct cg *newcg = (struct cg *)buf; 67 68 inoinfo(WINO)->ino_state = USTATE; 69 memset(newcg, 0, (size_t)fs->fs_cgsize); 70 newcg->cg_niblk = fs->fs_ipg; 71 if (cvtlevel >= 3) { 72 if (fs->fs_maxcontig < 2 && fs->fs_contigsumsize > 0) { 73 if (preen) 74 pwarn("DELETING CLUSTERING MAPS\n"); 75 if (preen || reply("DELETE CLUSTERING MAPS")) { 76 fs->fs_contigsumsize = 0; 77 rewritecg = 1; 78 sbdirty(); 79 } 80 } 81 if (fs->fs_maxcontig > 1) { 82 const char *doit = 0; 83 84 if (fs->fs_contigsumsize < 1) { 85 doit = "CREAT"; 86 } else if (fs->fs_contigsumsize < fs->fs_maxcontig && 87 fs->fs_contigsumsize < FS_MAXCONTIG) { 88 doit = "EXPAND"; 89 } 90 if (doit) { 91 i = fs->fs_contigsumsize; 92 fs->fs_contigsumsize = 93 MIN(fs->fs_maxcontig, FS_MAXCONTIG); 94 if (CGSIZE(fs) > (u_int)fs->fs_bsize) { 95 pwarn("CANNOT %s CLUSTER MAPS\n", doit); 96 fs->fs_contigsumsize = i; 97 } else if (preen || 98 reply("CREATE CLUSTER MAPS")) { 99 if (preen) 100 pwarn("%sING CLUSTER MAPS\n", 101 doit); 102 fs->fs_cgsize = 103 fragroundup(fs, CGSIZE(fs)); 104 rewritecg = 1; 105 sbdirty(); 106 } 107 } 108 } 109 } 110 basesize = &newcg->cg_space[0] - (u_char *)(&newcg->cg_firstfield); 111 if (sblock.fs_magic == FS_UFS2_MAGIC) { 112 newcg->cg_iusedoff = basesize; 113 } else { 114 /* 115 * We reserve the space for the old rotation summary 116 * tables for the benefit of old kernels, but do not 117 * maintain them in modern kernels. In time, they can 118 * go away. 119 */ 120 newcg->cg_old_btotoff = basesize; 121 newcg->cg_old_boff = newcg->cg_old_btotoff + 122 fs->fs_old_cpg * sizeof(int32_t); 123 newcg->cg_iusedoff = newcg->cg_old_boff + 124 fs->fs_old_cpg * fs->fs_old_nrpos * sizeof(u_int16_t); 125 memset(&newcg->cg_space[0], 0, newcg->cg_iusedoff - basesize); 126 } 127 inomapsize = howmany(fs->fs_ipg, CHAR_BIT); 128 newcg->cg_freeoff = newcg->cg_iusedoff + inomapsize; 129 blkmapsize = howmany(fs->fs_fpg, CHAR_BIT); 130 newcg->cg_nextfreeoff = newcg->cg_freeoff + blkmapsize; 131 if (fs->fs_contigsumsize > 0) { 132 newcg->cg_clustersumoff = newcg->cg_nextfreeoff - 133 sizeof(u_int32_t); 134 newcg->cg_clustersumoff = 135 roundup(newcg->cg_clustersumoff, sizeof(u_int32_t)); 136 newcg->cg_clusteroff = newcg->cg_clustersumoff + 137 (fs->fs_contigsumsize + 1) * sizeof(u_int32_t); 138 newcg->cg_nextfreeoff = newcg->cg_clusteroff + 139 howmany(fragstoblks(fs, fs->fs_fpg), CHAR_BIT); 140 } 141 newcg->cg_magic = CG_MAGIC; 142 mapsize = newcg->cg_nextfreeoff - newcg->cg_iusedoff; 143 memset(&idesc[0], 0, sizeof idesc); 144 for (i = 0; i < 3; i++) 145 idesc[i].id_type = ADDR; 146 memset(&cstotal, 0, sizeof(struct csum_total)); 147 dmax = blknum(fs, fs->fs_size + fs->fs_frag - 1); 148 for (d = fs->fs_size; d < dmax; d++) 149 setbmap(d); 150 for (c = 0; c < fs->fs_ncg; c++) { 151 if (got_siginfo) { 152 printf("%s: phase 5: cyl group %d of %d (%d%%)\n", 153 cdevname, c, sblock.fs_ncg, 154 c * 100 / sblock.fs_ncg); 155 got_siginfo = 0; 156 } 157 if (got_sigalarm) { 158 setproctitle("%s p5 %d%%", cdevname, 159 c * 100 / sblock.fs_ncg); 160 got_sigalarm = 0; 161 } 162 getblk(&cgblk, cgtod(fs, c), fs->fs_cgsize); 163 if (!cg_chkmagic(cg)) 164 pfatal("CG %d: BAD MAGIC NUMBER\n", c); 165 newcg->cg_time = cg->cg_time; 166 newcg->cg_old_time = cg->cg_old_time; 167 newcg->cg_cgx = c; 168 dbase = cgbase(fs, c); 169 dmax = dbase + fs->fs_fpg; 170 if (dmax > fs->fs_size) 171 dmax = fs->fs_size; 172 newcg->cg_ndblk = dmax - dbase; 173 if (fs->fs_magic == FS_UFS1_MAGIC) { 174 if (c == fs->fs_ncg - 1) 175 newcg->cg_old_ncyl = howmany(newcg->cg_ndblk, 176 fs->fs_fpg / fs->fs_old_cpg); 177 else 178 newcg->cg_old_ncyl = fs->fs_old_cpg; 179 newcg->cg_old_niblk = fs->fs_ipg; 180 newcg->cg_niblk = 0; 181 } 182 if (fs->fs_contigsumsize > 0) 183 newcg->cg_nclusterblks = newcg->cg_ndblk / fs->fs_frag; 184 newcg->cg_cs.cs_ndir = 0; 185 newcg->cg_cs.cs_nffree = 0; 186 newcg->cg_cs.cs_nbfree = 0; 187 newcg->cg_cs.cs_nifree = fs->fs_ipg; 188 if (cg->cg_rotor >= 0 && cg->cg_rotor < newcg->cg_ndblk) 189 newcg->cg_rotor = cg->cg_rotor; 190 else 191 newcg->cg_rotor = 0; 192 if (cg->cg_frotor >= 0 && cg->cg_frotor < newcg->cg_ndblk) 193 newcg->cg_frotor = cg->cg_frotor; 194 else 195 newcg->cg_frotor = 0; 196 if (cg->cg_irotor >= 0 && cg->cg_irotor < fs->fs_ipg) 197 newcg->cg_irotor = cg->cg_irotor; 198 else 199 newcg->cg_irotor = 0; 200 if (fs->fs_magic == FS_UFS1_MAGIC) { 201 newcg->cg_initediblk = 0; 202 } else { 203 if ((unsigned)cg->cg_initediblk > fs->fs_ipg) 204 newcg->cg_initediblk = fs->fs_ipg; 205 else 206 newcg->cg_initediblk = cg->cg_initediblk; 207 } 208 memset(&newcg->cg_frsum[0], 0, sizeof newcg->cg_frsum); 209 memset(cg_inosused(newcg), 0, (size_t)(mapsize)); 210 j = fs->fs_ipg * c; 211 for (i = 0; i < inostathead[c].il_numalloced; j++, i++) { 212 switch (inoinfo(j)->ino_state) { 213 214 case USTATE: 215 break; 216 217 case DSTATE: 218 case DCLEAR: 219 case DFOUND: 220 case DZLINK: 221 newcg->cg_cs.cs_ndir++; 222 /* FALLTHROUGH */ 223 224 case FSTATE: 225 case FCLEAR: 226 case FZLINK: 227 newcg->cg_cs.cs_nifree--; 228 setbit(cg_inosused(newcg), i); 229 break; 230 231 default: 232 if (j < (int)ROOTINO) 233 break; 234 errx(EEXIT, "BAD STATE %d FOR INODE I=%d", 235 inoinfo(j)->ino_state, j); 236 } 237 } 238 if (c == 0) 239 for (i = 0; i < (int)ROOTINO; i++) { 240 setbit(cg_inosused(newcg), i); 241 newcg->cg_cs.cs_nifree--; 242 } 243 for (i = 0, d = dbase; 244 d < dmax; 245 d += fs->fs_frag, i += fs->fs_frag) { 246 frags = 0; 247 for (j = 0; j < fs->fs_frag; j++) { 248 if (testbmap(d + j)) 249 continue; 250 setbit(cg_blksfree(newcg), i + j); 251 frags++; 252 } 253 if (frags == fs->fs_frag) { 254 newcg->cg_cs.cs_nbfree++; 255 if (fs->fs_contigsumsize > 0) 256 setbit(cg_clustersfree(newcg), 257 i / fs->fs_frag); 258 } else if (frags > 0) { 259 newcg->cg_cs.cs_nffree += frags; 260 blk = blkmap(fs, cg_blksfree(newcg), i); 261 ffs_fragacct(fs, blk, newcg->cg_frsum, 1); 262 } 263 } 264 if (fs->fs_contigsumsize > 0) { 265 int32_t *sump = cg_clustersum(newcg); 266 u_char *mapp = cg_clustersfree(newcg); 267 int map = *mapp++; 268 int bit = 1; 269 int run = 0; 270 271 for (i = 0; i < newcg->cg_nclusterblks; i++) { 272 if ((map & bit) != 0) { 273 run++; 274 } else if (run != 0) { 275 if (run > fs->fs_contigsumsize) 276 run = fs->fs_contigsumsize; 277 sump[run]++; 278 run = 0; 279 } 280 if ((i & (CHAR_BIT - 1)) != (CHAR_BIT - 1)) { 281 bit <<= 1; 282 } else { 283 map = *mapp++; 284 bit = 1; 285 } 286 } 287 if (run != 0) { 288 if (run > fs->fs_contigsumsize) 289 run = fs->fs_contigsumsize; 290 sump[run]++; 291 } 292 } 293 cstotal.cs_nffree += newcg->cg_cs.cs_nffree; 294 cstotal.cs_nbfree += newcg->cg_cs.cs_nbfree; 295 cstotal.cs_nifree += newcg->cg_cs.cs_nifree; 296 cstotal.cs_ndir += newcg->cg_cs.cs_ndir; 297 cs = &fs->fs_cs(fs, c); 298 if (cursnapshot == 0 && 299 memcmp(&newcg->cg_cs, cs, sizeof *cs) != 0 && 300 dofix(&idesc[0], "FREE BLK COUNT(S) WRONG IN SUPERBLK")) { 301 memmove(cs, &newcg->cg_cs, sizeof *cs); 302 sbdirty(); 303 } 304 if (rewritecg) { 305 memmove(cg, newcg, (size_t)fs->fs_cgsize); 306 cgdirty(); 307 continue; 308 } 309 if (cursnapshot == 0 && 310 memcmp(newcg, cg, basesize) != 0 && 311 dofix(&idesc[2], "SUMMARY INFORMATION BAD")) { 312 memmove(cg, newcg, (size_t)basesize); 313 cgdirty(); 314 } 315 if (bkgrdflag != 0 || usedsoftdep || debug) { 316 excessdirs = cg->cg_cs.cs_ndir - newcg->cg_cs.cs_ndir; 317 if (excessdirs < 0) { 318 pfatal("LOST %d DIRECTORIES\n", -excessdirs); 319 excessdirs = 0; 320 } 321 if (excessdirs > 0) 322 check_maps(cg_inosused(newcg), cg_inosused(cg), 323 inomapsize, cg->cg_cgx * fs->fs_ipg, "DIR", 324 freedirs, 0, excessdirs); 325 check_maps(cg_inosused(newcg), cg_inosused(cg), 326 inomapsize, cg->cg_cgx * fs->fs_ipg, "FILE", 327 freefiles, excessdirs, fs->fs_ipg); 328 check_maps(cg_blksfree(cg), cg_blksfree(newcg), 329 blkmapsize, cg->cg_cgx * fs->fs_fpg, "FRAG", 330 freeblks, 0, fs->fs_fpg); 331 } 332 if (cursnapshot == 0 && 333 memcmp(cg_inosused(newcg), cg_inosused(cg), mapsize) != 0 && 334 dofix(&idesc[1], "BLK(S) MISSING IN BIT MAPS")) { 335 memmove(cg_inosused(cg), cg_inosused(newcg), 336 (size_t)mapsize); 337 cgdirty(); 338 } 339 } 340 if (cursnapshot == 0 && 341 memcmp(&cstotal, &fs->fs_cstotal, sizeof cstotal) != 0 342 && dofix(&idesc[0], "SUMMARY BLK COUNT(S) WRONG IN SUPERBLK")) { 343 memmove(&fs->fs_cstotal, &cstotal, sizeof cstotal); 344 fs->fs_ronly = 0; 345 fs->fs_fmod = 0; 346 sbdirty(); 347 } 348 349 /* 350 * When doing background fsck on a snapshot, figure out whether 351 * the superblock summary is inaccurate and correct it when 352 * necessary. 353 */ 354 if (cursnapshot != 0) { 355 cmd.size = 1; 356 357 cmd.value = cstotal.cs_ndir - fs->fs_cstotal.cs_ndir; 358 if (cmd.value != 0) { 359 if (debug) 360 printf("adjndir by %+" PRIi64 "\n", cmd.value); 361 if (bkgrdsumadj == 0 || sysctl(adjndir, MIBSIZE, 0, 0, 362 &cmd, sizeof cmd) == -1) 363 rwerror("ADJUST NUMBER OF DIRECTORIES", cmd.value); 364 } 365 366 cmd.value = cstotal.cs_nbfree - fs->fs_cstotal.cs_nbfree; 367 if (cmd.value != 0) { 368 if (debug) 369 printf("adjnbfree by %+" PRIi64 "\n", cmd.value); 370 if (bkgrdsumadj == 0 || sysctl(adjnbfree, MIBSIZE, 0, 0, 371 &cmd, sizeof cmd) == -1) 372 rwerror("ADJUST NUMBER OF FREE BLOCKS", cmd.value); 373 } 374 375 cmd.value = cstotal.cs_nifree - fs->fs_cstotal.cs_nifree; 376 if (cmd.value != 0) { 377 if (debug) 378 printf("adjnifree by %+" PRIi64 "\n", cmd.value); 379 if (bkgrdsumadj == 0 || sysctl(adjnifree, MIBSIZE, 0, 0, 380 &cmd, sizeof cmd) == -1) 381 rwerror("ADJUST NUMBER OF FREE INODES", cmd.value); 382 } 383 384 cmd.value = cstotal.cs_nffree - fs->fs_cstotal.cs_nffree; 385 if (cmd.value != 0) { 386 if (debug) 387 printf("adjnffree by %+" PRIi64 "\n", cmd.value); 388 if (bkgrdsumadj == 0 || sysctl(adjnffree, MIBSIZE, 0, 0, 389 &cmd, sizeof cmd) == -1) 390 rwerror("ADJUST NUMBER OF FREE FRAGS", cmd.value); 391 } 392 393 cmd.value = cstotal.cs_numclusters - fs->fs_cstotal.cs_numclusters; 394 if (cmd.value != 0) { 395 if (debug) 396 printf("adjnumclusters by %+" PRIi64 "\n", cmd.value); 397 if (bkgrdsumadj == 0 || sysctl(adjnumclusters, MIBSIZE, 0, 0, 398 &cmd, sizeof cmd) == -1) 399 rwerror("ADJUST NUMBER OF FREE CLUSTERS", cmd.value); 400 } 401 } 402} 403 404static void 405check_maps( 406 u_char *map1, /* map of claimed allocations */ 407 u_char *map2, /* map of determined allocations */ 408 int mapsize, /* size of above two maps */ 409 int startvalue, /* resource value for first element in map */ 410 const char *name, /* name of resource found in maps */ 411 int *opcode, /* sysctl opcode to free resource */ 412 int skip, /* number of entries to skip before starting to free */ 413 int limit) /* limit on number of entries to free */ 414{ 415# define BUFSIZE 16 416 char buf[BUFSIZE]; 417 long i, j, k, l, m, n, size; 418 int astart, aend, ustart, uend; 419 void (*msg)(const char *fmt, ...); 420 421 if (bkgrdflag) 422 msg = pfatal; 423 else 424 msg = pwarn; 425 astart = ustart = aend = uend = -1; 426 for (i = 0; i < mapsize; i++) { 427 j = *map1++; 428 k = *map2++; 429 if (j == k) 430 continue; 431 for (m = 0, l = 1; m < CHAR_BIT; m++, l <<= 1) { 432 if ((j & l) == (k & l)) 433 continue; 434 n = startvalue + i * CHAR_BIT + m; 435 if ((j & l) != 0) { 436 if (astart == -1) { 437 astart = aend = n; 438 continue; 439 } 440 if (aend + 1 == n) { 441 aend = n; 442 continue; 443 } 444 if (astart == aend) 445 (*msg)("ALLOCATED %s %d MARKED FREE\n", 446 name, astart); 447 else 448 (*msg)("%s %sS %d-%d MARKED FREE\n", 449 "ALLOCATED", name, astart, aend); 450 astart = aend = n; 451 } else { 452 if (ustart == -1) { 453 ustart = uend = n; 454 continue; 455 } 456 if (uend + 1 == n) { 457 uend = n; 458 continue; 459 } 460 size = uend - ustart + 1; 461 if (size <= skip) { 462 skip -= size; 463 ustart = uend = n; 464 continue; 465 } 466 if (skip > 0) { 467 ustart += skip; 468 size -= skip; 469 skip = 0; 470 } 471 if (size > limit) 472 size = limit; 473 if (debug && size == 1) 474 pwarn("%s %s %d MARKED USED\n", 475 "UNALLOCATED", name, ustart); 476 else if (debug) 477 pwarn("%s %sS %d-%ld MARKED USED\n", 478 "UNALLOCATED", name, ustart, 479 ustart + size - 1); 480 if (bkgrdflag != 0) { 481 cmd.value = ustart; 482 cmd.size = size; 483 if (sysctl(opcode, MIBSIZE, 0, 0, 484 &cmd, sizeof cmd) == -1) { 485 snprintf(buf, BUFSIZE, 486 "FREE %s", name); 487 rwerror(buf, cmd.value); 488 } 489 } 490 limit -= size; 491 if (limit <= 0) 492 return; 493 ustart = uend = n; 494 } 495 } 496 } 497 if (astart != -1) { 498 if (astart == aend) 499 (*msg)("ALLOCATED %s %d MARKED FREE\n", name, astart); 500 else 501 (*msg)("ALLOCATED %sS %d-%d MARKED FREE\n", 502 name, astart, aend); 503 } 504 if (ustart != -1) { 505 size = uend - ustart + 1; 506 if (size <= skip) 507 return; 508 if (skip > 0) { 509 ustart += skip; 510 size -= skip; 511 } 512 if (size > limit) 513 size = limit; 514 if (debug) { 515 if (size == 1) 516 pwarn("UNALLOCATED %s %d MARKED USED\n", 517 name, ustart); 518 else 519 pwarn("UNALLOCATED %sS %d-%ld MARKED USED\n", 520 name, ustart, ustart + size - 1); 521 } 522 if (bkgrdflag != 0) { 523 cmd.value = ustart; 524 cmd.size = size; 525 if (sysctl(opcode, MIBSIZE, 0, 0, &cmd, 526 sizeof cmd) == -1) { 527 snprintf(buf, BUFSIZE, "FREE %s", name); 528 rwerror(buf, cmd.value); 529 } 530 } 531 } 532} 533