1 /*- 2 * Copyright (c) 2006 Pawel Jakub Dawidek <pjd@FreeBSD.org> 3 * 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 * 14 * THIS SOFTWARE IS PROVIDED BY THE AUTHORS AND CONTRIBUTORS ``AS IS'' AND 15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHORS OR CONTRIBUTORS BE LIABLE 18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 24 * SUCH DAMAGE. 25 * 26 * Copyright (c) 1982, 1986, 1989, 1993 27 * The Regents of the University of California. All rights reserved. 28 * 29 * Redistribution and use in source and binary forms, with or without 30 * modification, are permitted provided that the following conditions 31 * are met: 32 * 1. Redistributions of source code must retain the above copyright 33 * notice, this list of conditions and the following disclaimer. 34 * 2. Redistributions in binary form must reproduce the above copyright 35 * notice, this list of conditions and the following disclaimer in the 36 * documentation and/or other materials provided with the distribution. 37 * 4. Neither the name of the University nor the names of its contributors 38 * may be used to endorse or promote products derived from this software 39 * without specific prior written permission. 40 * 41 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 42 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 43 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 44 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 45 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 46 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 47 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 48 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 49 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 50 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 51 * SUCH DAMAGE. 52 */ 53 54 #include <sys/cdefs.h> 55 __FBSDID("$FreeBSD$"); 56 57 #include <sys/param.h> 58 #include <sys/disklabel.h> 59 #include <sys/mount.h> 60 #include <sys/stat.h> 61 62 #include <ufs/ufs/ufsmount.h> 63 #include <ufs/ufs/dinode.h> 64 #include <ufs/ffs/fs.h> 65 66 #include <stdio.h> 67 #include <stdlib.h> 68 #include <stdint.h> 69 #include <libufs.h> 70 #include <strings.h> 71 #include <err.h> 72 #include <assert.h> 73 74 #include "fsck.h" 75 76 struct cgchain { 77 union { 78 struct cg cgcu_cg; 79 char cgcu_buf[MAXBSIZE]; 80 } cgc_union; 81 int cgc_busy; 82 int cgc_dirty; 83 LIST_ENTRY(cgchain) cgc_next; 84 }; 85 #define cgc_cg cgc_union.cgcu_cg 86 87 #define MAX_CACHED_CGS 1024 88 static unsigned ncgs = 0; 89 static LIST_HEAD(, cgchain) cglist = LIST_HEAD_INITIALIZER(cglist); 90 91 static const char *devnam; 92 static struct uufsd *disk = NULL; 93 static struct fs *fs = NULL; 94 struct ufs2_dinode ufs2_zino; 95 96 static void putcgs(void); 97 98 /* 99 * Return cylinder group from the cache or load it if it is not in the 100 * cache yet. 101 * Don't cache more than MAX_CACHED_CGS cylinder groups. 102 */ 103 static struct cgchain * 104 getcg(int cg) 105 { 106 struct cgchain *cgc; 107 108 assert(disk != NULL && fs != NULL); 109 LIST_FOREACH(cgc, &cglist, cgc_next) { 110 if (cgc->cgc_cg.cg_cgx == cg) { 111 //printf("%s: Found cg=%d\n", __func__, cg); 112 return (cgc); 113 } 114 } 115 /* 116 * Our cache is full? Let's clean it up. 117 */ 118 if (ncgs >= MAX_CACHED_CGS) { 119 //printf("%s: Flushing CGs.\n", __func__); 120 putcgs(); 121 } 122 cgc = malloc(sizeof(*cgc)); 123 if (cgc == NULL) { 124 /* 125 * Cannot allocate memory? 126 * Let's put all currently loaded and not busy cylinder groups 127 * on disk and try again. 128 */ 129 //printf("%s: No memory, flushing CGs.\n", __func__); 130 putcgs(); 131 cgc = malloc(sizeof(*cgc)); 132 if (cgc == NULL) 133 err(1, "malloc(%zu)", sizeof(*cgc)); 134 } 135 if (cgread1(disk, cg) == -1) 136 err(1, "cgread1(%d)", cg); 137 bcopy(&disk->d_cg, &cgc->cgc_cg, sizeof(cgc->cgc_union)); 138 cgc->cgc_busy = 0; 139 cgc->cgc_dirty = 0; 140 LIST_INSERT_HEAD(&cglist, cgc, cgc_next); 141 ncgs++; 142 //printf("%s: Read cg=%d\n", __func__, cg); 143 return (cgc); 144 } 145 146 /* 147 * Mark cylinder group as dirty - it will be written back on putcgs(). 148 */ 149 static void 150 dirtycg(struct cgchain *cgc) 151 { 152 153 cgc->cgc_dirty = 1; 154 } 155 156 /* 157 * Mark cylinder group as busy - it will not be freed on putcgs(). 158 */ 159 static void 160 busycg(struct cgchain *cgc) 161 { 162 163 cgc->cgc_busy = 1; 164 } 165 166 /* 167 * Unmark the given cylinder group as busy. 168 */ 169 static void 170 unbusycg(struct cgchain *cgc) 171 { 172 173 cgc->cgc_busy = 0; 174 } 175 176 /* 177 * Write back all dirty cylinder groups. 178 * Free all non-busy cylinder groups. 179 */ 180 static void 181 putcgs(void) 182 { 183 struct cgchain *cgc, *cgc2; 184 185 assert(disk != NULL && fs != NULL); 186 LIST_FOREACH_SAFE(cgc, &cglist, cgc_next, cgc2) { 187 if (cgc->cgc_busy) 188 continue; 189 LIST_REMOVE(cgc, cgc_next); 190 ncgs--; 191 if (cgc->cgc_dirty) { 192 bcopy(&cgc->cgc_cg, &disk->d_cg, 193 sizeof(cgc->cgc_union)); 194 if (cgwrite1(disk, cgc->cgc_cg.cg_cgx) == -1) 195 err(1, "cgwrite1(%d)", cgc->cgc_cg.cg_cgx); 196 //printf("%s: Wrote cg=%d\n", __func__, 197 // cgc->cgc_cg.cg_cgx); 198 } 199 free(cgc); 200 } 201 } 202 203 #if 0 204 /* 205 * Free all non-busy cylinder groups without storing the dirty ones. 206 */ 207 static void 208 cancelcgs(void) 209 { 210 struct cgchain *cgc; 211 212 assert(disk != NULL && fs != NULL); 213 while ((cgc = LIST_FIRST(&cglist)) != NULL) { 214 if (cgc->cgc_busy) 215 continue; 216 LIST_REMOVE(cgc, cgc_next); 217 //printf("%s: Canceled cg=%d\n", __func__, cgc->cgc_cg.cg_cgx); 218 free(cgc); 219 } 220 } 221 #endif 222 223 /* 224 * Open the given provider, load superblock. 225 */ 226 static void 227 opendisk(void) 228 { 229 if (disk != NULL) 230 return; 231 disk = malloc(sizeof(*disk)); 232 if (disk == NULL) 233 err(1, "malloc(%zu)", sizeof(*disk)); 234 if (ufs_disk_fillout(disk, devnam) == -1) { 235 err(1, "ufs_disk_fillout(%s) failed: %s", devnam, 236 disk->d_error); 237 } 238 fs = &disk->d_fs; 239 } 240 241 /* 242 * Mark file system as clean, write the super-block back, close the disk. 243 */ 244 static void 245 closedisk(void) 246 { 247 248 fs->fs_clean = 1; 249 if (sbwrite(disk, 0) == -1) 250 err(1, "sbwrite(%s)", devnam); 251 if (ufs_disk_close(disk) == -1) 252 err(1, "ufs_disk_close(%s)", devnam); 253 free(disk); 254 disk = NULL; 255 fs = NULL; 256 } 257 258 static void 259 blkfree(ufs2_daddr_t bno, long size) 260 { 261 struct cgchain *cgc; 262 struct cg *cgp; 263 ufs1_daddr_t fragno, cgbno; 264 int i, cg, blk, frags, bbase; 265 u_int8_t *blksfree; 266 267 cg = dtog(fs, bno); 268 cgc = getcg(cg); 269 dirtycg(cgc); 270 cgp = &cgc->cgc_cg; 271 cgbno = dtogd(fs, bno); 272 blksfree = cg_blksfree(cgp); 273 if (size == fs->fs_bsize) { 274 fragno = fragstoblks(fs, cgbno); 275 if (!ffs_isfreeblock(fs, blksfree, fragno)) 276 assert(!"blkfree: freeing free block"); 277 ffs_setblock(fs, blksfree, fragno); 278 ffs_clusteracct(fs, cgp, fragno, 1); 279 cgp->cg_cs.cs_nbfree++; 280 fs->fs_cstotal.cs_nbfree++; 281 fs->fs_cs(fs, cg).cs_nbfree++; 282 } else { 283 bbase = cgbno - fragnum(fs, cgbno); 284 /* 285 * decrement the counts associated with the old frags 286 */ 287 blk = blkmap(fs, blksfree, bbase); 288 ffs_fragacct(fs, blk, cgp->cg_frsum, -1); 289 /* 290 * deallocate the fragment 291 */ 292 frags = numfrags(fs, size); 293 for (i = 0; i < frags; i++) { 294 if (isset(blksfree, cgbno + i)) 295 assert(!"blkfree: freeing free frag"); 296 setbit(blksfree, cgbno + i); 297 } 298 cgp->cg_cs.cs_nffree += i; 299 fs->fs_cstotal.cs_nffree += i; 300 fs->fs_cs(fs, cg).cs_nffree += i; 301 /* 302 * add back in counts associated with the new frags 303 */ 304 blk = blkmap(fs, blksfree, bbase); 305 ffs_fragacct(fs, blk, cgp->cg_frsum, 1); 306 /* 307 * if a complete block has been reassembled, account for it 308 */ 309 fragno = fragstoblks(fs, bbase); 310 if (ffs_isblock(fs, blksfree, fragno)) { 311 cgp->cg_cs.cs_nffree -= fs->fs_frag; 312 fs->fs_cstotal.cs_nffree -= fs->fs_frag; 313 fs->fs_cs(fs, cg).cs_nffree -= fs->fs_frag; 314 ffs_clusteracct(fs, cgp, fragno, 1); 315 cgp->cg_cs.cs_nbfree++; 316 fs->fs_cstotal.cs_nbfree++; 317 fs->fs_cs(fs, cg).cs_nbfree++; 318 } 319 } 320 } 321 322 /* 323 * Recursively free all indirect blocks. 324 */ 325 static void 326 freeindir(ufs2_daddr_t blk, int level) 327 { 328 char sblks[MAXBSIZE]; 329 ufs2_daddr_t *blks; 330 int i; 331 332 if (bread(disk, fsbtodb(fs, blk), (void *)&sblks, (size_t)fs->fs_bsize) == -1) 333 err(1, "bread: %s", disk->d_error); 334 blks = (ufs2_daddr_t *)&sblks; 335 for (i = 0; i < NINDIR(fs); i++) { 336 if (blks[i] == 0) 337 break; 338 if (level == 0) 339 blkfree(blks[i], fs->fs_bsize); 340 else 341 freeindir(blks[i], level - 1); 342 } 343 blkfree(blk, fs->fs_bsize); 344 } 345 346 #define dblksize(fs, dino, lbn) \ 347 ((dino)->di_size >= smalllblktosize(fs, (lbn) + 1) \ 348 ? (fs)->fs_bsize \ 349 : fragroundup(fs, blkoff(fs, (dino)->di_size))) 350 351 /* 352 * Free all blocks associated with the given inode. 353 */ 354 static void 355 clear_inode(struct ufs2_dinode *dino) 356 { 357 ufs2_daddr_t bn; 358 int extblocks, i, level; 359 off_t osize; 360 long bsize; 361 362 extblocks = 0; 363 if (fs->fs_magic == FS_UFS2_MAGIC && dino->di_extsize > 0) 364 extblocks = btodb(fragroundup(fs, dino->di_extsize)); 365 /* deallocate external attributes blocks */ 366 if (extblocks > 0) { 367 osize = dino->di_extsize; 368 dino->di_blocks -= extblocks; 369 dino->di_extsize = 0; 370 for (i = 0; i < NXADDR; i++) { 371 if (dino->di_extb[i] == 0) 372 continue; 373 blkfree(dino->di_extb[i], sblksize(fs, osize, i)); 374 } 375 } 376 #define SINGLE 0 /* index of single indirect block */ 377 #define DOUBLE 1 /* index of double indirect block */ 378 #define TRIPLE 2 /* index of triple indirect block */ 379 /* deallocate indirect blocks */ 380 for (level = SINGLE; level <= TRIPLE; level++) { 381 if (dino->di_ib[level] == 0) 382 break; 383 freeindir(dino->di_ib[level], level); 384 } 385 /* deallocate direct blocks and fragments */ 386 for (i = 0; i < NDADDR; i++) { 387 bn = dino->di_db[i]; 388 if (bn == 0) 389 continue; 390 bsize = dblksize(fs, dino, i); 391 blkfree(bn, bsize); 392 } 393 } 394 395 void 396 gjournal_check(const char *filesys) 397 { 398 struct ufs2_dinode *dino; 399 void *p; 400 struct cgchain *cgc; 401 struct cg *cgp; 402 uint8_t *inosused; 403 ino_t cino, ino; 404 int cg, mode; 405 406 devnam = filesys; 407 opendisk(); 408 /* Are there any unreferenced inodes in this file system? */ 409 if (fs->fs_unrefs == 0) { 410 //printf("No unreferenced inodes.\n"); 411 closedisk(); 412 return; 413 } 414 415 for (cg = 0; cg < fs->fs_ncg; cg++) { 416 /* Show progress if requested. */ 417 if (got_siginfo) { 418 printf("%s: phase j: cyl group %d of %d (%d%%)\n", 419 cdevname, cg, fs->fs_ncg, cg * 100 / fs->fs_ncg); 420 got_siginfo = 0; 421 } 422 if (got_sigalarm) { 423 setproctitle("%s pj %d%%", cdevname, 424 cg * 100 / fs->fs_ncg); 425 got_sigalarm = 0; 426 } 427 cgc = getcg(cg); 428 cgp = &cgc->cgc_cg; 429 /* Are there any unreferenced inodes in this cylinder group? */ 430 if (cgp->cg_unrefs == 0) 431 continue; 432 //printf("Analizing cylinder group %d (count=%d)\n", cg, cgp->cg_unrefs); 433 /* 434 * We are going to modify this cylinder group, so we want it to 435 * be written back. 436 */ 437 dirtycg(cgc); 438 /* We don't want it to be freed in the meantime. */ 439 busycg(cgc); 440 inosused = cg_inosused(cgp); 441 /* 442 * Now go through the list of all inodes in this cylinder group 443 * to find unreferenced ones. 444 */ 445 for (cino = 0; cino < fs->fs_ipg; cino++) { 446 ino = fs->fs_ipg * cg + cino; 447 /* Unallocated? Skip it. */ 448 if (isclr(inosused, cino)) 449 continue; 450 if (getino(disk, &p, ino, &mode) == -1) 451 err(1, "getino(cg=%d ino=%ju)", 452 cg, (uintmax_t)ino); 453 dino = p; 454 /* Not a regular file nor directory? Skip it. */ 455 if (!S_ISREG(dino->di_mode) && !S_ISDIR(dino->di_mode)) 456 continue; 457 /* Has reference(s)? Skip it. */ 458 if (dino->di_nlink > 0) 459 continue; 460 //printf("Clearing inode=%d (size=%jd)\n", ino, (intmax_t)dino->di_size); 461 /* Free inode's blocks. */ 462 clear_inode(dino); 463 /* Deallocate it. */ 464 clrbit(inosused, cino); 465 /* Update position of last used inode. */ 466 if (ino < cgp->cg_irotor) 467 cgp->cg_irotor = ino; 468 /* Update statistics. */ 469 cgp->cg_cs.cs_nifree++; 470 fs->fs_cs(fs, cg).cs_nifree++; 471 fs->fs_cstotal.cs_nifree++; 472 cgp->cg_unrefs--; 473 fs->fs_unrefs--; 474 /* If this is directory, update related statistics. */ 475 if (S_ISDIR(dino->di_mode)) { 476 cgp->cg_cs.cs_ndir--; 477 fs->fs_cs(fs, cg).cs_ndir--; 478 fs->fs_cstotal.cs_ndir--; 479 } 480 /* Zero-fill the inode. */ 481 *dino = ufs2_zino; 482 /* Write the inode back. */ 483 if (putino(disk) == -1) 484 err(1, "putino(cg=%d ino=%ju)", 485 cg, (uintmax_t)ino); 486 if (cgp->cg_unrefs == 0) { 487 //printf("No more unreferenced inodes in cg=%d.\n", cg); 488 break; 489 } 490 } 491 /* 492 * We don't need this cylinder group anymore, so feel free to 493 * free it if needed. 494 */ 495 unbusycg(cgc); 496 /* 497 * If there are no more unreferenced inodes, there is no need to 498 * check other cylinder groups. 499 */ 500 if (fs->fs_unrefs == 0) { 501 //printf("No more unreferenced inodes (cg=%d/%d).\n", cg, 502 // fs->fs_ncg); 503 break; 504 } 505 } 506 /* Write back modified cylinder groups. */ 507 putcgs(); 508 /* Write back updated statistics and super-block. */ 509 closedisk(); 510 } 511