Merge from vendor branch OPENSSL:
[dragonfly.git] / sbin / fsck / inode.c
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  * @(#)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.6 2004/02/04 17:39:59 joerg Exp $
36  */
37
38 #include <sys/param.h>
39 #include <sys/time.h>
40
41 #include <vfs/ufs/dinode.h>
42 #include <vfs/ufs/dir.h>
43 #include <vfs/ufs/fs.h>
44
45 #include <err.h>
46 #include <pwd.h>
47 #include <string.h>
48
49 #include "fsck.h"
50
51 static ino_t startinum;
52
53 static int iblock(struct inodesc *, long ilevel, quad_t isize);
54
55 int
56 ckinode(struct dinode *dp, register struct inodesc *idesc)
57 {
58         ufs_daddr_t *ap;
59         int ret;
60         long n, ndb, offset;
61         struct dinode dino;
62         quad_t remsize, sizepb;
63         mode_t mode;
64         char pathbuf[MAXPATHLEN + 1];
65
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))
73                 return (KEEPON);
74         dino = *dp;
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)
78                         idesc->id_numfrags =
79                                 numfrags(&sblock, fragroundup(&sblock, offset));
80                 else
81                         idesc->id_numfrags = sblock.fs_frag;
82                 if (*ap == 0) {
83                         if (idesc->id_type == DATA && ndb >= 0) {
84                                 /* An empty block in a directory XXX */
85                                 getpathname(pathbuf, idesc->id_number,
86                                                 idesc->id_number);
87                                 pfatal("DIRECTORY %s: CONTAINS EMPTY BLOCKS",
88                                         pathbuf);
89                                 if (reply("ADJUST LENGTH") == 1) {
90                                         dp = ginode(idesc->id_number);
91                                         dp->di_size = (ap - &dino.di_db[0]) *
92                                             sblock.fs_bsize;
93                                         printf(
94                                             "YOU MUST RERUN FSCK AFTERWARDS\n");
95                                         rerun = 1;
96                                         inodirty();
97                                         
98                                 }
99                         }
100                         continue;
101                 }
102                 idesc->id_blkno = *ap;
103                 if (idesc->id_type == ADDR)
104                         ret = (*idesc->id_func)(idesc);
105                 else
106                         ret = dirscan(idesc);
107                 if (ret & STOP)
108                         return (ret);
109         }
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++) {
114                 if (*ap) {
115                         idesc->id_blkno = *ap;
116                         ret = iblock(idesc, n, remsize);
117                         if (ret & STOP)
118                                 return (ret);
119                 } else {
120                         if (idesc->id_type == DATA && remsize > 0) {
121                                 /* An empty block in a directory XXX */
122                                 getpathname(pathbuf, idesc->id_number,
123                                                 idesc->id_number);
124                                 pfatal("DIRECTORY %s: CONTAINS EMPTY BLOCKS",
125                                         pathbuf);
126                                 if (reply("ADJUST LENGTH") == 1) {
127                                         dp = ginode(idesc->id_number);
128                                         dp->di_size -= remsize;
129                                         remsize = 0;
130                                         printf(
131                                             "YOU MUST RERUN FSCK AFTERWARDS\n");
132                                         rerun = 1;
133                                         inodirty();
134                                         break;
135                                 }
136                         }
137                 }
138                 sizepb *= NINDIR(&sblock);
139                 remsize -= sizepb;
140         }
141         return (KEEPON);
142 }
143
144 static int
145 iblock(struct inodesc *idesc, long ilevel, quad_t isize)
146 {
147         ufs_daddr_t *ap;
148         ufs_daddr_t *aplim;
149         struct bufarea *bp;
150         int i, n, (*func)(), nif;
151         quad_t sizepb;
152         char buf[BUFSIZ];
153         char pathbuf[MAXPATHLEN + 1];
154         struct dinode *dp;
155
156         if (idesc->id_type == ADDR) {
157                 func = idesc->id_func;
158                 if (((n = (*func)(idesc)) & KEEPON) == 0)
159                         return (n);
160         } else
161                 func = dirscan;
162         if (chkrange(idesc->id_blkno, idesc->id_numfrags))
163                 return (SKIP);
164         bp = getdatablk(idesc->id_blkno, sblock.fs_bsize);
165         ilevel--;
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++) {
174                         if (*ap == 0)
175                                 continue;
176                         (void)sprintf(buf, "PARTIALLY TRUNCATED INODE I=%lu",
177                             (u_long)idesc->id_number);
178                         if (dofix(idesc, buf)) {
179                                 *ap = 0;
180                                 dirty(bp);
181                         }
182                 }
183                 flush(fswritefd, bp);
184         }
185         aplim = &bp->b_un.b_indir[nif];
186         for (ap = bp->b_un.b_indir; ap < aplim; ap++) {
187                 if (*ap) {
188                         idesc->id_blkno = *ap;
189                         if (ilevel == 0)
190                                 n = (*func)(idesc);
191                         else
192                                 n = iblock(idesc, ilevel, isize);
193                         if (n & STOP) {
194                                 bp->b_flags &= ~B_INUSE;
195                                 return (n);
196                         }
197                 } else {
198                         if (idesc->id_type == DATA && isize > 0) {
199                                 /* An empty block in a directory XXX */
200                                 getpathname(pathbuf, idesc->id_number,
201                                                 idesc->id_number);
202                                 pfatal("DIRECTORY %s: CONTAINS EMPTY BLOCKS",
203                                         pathbuf);
204                                 if (reply("ADJUST LENGTH") == 1) {
205                                         dp = ginode(idesc->id_number);
206                                         dp->di_size -= isize;
207                                         isize = 0;
208                                         printf(
209                                             "YOU MUST RERUN FSCK AFTERWARDS\n");
210                                         rerun = 1;
211                                         inodirty();
212                                         bp->b_flags &= ~B_INUSE;
213                                         return(STOP);
214                                 }
215                         }
216                 }
217                 isize -= sizepb;
218         }
219         bp->b_flags &= ~B_INUSE;
220         return (KEEPON);
221 }
222
223 /*
224  * Check that a block in a legal block number.
225  * Return 0 if in range, 1 if out of range.
226  */
227 int
228 chkrange(ufs_daddr_t blk, int cnt)
229 {
230         register int c;
231
232         if (cnt <= 0 || blk <= 0 || blk > maxfsblock ||
233             cnt - 1 > maxfsblock - blk)
234                 return (1);
235         if (cnt > sblock.fs_frag ||
236             fragnum(&sblock, blk) + cnt > sblock.fs_frag) {
237                 if (debug)
238                         printf("bad size: blk %ld, offset %d, size %d\n",
239                                 (long)blk, fragnum(&sblock, blk), cnt);
240                 return (1);
241         }
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                                     (long)blk, (long)cgdmin(&sblock, c));
248                                 printf(" blk + cnt %ld > cgsbase %ld\n",
249                                     (long)(blk + cnt),
250                                     (long)cgsblock(&sblock, c));
251                         }
252                         return (1);
253                 }
254         } else {
255                 if ((blk + cnt) > cgbase(&sblock, c+1)) {
256                         if (debug)  {
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);
261                         }
262                         return (1);
263                 }
264         }
265         return (0);
266 }
267
268 /*
269  * General purpose interface for reading inodes.
270  */
271 struct dinode *
272 ginode(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  */
293 ino_t nextino, lastinum;
294 long readcnt, readpercg, fullcnt, inobufsize, partialcnt, partialsize;
295 struct dinode *inodebuf;
296
297 struct dinode *
298 getnextinode(ino_t inumber)
299 {
300         long size;
301         ufs_daddr_t dblk;
302         static struct dinode *dp;
303
304         if (inumber != nextino++ || inumber > maxino)
305                 errx(EEXIT, "bad inode number %d to nextinode", inumber);
306         if (inumber >= lastinum) {
307                 readcnt++;
308                 dblk = fsbtodb(&sblock, ino_to_fsba(&sblock, lastinum));
309                 if (readcnt % readpercg == 0) {
310                         size = partialsize;
311                         lastinum += partialcnt;
312                 } else {
313                         size = inobufsize;
314                         lastinum += fullcnt;
315                 }
316                 /*
317                  * If bread returns an error, it will already have zeroed
318                  * out the buffer, so we do not need to do so here.
319                  */
320                 (void)bread(fsreadfd, (char *)inodebuf, dblk, size);
321                 dp = inodebuf;
322         }
323         return (dp++);
324 }
325
326 void
327 setinodebuf(ino_t inum)
328 {
329
330         if (inum % sblock.fs_ipg != 0)
331                 errx(EEXIT, "bad inode number %d to setinodebuf", inum);
332         startinum = 0;
333         nextino = inum;
334         lastinum = inum;
335         readcnt = 0;
336         if (inodebuf != NULL)
337                 return;
338         inobufsize = blkroundup(&sblock, INOBUFSIZE);
339         fullcnt = inobufsize / sizeof(struct dinode);
340         readpercg = sblock.fs_ipg / fullcnt;
341         partialcnt = sblock.fs_ipg % fullcnt;
342         partialsize = partialcnt * sizeof(struct dinode);
343         if (partialcnt != 0) {
344                 readpercg++;
345         } else {
346                 partialcnt = fullcnt;
347                 partialsize = inobufsize;
348         }
349         if ((inodebuf = (struct dinode *)malloc((unsigned)inobufsize)) == NULL)
350                 errx(EEXIT, "cannot allocate space for inode buffer");
351 }
352
353 void
354 freeinodebuf(void)
355 {
356
357         if (inodebuf != NULL)
358                 free((char *)inodebuf);
359         inodebuf = NULL;
360 }
361
362 /*
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.
366  *
367  * Enter inodes into the cache.
368  */
369 void
370 cacheino(register struct dinode *dp, ino_t inumber)
371 {
372         register struct inoinfo *inp;
373         struct inoinfo **inpp;
374         int blks;
375
376         blks = howmany(dp->di_size, sblock.fs_bsize);
377         if (blks > NDADDR)
378                 blks = NDADDR + NIADDR;
379         inp = (struct inoinfo *)
380                 malloc(sizeof(*inp) + (blks - 1) * sizeof(ufs_daddr_t));
381         if (inp == NULL)
382                 errx(EEXIT, "cannot increase directory list");
383         inpp = &inphead[inumber % dirhash];
384         inp->i_nexthash = *inpp;
385         *inpp = inp;
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) {
393                 listmax += 100;
394                 inpsort = (struct inoinfo **)realloc((char *)inpsort,
395                     (unsigned)listmax * sizeof(struct inoinfo *));
396                 if (inpsort == NULL)
397                         errx(EEXIT, "cannot increase directory list");
398         }
399         inpsort[inplast++] = inp;
400 }
401
402 /*
403  * Look up an inode cache structure.
404  */
405 struct inoinfo *
406 getinoinfo(ino_t inumber)
407 {
408         register struct inoinfo *inp;
409
410         for (inp = inphead[inumber % dirhash]; inp; inp = inp->i_nexthash) {
411                 if (inp->i_number != inumber)
412                         continue;
413                 return (inp);
414         }
415         errx(EEXIT, "cannot find inode %d", inumber);
416         return ((struct inoinfo *)0);
417 }
418
419 /*
420  * Clean up all the inode cache structure.
421  */
422 void
423 inocleanup(void)
424 {
425         register struct inoinfo **inpp;
426
427         if (inphead == NULL)
428                 return;
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;
434 }
435
436 void
437 inodirty(void)
438 {
439
440         dirty(pbp);
441 }
442
443 void
444 clri(register struct inodesc *idesc, char *type, int flag)
445 {
446         register struct dinode *dp;
447
448         dp = ginode(idesc->id_number);
449         if (flag == 1) {
450                 pwarn("%s %s", type,
451                     (dp->di_mode & IFMT) == IFDIR ? "DIR" : "FILE");
452                 pinode(idesc->id_number);
453         }
454         if (preen || reply("CLEAR") == 1) {
455                 if (preen)
456                         printf(" (CLEARED)\n");
457                 n_files--;
458                 (void)ckinode(dp, idesc);
459                 clearinode(dp);
460                 inoinfo(idesc->id_number)->ino_state = USTATE;
461                 inodirty();
462         }
463 }
464
465 int
466 findname(struct inodesc *idesc)
467 {
468         register struct direct *dirp = idesc->id_dirp;
469
470         if (dirp->d_ino != idesc->id_parent || idesc->id_entryno < 2) {
471                 idesc->id_entryno++;
472                 return (KEEPON);
473         }
474         memmove(idesc->id_name, dirp->d_name, (size_t)dirp->d_namlen + 1);
475         return (STOP|FOUND);
476 }
477
478 int
479 findino(struct inodesc *idesc)
480 {
481         register struct direct *dirp = idesc->id_dirp;
482
483         if (dirp->d_ino == 0)
484                 return (KEEPON);
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;
488                 return (STOP|FOUND);
489         }
490         return (KEEPON);
491 }
492
493 int
494 clearentry(struct inodesc *idesc)
495 {
496         register struct direct *dirp = idesc->id_dirp;
497
498         if (dirp->d_ino != idesc->id_parent || idesc->id_entryno < 2) {
499                 idesc->id_entryno++;
500                 return (KEEPON);
501         }
502         dirp->d_ino = 0;
503         return (STOP|FOUND|ALTERED);
504 }
505
506 void
507 pinode(ino_t ino)
508 {
509         register struct dinode *dp;
510         register char *p;
511         struct passwd *pw;
512         time_t t;
513
514         printf(" I=%lu ", (u_long)ino);
515         if (ino < ROOTINO || ino > maxino)
516                 return;
517         dp = ginode(ino);
518         printf(" OWNER=");
519         if ((pw = getpwuid((int)dp->di_uid)) != 0)
520                 printf("%s ", pw->pw_name);
521         else
522                 printf("%u ", (unsigned)dp->di_uid);
523         printf("MODE=%o\n", dp->di_mode);
524         if (preen)
525                 printf("%s: ", cdevname);
526         printf("SIZE=%qu ", dp->di_size);
527         t = dp->di_mtime;
528         p = ctime(&t);
529         printf("MTIME=%12.12s %4.4s ", &p[4], &p[20]);
530 }
531
532 void
533 blkerror(ino_t ino, char *type, ufs_daddr_t blk)
534 {
535
536         pfatal("%ld %s I=%lu", blk, type, ino);
537         printf("\n");
538         switch (inoinfo(ino)->ino_state) {
539
540         case FSTATE:
541                 inoinfo(ino)->ino_state = FCLEAR;
542                 return;
543
544         case DSTATE:
545                 inoinfo(ino)->ino_state = DCLEAR;
546                 return;
547
548         case FCLEAR:
549         case DCLEAR:
550                 return;
551
552         default:
553                 errx(EEXIT, "BAD STATE %d TO BLKERR", inoinfo(ino)->ino_state);
554                 /* NOTREACHED */
555         }
556 }
557
558 /*
559  * allocate an unused inode
560  */
561 ino_t
562 allocino(ino_t request, int type)
563 {
564         register ino_t ino;
565         register struct dinode *dp;
566         struct cg *cgp = &cgrp;
567         int cg;
568
569         if (request == 0)
570                 request = ROOTINO;
571         else if (inoinfo(request)->ino_state != USTATE)
572                 return (0);
573         for (ino = request; ino < maxino; ino++)
574                 if (inoinfo(ino)->ino_state == USTATE)
575                         break;
576         if (ino == maxino)
577                 return (0);
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) {
585         case IFDIR:
586                 inoinfo(ino)->ino_state = DSTATE;
587                 cgp->cg_cs.cs_ndir++;
588                 break;
589         case IFREG:
590         case IFLNK:
591                 inoinfo(ino)->ino_state = FSTATE;
592                 break;
593         default:
594                 return (0);
595         }
596         cgdirty();
597         dp = ginode(ino);
598         dp->di_db[0] = allocblk((long)1);
599         if (dp->di_db[0] == 0) {
600                 inoinfo(ino)->ino_state = USTATE;
601                 return (0);
602         }
603         dp->di_mode = type;
604         dp->di_flags = 0;
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);
610         n_files++;
611         inodirty();
612         if (newinofmt)
613                 inoinfo(ino)->ino_type = IFTODT(type);
614         return (ino);
615 }
616
617 /*
618  * deallocate an inode
619  */
620 void
621 freeino(ino_t ino)
622 {
623         struct inodesc idesc;
624         struct dinode *dp;
625
626         memset(&idesc, 0, sizeof(struct inodesc));
627         idesc.id_type = ADDR;
628         idesc.id_func = pass4check;
629         idesc.id_number = ino;
630         dp = ginode(ino);
631         (void)ckinode(dp, &idesc);
632         clearinode(dp);
633         inodirty();
634         inoinfo(ino)->ino_state = USTATE;
635         n_files--;
636 }