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
i_d_cmp(const void * va,const void * vb)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
pass1(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
nonzero_db(union lfs_dinode * dip)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
nonzero_ib(union lfs_dinode * dip)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
checkinode(ino_t inumber,struct inodesc * idesc)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
pass1check(struct inodesc * idesc)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