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 * 3. All advertising materials mentioning features or use of this software
14 * must display the following acknowledgement:
15 * This product includes software developed by the University of
16 * California, Berkeley and its contributors.
17 * 4. Neither the name of the University nor the names of its contributors
18 * may be used to endorse or promote products derived from this software
19 * without specific prior written permission.
21 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33 * @(#)dir.c 8.8 (Berkeley) 4/28/95
34 * $FreeBSD: src/sbin/fsck/dir.c,v 1.15 1999/08/28 00:12:45 peter Exp $
35 * $DragonFly: src/sbin/fsck/dir.c,v 1.11 2006/10/19 21:11:13 pavalos Exp $
38 #include <sys/param.h>
41 #include <vfs/ufs/dinode.h>
42 #include <vfs/ufs/dir.h>
43 #include <vfs/ufs/fs.h>
50 char *lfname
= "lost+found";
52 struct dirtemplate emptydir
= { 0, DIRBLKSIZ
};
53 struct dirtemplate dirhead
= {
54 0, 12, DT_DIR
, 1, ".",
55 0, DIRBLKSIZ
- 12, DT_DIR
, 2, ".."
57 struct odirtemplate odirhead
= {
59 0, DIRBLKSIZ
- 12, 2, ".."
62 static int chgino(struct inodesc
*);
63 static int dircheck(struct inodesc
*, struct direct
*);
64 static int expanddir(struct ufs1_dinode
*dp
, char *name
);
65 static void freedir(ufs1_ino_t ino
, ufs1_ino_t parent
);
66 static struct direct
*fsck_readdir(struct inodesc
*);
67 static struct bufarea
*getdirblk(ufs_daddr_t blkno
, long size
);
68 static int lftempname(char *bufp
, ufs1_ino_t ino
);
69 static int mkentry(struct inodesc
*);
72 * Propagate connected state through the tree.
77 struct inoinfo
**inpp
, *inp
;
78 struct inoinfo
**inpend
;
81 inpend
= &inpsort
[inplast
];
84 for (inpp
= inpsort
; inpp
< inpend
; inpp
++) {
86 if (inp
->i_parent
== 0)
88 if (inoinfo(inp
->i_parent
)->ino_state
== DFOUND
&&
89 inoinfo(inp
->i_number
)->ino_state
== DSTATE
) {
90 inoinfo(inp
->i_number
)->ino_state
= DFOUND
;
98 * Scan each entry in a directory block.
101 dirscan(struct inodesc
*idesc
)
105 unsigned int dsize
, n
;
107 char dbuf
[DIRBLKSIZ
];
109 if (idesc
->id_type
!= DATA
)
110 errx(EEXIT
, "wrong type to dirscan %d", idesc
->id_type
);
111 if (idesc
->id_entryno
== 0 &&
112 (idesc
->id_filesize
& (DIRBLKSIZ
- 1)) != 0)
113 idesc
->id_filesize
= roundup(idesc
->id_filesize
, DIRBLKSIZ
);
114 blksiz
= idesc
->id_numfrags
* sblock
.fs_fsize
;
115 if (chkrange(idesc
->id_blkno
, idesc
->id_numfrags
)) {
116 idesc
->id_filesize
-= blksiz
;
120 for (dp
= fsck_readdir(idesc
); dp
!= NULL
; dp
= fsck_readdir(idesc
)) {
121 dsize
= dp
->d_reclen
;
122 if (dsize
> sizeof(dbuf
))
123 dsize
= sizeof(dbuf
);
124 memmove(dbuf
, dp
, (size_t)dsize
);
125 # if (BYTE_ORDER == LITTLE_ENDIAN)
127 struct direct
*tdp
= (struct direct
*)dbuf
;
131 tdp
->d_namlen
= tdp
->d_type
;
135 idesc
->id_dirp
= (struct direct
*)dbuf
;
136 if ((n
= (*idesc
->id_func
)(idesc
)) & ALTERED
) {
137 # if (BYTE_ORDER == LITTLE_ENDIAN)
138 if (!newinofmt
&& !doinglevel2
) {
142 tdp
= (struct direct
*)dbuf
;
144 tdp
->d_namlen
= tdp
->d_type
;
148 bp
= getdirblk(idesc
->id_blkno
, blksiz
);
149 memmove(bp
->b_un
.b_buf
+ idesc
->id_loc
- dsize
, dbuf
,
157 return (idesc
->id_filesize
> 0 ? KEEPON
: STOP
);
161 * get next entry in a directory.
163 static struct direct
*
164 fsck_readdir(struct inodesc
*idesc
)
166 struct direct
*dp
, *ndp
;
168 long size
, blksiz
, fix
, dploc
;
170 blksiz
= idesc
->id_numfrags
* sblock
.fs_fsize
;
171 bp
= getdirblk(idesc
->id_blkno
, blksiz
);
172 if (idesc
->id_loc
% DIRBLKSIZ
== 0 && idesc
->id_filesize
> 0 &&
173 idesc
->id_loc
< blksiz
) {
174 dp
= (struct direct
*)(bp
->b_un
.b_buf
+ idesc
->id_loc
);
175 if (dircheck(idesc
, dp
))
177 if (idesc
->id_fix
== IGNORE
)
179 fix
= dofix(idesc
, "DIRECTORY CORRUPTED");
180 bp
= getdirblk(idesc
->id_blkno
, blksiz
);
181 dp
= (struct direct
*)(bp
->b_un
.b_buf
+ idesc
->id_loc
);
182 dp
->d_reclen
= DIRBLKSIZ
;
186 dp
->d_name
[0] = '\0';
189 idesc
->id_loc
+= DIRBLKSIZ
;
190 idesc
->id_filesize
-= DIRBLKSIZ
;
194 if (idesc
->id_filesize
<= 0 || idesc
->id_loc
>= blksiz
)
196 dploc
= idesc
->id_loc
;
197 dp
= (struct direct
*)(bp
->b_un
.b_buf
+ dploc
);
198 idesc
->id_loc
+= dp
->d_reclen
;
199 idesc
->id_filesize
-= dp
->d_reclen
;
200 if ((idesc
->id_loc
% DIRBLKSIZ
) == 0)
202 ndp
= (struct direct
*)(bp
->b_un
.b_buf
+ idesc
->id_loc
);
203 if (idesc
->id_loc
< blksiz
&& idesc
->id_filesize
> 0 &&
204 dircheck(idesc
, ndp
) == 0) {
205 size
= DIRBLKSIZ
- (idesc
->id_loc
% DIRBLKSIZ
);
206 idesc
->id_loc
+= size
;
207 idesc
->id_filesize
-= size
;
208 if (idesc
->id_fix
== IGNORE
)
210 fix
= dofix(idesc
, "DIRECTORY CORRUPTED");
211 bp
= getdirblk(idesc
->id_blkno
, blksiz
);
212 dp
= (struct direct
*)(bp
->b_un
.b_buf
+ dploc
);
213 dp
->d_reclen
+= size
;
221 * Verify that a directory entry is valid.
222 * This is a superset of the checks made in the kernel.
225 dircheck(struct inodesc
*idesc
, struct direct
*dp
)
232 spaceleft
= DIRBLKSIZ
- (idesc
->id_loc
% DIRBLKSIZ
);
233 if (dp
->d_reclen
== 0 ||
234 dp
->d_reclen
> spaceleft
||
235 (dp
->d_reclen
& 0x3) != 0)
239 size
= DIRSIZ(!newinofmt
, dp
);
240 # if (BYTE_ORDER == LITTLE_ENDIAN)
245 namlen
= dp
->d_namlen
;
249 namlen
= dp
->d_namlen
;
252 if (dp
->d_reclen
< size
||
253 idesc
->id_filesize
< size
||
256 for (cp
= dp
->d_name
, size
= 0; size
< namlen
; size
++)
257 if (*cp
== '\0' || (*cp
++ == '/'))
265 direrror(ufs1_ino_t ino
, char *errmesg
)
268 fileerror(ino
, ino
, errmesg
);
272 fileerror(ufs1_ino_t cwd
, ufs1_ino_t ino
, char *errmesg
)
274 struct ufs1_dinode
*dp
;
275 char pathbuf
[MAXPATHLEN
+ 1];
277 pwarn("%s ", errmesg
);
280 getpathname(pathbuf
, cwd
, ino
);
281 if (ino
< ROOTINO
|| ino
> maxino
) {
282 pfatal("NAME=%s\n", pathbuf
);
288 (dp
->di_mode
& IFMT
) == IFDIR
? "DIR" : "FILE", pathbuf
);
290 pfatal("NAME=%s\n", pathbuf
);
294 adjust(struct inodesc
*idesc
, int lcnt
)
296 struct ufs1_dinode
*dp
;
299 dp
= ginode(idesc
->id_number
);
300 if (dp
->di_nlink
== lcnt
) {
302 * If we have not hit any unresolved problems, are running
303 * in preen mode, and are on a filesystem using soft updates,
304 * then just toss any partially allocated files.
306 if (resolved
&& preen
&& usedsoftdep
) {
307 clri(idesc
, "UNREF", 1);
311 * The filesystem can be marked clean even if
312 * a file is not linked up, but is cleared.
313 * Hence, resolved should not be cleared when
314 * linkup is answered no, but clri is answered yes.
316 saveresolved
= resolved
;
317 if (linkup(idesc
->id_number
, (ufs1_ino_t
)0, NULL
) == 0) {
318 resolved
= saveresolved
;
319 clri(idesc
, "UNREF", 0);
323 * Account for the new reference created by linkup().
325 dp
= ginode(idesc
->id_number
);
330 pwarn("LINK COUNT %s", (lfdir
== idesc
->id_number
) ? lfname
:
331 ((dp
->di_mode
& IFMT
) == IFDIR
? "DIR" : "FILE"));
332 pinode(idesc
->id_number
);
333 printf(" COUNT %d SHOULD BE %d",
334 dp
->di_nlink
, dp
->di_nlink
- lcnt
);
335 if (preen
|| usedsoftdep
) {
338 pfatal("LINK COUNT INCREASING");
341 printf(" (ADJUSTED)\n");
343 if (preen
|| reply("ADJUST") == 1) {
344 dp
->di_nlink
-= lcnt
;
351 mkentry(struct inodesc
*idesc
)
353 struct direct
*dirp
= idesc
->id_dirp
;
354 struct direct newent
;
357 newent
.d_namlen
= strlen(idesc
->id_name
);
358 newlen
= DIRSIZ(0, &newent
);
359 if (dirp
->d_ino
!= 0)
360 oldlen
= DIRSIZ(0, dirp
);
363 if (dirp
->d_reclen
- oldlen
< newlen
)
365 newent
.d_reclen
= dirp
->d_reclen
- oldlen
;
366 dirp
->d_reclen
= oldlen
;
367 dirp
= (struct direct
*)(((char *)dirp
) + oldlen
);
368 dirp
->d_ino
= idesc
->id_parent
; /* ino to be entered is in id_parent */
369 dirp
->d_reclen
= newent
.d_reclen
;
371 dirp
->d_type
= inoinfo(idesc
->id_parent
)->ino_type
;
374 dirp
->d_namlen
= newent
.d_namlen
;
375 memmove(dirp
->d_name
, idesc
->id_name
, (size_t)newent
.d_namlen
+ 1);
376 # if (BYTE_ORDER == LITTLE_ENDIAN)
378 * If the entry was split, dirscan() will only reverse the byte
379 * order of the original entry, and not the new one, before
380 * writing it back out. So, we reverse the byte order here if
383 if (oldlen
!= 0 && !newinofmt
&& !doinglevel2
) {
386 tmp
= dirp
->d_namlen
;
387 dirp
->d_namlen
= dirp
->d_type
;
391 return (ALTERED
|STOP
);
395 chgino(struct inodesc
*idesc
)
397 struct direct
*dirp
= idesc
->id_dirp
;
399 if (memcmp(dirp
->d_name
, idesc
->id_name
, (int)dirp
->d_namlen
+ 1))
401 dirp
->d_ino
= idesc
->id_parent
;
403 dirp
->d_type
= inoinfo(idesc
->id_parent
)->ino_type
;
406 return (ALTERED
|STOP
);
410 linkup(ufs1_ino_t orphan
, ufs1_ino_t parentdir
, char *name
)
412 struct ufs1_dinode
*dp
;
415 struct inodesc idesc
;
416 char tempname
[BUFSIZ
];
418 memset(&idesc
, 0, sizeof(struct inodesc
));
420 lostdir
= (dp
->di_mode
& IFMT
) == IFDIR
;
421 pwarn("UNREF %s ", lostdir
? "DIR" : "FILE");
423 if (preen
&& dp
->di_size
== 0)
426 printf(" (RECONNECTED)\n");
428 if (reply("RECONNECT") == 0)
431 dp
= ginode(ROOTINO
);
432 idesc
.id_name
= lfname
;
433 idesc
.id_type
= DATA
;
434 idesc
.id_func
= findino
;
435 idesc
.id_number
= ROOTINO
;
436 if ((ckinode(dp
, &idesc
) & FOUND
) != 0) {
437 lfdir
= idesc
.id_parent
;
439 pwarn("NO lost+found DIRECTORY");
440 if (preen
|| reply("CREATE")) {
441 lfdir
= allocdir(ROOTINO
, (ufs1_ino_t
)0, lfmode
);
443 if (makeentry(ROOTINO
, lfdir
, lfname
) != 0) {
446 printf(" (CREATED)\n");
448 freedir(lfdir
, ROOTINO
);
457 pfatal("SORRY. CANNOT CREATE lost+found DIRECTORY");
463 if ((dp
->di_mode
& IFMT
) != IFDIR
) {
464 pfatal("lost+found IS NOT A DIRECTORY");
465 if (reply("REALLOCATE") == 0)
468 if ((lfdir
= allocdir(ROOTINO
, (ufs1_ino_t
)0, lfmode
)) == 0) {
469 pfatal("SORRY. CANNOT CREATE lost+found DIRECTORY\n\n");
472 if ((changeino(ROOTINO
, lfname
, lfdir
) & ALTERED
) == 0) {
473 pfatal("SORRY. CANNOT CREATE lost+found DIRECTORY\n\n");
477 idesc
.id_type
= ADDR
;
478 idesc
.id_func
= pass4check
;
479 idesc
.id_number
= oldlfdir
;
480 adjust(&idesc
, inoinfo(oldlfdir
)->ino_linkcnt
+ 1);
481 inoinfo(oldlfdir
)->ino_linkcnt
= 0;
484 if (inoinfo(lfdir
)->ino_state
!= DFOUND
) {
485 pfatal("SORRY. NO lost+found DIRECTORY\n\n");
488 lftempname(tempname
, orphan
);
489 if (makeentry(lfdir
, orphan
, (name
? name
: tempname
)) == 0) {
490 pfatal("SORRY. NO SPACE IN lost+found DIRECTORY");
494 inoinfo(orphan
)->ino_linkcnt
--;
496 if ((changeino(orphan
, "..", lfdir
) & ALTERED
) == 0 &&
497 parentdir
!= (ufs1_ino_t
)-1)
498 makeentry(orphan
, lfdir
, "..");
502 inoinfo(lfdir
)->ino_linkcnt
++;
503 pwarn("DIR I=%lu CONNECTED. ", orphan
);
504 if (parentdir
!= (ufs1_ino_t
)-1) {
505 printf("PARENT WAS I=%lu\n", (u_long
)parentdir
);
507 * The parent directory, because of the ordering
508 * guarantees, has had the link count incremented
509 * for the child, but no entry was made. This
510 * fixes the parent link count so that fsck does
511 * not need to be rerun.
513 inoinfo(parentdir
)->ino_linkcnt
++;
522 * fix an entry in a directory.
525 changeino(ufs1_ino_t dir
, char *name
, ufs1_ino_t newnum
)
527 struct inodesc idesc
;
529 memset(&idesc
, 0, sizeof(struct inodesc
));
530 idesc
.id_type
= DATA
;
531 idesc
.id_func
= chgino
;
532 idesc
.id_number
= dir
;
533 idesc
.id_fix
= DONTKNOW
;
534 idesc
.id_name
= name
;
535 idesc
.id_parent
= newnum
; /* new value for name */
536 return (ckinode(ginode(dir
), &idesc
));
540 * make an entry in a directory
543 makeentry(ufs1_ino_t parent
, ufs1_ino_t ino
, char *name
)
545 struct ufs1_dinode
*dp
;
546 struct inodesc idesc
;
547 char pathbuf
[MAXPATHLEN
+ 1];
549 if (parent
< ROOTINO
|| parent
>= maxino
||
550 ino
< ROOTINO
|| ino
>= maxino
)
552 memset(&idesc
, 0, sizeof(struct inodesc
));
553 idesc
.id_type
= DATA
;
554 idesc
.id_func
= mkentry
;
555 idesc
.id_number
= parent
;
556 idesc
.id_parent
= ino
; /* this is the inode to enter */
557 idesc
.id_fix
= DONTKNOW
;
558 idesc
.id_name
= name
;
560 if (dp
->di_size
% DIRBLKSIZ
) {
561 dp
->di_size
= roundup(dp
->di_size
, DIRBLKSIZ
);
564 if ((ckinode(dp
, &idesc
) & ALTERED
) != 0)
566 getpathname(pathbuf
, parent
, parent
);
568 if (expanddir(dp
, pathbuf
) == 0)
570 return (ckinode(dp
, &idesc
) & ALTERED
);
574 * Attempt to expand the size of a directory
577 expanddir(struct ufs1_dinode
*dp
, char *name
)
579 ufs_daddr_t lastbn
, newblk
;
581 char *cp
, firstblk
[DIRBLKSIZ
];
583 lastbn
= lblkno(&sblock
, dp
->di_size
);
584 if (lastbn
>= NDADDR
- 1 || dp
->di_db
[lastbn
] == 0 || dp
->di_size
== 0)
586 if ((newblk
= allocblk(sblock
.fs_frag
)) == 0)
588 dp
->di_db
[lastbn
+ 1] = dp
->di_db
[lastbn
];
589 dp
->di_db
[lastbn
] = newblk
;
590 dp
->di_size
+= sblock
.fs_bsize
;
591 dp
->di_blocks
+= btodb(sblock
.fs_bsize
);
592 bp
= getdirblk(dp
->di_db
[lastbn
+ 1],
593 (long)dblksize(&sblock
, dp
, lastbn
+ 1));
596 memmove(firstblk
, bp
->b_un
.b_buf
, DIRBLKSIZ
);
597 bp
= getdirblk(newblk
, sblock
.fs_bsize
);
600 memmove(bp
->b_un
.b_buf
, firstblk
, DIRBLKSIZ
);
601 for (cp
= &bp
->b_un
.b_buf
[DIRBLKSIZ
];
602 cp
< &bp
->b_un
.b_buf
[sblock
.fs_bsize
];
604 memmove(cp
, &emptydir
, sizeof emptydir
);
606 bp
= getdirblk(dp
->di_db
[lastbn
+ 1],
607 (long)dblksize(&sblock
, dp
, lastbn
+ 1));
610 memmove(bp
->b_un
.b_buf
, &emptydir
, sizeof emptydir
);
611 pwarn("NO SPACE LEFT IN %s", name
);
613 printf(" (EXPANDED)\n");
614 else if (reply("EXPAND") == 0)
620 dp
->di_db
[lastbn
] = dp
->di_db
[lastbn
+ 1];
621 dp
->di_db
[lastbn
+ 1] = 0;
622 dp
->di_size
-= sblock
.fs_bsize
;
623 dp
->di_blocks
-= btodb(sblock
.fs_bsize
);
624 freeblk(newblk
, sblock
.fs_frag
);
629 * allocate a new directory
632 allocdir(ufs1_ino_t parent
, ufs1_ino_t request
, int mode
)
636 struct ufs1_dinode
*dp
;
638 struct dirtemplate
*dirp
;
640 ino
= allocino(request
, IFDIR
|mode
);
644 dirp
= (struct dirtemplate
*)&odirhead
;
646 dirp
->dotdot_ino
= parent
;
648 bp
= getdirblk(dp
->di_db
[0], sblock
.fs_fsize
);
653 memmove(bp
->b_un
.b_buf
, dirp
, sizeof(struct dirtemplate
));
654 for (cp
= &bp
->b_un
.b_buf
[DIRBLKSIZ
];
655 cp
< &bp
->b_un
.b_buf
[sblock
.fs_fsize
];
657 memmove(cp
, &emptydir
, sizeof emptydir
);
661 if (ino
== ROOTINO
) {
662 inoinfo(ino
)->ino_linkcnt
= dp
->di_nlink
;
666 if (inoinfo(parent
)->ino_state
!= DSTATE
&&
667 inoinfo(parent
)->ino_state
!= DFOUND
) {
672 inoinfo(ino
)->ino_state
= inoinfo(parent
)->ino_state
;
673 if (inoinfo(ino
)->ino_state
== DSTATE
) {
674 inoinfo(ino
)->ino_linkcnt
= dp
->di_nlink
;
675 inoinfo(parent
)->ino_linkcnt
++;
684 * free a directory inode
687 freedir(ufs1_ino_t ino
, ufs1_ino_t parent
)
689 struct ufs1_dinode
*dp
;
700 * generate a temporary name for the lost+found directory.
703 lftempname(char *bufp
, ufs1_ino_t ino
)
710 for (in
= maxino
; in
> 0; in
/= 10)
716 *--cp
= (in
% 10) + '0';
724 * Get a directory block.
725 * Insure that it is held until another is requested.
727 static struct bufarea
*
728 getdirblk(ufs_daddr_t blkno
, long size
)
732 pdirbp
->b_flags
&= ~B_INUSE
;
733 pdirbp
= getdatablk(blkno
, size
);