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