![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to restore.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSDReno / sbin / restore|
Return to restore.c CVS log | Up to [CSRG BSD Unix] / 43BSDReno / sbin / restore |
1.1 root 1: /*
2: * Copyright (c) 1983 The Regents of the University of California.
3: * All rights reserved.
4: *
5: * Redistribution and use in source and binary forms are permitted
6: * provided that: (1) source distributions retain this entire copyright
7: * notice and comment, and (2) distributions including binaries display
8: * the following acknowledgement: ``This product includes software
9: * developed by the University of California, Berkeley and its contributors''
10: * in the documentation or other materials provided with the distribution
11: * and in all advertising materials mentioning features or use of this
12: * software. Neither the name of the University nor the names of its
13: * contributors may be used to endorse or promote products derived
14: * from this software without specific prior written permission.
15: * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
16: * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
17: * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
18: */
19:
20: #ifndef lint
21: static char sccsid[] = "@(#)restore.c 5.7 (Berkeley) 6/1/90";
22: #endif /* not lint */
23:
24: #include "restore.h"
25:
26: /*
27: * This implements the 't' option.
28: * List entries on the tape.
29: */
30: long
31: listfile(name, ino, type)
32: char *name;
33: ino_t ino;
34: int type;
35: {
36: long descend = hflag ? GOOD : FAIL;
37:
38: if (BIT(ino, dumpmap) == 0) {
39: return (descend);
40: }
41: vprintf(stdout, "%s", type == LEAF ? "leaf" : "dir ");
42: fprintf(stdout, "%10d\t%s\n", ino, name);
43: return (descend);
44: }
45:
46: /*
47: * This implements the 'x' option.
48: * Request that new entries be extracted.
49: */
50: long
51: addfile(name, ino, type)
52: char *name;
53: ino_t ino;
54: int type;
55: {
56: register struct entry *ep;
57: long descend = hflag ? GOOD : FAIL;
58: char buf[100];
59:
60: if (BIT(ino, dumpmap) == 0) {
61: dprintf(stdout, "%s: not on the tape\n", name);
62: return (descend);
63: }
64: if (!mflag) {
65: (void) sprintf(buf, "./%u", ino);
66: name = buf;
67: if (type == NODE) {
68: (void) genliteraldir(name, ino);
69: return (descend);
70: }
71: }
72: ep = lookupino(ino);
73: if (ep != NIL) {
74: if (strcmp(name, myname(ep)) == 0) {
75: ep->e_flags |= NEW;
76: return (descend);
77: }
78: type |= LINK;
79: }
80: ep = addentry(name, ino, type);
81: if (type == NODE)
82: newnode(ep);
83: ep->e_flags |= NEW;
84: return (descend);
85: }
86:
87: /*
88: * This is used by the 'i' option to undo previous requests made by addfile.
89: * Delete entries from the request queue.
90: */
91: /* ARGSUSED */
92: long
93: deletefile(name, ino, type)
94: char *name;
95: ino_t ino;
96: int type;
97: {
98: long descend = hflag ? GOOD : FAIL;
99: struct entry *ep;
100:
101: if (BIT(ino, dumpmap) == 0) {
102: return (descend);
103: }
104: ep = lookupino(ino);
105: if (ep != NIL)
106: ep->e_flags &= ~NEW;
107: return (descend);
108: }
109:
110: /*
111: * The following four routines implement the incremental
112: * restore algorithm. The first removes old entries, the second
113: * does renames and calculates the extraction list, the third
114: * cleans up link names missed by the first two, and the final
115: * one deletes old directories.
116: *
117: * Directories cannot be immediately deleted, as they may have
118: * other files in them which need to be moved out first. As
119: * directories to be deleted are found, they are put on the
120: * following deletion list. After all deletions and renames
121: * are done, this list is actually deleted.
122: */
123: static struct entry *removelist;
124:
125: /*
126: * Remove unneeded leaves from the old tree.
127: * Remove directories from the lookup chains.
128: */
129: removeoldleaves()
130: {
131: register struct entry *ep;
132: register ino_t i;
133:
134: vprintf(stdout, "Mark entries to be removed.\n");
135: for (i = ROOTINO + 1; i < maxino; i++) {
136: ep = lookupino(i);
137: if (ep == NIL)
138: continue;
139: if (BIT(i, clrimap))
140: continue;
141: for ( ; ep != NIL; ep = ep->e_links) {
142: dprintf(stdout, "%s: REMOVE\n", myname(ep));
143: if (ep->e_type == LEAF) {
144: removeleaf(ep);
145: freeentry(ep);
146: } else {
147: mktempname(ep);
148: deleteino(ep->e_ino);
149: ep->e_next = removelist;
150: removelist = ep;
151: }
152: }
153: }
154: }
155:
156: /*
157: * For each directory entry on the incremental tape, determine which
158: * category it falls into as follows:
159: * KEEP - entries that are to be left alone.
160: * NEW - new entries to be added.
161: * EXTRACT - files that must be updated with new contents.
162: * LINK - new links to be added.
163: * Renames are done at the same time.
164: */
165: long
166: nodeupdates(name, ino, type)
167: char *name;
168: ino_t ino;
169: int type;
170: {
171: register struct entry *ep, *np, *ip;
172: long descend = GOOD;
173: int lookuptype = 0;
174: int key = 0;
175: /* key values */
176: # define ONTAPE 0x1 /* inode is on the tape */
177: # define INOFND 0x2 /* inode already exists */
178: # define NAMEFND 0x4 /* name already exists */
179: # define MODECHG 0x8 /* mode of inode changed */
180: extern char *keyval();
181:
182: /*
183: * This routine is called once for each element in the
184: * directory hierarchy, with a full path name.
185: * The "type" value is incorrectly specified as LEAF for
186: * directories that are not on the dump tape.
187: *
188: * Check to see if the file is on the tape.
189: */
190: if (BIT(ino, dumpmap))
191: key |= ONTAPE;
192: /*
193: * Check to see if the name exists, and if the name is a link.
194: */
195: np = lookupname(name);
196: if (np != NIL) {
197: key |= NAMEFND;
198: ip = lookupino(np->e_ino);
199: if (ip == NULL)
200: panic("corrupted symbol table\n");
201: if (ip != np)
202: lookuptype = LINK;
203: }
204: /*
205: * Check to see if the inode exists, and if one of its links
206: * corresponds to the name (if one was found).
207: */
208: ip = lookupino(ino);
209: if (ip != NIL) {
210: key |= INOFND;
211: for (ep = ip->e_links; ep != NIL; ep = ep->e_links) {
212: if (ep == np) {
213: ip = ep;
214: break;
215: }
216: }
217: }
218: /*
219: * If both a name and an inode are found, but they do not
220: * correspond to the same file, then both the inode that has
221: * been found and the inode corresponding to the name that
222: * has been found need to be renamed. The current pathname
223: * is the new name for the inode that has been found. Since
224: * all files to be deleted have already been removed, the
225: * named file is either a now unneeded link, or it must live
226: * under a new name in this dump level. If it is a link, it
227: * can be removed. If it is not a link, it is given a
228: * temporary name in anticipation that it will be renamed
229: * when it is later found by inode number.
230: */
231: if (((key & (INOFND|NAMEFND)) == (INOFND|NAMEFND)) && ip != np) {
232: if (lookuptype == LINK) {
233: removeleaf(np);
234: freeentry(np);
235: } else {
236: dprintf(stdout, "name/inode conflict, mktempname %s\n",
237: myname(np));
238: mktempname(np);
239: }
240: np = NIL;
241: key &= ~NAMEFND;
242: }
243: if ((key & ONTAPE) &&
244: (((key & INOFND) && ip->e_type != type) ||
245: ((key & NAMEFND) && np->e_type != type)))
246: key |= MODECHG;
247:
248: /*
249: * Decide on the disposition of the file based on its flags.
250: * Note that we have already handled the case in which
251: * a name and inode are found that correspond to different files.
252: * Thus if both NAMEFND and INOFND are set then ip == np.
253: */
254: switch (key) {
255:
256: /*
257: * A previously existing file has been found.
258: * Mark it as KEEP so that other links to the inode can be
259: * detected, and so that it will not be reclaimed by the search
260: * for unreferenced names.
261: */
262: case INOFND|NAMEFND:
263: ip->e_flags |= KEEP;
264: dprintf(stdout, "[%s] %s: %s\n", keyval(key), name,
265: flagvalues(ip));
266: break;
267:
268: /*
269: * A file on the tape has a name which is the same as a name
270: * corresponding to a different file in the previous dump.
271: * Since all files to be deleted have already been removed,
272: * this file is either a now unneeded link, or it must live
273: * under a new name in this dump level. If it is a link, it
274: * can simply be removed. If it is not a link, it is given a
275: * temporary name in anticipation that it will be renamed
276: * when it is later found by inode number (see INOFND case
277: * below). The entry is then treated as a new file.
278: */
279: case ONTAPE|NAMEFND:
280: case ONTAPE|NAMEFND|MODECHG:
281: if (lookuptype == LINK) {
282: removeleaf(np);
283: freeentry(np);
284: } else {
285: mktempname(np);
286: }
287: /* fall through */
288:
289: /*
290: * A previously non-existent file.
291: * Add it to the file system, and request its extraction.
292: * If it is a directory, create it immediately.
293: * (Since the name is unused there can be no conflict)
294: */
295: case ONTAPE:
296: ep = addentry(name, ino, type);
297: if (type == NODE)
298: newnode(ep);
299: ep->e_flags |= NEW|KEEP;
300: dprintf(stdout, "[%s] %s: %s\n", keyval(key), name,
301: flagvalues(ep));
302: break;
303:
304: /*
305: * A file with the same inode number, but a different
306: * name has been found. If the other name has not already
307: * been found (indicated by the KEEP flag, see above) then
308: * this must be a new name for the file, and it is renamed.
309: * If the other name has been found then this must be a
310: * link to the file. Hard links to directories are not
311: * permitted, and are either deleted or converted to
312: * symbolic links. Finally, if the file is on the tape,
313: * a request is made to extract it.
314: */
315: case ONTAPE|INOFND:
316: if (type == LEAF && (ip->e_flags & KEEP) == 0)
317: ip->e_flags |= EXTRACT;
318: /* fall through */
319: case INOFND:
320: if ((ip->e_flags & KEEP) == 0) {
321: renameit(myname(ip), name);
322: moveentry(ip, name);
323: ip->e_flags |= KEEP;
324: dprintf(stdout, "[%s] %s: %s\n", keyval(key), name,
325: flagvalues(ip));
326: break;
327: }
328: if (ip->e_type == NODE) {
329: descend = FAIL;
330: fprintf(stderr,
331: "deleted hard link %s to directory %s\n",
332: name, myname(ip));
333: break;
334: }
335: ep = addentry(name, ino, type|LINK);
336: ep->e_flags |= NEW;
337: dprintf(stdout, "[%s] %s: %s|LINK\n", keyval(key), name,
338: flagvalues(ep));
339: break;
340:
341: /*
342: * A previously known file which is to be updated.
343: */
344: case ONTAPE|INOFND|NAMEFND:
345: if (type == LEAF && lookuptype != LINK)
346: np->e_flags |= EXTRACT;
347: np->e_flags |= KEEP;
348: dprintf(stdout, "[%s] %s: %s\n", keyval(key), name,
349: flagvalues(np));
350: break;
351:
352: /*
353: * An inode is being reused in a completely different way.
354: * Normally an extract can simply do an "unlink" followed
355: * by a "creat". Here we must do effectively the same
356: * thing. The complications arise because we cannot really
357: * delete a directory since it may still contain files
358: * that we need to rename, so we delete it from the symbol
359: * table, and put it on the list to be deleted eventually.
360: * Conversely if a directory is to be created, it must be
361: * done immediately, rather than waiting until the
362: * extraction phase.
363: */
364: case ONTAPE|INOFND|MODECHG:
365: case ONTAPE|INOFND|NAMEFND|MODECHG:
366: if (ip->e_flags & KEEP) {
367: badentry(ip, "cannot KEEP and change modes");
368: break;
369: }
370: if (ip->e_type == LEAF) {
371: /* changing from leaf to node */
372: removeleaf(ip);
373: freeentry(ip);
374: ip = addentry(name, ino, type);
375: newnode(ip);
376: } else {
377: /* changing from node to leaf */
378: if ((ip->e_flags & TMPNAME) == 0)
379: mktempname(ip);
380: deleteino(ip->e_ino);
381: ip->e_next = removelist;
382: removelist = ip;
383: ip = addentry(name, ino, type);
384: }
385: ip->e_flags |= NEW|KEEP;
386: dprintf(stdout, "[%s] %s: %s\n", keyval(key), name,
387: flagvalues(ip));
388: break;
389:
390: /*
391: * A hard link to a diirectory that has been removed.
392: * Ignore it.
393: */
394: case NAMEFND:
395: dprintf(stdout, "[%s] %s: Extraneous name\n", keyval(key),
396: name);
397: descend = FAIL;
398: break;
399:
400: /*
401: * If we find a directory entry for a file that is not on
402: * the tape, then we must have found a file that was created
403: * while the dump was in progress. Since we have no contents
404: * for it, we discard the name knowing that it will be on the
405: * next incremental tape.
406: */
407: case NIL:
408: fprintf(stderr, "%s: (inode %d) not found on tape\n",
409: name, ino);
410: break;
411:
412: /*
413: * If any of these arise, something is grievously wrong with
414: * the current state of the symbol table.
415: */
416: case INOFND|NAMEFND|MODECHG:
417: case NAMEFND|MODECHG:
418: case INOFND|MODECHG:
419: fprintf(stderr, "[%s] %s: inconsistent state\n", keyval(key),
420: name);
421: break;
422:
423: /*
424: * These states "cannot" arise for any state of the symbol table.
425: */
426: case ONTAPE|MODECHG:
427: case MODECHG:
428: default:
429: panic("[%s] %s: impossible state\n", keyval(key), name);
430: break;
431: }
432: return (descend);
433: }
434:
435: /*
436: * Calculate the active flags in a key.
437: */
438: char *
439: keyval(key)
440: int key;
441: {
442: static char keybuf[32];
443:
444: (void) strcpy(keybuf, "|NIL");
445: keybuf[0] = '\0';
446: if (key & ONTAPE)
447: (void) strcat(keybuf, "|ONTAPE");
448: if (key & INOFND)
449: (void) strcat(keybuf, "|INOFND");
450: if (key & NAMEFND)
451: (void) strcat(keybuf, "|NAMEFND");
452: if (key & MODECHG)
453: (void) strcat(keybuf, "|MODECHG");
454: return (&keybuf[1]);
455: }
456:
457: /*
458: * Find unreferenced link names.
459: */
460: findunreflinks()
461: {
462: register struct entry *ep, *np;
463: register ino_t i;
464:
465: vprintf(stdout, "Find unreferenced names.\n");
466: for (i = ROOTINO; i < maxino; i++) {
467: ep = lookupino(i);
468: if (ep == NIL || ep->e_type == LEAF || BIT(i, dumpmap) == 0)
469: continue;
470: for (np = ep->e_entries; np != NIL; np = np->e_sibling) {
471: if (np->e_flags == 0) {
472: dprintf(stdout,
473: "%s: remove unreferenced name\n",
474: myname(np));
475: removeleaf(np);
476: freeentry(np);
477: }
478: }
479: }
480: /*
481: * Any leaves remaining in removed directories is unreferenced.
482: */
483: for (ep = removelist; ep != NIL; ep = ep->e_next) {
484: for (np = ep->e_entries; np != NIL; np = np->e_sibling) {
485: if (np->e_type == LEAF) {
486: if (np->e_flags != 0)
487: badentry(np, "unreferenced with flags");
488: dprintf(stdout,
489: "%s: remove unreferenced name\n",
490: myname(np));
491: removeleaf(np);
492: freeentry(np);
493: }
494: }
495: }
496: }
497:
498: /*
499: * Remove old nodes (directories).
500: * Note that this routine runs in O(N*D) where:
501: * N is the number of directory entries to be removed.
502: * D is the maximum depth of the tree.
503: * If N == D this can be quite slow. If the list were
504: * topologically sorted, the deletion could be done in
505: * time O(N).
506: */
507: removeoldnodes()
508: {
509: register struct entry *ep, **prev;
510: long change;
511:
512: vprintf(stdout, "Remove old nodes (directories).\n");
513: do {
514: change = 0;
515: prev = &removelist;
516: for (ep = removelist; ep != NIL; ep = *prev) {
517: if (ep->e_entries != NIL) {
518: prev = &ep->e_next;
519: continue;
520: }
521: *prev = ep->e_next;
522: removenode(ep);
523: freeentry(ep);
524: change++;
525: }
526: } while (change);
527: for (ep = removelist; ep != NIL; ep = ep->e_next)
528: badentry(ep, "cannot remove, non-empty");
529: }
530:
531: /*
532: * This is the routine used to extract files for the 'r' command.
533: * Extract new leaves.
534: */
535: createleaves(symtabfile)
536: char *symtabfile;
537: {
538: register struct entry *ep;
539: ino_t first;
540: long curvol;
541:
542: if (command == 'R') {
543: vprintf(stdout, "Continue extraction of new leaves\n");
544: } else {
545: vprintf(stdout, "Extract new leaves.\n");
546: dumpsymtable(symtabfile, volno);
547: }
548: first = lowerbnd(ROOTINO);
549: curvol = volno;
550: while (curfile.ino < maxino) {
551: first = lowerbnd(first);
552: /*
553: * If the next available file is not the one which we
554: * expect then we have missed one or more files. Since
555: * we do not request files that were not on the tape,
556: * the lost files must have been due to a tape read error,
557: * or a file that was removed while the dump was in progress.
558: */
559: while (first < curfile.ino) {
560: ep = lookupino(first);
561: if (ep == NIL)
562: panic("%d: bad first\n", first);
563: fprintf(stderr, "%s: not found on tape\n", myname(ep));
564: ep->e_flags &= ~(NEW|EXTRACT);
565: first = lowerbnd(first);
566: }
567: /*
568: * If we find files on the tape that have no corresponding
569: * directory entries, then we must have found a file that
570: * was created while the dump was in progress. Since we have
571: * no name for it, we discard it knowing that it will be
572: * on the next incremental tape.
573: */
574: if (first != curfile.ino) {
575: fprintf(stderr, "expected next file %d, got %d\n",
576: first, curfile.ino);
577: skipfile();
578: goto next;
579: }
580: ep = lookupino(curfile.ino);
581: if (ep == NIL)
582: panic("unknown file on tape\n");
583: if ((ep->e_flags & (NEW|EXTRACT)) == 0)
584: badentry(ep, "unexpected file on tape");
585: /*
586: * If the file is to be extracted, then the old file must
587: * be removed since its type may change from one leaf type
588: * to another (eg "file" to "character special").
589: */
590: if ((ep->e_flags & EXTRACT) != 0) {
591: removeleaf(ep);
592: ep->e_flags &= ~REMOVED;
593: }
594: (void) extractfile(myname(ep));
595: ep->e_flags &= ~(NEW|EXTRACT);
596: /*
597: * We checkpoint the restore after every tape reel, so
598: * as to simplify the amount of work re quired by the
599: * 'R' command.
600: */
601: next:
602: if (curvol != volno) {
603: dumpsymtable(symtabfile, volno);
604: skipmaps();
605: curvol = volno;
606: }
607: }
608: }
609:
610: /*
611: * This is the routine used to extract files for the 'x' and 'i' commands.
612: * Efficiently extract a subset of the files on a tape.
613: */
614: createfiles()
615: {
616: register ino_t first, next, last;
617: register struct entry *ep;
618: long curvol;
619:
620: vprintf(stdout, "Extract requested files\n");
621: curfile.action = SKIP;
622: getvol((long)1);
623: skipmaps();
624: skipdirs();
625: first = lowerbnd(ROOTINO);
626: last = upperbnd(maxino - 1);
627: for (;;) {
628: first = lowerbnd(first);
629: last = upperbnd(last);
630: /*
631: * Check to see if any files remain to be extracted
632: */
633: if (first > last)
634: return;
635: /*
636: * Reject any volumes with inodes greater
637: * than the last one needed
638: */
639: while (curfile.ino > last) {
640: curfile.action = SKIP;
641: getvol((long)0);
642: skipmaps();
643: skipdirs();
644: }
645: /*
646: * Decide on the next inode needed.
647: * Skip across the inodes until it is found
648: * or an out of order volume change is encountered
649: */
650: next = lowerbnd(curfile.ino);
651: do {
652: curvol = volno;
653: while (next > curfile.ino && volno == curvol)
654: skipfile();
655: skipmaps();
656: skipdirs();
657: } while (volno == curvol + 1);
658: /*
659: * If volume change out of order occurred the
660: * current state must be recalculated
661: */
662: if (volno != curvol)
663: continue;
664: /*
665: * If the current inode is greater than the one we were
666: * looking for then we missed the one we were looking for.
667: * Since we only attempt to extract files listed in the
668: * dump map, the lost files must have been due to a tape
669: * read error, or a file that was removed while the dump
670: * was in progress. Thus we report all requested files
671: * between the one we were looking for, and the one we
672: * found as missing, and delete their request flags.
673: */
674: while (next < curfile.ino) {
675: ep = lookupino(next);
676: if (ep == NIL)
677: panic("corrupted symbol table\n");
678: fprintf(stderr, "%s: not found on tape\n", myname(ep));
679: ep->e_flags &= ~NEW;
680: next = lowerbnd(next);
681: }
682: /*
683: * The current inode is the one that we are looking for,
684: * so extract it per its requested name.
685: */
686: if (next == curfile.ino && next <= last) {
687: ep = lookupino(next);
688: if (ep == NIL)
689: panic("corrupted symbol table\n");
690: (void) extractfile(myname(ep));
691: ep->e_flags &= ~NEW;
692: if (volno != curvol)
693: skipmaps();
694: }
695: }
696: }
697:
698: /*
699: * Add links.
700: */
701: createlinks()
702: {
703: register struct entry *np, *ep;
704: register ino_t i;
705: char name[BUFSIZ];
706:
707: vprintf(stdout, "Add links\n");
708: for (i = ROOTINO; i < maxino; i++) {
709: ep = lookupino(i);
710: if (ep == NIL)
711: continue;
712: for (np = ep->e_links; np != NIL; np = np->e_links) {
713: if ((np->e_flags & NEW) == 0)
714: continue;
715: (void) strcpy(name, myname(ep));
716: if (ep->e_type == NODE) {
717: (void) linkit(name, myname(np), SYMLINK);
718: } else {
719: (void) linkit(name, myname(np), HARDLINK);
720: }
721: np->e_flags &= ~NEW;
722: }
723: }
724: }
725:
726: /*
727: * Check the symbol table.
728: * We do this to insure that all the requested work was done, and
729: * that no temporary names remain.
730: */
731: checkrestore()
732: {
733: register struct entry *ep;
734: register ino_t i;
735:
736: vprintf(stdout, "Check the symbol table.\n");
737: for (i = ROOTINO; i < maxino; i++) {
738: for (ep = lookupino(i); ep != NIL; ep = ep->e_links) {
739: ep->e_flags &= ~KEEP;
740: if (ep->e_type == NODE)
741: ep->e_flags &= ~(NEW|EXISTED);
742: if (ep->e_flags != NULL)
743: badentry(ep, "incomplete operations");
744: }
745: }
746: }
747:
748: /*
749: * Compare with the directory structure on the tape
750: * A paranoid check that things are as they should be.
751: */
752: long
753: verifyfile(name, ino, type)
754: char *name;
755: ino_t ino;
756: int type;
757: {
758: struct entry *np, *ep;
759: long descend = GOOD;
760:
761: ep = lookupname(name);
762: if (ep == NIL) {
763: fprintf(stderr, "Warning: missing name %s\n", name);
764: return (FAIL);
765: }
766: np = lookupino(ino);
767: if (np != ep)
768: descend = FAIL;
769: for ( ; np != NIL; np = np->e_links)
770: if (np == ep)
771: break;
772: if (np == NIL)
773: panic("missing inumber %d\n", ino);
774: if (ep->e_type == LEAF && type != LEAF)
775: badentry(ep, "type should be LEAF");
776: return (descend);
777: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.