pass1.c revision 1.43
1 /* $NetBSD: pass1.c,v 1.43 2015/09/01 06:12:04 dholland 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 "vnode.h" 52 #include "lfs_user.h" 53 54 #include "fsck.h" 55 #include "extern.h" 56 #include "fsutil.h" 57 58 SEGUSE *seg_table; 59 extern ulfs_daddr_t *din_table; 60 61 ulfs_daddr_t badblk; 62 static ulfs_daddr_t dupblk; 63 static int i_d_cmp(const void *, const void *); 64 65 struct ino_daddr { 66 ino_t ino; 67 ulfs_daddr_t daddr; 68 }; 69 70 static int 71 i_d_cmp(const void *va, const void *vb) 72 { 73 const struct ino_daddr *a, *b; 74 75 a = *((const struct ino_daddr *const *) va); 76 b = *((const struct ino_daddr *const *) vb); 77 78 if (a->daddr == b->daddr) { 79 return (a->ino - b->ino); 80 } 81 if (a->daddr > b->daddr) { 82 return 1; 83 } 84 return -1; 85 } 86 87 void 88 pass1(void) 89 { 90 ino_t inumber; 91 int i; 92 struct inodesc idesc; 93 union lfs_dinode *tinode; 94 IFILE *ifp; 95 struct ubuf *bp; 96 struct ino_daddr **dins; 97 98 /* 99 * Find all allocated blocks, initialize numdirs. 100 */ 101 memset(&idesc, 0, sizeof(struct inodesc)); 102 idesc.id_type = ADDR; 103 idesc.id_func = pass1check; 104 idesc.id_lblkno = 0; 105 inumber = 0; 106 n_files = n_blks = 0; 107 108 if (debug) 109 printf("creating sorted inode address table...\n"); 110 /* Sort by daddr */ 111 dins = ecalloc(maxino, sizeof(*dins)); 112 for (i = 0; i < maxino; i++) { 113 dins[i] = emalloc(sizeof(**dins)); 114 dins[i]->ino = i; 115 if (i == LFS_IFILE_INUM) 116 dins[i]->daddr = lfs_sb_getidaddr(fs); 117 else { 118 LFS_IENTRY(ifp, fs, i, bp); 119 dins[i]->daddr = lfs_if_getdaddr(fs, ifp); 120 brelse(bp, 0); 121 } 122 } 123 qsort(dins, maxino, sizeof(*dins), i_d_cmp); 124 125 /* find a value for numdirs, fill in din_table */ 126 if (debug) 127 printf("counting dirs...\n"); 128 numdirs = 0; 129 for (i = 0; i < maxino; i++) { 130 inumber = dins[i]->ino; 131 if (inumber == 0 || dins[i]->daddr == 0) 132 continue; 133 tinode = ginode(inumber); 134 if (tinode && (lfs_dino_getmode(fs, tinode) & LFS_IFMT) == LFS_IFDIR) 135 numdirs++; 136 } 137 138 /* from setup.c */ 139 inplast = 0; 140 listmax = numdirs + 10; 141 inpsort = ecalloc(listmax, sizeof(struct inoinfo *)); 142 inphead = ecalloc(numdirs, sizeof(struct inoinfo *)); 143 if (debug) 144 printf("counting blocks...\n"); 145 146 for (i = 0; i < maxino; i++) { 147 inumber = dins[i]->ino; 148 if (inumber == 0 || dins[i]->daddr == 0) { 149 statemap[inumber] = USTATE; 150 continue; 151 } 152 if (dins[i]->daddr != LFS_UNUSED_DADDR) { 153 checkinode(inumber, &idesc); 154 } else { 155 statemap[inumber] = USTATE; 156 } 157 free(dins[i]); 158 } 159 free(dins); 160 } 161 162 static int 163 nonzero_db(union lfs_dinode *dip) 164 { 165 unsigned i; 166 167 for (i=0; i<ULFS_NDADDR; i++) { 168 if (lfs_dino_getdb(fs, dip, i) != 0) { 169 return 1; 170 } 171 } 172 return 0; 173 } 174 175 static int 176 nonzero_ib(union lfs_dinode *dip) 177 { 178 unsigned i; 179 180 for (i=0; i<ULFS_NIADDR; i++) { 181 if (lfs_dino_getib(fs, dip, i) != 0) { 182 return 1; 183 } 184 } 185 return 0; 186 } 187 188 void 189 checkinode(ino_t inumber, struct inodesc * idesc) 190 { 191 union lfs_dinode *dp; 192 struct uvnode *vp; 193 struct zlncnt *zlnp; 194 struct ubuf *bp; 195 IFILE *ifp; 196 int64_t ndb, j; 197 mode_t mode; 198 199 vp = vget(fs, inumber); 200 if (vp) 201 dp = VTOD(vp); 202 else 203 dp = NULL; 204 205 if (dp == NULL) { 206 statemap[inumber] = USTATE; 207 return; 208 } 209 mode = lfs_dino_getmode(fs, dp) & LFS_IFMT; 210 211 /* XXX - LFS doesn't have this particular problem (?) */ 212 if (mode == 0) { 213 if (nonzero_db(dp) || nonzero_ib(dp) || 214 lfs_dino_getmode(fs, dp) || lfs_dino_getsize(fs, dp)) { 215 pwarn("mode=o%o, ifmt=o%o\n", lfs_dino_getmode(fs, dp), mode); 216 pfatal("PARTIALLY ALLOCATED INODE I=%llu", 217 (unsigned long long)inumber); 218 if (reply("CLEAR") == 1) { 219 vp = vget(fs, inumber); 220 clearinode(inumber); 221 vnode_destroy(vp); 222 } 223 } 224 statemap[inumber] = USTATE; 225 return; 226 } 227 lastino = inumber; 228 if (/* lfs_dino_getsize(fs, dp) < 0 || */ 229 lfs_dino_getsize(fs, dp) + lfs_sb_getbsize(fs) - 1 < lfs_dino_getsize(fs, dp)) { 230 if (debug) 231 printf("bad size %ju:", 232 (uintmax_t)lfs_dino_getsize(fs, dp)); 233 goto unknown; 234 } 235 if (!preen && mode == LFS_IFMT && reply("HOLD BAD BLOCK") == 1) { 236 vp = vget(fs, inumber); 237 dp = VTOD(vp); 238 lfs_dino_setsize(fs, dp, lfs_sb_getfsize(fs)); 239 lfs_dino_setmode(fs, dp, LFS_IFREG | 0600); 240 inodirty(VTOI(vp)); 241 } 242 ndb = howmany(lfs_dino_getsize(fs, dp), lfs_sb_getbsize(fs)); 243 if (ndb < 0) { 244 if (debug) 245 printf("bad size %ju ndb %jd:", 246 (uintmax_t)lfs_dino_getsize(fs, dp), (intmax_t)ndb); 247 goto unknown; 248 } 249 if (mode == LFS_IFBLK || mode == LFS_IFCHR) 250 ndb++; 251 if (mode == LFS_IFLNK) { 252 /* 253 * Fake ndb value so direct/indirect block checks below 254 * will detect any garbage after symlink string. 255 */ 256 if (lfs_dino_getsize(fs, dp) < lfs_sb_getmaxsymlinklen(fs) || 257 (lfs_sb_getmaxsymlinklen(fs) == 0 && lfs_dino_getblocks(fs, dp) == 0)) { 258 ndb = howmany(lfs_dino_getsize(fs, dp), sizeof(ulfs_daddr_t)); 259 if (ndb > ULFS_NDADDR) { 260 j = ndb - ULFS_NDADDR; 261 for (ndb = 1; j > 1; j--) 262 ndb *= LFS_NINDIR(fs); 263 ndb += ULFS_NDADDR; 264 } 265 } 266 } 267 for (j = ndb; j < ULFS_NDADDR; j++) 268 if (lfs_dino_getdb(fs, dp, j) != 0) { 269 if (debug) 270 printf("bad direct addr for size %ju lbn %jd: 0x%jx\n", 271 (uintmax_t)lfs_dino_getsize(fs, dp), 272 (intmax_t)j, 273 (intmax_t)lfs_dino_getdb(fs, dp, j)); 274 goto unknown; 275 } 276 for (j = 0, ndb -= ULFS_NDADDR; ndb > 0; j++) 277 ndb /= LFS_NINDIR(fs); 278 for (; j < ULFS_NIADDR; j++) 279 if (lfs_dino_getib(fs, dp, j) != 0) { 280 if (debug) 281 printf("bad indirect addr for size %ju # %jd: 0x%jx\n", 282 (uintmax_t)lfs_dino_getsize(fs, dp), 283 (intmax_t)j, 284 (intmax_t)lfs_dino_getib(fs, dp, j)); 285 goto unknown; 286 } 287 if (ftypeok(dp) == 0) 288 goto unknown; 289 n_files++; 290 lncntp[inumber] = lfs_dino_getnlink(fs, dp); 291 if (lfs_dino_getnlink(fs, dp) <= 0) { 292 zlnp = emalloc(sizeof *zlnp); 293 zlnp->zlncnt = inumber; 294 zlnp->next = zlnhead; 295 zlnhead = zlnp; 296 } 297 if (mode == LFS_IFDIR) { 298 if (lfs_dino_getsize(fs, dp) == 0) 299 statemap[inumber] = DCLEAR; 300 else 301 statemap[inumber] = DSTATE; 302 cacheino(dp, inumber); 303 } else 304 statemap[inumber] = FSTATE; 305 306 /* 307 * Check for an orphaned file. These happen when the cleaner has 308 * to rewrite blocks from a file whose directory operation (removal) 309 * is in progress. 310 */ 311 if (lfs_dino_getnlink(fs, dp) <= 0) { 312 LFS_IENTRY(ifp, fs, inumber, bp); 313 if (lfs_if_getnextfree(fs, ifp) == LFS_ORPHAN_NEXTFREE) { 314 statemap[inumber] = (mode == LFS_IFDIR ? DCLEAR : FCLEAR); 315 /* Add this to our list of orphans */ 316 zlnp = emalloc(sizeof *zlnp); 317 zlnp->zlncnt = inumber; 318 zlnp->next = orphead; 319 orphead = zlnp; 320 } 321 brelse(bp, 0); 322 } 323 324 /* XXX: why VTOD(vp) instead of dp here? */ 325 326 typemap[inumber] = LFS_IFTODT(mode); 327 badblk = dupblk = 0; 328 idesc->id_number = inumber; 329 (void) ckinode(VTOD(vp), idesc); 330 if (lfs_dino_getblocks(fs, dp) != idesc->id_entryno) { 331 pwarn("INCORRECT BLOCK COUNT I=%llu (%ju SHOULD BE %d)", 332 (unsigned long long)inumber, lfs_dino_getblocks(fs, dp), 333 idesc->id_entryno); 334 if (preen) 335 printf(" (CORRECTED)\n"); 336 else if (reply("CORRECT") == 0) 337 return; 338 lfs_dino_setblocks(fs, VTOD(vp), idesc->id_entryno); 339 inodirty(VTOI(vp)); 340 } 341 return; 342 unknown: 343 pfatal("UNKNOWN FILE TYPE I=%llu", (unsigned long long)inumber); 344 statemap[inumber] = FCLEAR; 345 if (reply("CLEAR") == 1) { 346 statemap[inumber] = USTATE; 347 vp = vget(fs, inumber); 348 clearinode(inumber); 349 vnode_destroy(vp); 350 } 351 } 352 353 int 354 pass1check(struct inodesc *idesc) 355 { 356 int res = KEEPON; 357 int anyout, ndblks; 358 daddr_t blkno = idesc->id_blkno; 359 struct dups *dlp; 360 struct dups *new; 361 362 if ((anyout = chkrange(blkno, idesc->id_numfrags)) != 0) { 363 blkerror(idesc->id_number, "BAD", blkno); 364 if (badblk++ >= MAXBAD) { 365 pwarn("EXCESSIVE BAD BLKS I=%llu", 366 (unsigned long long)idesc->id_number); 367 if (preen) 368 printf(" (SKIPPING)\n"); 369 else if (reply("CONTINUE") == 0) 370 err(EEXIT, "%s", ""); 371 return (STOP); 372 } 373 } else if (!testbmap(blkno)) { 374 seg_table[lfs_dtosn(fs, blkno)].su_nbytes += idesc->id_numfrags * lfs_sb_getfsize(fs); 375 } 376 for (ndblks = idesc->id_numfrags; ndblks > 0; blkno++, ndblks--) { 377 if (anyout && chkrange(blkno, 1)) { 378 res = SKIP; 379 } else if (!testbmap(blkno)) { 380 n_blks++; 381 #ifndef VERBOSE_BLOCKMAP 382 setbmap(blkno); 383 #else 384 setbmap(blkno, idesc->id_number); 385 #endif 386 } else { 387 blkerror(idesc->id_number, "DUP", blkno); 388 #ifdef VERBOSE_BLOCKMAP 389 pwarn("(lbn %lld: Holder is %lld)\n", 390 (long long)idesc->id_lblkno, 391 (long long)testbmap(blkno)); 392 #endif 393 if (dupblk++ >= MAXDUP) { 394 pwarn("EXCESSIVE DUP BLKS I=%llu", 395 (unsigned long long)idesc->id_number); 396 if (preen) 397 printf(" (SKIPPING)\n"); 398 else if (reply("CONTINUE") == 0) 399 err(EEXIT, "%s", ""); 400 return (STOP); 401 } 402 new = emalloc(sizeof(struct dups)); 403 new->dup = blkno; 404 if (muldup == 0) { 405 duplist = muldup = new; 406 new->next = 0; 407 } else { 408 new->next = muldup->next; 409 muldup->next = new; 410 } 411 for (dlp = duplist; dlp != muldup; dlp = dlp->next) 412 if (dlp->dup == blkno) 413 break; 414 if (dlp == muldup && dlp->dup != blkno) 415 muldup = new; 416 } 417 /* 418 * count the number of blocks found in id_entryno 419 */ 420 idesc->id_entryno++; 421 } 422 return (res); 423 } 424
Indexes created Sat Oct 18 17:09:52 GMT 2025