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