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