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