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 36 static 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$"); 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 54 static void check_maps(u_char *, u_char *, int, int, const char *, int *, int, int); 55 56 void 57 pass5(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 if (got_sigalarm) { 161 setproctitle("%s p5 %d%%", cdevname, 162 c * 100 / sblock.fs_ncg); 163 got_sigalarm = 0; 164 } 165 getblk(&cgblk, cgtod(fs, c), fs->fs_cgsize); 166 if (!cg_chkmagic(cg)) 167 pfatal("CG %d: BAD MAGIC NUMBER\n", c); 168 newcg->cg_time = cg->cg_time; 169 newcg->cg_old_time = cg->cg_old_time; 170 newcg->cg_cgx = c; 171 dbase = cgbase(fs, c); 172 dmax = dbase + fs->fs_fpg; 173 if (dmax > fs->fs_size) 174 dmax = fs->fs_size; 175 newcg->cg_ndblk = dmax - dbase; 176 if (fs->fs_magic == FS_UFS1_MAGIC) { 177 if (c == fs->fs_ncg - 1) 178 newcg->cg_old_ncyl = howmany(newcg->cg_ndblk, 179 fs->fs_fpg / fs->fs_old_cpg); 180 else 181 newcg->cg_old_ncyl = fs->fs_old_cpg; 182 newcg->cg_old_niblk = fs->fs_ipg; 183 newcg->cg_niblk = 0; 184 } 185 if (fs->fs_contigsumsize > 0) 186 newcg->cg_nclusterblks = newcg->cg_ndblk / fs->fs_frag; 187 newcg->cg_cs.cs_ndir = 0; 188 newcg->cg_cs.cs_nffree = 0; 189 newcg->cg_cs.cs_nbfree = 0; 190 newcg->cg_cs.cs_nifree = fs->fs_ipg; 191 if (cg->cg_rotor >= 0 && cg->cg_rotor < newcg->cg_ndblk) 192 newcg->cg_rotor = cg->cg_rotor; 193 else 194 newcg->cg_rotor = 0; 195 if (cg->cg_frotor >= 0 && cg->cg_frotor < newcg->cg_ndblk) 196 newcg->cg_frotor = cg->cg_frotor; 197 else 198 newcg->cg_frotor = 0; 199 if (cg->cg_irotor >= 0 && cg->cg_irotor < fs->fs_ipg) 200 newcg->cg_irotor = cg->cg_irotor; 201 else 202 newcg->cg_irotor = 0; 203 if (fs->fs_magic == FS_UFS1_MAGIC) { 204 newcg->cg_initediblk = 0; 205 } else { 206 if ((unsigned)cg->cg_initediblk > fs->fs_ipg) 207 newcg->cg_initediblk = fs->fs_ipg; 208 else 209 newcg->cg_initediblk = cg->cg_initediblk; 210 } 211 memset(&newcg->cg_frsum[0], 0, sizeof newcg->cg_frsum); 212 memset(cg_inosused(newcg), 0, (size_t)(mapsize)); 213 j = fs->fs_ipg * c; 214 for (i = 0; i < inostathead[c].il_numalloced; j++, i++) { 215 switch (inoinfo(j)->ino_state) { 216 217 case USTATE: 218 break; 219 220 case DSTATE: 221 case DCLEAR: 222 case DFOUND: 223 newcg->cg_cs.cs_ndir++; 224 /* FALLTHROUGH */ 225 226 case FSTATE: 227 case FCLEAR: 228 newcg->cg_cs.cs_nifree--; 229 setbit(cg_inosused(newcg), i); 230 break; 231 232 default: 233 if (j < (int)ROOTINO) 234 break; 235 errx(EEXIT, "BAD STATE %d FOR INODE I=%d", 236 inoinfo(j)->ino_state, j); 237 } 238 } 239 if (c == 0) 240 for (i = 0; i < (int)ROOTINO; i++) { 241 setbit(cg_inosused(newcg), i); 242 newcg->cg_cs.cs_nifree--; 243 } 244 for (i = 0, d = dbase; 245 d < dmax; 246 d += fs->fs_frag, i += fs->fs_frag) { 247 frags = 0; 248 for (j = 0; j < fs->fs_frag; j++) { 249 if (testbmap(d + j)) 250 continue; 251 setbit(cg_blksfree(newcg), i + j); 252 frags++; 253 } 254 if (frags == fs->fs_frag) { 255 newcg->cg_cs.cs_nbfree++; 256 if (fs->fs_contigsumsize > 0) 257 setbit(cg_clustersfree(newcg), 258 i / fs->fs_frag); 259 } else if (frags > 0) { 260 newcg->cg_cs.cs_nffree += frags; 261 blk = blkmap(fs, cg_blksfree(newcg), i); 262 ffs_fragacct(fs, blk, newcg->cg_frsum, 1); 263 } 264 } 265 if (fs->fs_contigsumsize > 0) { 266 int32_t *sump = cg_clustersum(newcg); 267 u_char *mapp = cg_clustersfree(newcg); 268 int map = *mapp++; 269 int bit = 1; 270 int run = 0; 271 272 for (i = 0; i < newcg->cg_nclusterblks; i++) { 273 if ((map & bit) != 0) { 274 run++; 275 } else if (run != 0) { 276 if (run > fs->fs_contigsumsize) 277 run = fs->fs_contigsumsize; 278 sump[run]++; 279 run = 0; 280 } 281 if ((i & (CHAR_BIT - 1)) != (CHAR_BIT - 1)) { 282 bit <<= 1; 283 } else { 284 map = *mapp++; 285 bit = 1; 286 } 287 } 288 if (run != 0) { 289 if (run > fs->fs_contigsumsize) 290 run = fs->fs_contigsumsize; 291 sump[run]++; 292 } 293 } 294 cstotal.cs_nffree += newcg->cg_cs.cs_nffree; 295 cstotal.cs_nbfree += newcg->cg_cs.cs_nbfree; 296 cstotal.cs_nifree += newcg->cg_cs.cs_nifree; 297 cstotal.cs_ndir += newcg->cg_cs.cs_ndir; 298 cs = &fs->fs_cs(fs, c); 299 if (cursnapshot == 0 && 300 memcmp(&newcg->cg_cs, cs, sizeof *cs) != 0 && 301 dofix(&idesc[0], "FREE BLK COUNT(S) WRONG IN SUPERBLK")) { 302 memmove(cs, &newcg->cg_cs, sizeof *cs); 303 sbdirty(); 304 } 305 if (rewritecg) { 306 memmove(cg, newcg, (size_t)fs->fs_cgsize); 307 cgdirty(); 308 continue; 309 } 310 if (cursnapshot == 0 && 311 memcmp(newcg, cg, basesize) != 0 && 312 dofix(&idesc[2], "SUMMARY INFORMATION BAD")) { 313 memmove(cg, newcg, (size_t)basesize); 314 cgdirty(); 315 } 316 if (bkgrdflag != 0 || usedsoftdep || debug) { 317 excessdirs = cg->cg_cs.cs_ndir - newcg->cg_cs.cs_ndir; 318 if (excessdirs < 0) { 319 pfatal("LOST %d DIRECTORIES\n", -excessdirs); 320 excessdirs = 0; 321 } 322 if (excessdirs > 0) 323 check_maps(cg_inosused(newcg), cg_inosused(cg), 324 inomapsize, cg->cg_cgx * fs->fs_ipg, "DIR", 325 freedirs, 0, excessdirs); 326 check_maps(cg_inosused(newcg), cg_inosused(cg), 327 inomapsize, cg->cg_cgx * fs->fs_ipg, "FILE", 328 freefiles, excessdirs, fs->fs_ipg); 329 check_maps(cg_blksfree(cg), cg_blksfree(newcg), 330 blkmapsize, cg->cg_cgx * fs->fs_fpg, "FRAG", 331 freeblks, 0, fs->fs_fpg); 332 } 333 if (cursnapshot == 0 && 334 memcmp(cg_inosused(newcg), cg_inosused(cg), mapsize) != 0 && 335 dofix(&idesc[1], "BLK(S) MISSING IN BIT MAPS")) { 336 memmove(cg_inosused(cg), cg_inosused(newcg), 337 (size_t)mapsize); 338 cgdirty(); 339 } 340 } 341 if (cursnapshot == 0 && 342 memcmp(&cstotal, &fs->fs_cstotal, sizeof cstotal) != 0 343 && dofix(&idesc[0], "SUMMARY BLK COUNT(S) WRONG IN SUPERBLK")) { 344 memmove(&fs->fs_cstotal, &cstotal, sizeof cstotal); 345 fs->fs_ronly = 0; 346 fs->fs_fmod = 0; 347 sbdirty(); 348 } 349 } 350 351 static void 352 check_maps( 353 u_char *map1, /* map of claimed allocations */ 354 u_char *map2, /* map of determined allocations */ 355 int mapsize, /* size of above two maps */ 356 int startvalue, /* resource value for first element in map */ 357 const char *name, /* name of resource found in maps */ 358 int *opcode, /* sysctl opcode to free resource */ 359 int skip, /* number of entries to skip before starting to free */ 360 int limit) /* limit on number of entries to free */ 361 { 362 # define BUFSIZE 16 363 char buf[BUFSIZE]; 364 long i, j, k, l, m, n, size; 365 int astart, aend, ustart, uend; 366 void (*msg)(const char *fmt, ...); 367 368 if (bkgrdflag) 369 msg = pfatal; 370 else 371 msg = pwarn; 372 astart = ustart = aend = uend = -1; 373 for (i = 0; i < mapsize; i++) { 374 j = *map1++; 375 k = *map2++; 376 if (j == k) 377 continue; 378 for (m = 0, l = 1; m < CHAR_BIT; m++, l <<= 1) { 379 if ((j & l) == (k & l)) 380 continue; 381 n = startvalue + i * CHAR_BIT + m; 382 if ((j & l) != 0) { 383 if (astart == -1) { 384 astart = aend = n; 385 continue; 386 } 387 if (aend + 1 == n) { 388 aend = n; 389 continue; 390 } 391 if (astart == aend) 392 (*msg)("ALLOCATED %s %d MARKED FREE\n", 393 name, astart); 394 else 395 (*msg)("%s %sS %d-%d MARKED FREE\n", 396 "ALLOCATED", name, astart, aend); 397 astart = aend = n; 398 } else { 399 if (ustart == -1) { 400 ustart = uend = n; 401 continue; 402 } 403 if (uend + 1 == n) { 404 uend = n; 405 continue; 406 } 407 size = uend - ustart + 1; 408 if (size <= skip) { 409 skip -= size; 410 ustart = uend = n; 411 continue; 412 } 413 if (skip > 0) { 414 ustart += skip; 415 size -= skip; 416 skip = 0; 417 } 418 if (size > limit) 419 size = limit; 420 if (debug && size == 1) 421 pwarn("%s %s %d MARKED USED\n", 422 "UNALLOCATED", name, ustart); 423 else if (debug) 424 pwarn("%s %sS %d-%ld MARKED USED\n", 425 "UNALLOCATED", name, ustart, 426 ustart + size - 1); 427 if (bkgrdflag != 0) { 428 cmd.value = ustart; 429 cmd.size = size; 430 if (sysctl(opcode, MIBSIZE, 0, 0, 431 &cmd, sizeof cmd) == -1) { 432 snprintf(buf, BUFSIZE, 433 "FREE %s", name); 434 rwerror(buf, cmd.value); 435 } 436 } 437 limit -= size; 438 if (limit <= 0) 439 return; 440 ustart = uend = n; 441 } 442 } 443 } 444 if (astart != -1) { 445 if (astart == aend) 446 (*msg)("ALLOCATED %s %d MARKED FREE\n", name, astart); 447 else 448 (*msg)("ALLOCATED %sS %d-%d MARKED FREE\n", 449 name, astart, aend); 450 } 451 if (ustart != -1) { 452 size = uend - ustart + 1; 453 if (size <= skip) 454 return; 455 if (skip > 0) { 456 ustart += skip; 457 size -= skip; 458 } 459 if (size > limit) 460 size = limit; 461 if (debug) { 462 if (size == 1) 463 pwarn("UNALLOCATED %s %d MARKED USED\n", 464 name, ustart); 465 else 466 pwarn("UNALLOCATED %sS %d-%ld MARKED USED\n", 467 name, ustart, ustart + size - 1); 468 } 469 if (bkgrdflag != 0) { 470 cmd.value = ustart; 471 cmd.size = size; 472 if (sysctl(opcode, MIBSIZE, 0, 0, &cmd, 473 sizeof cmd) == -1) { 474 snprintf(buf, BUFSIZE, "FREE %s", name); 475 rwerror(buf, cmd.value); 476 } 477 } 478 } 479 } 480