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.11 2006/10/12 04:04:03 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>
52 static ufs1_ino_t startinum
;
54 static int iblock(struct inodesc
*, long ilevel
, quad_t isize
);
57 ckinode(struct ufs1_dinode
*dp
, struct inodesc
*idesc
)
62 struct ufs1_dinode dino
;
63 quad_t remsize
, sizepb
;
65 char pathbuf
[MAXPATHLEN
+ 1];
67 if (idesc
->id_fix
!= IGNORE
)
68 idesc
->id_fix
= DONTKNOW
;
69 idesc
->id_entryno
= 0;
70 idesc
->id_filesize
= dp
->di_size
;
71 mode
= dp
->di_mode
& IFMT
;
72 if (mode
== IFBLK
|| mode
== IFCHR
|| (mode
== IFLNK
&&
73 dp
->di_size
< (unsigned)sblock
.fs_maxsymlinklen
))
76 ndb
= howmany(dino
.di_size
, sblock
.fs_bsize
);
77 for (ap
= &dino
.di_db
[0]; ap
< &dino
.di_db
[NDADDR
]; ap
++) {
78 if (--ndb
== 0 && (offset
= blkoff(&sblock
, dino
.di_size
)) != 0)
80 numfrags(&sblock
, fragroundup(&sblock
, offset
));
82 idesc
->id_numfrags
= sblock
.fs_frag
;
84 if (idesc
->id_type
== DATA
&& ndb
>= 0) {
85 /* An empty block in a directory XXX */
86 getpathname(pathbuf
, idesc
->id_number
,
88 pfatal("DIRECTORY %s: CONTAINS EMPTY BLOCKS",
90 if (reply("ADJUST LENGTH") == 1) {
91 dp
= ginode(idesc
->id_number
);
92 dp
->di_size
= (ap
- &dino
.di_db
[0]) *
95 "YOU MUST RERUN FSCK AFTERWARDS\n");
103 idesc
->id_blkno
= *ap
;
104 if (idesc
->id_type
== ADDR
)
105 ret
= (*idesc
->id_func
)(idesc
);
107 ret
= dirscan(idesc
);
111 idesc
->id_numfrags
= sblock
.fs_frag
;
112 remsize
= dino
.di_size
- sblock
.fs_bsize
* NDADDR
;
113 sizepb
= sblock
.fs_bsize
;
114 for (ap
= &dino
.di_ib
[0], n
= 1; n
<= NIADDR
; ap
++, n
++) {
116 idesc
->id_blkno
= *ap
;
117 ret
= iblock(idesc
, n
, remsize
);
121 if (idesc
->id_type
== DATA
&& remsize
> 0) {
122 /* An empty block in a directory XXX */
123 getpathname(pathbuf
, idesc
->id_number
,
125 pfatal("DIRECTORY %s: CONTAINS EMPTY BLOCKS",
127 if (reply("ADJUST LENGTH") == 1) {
128 dp
= ginode(idesc
->id_number
);
129 dp
->di_size
-= remsize
;
132 "YOU MUST RERUN FSCK AFTERWARDS\n");
139 sizepb
*= NINDIR(&sblock
);
146 iblock(struct inodesc
*idesc
, long ilevel
, quad_t isize
)
151 int i
, n
, (*func
)(), nif
;
154 char pathbuf
[MAXPATHLEN
+ 1];
155 struct ufs1_dinode
*dp
;
157 if (idesc
->id_type
== ADDR
) {
158 func
= idesc
->id_func
;
159 if (((n
= (*func
)(idesc
)) & KEEPON
) == 0)
163 if (chkrange(idesc
->id_blkno
, idesc
->id_numfrags
))
165 bp
= getdatablk(idesc
->id_blkno
, sblock
.fs_bsize
);
167 for (sizepb
= sblock
.fs_bsize
, i
= 0; i
< ilevel
; i
++)
168 sizepb
*= NINDIR(&sblock
);
169 nif
= howmany(isize
, sizepb
);
170 if (nif
> NINDIR(&sblock
))
171 nif
= NINDIR(&sblock
);
172 if (idesc
->id_func
== pass1check
&& nif
< NINDIR(&sblock
)) {
173 aplim
= &bp
->b_un
.b_indir
[NINDIR(&sblock
)];
174 for (ap
= &bp
->b_un
.b_indir
[nif
]; ap
< aplim
; ap
++) {
177 sprintf(buf
, "PARTIALLY TRUNCATED INODE I=%lu",
178 (u_long
)idesc
->id_number
);
179 if (dofix(idesc
, buf
)) {
184 flush(fswritefd
, bp
);
186 aplim
= &bp
->b_un
.b_indir
[nif
];
187 for (ap
= bp
->b_un
.b_indir
; ap
< aplim
; ap
++) {
189 idesc
->id_blkno
= *ap
;
193 n
= iblock(idesc
, ilevel
, isize
);
195 bp
->b_flags
&= ~B_INUSE
;
199 if (idesc
->id_type
== DATA
&& isize
> 0) {
200 /* An empty block in a directory XXX */
201 getpathname(pathbuf
, idesc
->id_number
,
203 pfatal("DIRECTORY %s: CONTAINS EMPTY BLOCKS",
205 if (reply("ADJUST LENGTH") == 1) {
206 dp
= ginode(idesc
->id_number
);
207 dp
->di_size
-= isize
;
210 "YOU MUST RERUN FSCK AFTERWARDS\n");
213 bp
->b_flags
&= ~B_INUSE
;
220 bp
->b_flags
&= ~B_INUSE
;
225 * Check that a block in a legal block number.
226 * Return 0 if in range, 1 if out of range.
229 chkrange(ufs_daddr_t blk
, int cnt
)
233 if (cnt
<= 0 || blk
<= 0 || blk
> maxfsblock
||
234 cnt
- 1 > maxfsblock
- blk
)
236 if (cnt
> sblock
.fs_frag
||
237 fragnum(&sblock
, blk
) + cnt
> sblock
.fs_frag
) {
239 printf("bad size: blk %ld, offset %d, size %d\n",
240 (long)blk
, fragnum(&sblock
, blk
), cnt
);
243 c
= dtog(&sblock
, blk
);
244 if (blk
< cgdmin(&sblock
, c
)) {
245 if ((blk
+ cnt
) > cgsblock(&sblock
, c
)) {
247 printf("blk %ld < cgdmin %ld;",
248 (long)blk
, (long)cgdmin(&sblock
, c
));
249 printf(" blk + cnt %ld > cgsbase %ld\n",
251 (long)cgsblock(&sblock
, c
));
256 if ((blk
+ cnt
) > cgbase(&sblock
, c
+1)) {
258 printf("blk %ld >= cgdmin %ld;",
259 (long)blk
, (long)cgdmin(&sblock
, c
));
260 printf(" blk + cnt %ld > sblock.fs_fpg %ld\n",
261 (long)(blk
+ cnt
), (long)sblock
.fs_fpg
);
270 * General purpose interface for reading inodes.
273 ginode(ufs1_ino_t inumber
)
277 if (inumber
< ROOTINO
|| inumber
> maxino
)
278 errx(EEXIT
, "bad inode number %d to ginode", inumber
);
279 if (startinum
== 0 ||
280 inumber
< startinum
|| inumber
>= startinum
+ INOPB(&sblock
)) {
281 iblk
= ino_to_fsba(&sblock
, inumber
);
283 pbp
->b_flags
&= ~B_INUSE
;
284 pbp
= getdatablk(iblk
, sblock
.fs_bsize
);
285 startinum
= (inumber
/ INOPB(&sblock
)) * INOPB(&sblock
);
287 return (&pbp
->b_un
.b_dinode
[inumber
% INOPB(&sblock
)]);
291 * Special purpose version of ginode used to optimize first pass
292 * over all the inodes in numerical order.
294 ufs1_ino_t nextino
, lastinum
;
295 long readcnt
, readpercg
, fullcnt
, inobufsize
, partialcnt
, partialsize
;
296 struct ufs1_dinode
*inodebuf
;
299 getnextinode(ufs1_ino_t inumber
)
303 static struct ufs1_dinode
*dp
;
305 if (inumber
!= nextino
++ || inumber
> maxino
)
306 errx(EEXIT
, "bad inode number %d to nextinode", inumber
);
307 if (inumber
>= lastinum
) {
309 dblk
= fsbtodb(&sblock
, ino_to_fsba(&sblock
, lastinum
));
310 if (readcnt
% readpercg
== 0) {
312 lastinum
+= partialcnt
;
318 * If bread returns an error, it will already have zeroed
319 * out the buffer, so we do not need to do so here.
321 bread(fsreadfd
, (char *)inodebuf
, dblk
, size
);
328 setinodebuf(ufs1_ino_t inum
)
331 if (inum
% sblock
.fs_ipg
!= 0)
332 errx(EEXIT
, "bad inode number %d to setinodebuf", inum
);
337 if (inodebuf
!= NULL
)
339 inobufsize
= blkroundup(&sblock
, INOBUFSIZE
);
340 fullcnt
= inobufsize
/ sizeof(struct ufs1_dinode
);
341 readpercg
= sblock
.fs_ipg
/ fullcnt
;
342 partialcnt
= sblock
.fs_ipg
% fullcnt
;
343 partialsize
= partialcnt
* sizeof(struct ufs1_dinode
);
344 if (partialcnt
!= 0) {
347 partialcnt
= fullcnt
;
348 partialsize
= inobufsize
;
350 if ((inodebuf
= (struct ufs1_dinode
*)malloc((unsigned)inobufsize
)) == NULL
)
351 errx(EEXIT
, "cannot allocate space for inode buffer");
358 if (inodebuf
!= NULL
)
359 free((char *)inodebuf
);
364 * Routines to maintain information about directory inodes.
365 * This is built during the first pass and used during the
366 * second and third passes.
368 * Enter inodes into the cache.
370 static struct memzone inoinfo_zone
;
373 cacheino(struct ufs1_dinode
*dp
, ufs1_ino_t inumber
)
376 struct inoinfo
**inpp
;
379 blks
= howmany(dp
->di_size
, sblock
.fs_bsize
);
381 blks
= NDADDR
+ NIADDR
;
382 inp
= mzalloc(&inoinfo_zone
,
383 sizeof(*inp
) + (blks
- 1) * sizeof(ufs_daddr_t
));
385 errx(EEXIT
, "cannot increase directory list");
386 inpp
= &inphead
[DIRHASH(inumber
)];
387 inp
->i_nexthash
= *inpp
;
389 inp
->i_parent
= inumber
== ROOTINO
? ROOTINO
: (ufs1_ino_t
)0;
390 inp
->i_dotdot
= (ufs1_ino_t
)0;
391 inp
->i_number
= inumber
;
392 inp
->i_isize
= dp
->di_size
;
393 inp
->i_numblks
= blks
* sizeof(ufs_daddr_t
);
394 memmove(&inp
->i_blks
[0], &dp
->di_db
[0], (size_t)inp
->i_numblks
);
395 if (inplast
== listmax
) {
397 inpsort
= (struct inoinfo
**)realloc((char *)inpsort
,
398 (unsigned)listmax
* sizeof(struct inoinfo
*));
400 errx(EEXIT
, "cannot increase directory list");
402 inpsort
[inplast
++] = inp
;
406 * Look up an inode cache structure.
409 getinoinfo(ufs1_ino_t inumber
)
413 for (inp
= inphead
[DIRHASH(inumber
)]; inp
; inp
= inp
->i_nexthash
) {
414 if (inp
->i_number
!= inumber
)
418 errx(EEXIT
, "cannot find inode %d", inumber
);
423 * Clean up all the inode cache structure.
428 struct inoinfo
**inpp
;
432 mzpurge(&inoinfo_zone
);
433 free((char *)inphead
);
434 free((char *)inpsort
);
435 inphead
= inpsort
= NULL
;
446 clri(struct inodesc
*idesc
, char *type
, int flag
)
448 struct ufs1_dinode
*dp
;
450 dp
= ginode(idesc
->id_number
);
453 (dp
->di_mode
& IFMT
) == IFDIR
? "DIR" : "FILE");
454 pinode(idesc
->id_number
);
456 if (preen
|| reply("CLEAR") == 1) {
458 printf(" (CLEARED)\n");
462 inoinfo(idesc
->id_number
)->ino_state
= USTATE
;
468 findname(struct inodesc
*idesc
)
470 struct direct
*dirp
= idesc
->id_dirp
;
472 if (dirp
->d_ino
!= idesc
->id_parent
|| idesc
->id_entryno
< 2) {
476 memmove(idesc
->id_name
, dirp
->d_name
, (size_t)dirp
->d_namlen
+ 1);
481 findino(struct inodesc
*idesc
)
483 struct direct
*dirp
= idesc
->id_dirp
;
485 if (dirp
->d_ino
== 0)
487 if (strcmp(dirp
->d_name
, idesc
->id_name
) == 0 &&
488 dirp
->d_ino
>= ROOTINO
&& dirp
->d_ino
<= maxino
) {
489 idesc
->id_parent
= dirp
->d_ino
;
496 clearentry(struct inodesc
*idesc
)
498 struct direct
*dirp
= idesc
->id_dirp
;
500 if (dirp
->d_ino
!= idesc
->id_parent
|| idesc
->id_entryno
< 2) {
505 return (STOP
|FOUND
|ALTERED
);
509 pinode(ufs1_ino_t ino
)
511 struct ufs1_dinode
*dp
;
516 printf(" I=%lu ", (u_long
)ino
);
517 if (ino
< ROOTINO
|| ino
> maxino
)
521 if ((pw
= getpwuid((int)dp
->di_uid
)) != 0)
522 printf("%s ", pw
->pw_name
);
524 printf("%u ", (unsigned)dp
->di_uid
);
525 printf("MODE=%o\n", dp
->di_mode
);
527 printf("%s: ", cdevname
);
528 printf("SIZE=%qu ", dp
->di_size
);
531 printf("MTIME=%12.12s %4.4s ", &p
[4], &p
[20]);
535 blkerror(ufs1_ino_t ino
, char *type
, ufs_daddr_t blk
)
538 pfatal("%ld %s I=%lu", blk
, type
, ino
);
540 switch (inoinfo(ino
)->ino_state
) {
543 inoinfo(ino
)->ino_state
= FCLEAR
;
547 inoinfo(ino
)->ino_state
= DCLEAR
;
555 errx(EEXIT
, "BAD STATE %d TO BLKERR", inoinfo(ino
)->ino_state
);
561 * allocate an unused inode
564 allocino(ufs1_ino_t request
, int type
)
567 struct ufs1_dinode
*dp
;
568 struct cg
*cgp
= &cgrp
;
573 else if (inoinfo(request
)->ino_state
!= USTATE
)
575 for (ino
= request
; ino
< maxino
; ino
++)
576 if (inoinfo(ino
)->ino_state
== USTATE
)
580 cg
= ino_to_cg(&sblock
, ino
);
581 getblk(&cgblk
, cgtod(&sblock
, cg
), sblock
.fs_cgsize
);
582 if (!cg_chkmagic(cgp
))
583 pfatal("CG %d: BAD MAGIC NUMBER\n", cg
);
584 setbit(cg_inosused(cgp
), ino
% sblock
.fs_ipg
);
585 cgp
->cg_cs
.cs_nifree
--;
586 switch (type
& IFMT
) {
588 inoinfo(ino
)->ino_state
= DSTATE
;
589 cgp
->cg_cs
.cs_ndir
++;
593 inoinfo(ino
)->ino_state
= FSTATE
;
600 dp
->di_db
[0] = allocblk((long)1);
601 if (dp
->di_db
[0] == 0) {
602 inoinfo(ino
)->ino_state
= USTATE
;
607 dp
->di_atime
= time(NULL
);
608 dp
->di_mtime
= dp
->di_ctime
= dp
->di_atime
;
609 dp
->di_mtimensec
= dp
->di_ctimensec
= dp
->di_atimensec
= 0;
610 dp
->di_size
= sblock
.fs_fsize
;
611 dp
->di_blocks
= btodb(sblock
.fs_fsize
);
615 inoinfo(ino
)->ino_type
= IFTODT(type
);
620 * deallocate an inode
623 freeino(ufs1_ino_t ino
)
625 struct inodesc idesc
;
626 struct ufs1_dinode
*dp
;
628 memset(&idesc
, 0, sizeof(struct inodesc
));
629 idesc
.id_type
= ADDR
;
630 idesc
.id_func
= pass4check
;
631 idesc
.id_number
= ino
;
636 inoinfo(ino
)->ino_state
= USTATE
;