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. 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 * @(#)inode.c 8.8 (Berkeley) 4/28/95
30 * $FreeBSD: src/sbin/fsck/inode.c,v 1.20 2000/02/28 20:02:41 mckusick Exp $
33 #include <sys/param.h>
36 #include <vfs/ufs/dinode.h>
37 #include <vfs/ufs/dir.h>
38 #include <vfs/ufs/fs.h>
47 static ufs1_ino_t startinum
;
49 static int iblock(struct inodesc
*, long ilevel
, quad_t isize
);
52 ckinode(struct ufs1_dinode
*dp
, struct inodesc
*idesc
)
57 struct ufs1_dinode dino
;
58 quad_t remsize
, sizepb
;
60 char pathbuf
[MAXPATHLEN
+ 1];
62 if (idesc
->id_fix
!= IGNORE
)
63 idesc
->id_fix
= DONTKNOW
;
64 idesc
->id_entryno
= 0;
65 idesc
->id_filesize
= dp
->di_size
;
66 mode
= dp
->di_mode
& IFMT
;
67 if (mode
== IFBLK
|| mode
== IFCHR
|| (mode
== IFLNK
&&
68 dp
->di_size
< (unsigned)sblock
.fs_maxsymlinklen
))
71 ndb
= howmany(dino
.di_size
, sblock
.fs_bsize
);
72 for (ap
= &dino
.di_db
[0]; ap
< &dino
.di_db
[NDADDR
]; ap
++) {
73 if (--ndb
== 0 && (offset
= blkoff(&sblock
, dino
.di_size
)) != 0)
75 numfrags(&sblock
, fragroundup(&sblock
, offset
));
77 idesc
->id_numfrags
= sblock
.fs_frag
;
79 if (idesc
->id_type
== DATA
&& ndb
>= 0) {
80 /* An empty block in a directory XXX */
81 getpathname(pathbuf
, idesc
->id_number
,
83 pfatal("DIRECTORY %s: CONTAINS EMPTY BLOCKS",
85 if (reply("ADJUST LENGTH") == 1) {
86 dp
= ginode(idesc
->id_number
);
87 dp
->di_size
= (ap
- &dino
.di_db
[0]) *
90 "YOU MUST RERUN FSCK AFTERWARDS\n");
98 idesc
->id_blkno
= *ap
;
99 if (idesc
->id_type
== ADDR
)
100 ret
= (*idesc
->id_func
)(idesc
);
102 ret
= dirscan(idesc
);
106 idesc
->id_numfrags
= sblock
.fs_frag
;
107 remsize
= dino
.di_size
- sblock
.fs_bsize
* NDADDR
;
108 sizepb
= sblock
.fs_bsize
;
109 for (ap
= &dino
.di_ib
[0], n
= 1; n
<= NIADDR
; ap
++, n
++) {
111 idesc
->id_blkno
= *ap
;
112 ret
= iblock(idesc
, n
, remsize
);
116 if (idesc
->id_type
== DATA
&& remsize
> 0) {
117 /* An empty block in a directory XXX */
118 getpathname(pathbuf
, idesc
->id_number
,
120 pfatal("DIRECTORY %s: CONTAINS EMPTY BLOCKS",
122 if (reply("ADJUST LENGTH") == 1) {
123 dp
= ginode(idesc
->id_number
);
124 dp
->di_size
-= remsize
;
127 "YOU MUST RERUN FSCK AFTERWARDS\n");
134 sizepb
*= NINDIR(&sblock
);
141 iblock(struct inodesc
*idesc
, long ilevel
, quad_t isize
)
146 int i
, n
, (*func
)(), nif
;
149 char pathbuf
[MAXPATHLEN
+ 1];
150 struct ufs1_dinode
*dp
;
152 if (idesc
->id_type
== ADDR
) {
153 func
= idesc
->id_func
;
154 if (((n
= (*func
)(idesc
)) & KEEPON
) == 0)
158 if (chkrange(idesc
->id_blkno
, idesc
->id_numfrags
))
160 bp
= getdatablk(idesc
->id_blkno
, sblock
.fs_bsize
);
162 for (sizepb
= sblock
.fs_bsize
, i
= 0; i
< ilevel
; i
++)
163 sizepb
*= NINDIR(&sblock
);
164 nif
= howmany(isize
, sizepb
);
165 if (nif
> NINDIR(&sblock
))
166 nif
= NINDIR(&sblock
);
167 if (idesc
->id_func
== pass1check
&& nif
< NINDIR(&sblock
)) {
168 aplim
= &bp
->b_un
.b_indir
[NINDIR(&sblock
)];
169 for (ap
= &bp
->b_un
.b_indir
[nif
]; ap
< aplim
; ap
++) {
172 sprintf(buf
, "PARTIALLY TRUNCATED INODE I=%lu",
173 (u_long
)idesc
->id_number
);
174 if (dofix(idesc
, buf
)) {
179 flush(fswritefd
, bp
);
181 aplim
= &bp
->b_un
.b_indir
[nif
];
182 for (ap
= bp
->b_un
.b_indir
; ap
< aplim
; ap
++) {
184 idesc
->id_blkno
= *ap
;
188 n
= iblock(idesc
, ilevel
, isize
);
190 bp
->b_flags
&= ~B_INUSE
;
194 if (idesc
->id_type
== DATA
&& isize
> 0) {
195 /* An empty block in a directory XXX */
196 getpathname(pathbuf
, idesc
->id_number
,
198 pfatal("DIRECTORY %s: CONTAINS EMPTY BLOCKS",
200 if (reply("ADJUST LENGTH") == 1) {
201 dp
= ginode(idesc
->id_number
);
202 dp
->di_size
-= isize
;
205 "YOU MUST RERUN FSCK AFTERWARDS\n");
208 bp
->b_flags
&= ~B_INUSE
;
215 bp
->b_flags
&= ~B_INUSE
;
220 * Check that a block in a legal block number.
221 * Return 0 if in range, 1 if out of range.
224 chkrange(ufs_daddr_t blk
, int cnt
)
228 if (cnt
<= 0 || blk
<= 0 || blk
> maxfsblock
||
229 cnt
- 1 > maxfsblock
- blk
)
231 if (cnt
> sblock
.fs_frag
||
232 fragnum(&sblock
, blk
) + cnt
> sblock
.fs_frag
) {
234 printf("bad size: blk %ld, offset %d, size %d\n",
235 (long)blk
, fragnum(&sblock
, blk
), cnt
);
238 c
= dtog(&sblock
, blk
);
239 if (blk
< cgdmin(&sblock
, c
)) {
240 if ((blk
+ cnt
) > cgsblock(&sblock
, c
)) {
242 printf("blk %ld < cgdmin %ld;",
243 (long)blk
, (long)cgdmin(&sblock
, c
));
244 printf(" blk + cnt %ld > cgsbase %ld\n",
246 (long)cgsblock(&sblock
, c
));
251 if ((blk
+ cnt
) > cgbase(&sblock
, c
+1)) {
253 printf("blk %ld >= cgdmin %ld;",
254 (long)blk
, (long)cgdmin(&sblock
, c
));
255 printf(" blk + cnt %ld > sblock.fs_fpg %ld\n",
256 (long)(blk
+ cnt
), (long)sblock
.fs_fpg
);
265 * General purpose interface for reading inodes.
268 ginode(ufs1_ino_t inumber
)
272 if (inumber
< ROOTINO
|| inumber
> maxino
)
273 errx(EEXIT
, "bad inode number %d to ginode", inumber
);
274 if (startinum
== 0 ||
275 inumber
< startinum
|| inumber
>= startinum
+ INOPB(&sblock
)) {
276 iblk
= ino_to_fsba(&sblock
, inumber
);
278 pbp
->b_flags
&= ~B_INUSE
;
279 pbp
= getdatablk(iblk
, sblock
.fs_bsize
);
280 startinum
= (inumber
/ INOPB(&sblock
)) * INOPB(&sblock
);
282 return (&pbp
->b_un
.b_dinode
[inumber
% INOPB(&sblock
)]);
286 * Special purpose version of ginode used to optimize first pass
287 * over all the inodes in numerical order.
289 ufs1_ino_t nextino
, lastinum
;
290 long readcnt
, readpercg
, fullcnt
, inobufsize
, partialcnt
, partialsize
;
291 struct ufs1_dinode
*inodebuf
;
294 getnextinode(ufs1_ino_t inumber
)
298 static struct ufs1_dinode
*dp
;
300 if (inumber
!= nextino
++ || inumber
> maxino
)
301 errx(EEXIT
, "bad inode number %d to nextinode", inumber
);
302 if (inumber
>= lastinum
) {
304 dblk
= fsbtodb(&sblock
, ino_to_fsba(&sblock
, lastinum
));
305 if (readcnt
% readpercg
== 0) {
307 lastinum
+= partialcnt
;
313 * If bread returns an error, it will already have zeroed
314 * out the buffer, so we do not need to do so here.
316 bread(fsreadfd
, (char *)inodebuf
, dblk
, size
);
323 setinodebuf(ufs1_ino_t inum
)
326 if (inum
% sblock
.fs_ipg
!= 0)
327 errx(EEXIT
, "bad inode number %d to setinodebuf", inum
);
332 if (inodebuf
!= NULL
)
334 inobufsize
= blkroundup(&sblock
, INOBUFSIZE
);
335 fullcnt
= inobufsize
/ sizeof(struct ufs1_dinode
);
336 readpercg
= sblock
.fs_ipg
/ fullcnt
;
337 partialcnt
= sblock
.fs_ipg
% fullcnt
;
338 partialsize
= partialcnt
* sizeof(struct ufs1_dinode
);
339 if (partialcnt
!= 0) {
342 partialcnt
= fullcnt
;
343 partialsize
= inobufsize
;
345 if ((inodebuf
= (struct ufs1_dinode
*)malloc((unsigned)inobufsize
)) == NULL
)
346 errx(EEXIT
, "cannot allocate space for inode buffer");
353 if (inodebuf
!= NULL
)
354 free((char *)inodebuf
);
359 * Routines to maintain information about directory inodes.
360 * This is built during the first pass and used during the
361 * second and third passes.
363 * Enter inodes into the cache.
365 static struct memzone inoinfo_zone
;
368 cacheino(struct ufs1_dinode
*dp
, ufs1_ino_t inumber
)
371 struct inoinfo
**inpp
;
374 blks
= howmany(dp
->di_size
, sblock
.fs_bsize
);
376 blks
= NDADDR
+ NIADDR
;
377 inp
= mzalloc(&inoinfo_zone
,
378 sizeof(*inp
) + (blks
- 1) * sizeof(ufs_daddr_t
));
380 errx(EEXIT
, "cannot increase directory list");
381 inpp
= &inphead
[DIRHASH(inumber
)];
382 inp
->i_nexthash
= *inpp
;
384 inp
->i_parent
= inumber
== ROOTINO
? ROOTINO
: (ufs1_ino_t
)0;
385 inp
->i_dotdot
= (ufs1_ino_t
)0;
386 inp
->i_number
= inumber
;
387 inp
->i_isize
= dp
->di_size
;
388 inp
->i_numblks
= blks
* sizeof(ufs_daddr_t
);
389 memmove(&inp
->i_blks
[0], &dp
->di_db
[0], (size_t)inp
->i_numblks
);
390 if (inplast
== listmax
) {
392 inpsort
= (struct inoinfo
**)realloc((char *)inpsort
,
393 (unsigned)listmax
* sizeof(struct inoinfo
*));
395 errx(EEXIT
, "cannot increase directory list");
397 inpsort
[inplast
++] = inp
;
401 * Look up an inode cache structure.
404 getinoinfo(ufs1_ino_t inumber
)
408 for (inp
= inphead
[DIRHASH(inumber
)]; inp
; inp
= inp
->i_nexthash
) {
409 if (inp
->i_number
!= inumber
)
413 errx(EEXIT
, "cannot find inode %d", inumber
);
418 * Clean up all the inode cache structure.
425 mzpurge(&inoinfo_zone
);
426 free((char *)inphead
);
427 free((char *)inpsort
);
428 inphead
= inpsort
= NULL
;
439 clri(struct inodesc
*idesc
, char *type
, int flag
)
441 struct ufs1_dinode
*dp
;
443 dp
= ginode(idesc
->id_number
);
446 (dp
->di_mode
& IFMT
) == IFDIR
? "DIR" : "FILE");
447 pinode(idesc
->id_number
);
449 if (preen
|| reply("CLEAR") == 1) {
451 printf(" (CLEARED)\n");
455 inoinfo(idesc
->id_number
)->ino_state
= USTATE
;
461 findname(struct inodesc
*idesc
)
463 struct direct
*dirp
= idesc
->id_dirp
;
465 if (dirp
->d_ino
!= idesc
->id_parent
|| idesc
->id_entryno
< 2) {
469 memmove(idesc
->id_name
, dirp
->d_name
, (size_t)dirp
->d_namlen
+ 1);
474 findino(struct inodesc
*idesc
)
476 struct direct
*dirp
= idesc
->id_dirp
;
478 if (dirp
->d_ino
== 0)
480 if (strcmp(dirp
->d_name
, idesc
->id_name
) == 0 &&
481 dirp
->d_ino
>= ROOTINO
&& dirp
->d_ino
<= maxino
) {
482 idesc
->id_parent
= dirp
->d_ino
;
489 clearentry(struct inodesc
*idesc
)
491 struct direct
*dirp
= idesc
->id_dirp
;
493 if (dirp
->d_ino
!= idesc
->id_parent
|| idesc
->id_entryno
< 2) {
498 return (STOP
|FOUND
|ALTERED
);
502 pinode(ufs1_ino_t ino
)
504 struct ufs1_dinode
*dp
;
509 printf(" I=%lu ", (u_long
)ino
);
510 if (ino
< ROOTINO
|| ino
> maxino
)
514 if ((pw
= getpwuid((int)dp
->di_uid
)) != NULL
)
515 printf("%s ", pw
->pw_name
);
517 printf("%u ", (unsigned)dp
->di_uid
);
518 printf("MODE=%o\n", dp
->di_mode
);
520 printf("%s: ", cdevname
);
521 printf("SIZE=%ju ", (uintmax_t)dp
->di_size
);
524 printf("MTIME=%12.12s %4.4s ", &p
[4], &p
[20]);
528 blkerror(ufs1_ino_t ino
, char *type
, ufs_daddr_t blk
)
531 pfatal("%d %s I=%u", blk
, type
, ino
);
533 switch (inoinfo(ino
)->ino_state
) {
536 inoinfo(ino
)->ino_state
= FCLEAR
;
540 inoinfo(ino
)->ino_state
= DCLEAR
;
548 errx(EEXIT
, "BAD STATE %d TO BLKERR", inoinfo(ino
)->ino_state
);
554 * allocate an unused inode
557 allocino(ufs1_ino_t request
, int type
)
560 struct ufs1_dinode
*dp
;
561 struct cg
*cgp
= &cgrp
;
566 else if (inoinfo(request
)->ino_state
!= USTATE
)
568 for (ino
= request
; ino
< maxino
; ino
++)
569 if (inoinfo(ino
)->ino_state
== USTATE
)
573 cg
= ino_to_cg(&sblock
, ino
);
574 getblk(&cgblk
, cgtod(&sblock
, cg
), sblock
.fs_cgsize
);
575 if (!cg_chkmagic(cgp
))
576 pfatal("CG %d: BAD MAGIC NUMBER\n", cg
);
577 setbit(cg_inosused(cgp
), ino
% sblock
.fs_ipg
);
578 cgp
->cg_cs
.cs_nifree
--;
579 switch (type
& IFMT
) {
581 inoinfo(ino
)->ino_state
= DSTATE
;
582 cgp
->cg_cs
.cs_ndir
++;
586 inoinfo(ino
)->ino_state
= FSTATE
;
593 dp
->di_db
[0] = allocblk((long)1);
594 if (dp
->di_db
[0] == 0) {
595 inoinfo(ino
)->ino_state
= USTATE
;
600 dp
->di_atime
= time(NULL
);
601 dp
->di_mtime
= dp
->di_ctime
= dp
->di_atime
;
602 dp
->di_mtimensec
= dp
->di_ctimensec
= dp
->di_atimensec
= 0;
603 dp
->di_size
= sblock
.fs_fsize
;
604 dp
->di_blocks
= btodb(sblock
.fs_fsize
);
608 inoinfo(ino
)->ino_type
= IFTODT(type
);
613 * deallocate an inode
616 freeino(ufs1_ino_t ino
)
618 struct inodesc idesc
;
619 struct ufs1_dinode
*dp
;
621 memset(&idesc
, 0, sizeof(struct inodesc
));
622 idesc
.id_type
= ADDR
;
623 idesc
.id_func
= pass4check
;
624 idesc
.id_number
= ino
;
629 inoinfo(ino
)->ino_state
= USTATE
;