Initial import from FreeBSD RELENG_4:
[dragonfly.git] / sbin / dump / traverse.c
1 /*-
2  * Copyright (c) 1980, 1988, 1991, 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
35 #if 0
36 static char sccsid[] = "@(#)traverse.c  8.7 (Berkeley) 6/15/95";
37 #endif
38 static const char rcsid[] =
39   "$FreeBSD: src/sbin/dump/traverse.c,v 1.10.2.6 2003/04/14 20:10:35 johan Exp $";
40 #endif /* not lint */
41
42 #include <sys/param.h>
43 #include <sys/stat.h>
44 #ifdef sunos
45 #include <sys/vnode.h>
46
47 #include <ufs/fs.h>
48 #include <ufs/fsdir.h>
49 #include <ufs/inode.h>
50 #else
51 #include <ufs/ufs/dir.h>
52 #include <ufs/ufs/dinode.h>
53 #include <ufs/ffs/fs.h>
54 #endif
55
56 #include <protocols/dumprestore.h>
57
58 #include <ctype.h>
59 #include <stdio.h>
60 #ifdef __STDC__
61 #include <errno.h>
62 #include <string.h>
63 #include <unistd.h>
64 #endif
65
66 #include "dump.h"
67
68 #define HASDUMPEDFILE   0x1
69 #define HASSUBDIRS      0x2
70
71 #ifdef  FS_44INODEFMT
72 typedef quad_t fsizeT;
73 #else
74 typedef long fsizeT;
75 #endif
76
77 static  int dirindir __P((ino_t ino, daddr_t blkno, int level, long *size,
78     long *tapesize, int nodump));
79 static  void dmpindir __P((ino_t ino, daddr_t blk, int level, fsizeT *size));
80 static  int searchdir __P((ino_t ino, daddr_t blkno, long size, long filesize,
81     long *tapesize, int nodump));
82
83 /*
84  * This is an estimation of the number of TP_BSIZE blocks in the file.
85  * It estimates the number of blocks in files with holes by assuming
86  * that all of the blocks accounted for by di_blocks are data blocks
87  * (when some of the blocks are usually used for indirect pointers);
88  * hence the estimate may be high.
89  */
90 long
91 blockest(dp)
92         register struct dinode *dp;
93 {
94         long blkest, sizeest;
95
96         /*
97          * dp->di_size is the size of the file in bytes.
98          * dp->di_blocks stores the number of sectors actually in the file.
99          * If there are more sectors than the size would indicate, this just
100          *      means that there are indirect blocks in the file or unused
101          *      sectors in the last file block; we can safely ignore these
102          *      (blkest = sizeest below).
103          * If the file is bigger than the number of sectors would indicate,
104          *      then the file has holes in it.  In this case we must use the
105          *      block count to estimate the number of data blocks used, but
106          *      we use the actual size for estimating the number of indirect
107          *      dump blocks (sizeest vs. blkest in the indirect block
108          *      calculation).
109          */
110         blkest = howmany(dbtob(dp->di_blocks), TP_BSIZE);
111         sizeest = howmany(dp->di_size, TP_BSIZE);
112         if (blkest > sizeest)
113                 blkest = sizeest;
114         if (dp->di_size > sblock->fs_bsize * NDADDR) {
115                 /* calculate the number of indirect blocks on the dump tape */
116                 blkest +=
117                         howmany(sizeest - NDADDR * sblock->fs_bsize / TP_BSIZE,
118                         TP_NINDIR);
119         }
120         return (blkest + 1);
121 }
122
123 /* Auxiliary macro to pick up files changed since previous dump. */
124 #define CHANGEDSINCE(dp, t) \
125         ((dp)->di_mtime >= (t) || (dp)->di_ctime >= (t))
126
127 /* The WANTTODUMP macro decides whether a file should be dumped. */
128 #ifdef UF_NODUMP
129 #define WANTTODUMP(dp) \
130         (CHANGEDSINCE(dp, spcl.c_ddate) && \
131          (nonodump || ((dp)->di_flags & UF_NODUMP) != UF_NODUMP))
132 #else
133 #define WANTTODUMP(dp) CHANGEDSINCE(dp, spcl.c_ddate)
134 #endif
135
136 /*
137  * Dump pass 1.
138  *
139  * Walk the inode list for a filesystem to find all allocated inodes
140  * that have been modified since the previous dump time. Also, find all
141  * the directories in the filesystem.
142  */
143 int
144 mapfiles(maxino, tapesize)
145         ino_t maxino;
146         long *tapesize;
147 {
148         register int mode;
149         register ino_t ino;
150         register struct dinode *dp;
151         int anydirskipped = 0;
152
153         for (ino = ROOTINO; ino < maxino; ino++) {
154                 dp = getino(ino);
155                 if ((mode = (dp->di_mode & IFMT)) == 0)
156                         continue;
157                 /*
158                  * Everything must go in usedinomap so that a check
159                  * for "in dumpdirmap but not in usedinomap" to detect
160                  * dirs with nodump set has a chance of succeeding
161                  * (this is used in mapdirs()).
162                  */
163                 SETINO(ino, usedinomap);
164                 if (mode == IFDIR)
165                         SETINO(ino, dumpdirmap);
166                 if (WANTTODUMP(dp)) {
167                         SETINO(ino, dumpinomap);
168                         if (mode != IFREG && mode != IFDIR && mode != IFLNK)
169                                 *tapesize += 1;
170                         else
171                                 *tapesize += blockest(dp);
172                         continue;
173                 }
174                 if (mode == IFDIR) {
175                         if (!nonodump && (dp->di_flags & UF_NODUMP))
176                                 CLRINO(ino, usedinomap);
177                         anydirskipped = 1;
178                 }
179         }
180         /*
181          * Restore gets very upset if the root is not dumped,
182          * so ensure that it always is dumped.
183          */
184         SETINO(ROOTINO, dumpinomap);
185         return (anydirskipped);
186 }
187
188 /*
189  * Dump pass 2.
190  *
191  * Scan each directory on the filesystem to see if it has any modified
192  * files in it. If it does, and has not already been added to the dump
193  * list (because it was itself modified), then add it. If a directory
194  * has not been modified itself, contains no modified files and has no
195  * subdirectories, then it can be deleted from the dump list and from
196  * the list of directories. By deleting it from the list of directories,
197  * its parent may now qualify for the same treatment on this or a later
198  * pass using this algorithm.
199  */
200 int
201 mapdirs(maxino, tapesize)
202         ino_t maxino;
203         long *tapesize;
204 {
205         register struct dinode *dp;
206         register int i, isdir, nodump;
207         register char *map;
208         register ino_t ino;
209         struct dinode di;
210         long filesize;
211         int ret, change = 0;
212
213         isdir = 0;              /* XXX just to get gcc to shut up */
214         for (map = dumpdirmap, ino = 1; ino < maxino; ino++) {
215                 if (((ino - 1) % NBBY) == 0)    /* map is offset by 1 */
216                         isdir = *map++;
217                 else
218                         isdir >>= 1;
219                 /*
220                  * If a directory has been removed from usedinomap, it
221                  * either has the nodump flag set, or has inherited
222                  * it.  Although a directory can't be in dumpinomap if
223                  * it isn't in usedinomap, we have to go through it to
224                  * propagate the nodump flag.
225                  */
226                 nodump = !nonodump && (TSTINO(ino, usedinomap) == 0);
227                 if ((isdir & 1) == 0 || (TSTINO(ino, dumpinomap) && !nodump))
228                         continue;
229                 dp = getino(ino);
230                 di = *dp;       /* inode buf may change in searchdir(). */
231                 filesize = di.di_size;
232                 for (ret = 0, i = 0; filesize > 0 && i < NDADDR; i++) {
233                         if (di.di_db[i] != 0)
234                                 ret |= searchdir(ino, di.di_db[i],
235                                         (long)dblksize(sblock, dp, i),
236                                         filesize, tapesize, nodump);
237                         if (ret & HASDUMPEDFILE)
238                                 filesize = 0;
239                         else
240                                 filesize -= sblock->fs_bsize;
241                 }
242                 for (i = 0; filesize > 0 && i < NIADDR; i++) {
243                         if (di.di_ib[i] == 0)
244                                 continue;
245                         ret |= dirindir(ino, di.di_ib[i], i, &filesize,
246                             tapesize, nodump);
247                 }
248                 if (ret & HASDUMPEDFILE) {
249                         SETINO(ino, dumpinomap);
250                         *tapesize += blockest(dp);
251                         change = 1;
252                         continue;
253                 }
254                 if (nodump) {
255                         if (ret & HASSUBDIRS)
256                                 change = 1;     /* subdirs inherit nodump */
257                         CLRINO(ino, dumpdirmap);
258                 } else if ((ret & HASSUBDIRS) == 0)
259                         if (!TSTINO(ino, dumpinomap)) {
260                                 CLRINO(ino, dumpdirmap);
261                                 change = 1;
262                         }
263         }
264         return (change);
265 }
266
267 /*
268  * Read indirect blocks, and pass the data blocks to be searched
269  * as directories. Quit as soon as any entry is found that will
270  * require the directory to be dumped.
271  */
272 static int
273 dirindir(ino, blkno, ind_level, filesize, tapesize, nodump)
274         ino_t ino;
275         daddr_t blkno;
276         int ind_level;
277         long *filesize;
278         long *tapesize;
279         int nodump;
280 {
281         int ret = 0;
282         register int i;
283         daddr_t idblk[MAXNINDIR];
284
285         bread(fsbtodb(sblock, blkno), (char *)idblk, (int)sblock->fs_bsize);
286         if (ind_level <= 0) {
287                 for (i = 0; *filesize > 0 && i < NINDIR(sblock); i++) {
288                         blkno = idblk[i];
289                         if (blkno != 0)
290                                 ret |= searchdir(ino, blkno, sblock->fs_bsize,
291                                         *filesize, tapesize, nodump);
292                         if (ret & HASDUMPEDFILE)
293                                 *filesize = 0;
294                         else
295                                 *filesize -= sblock->fs_bsize;
296                 }
297                 return (ret);
298         }
299         ind_level--;
300         for (i = 0; *filesize > 0 && i < NINDIR(sblock); i++) {
301                 blkno = idblk[i];
302                 if (blkno != 0)
303                         ret |= dirindir(ino, blkno, ind_level, filesize,
304                             tapesize, nodump);
305         }
306         return (ret);
307 }
308
309 /*
310  * Scan a disk block containing directory information looking to see if
311  * any of the entries are on the dump list and to see if the directory
312  * contains any subdirectories.
313  */
314 static int
315 searchdir(ino, blkno, size, filesize, tapesize, nodump)
316         ino_t ino;
317         daddr_t blkno;
318         register long size;
319         long filesize;
320         long *tapesize;
321         int nodump;
322 {
323         register struct direct *dp;
324         register struct dinode *ip;
325         register long loc, ret = 0;
326         char dblk[MAXBSIZE];
327
328         bread(fsbtodb(sblock, blkno), dblk, (int)size);
329         if (filesize < size)
330                 size = filesize;
331         for (loc = 0; loc < size; ) {
332                 dp = (struct direct *)(dblk + loc);
333                 if (dp->d_reclen == 0) {
334                         msg("corrupted directory, inumber %d\n", ino);
335                         break;
336                 }
337                 loc += dp->d_reclen;
338                 if (dp->d_ino == 0)
339                         continue;
340                 if (dp->d_name[0] == '.') {
341                         if (dp->d_name[1] == '\0')
342                                 continue;
343                         if (dp->d_name[1] == '.' && dp->d_name[2] == '\0')
344                                 continue;
345                 }
346                 if (nodump) {
347                         ip = getino(dp->d_ino);
348                         if (TSTINO(dp->d_ino, dumpinomap)) {
349                                 CLRINO(dp->d_ino, dumpinomap);
350                                 CLRINO(dp->d_ino, usedinomap);
351                                 *tapesize -= blockest(ip);
352                         }
353                         /* Add back to dumpdirmap to propagate nodump. */
354                         if ((ip->di_mode & IFMT) == IFDIR) {
355                                 SETINO(dp->d_ino, dumpdirmap);
356                                 ret |= HASSUBDIRS;
357                         }
358                 } else {
359                         if (TSTINO(dp->d_ino, dumpinomap)) {
360                                 ret |= HASDUMPEDFILE;
361                                 if (ret & HASSUBDIRS)
362                                         break;
363                         }
364                         if (TSTINO(dp->d_ino, dumpdirmap)) {
365                                 ret |= HASSUBDIRS;
366                                 if (ret & HASDUMPEDFILE)
367                                         break;
368                         }
369                 }
370         }
371         return (ret);
372 }
373
374 /*
375  * Dump passes 3 and 4.
376  *
377  * Dump the contents of an inode to tape.
378  */
379 void
380 dumpino(dp, ino)
381         register struct dinode *dp;
382         ino_t ino;
383 {
384         int ind_level, cnt;
385         fsizeT size;
386         char buf[TP_BSIZE];
387
388         if (newtape) {
389                 newtape = 0;
390                 dumpmap(dumpinomap, TS_BITS, ino);
391         }
392         CLRINO(ino, dumpinomap);
393         spcl.c_dinode = *dp;
394         spcl.c_type = TS_INODE;
395         spcl.c_count = 0;
396         switch (dp->di_mode & S_IFMT) {
397
398         case 0:
399                 /*
400                  * Freed inode.
401                  */
402                 return;
403
404         case S_IFLNK:
405                 /*
406                  * Check for short symbolic link.
407                  */
408 #ifdef FS_44INODEFMT
409                 if (dp->di_size > 0 &&
410                     dp->di_size < sblock->fs_maxsymlinklen) {
411                         spcl.c_addr[0] = 1;
412                         spcl.c_count = 1;
413                         writeheader(ino);
414                         memmove(buf, dp->di_shortlink, (u_long)dp->di_size);
415                         buf[dp->di_size] = '\0';
416                         writerec(buf, 0);
417                         return;
418                 }
419 #endif
420                 /* fall through */
421
422         case S_IFDIR:
423         case S_IFREG:
424                 if (dp->di_size > 0)
425                         break;
426                 /* fall through */
427
428         case S_IFIFO:
429         case S_IFSOCK:
430         case S_IFCHR:
431         case S_IFBLK:
432                 writeheader(ino);
433                 return;
434
435         default:
436                 msg("Warning: undefined file type 0%o\n", dp->di_mode & IFMT);
437                 return;
438         }
439         if (dp->di_size > NDADDR * sblock->fs_bsize)
440                 cnt = NDADDR * sblock->fs_frag;
441         else
442                 cnt = howmany(dp->di_size, sblock->fs_fsize);
443         blksout(&dp->di_db[0], cnt, ino);
444         if ((size = dp->di_size - NDADDR * sblock->fs_bsize) <= 0)
445                 return;
446         for (ind_level = 0; ind_level < NIADDR; ind_level++) {
447                 dmpindir(ino, dp->di_ib[ind_level], ind_level, &size);
448                 if (size <= 0)
449                         return;
450         }
451 }
452
453 /*
454  * Read indirect blocks, and pass the data blocks to be dumped.
455  */
456 static void
457 dmpindir(ino, blk, ind_level, size)
458         ino_t ino;
459         daddr_t blk;
460         int ind_level;
461         fsizeT *size;
462 {
463         int i, cnt;
464         daddr_t idblk[MAXNINDIR];
465
466         if (blk != 0)
467                 bread(fsbtodb(sblock, blk), (char *)idblk, (int) sblock->fs_bsize);
468         else
469                 memset(idblk, 0, (int)sblock->fs_bsize);
470         if (ind_level <= 0) {
471                 if (*size < NINDIR(sblock) * sblock->fs_bsize)
472                         cnt = howmany(*size, sblock->fs_fsize);
473                 else
474                         cnt = NINDIR(sblock) * sblock->fs_frag;
475                 *size -= NINDIR(sblock) * sblock->fs_bsize;
476                 blksout(&idblk[0], cnt, ino);
477                 return;
478         }
479         ind_level--;
480         for (i = 0; i < NINDIR(sblock); i++) {
481                 dmpindir(ino, idblk[i], ind_level, size);
482                 if (*size <= 0)
483                         return;
484         }
485 }
486
487 /*
488  * Collect up the data into tape record sized buffers and output them.
489  */
490 void
491 blksout(blkp, frags, ino)
492         daddr_t *blkp;
493         int frags;
494         ino_t ino;
495 {
496         register daddr_t *bp;
497         int i, j, count, blks, tbperdb;
498
499         blks = howmany(frags * sblock->fs_fsize, TP_BSIZE);
500         tbperdb = sblock->fs_bsize >> tp_bshift;
501         for (i = 0; i < blks; i += TP_NINDIR) {
502                 if (i + TP_NINDIR > blks)
503                         count = blks;
504                 else
505                         count = i + TP_NINDIR;
506                 for (j = i; j < count; j++)
507                         if (blkp[j / tbperdb] != 0)
508                                 spcl.c_addr[j - i] = 1;
509                         else
510                                 spcl.c_addr[j - i] = 0;
511                 spcl.c_count = count - i;
512                 writeheader(ino);
513                 bp = &blkp[i / tbperdb];
514                 for (j = i; j < count; j += tbperdb, bp++)
515                         if (*bp != 0) {
516                                 if (j + tbperdb <= count)
517                                         dumpblock(*bp, (int)sblock->fs_bsize);
518                                 else
519                                         dumpblock(*bp, (count - j) * TP_BSIZE);
520                         }
521                 spcl.c_type = TS_ADDR;
522         }
523 }
524
525 /*
526  * Dump a map to the tape.
527  */
528 void
529 dumpmap(map, type, ino)
530         char *map;
531         int type;
532         ino_t ino;
533 {
534         register int i;
535         char *cp;
536
537         spcl.c_type = type;
538         spcl.c_count = howmany(mapsize * sizeof(char), TP_BSIZE);
539         writeheader(ino);
540         for (i = 0, cp = map; i < spcl.c_count; i++, cp += TP_BSIZE)
541                 writerec(cp, 0);
542 }
543
544 /*
545  * Write a header record to the dump tape.
546  */
547 void
548 writeheader(ino)
549         ino_t ino;
550 {
551         register int32_t sum, cnt, *lp;
552
553         spcl.c_inumber = ino;
554         spcl.c_magic = NFS_MAGIC;
555         spcl.c_checksum = 0;
556         lp = (int32_t *)&spcl;
557         sum = 0;
558         cnt = sizeof(union u_spcl) / (4 * sizeof(int32_t));
559         while (--cnt >= 0) {
560                 sum += *lp++;
561                 sum += *lp++;
562                 sum += *lp++;
563                 sum += *lp++;
564         }
565         spcl.c_checksum = CHECKSUM - sum;
566         writerec((char *)&spcl, 1);
567 }
568
569 struct dinode *
570 getino(inum)
571         ino_t inum;
572 {
573         static daddr_t minino, maxino;
574         static struct dinode inoblock[MAXINOPB];
575
576         curino = inum;
577         if (inum >= minino && inum < maxino)
578                 return (&inoblock[inum - minino]);
579         bread(fsbtodb(sblock, ino_to_fsba(sblock, inum)), (char *)inoblock,
580             (int)sblock->fs_bsize);
581         minino = inum - (inum % INOPB(sblock));
582         maxino = minino + INOPB(sblock);
583         return (&inoblock[inum - minino]);
584 }
585
586 /*
587  * Read a chunk of data from the disk.
588  * Try to recover from hard errors by reading in sector sized pieces.
589  * Error recovery is attempted at most BREADEMAX times before seeking
590  * consent from the operator to continue.
591  */
592 int     breaderrors = 0;
593 #define BREADEMAX 32
594
595 void
596 bread(blkno, buf, size)
597         daddr_t blkno;
598         char *buf;
599         int size;
600 {
601         int cnt, i;
602
603 loop:
604         cnt = cread(diskfd, buf, size, ((off_t)blkno << dev_bshift));
605         if (cnt == size)
606                 return;
607         if (blkno + (size / dev_bsize) > fsbtodb(sblock, sblock->fs_size)) {
608                 /*
609                  * Trying to read the final fragment.
610                  *
611                  * NB - dump only works in TP_BSIZE blocks, hence
612                  * rounds `dev_bsize' fragments up to TP_BSIZE pieces.
613                  * It should be smarter about not actually trying to
614                  * read more than it can get, but for the time being
615                  * we punt and scale back the read only when it gets
616                  * us into trouble. (mkm 9/25/83)
617                  */
618                 size -= dev_bsize;
619                 goto loop;
620         }
621         if (cnt == -1)
622                 msg("read error from %s: %s: [block %d]: count=%d\n",
623                         disk, strerror(errno), blkno, size);
624         else
625                 msg("short read error from %s: [block %d]: count=%d, got=%d\n",
626                         disk, blkno, size, cnt);
627         if (++breaderrors > BREADEMAX) {
628                 msg("More than %d block read errors from %s\n",
629                         BREADEMAX, disk);
630                 broadcast("DUMP IS AILING!\n");
631                 msg("This is an unrecoverable error.\n");
632                 if (!query("Do you want to attempt to continue?")){
633                         dumpabort(0);
634                         /*NOTREACHED*/
635                 } else
636                         breaderrors = 0;
637         }
638         /*
639          * Zero buffer, then try to read each sector of buffer separately,
640          * and bypass the cache.
641          */
642         memset(buf, 0, size);
643         for (i = 0; i < size; i += dev_bsize, buf += dev_bsize, blkno++) {
644                 if ((cnt = pread(diskfd, buf, (int)dev_bsize,
645                     ((off_t)blkno << dev_bshift))) == dev_bsize)
646                         continue;
647                 if (cnt == -1) {
648                         msg("read error from %s: %s: [sector %d]: count=%d\n",
649                                 disk, strerror(errno), blkno, dev_bsize);
650                         continue;
651                 }
652                 msg("short read error from %s: [sector %d]: count=%d, got=%d\n",
653                         disk, blkno, dev_bsize, cnt);
654         }
655 }