pass5.c revision 74556
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 74556 2001-03-21 09:48:03Z mckusick $"; 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 __P((u_char *, u_char *, int, int, char *, int *, 54 int, int)); 55 56void 57pass5() 58{ 59 int c, blk, frags, basesize, sumsize, mapsize, savednrpos = 0; 60 int inomapsize, blkmapsize; 61 struct fs *fs = &sblock; 62 struct cg *cg = &cgrp; 63 ufs_daddr_t dbase, dmax, d; 64 int i, j, excessdirs; 65 struct csum *cs; 66 struct csum cstotal; 67 struct inodesc idesc[3]; 68 char buf[MAXBSIZE]; 69 register struct cg *newcg = (struct cg *)buf; 70 struct ocg *ocg = (struct ocg *)buf; 71 72 inoinfo(WINO)->ino_state = USTATE; 73 memset(newcg, 0, (size_t)fs->fs_cgsize); 74 newcg->cg_niblk = fs->fs_ipg; 75 if (cvtlevel >= 3) { 76 if (fs->fs_maxcontig < 2 && fs->fs_contigsumsize > 0) { 77 if (preen) 78 pwarn("DELETING CLUSTERING MAPS\n"); 79 if (preen || reply("DELETE CLUSTERING MAPS")) { 80 fs->fs_contigsumsize = 0; 81 doinglevel1 = 1; 82 sbdirty(); 83 } 84 } 85 if (fs->fs_maxcontig > 1) { 86 char *doit = 0; 87 88 if (fs->fs_contigsumsize < 1) { 89 doit = "CREAT"; 90 } else if (fs->fs_contigsumsize < fs->fs_maxcontig && 91 fs->fs_contigsumsize < FS_MAXCONTIG) { 92 doit = "EXPAND"; 93 } 94 if (doit) { 95 i = fs->fs_contigsumsize; 96 fs->fs_contigsumsize = 97 MIN(fs->fs_maxcontig, FS_MAXCONTIG); 98 if (CGSIZE(fs) > (u_int)fs->fs_bsize) { 99 pwarn("CANNOT %s CLUSTER MAPS\n", doit); 100 fs->fs_contigsumsize = i; 101 } else if (preen || 102 reply("CREATE CLUSTER MAPS")) { 103 if (preen) 104 pwarn("%sING CLUSTER MAPS\n", 105 doit); 106 fs->fs_cgsize = 107 fragroundup(fs, CGSIZE(fs)); 108 doinglevel1 = 1; 109 sbdirty(); 110 } 111 } 112 } 113 } 114 switch ((int)fs->fs_postblformat) { 115 116 case FS_42POSTBLFMT: 117 basesize = (char *)(&ocg->cg_btot[0]) - 118 (char *)(&ocg->cg_firstfield); 119 sumsize = &ocg->cg_iused[0] - (u_int8_t *)(&ocg->cg_btot[0]); 120 mapsize = &ocg->cg_free[howmany(fs->fs_fpg, NBBY)] - 121 (u_char *)&ocg->cg_iused[0]; 122 blkmapsize = howmany(fs->fs_fpg, NBBY); 123 inomapsize = &ocg->cg_free[0] - (u_char *)&ocg->cg_iused[0]; 124 ocg->cg_magic = CG_MAGIC; 125 savednrpos = fs->fs_nrpos; 126 fs->fs_nrpos = 8; 127 break; 128 129 case FS_DYNAMICPOSTBLFMT: 130 newcg->cg_btotoff = 131 &newcg->cg_space[0] - (u_char *)(&newcg->cg_firstfield); 132 newcg->cg_boff = 133 newcg->cg_btotoff + fs->fs_cpg * sizeof(int32_t); 134 newcg->cg_iusedoff = newcg->cg_boff + 135 fs->fs_cpg * fs->fs_nrpos * sizeof(u_int16_t); 136 newcg->cg_freeoff = 137 newcg->cg_iusedoff + howmany(fs->fs_ipg, NBBY); 138 inomapsize = newcg->cg_freeoff - newcg->cg_iusedoff; 139 newcg->cg_nextfreeoff = newcg->cg_freeoff + 140 howmany(fs->fs_cpg * fs->fs_spc / NSPF(fs), NBBY); 141 blkmapsize = newcg->cg_nextfreeoff - newcg->cg_freeoff; 142 if (fs->fs_contigsumsize > 0) { 143 newcg->cg_clustersumoff = newcg->cg_nextfreeoff - 144 sizeof(u_int32_t); 145 newcg->cg_clustersumoff = 146 roundup(newcg->cg_clustersumoff, sizeof(u_int32_t)); 147 newcg->cg_clusteroff = newcg->cg_clustersumoff + 148 (fs->fs_contigsumsize + 1) * sizeof(u_int32_t); 149 newcg->cg_nextfreeoff = newcg->cg_clusteroff + 150 howmany(fs->fs_cpg * fs->fs_spc / NSPB(fs), NBBY); 151 } 152 newcg->cg_magic = CG_MAGIC; 153 basesize = &newcg->cg_space[0] - 154 (u_char *)(&newcg->cg_firstfield); 155 sumsize = newcg->cg_iusedoff - newcg->cg_btotoff; 156 mapsize = newcg->cg_nextfreeoff - newcg->cg_iusedoff; 157 break; 158 159 default: 160 inomapsize = blkmapsize = sumsize = 0; /* keep lint happy */ 161 errx(EEXIT, "UNKNOWN ROTATIONAL TABLE FORMAT %d", 162 fs->fs_postblformat); 163 } 164 memset(&idesc[0], 0, sizeof idesc); 165 for (i = 0; i < 3; i++) { 166 idesc[i].id_type = ADDR; 167 if (doinglevel2) 168 idesc[i].id_fix = FIX; 169 } 170 memset(&cstotal, 0, sizeof(struct csum)); 171 j = blknum(fs, fs->fs_size + fs->fs_frag - 1); 172 for (i = fs->fs_size; i < j; i++) 173 setbmap(i); 174 for (c = 0; c < fs->fs_ncg; c++) { 175 if (got_siginfo) { 176 printf("%s: phase 5: cyl group %d of %d (%d%%)\n", 177 cdevname, c, sblock.fs_ncg, 178 c * 100 / sblock.fs_ncg); 179 got_siginfo = 0; 180 } 181 getblk(&cgblk, cgtod(fs, c), fs->fs_cgsize); 182 if (!cg_chkmagic(cg)) 183 pfatal("CG %d: BAD MAGIC NUMBER\n", c); 184 dbase = cgbase(fs, c); 185 dmax = dbase + fs->fs_fpg; 186 if (dmax > fs->fs_size) 187 dmax = fs->fs_size; 188 newcg->cg_time = cg->cg_time; 189 newcg->cg_cgx = c; 190 if (c == fs->fs_ncg - 1) 191 newcg->cg_ncyl = fs->fs_ncyl % fs->fs_cpg; 192 else 193 newcg->cg_ncyl = fs->fs_cpg; 194 newcg->cg_ndblk = dmax - dbase; 195 if (fs->fs_contigsumsize > 0) 196 newcg->cg_nclusterblks = newcg->cg_ndblk / fs->fs_frag; 197 newcg->cg_cs.cs_ndir = 0; 198 newcg->cg_cs.cs_nffree = 0; 199 newcg->cg_cs.cs_nbfree = 0; 200 newcg->cg_cs.cs_nifree = fs->fs_ipg; 201 if (cg->cg_rotor < newcg->cg_ndblk) 202 newcg->cg_rotor = cg->cg_rotor; 203 else 204 newcg->cg_rotor = 0; 205 if (cg->cg_frotor < newcg->cg_ndblk) 206 newcg->cg_frotor = cg->cg_frotor; 207 else 208 newcg->cg_frotor = 0; 209 if (cg->cg_irotor < newcg->cg_niblk) 210 newcg->cg_irotor = cg->cg_irotor; 211 else 212 newcg->cg_irotor = 0; 213 memset(&newcg->cg_frsum[0], 0, sizeof newcg->cg_frsum); 214 memset(&cg_blktot(newcg)[0], 0, 215 (size_t)(sumsize + mapsize)); 216 if (fs->fs_postblformat == FS_42POSTBLFMT) 217 ocg->cg_magic = CG_MAGIC; 218 j = fs->fs_ipg * c; 219 for (i = 0; i < inostathead[c].il_numalloced; j++, i++) { 220 switch (inoinfo(j)->ino_state) { 221 222 case USTATE: 223 break; 224 225 case DSTATE: 226 case DCLEAR: 227 case DFOUND: 228 newcg->cg_cs.cs_ndir++; 229 /* fall through */ 230 231 case FSTATE: 232 case FCLEAR: 233 newcg->cg_cs.cs_nifree--; 234 setbit(cg_inosused(newcg), i); 235 break; 236 237 default: 238 if (j < (int)ROOTINO) 239 break; 240 errx(EEXIT, "BAD STATE %d FOR INODE I=%ld", 241 inoinfo(j)->ino_state, j); 242 } 243 } 244 if (c == 0) 245 for (i = 0; i < (int)ROOTINO; i++) { 246 setbit(cg_inosused(newcg), i); 247 newcg->cg_cs.cs_nifree--; 248 } 249 for (i = 0, d = dbase; 250 d < dmax; 251 d += fs->fs_frag, i += fs->fs_frag) { 252 frags = 0; 253 for (j = 0; j < fs->fs_frag; j++) { 254 if (testbmap(d + j)) 255 continue; 256 setbit(cg_blksfree(newcg), i + j); 257 frags++; 258 } 259 if (frags == fs->fs_frag) { 260 newcg->cg_cs.cs_nbfree++; 261 j = cbtocylno(fs, i); 262 cg_blktot(newcg)[j]++; 263 cg_blks(fs, newcg, j)[cbtorpos(fs, i)]++; 264 if (fs->fs_contigsumsize > 0) 265 setbit(cg_clustersfree(newcg), 266 i / fs->fs_frag); 267 } else if (frags > 0) { 268 newcg->cg_cs.cs_nffree += frags; 269 blk = blkmap(fs, cg_blksfree(newcg), i); 270 ffs_fragacct(fs, blk, newcg->cg_frsum, 1); 271 } 272 } 273 if (fs->fs_contigsumsize > 0) { 274 int32_t *sump = cg_clustersum(newcg); 275 u_char *mapp = cg_clustersfree(newcg); 276 int map = *mapp++; 277 int bit = 1; 278 int run = 0; 279 280 for (i = 0; i < newcg->cg_nclusterblks; i++) { 281 if ((map & bit) != 0) { 282 run++; 283 } else if (run != 0) { 284 if (run > fs->fs_contigsumsize) 285 run = fs->fs_contigsumsize; 286 sump[run]++; 287 run = 0; 288 } 289 if ((i & (NBBY - 1)) != (NBBY - 1)) { 290 bit <<= 1; 291 } else { 292 map = *mapp++; 293 bit = 1; 294 } 295 } 296 if (run != 0) { 297 if (run > fs->fs_contigsumsize) 298 run = fs->fs_contigsumsize; 299 sump[run]++; 300 } 301 } 302 cstotal.cs_nffree += newcg->cg_cs.cs_nffree; 303 cstotal.cs_nbfree += newcg->cg_cs.cs_nbfree; 304 cstotal.cs_nifree += newcg->cg_cs.cs_nifree; 305 cstotal.cs_ndir += newcg->cg_cs.cs_ndir; 306 cs = &fs->fs_cs(fs, c); 307 if (cursnapshot == 0 && 308 memcmp(&newcg->cg_cs, cs, sizeof *cs) != 0 && 309 dofix(&idesc[0], "FREE BLK COUNT(S) WRONG IN SUPERBLK")) { 310 memmove(cs, &newcg->cg_cs, sizeof *cs); 311 sbdirty(); 312 } 313 if (doinglevel1) { 314 memmove(cg, newcg, (size_t)fs->fs_cgsize); 315 cgdirty(); 316 continue; 317 } 318 if (cursnapshot == 0 && 319 (memcmp(newcg, cg, basesize) != 0 || 320 memcmp(&cg_blktot(newcg)[0], 321 &cg_blktot(cg)[0], sumsize) != 0) && 322 dofix(&idesc[2], "SUMMARY INFORMATION BAD")) { 323 memmove(cg, newcg, (size_t)basesize); 324 memmove(&cg_blktot(cg)[0], 325 &cg_blktot(newcg)[0], (size_t)sumsize); 326 cgdirty(); 327 } 328 if (bkgrdflag != 0 || usedsoftdep || debug) { 329 excessdirs = cg->cg_cs.cs_ndir - newcg->cg_cs.cs_ndir; 330 if (excessdirs < 0) { 331 pfatal("LOST %d DIRECTORIES\n", -excessdirs); 332 excessdirs = 0; 333 } 334 if (excessdirs > 0) 335 check_maps(cg_inosused(newcg), cg_inosused(cg), 336 inomapsize, cg->cg_cgx * fs->fs_ipg, "DIR", 337 freedirs, 0, excessdirs); 338 check_maps(cg_inosused(newcg), cg_inosused(cg), 339 inomapsize, cg->cg_cgx * fs->fs_ipg, "FILE", 340 freefiles, excessdirs, fs->fs_ipg); 341 check_maps(cg_blksfree(cg), cg_blksfree(newcg), 342 blkmapsize, cg->cg_cgx * fs->fs_fpg, "FRAG", 343 freeblks, 0, fs->fs_fpg); 344 } 345 if (cursnapshot == 0 && 346 memcmp(cg_inosused(newcg), cg_inosused(cg), mapsize) != 0 && 347 dofix(&idesc[1], "BLK(S) MISSING IN BIT MAPS")) { 348 memmove(cg_inosused(cg), cg_inosused(newcg), 349 (size_t)mapsize); 350 cgdirty(); 351 } 352 } 353 if (fs->fs_postblformat == FS_42POSTBLFMT) 354 fs->fs_nrpos = savednrpos; 355 if (cursnapshot == 0 && 356 memcmp(&cstotal, &fs->fs_cstotal, sizeof *cs) != 0 357 && dofix(&idesc[0], "FREE BLK COUNT(S) WRONG IN SUPERBLK")) { 358 memmove(&fs->fs_cstotal, &cstotal, sizeof *cs); 359 fs->fs_ronly = 0; 360 fs->fs_fmod = 0; 361 sbdirty(); 362 } 363} 364 365static void 366check_maps(map1, map2, mapsize, startvalue, name, opcode, skip, limit) 367 u_char *map1; /* map of claimed allocations */ 368 u_char *map2; /* map of determined allocations */ 369 int mapsize; /* size of above two maps */ 370 int startvalue; /* resource value for first element in map */ 371 char *name; /* name of resource found in maps */ 372 int *opcode; /* sysctl opcode to free resource */ 373 int skip; /* number of entries to skip before starting to free */ 374 int limit; /* limit on number of entries to free */ 375{ 376# define BUFSIZE 16 377 char buf[BUFSIZE]; 378 long i, j, k, l, m, n, size; 379 int astart, aend, ustart, uend; 380 381 astart = ustart = aend = uend = -1; 382 for (i = 0; i < mapsize; i++) { 383 j = *map1++; 384 k = *map2++; 385 if (j == k) 386 continue; 387 for (m = 0, l = 1; m < NBBY; m++, l <<= 1) { 388 if ((j & l) == (k & l)) 389 continue; 390 n = startvalue + i * NBBY + m; 391 if ((j & l) != 0) { 392 if (astart == -1) { 393 astart = aend = n; 394 continue; 395 } 396 if (aend + 1 == n) { 397 aend = n; 398 continue; 399 } 400 if (astart == aend) 401 pfatal("ALLOCATED %s %d MARKED FREE\n", 402 name, astart); 403 else 404 pfatal("%s %sS %d-%d MARKED FREE\n", 405 "ALLOCATED", name, astart, aend); 406 astart = aend = n; 407 } else { 408 if (ustart == -1) { 409 ustart = uend = n; 410 continue; 411 } 412 if (uend + 1 == n) { 413 uend = n; 414 continue; 415 } 416 size = uend - ustart + 1; 417 if (size <= skip) { 418 skip -= size; 419 ustart = uend = n; 420 continue; 421 } 422 if (skip > 0) { 423 ustart += skip; 424 size -= skip; 425 skip = 0; 426 } 427 if (size > limit) 428 size = limit; 429 if (debug && size == 1) 430 pwarn("%s %s %d MARKED USED\n", 431 "UNALLOCATED", name, ustart); 432 else if (debug) 433 pwarn("%s %sS %d-%d MARKED USED\n", 434 "UNALLOCATED", name, ustart, 435 ustart + size - 1); 436 if (bkgrdflag != 0) { 437 cmd.value = ustart; 438 cmd.size = size; 439 if (sysctl(opcode, MIBSIZE, 0, 0, 440 &cmd, sizeof cmd) == -1) { 441 snprintf(buf, BUFSIZE, 442 "FREE %s", name); 443 rwerror(buf, cmd.value); 444 } 445 } 446 limit -= size; 447 if (limit <= 0) 448 return; 449 ustart = uend = n; 450 } 451 } 452 } 453 if (astart != -1) 454 if (astart == aend) 455 pfatal("ALLOCATED %s %d MARKED FREE\n", name, astart); 456 else 457 pfatal("ALLOCATED %sS %d-%d MARKED FREE\n", 458 name, astart, aend); 459 if (ustart != -1) { 460 size = uend - ustart + 1; 461 if (size <= skip) 462 return; 463 if (skip > 0) { 464 ustart += skip; 465 size -= skip; 466 } 467 if (size > limit) 468 size = limit; 469 if (debug) { 470 if (size == 1) 471 pwarn("UNALLOCATED %s %d MARKED USED\n", 472 name, ustart); 473 else 474 pwarn("UNALLOCATED %sS %d-%d MARKED USED\n", 475 name, ustart, ustart + size - 1); 476 } 477 if (bkgrdflag != 0) { 478 cmd.value = ustart; 479 cmd.size = size; 480 if (sysctl(opcode, MIBSIZE, 0, 0, &cmd, 481 sizeof cmd) == -1) { 482 snprintf(buf, BUFSIZE, "FREE %s", name); 483 rwerror(buf, cmd.value); 484 } 485 } 486 } 487} 488