2 * Copyright (c) 1980, 1986, 1993
3 * The Regents of the University of California. All rights reserved.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * 4. Neither the name of the University nor the names of its contributors
14 * may be used to endorse or promote products derived from this software
15 * without specific prior written permission.
17 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29 * @(#)pass2.c 8.9 (Berkeley) 4/28/95
30 * $FreeBSD: src/sbin/fsck/pass2.c,v 1.10.2.2 2001/11/24 15:14:59 iedowse Exp $
31 * $DragonFly: src/sbin/fsck/pass2.c,v 1.11 2006/10/12 04:04:03 dillon Exp $
34 #include <sys/param.h>
36 #include <vfs/ufs/dinode.h>
37 #include <vfs/ufs/dir.h>
44 #define MINDIRSIZE (sizeof (struct dirtemplate))
46 static int blksort(const void *, const void *);
47 static int pass2check(struct inodesc
*);
52 struct ufs1_dinode
*dp
;
53 struct inoinfo
**inpp
, *inp
;
54 struct inoinfo
**inpend
;
55 struct inodesc curino
;
56 struct ufs1_dinode dino
;
57 char pathbuf
[MAXPATHLEN
+ 1];
60 switch (inoinfo(ROOTINO
)->ino_state
) {
63 pfatal("ROOT INODE UNALLOCATED");
64 if (reply("ALLOCATE") == 0) {
68 if (allocdir(ROOTINO
, ROOTINO
, 0755) != ROOTINO
)
69 errx(EEXIT
, "CANNOT ALLOCATE ROOT INODE");
73 pfatal("DUPS/BAD IN ROOT INODE");
74 if (reply("REALLOCATE")) {
76 if (allocdir(ROOTINO
, ROOTINO
, 0755) != ROOTINO
)
77 errx(EEXIT
, "CANNOT ALLOCATE ROOT INODE");
80 if (reply("CONTINUE") == 0) {
88 pfatal("ROOT INODE NOT DIRECTORY");
89 if (reply("REALLOCATE")) {
91 if (allocdir(ROOTINO
, ROOTINO
, 0755) != ROOTINO
)
92 errx(EEXIT
, "CANNOT ALLOCATE ROOT INODE");
95 if (reply("FIX") == 0) {
100 dp
->di_mode
&= ~IFMT
;
101 dp
->di_mode
|= IFDIR
;
109 errx(EEXIT
, "BAD STATE %d FOR ROOT INODE",
110 inoinfo(ROOTINO
)->ino_state
);
112 inoinfo(ROOTINO
)->ino_state
= DFOUND
;
114 inoinfo(WINO
)->ino_state
= FSTATE
;
115 inoinfo(WINO
)->ino_type
= DT_WHT
;
118 * Sort the directory list into disk block order. Do this in blocks
119 * of 1000 directories in order to maintain locality of reference
120 * in memory in case fsck is using swap space.
122 for (i
= 0; i
< inplast
; i
+= 1000) {
123 if ((n
= inplast
- i
) > 1000)
125 qsort(inpsort
+ i
, (size_t)n
, sizeof *inpsort
, blksort
);
129 * Check the integrity of each directory.
131 memset(&curino
, 0, sizeof(struct inodesc
));
132 curino
.id_type
= DATA
;
133 curino
.id_func
= pass2check
;
135 inpend
= &inpsort
[inplast
];
136 for (inpp
= inpsort
; inpp
< inpend
; inpp
++) {
138 printf("%s: phase 2: dir %d of %ld (%d%%)\n", cdevname
,
139 inpp
- inpsort
, inplast
, (int)((inpp
- inpsort
) * 100 /
144 if (inp
->i_isize
== 0)
146 if (inp
->i_isize
< MINDIRSIZE
) {
147 direrror(inp
->i_number
, "DIRECTORY TOO SHORT");
148 inp
->i_isize
= roundup(MINDIRSIZE
, DIRBLKSIZ
);
149 if (reply("FIX") == 1) {
150 dp
= ginode(inp
->i_number
);
151 dp
->di_size
= inp
->i_isize
;
155 } else if ((inp
->i_isize
& (DIRBLKSIZ
- 1)) != 0) {
156 getpathname(pathbuf
, inp
->i_number
, inp
->i_number
);
158 pfatal("%s %s: LENGTH %d NOT MULTIPLE OF %d",
159 "DIRECTORY", pathbuf
, inp
->i_isize
,
162 pwarn("%s %s: LENGTH %d NOT MULTIPLE OF %d",
163 "DIRECTORY", pathbuf
, inp
->i_isize
,
166 printf(" (ADJUSTED)\n");
167 inp
->i_isize
= roundup(inp
->i_isize
, DIRBLKSIZ
);
168 if (preen
|| reply("ADJUST") == 1) {
169 dp
= ginode(inp
->i_number
);
170 dp
->di_size
= roundup(inp
->i_isize
, DIRBLKSIZ
);
175 memset(&dino
, 0, sizeof(struct ufs1_dinode
));
176 dino
.di_mode
= IFDIR
;
177 dp
->di_size
= inp
->i_isize
;
178 memmove(&dp
->di_db
[0], &inp
->i_blks
[0], (size_t)inp
->i_numblks
);
179 curino
.id_number
= inp
->i_number
;
180 curino
.id_parent
= inp
->i_parent
;
181 ckinode(dp
, &curino
);
184 * Now that the parents of all directories have been found,
185 * make another pass to verify the value of `..'
187 for (inpp
= inpsort
; inpp
< inpend
; inpp
++) {
189 if (inp
->i_parent
== 0 || inp
->i_isize
== 0)
191 if (inoinfo(inp
->i_parent
)->ino_state
== DFOUND
&&
192 inoinfo(inp
->i_number
)->ino_state
== DSTATE
)
193 inoinfo(inp
->i_number
)->ino_state
= DFOUND
;
194 if (inp
->i_dotdot
== inp
->i_parent
||
195 inp
->i_dotdot
== (ufs1_ino_t
)-1)
197 if (inp
->i_dotdot
== 0) {
198 inp
->i_dotdot
= inp
->i_parent
;
199 fileerror(inp
->i_parent
, inp
->i_number
, "MISSING '..'");
200 if (reply("FIX") == 0)
202 makeentry(inp
->i_number
, inp
->i_parent
, "..");
203 inoinfo(inp
->i_parent
)->ino_linkcnt
--;
206 fileerror(inp
->i_parent
, inp
->i_number
,
207 "BAD INODE NUMBER FOR '..'");
208 if (reply("FIX") == 0)
210 inoinfo(inp
->i_dotdot
)->ino_linkcnt
++;
211 inoinfo(inp
->i_parent
)->ino_linkcnt
--;
212 inp
->i_dotdot
= inp
->i_parent
;
213 changeino(inp
->i_number
, "..", inp
->i_parent
);
216 * Mark all the directories that can be found from the root.
222 pass2check(struct inodesc
*idesc
)
224 struct direct
*dirp
= idesc
->id_dirp
;
226 int n
, entrysize
, ret
= 0;
227 struct ufs1_dinode
*dp
;
230 char namebuf
[MAXPATHLEN
+ 1];
231 char pathbuf
[MAXPATHLEN
+ 1];
234 * If converting, set directory entry type.
236 if (doinglevel2
&& dirp
->d_ino
> 0 && dirp
->d_ino
< maxino
) {
237 dirp
->d_type
= inoinfo(dirp
->d_ino
)->ino_type
;
243 if (idesc
->id_entryno
!= 0)
245 if (dirp
->d_ino
!= 0 && strcmp(dirp
->d_name
, ".") == 0) {
246 if (dirp
->d_ino
!= idesc
->id_number
) {
247 direrror(idesc
->id_number
, "BAD INODE NUMBER FOR '.'");
248 dirp
->d_ino
= idesc
->id_number
;
249 if (reply("FIX") == 1)
252 if (newinofmt
&& dirp
->d_type
!= DT_DIR
) {
253 direrror(idesc
->id_number
, "BAD TYPE VALUE FOR '.'");
254 dirp
->d_type
= DT_DIR
;
255 if (reply("FIX") == 1)
260 direrror(idesc
->id_number
, "MISSING '.'");
261 proto
.d_ino
= idesc
->id_number
;
263 proto
.d_type
= DT_DIR
;
267 strcpy(proto
.d_name
, ".");
268 # if BYTE_ORDER == LITTLE_ENDIAN
273 proto
.d_type
= proto
.d_namlen
;
274 proto
.d_namlen
= tmp
;
277 entrysize
= DIRSIZ(0, &proto
);
278 if (dirp
->d_ino
!= 0 && strcmp(dirp
->d_name
, "..") != 0) {
279 pfatal("CANNOT FIX, FIRST ENTRY IN DIRECTORY CONTAINS %s\n",
281 } else if (dirp
->d_reclen
< entrysize
) {
282 pfatal("CANNOT FIX, INSUFFICIENT SPACE TO ADD '.'\n");
283 } else if (dirp
->d_reclen
< 2 * entrysize
) {
284 proto
.d_reclen
= dirp
->d_reclen
;
285 memmove(dirp
, &proto
, (size_t)entrysize
);
286 if (reply("FIX") == 1)
289 n
= dirp
->d_reclen
- entrysize
;
290 proto
.d_reclen
= entrysize
;
291 memmove(dirp
, &proto
, (size_t)entrysize
);
293 inoinfo(dirp
->d_ino
)->ino_linkcnt
--;
294 dirp
= (struct direct
*)((char *)(dirp
) + entrysize
);
295 memset(dirp
, 0, (size_t)n
);
297 if (reply("FIX") == 1)
301 if (idesc
->id_entryno
> 1)
303 inp
= getinoinfo(idesc
->id_number
);
304 proto
.d_ino
= inp
->i_parent
;
306 proto
.d_type
= DT_DIR
;
310 strcpy(proto
.d_name
, "..");
311 # if BYTE_ORDER == LITTLE_ENDIAN
316 proto
.d_type
= proto
.d_namlen
;
317 proto
.d_namlen
= tmp
;
320 entrysize
= DIRSIZ(0, &proto
);
321 if (idesc
->id_entryno
== 0) {
323 if (dirp
->d_reclen
< n
+ entrysize
)
325 proto
.d_reclen
= dirp
->d_reclen
- n
;
328 inoinfo(dirp
->d_ino
)->ino_linkcnt
--;
329 dirp
= (struct direct
*)((char *)(dirp
) + n
);
330 memset(dirp
, 0, (size_t)proto
.d_reclen
);
331 dirp
->d_reclen
= proto
.d_reclen
;
333 if (dirp
->d_ino
!= 0 && strcmp(dirp
->d_name
, "..") == 0) {
334 inp
->i_dotdot
= dirp
->d_ino
;
335 if (newinofmt
&& dirp
->d_type
!= DT_DIR
) {
336 direrror(idesc
->id_number
, "BAD TYPE VALUE FOR '..'");
337 dirp
->d_type
= DT_DIR
;
338 if (reply("FIX") == 1)
343 if (dirp
->d_ino
!= 0 && strcmp(dirp
->d_name
, ".") != 0) {
344 fileerror(inp
->i_parent
, idesc
->id_number
, "MISSING '..'");
345 pfatal("CANNOT FIX, SECOND ENTRY IN DIRECTORY CONTAINS %s\n",
347 inp
->i_dotdot
= (ufs1_ino_t
)-1;
348 } else if (dirp
->d_reclen
< entrysize
) {
349 fileerror(inp
->i_parent
, idesc
->id_number
, "MISSING '..'");
350 pfatal("CANNOT FIX, INSUFFICIENT SPACE TO ADD '..'\n");
351 inp
->i_dotdot
= (ufs1_ino_t
)-1;
352 } else if (inp
->i_parent
!= 0) {
354 * We know the parent, so fix now.
356 inp
->i_dotdot
= inp
->i_parent
;
357 fileerror(inp
->i_parent
, idesc
->id_number
, "MISSING '..'");
358 proto
.d_reclen
= dirp
->d_reclen
;
359 memmove(dirp
, &proto
, (size_t)entrysize
);
360 if (reply("FIX") == 1)
364 if (dirp
->d_ino
!= 0)
365 inoinfo(dirp
->d_ino
)->ino_linkcnt
--;
368 if (dirp
->d_ino
== 0)
370 if (dirp
->d_namlen
<= 2 &&
371 dirp
->d_name
[0] == '.' &&
372 idesc
->id_entryno
>= 2) {
373 if (dirp
->d_namlen
== 1) {
374 direrror(idesc
->id_number
, "EXTRA '.' ENTRY");
376 if (reply("FIX") == 1)
378 return (KEEPON
| ret
);
380 if (dirp
->d_name
[1] == '.') {
381 direrror(idesc
->id_number
, "EXTRA '..' ENTRY");
383 if (reply("FIX") == 1)
385 return (KEEPON
| ret
);
390 if (dirp
->d_ino
> maxino
) {
391 fileerror(idesc
->id_number
, dirp
->d_ino
, "I OUT OF RANGE");
393 } else if (newinofmt
&&
394 ((dirp
->d_ino
== WINO
&& dirp
->d_type
!= DT_WHT
) ||
395 (dirp
->d_ino
!= WINO
&& dirp
->d_type
== DT_WHT
))) {
396 fileerror(idesc
->id_number
, dirp
->d_ino
, "BAD WHITEOUT ENTRY");
398 dirp
->d_type
= DT_WHT
;
399 if (reply("FIX") == 1)
403 switch (inoinfo(dirp
->d_ino
)->ino_state
) {
405 if (idesc
->id_entryno
<= 2)
407 fileerror(idesc
->id_number
, dirp
->d_ino
, "UNALLOCATED");
413 if (idesc
->id_entryno
<= 2)
415 if (inoinfo(dirp
->d_ino
)->ino_state
== FCLEAR
)
417 else if (!preen
&& !usedsoftdep
)
418 errmsg
= "ZERO LENGTH DIRECTORY";
423 fileerror(idesc
->id_number
, dirp
->d_ino
, errmsg
);
424 if ((n
= reply("REMOVE")) == 1)
426 dp
= ginode(dirp
->d_ino
);
427 inoinfo(dirp
->d_ino
)->ino_state
=
428 (dp
->di_mode
& IFMT
) == IFDIR
? DSTATE
: FSTATE
;
429 inoinfo(dirp
->d_ino
)->ino_linkcnt
= dp
->di_nlink
;
433 if (inoinfo(idesc
->id_number
)->ino_state
== DFOUND
)
434 inoinfo(dirp
->d_ino
)->ino_state
= DFOUND
;
438 inp
= getinoinfo(dirp
->d_ino
);
439 if (inp
->i_parent
!= 0 && idesc
->id_entryno
> 2) {
440 getpathname(pathbuf
, idesc
->id_number
,
442 getpathname(namebuf
, dirp
->d_ino
, dirp
->d_ino
);
443 pwarn("%s%s%s %s %s\n", pathbuf
,
444 (strcmp(pathbuf
, "/") == 0 ? "" : "/"),
446 "IS AN EXTRANEOUS HARD LINK TO DIRECTORY",
449 printf(" (REMOVED)\n");
453 if ((n
= reply("REMOVE")) == 1)
456 if (idesc
->id_entryno
> 2)
457 inp
->i_parent
= idesc
->id_number
;
462 dirp
->d_type
!= inoinfo(dirp
->d_ino
)->ino_type
) {
463 fileerror(idesc
->id_number
, dirp
->d_ino
,
465 dirp
->d_type
= inoinfo(dirp
->d_ino
)->ino_type
;
466 if (reply("FIX") == 1)
469 inoinfo(dirp
->d_ino
)->ino_linkcnt
--;
473 errx(EEXIT
, "BAD STATE %d FOR INODE I=%d",
474 inoinfo(dirp
->d_ino
)->ino_state
, dirp
->d_ino
);
480 return (ret
|KEEPON
|ALTERED
);
484 * Routine to sort disk blocks.
487 blksort(const void *arg1
, const void *arg2
)
490 return ((*(struct inoinfo
**)arg1
)->i_blks
[0] -
491 (*(struct inoinfo
**)arg2
)->i_blks
[0]);