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