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