1/*
2 * Copyright (c) 1980, 1986, 1993
3 * The Regents of the University of California. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
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.
20 *
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
31 * SUCH DAMAGE.
32 */
33
34#ifndef lint
35static const char sccsid[] = "@(#)inode.c 8.8 (Berkeley) 4/28/95";
36#endif /* not lint */
37
38#include <sys/param.h>
39#include <sys/time.h>
40
41#include <ufs/ufs/dinode.h>
42#include <ufs/ufs/dir.h>
43#include <ufs/ffs/fs.h>
44
45#include <err.h>
46#include <pwd.h>
47#include <stdio.h>
48#include <stdlib.h>
49#include <string.h>
50
51#include "fsck.h"
52
53static ino_t startinum;
54
55static int iblock __P((struct inodesc *, long ilevel, quad_t isize));
56
57int
58ckinode(dp, idesc)
59 struct dinode *dp;
60 register struct inodesc *idesc;
61{
62 ufs_daddr_t *ap;
63 long ret, n, ndb, offset;
64 struct dinode dino;
65 quad_t remsize, sizepb;
66 mode_t mode;
67 char pathbuf[MAXPATHLEN + 1];
68
69 if (idesc->id_fix != IGNORE)
70 idesc->id_fix = DONTKNOW;
71 idesc->id_entryno = 0;
72 idesc->id_filesize = dp->di_size;
73 mode = dp->di_mode & IFMT;
74 if (mode == IFBLK || mode == IFCHR || (mode == IFLNK &&
75 (dp->di_size < sblock.fs_maxsymlinklen || dp->di_blocks == 0)))
76 return (KEEPON);
77 dino = *dp;
78 ndb = howmany(dino.di_size, sblock.fs_bsize);
79 for (ap = &dino.di_db[0]; ap < &dino.di_db[NDADDR]; ap++) {
80 if (--ndb == 0 && (offset = blkoff(&sblock, dino.di_size)) != 0)
81 idesc->id_numfrags =
82 numfrags(&sblock, fragroundup(&sblock, offset));
83 else
84 idesc->id_numfrags = sblock.fs_frag;
85 if (*ap == 0) {
86 if (idesc->id_type == DATA && ndb >= 0) {
87 /* An empty block in a directory XXX */
88 getpathname(pathbuf, idesc->id_number,
89 idesc->id_number);
90 pfatal("DIRECTORY %s: CONTAINS EMPTY BLOCKS",
91 pathbuf);
92 if (reply("ADJUST LENGTH") == 1) {
93 dp = ginode(idesc->id_number);
94 dp->di_size = (ap - &dino.di_db[0]) *
95 sblock.fs_bsize;
96 printf(
97 "YOU MUST RERUN FSCK AFTERWARDS\n");
98 rerun = 1;
99 inodirty();
100
101 }
102 }
103 continue;
104 }
105 idesc->id_blkno = *ap;
106 if (idesc->id_type == ADDR)
107 ret = (*idesc->id_func)(idesc);
108 else
109 ret = dirscan(idesc);
110 if (ret & STOP)
111 return (ret);
112 }
113 idesc->id_numfrags = sblock.fs_frag;
114 remsize = dino.di_size - sblock.fs_bsize * NDADDR;
115 sizepb = sblock.fs_bsize;
116 for (ap = &dino.di_ib[0], n = 1; n <= NIADDR; ap++, n++) {
117 if (*ap) {
118 idesc->id_blkno = *ap;
119 ret = iblock(idesc, n, remsize);
120 if (ret & STOP)
121 return (ret);
122 } else {
123 if (idesc->id_type == DATA && remsize > 0) {
124 /* An empty block in a directory XXX */
125 getpathname(pathbuf, idesc->id_number,
126 idesc->id_number);
127 pfatal("DIRECTORY %s: CONTAINS EMPTY BLOCKS",
128 pathbuf);
129 if (reply("ADJUST LENGTH") == 1) {
130 dp = ginode(idesc->id_number);
131 dp->di_size -= remsize;
132 remsize = 0;
133 printf(
134 "YOU MUST RERUN FSCK AFTERWARDS\n");
135 rerun = 1;
136 inodirty();
137 break;
138 }
139 }
140 }
141 sizepb *= NINDIR(&sblock);
142 remsize -= sizepb;
143 }
144 return (KEEPON);
145}
146
147static int
148iblock(idesc, ilevel, isize)
149 struct inodesc *idesc;
150 long ilevel;
151 quad_t isize;
152{
153 ufs_daddr_t *ap;
154 ufs_daddr_t *aplim;
155 struct bufarea *bp;
156 int i, n, (*func)(), nif;
157 quad_t sizepb;
158 char buf[BUFSIZ];
159 char pathbuf[MAXPATHLEN + 1];
160 struct dinode *dp;
161
162 if (idesc->id_type == ADDR) {
163 func = idesc->id_func;
164 if (((n = (*func)(idesc)) & KEEPON) == 0)
165 return (n);
166 } else
167 func = dirscan;
168 if (chkrange(idesc->id_blkno, idesc->id_numfrags))
169 return (SKIP);
170 bp = getdatablk(idesc->id_blkno, sblock.fs_bsize);
171 ilevel--;
172 for (sizepb = sblock.fs_bsize, i = 0; i < ilevel; i++)
173 sizepb *= NINDIR(&sblock);
174 nif = howmany(isize , sizepb);
175 if (nif > NINDIR(&sblock))
176 nif = NINDIR(&sblock);
177 if (idesc->id_func == pass1check && nif < NINDIR(&sblock)) {
178 aplim = &bp->b_un.b_indir[NINDIR(&sblock)];
179 for (ap = &bp->b_un.b_indir[nif]; ap < aplim; ap++) {
180 if (*ap == 0)
181 continue;
182 (void)sprintf(buf, "PARTIALLY TRUNCATED INODE I=%lu",
183 idesc->id_number);
184 if (dofix(idesc, buf)) {
185 *ap = 0;
186 dirty(bp);
187 }
188 }
189 flush(fswritefd, bp);
190 }
191 aplim = &bp->b_un.b_indir[nif];
192 for (ap = bp->b_un.b_indir; ap < aplim; ap++) {
193 if (*ap) {
194 idesc->id_blkno = *ap;
195 if (ilevel == 0)
196 n = (*func)(idesc);
197 else
198 n = iblock(idesc, ilevel, isize);
199 if (n & STOP) {
200 bp->b_flags &= ~B_INUSE;
201 return (n);
202 }
203 } else {
204 if (idesc->id_type == DATA && isize > 0) {
205 /* An empty block in a directory XXX */
206 getpathname(pathbuf, idesc->id_number,
207 idesc->id_number);
208 pfatal("DIRECTORY %s: CONTAINS EMPTY BLOCKS",
209 pathbuf);
210 if (reply("ADJUST LENGTH") == 1) {
211 dp = ginode(idesc->id_number);
212 dp->di_size -= isize;
213 isize = 0;
214 printf(
215 "YOU MUST RERUN FSCK AFTERWARDS\n");
216 rerun = 1;
217 inodirty();
218 bp->b_flags &= ~B_INUSE;
219 return(STOP);
220 }
221 }
222 }
223 isize -= sizepb;
224 }
225 bp->b_flags &= ~B_INUSE;
226 return (KEEPON);
227}
228
229/*
230 * Check that a block in a legal block number.
231 * Return 0 if in range, 1 if out of range.
232 */
233int
234chkrange(blk, cnt)
235 ufs_daddr_t blk;
236 int cnt;
237{
238 register int c;
239
240 if ((unsigned)(blk + cnt) > maxfsblock)
241 return (1);
242 c = dtog(&sblock, blk);
243 if (blk < cgdmin(&sblock, c)) {
244 if ((blk + cnt) > cgsblock(&sblock, c)) {
245 if (debug) {
246 printf("blk %ld < cgdmin %ld;",
247 blk, cgdmin(&sblock, c));
248 printf(" blk + cnt %ld > cgsbase %ld\n",
249 blk + cnt, cgsblock(&sblock, c));
250 }
251 return (1);
252 }
253 } else {
254 if ((blk + cnt) > cgbase(&sblock, c+1)) {
255 if (debug) {
256 printf("blk %ld >= cgdmin %ld;",
257 blk, cgdmin(&sblock, c));
258 printf(" blk + cnt %ld > sblock.fs_fpg %ld\n",
259 blk+cnt, sblock.fs_fpg);
260 }
261 return (1);
262 }
263 }
264 return (0);
265}
266
267/*
268 * General purpose interface for reading inodes.
269 */
270struct dinode *
271ginode(inumber)
272 ino_t inumber;
273{
274 ufs_daddr_t iblk;
275
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);
281 if (pbp != 0)
282 pbp->b_flags &= ~B_INUSE;
283 pbp = getdatablk(iblk, sblock.fs_bsize);
284 startinum = (inumber / INOPB(&sblock)) * INOPB(&sblock);
285 }
286 return (&pbp->b_un.b_dinode[inumber % INOPB(&sblock)]);
287}
288
289/*
290 * Special purpose version of ginode used to optimize first pass
291 * over all the inodes in numerical order.
292 */
293ino_t nextino, lastinum;
294long readcnt, readpercg, fullcnt, inobufsize, partialcnt, partialsize;
295struct dinode *inodebuf;
296
297struct dinode *
298getnextinode(inumber)
299 ino_t inumber;
300{
301 long size;
302 ufs_daddr_t dblk;
303 static struct dinode *dp;
304
305 if (inumber != nextino++ || inumber > maxino)
306 errx(EEXIT, "bad inode number %d to nextinode", inumber);
307 if (inumber >= lastinum) {
308 readcnt++;
309 dblk = fsbtodb(&sblock, ino_to_fsba(&sblock, lastinum));
310 if (readcnt % readpercg == 0) {
311 size = partialsize;
312 lastinum += partialcnt;
313 } else {
314 size = inobufsize;
315 lastinum += fullcnt;
316 }
317 (void)bread(fsreadfd, (char *)inodebuf, dblk, size); /* ??? */
318 dp = inodebuf;
319 }
320 return (dp++);
321}
322
323void
324resetinodebuf()
325{
326
327 startinum = 0;
328 nextino = 0;
329 lastinum = 0;
330 readcnt = 0;
331 inobufsize = blkroundup(&sblock, INOBUFSIZE);
332 fullcnt = inobufsize / sizeof(struct dinode);
333 readpercg = sblock.fs_ipg / fullcnt;
334 partialcnt = sblock.fs_ipg % fullcnt;
335 partialsize = partialcnt * sizeof(struct dinode);
336 if (partialcnt != 0) {
337 readpercg++;
338 } else {
339 partialcnt = fullcnt;
340 partialsize = inobufsize;
341 }
342 if (inodebuf == NULL &&
343 (inodebuf = (struct dinode *)malloc((unsigned)inobufsize)) == NULL)
344 errx(EEXIT, "Cannot allocate space for inode buffer");
345 while (nextino < ROOTINO)
346 (void)getnextinode(nextino);
347}
348
349void
350freeinodebuf()
351{
352
353 if (inodebuf != NULL)
354 free((char *)inodebuf);
355 inodebuf = NULL;
356}
357
358/*
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.
362 *
363 * Enter inodes into the cache.
364 */
365void
366cacheino(dp, inumber)
367 register struct dinode *dp;
368 ino_t inumber;
369{
370 register struct inoinfo *inp;
371 struct inoinfo **inpp;
372 unsigned int blks;
373
374 blks = howmany(dp->di_size, sblock.fs_bsize);
375 if (blks > NDADDR)
376 blks = NDADDR + NIADDR;
377 inp = (struct inoinfo *)
378 malloc(sizeof(*inp) + (blks - 1) * sizeof(ufs_daddr_t));
379 if (inp == NULL)
380 return;
381 inpp = &inphead[inumber % numdirs];
382 inp->i_nexthash = *inpp;
383 *inpp = inp;
384 if (inumber == ROOTINO)
385 inp->i_parent = ROOTINO;
386 else
387 inp->i_parent = (ino_t)0;
388 inp->i_dotdot = (ino_t)0;
389 inp->i_number = inumber;
390 inp->i_isize = dp->di_size;
391 inp->i_numblks = blks * sizeof(ufs_daddr_t);
392 memmove(&inp->i_blks[0], &dp->di_db[0], (size_t)inp->i_numblks);
393 if (inplast == listmax) {
394 listmax += 100;
395 inpsort = (struct inoinfo **)realloc((char *)inpsort,
396 (unsigned)listmax * sizeof(struct inoinfo *));
397 if (inpsort == NULL)
398 errx(EEXIT, "cannot increase directory list");
399 }
400 inpsort[inplast++] = inp;
401}
402
403/*
404 * Look up an inode cache structure.
405 */
406struct inoinfo *
407getinoinfo(inumber)
408 ino_t inumber;
409{
410 register struct inoinfo *inp;
411
412 for (inp = inphead[inumber % numdirs]; inp; inp = inp->i_nexthash) {
413 if (inp->i_number != inumber)
414 continue;
415 return (inp);
416 }
417 errx(EEXIT, "cannot find inode %d", inumber);
418 return ((struct inoinfo *)0);
419}
420
421/*
422 * Clean up all the inode cache structure.
423 */
424void
425inocleanup()
426{
427 register struct inoinfo **inpp;
428
429 if (inphead == NULL)
430 return;
431 for (inpp = &inpsort[inplast - 1]; inpp >= inpsort; inpp--)
432 free((char *)(*inpp));
433 free((char *)inphead);
434 free((char *)inpsort);
435 inphead = inpsort = NULL;
436}
437
438void
439inodirty()
440{
441 dirty(pbp);
442}
443
444void
445clri(idesc, type, flag)
446 register struct inodesc *idesc;
447 char *type;
448 int flag;
449{
450 register struct dinode *dp;
451
452 dp = ginode(idesc->id_number);
453 if (flag == 1) {
454 pwarn("%s %s", type,
455 (dp->di_mode & IFMT) == IFDIR ? "DIR" : "FILE");
456 pinode(idesc->id_number);
457 }
458 if (preen || reply("CLEAR") == 1) {
459 if (preen)
460 printf(" (CLEARED)\n");
461 n_files--;
462 (void)ckinode(dp, idesc);
463 clearinode(dp);
464 statemap[idesc->id_number] = USTATE;
465 inodirty();
466 }
467}
468
469int
470findname(idesc)
471 struct inodesc *idesc;
472{
473 register struct direct *dirp = idesc->id_dirp;
474
475 if (dirp->d_ino != idesc->id_parent)
476 return (KEEPON);
477 memmove(idesc->id_name, dirp->d_name, (size_t)dirp->d_namlen + 1);
478 return (STOP|FOUND);
479}
480
481int
482findino(idesc)
483 struct inodesc *idesc;
484{
485 register struct direct *dirp = idesc->id_dirp;
486
487 if (dirp->d_ino == 0)
488 return (KEEPON);
489 if (strcmp(dirp->d_name, idesc->id_name) == 0 &&
490 dirp->d_ino >= ROOTINO && dirp->d_ino <= maxino) {
491 idesc->id_parent = dirp->d_ino;
492 return (STOP|FOUND);
493 }
494 return (KEEPON);
495}
496
497void
498pinode(ino)
499 ino_t ino;
500{
501 register struct dinode *dp;
502 register char *p;
503 struct passwd *pw;
504 char *ctime();
505
506 printf(" I=%lu ", ino);
507 if (ino < ROOTINO || ino > maxino)
508 return;
509 dp = ginode(ino);
510 printf(" OWNER=");
511 if ((pw = getpwuid((int)dp->di_uid)) != 0)
512 printf("%s ", pw->pw_name);
513 else
514 printf("%u ", (unsigned)dp->di_uid);
515 printf("MODE=%o\n", dp->di_mode);
516 if (preen)
517 printf("%s: ", cdevname);
518 printf("SIZE=%qu ", dp->di_size);
519 p = ctime(&dp->di_mtime);
520 printf("MTIME=%12.12s %4.4s ", &p[4], &p[20]);
521}
522
523void
524blkerror(ino, type, blk)
525 ino_t ino;
526 char *type;
527 ufs_daddr_t blk;
528{
529
530 pfatal("%ld %s I=%lu", blk, type, ino);
531 printf("\n");
532 switch (statemap[ino]) {
533
534 case FSTATE:
535 statemap[ino] = FCLEAR;
536 return;
537
538 case DSTATE:
539 statemap[ino] = DCLEAR;
540 return;
541
542 case FCLEAR:
543 case DCLEAR:
544 return;
545
546 default:
547 errx(EEXIT, "BAD STATE %d TO BLKERR", statemap[ino]);
548 /* NOTREACHED */
549 }
550}
551
552/*
553 * allocate an unused inode
554 */
555ino_t
556allocino(request, type)
557 ino_t request;
558 int type;
559{
560 register ino_t ino;
561 register struct dinode *dp;
562
563 if (request == 0)
564 request = ROOTINO;
565 else if (statemap[request] != USTATE)
566 return (0);
567 for (ino = request; ino < maxino; ino++)
568 if (statemap[ino] == USTATE)
569 break;
570 if (ino == maxino)
571 return (0);
572 switch (type & IFMT) {
573 case IFDIR:
574 statemap[ino] = DSTATE;
575 break;
576 case IFREG:
577 case IFLNK:
578 statemap[ino] = FSTATE;
579 break;
580 default:
581 return (0);
582 }
583 dp = ginode(ino);
584 dp->di_db[0] = allocblk((long)1);
585 if (dp->di_db[0] == 0) {
586 statemap[ino] = USTATE;
587 return (0);
588 }
589 dp->di_mode = type;
590 (void)time(&dp->di_atime);
591 dp->di_mtime = dp->di_ctime = dp->di_atime;
592 dp->di_size = sblock.fs_fsize;
593 dp->di_blocks = btodb(sblock.fs_fsize);
594 n_files++;
595 inodirty();
596 if (newinofmt)
597 typemap[ino] = IFTODT(type);
598 return (ino);
599}
600
601/*
602 * deallocate an inode
603 */
604void
605freeino(ino)
606 ino_t ino;
607{
608 struct inodesc idesc;
609 struct dinode *dp;
610
611 memset(&idesc, 0, sizeof(struct inodesc));
612 idesc.id_type = ADDR;
613 idesc.id_func = pass4check;
614 idesc.id_number = ino;
615 dp = ginode(ino);
616 (void)ckinode(dp, &idesc);
617 clearinode(dp);
618 inodirty();
619 statemap[ino] = USTATE;
620 n_files--;
621}