pass5.c revision 107829
1258065Spjd/* 2258065Spjd * Copyright (c) 1980, 1986, 1993 3286796Soshogbo * The Regents of the University of California. All rights reserved. 4258065Spjd * 5258065Spjd * Redistribution and use in source and binary forms, with or without 6258065Spjd * modification, are permitted provided that the following conditions 7258065Spjd * are met: 8258065Spjd * 1. Redistributions of source code must retain the above copyright 9258065Spjd * notice, this list of conditions and the following disclaimer. 10258065Spjd * 2. Redistributions in binary form must reproduce the above copyright 11258065Spjd * notice, this list of conditions and the following disclaimer in the 12258065Spjd * documentation and/or other materials provided with the distribution. 13258065Spjd * 3. All advertising materials mentioning features or use of this software 14258065Spjd * must display the following acknowledgement: 15258065Spjd * This product includes software developed by the University of 16258065Spjd * California, Berkeley and its contributors. 17258065Spjd * 4. Neither the name of the University nor the names of its contributors 18258065Spjd * may be used to endorse or promote products derived from this software 19258065Spjd * without specific prior written permission. 20258065Spjd * 21258065Spjd * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 22258065Spjd * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 23258065Spjd * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 24258065Spjd * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 25258065Spjd * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 26258065Spjd * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 27258065Spjd * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 28258065Spjd * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 29258065Spjd * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 30258065Spjd * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 31258065Spjd * SUCH DAMAGE. 32258065Spjd */ 33258065Spjd 34258065Spjd#if 0 35258065Spjd#ifndef lint 36258065Spjdstatic const char sccsid[] = "@(#)pass5.c 8.9 (Berkeley) 4/28/95"; 37258065Spjd#endif /* not lint */ 38258065Spjd#endif 39258065Spjd 40258065Spjd#include <sys/cdefs.h> 41258065Spjd__FBSDID("$FreeBSD: head/sbin/fsck_ffs/pass5.c 107829 2002-12-13 19:47:07Z imp $"); 42258065Spjd 43286796Soshogbo#include <sys/param.h> 44271579Spjd#include <sys/sysctl.h> 45271579Spjd 46282248Soshogbo#include <ufs/ufs/dinode.h> 47286796Soshogbo#include <ufs/ffs/fs.h> 48258065Spjd 49286796Soshogbo#include <err.h> 50286796Soshogbo#include <limits.h> 51258065Spjd#include <string.h> 52279438Srstone 53282250Soshogbo#include "fsck.h" 54279438Srstone 55282250Soshogbostatic void check_maps(u_char *, u_char *, int, int, const char *, int *, int, int); 56279438Srstone 57282250Soshogbovoid 58279438Srstonepass5(void) 59279438Srstone{ 60279438Srstone int c, i, j, blk, frags, basesize, mapsize; 61279438Srstone int inomapsize, blkmapsize; 62282282Soshogbo struct fs *fs = &sblock; 63282282Soshogbo struct cg *cg = &cgrp; 64282282Soshogbo ufs2_daddr_t d, dbase, dmax; 65279438Srstone int excessdirs, rewritecg = 0; 66279438Srstone struct csum *cs; 67279438Srstone struct csum_total cstotal; 68279438Srstone struct inodesc idesc[3]; 69279438Srstone char buf[MAXBSIZE]; 70279438Srstone struct cg *newcg = (struct cg *)buf; 71279438Srstone 72279438Srstone inoinfo(WINO)->ino_state = USTATE; 73279438Srstone memset(newcg, 0, (size_t)fs->fs_cgsize); 74279438Srstone newcg->cg_niblk = fs->fs_ipg; 75279438Srstone if (cvtlevel >= 3) { 76279438Srstone if (fs->fs_maxcontig < 2 && fs->fs_contigsumsize > 0) { 77282282Soshogbo if (preen) 78282282Soshogbo pwarn("DELETING CLUSTERING MAPS\n"); 79282282Soshogbo if (preen || reply("DELETE CLUSTERING MAPS")) { 80282282Soshogbo fs->fs_contigsumsize = 0; 81282282Soshogbo rewritecg = 1; 82279438Srstone sbdirty(); 83282282Soshogbo } 84282282Soshogbo } 85282282Soshogbo if (fs->fs_maxcontig > 1) { 86279438Srstone const char *doit = 0; 87279438Srstone 88279438Srstone if (fs->fs_contigsumsize < 1) { 89279438Srstone doit = "CREAT"; 90258065Spjd } else if (fs->fs_contigsumsize < fs->fs_maxcontig && 91258065Spjd fs->fs_contigsumsize < FS_MAXCONTIG) { 92286796Soshogbo doit = "EXPAND"; 93258065Spjd } 94258065Spjd if (doit) { 95258065Spjd i = fs->fs_contigsumsize; 96258065Spjd fs->fs_contigsumsize = 97258065Spjd MIN(fs->fs_maxcontig, FS_MAXCONTIG); 98258065Spjd if (CGSIZE(fs) > (u_int)fs->fs_bsize) { 99258065Spjd pwarn("CANNOT %s CLUSTER MAPS\n", doit); 100286645Soshogbo fs->fs_contigsumsize = i; 101258065Spjd } else if (preen || 102271579Spjd reply("CREATE CLUSTER MAPS")) { 103286796Soshogbo if (preen) 104271579Spjd pwarn("%sING CLUSTER MAPS\n", 105258065Spjd doit); 106258065Spjd fs->fs_cgsize = 107258065Spjd fragroundup(fs, CGSIZE(fs)); 108258065Spjd rewritecg = 1; 109258065Spjd sbdirty(); 110258065Spjd } 111258065Spjd } 112258065Spjd } 113258065Spjd } 114258065Spjd basesize = &newcg->cg_space[0] - (u_char *)(&newcg->cg_firstfield); 115258065Spjd if (sblock.fs_magic == FS_UFS2_MAGIC) { 116258065Spjd newcg->cg_iusedoff = basesize; 117258065Spjd } else { 118258065Spjd /* 119258065Spjd * We reserve the space for the old rotation summary 120258065Spjd * tables for the benefit of old kernels, but do not 121258065Spjd * maintain them in modern kernels. In time, they can 122258065Spjd * go away. 123258065Spjd */ 124258065Spjd newcg->cg_old_btotoff = basesize; 125258065Spjd newcg->cg_old_boff = newcg->cg_old_btotoff + 126258065Spjd fs->fs_old_cpg * sizeof(int32_t); 127258065Spjd newcg->cg_iusedoff = newcg->cg_old_boff + 128286796Soshogbo fs->fs_old_cpg * fs->fs_old_nrpos * sizeof(u_int16_t); 129286796Soshogbo memset(&newcg->cg_space[0], 0, newcg->cg_iusedoff - basesize); 130286796Soshogbo } 131286796Soshogbo inomapsize = howmany(fs->fs_ipg, CHAR_BIT); 132286796Soshogbo newcg->cg_freeoff = newcg->cg_iusedoff + inomapsize; 133258065Spjd blkmapsize = howmany(fs->fs_fpg, CHAR_BIT); 134258065Spjd newcg->cg_nextfreeoff = newcg->cg_freeoff + blkmapsize; 135258065Spjd if (fs->fs_contigsumsize > 0) { 136258065Spjd newcg->cg_clustersumoff = newcg->cg_nextfreeoff - 137258065Spjd sizeof(u_int32_t); 138286796Soshogbo newcg->cg_clustersumoff = 139286796Soshogbo roundup(newcg->cg_clustersumoff, sizeof(u_int32_t)); 140286796Soshogbo newcg->cg_clusteroff = newcg->cg_clustersumoff + 141286796Soshogbo (fs->fs_contigsumsize + 1) * sizeof(u_int32_t); 142286796Soshogbo newcg->cg_nextfreeoff = newcg->cg_clusteroff + 143258065Spjd howmany(fragstoblks(fs, fs->fs_fpg), CHAR_BIT); 144286796Soshogbo } 145286796Soshogbo newcg->cg_magic = CG_MAGIC; 146286796Soshogbo mapsize = newcg->cg_nextfreeoff - newcg->cg_iusedoff; 147286796Soshogbo memset(&idesc[0], 0, sizeof idesc); 148286796Soshogbo for (i = 0; i < 3; i++) 149286796Soshogbo idesc[i].id_type = ADDR; 150286796Soshogbo memset(&cstotal, 0, sizeof(struct csum_total)); 151286796Soshogbo dmax = blknum(fs, fs->fs_size + fs->fs_frag - 1); 152286796Soshogbo for (d = fs->fs_size; d < dmax; d++) 153286796Soshogbo setbmap(d); 154286796Soshogbo for (c = 0; c < fs->fs_ncg; c++) { 155258065Spjd if (got_siginfo) { 156258065Spjd printf("%s: phase 5: cyl group %d of %d (%d%%)\n", 157258065Spjd cdevname, c, sblock.fs_ncg, 158258065Spjd c * 100 / sblock.fs_ncg); 159 got_siginfo = 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 newcg->cg_cs.cs_ndir++; 220 /* FALLTHROUGH */ 221 222 case FSTATE: 223 case FCLEAR: 224 newcg->cg_cs.cs_nifree--; 225 setbit(cg_inosused(newcg), i); 226 break; 227 228 default: 229 if (j < (int)ROOTINO) 230 break; 231 errx(EEXIT, "BAD STATE %d FOR INODE I=%d", 232 inoinfo(j)->ino_state, j); 233 } 234 } 235 if (c == 0) 236 for (i = 0; i < (int)ROOTINO; i++) { 237 setbit(cg_inosused(newcg), i); 238 newcg->cg_cs.cs_nifree--; 239 } 240 for (i = 0, d = dbase; 241 d < dmax; 242 d += fs->fs_frag, i += fs->fs_frag) { 243 frags = 0; 244 for (j = 0; j < fs->fs_frag; j++) { 245 if (testbmap(d + j)) 246 continue; 247 setbit(cg_blksfree(newcg), i + j); 248 frags++; 249 } 250 if (frags == fs->fs_frag) { 251 newcg->cg_cs.cs_nbfree++; 252 if (fs->fs_contigsumsize > 0) 253 setbit(cg_clustersfree(newcg), 254 i / fs->fs_frag); 255 } else if (frags > 0) { 256 newcg->cg_cs.cs_nffree += frags; 257 blk = blkmap(fs, cg_blksfree(newcg), i); 258 ffs_fragacct(fs, blk, newcg->cg_frsum, 1); 259 } 260 } 261 if (fs->fs_contigsumsize > 0) { 262 int32_t *sump = cg_clustersum(newcg); 263 u_char *mapp = cg_clustersfree(newcg); 264 int map = *mapp++; 265 int bit = 1; 266 int run = 0; 267 268 for (i = 0; i < newcg->cg_nclusterblks; i++) { 269 if ((map & bit) != 0) { 270 run++; 271 } else if (run != 0) { 272 if (run > fs->fs_contigsumsize) 273 run = fs->fs_contigsumsize; 274 sump[run]++; 275 run = 0; 276 } 277 if ((i & (CHAR_BIT - 1)) != (CHAR_BIT - 1)) { 278 bit <<= 1; 279 } else { 280 map = *mapp++; 281 bit = 1; 282 } 283 } 284 if (run != 0) { 285 if (run > fs->fs_contigsumsize) 286 run = fs->fs_contigsumsize; 287 sump[run]++; 288 } 289 } 290 cstotal.cs_nffree += newcg->cg_cs.cs_nffree; 291 cstotal.cs_nbfree += newcg->cg_cs.cs_nbfree; 292 cstotal.cs_nifree += newcg->cg_cs.cs_nifree; 293 cstotal.cs_ndir += newcg->cg_cs.cs_ndir; 294 cs = &fs->fs_cs(fs, c); 295 if (cursnapshot == 0 && 296 memcmp(&newcg->cg_cs, cs, sizeof *cs) != 0 && 297 dofix(&idesc[0], "FREE BLK COUNT(S) WRONG IN SUPERBLK")) { 298 memmove(cs, &newcg->cg_cs, sizeof *cs); 299 sbdirty(); 300 } 301 if (rewritecg) { 302 memmove(cg, newcg, (size_t)fs->fs_cgsize); 303 cgdirty(); 304 continue; 305 } 306 if (cursnapshot == 0 && 307 memcmp(newcg, cg, basesize) != 0 && 308 dofix(&idesc[2], "SUMMARY INFORMATION BAD")) { 309 memmove(cg, newcg, (size_t)basesize); 310 cgdirty(); 311 } 312 if (bkgrdflag != 0 || usedsoftdep || debug) { 313 excessdirs = cg->cg_cs.cs_ndir - newcg->cg_cs.cs_ndir; 314 if (excessdirs < 0) { 315 pfatal("LOST %d DIRECTORIES\n", -excessdirs); 316 excessdirs = 0; 317 } 318 if (excessdirs > 0) 319 check_maps(cg_inosused(newcg), cg_inosused(cg), 320 inomapsize, cg->cg_cgx * fs->fs_ipg, "DIR", 321 freedirs, 0, excessdirs); 322 check_maps(cg_inosused(newcg), cg_inosused(cg), 323 inomapsize, cg->cg_cgx * fs->fs_ipg, "FILE", 324 freefiles, excessdirs, fs->fs_ipg); 325 check_maps(cg_blksfree(cg), cg_blksfree(newcg), 326 blkmapsize, cg->cg_cgx * fs->fs_fpg, "FRAG", 327 freeblks, 0, fs->fs_fpg); 328 } 329 if (cursnapshot == 0 && 330 memcmp(cg_inosused(newcg), cg_inosused(cg), mapsize) != 0 && 331 dofix(&idesc[1], "BLK(S) MISSING IN BIT MAPS")) { 332 memmove(cg_inosused(cg), cg_inosused(newcg), 333 (size_t)mapsize); 334 cgdirty(); 335 } 336 } 337 if (cursnapshot == 0 && 338 memcmp(&cstotal, &fs->fs_cstotal, sizeof cstotal) != 0 339 && dofix(&idesc[0], "SUMMARY BLK COUNT(S) WRONG IN SUPERBLK")) { 340 memmove(&fs->fs_cstotal, &cstotal, sizeof cstotal); 341 fs->fs_ronly = 0; 342 fs->fs_fmod = 0; 343 sbdirty(); 344 } 345} 346 347static void 348check_maps( 349 u_char *map1, /* map of claimed allocations */ 350 u_char *map2, /* map of determined allocations */ 351 int mapsize, /* size of above two maps */ 352 int startvalue, /* resource value for first element in map */ 353 const char *name, /* name of resource found in maps */ 354 int *opcode, /* sysctl opcode to free resource */ 355 int skip, /* number of entries to skip before starting to free */ 356 int limit) /* limit on number of entries to free */ 357{ 358# define BUFSIZE 16 359 char buf[BUFSIZE]; 360 long i, j, k, l, m, n, size; 361 int astart, aend, ustart, uend; 362 void (*msg)(const char *fmt, ...); 363 364 if (bkgrdflag) 365 msg = pfatal; 366 else 367 msg = pwarn; 368 astart = ustart = aend = uend = -1; 369 for (i = 0; i < mapsize; i++) { 370 j = *map1++; 371 k = *map2++; 372 if (j == k) 373 continue; 374 for (m = 0, l = 1; m < CHAR_BIT; m++, l <<= 1) { 375 if ((j & l) == (k & l)) 376 continue; 377 n = startvalue + i * CHAR_BIT + m; 378 if ((j & l) != 0) { 379 if (astart == -1) { 380 astart = aend = n; 381 continue; 382 } 383 if (aend + 1 == n) { 384 aend = n; 385 continue; 386 } 387 if (astart == aend) 388 (*msg)("ALLOCATED %s %d MARKED FREE\n", 389 name, astart); 390 else 391 (*msg)("%s %sS %d-%d MARKED FREE\n", 392 "ALLOCATED", name, astart, aend); 393 astart = aend = n; 394 } else { 395 if (ustart == -1) { 396 ustart = uend = n; 397 continue; 398 } 399 if (uend + 1 == n) { 400 uend = n; 401 continue; 402 } 403 size = uend - ustart + 1; 404 if (size <= skip) { 405 skip -= size; 406 ustart = uend = n; 407 continue; 408 } 409 if (skip > 0) { 410 ustart += skip; 411 size -= skip; 412 skip = 0; 413 } 414 if (size > limit) 415 size = limit; 416 if (debug && size == 1) 417 pwarn("%s %s %d MARKED USED\n", 418 "UNALLOCATED", name, ustart); 419 else if (debug) 420 pwarn("%s %sS %d-%ld MARKED USED\n", 421 "UNALLOCATED", name, ustart, 422 ustart + size - 1); 423 if (bkgrdflag != 0) { 424 cmd.value = ustart; 425 cmd.size = size; 426 if (sysctl(opcode, MIBSIZE, 0, 0, 427 &cmd, sizeof cmd) == -1) { 428 snprintf(buf, BUFSIZE, 429 "FREE %s", name); 430 rwerror(buf, cmd.value); 431 } 432 } 433 limit -= size; 434 if (limit <= 0) 435 return; 436 ustart = uend = n; 437 } 438 } 439 } 440 if (astart != -1) { 441 if (astart == aend) 442 (*msg)("ALLOCATED %s %d MARKED FREE\n", name, astart); 443 else 444 (*msg)("ALLOCATED %sS %d-%d MARKED FREE\n", 445 name, astart, aend); 446 } 447 if (ustart != -1) { 448 size = uend - ustart + 1; 449 if (size <= skip) 450 return; 451 if (skip > 0) { 452 ustart += skip; 453 size -= skip; 454 } 455 if (size > limit) 456 size = limit; 457 if (debug) { 458 if (size == 1) 459 pwarn("UNALLOCATED %s %d MARKED USED\n", 460 name, ustart); 461 else 462 pwarn("UNALLOCATED %sS %d-%ld MARKED USED\n", 463 name, ustart, ustart + size - 1); 464 } 465 if (bkgrdflag != 0) { 466 cmd.value = ustart; 467 cmd.size = size; 468 if (sysctl(opcode, MIBSIZE, 0, 0, &cmd, 469 sizeof cmd) == -1) { 470 snprintf(buf, BUFSIZE, "FREE %s", name); 471 rwerror(buf, cmd.value); 472 } 473 } 474 } 475} 476