1 /* $OpenBSD: pass2.c,v 1.39 2024/02/03 18:51:57 beck Exp $ */
2 /* $NetBSD: pass2.c,v 1.17 1996/09/27 22:45:15 christos Exp $ */
3
4 /*
5 * Copyright (c) 1980, 1986, 1993
6 * The Regents of the University of California. All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 * 3. Neither the name of the University nor the names of its contributors
17 * may be used to endorse or promote products derived from this software
18 * without specific prior written permission.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30 * SUCH DAMAGE.
31 */
32
33 #include <sys/param.h> /* DEV_BSIZE roundup */
34 #include <sys/time.h>
35 #include <ufs/ufs/dinode.h>
36 #include <ufs/ufs/dir.h>
37 #include <ufs/ffs/fs.h>
38
39 #include <stdio.h>
40 #include <stdlib.h>
41 #include <string.h>
42 #include <limits.h>
43
44 #include "fsck.h"
45 #include "fsutil.h"
46 #include "extern.h"
47
48 #define MINDIRSIZE (sizeof(struct dirtemplate))
49
50 static int pass2check(struct inodesc *);
51 static int blksort(const void *, const void *);
52
53 static int info_max;
54 static int info_pos;
55
56 static int
pass2_info1(char * buf,size_t buflen)57 pass2_info1(char *buf, size_t buflen)
58 {
59 return (snprintf(buf, buflen, "phase 2, directory %d/%d",
60 info_pos, info_max) > 0);
61 }
62
63 static int
pass2_info2(char * buf,size_t buflen)64 pass2_info2(char *buf, size_t buflen)
65 {
66 if (snprintf(buf, buflen, "phase 2, parent directory %d/%d",
67 info_pos, info_max) > 0)
68 return (strlen(buf));
69 return (0);
70 }
71
72 void
pass2(void)73 pass2(void)
74 {
75 union dinode *dp;
76 struct inoinfo **inpp, *inp, *pinp;
77 struct inoinfo **inpend;
78 struct inodesc curino;
79 union dinode dino;
80 char pathbuf[PATH_MAX + 1];
81 int i;
82
83 switch (GET_ISTATE(ROOTINO)) {
84
85 case USTATE:
86 pfatal("ROOT INODE UNALLOCATED");
87 if (reply("ALLOCATE") == 0) {
88 ckfini(0);
89 errexit("%s", "");
90 }
91 if (allocdir(ROOTINO, ROOTINO, 0755) != ROOTINO)
92 errexit("CANNOT ALLOCATE ROOT INODE\n");
93 break;
94
95 case DCLEAR:
96 pfatal("DUPS/BAD IN ROOT INODE");
97 if (reply("REALLOCATE")) {
98 freeino(ROOTINO);
99 if (allocdir(ROOTINO, ROOTINO, 0755) != ROOTINO)
100 errexit("CANNOT ALLOCATE ROOT INODE\n");
101 break;
102 }
103 if (reply("CONTINUE") == 0) {
104 ckfini(0);
105 errexit("%s", "");
106 }
107 break;
108
109 case FSTATE:
110 case FCLEAR:
111 pfatal("ROOT INODE NOT DIRECTORY");
112 if (reply("REALLOCATE")) {
113 freeino(ROOTINO);
114 if (allocdir(ROOTINO, ROOTINO, 0755) != ROOTINO)
115 errexit("CANNOT ALLOCATE ROOT INODE\n");
116 break;
117 }
118 if (reply("FIX") == 0) {
119 ckfini(0);
120 errexit("%s", "");
121 }
122 dp = ginode(ROOTINO);
123 DIP_SET(dp, di_mode, DIP(dp, di_mode) & ~IFMT);
124 DIP_SET(dp, di_mode, DIP(dp, di_mode) | IFDIR);
125 inodirty();
126 break;
127
128 case DSTATE:
129 break;
130
131 default:
132 errexit("BAD STATE %d FOR ROOT INODE\n", GET_ISTATE(ROOTINO));
133 }
134 SET_ISTATE(ROOTINO, DFOUND);
135 /*
136 * Sort the directory list into disk block order.
137 */
138 qsort(inpsort, (size_t)inplast, sizeof *inpsort, blksort);
139 /*
140 * Check the integrity of each directory.
141 */
142 memset(&curino, 0, sizeof(struct inodesc));
143 curino.id_type = DATA;
144 curino.id_func = pass2check;
145 inpend = &inpsort[inplast];
146 info_pos = 0;
147 info_max = inpend - inpsort;
148 info_fn = pass2_info1;
149 for (inpp = inpsort; inpp < inpend; inpp++) {
150 inp = *inpp;
151 info_pos ++;
152 if (inp->i_isize == 0)
153 continue;
154 if (inp->i_isize < MINDIRSIZE) {
155 direrror(inp->i_number, "DIRECTORY TOO SHORT");
156 inp->i_isize = roundup(MINDIRSIZE, DIRBLKSIZ);
157 if (reply("FIX") == 1) {
158 dp = ginode(inp->i_number);
159 DIP_SET(dp, di_size, inp->i_isize);
160 inodirty();
161 }
162 } else if ((inp->i_isize & (DIRBLKSIZ - 1)) != 0) {
163 getpathname(pathbuf, sizeof pathbuf,
164 inp->i_number, inp->i_number);
165 pwarn("%s %s: LENGTH %zu NOT MULTIPLE OF %d",
166 "DIRECTORY", pathbuf, inp->i_isize,
167 DIRBLKSIZ);
168 if (preen)
169 printf(" (ADJUSTED)\n");
170 inp->i_isize = roundup(inp->i_isize, DIRBLKSIZ);
171 if (preen || reply("ADJUST") == 1) {
172 dp = ginode(inp->i_number);
173 DIP_SET(dp, di_size, inp->i_isize);
174 inodirty();
175 }
176 }
177 memset(&dino, 0, sizeof(union dinode));
178 dp = &dino;
179 DIP_SET(dp, di_mode, IFDIR);
180 DIP_SET(dp, di_size, inp->i_isize);
181 for (i = 0;
182 i < (inp->i_numblks<NDADDR ? inp->i_numblks : NDADDR);
183 i++)
184 DIP_SET(dp, di_db[i], inp->i_blks[i]);
185 if (inp->i_numblks > NDADDR)
186 for (i = 0; i < NIADDR; i++)
187 DIP_SET(dp, di_ib[i], inp->i_blks[NDADDR + i]);
188 curino.id_number = inp->i_number;
189 curino.id_parent = inp->i_parent;
190 (void)ckinode(dp, &curino);
191 }
192 /*
193 * Now that the parents of all directories have been found,
194 * make another pass to verify the value of `..'
195 */
196 info_pos = 0;
197 info_fn = pass2_info2;
198 for (inpp = inpsort; inpp < inpend; inpp++) {
199 inp = *inpp;
200 info_pos++;
201 if (inp->i_parent == 0 || inp->i_isize == 0)
202 continue;
203 if (inp->i_dotdot == inp->i_parent ||
204 inp->i_dotdot == (ino_t)-1)
205 continue;
206 if (inp->i_dotdot == 0) {
207 inp->i_dotdot = inp->i_parent;
208 fileerror(inp->i_parent, inp->i_number, "MISSING '..'");
209 if (reply("FIX") == 0)
210 continue;
211 (void)makeentry(inp->i_number, inp->i_parent, "..");
212 ILNCOUNT(inp->i_parent)--;
213 continue;
214 }
215 fileerror(inp->i_parent, inp->i_number,
216 "BAD INODE NUMBER FOR '..'");
217 if (reply("FIX") == 0)
218 continue;
219 ILNCOUNT(inp->i_dotdot)++;
220 ILNCOUNT(inp->i_parent)--;
221 inp->i_dotdot = inp->i_parent;
222 (void)changeino(inp->i_number, "..", inp->i_parent);
223 }
224 info_fn = NULL;
225 /*
226 * Create a list of children for each directory.
227 */
228 inpend = &inpsort[inplast];
229 for (inpp = inpsort; inpp < inpend; inpp++) {
230 inp = *inpp;
231 if (inp->i_parent == 0 ||
232 inp->i_number == ROOTINO)
233 continue;
234 pinp = getinoinfo(inp->i_parent);
235 inp->i_sibling = pinp->i_child;
236 pinp->i_child = inp;
237 }
238 /*
239 * Mark all the directories that can be found from the root.
240 */
241 propagate(ROOTINO);
242 }
243
244 static int
pass2check(struct inodesc * idesc)245 pass2check(struct inodesc *idesc)
246 {
247 struct direct *dirp = idesc->id_dirp;
248 struct inoinfo *inp;
249 int n, entrysize, ret = 0;
250 union dinode *dp;
251 char *errmsg;
252 struct direct proto;
253 char namebuf[PATH_MAX + 1];
254 char pathbuf[PATH_MAX + 1];
255
256 /*
257 * check for "."
258 */
259 if (idesc->id_entryno != 0)
260 goto chk1;
261 if (dirp->d_ino != 0 && strcmp(dirp->d_name, ".") == 0) {
262 if (dirp->d_ino != idesc->id_number) {
263 direrror(idesc->id_number, "BAD INODE NUMBER FOR '.'");
264 dirp->d_ino = idesc->id_number;
265 if (reply("FIX") == 1)
266 ret |= ALTERED;
267 }
268 if (dirp->d_type != DT_DIR) {
269 direrror(idesc->id_number, "BAD TYPE VALUE FOR '.'");
270 dirp->d_type = DT_DIR;
271 if (reply("FIX") == 1)
272 ret |= ALTERED;
273 }
274 goto chk1;
275 }
276 direrror(idesc->id_number, "MISSING '.'");
277 proto.d_ino = idesc->id_number;
278 proto.d_type = DT_DIR;
279 proto.d_namlen = 1;
280 (void)strlcpy(proto.d_name, ".", sizeof proto.d_name);
281 entrysize = DIRSIZ(&proto);
282 if (dirp->d_ino != 0 && strcmp(dirp->d_name, "..") != 0) {
283 pfatal("CANNOT FIX, FIRST ENTRY IN DIRECTORY CONTAINS %s\n",
284 dirp->d_name);
285 } else if (dirp->d_reclen < entrysize) {
286 pfatal("CANNOT FIX, INSUFFICIENT SPACE TO ADD '.'\n");
287 } else if (dirp->d_reclen < 2 * entrysize) {
288 proto.d_reclen = dirp->d_reclen;
289 memcpy(dirp, &proto, (size_t)entrysize);
290 if (reply("FIX") == 1)
291 ret |= ALTERED;
292 } else {
293 n = dirp->d_reclen - entrysize;
294 proto.d_reclen = entrysize;
295 memcpy(dirp, &proto, (size_t)entrysize);
296 idesc->id_entryno++;
297 ILNCOUNT(dirp->d_ino)--;
298 dirp = (struct direct *)((char *)(dirp) + entrysize);
299 memset(dirp, 0, (size_t)n);
300 dirp->d_reclen = n;
301 if (reply("FIX") == 1)
302 ret |= ALTERED;
303 }
304 chk1:
305 if (idesc->id_entryno > 1)
306 goto chk2;
307 inp = getinoinfo(idesc->id_number);
308 proto.d_ino = inp->i_parent;
309 proto.d_type = DT_DIR;
310 proto.d_namlen = 2;
311 (void)strlcpy(proto.d_name, "..", sizeof proto.d_name);
312 entrysize = DIRSIZ(&proto);
313 if (idesc->id_entryno == 0) {
314 n = DIRSIZ(dirp);
315 if (dirp->d_reclen < n + entrysize)
316 goto chk2;
317 proto.d_reclen = dirp->d_reclen - n;
318 dirp->d_reclen = n;
319 idesc->id_entryno++;
320 ILNCOUNT(dirp->d_ino)--;
321 dirp = (struct direct *)((char *)(dirp) + n);
322 memset(dirp, 0, (size_t)proto.d_reclen);
323 dirp->d_reclen = proto.d_reclen;
324 }
325 if (dirp->d_ino != 0 && strcmp(dirp->d_name, "..") == 0) {
326 inp->i_dotdot = dirp->d_ino;
327 if (dirp->d_type != DT_DIR) {
328 direrror(idesc->id_number, "BAD TYPE VALUE FOR '..'");
329 dirp->d_type = DT_DIR;
330 if (reply("FIX") == 1)
331 ret |= ALTERED;
332 }
333 goto chk2;
334 }
335 if (dirp->d_ino != 0 && strcmp(dirp->d_name, ".") != 0) {
336 fileerror(inp->i_parent, idesc->id_number, "MISSING '..'");
337 pfatal("CANNOT FIX, SECOND ENTRY IN DIRECTORY CONTAINS %s\n",
338 dirp->d_name);
339 inp->i_dotdot = -1;
340 } else if (dirp->d_reclen < entrysize) {
341 fileerror(inp->i_parent, idesc->id_number, "MISSING '..'");
342 pfatal("CANNOT FIX, INSUFFICIENT SPACE TO ADD '..'\n");
343 inp->i_dotdot = -1;
344 } else if (inp->i_parent != 0) {
345 /*
346 * We know the parent, so fix now.
347 */
348 inp->i_dotdot = inp->i_parent;
349 fileerror(inp->i_parent, idesc->id_number, "MISSING '..'");
350 proto.d_reclen = dirp->d_reclen;
351 memcpy(dirp, &proto, (size_t)entrysize);
352 if (reply("FIX") == 1)
353 ret |= ALTERED;
354 }
355 idesc->id_entryno++;
356 if (dirp->d_ino != 0)
357 ILNCOUNT(dirp->d_ino)--;
358 return (ret|KEEPON);
359 chk2:
360 if (dirp->d_ino == 0)
361 return (ret|KEEPON);
362 if (dirp->d_namlen <= 2 &&
363 dirp->d_name[0] == '.' &&
364 idesc->id_entryno >= 2) {
365 if (dirp->d_namlen == 1) {
366 direrror(idesc->id_number, "EXTRA '.' ENTRY");
367 dirp->d_ino = 0;
368 if (reply("FIX") == 1)
369 ret |= ALTERED;
370 return (KEEPON | ret);
371 }
372 if (dirp->d_name[1] == '.') {
373 direrror(idesc->id_number, "EXTRA '..' ENTRY");
374 dirp->d_ino = 0;
375 if (reply("FIX") == 1)
376 ret |= ALTERED;
377 return (KEEPON | ret);
378 }
379 }
380 idesc->id_entryno++;
381 n = 0;
382 if (dirp->d_ino > maxino) {
383 fileerror(idesc->id_number, dirp->d_ino, "I OUT OF RANGE");
384 n = reply("REMOVE");
385 } else {
386 again:
387 switch (GET_ISTATE(dirp->d_ino)) {
388 case USTATE:
389 if (idesc->id_entryno <= 2)
390 break;
391 fileerror(idesc->id_number, dirp->d_ino, "UNALLOCATED");
392 n = reply("REMOVE");
393 break;
394
395 case DCLEAR:
396 case FCLEAR:
397 if (idesc->id_entryno <= 2)
398 break;
399 if (GET_ISTATE(dirp->d_ino) == FCLEAR)
400 errmsg = "DUP/BAD";
401 else if (!preen)
402 errmsg = "ZERO LENGTH DIRECTORY";
403 else {
404 n = 1;
405 break;
406 }
407 fileerror(idesc->id_number, dirp->d_ino, errmsg);
408 if ((n = reply("REMOVE")) == 1)
409 break;
410 dp = ginode(dirp->d_ino);
411 SET_ISTATE(dirp->d_ino, (DIP(dp, di_mode) & IFMT) ==
412 IFDIR ? DSTATE : FSTATE);
413 ILNCOUNT(dirp->d_ino) = DIP(dp, di_nlink);
414 goto again;
415
416 case DSTATE:
417 case DFOUND:
418 inp = getinoinfo(dirp->d_ino);
419 if (inp->i_parent != 0 && idesc->id_entryno > 2) {
420 getpathname(pathbuf, sizeof pathbuf,
421 idesc->id_number, idesc->id_number);
422 getpathname(namebuf, sizeof namebuf,
423 dirp->d_ino, dirp->d_ino);
424 pwarn("%s %s %s\n", pathbuf,
425 "IS AN EXTRANEOUS HARD LINK TO DIRECTORY",
426 namebuf);
427 if (preen) {
428 printf (" (REMOVED)\n");
429 n = 1;
430 break;
431 }
432 if ((n = reply("REMOVE")) == 1)
433 break;
434 }
435 if (idesc->id_entryno > 2)
436 inp->i_parent = idesc->id_number;
437 /* FALLTHROUGH */
438
439 case FSTATE:
440 if (dirp->d_type != GET_ITYPE(dirp->d_ino)) {
441 fileerror(idesc->id_number, dirp->d_ino,
442 "BAD TYPE VALUE");
443 dirp->d_type = GET_ITYPE(dirp->d_ino);
444 if (reply("FIX") == 1)
445 ret |= ALTERED;
446 }
447 ILNCOUNT(dirp->d_ino)--;
448 break;
449
450 default:
451 errexit("BAD STATE %d FOR INODE I=%llu\n",
452 GET_ISTATE(dirp->d_ino),
453 (unsigned long long)dirp->d_ino);
454 }
455 }
456 if (n == 0)
457 return (ret|KEEPON);
458 dirp->d_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 daddr_t d;
469
470 d = (* (struct inoinfo **) inpp1)->i_blks[0] -
471 (* (struct inoinfo **) inpp2)->i_blks[0];
472 if (d < 0)
473 return (-1);
474 else if (d > 0)
475 return (1);
476 else
477 return (0);
478 }
479