pass1.c revision 1.27
1 /* $NetBSD: pass1.c,v 1.27 2006/10/16 03:21:34 christos 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 #include <ufs/ufs/inode.h> 38 #include <ufs/ufs/dir.h> 39 #define vnode uvnode 40 #include <ufs/lfs/lfs.h> 41 #undef vnode 42 43 #include <err.h> 44 #include <stdio.h> 45 #include <stdlib.h> 46 #include <string.h> 47 48 #include <signal.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 ufs_daddr_t *din_table; 60 61 ufs_daddr_t badblk; 62 static ufs_daddr_t dupblk; 63 static int i_d_cmp(const void *, const void *); 64 65 struct ino_daddr { 66 ino_t ino; 67 ufs_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 struct ufs1_dinode *tinode; 94 struct 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 = (struct ino_daddr **) malloc(maxino * sizeof(*dins)); 112 if (dins == NULL) 113 err(1, NULL); 114 for (i = 0; i < maxino; i++) { 115 dins[i] = malloc(sizeof(**dins)); 116 if (dins[i] == NULL) 117 err(1, NULL); 118 dins[i]->ino = i; 119 if (i == fs->lfs_ifile) 120 dins[i]->daddr = fs->lfs_idaddr; 121 else { 122 LFS_IENTRY(ifp, fs, i, bp); 123 dins[i]->daddr = ifp->if_daddr; 124 brelse(bp); 125 } 126 } 127 qsort(dins, maxino, sizeof(*dins), i_d_cmp); 128 129 /* find a value for numdirs, fill in din_table */ 130 if (debug) 131 printf("counting dirs...\n"); 132 numdirs = 0; 133 for (i = 0; i < maxino; i++) { 134 inumber = dins[i]->ino; 135 if (inumber == 0 || dins[i]->daddr == 0) 136 continue; 137 tinode = ginode(inumber); 138 if (tinode && (tinode->di_mode & IFMT) == IFDIR) 139 numdirs++; 140 } 141 142 /* from setup.c */ 143 inplast = 0; 144 listmax = numdirs + 10; 145 inpsort = (struct inoinfo **) calloc((unsigned) listmax, 146 sizeof(struct inoinfo *)); 147 inphead = (struct inoinfo **) calloc((unsigned) numdirs, 148 sizeof(struct inoinfo *)); 149 if (inpsort == NULL || inphead == NULL) { 150 printf("cannot alloc %lu bytes for inphead\n", 151 (unsigned long) numdirs * sizeof(struct inoinfo *)); 152 exit(1); 153 } 154 if (debug) 155 printf("counting blocks...\n"); 156 157 for (i = 0; i < maxino; i++) { 158 inumber = dins[i]->ino; 159 if (inumber == 0 || dins[i]->daddr == 0) { 160 statemap[inumber] = USTATE; 161 continue; 162 } 163 if (dins[i]->daddr != LFS_UNUSED_DADDR) { 164 checkinode(inumber, &idesc); 165 } else { 166 statemap[inumber] = USTATE; 167 } 168 free(dins[i]); 169 } 170 free(dins); 171 } 172 173 void 174 checkinode(ino_t inumber, struct inodesc * idesc) 175 { 176 struct ufs1_dinode *dp; 177 struct uvnode *vp; 178 struct zlncnt *zlnp; 179 struct ubuf *bp; 180 IFILE *ifp; 181 int ndb, j; 182 mode_t mode; 183 184 vp = vget(fs, inumber); 185 if (vp) 186 dp = VTOD(vp); 187 else 188 dp = NULL; 189 190 if (dp == NULL) { 191 statemap[inumber] = USTATE; 192 return; 193 } 194 mode = dp->di_mode & IFMT; 195 196 /* XXX - LFS doesn't have this particular problem (?) */ 197 if (mode == 0) { 198 if (memcmp(dp->di_db, zino.di_db, NDADDR * sizeof(ufs_daddr_t)) || 199 memcmp(dp->di_ib, zino.di_ib, NIADDR * sizeof(ufs_daddr_t)) || 200 dp->di_mode || dp->di_size) { 201 pwarn("mode=o%o, ifmt=o%o\n", dp->di_mode, mode); 202 pfatal("PARTIALLY ALLOCATED INODE I=%llu", 203 (unsigned long long)inumber); 204 if (reply("CLEAR") == 1) { 205 vp = vget(fs, inumber); 206 clearinode(inumber); 207 vnode_destroy(vp); 208 } 209 } 210 statemap[inumber] = USTATE; 211 return; 212 } 213 lastino = inumber; 214 if (/* dp->di_size < 0 || */ 215 dp->di_size + fs->lfs_bsize - 1 < dp->di_size) { 216 if (debug) 217 printf("bad size %llu:", 218 (unsigned long long) dp->di_size); 219 goto unknown; 220 } 221 if (!preen && mode == IFMT && reply("HOLD BAD BLOCK") == 1) { 222 vp = vget(fs, inumber); 223 dp = VTOD(vp); 224 dp->di_size = fs->lfs_fsize; 225 dp->di_mode = IFREG | 0600; 226 inodirty(VTOI(vp)); 227 } 228 ndb = howmany(dp->di_size, fs->lfs_bsize); 229 if (ndb < 0) { 230 if (debug) 231 printf("bad size %llu ndb %d:", 232 (unsigned long long) dp->di_size, ndb); 233 goto unknown; 234 } 235 if (mode == IFBLK || mode == IFCHR) 236 ndb++; 237 if (mode == IFLNK) { 238 /* 239 * Fake ndb value so direct/indirect block checks below 240 * will detect any garbage after symlink string. 241 */ 242 if (dp->di_size < fs->lfs_maxsymlinklen || 243 (fs->lfs_maxsymlinklen == 0 && dp->di_blocks == 0)) { 244 ndb = howmany(dp->di_size, sizeof(ufs_daddr_t)); 245 if (ndb > NDADDR) { 246 j = ndb - NDADDR; 247 for (ndb = 1; j > 1; j--) 248 ndb *= NINDIR(fs); 249 ndb += NDADDR; 250 } 251 } 252 } 253 for (j = ndb; j < NDADDR; j++) 254 if (dp->di_db[j] != 0) { 255 if (debug) 256 printf("bad direct addr for size %lld lbn %d: 0x%x\n", 257 (long long)dp->di_size, j, (unsigned)dp->di_db[j]); 258 goto unknown; 259 } 260 for (j = 0, ndb -= NDADDR; ndb > 0; j++) 261 ndb /= NINDIR(fs); 262 for (; j < NIADDR; j++) 263 if (dp->di_ib[j] != 0) { 264 if (debug) 265 printf("bad indirect addr for size %lld # %d: 0x%x\n", 266 (long long)dp->di_size, j, (unsigned)dp->di_ib[j]); 267 goto unknown; 268 } 269 if (ftypeok(dp) == 0) 270 goto unknown; 271 n_files++; 272 lncntp[inumber] = dp->di_nlink; 273 if (dp->di_nlink <= 0) { 274 zlnp = (struct zlncnt *) malloc(sizeof *zlnp); 275 if (zlnp == NULL) { 276 pfatal("LINK COUNT TABLE OVERFLOW"); 277 if (reply("CONTINUE") == 0) 278 err(8, "%s", ""); 279 } else { 280 zlnp->zlncnt = inumber; 281 zlnp->next = zlnhead; 282 zlnhead = zlnp; 283 } 284 } 285 if (mode == IFDIR) { 286 if (dp->di_size == 0) 287 statemap[inumber] = DCLEAR; 288 else 289 statemap[inumber] = DSTATE; 290 cacheino(dp, inumber); 291 } else 292 statemap[inumber] = FSTATE; 293 294 /* 295 * Check for an orphaned file. These happen when the cleaner has 296 * to rewrite blocks from a file whose directory operation (removal) 297 * is in progress. 298 */ 299 if (dp->di_nlink <= 0) { 300 LFS_IENTRY(ifp, fs, inumber, bp); 301 if (ifp->if_nextfree == LFS_ORPHAN_NEXTFREE) { 302 statemap[inumber] = (mode == IFDIR ? DCLEAR : FCLEAR); 303 /* Add this to our list of orphans */ 304 zlnp = (struct zlncnt *) malloc(sizeof *zlnp); 305 if (zlnp == NULL) { 306 pfatal("LINK COUNT TABLE OVERFLOW"); 307 if (reply("CONTINUE") == 0) 308 err(8, "%s", ""); 309 } else { 310 zlnp->zlncnt = inumber; 311 zlnp->next = orphead; 312 orphead = zlnp; 313 } 314 } 315 brelse(bp); 316 } 317 318 typemap[inumber] = IFTODT(mode); 319 badblk = dupblk = 0; 320 idesc->id_number = inumber; 321 (void) ckinode(VTOD(vp), idesc); 322 if (dp->di_blocks != idesc->id_entryno) { 323 pwarn("INCORRECT BLOCK COUNT I=%llu (%d SHOULD BE %d)", 324 (unsigned long long)inumber, dp->di_blocks, 325 idesc->id_entryno); 326 if (preen) 327 printf(" (CORRECTED)\n"); 328 else if (reply("CORRECT") == 0) 329 return; 330 VTOI(vp)->i_ffs1_blocks = idesc->id_entryno; 331 inodirty(VTOI(vp)); 332 } 333 return; 334 unknown: 335 pfatal("UNKNOWN FILE TYPE I=%llu", (unsigned long long)inumber); 336 statemap[inumber] = FCLEAR; 337 if (reply("CLEAR") == 1) { 338 statemap[inumber] = USTATE; 339 vp = vget(fs, inumber); 340 clearinode(inumber); 341 vnode_destroy(vp); 342 } 343 } 344 345 int 346 pass1check(struct inodesc *idesc) 347 { 348 int res = KEEPON; 349 int anyout, ndblks; 350 daddr_t blkno = idesc->id_blkno; 351 struct dups *dlp; 352 struct dups *new; 353 354 if ((anyout = chkrange(blkno, fragstofsb(fs, idesc->id_numfrags))) != 0) { 355 blkerror(idesc->id_number, "BAD", blkno); 356 if (badblk++ >= MAXBAD) { 357 pwarn("EXCESSIVE BAD BLKS I=%llu", 358 (unsigned long long)idesc->id_number); 359 if (preen) 360 printf(" (SKIPPING)\n"); 361 else if (reply("CONTINUE") == 0) 362 err(8, "%s", ""); 363 return (STOP); 364 } 365 } else if (!testbmap(blkno)) { 366 seg_table[dtosn(fs, blkno)].su_nbytes += idesc->id_numfrags * fs->lfs_fsize; 367 } 368 for (ndblks = fragstofsb(fs, idesc->id_numfrags); ndblks > 0; blkno++, ndblks--) { 369 if (anyout && chkrange(blkno, 1)) { 370 res = SKIP; 371 } else if (!testbmap(blkno)) { 372 n_blks++; 373 #ifndef VERBOSE_BLOCKMAP 374 setbmap(blkno); 375 #else 376 setbmap(blkno, idesc->id_number); 377 #endif 378 } else { 379 blkerror(idesc->id_number, "DUP", blkno); 380 #ifdef VERBOSE_BLOCKMAP 381 pwarn("(lbn %lld: Holder is %lld)\n", 382 (long long)idesc->id_lblkno, 383 (long long)testbmap(blkno)); 384 #endif 385 if (dupblk++ >= MAXDUP) { 386 pwarn("EXCESSIVE DUP BLKS I=%llu", 387 (unsigned long long)idesc->id_number); 388 if (preen) 389 printf(" (SKIPPING)\n"); 390 else if (reply("CONTINUE") == 0) 391 err(8, "%s", ""); 392 return (STOP); 393 } 394 new = (struct dups *) malloc(sizeof(struct dups)); 395 if (new == NULL) { 396 pfatal("DUP TABLE OVERFLOW."); 397 if (reply("CONTINUE") == 0) 398 err(8, "%s", ""); 399 return (STOP); 400 } 401 new->dup = blkno; 402 if (muldup == 0) { 403 duplist = muldup = new; 404 new->next = 0; 405 } else { 406 new->next = muldup->next; 407 muldup->next = new; 408 } 409 for (dlp = duplist; dlp != muldup; dlp = dlp->next) 410 if (dlp->dup == blkno) 411 break; 412 if (dlp == muldup && dlp->dup != blkno) 413 muldup = new; 414 } 415 /* 416 * count the number of blocks found in id_entryno 417 */ 418 idesc->id_entryno++; 419 } 420 return (res); 421 } 422
Indexes created Mon Oct 20 16:09:52 GMT 2025