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