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