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 97 static void putcgs(void); 98 99 /* 100 * Return cylinder group from the cache or load it if it is not in the 101 * cache yet. 102 * Don't cache more than MAX_CACHED_CGS cylinder groups. 103 */ 104 static struct cgchain * 105 getcg(int cg) 106 { 107 struct cgchain *cgc; 108 109 assert(diskp != NULL && fs != NULL); 110 LIST_FOREACH(cgc, &cglist, cgc_next) { 111 if (cgc->cgc_cg.cg_cgx == cg) { 112 //printf("%s: Found cg=%d\n", __func__, cg); 113 return (cgc); 114 } 115 } 116 /* 117 * Our cache is full? Let's clean it up. 118 */ 119 if (ncgs >= MAX_CACHED_CGS) { 120 //printf("%s: Flushing CGs.\n", __func__); 121 putcgs(); 122 } 123 cgc = malloc(sizeof(*cgc)); 124 if (cgc == NULL) { 125 /* 126 * Cannot allocate memory? 127 * Let's put all currently loaded and not busy cylinder groups 128 * on disk and try again. 129 */ 130 //printf("%s: No memory, flushing CGs.\n", __func__); 131 putcgs(); 132 cgc = malloc(sizeof(*cgc)); 133 if (cgc == NULL) 134 err(1, "malloc(%zu)", sizeof(*cgc)); 135 } 136 if (cgget(diskp, cg, &cgc->cgc_cg) == -1) 137 err(1, "cgget(%d)", cg); 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(diskp != 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 if (cgput(diskp, &cgc->cgc_cg) == -1) 193 err(1, "cgput(%d)", cgc->cgc_cg.cg_cgx); 194 //printf("%s: Wrote cg=%d\n", __func__, 195 // cgc->cgc_cg.cg_cgx); 196 } 197 free(cgc); 198 } 199 } 200 201 #if 0 202 /* 203 * Free all non-busy cylinder groups without storing the dirty ones. 204 */ 205 static void 206 cancelcgs(void) 207 { 208 struct cgchain *cgc; 209 210 assert(diskp != NULL && fs != NULL); 211 while ((cgc = LIST_FIRST(&cglist)) != NULL) { 212 if (cgc->cgc_busy) 213 continue; 214 LIST_REMOVE(cgc, cgc_next); 215 //printf("%s: Canceled cg=%d\n", __func__, cgc->cgc_cg.cg_cgx); 216 free(cgc); 217 } 218 } 219 #endif 220 221 /* 222 * Open the given provider, load superblock. 223 */ 224 static void 225 opendisk(void) 226 { 227 if (diskp != NULL) 228 return; 229 diskp = &disk; 230 if (ufs_disk_fillout(diskp, devnam) == -1) { 231 err(1, "ufs_disk_fillout(%s) failed: %s", devnam, 232 diskp->d_error); 233 } 234 fs = &diskp->d_fs; 235 } 236 237 /* 238 * Mark file system as clean, write the super-block back, close the disk. 239 */ 240 static void 241 closedisk(void) 242 { 243 244 fs->fs_clean = 1; 245 if (sbwrite(diskp, 0) == -1) 246 err(1, "sbwrite(%s)", devnam); 247 if (ufs_disk_close(diskp) == -1) 248 err(1, "ufs_disk_close(%s)", devnam); 249 free(diskp); 250 diskp = NULL; 251 fs = NULL; 252 } 253 254 static void 255 blkfree(ufs2_daddr_t bno, long size) 256 { 257 struct cgchain *cgc; 258 struct cg *cgp; 259 ufs1_daddr_t fragno, cgbno; 260 int i, cg, blk, frags, bbase; 261 u_int8_t *blksfree; 262 263 cg = dtog(fs, bno); 264 cgc = getcg(cg); 265 dirtycg(cgc); 266 cgp = &cgc->cgc_cg; 267 cgbno = dtogd(fs, bno); 268 blksfree = cg_blksfree(cgp); 269 if (size == fs->fs_bsize) { 270 fragno = fragstoblks(fs, cgbno); 271 if (!ffs_isfreeblock(fs, blksfree, fragno)) 272 assert(!"blkfree: freeing free block"); 273 ffs_setblock(fs, blksfree, fragno); 274 ffs_clusteracct(fs, cgp, fragno, 1); 275 cgp->cg_cs.cs_nbfree++; 276 fs->fs_cstotal.cs_nbfree++; 277 fs->fs_cs(fs, cg).cs_nbfree++; 278 } else { 279 bbase = cgbno - fragnum(fs, cgbno); 280 /* 281 * decrement the counts associated with the old frags 282 */ 283 blk = blkmap(fs, blksfree, bbase); 284 ffs_fragacct(fs, blk, cgp->cg_frsum, -1); 285 /* 286 * deallocate the fragment 287 */ 288 frags = numfrags(fs, size); 289 for (i = 0; i < frags; i++) { 290 if (isset(blksfree, cgbno + i)) 291 assert(!"blkfree: freeing free frag"); 292 setbit(blksfree, cgbno + i); 293 } 294 cgp->cg_cs.cs_nffree += i; 295 fs->fs_cstotal.cs_nffree += i; 296 fs->fs_cs(fs, cg).cs_nffree += i; 297 /* 298 * add back in counts associated with the new frags 299 */ 300 blk = blkmap(fs, blksfree, bbase); 301 ffs_fragacct(fs, blk, cgp->cg_frsum, 1); 302 /* 303 * if a complete block has been reassembled, account for it 304 */ 305 fragno = fragstoblks(fs, bbase); 306 if (ffs_isblock(fs, blksfree, fragno)) { 307 cgp->cg_cs.cs_nffree -= fs->fs_frag; 308 fs->fs_cstotal.cs_nffree -= fs->fs_frag; 309 fs->fs_cs(fs, cg).cs_nffree -= fs->fs_frag; 310 ffs_clusteracct(fs, cgp, fragno, 1); 311 cgp->cg_cs.cs_nbfree++; 312 fs->fs_cstotal.cs_nbfree++; 313 fs->fs_cs(fs, cg).cs_nbfree++; 314 } 315 } 316 } 317 318 /* 319 * Recursively free all indirect blocks. 320 */ 321 static void 322 freeindir(ufs2_daddr_t blk, int level) 323 { 324 char sblks[MAXBSIZE]; 325 ufs2_daddr_t *blks; 326 int i; 327 328 if (bread(diskp, fsbtodb(fs, blk), (void *)&sblks, (size_t)fs->fs_bsize) == -1) 329 err(1, "bread: %s", diskp->d_error); 330 blks = (ufs2_daddr_t *)&sblks; 331 for (i = 0; i < NINDIR(fs); i++) { 332 if (blks[i] == 0) 333 break; 334 if (level == 0) 335 blkfree(blks[i], fs->fs_bsize); 336 else 337 freeindir(blks[i], level - 1); 338 } 339 blkfree(blk, fs->fs_bsize); 340 } 341 342 #define dblksize(fs, dino, lbn) \ 343 ((dino)->di_size >= smalllblktosize(fs, (lbn) + 1) \ 344 ? (fs)->fs_bsize \ 345 : fragroundup(fs, blkoff(fs, (dino)->di_size))) 346 347 /* 348 * Free all blocks associated with the given inode. 349 */ 350 static void 351 clear_inode(struct ufs2_dinode *dino) 352 { 353 ufs2_daddr_t bn; 354 int extblocks, i, level; 355 off_t osize; 356 long bsize; 357 358 extblocks = 0; 359 if (fs->fs_magic == FS_UFS2_MAGIC && dino->di_extsize > 0) 360 extblocks = btodb(fragroundup(fs, dino->di_extsize)); 361 /* deallocate external attributes blocks */ 362 if (extblocks > 0) { 363 osize = dino->di_extsize; 364 dino->di_blocks -= extblocks; 365 dino->di_extsize = 0; 366 for (i = 0; i < UFS_NXADDR; i++) { 367 if (dino->di_extb[i] == 0) 368 continue; 369 blkfree(dino->di_extb[i], sblksize(fs, osize, i)); 370 } 371 } 372 #define SINGLE 0 /* index of single indirect block */ 373 #define DOUBLE 1 /* index of double indirect block */ 374 #define TRIPLE 2 /* index of triple indirect block */ 375 /* deallocate indirect blocks */ 376 for (level = SINGLE; level <= TRIPLE; level++) { 377 if (dino->di_ib[level] == 0) 378 break; 379 freeindir(dino->di_ib[level], level); 380 } 381 /* deallocate direct blocks and fragments */ 382 for (i = 0; i < UFS_NDADDR; i++) { 383 bn = dino->di_db[i]; 384 if (bn == 0) 385 continue; 386 bsize = dblksize(fs, dino, i); 387 blkfree(bn, bsize); 388 } 389 } 390 391 void 392 gjournal_check(const char *filesys) 393 { 394 union dinodep dp; 395 struct cgchain *cgc; 396 struct cg *cgp; 397 uint8_t *inosused; 398 ino_t cino, ino; 399 int cg; 400 401 devnam = filesys; 402 opendisk(); 403 /* Are there any unreferenced inodes in this file system? */ 404 if (fs->fs_unrefs == 0) { 405 //printf("No unreferenced inodes.\n"); 406 closedisk(); 407 return; 408 } 409 410 for (cg = 0; cg < fs->fs_ncg; cg++) { 411 /* Show progress if requested. */ 412 if (got_siginfo) { 413 printf("%s: phase j: cyl group %d of %d (%d%%)\n", 414 cdevname, cg, fs->fs_ncg, cg * 100 / fs->fs_ncg); 415 got_siginfo = 0; 416 } 417 if (got_sigalarm) { 418 setproctitle("%s pj %d%%", cdevname, 419 cg * 100 / fs->fs_ncg); 420 got_sigalarm = 0; 421 } 422 cgc = getcg(cg); 423 cgp = &cgc->cgc_cg; 424 /* Are there any unreferenced inodes in this cylinder group? */ 425 if (cgp->cg_unrefs == 0) 426 continue; 427 //printf("Analizing cylinder group %d (count=%d)\n", cg, cgp->cg_unrefs); 428 /* 429 * We are going to modify this cylinder group, so we want it to 430 * be written back. 431 */ 432 dirtycg(cgc); 433 /* We don't want it to be freed in the meantime. */ 434 busycg(cgc); 435 inosused = cg_inosused(cgp); 436 /* 437 * Now go through the list of all inodes in this cylinder group 438 * to find unreferenced ones. 439 */ 440 for (cino = 0; cino < fs->fs_ipg; cino++) { 441 ino = fs->fs_ipg * cg + cino; 442 /* Unallocated? Skip it. */ 443 if (isclr(inosused, cino)) 444 continue; 445 if (getinode(diskp, &dp, ino) == -1) 446 err(1, "getinode (cg=%d ino=%ju) %s", 447 cg, (uintmax_t)ino, diskp->d_error); 448 /* Not a regular file nor directory? Skip it. */ 449 if (!S_ISREG(dp.dp2->di_mode) && 450 !S_ISDIR(dp.dp2->di_mode)) 451 continue; 452 /* Has reference(s)? Skip it. */ 453 if (dp.dp2->di_nlink > 0) 454 continue; 455 /* printf("Clearing inode=%d (size=%jd)\n", ino, 456 (intmax_t)dp.dp2->di_size); */ 457 /* Free inode's blocks. */ 458 clear_inode(dp.dp2); 459 /* Deallocate it. */ 460 clrbit(inosused, cino); 461 /* Update position of last used inode. */ 462 if (ino < cgp->cg_irotor) 463 cgp->cg_irotor = ino; 464 /* Update statistics. */ 465 cgp->cg_cs.cs_nifree++; 466 fs->fs_cs(fs, cg).cs_nifree++; 467 fs->fs_cstotal.cs_nifree++; 468 cgp->cg_unrefs--; 469 fs->fs_unrefs--; 470 /* If this is directory, update related statistics. */ 471 if (S_ISDIR(dp.dp2->di_mode)) { 472 cgp->cg_cs.cs_ndir--; 473 fs->fs_cs(fs, cg).cs_ndir--; 474 fs->fs_cstotal.cs_ndir--; 475 } 476 /* Zero-fill the inode. */ 477 *dp.dp2 = ufs2_zino; 478 /* Write the inode back. */ 479 if (putinode(diskp) == -1) 480 err(1, "putinode (cg=%d ino=%ju) %s", 481 cg, (uintmax_t)ino, diskp->d_error); 482 if (cgp->cg_unrefs == 0) { 483 //printf("No more unreferenced inodes in cg=%d.\n", cg); 484 break; 485 } 486 } 487 /* 488 * We don't need this cylinder group anymore, so feel free to 489 * free it if needed. 490 */ 491 unbusycg(cgc); 492 /* 493 * If there are no more unreferenced inodes, there is no need to 494 * check other cylinder groups. 495 */ 496 if (fs->fs_unrefs == 0) { 497 //printf("No more unreferenced inodes (cg=%d/%d).\n", cg, 498 // fs->fs_ncg); 499 break; 500 } 501 } 502 /* Write back modified cylinder groups. */ 503 putcgs(); 504 /* Write back updated statistics and super-block. */ 505 closedisk(); 506 } 507