1 /* $NetBSD: pass1.c,v 1.47 2020/04/03 19:36:33 joerg Exp $ */ 2 3 /* 4 * Copyright (c) 1980, 1986, 1993 5 * The Regents of the University of California. 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 * 3. Neither the name of the University nor the names of its contributors 16 * may be used to endorse or promote products derived from this software 17 * without specific prior written permission. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 22 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 23 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 24 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 25 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 27 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 28 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 29 * SUCH DAMAGE. 30 */ 31 32 #include <sys/param.h> 33 #include <sys/time.h> 34 #include <sys/mount.h> 35 #include <sys/buf.h> 36 37 #define vnode uvnode 38 #include <ufs/lfs/lfs.h> 39 #include <ufs/lfs/lfs_accessors.h> 40 #include <ufs/lfs/lfs_inode.h> 41 #undef vnode 42 43 #include <err.h> 44 #include <stdio.h> 45 #include <stdlib.h> 46 #include <string.h> 47 #include <signal.h> 48 #include <util.h> 49 50 #include "bufcache.h" 51 #include "lfs_user.h" 52 53 #include "fsck.h" 54 #include "extern.h" 55 #include "fsutil.h" 56 57 blkcnt_t badblkcount; 58 static blkcnt_t dupblkcount; 59 static int i_d_cmp(const void *, const void *); 60 61 struct ino_daddr { 62 ino_t ino; 63 daddr_t daddr; 64 }; 65 66 static int 67 i_d_cmp(const void *va, const void *vb) 68 { 69 const struct ino_daddr *a, *b; 70 71 a = *((const struct ino_daddr *const *) va); 72 b = *((const struct ino_daddr *const *) vb); 73 74 if (a->daddr == b->daddr) { 75 return (a->ino - b->ino); 76 } 77 if (a->daddr > b->daddr) { 78 return 1; 79 } 80 return -1; 81 } 82 83 void 84 pass1(void) 85 { 86 ino_t inumber; 87 int i; 88 struct inodesc idesc; 89 union lfs_dinode *tinode; 90 IFILE *ifp; 91 struct ubuf *bp; 92 struct ino_daddr **dins; 93 94 /* 95 * Find all allocated blocks, initialize numdirs. 96 */ 97 memset(&idesc, 0, sizeof(struct inodesc)); 98 idesc.id_type = ADDR; 99 idesc.id_func = pass1check; 100 idesc.id_lblkno = 0; 101 inumber = 0; 102 n_files = n_blks = 0; 103 104 if (debug) 105 printf("creating sorted inode address table...\n"); 106 /* Sort by daddr */ 107 dins = ecalloc(maxino, sizeof(*dins)); 108 for (i = 0; i < maxino; i++) { 109 dins[i] = emalloc(sizeof(**dins)); 110 dins[i]->ino = i; 111 if (i == LFS_IFILE_INUM) 112 dins[i]->daddr = lfs_sb_getidaddr(fs); 113 else { 114 LFS_IENTRY(ifp, fs, i, bp); 115 dins[i]->daddr = lfs_if_getdaddr(fs, ifp); 116 brelse(bp, 0); 117 } 118 } 119 qsort(dins, maxino, sizeof(*dins), i_d_cmp); 120 121 /* find a value for numdirs, fill in din_table */ 122 if (debug) 123 printf("counting dirs...\n"); 124 numdirs = 0; 125 for (i = 0; i < maxino; i++) { 126 inumber = dins[i]->ino; 127 if (inumber == 0 || dins[i]->daddr == 0) 128 continue; 129 tinode = ginode(inumber); 130 if (tinode && (lfs_dino_getmode(fs, tinode) & LFS_IFMT) == LFS_IFDIR) 131 numdirs++; 132 } 133 134 /* from setup.c */ 135 inplast = 0; 136 listmax = numdirs + 10; 137 inpsort = ecalloc(listmax, sizeof(struct inoinfo *)); 138 inphead = ecalloc(numdirs, sizeof(struct inoinfo *)); 139 if (debug) 140 printf("counting blocks...\n"); 141 142 for (i = 0; i < maxino; i++) { 143 inumber = dins[i]->ino; 144 if (inumber == 0 || dins[i]->daddr == 0) { 145 statemap[inumber] = USTATE; 146 continue; 147 } 148 if (dins[i]->daddr != LFS_UNUSED_DADDR) { 149 checkinode(inumber, &idesc); 150 } else { 151 statemap[inumber] = USTATE; 152 } 153 free(dins[i]); 154 } 155 free(dins); 156 } 157 158 static int 159 nonzero_db(union lfs_dinode *dip) 160 { 161 unsigned i; 162 163 for (i=0; i<ULFS_NDADDR; i++) { 164 if (lfs_dino_getdb(fs, dip, i) != 0) { 165 return 1; 166 } 167 } 168 return 0; 169 } 170 171 static int 172 nonzero_ib(union lfs_dinode *dip) 173 { 174 unsigned i; 175 176 for (i=0; i<ULFS_NIADDR; i++) { 177 if (lfs_dino_getib(fs, dip, i) != 0) { 178 return 1; 179 } 180 } 181 return 0; 182 } 183 184 void 185 checkinode(ino_t inumber, struct inodesc * idesc) 186 { 187 union lfs_dinode *dp; 188 struct uvnode *vp; 189 struct zlncnt *zlnp; 190 struct ubuf *bp; 191 IFILE *ifp; 192 int64_t ndb, j; 193 mode_t mode; 194 195 vp = vget(fs, inumber); 196 if (vp) 197 dp = VTOD(vp); 198 else 199 dp = NULL; 200 201 if (dp == NULL) { 202 statemap[inumber] = USTATE; 203 return; 204 } 205 mode = lfs_dino_getmode(fs, dp) & LFS_IFMT; 206 207 /* XXX - LFS doesn't have this particular problem (?) */ 208 if (mode == 0) { 209 if (nonzero_db(dp) || nonzero_ib(dp) || 210 lfs_dino_getmode(fs, dp) || lfs_dino_getsize(fs, dp)) { 211 pwarn("mode=o%o, ifmt=o%o\n", lfs_dino_getmode(fs, dp), mode); 212 pfatal("PARTIALLY ALLOCATED INODE I=%llu", 213 (unsigned long long)inumber); 214 if (reply("CLEAR") == 1) { 215 vp = vget(fs, inumber); 216 clearinode(inumber); 217 vnode_destroy(vp); 218 } 219 } 220 statemap[inumber] = USTATE; 221 return; 222 } 223 lastino = inumber; 224 if (/* lfs_dino_getsize(fs, dp) < 0 || */ 225 lfs_dino_getsize(fs, dp) + lfs_sb_getbsize(fs) - 1 < lfs_dino_getsize(fs, dp)) { 226 if (debug) 227 printf("bad size %ju:", 228 (uintmax_t)lfs_dino_getsize(fs, dp)); 229 goto unknown; 230 } 231 if (!preen && mode == LFS_IFMT && reply("HOLD BAD BLOCK") == 1) { 232 vp = vget(fs, inumber); 233 dp = VTOD(vp); 234 lfs_dino_setsize(fs, dp, lfs_sb_getfsize(fs)); 235 lfs_dino_setmode(fs, dp, LFS_IFREG | 0600); 236 inodirty(VTOI(vp)); 237 } 238 ndb = howmany(lfs_dino_getsize(fs, dp), lfs_sb_getbsize(fs)); 239 if (ndb < 0) { 240 if (debug) 241 printf("bad size %ju ndb %jd:", 242 (uintmax_t)lfs_dino_getsize(fs, dp), (intmax_t)ndb); 243 goto unknown; 244 } 245 if (mode == LFS_IFBLK || mode == LFS_IFCHR) 246 ndb++; 247 if (mode == LFS_IFLNK) { 248 /* 249 * Fake ndb value so direct/indirect block checks below 250 * will detect any garbage after symlink string. 251 */ 252 if (lfs_dino_getsize(fs, dp) < lfs_sb_getmaxsymlinklen(fs) || 253 (lfs_sb_getmaxsymlinklen(fs) == 0 && lfs_dino_getblocks(fs, dp) == 0)) { 254 ndb = howmany(lfs_dino_getsize(fs, dp), LFS_BLKPTRSIZE(fs)); 255 if (ndb > ULFS_NDADDR) { 256 j = ndb - ULFS_NDADDR; 257 for (ndb = 1; j > 1; j--) 258 ndb *= LFS_NINDIR(fs); 259 ndb += ULFS_NDADDR; 260 } 261 } 262 } 263 for (j = ndb; j < ULFS_NDADDR; j++) 264 if (lfs_dino_getdb(fs, dp, j) != 0) { 265 if (debug) 266 printf("bad direct addr for size %ju lbn %jd: 0x%jx\n", 267 (uintmax_t)lfs_dino_getsize(fs, dp), 268 (intmax_t)j, 269 (intmax_t)lfs_dino_getdb(fs, dp, j)); 270 goto unknown; 271 } 272 for (j = 0, ndb -= ULFS_NDADDR; ndb > 0; j++) 273 ndb /= LFS_NINDIR(fs); 274 for (; j < ULFS_NIADDR; j++) 275 if (lfs_dino_getib(fs, dp, j) != 0) { 276 if (debug) 277 printf("bad indirect addr for size %ju # %jd: 0x%jx\n", 278 (uintmax_t)lfs_dino_getsize(fs, dp), 279 (intmax_t)j, 280 (intmax_t)lfs_dino_getib(fs, dp, j)); 281 goto unknown; 282 } 283 if (ftypeok(dp) == 0) 284 goto unknown; 285 n_files++; 286 lncntp[inumber] = lfs_dino_getnlink(fs, dp); 287 if (lfs_dino_getnlink(fs, dp) <= 0) { 288 zlnp = emalloc(sizeof *zlnp); 289 zlnp->zlncnt = inumber; 290 zlnp->next = zlnhead; 291 zlnhead = zlnp; 292 } 293 if (mode == LFS_IFDIR) { 294 if (lfs_dino_getsize(fs, dp) == 0) 295 statemap[inumber] = DCLEAR; 296 else 297 statemap[inumber] = DSTATE; 298 cacheino(dp, inumber); 299 } else 300 statemap[inumber] = FSTATE; 301 302 /* 303 * Check for an orphaned file. These happen when the cleaner has 304 * to rewrite blocks from a file whose directory operation (removal) 305 * is in progress. 306 */ 307 if (lfs_dino_getnlink(fs, dp) <= 0) { 308 LFS_IENTRY(ifp, fs, inumber, bp); 309 if (lfs_if_getnextfree(fs, ifp) == LFS_ORPHAN_NEXTFREE(fs)) { 310 statemap[inumber] = (mode == LFS_IFDIR ? DCLEAR : FCLEAR); 311 /* Add this to our list of orphans */ 312 zlnp = emalloc(sizeof *zlnp); 313 zlnp->zlncnt = inumber; 314 zlnp->next = orphead; 315 orphead = zlnp; 316 } 317 brelse(bp, 0); 318 } 319 320 /* XXX: why VTOD(vp) instead of dp here? */ 321 322 typemap[inumber] = LFS_IFTODT(mode); 323 badblkcount = dupblkcount = 0; 324 idesc->id_number = inumber; 325 (void) ckinode(VTOD(vp), idesc); 326 if (lfs_dino_getblocks(fs, dp) != idesc->id_entryno) { 327 pwarn("INCORRECT BLOCK COUNT I=%llu (%ju SHOULD BE %lld)", 328 (unsigned long long)inumber, lfs_dino_getblocks(fs, dp), 329 idesc->id_entryno); 330 if (preen) 331 printf(" (CORRECTED)\n"); 332 else if (reply("CORRECT") == 0) 333 return; 334 lfs_dino_setblocks(fs, VTOD(vp), idesc->id_entryno); 335 inodirty(VTOI(vp)); 336 } 337 return; 338 unknown: 339 pfatal("UNKNOWN FILE TYPE I=%llu", (unsigned long long)inumber); 340 statemap[inumber] = FCLEAR; 341 if (reply("CLEAR") == 1) { 342 statemap[inumber] = USTATE; 343 vp = vget(fs, inumber); 344 clearinode(inumber); 345 vnode_destroy(vp); 346 } 347 } 348 349 int 350 pass1check(struct inodesc *idesc) 351 { 352 int res = KEEPON; 353 int anyout, ndblks; 354 daddr_t blkno = idesc->id_blkno; 355 struct dups *dlp; 356 struct dups *new; 357 358 if ((anyout = chkrange(blkno, idesc->id_numfrags)) != 0) { 359 blkerror(idesc->id_number, "BAD", blkno); 360 if (badblkcount++ >= MAXBAD) { 361 pwarn("EXCESSIVE BAD BLKS I=%llu", 362 (unsigned long long)idesc->id_number); 363 if (preen) 364 printf(" (SKIPPING)\n"); 365 else if (reply("CONTINUE") == 0) 366 err(EEXIT, "%s", ""); 367 return (STOP); 368 } 369 } else if (!testbmap(blkno)) { 370 seg_table[lfs_dtosn(fs, blkno)].su_nbytes += idesc->id_numfrags * lfs_sb_getfsize(fs); 371 } 372 for (ndblks = idesc->id_numfrags; ndblks > 0; blkno++, ndblks--) { 373 if (anyout && chkrange(blkno, 1)) { 374 res = SKIP; 375 } else if (!testbmap(blkno)) { 376 n_blks++; 377 #ifndef VERBOSE_BLOCKMAP 378 setbmap(blkno); 379 #else 380 setbmap(blkno, idesc->id_number); 381 #endif 382 } else { 383 blkerror(idesc->id_number, "DUP", blkno); 384 #ifdef VERBOSE_BLOCKMAP 385 pwarn("(lbn %lld: Holder is %lld)\n", 386 (long long)idesc->id_lblkno, 387 (long long)testbmap(blkno)); 388 #endif 389 if (dupblkcount++ >= MAXDUP) { 390 pwarn("EXCESSIVE DUP BLKS I=%llu", 391 (unsigned long long)idesc->id_number); 392 if (preen) 393 printf(" (SKIPPING)\n"); 394 else if (reply("CONTINUE") == 0) 395 err(EEXIT, "%s", ""); 396 return (STOP); 397 } 398 new = emalloc(sizeof(struct dups)); 399 new->dup = blkno; 400 if (muldup == 0) { 401 duplist = muldup = new; 402 new->next = 0; 403 } else { 404 new->next = muldup->next; 405 muldup->next = new; 406 } 407 for (dlp = duplist; dlp != muldup; dlp = dlp->next) 408 if (dlp->dup == blkno) 409 break; 410 if (dlp == muldup && dlp->dup != blkno) 411 muldup = new; 412 } 413 /* 414 * count the number of blocks found in id_entryno 415 */ 416 idesc->id_entryno++; 417 } 418 return (res); 419 } 420
Indexes created Sat Sep 20 22:09:52 GMT 2025