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