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