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