1 /* $NetBSD: pass2.c,v 1.15 2009/10/19 18:41:08 bouyer 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 /*
33 * Copyright (c) 1997 Manuel Bouyer.
34 *
35 * Redistribution and use in source and binary forms, with or without
36 * modification, are permitted provided that the following conditions
37 * are met:
38 * 1. Redistributions of source code must retain the above copyright
39 * notice, this list of conditions and the following disclaimer.
40 * 2. Redistributions in binary form must reproduce the above copyright
41 * notice, this list of conditions and the following disclaimer in the
42 * documentation and/or other materials provided with the distribution.
43 *
44 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
45 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
46 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
47 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
48 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
49 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
50 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
51 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
52 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
53 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
54 */
55
56 #include <sys/cdefs.h>
57 #ifndef lint
58 #if 0
59 static char sccsid[] = "@(#)pass2.c 8.6 (Berkeley) 10/27/94";
60 #else
61 __RCSID("$NetBSD: pass2.c,v 1.15 2009/10/19 18:41:08 bouyer Exp $");
62 #endif
63 #endif /* not lint */
64
65 #include <sys/param.h>
66 #include <sys/time.h>
67 #include <ufs/ext2fs/ext2fs_dinode.h>
68 #include <ufs/ext2fs/ext2fs_dir.h>
69 #include <ufs/ext2fs/ext2fs.h>
70
71 #include <ufs/ufs/dinode.h> /* for IFMT & friends */
72
73 #include <stdio.h>
74 #include <stdlib.h>
75 #include <string.h>
76
77 #include "fsck.h"
78 #include "fsutil.h"
79 #include "extern.h"
80 #include "exitvalues.h"
81
82 #define MINDIRSIZE (sizeof (struct ext2fs_dirtemplate))
83
84 static int pass2check(struct inodesc *);
85 static int blksort(const void *, const void *);
86
87 void
pass2(void)88 pass2(void)
89 {
90 struct ext2fs_dinode *dp;
91 struct inoinfo **inpp, *inp;
92 struct inoinfo **inpend;
93 struct inodesc curino;
94 struct ext2fs_dinode dino;
95 char pathbuf[MAXPATHLEN + 1];
96
97 switch (statemap[EXT2_ROOTINO]) {
98
99 case USTATE:
100 pfatal("ROOT INODE UNALLOCATED");
101 if (reply("ALLOCATE") == 0)
102 exit(FSCK_EXIT_CHECK_FAILED);
103 if (allocdir(EXT2_ROOTINO, EXT2_ROOTINO, 0755) != EXT2_ROOTINO)
104 errexit("CANNOT ALLOCATE ROOT INODE");
105 break;
106
107 case DCLEAR:
108 pfatal("DUPS/BAD IN ROOT INODE");
109 if (reply("REALLOCATE")) {
110 freeino(EXT2_ROOTINO);
111 if (allocdir(EXT2_ROOTINO, EXT2_ROOTINO, 0755) != EXT2_ROOTINO)
112 errexit("CANNOT ALLOCATE ROOT INODE");
113 break;
114 }
115 if (reply("CONTINUE") == 0)
116 exit(FSCK_EXIT_CHECK_FAILED);
117 break;
118
119 case FSTATE:
120 case FCLEAR:
121 pfatal("ROOT INODE NOT DIRECTORY");
122 if (reply("REALLOCATE")) {
123 freeino(EXT2_ROOTINO);
124 if (allocdir(EXT2_ROOTINO, EXT2_ROOTINO, 0755) != EXT2_ROOTINO)
125 errexit("CANNOT ALLOCATE ROOT INODE");
126 break;
127 }
128 if (reply("FIX") == 0)
129 exit(FSCK_EXIT_CHECK_FAILED);
130 dp = ginode(EXT2_ROOTINO);
131 dp->e2di_mode = h2fs16((fs2h16(dp->e2di_mode) & ~IFMT) | IFDIR);
132 inodirty();
133 break;
134
135 case DSTATE:
136 break;
137
138 default:
139 errexit("BAD STATE %d FOR ROOT INODE", statemap[EXT2_ROOTINO]);
140 }
141
142 /*
143 * Sort the directory list into disk block order.
144 */
145 qsort((char *)inpsort, (size_t)inplast, sizeof *inpsort, blksort);
146 /*
147 * Check the integrity of each directory.
148 */
149 memset(&curino, 0, sizeof(struct inodesc));
150 curino.id_type = DATA;
151 curino.id_func = pass2check;
152 inpend = &inpsort[inplast];
153 for (inpp = inpsort; inpp < inpend; inpp++) {
154 inp = *inpp;
155 if (inp->i_isize == 0)
156 continue;
157 if (inp->i_isize < MINDIRSIZE) {
158 direrror(inp->i_number, "DIRECTORY TOO SHORT");
159 inp->i_isize = roundup(MINDIRSIZE, sblock.e2fs_bsize);
160 if (reply("FIX") == 1) {
161 dp = ginode(inp->i_number);
162 inossize(dp, inp->i_isize);
163 inodirty();
164 }
165 } else if ((inp->i_isize & (sblock.e2fs_bsize - 1)) != 0) {
166 getpathname(pathbuf, sizeof(pathbuf), inp->i_number,
167 inp->i_number);
168 pwarn("DIRECTORY %s: LENGTH %lu NOT MULTIPLE OF %d",
169 pathbuf, (u_long)inp->i_isize, sblock.e2fs_bsize);
170 if (preen)
171 printf(" (ADJUSTED)\n");
172 inp->i_isize = roundup(inp->i_isize, sblock.e2fs_bsize);
173 if (preen || reply("ADJUST") == 1) {
174 dp = ginode(inp->i_number);
175 inossize(dp, inp->i_isize);
176 inodirty();
177 }
178 }
179 memset(&dino, 0, sizeof(struct ext2fs_dinode));
180 dino.e2di_mode = h2fs16(IFDIR);
181 inossize(&dino, inp->i_isize);
182 memcpy(&dino.e2di_blocks[0], &inp->i_blks[0], (size_t)inp->i_numblks);
183 curino.id_number = inp->i_number;
184 curino.id_parent = inp->i_parent;
185 (void)ckinode(&dino, &curino);
186 }
187 /*
188 * Now that the parents of all directories have been found,
189 * make another pass to verify the value of `..'
190 */
191 for (inpp = inpsort; inpp < inpend; inpp++) {
192 inp = *inpp;
193 if (inp->i_parent == 0 || inp->i_isize == 0)
194 continue;
195 if (inp->i_dotdot == inp->i_parent ||
196 inp->i_dotdot == (ino_t)-1)
197 continue;
198 if (inp->i_dotdot == 0) {
199 inp->i_dotdot = inp->i_parent;
200 fileerror(inp->i_parent, inp->i_number, "MISSING '..'");
201 if (reply("FIX") == 0)
202 continue;
203 (void)makeentry(inp->i_number, inp->i_parent, "..");
204 lncntp[inp->i_parent]--;
205 continue;
206 }
207 fileerror(inp->i_parent, inp->i_number,
208 "BAD INODE NUMBER FOR '..'");
209 if (reply("FIX") == 0)
210 continue;
211 lncntp[inp->i_dotdot]++;
212 lncntp[inp->i_parent]--;
213 inp->i_dotdot = inp->i_parent;
214 (void)changeino(inp->i_number, "..", inp->i_parent);
215 }
216 /*
217 * Mark all the directories that can be found from the root.
218 */
219 propagate();
220 }
221
222 static int
pass2check(struct inodesc * idesc)223 pass2check(struct inodesc *idesc)
224 {
225 struct ext2fs_direct *dirp = idesc->id_dirp;
226 struct inoinfo *inp;
227 int n, entrysize, ret = 0;
228 struct ext2fs_dinode *dp;
229 const char *errmsg;
230 struct ext2fs_direct proto;
231 char namebuf[MAXPATHLEN + 1];
232 char pathbuf[MAXPATHLEN + 1];
233
234 /*
235 * check for "."
236 */
237 if (idesc->id_entryno != 0)
238 goto chk1;
239 if (fs2h32(dirp->e2d_ino) != 0 && dirp->e2d_namlen == 1 &&
240 dirp->e2d_name[0] == '.') {
241 if (fs2h32(dirp->e2d_ino) != idesc->id_number) {
242 direrror(idesc->id_number, "BAD INODE NUMBER FOR '.'");
243 dirp->e2d_ino = h2fs32(idesc->id_number);
244 if (reply("FIX") == 1)
245 ret |= ALTERED;
246 }
247 if (sblock.e2fs.e2fs_rev > E2FS_REV0 &&
248 (sblock.e2fs.e2fs_features_incompat & EXT2F_INCOMPAT_FTYPE)
249 && (dirp->e2d_type != EXT2_FT_DIR)) {
250 direrror(idesc->id_number, "BAD TYPE VALUE FOR '.'");
251 dirp->e2d_type = EXT2_FT_DIR;
252 if (reply("FIX") == 1)
253 ret |= ALTERED;
254 }
255 goto chk1;
256 }
257 direrror(idesc->id_number, "MISSING '.'");
258 proto.e2d_ino = h2fs32(idesc->id_number);
259 proto.e2d_namlen = 1;
260 if (sblock.e2fs.e2fs_rev > E2FS_REV0 &&
261 (sblock.e2fs.e2fs_features_incompat & EXT2F_INCOMPAT_FTYPE))
262 proto.e2d_type = EXT2_FT_DIR;
263 else
264 proto.e2d_type = 0;
265 (void)strlcpy(proto.e2d_name, ".", sizeof(proto.e2d_name));
266 entrysize = EXT2FS_DIRSIZ(proto.e2d_namlen);
267 if (fs2h32(dirp->e2d_ino) != 0 && strcmp(dirp->e2d_name, "..") != 0) {
268 pfatal("CANNOT FIX, FIRST ENTRY IN DIRECTORY CONTAINS %s\n",
269 dirp->e2d_name);
270 } else if (fs2h16(dirp->e2d_reclen) < entrysize) {
271 pfatal("CANNOT FIX, INSUFFICIENT SPACE TO ADD '.'\n");
272 } else if (fs2h16(dirp->e2d_reclen) < 2 * entrysize) {
273 proto.e2d_reclen = dirp->e2d_reclen;
274 memcpy(dirp, &proto, (size_t)entrysize);
275 if (reply("FIX") == 1)
276 ret |= ALTERED;
277 } else {
278 n = fs2h16(dirp->e2d_reclen) - entrysize;
279 proto.e2d_reclen = h2fs16(entrysize);
280 memcpy(dirp, &proto, (size_t)entrysize);
281 idesc->id_entryno++;
282 lncntp[fs2h32(dirp->e2d_ino)]--;
283 dirp = (struct ext2fs_direct *)((char *)(dirp) + entrysize);
284 memset(dirp, 0, (size_t)n);
285 dirp->e2d_reclen = h2fs16(n);
286 if (reply("FIX") == 1)
287 ret |= ALTERED;
288 }
289 chk1:
290 if (idesc->id_entryno > 1)
291 goto chk2;
292 inp = getinoinfo(idesc->id_number);
293 proto.e2d_ino = h2fs32(inp->i_parent);
294 proto.e2d_namlen = 2;
295 if (sblock.e2fs.e2fs_rev > E2FS_REV0 &&
296 (sblock.e2fs.e2fs_features_incompat & EXT2F_INCOMPAT_FTYPE))
297 proto.e2d_type = EXT2_FT_DIR;
298 else
299 proto.e2d_type = 0;
300 (void)strlcpy(proto.e2d_name, "..", sizeof(proto.e2d_name));
301 entrysize = EXT2FS_DIRSIZ(2);
302 if (idesc->id_entryno == 0) {
303 n = EXT2FS_DIRSIZ(dirp->e2d_namlen);
304 if (fs2h16(dirp->e2d_reclen) < n + entrysize)
305 goto chk2;
306 proto.e2d_reclen = h2fs16(fs2h16(dirp->e2d_reclen) - n);
307 dirp->e2d_reclen = h2fs16(n);
308 idesc->id_entryno++;
309 lncntp[fs2h32(dirp->e2d_ino)]--;
310 dirp = (struct ext2fs_direct *)((char *)(dirp) + n);
311 memset(dirp, 0, (size_t)fs2h16(proto.e2d_reclen));
312 dirp->e2d_reclen = proto.e2d_reclen;
313 }
314 if (fs2h32(dirp->e2d_ino) != 0 &&
315 dirp->e2d_namlen == 2 &&
316 strncmp(dirp->e2d_name, "..", 2) == 0) {
317 inp->i_dotdot = fs2h32(dirp->e2d_ino);
318 if (sblock.e2fs.e2fs_rev > E2FS_REV0 &&
319 (sblock.e2fs.e2fs_features_incompat & EXT2F_INCOMPAT_FTYPE)
320 && dirp->e2d_type != EXT2_FT_DIR) {
321 direrror(idesc->id_number, "BAD TYPE VALUE FOR '..'");
322 dirp->e2d_type = EXT2_FT_DIR;
323 if (reply("FIX") == 1)
324 ret |= ALTERED;
325 }
326 goto chk2;
327 }
328 if (fs2h32(dirp->e2d_ino) != 0 &&
329 dirp->e2d_namlen == 1 &&
330 strncmp(dirp->e2d_name, ".", 1) != 0) {
331 fileerror(inp->i_parent, idesc->id_number, "MISSING '..'");
332 pfatal("CANNOT FIX, SECOND ENTRY IN DIRECTORY CONTAINS %s\n",
333 dirp->e2d_name);
334 inp->i_dotdot = (ino_t)-1;
335 } else if (fs2h16(dirp->e2d_reclen) < entrysize) {
336 fileerror(inp->i_parent, idesc->id_number, "MISSING '..'");
337 pfatal("CANNOT FIX, INSUFFICIENT SPACE TO ADD '..'\n");
338 inp->i_dotdot = (ino_t)-1;
339 } else if (inp->i_parent != 0) {
340 /*
341 * We know the parent, so fix now.
342 */
343 inp->i_dotdot = inp->i_parent;
344 fileerror(inp->i_parent, idesc->id_number, "MISSING '..'");
345 proto.e2d_reclen = dirp->e2d_reclen;
346 memcpy(dirp, &proto, (size_t)entrysize);
347 if (reply("FIX") == 1)
348 ret |= ALTERED;
349 }
350 idesc->id_entryno++;
351 if (fs2h32(dirp->e2d_ino) != 0)
352 lncntp[fs2h32(dirp->e2d_ino)]--;
353 return (ret|KEEPON);
354 chk2:
355 if (fs2h32(dirp->e2d_ino) == 0)
356 return (ret|KEEPON);
357 if (dirp->e2d_namlen <= 2 &&
358 dirp->e2d_name[0] == '.' &&
359 idesc->id_entryno >= 2) {
360 if (dirp->e2d_namlen == 1) {
361 direrror(idesc->id_number, "EXTRA '.' ENTRY");
362 dirp->e2d_ino = 0;
363 if (reply("FIX") == 1)
364 ret |= ALTERED;
365 return (KEEPON | ret);
366 }
367 if (dirp->e2d_name[1] == '.') {
368 direrror(idesc->id_number, "EXTRA '..' ENTRY");
369 dirp->e2d_ino = 0;
370 if (reply("FIX") == 1)
371 ret |= ALTERED;
372 return (KEEPON | ret);
373 }
374 }
375 idesc->id_entryno++;
376 n = 0;
377 if (fs2h32(dirp->e2d_ino) > maxino ||
378 (fs2h32(dirp->e2d_ino) < EXT2_FIRSTINO &&
379 fs2h32(dirp->e2d_ino) != EXT2_ROOTINO)) {
380 fileerror(idesc->id_number, fs2h32(dirp->e2d_ino), "I OUT OF RANGE");
381 n = reply("REMOVE");
382 } else {
383 again:
384 switch (statemap[fs2h32(dirp->e2d_ino)]) {
385 case USTATE:
386 if (idesc->id_entryno <= 2)
387 break;
388 fileerror(idesc->id_number, fs2h32(dirp->e2d_ino), "UNALLOCATED");
389 n = reply("REMOVE");
390 break;
391
392 case DCLEAR:
393 case FCLEAR:
394 if (idesc->id_entryno <= 2)
395 break;
396 if (statemap[fs2h32(dirp->e2d_ino)] == FCLEAR)
397 errmsg = "DUP/BAD";
398 else if (!preen)
399 errmsg = "ZERO LENGTH DIRECTORY";
400 else {
401 n = 1;
402 break;
403 }
404 fileerror(idesc->id_number, fs2h32(dirp->e2d_ino), errmsg);
405 if ((n = reply("REMOVE")) == 1)
406 break;
407 dp = ginode(fs2h32(dirp->e2d_ino));
408 statemap[fs2h32(dirp->e2d_ino)] =
409 (fs2h16(dp->e2di_mode) & IFMT) == IFDIR ? DSTATE : FSTATE;
410 lncntp[fs2h32(dirp->e2d_ino)] = fs2h16(dp->e2di_nlink);
411 goto again;
412
413 case DSTATE:
414 case DFOUND:
415 inp = getinoinfo(fs2h32(dirp->e2d_ino));
416 if (inp->i_parent != 0 && idesc->id_entryno > 2) {
417 getpathname(pathbuf, sizeof(pathbuf),
418 idesc->id_number, idesc->id_number);
419 getpathname(namebuf, sizeof(namebuf),
420 fs2h32(dirp->e2d_ino),
421 fs2h32(dirp->e2d_ino));
422 pwarn("%s %s %s\n", pathbuf,
423 "IS AN EXTRANEOUS HARD LINK TO DIRECTORY",
424 namebuf);
425 if (preen)
426 printf(" (IGNORED)\n");
427 else if ((n = reply("REMOVE")) == 1)
428 break;
429 }
430 if (idesc->id_entryno > 2)
431 inp->i_parent = idesc->id_number;
432 /* fall through */
433
434 case FSTATE:
435 if (sblock.e2fs.e2fs_rev > E2FS_REV0 &&
436 (sblock.e2fs.e2fs_features_incompat &
437 EXT2F_INCOMPAT_FTYPE) &&
438 dirp->e2d_type !=
439 inot2ext2dt(typemap[fs2h32(dirp->e2d_ino)])) {
440 dirp->e2d_type =
441 inot2ext2dt(typemap[fs2h32(dirp->e2d_ino)]);
442 fileerror(idesc->id_number,
443 fs2h32(dirp->e2d_ino),
444 "BAD TYPE VALUE");
445 if (reply("FIX") == 1)
446 ret |= ALTERED;
447 }
448 lncntp[fs2h32(dirp->e2d_ino)]--;
449 break;
450
451 default:
452 errexit("BAD STATE %d FOR INODE I=%d",
453 statemap[fs2h32(dirp->e2d_ino)], fs2h32(dirp->e2d_ino));
454 }
455 }
456 if (n == 0)
457 return (ret|KEEPON);
458 dirp->e2d_ino = 0;
459 return (ret|KEEPON|ALTERED);
460 }
461
462 /*
463 * Routine to sort disk blocks.
464 */
465 static int
blksort(const void * inpp1,const void * inpp2)466 blksort(const void *inpp1, const void *inpp2)
467 {
468 return ((* (const struct inoinfo * const*) inpp1)->i_blks[0] -
469 (* (const struct inoinfo * const*) inpp2)->i_blks[0]);
470 }
471