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 * @(#)inode.c 8.8 (Berkeley) 4/28/95
34 * $FreeBSD: src/sbin/fsck/inode.c,v 1.20 2000/02/28 20:02:41 mckusick Exp $
35 * $DragonFly: src/sbin/fsck/inode.c,v 1.9 2006/04/03 01:58:49 dillon Exp $
38 #include <sys/param.h>
41 #include <vfs/ufs/dinode.h>
42 #include <vfs/ufs/dir.h>
43 #include <vfs/ufs/fs.h>
51 static ino_t startinum
;
53 static int iblock(struct inodesc
*, long ilevel
, quad_t isize
);
56 ckinode(struct ufs1_dinode
*dp
, struct inodesc
*idesc
)
61 struct ufs1_dinode dino
;
62 quad_t remsize
, sizepb
;
64 char pathbuf
[MAXPATHLEN
+ 1];
66 if (idesc
->id_fix
!= IGNORE
)
67 idesc
->id_fix
= DONTKNOW
;
68 idesc
->id_entryno
= 0;
69 idesc
->id_filesize
= dp
->di_size
;
70 mode
= dp
->di_mode
& IFMT
;
71 if (mode
== IFBLK
|| mode
== IFCHR
|| (mode
== IFLNK
&&
72 dp
->di_size
< (unsigned)sblock
.fs_maxsymlinklen
))
75 ndb
= howmany(dino
.di_size
, sblock
.fs_bsize
);
76 for (ap
= &dino
.di_db
[0]; ap
< &dino
.di_db
[NDADDR
]; ap
++) {
77 if (--ndb
== 0 && (offset
= blkoff(&sblock
, dino
.di_size
)) != 0)
79 numfrags(&sblock
, fragroundup(&sblock
, offset
));
81 idesc
->id_numfrags
= sblock
.fs_frag
;
83 if (idesc
->id_type
== DATA
&& ndb
>= 0) {
84 /* An empty block in a directory XXX */
85 getpathname(pathbuf
, idesc
->id_number
,
87 pfatal("DIRECTORY %s: CONTAINS EMPTY BLOCKS",
89 if (reply("ADJUST LENGTH") == 1) {
90 dp
= ginode(idesc
->id_number
);
91 dp
->di_size
= (ap
- &dino
.di_db
[0]) *
94 "YOU MUST RERUN FSCK AFTERWARDS\n");
102 idesc
->id_blkno
= *ap
;
103 if (idesc
->id_type
== ADDR
)
104 ret
= (*idesc
->id_func
)(idesc
);
106 ret
= dirscan(idesc
);
110 idesc
->id_numfrags
= sblock
.fs_frag
;
111 remsize
= dino
.di_size
- sblock
.fs_bsize
* NDADDR
;
112 sizepb
= sblock
.fs_bsize
;
113 for (ap
= &dino
.di_ib
[0], n
= 1; n
<= NIADDR
; ap
++, n
++) {
115 idesc
->id_blkno
= *ap
;
116 ret
= iblock(idesc
, n
, remsize
);
120 if (idesc
->id_type
== DATA
&& remsize
> 0) {
121 /* An empty block in a directory XXX */
122 getpathname(pathbuf
, idesc
->id_number
,
124 pfatal("DIRECTORY %s: CONTAINS EMPTY BLOCKS",
126 if (reply("ADJUST LENGTH") == 1) {
127 dp
= ginode(idesc
->id_number
);
128 dp
->di_size
-= remsize
;
131 "YOU MUST RERUN FSCK AFTERWARDS\n");
138 sizepb
*= NINDIR(&sblock
);
145 iblock(struct inodesc
*idesc
, long ilevel
, quad_t isize
)
150 int i
, n
, (*func
)(), nif
;
153 char pathbuf
[MAXPATHLEN
+ 1];
154 struct ufs1_dinode
*dp
;
156 if (idesc
->id_type
== ADDR
) {
157 func
= idesc
->id_func
;
158 if (((n
= (*func
)(idesc
)) & KEEPON
) == 0)
162 if (chkrange(idesc
->id_blkno
, idesc
->id_numfrags
))
164 bp
= getdatablk(idesc
->id_blkno
, sblock
.fs_bsize
);
166 for (sizepb
= sblock
.fs_bsize
, i
= 0; i
< ilevel
; i
++)
167 sizepb
*= NINDIR(&sblock
);
168 nif
= howmany(isize
, sizepb
);
169 if (nif
> NINDIR(&sblock
))
170 nif
= NINDIR(&sblock
);
171 if (idesc
->id_func
== pass1check
&& nif
< NINDIR(&sblock
)) {
172 aplim
= &bp
->b_un
.b_indir
[NINDIR(&sblock
)];
173 for (ap
= &bp
->b_un
.b_indir
[nif
]; ap
< aplim
; ap
++) {
176 sprintf(buf
, "PARTIALLY TRUNCATED INODE I=%lu",
177 (u_long
)idesc
->id_number
);
178 if (dofix(idesc
, buf
)) {
183 flush(fswritefd
, bp
);
185 aplim
= &bp
->b_un
.b_indir
[nif
];
186 for (ap
= bp
->b_un
.b_indir
; ap
< aplim
; ap
++) {
188 idesc
->id_blkno
= *ap
;
192 n
= iblock(idesc
, ilevel
, isize
);
194 bp
->b_flags
&= ~B_INUSE
;
198 if (idesc
->id_type
== DATA
&& isize
> 0) {
199 /* An empty block in a directory XXX */
200 getpathname(pathbuf
, idesc
->id_number
,
202 pfatal("DIRECTORY %s: CONTAINS EMPTY BLOCKS",
204 if (reply("ADJUST LENGTH") == 1) {
205 dp
= ginode(idesc
->id_number
);
206 dp
->di_size
-= isize
;
209 "YOU MUST RERUN FSCK AFTERWARDS\n");
212 bp
->b_flags
&= ~B_INUSE
;
219 bp
->b_flags
&= ~B_INUSE
;
224 * Check that a block in a legal block number.
225 * Return 0 if in range, 1 if out of range.
228 chkrange(ufs_daddr_t blk
, int cnt
)
232 if (cnt
<= 0 || blk
<= 0 || blk
> maxfsblock
||
233 cnt
- 1 > maxfsblock
- blk
)
235 if (cnt
> sblock
.fs_frag
||
236 fragnum(&sblock
, blk
) + cnt
> sblock
.fs_frag
) {
238 printf("bad size: blk %ld, offset %d, size %d\n",
239 (long)blk
, fragnum(&sblock
, blk
), cnt
);
242 c
= dtog(&sblock
, blk
);
243 if (blk
< cgdmin(&sblock
, c
)) {
244 if ((blk
+ cnt
) > cgsblock(&sblock
, c
)) {
246 printf("blk %ld < cgdmin %ld;",
247 (long)blk
, (long)cgdmin(&sblock
, c
));
248 printf(" blk + cnt %ld > cgsbase %ld\n",
250 (long)cgsblock(&sblock
, c
));
255 if ((blk
+ cnt
) > cgbase(&sblock
, c
+1)) {
257 printf("blk %ld >= cgdmin %ld;",
258 (long)blk
, (long)cgdmin(&sblock
, c
));
259 printf(" blk + cnt %ld > sblock.fs_fpg %ld\n",
260 (long)(blk
+ cnt
), (long)sblock
.fs_fpg
);
269 * General purpose interface for reading inodes.
272 ginode(ino_t inumber
)
276 if (inumber
< ROOTINO
|| inumber
> maxino
)
277 errx(EEXIT
, "bad inode number %d to ginode", inumber
);
278 if (startinum
== 0 ||
279 inumber
< startinum
|| inumber
>= startinum
+ INOPB(&sblock
)) {
280 iblk
= ino_to_fsba(&sblock
, inumber
);
282 pbp
->b_flags
&= ~B_INUSE
;
283 pbp
= getdatablk(iblk
, sblock
.fs_bsize
);
284 startinum
= (inumber
/ INOPB(&sblock
)) * INOPB(&sblock
);
286 return (&pbp
->b_un
.b_dinode
[inumber
% INOPB(&sblock
)]);
290 * Special purpose version of ginode used to optimize first pass
291 * over all the inodes in numerical order.
293 ino_t nextino
, lastinum
;
294 long readcnt
, readpercg
, fullcnt
, inobufsize
, partialcnt
, partialsize
;
295 struct ufs1_dinode
*inodebuf
;
298 getnextinode(ino_t inumber
)
302 static struct ufs1_dinode
*dp
;
304 if (inumber
!= nextino
++ || inumber
> maxino
)
305 errx(EEXIT
, "bad inode number %d to nextinode", inumber
);
306 if (inumber
>= lastinum
) {
308 dblk
= fsbtodb(&sblock
, ino_to_fsba(&sblock
, lastinum
));
309 if (readcnt
% readpercg
== 0) {
311 lastinum
+= partialcnt
;
317 * If bread returns an error, it will already have zeroed
318 * out the buffer, so we do not need to do so here.
320 bread(fsreadfd
, (char *)inodebuf
, dblk
, size
);
327 setinodebuf(ino_t inum
)
330 if (inum
% sblock
.fs_ipg
!= 0)
331 errx(EEXIT
, "bad inode number %d to setinodebuf", inum
);
336 if (inodebuf
!= NULL
)
338 inobufsize
= blkroundup(&sblock
, INOBUFSIZE
);
339 fullcnt
= inobufsize
/ sizeof(struct ufs1_dinode
);
340 readpercg
= sblock
.fs_ipg
/ fullcnt
;
341 partialcnt
= sblock
.fs_ipg
% fullcnt
;
342 partialsize
= partialcnt
* sizeof(struct ufs1_dinode
);
343 if (partialcnt
!= 0) {
346 partialcnt
= fullcnt
;
347 partialsize
= inobufsize
;
349 if ((inodebuf
= (struct ufs1_dinode
*)malloc((unsigned)inobufsize
)) == NULL
)
350 errx(EEXIT
, "cannot allocate space for inode buffer");
357 if (inodebuf
!= NULL
)
358 free((char *)inodebuf
);
363 * Routines to maintain information about directory inodes.
364 * This is built during the first pass and used during the
365 * second and third passes.
367 * Enter inodes into the cache.
370 cacheino(struct ufs1_dinode
*dp
, ino_t inumber
)
373 struct inoinfo
**inpp
;
376 blks
= howmany(dp
->di_size
, sblock
.fs_bsize
);
378 blks
= NDADDR
+ NIADDR
;
379 inp
= (struct inoinfo
*)
380 malloc(sizeof(*inp
) + (blks
- 1) * sizeof(ufs_daddr_t
));
382 errx(EEXIT
, "cannot increase directory list");
383 inpp
= &inphead
[inumber
% dirhash
];
384 inp
->i_nexthash
= *inpp
;
386 inp
->i_parent
= inumber
== ROOTINO
? ROOTINO
: (ino_t
)0;
387 inp
->i_dotdot
= (ino_t
)0;
388 inp
->i_number
= inumber
;
389 inp
->i_isize
= dp
->di_size
;
390 inp
->i_numblks
= blks
* sizeof(ufs_daddr_t
);
391 memmove(&inp
->i_blks
[0], &dp
->di_db
[0], (size_t)inp
->i_numblks
);
392 if (inplast
== listmax
) {
394 inpsort
= (struct inoinfo
**)realloc((char *)inpsort
,
395 (unsigned)listmax
* sizeof(struct inoinfo
*));
397 errx(EEXIT
, "cannot increase directory list");
399 inpsort
[inplast
++] = inp
;
403 * Look up an inode cache structure.
406 getinoinfo(ino_t inumber
)
410 for (inp
= inphead
[inumber
% dirhash
]; inp
; inp
= inp
->i_nexthash
) {
411 if (inp
->i_number
!= inumber
)
415 errx(EEXIT
, "cannot find inode %d", inumber
);
416 return ((struct inoinfo
*)0);
420 * Clean up all the inode cache structure.
425 struct inoinfo
**inpp
;
429 for (inpp
= &inpsort
[inplast
- 1]; inpp
>= inpsort
; inpp
--)
430 free((char *)(*inpp
));
431 free((char *)inphead
);
432 free((char *)inpsort
);
433 inphead
= inpsort
= NULL
;
444 clri(struct inodesc
*idesc
, char *type
, int flag
)
446 struct ufs1_dinode
*dp
;
448 dp
= ginode(idesc
->id_number
);
451 (dp
->di_mode
& IFMT
) == IFDIR
? "DIR" : "FILE");
452 pinode(idesc
->id_number
);
454 if (preen
|| reply("CLEAR") == 1) {
456 printf(" (CLEARED)\n");
460 inoinfo(idesc
->id_number
)->ino_state
= USTATE
;
466 findname(struct inodesc
*idesc
)
468 struct direct
*dirp
= idesc
->id_dirp
;
470 if (dirp
->d_ino
!= idesc
->id_parent
|| idesc
->id_entryno
< 2) {
474 memmove(idesc
->id_name
, dirp
->d_name
, (size_t)dirp
->d_namlen
+ 1);
479 findino(struct inodesc
*idesc
)
481 struct direct
*dirp
= idesc
->id_dirp
;
483 if (dirp
->d_ino
== 0)
485 if (strcmp(dirp
->d_name
, idesc
->id_name
) == 0 &&
486 dirp
->d_ino
>= ROOTINO
&& dirp
->d_ino
<= maxino
) {
487 idesc
->id_parent
= dirp
->d_ino
;
494 clearentry(struct inodesc
*idesc
)
496 struct direct
*dirp
= idesc
->id_dirp
;
498 if (dirp
->d_ino
!= idesc
->id_parent
|| idesc
->id_entryno
< 2) {
503 return (STOP
|FOUND
|ALTERED
);
509 struct ufs1_dinode
*dp
;
514 printf(" I=%lu ", (u_long
)ino
);
515 if (ino
< ROOTINO
|| ino
> maxino
)
519 if ((pw
= getpwuid((int)dp
->di_uid
)) != 0)
520 printf("%s ", pw
->pw_name
);
522 printf("%u ", (unsigned)dp
->di_uid
);
523 printf("MODE=%o\n", dp
->di_mode
);
525 printf("%s: ", cdevname
);
526 printf("SIZE=%qu ", dp
->di_size
);
529 printf("MTIME=%12.12s %4.4s ", &p
[4], &p
[20]);
533 blkerror(ino_t ino
, char *type
, ufs_daddr_t blk
)
536 pfatal("%ld %s I=%lu", blk
, type
, ino
);
538 switch (inoinfo(ino
)->ino_state
) {
541 inoinfo(ino
)->ino_state
= FCLEAR
;
545 inoinfo(ino
)->ino_state
= DCLEAR
;
553 errx(EEXIT
, "BAD STATE %d TO BLKERR", inoinfo(ino
)->ino_state
);
559 * allocate an unused inode
562 allocino(ino_t request
, int type
)
565 struct ufs1_dinode
*dp
;
566 struct cg
*cgp
= &cgrp
;
571 else if (inoinfo(request
)->ino_state
!= USTATE
)
573 for (ino
= request
; ino
< maxino
; ino
++)
574 if (inoinfo(ino
)->ino_state
== USTATE
)
578 cg
= ino_to_cg(&sblock
, ino
);
579 getblk(&cgblk
, cgtod(&sblock
, cg
), sblock
.fs_cgsize
);
580 if (!cg_chkmagic(cgp
))
581 pfatal("CG %d: BAD MAGIC NUMBER\n", cg
);
582 setbit(cg_inosused(cgp
), ino
% sblock
.fs_ipg
);
583 cgp
->cg_cs
.cs_nifree
--;
584 switch (type
& IFMT
) {
586 inoinfo(ino
)->ino_state
= DSTATE
;
587 cgp
->cg_cs
.cs_ndir
++;
591 inoinfo(ino
)->ino_state
= FSTATE
;
598 dp
->di_db
[0] = allocblk((long)1);
599 if (dp
->di_db
[0] == 0) {
600 inoinfo(ino
)->ino_state
= USTATE
;
605 dp
->di_atime
= time(NULL
);
606 dp
->di_mtime
= dp
->di_ctime
= dp
->di_atime
;
607 dp
->di_mtimensec
= dp
->di_ctimensec
= dp
->di_atimensec
= 0;
608 dp
->di_size
= sblock
.fs_fsize
;
609 dp
->di_blocks
= btodb(sblock
.fs_fsize
);
613 inoinfo(ino
)->ino_type
= IFTODT(type
);
618 * deallocate an inode
623 struct inodesc idesc
;
624 struct ufs1_dinode
*dp
;
626 memset(&idesc
, 0, sizeof(struct inodesc
));
627 idesc
.id_type
= ADDR
;
628 idesc
.id_func
= pass4check
;
629 idesc
.id_number
= ino
;
634 inoinfo(ino
)->ino_state
= USTATE
;