![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to symtab.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSD / etc / restore|
Return to symtab.c CVS log | Up to [CSRG BSD Unix] / 43BSD / etc / restore |
1.1 root 1: /*
2: * Copyright (c) 1983 Regents of the University of California.
3: * All rights reserved. The Berkeley software License Agreement
4: * specifies the terms and conditions for redistribution.
5: */
6:
7: #ifndef lint
8: static char sccsid[] = "@(#)symtab.c 5.1 (Berkeley) 5/28/85";
9: #endif not lint
10:
11: /*
12: * These routines maintain the symbol table which tracks the state
13: * of the file system being restored. They provide lookup by either
14: * name or inode number. They also provide for creation, deletion,
15: * and renaming of entries. Because of the dynamic nature of pathnames,
16: * names should not be saved, but always constructed just before they
17: * are needed, by calling "myname".
18: */
19:
20: #include "restore.h"
21: #include <sys/stat.h>
22:
23: /*
24: * The following variables define the inode symbol table.
25: * The primary hash table is dynamically allocated based on
26: * the number of inodes in the file system (maxino), scaled by
27: * HASHFACTOR. The variable "entry" points to the hash table;
28: * the variable "entrytblsize" indicates its size (in entries).
29: */
30: #define HASHFACTOR 5
31: static struct entry **entry;
32: static long entrytblsize;
33:
34: /*
35: * Look up an entry by inode number
36: */
37: struct entry *
38: lookupino(inum)
39: ino_t inum;
40: {
41: register struct entry *ep;
42:
43: if (inum < ROOTINO || inum >= maxino)
44: return (NIL);
45: for (ep = entry[inum % entrytblsize]; ep != NIL; ep = ep->e_next)
46: if (ep->e_ino == inum)
47: return (ep);
48: return (NIL);
49: }
50:
51: /*
52: * Add an entry into the entry table
53: */
54: addino(inum, np)
55: ino_t inum;
56: struct entry *np;
57: {
58: struct entry **epp;
59:
60: if (inum < ROOTINO || inum >= maxino)
61: panic("addino: out of range %d\n", inum);
62: epp = &entry[inum % entrytblsize];
63: np->e_ino = inum;
64: np->e_next = *epp;
65: *epp = np;
66: if (dflag)
67: for (np = np->e_next; np != NIL; np = np->e_next)
68: if (np->e_ino == inum)
69: badentry(np, "duplicate inum");
70: }
71:
72: /*
73: * Delete an entry from the entry table
74: */
75: deleteino(inum)
76: ino_t inum;
77: {
78: register struct entry *next;
79: struct entry **prev;
80:
81: if (inum < ROOTINO || inum >= maxino)
82: panic("deleteino: out of range %d\n", inum);
83: prev = &entry[inum % entrytblsize];
84: for (next = *prev; next != NIL; next = next->e_next) {
85: if (next->e_ino == inum) {
86: next->e_ino = 0;
87: *prev = next->e_next;
88: return;
89: }
90: prev = &next->e_next;
91: }
92: panic("deleteino: %d not found\n", inum);
93: }
94:
95: /*
96: * Look up an entry by name
97: */
98: struct entry *
99: lookupname(name)
100: char *name;
101: {
102: register struct entry *ep;
103: register char *np, *cp;
104: char buf[MAXPATHLEN];
105:
106: cp = name;
107: for (ep = lookupino(ROOTINO); ep != NIL; ep = ep->e_entries) {
108: for (np = buf; *cp != '/' && *cp != '\0'; )
109: *np++ = *cp++;
110: *np = '\0';
111: for ( ; ep != NIL; ep = ep->e_sibling)
112: if (strcmp(ep->e_name, buf) == 0)
113: break;
114: if (ep == NIL)
115: break;
116: if (*cp++ == '\0')
117: return (ep);
118: }
119: return (NIL);
120: }
121:
122: /*
123: * Look up the parent of a pathname
124: */
125: struct entry *
126: lookupparent(name)
127: char *name;
128: {
129: struct entry *ep;
130: char *tailindex;
131:
132: tailindex = rindex(name, '/');
133: if (tailindex == 0)
134: return (NIL);
135: *tailindex = '\0';
136: ep = lookupname(name);
137: *tailindex = '/';
138: if (ep == NIL)
139: return (NIL);
140: if (ep->e_type != NODE)
141: panic("%s is not a directory\n", name);
142: return (ep);
143: }
144:
145: /*
146: * Determine the current pathname of a node or leaf
147: */
148: char *
149: myname(ep)
150: register struct entry *ep;
151: {
152: register char *cp;
153: static char namebuf[MAXPATHLEN];
154:
155: for (cp = &namebuf[MAXPATHLEN - 2]; cp > &namebuf[ep->e_namlen]; ) {
156: cp -= ep->e_namlen;
157: bcopy(ep->e_name, cp, (long)ep->e_namlen);
158: if (ep == lookupino(ROOTINO))
159: return (cp);
160: *(--cp) = '/';
161: ep = ep->e_parent;
162: }
163: panic("%s: pathname too long\n", cp);
164: return(cp);
165: }
166:
167: /*
168: * Unused symbol table entries are linked together on a freelist
169: * headed by the following pointer.
170: */
171: static struct entry *freelist = NIL;
172:
173: /*
174: * add an entry to the symbol table
175: */
176: struct entry *
177: addentry(name, inum, type)
178: char *name;
179: ino_t inum;
180: int type;
181: {
182: register struct entry *np, *ep;
183:
184: if (freelist != NIL) {
185: np = freelist;
186: freelist = np->e_next;
187: bzero((char *)np, (long)sizeof(struct entry));
188: } else {
189: np = (struct entry *)calloc(1, sizeof(struct entry));
190: if (np == NIL)
191: panic("no memory to extend symbol table\n");
192: }
193: np->e_type = type & ~LINK;
194: ep = lookupparent(name);
195: if (ep == NIL) {
196: if (inum != ROOTINO || lookupino(ROOTINO) != NIL)
197: panic("bad name to addentry %s\n", name);
198: np->e_name = savename(name);
199: np->e_namlen = strlen(name);
200: np->e_parent = np;
201: addino(ROOTINO, np);
202: return (np);
203: }
204: np->e_name = savename(rindex(name, '/') + 1);
205: np->e_namlen = strlen(np->e_name);
206: np->e_parent = ep;
207: np->e_sibling = ep->e_entries;
208: ep->e_entries = np;
209: if (type & LINK) {
210: ep = lookupino(inum);
211: if (ep == NIL)
212: panic("link to non-existant name\n");
213: np->e_ino = inum;
214: np->e_links = ep->e_links;
215: ep->e_links = np;
216: } else if (inum != 0) {
217: if (lookupino(inum) != NIL)
218: panic("duplicate entry\n");
219: addino(inum, np);
220: }
221: return (np);
222: }
223:
224: /*
225: * delete an entry from the symbol table
226: */
227: freeentry(ep)
228: register struct entry *ep;
229: {
230: register struct entry *np;
231: ino_t inum;
232:
233: if (ep->e_flags != REMOVED)
234: badentry(ep, "not marked REMOVED");
235: if (ep->e_type == NODE) {
236: if (ep->e_links != NIL)
237: badentry(ep, "freeing referenced directory");
238: if (ep->e_entries != NIL)
239: badentry(ep, "freeing non-empty directory");
240: }
241: if (ep->e_ino != 0) {
242: np = lookupino(ep->e_ino);
243: if (np == NIL)
244: badentry(ep, "lookupino failed");
245: if (np == ep) {
246: inum = ep->e_ino;
247: deleteino(inum);
248: if (ep->e_links != NIL)
249: addino(inum, ep->e_links);
250: } else {
251: for (; np != NIL; np = np->e_links) {
252: if (np->e_links == ep) {
253: np->e_links = ep->e_links;
254: break;
255: }
256: }
257: if (np == NIL)
258: badentry(ep, "link not found");
259: }
260: }
261: removeentry(ep);
262: freename(ep->e_name);
263: ep->e_next = freelist;
264: freelist = ep;
265: }
266:
267: /*
268: * Relocate an entry in the tree structure
269: */
270: moveentry(ep, newname)
271: register struct entry *ep;
272: char *newname;
273: {
274: struct entry *np;
275: char *cp;
276:
277: np = lookupparent(newname);
278: if (np == NIL)
279: badentry(ep, "cannot move ROOT");
280: if (np != ep->e_parent) {
281: removeentry(ep);
282: ep->e_parent = np;
283: ep->e_sibling = np->e_entries;
284: np->e_entries = ep;
285: }
286: cp = rindex(newname, '/') + 1;
287: freename(ep->e_name);
288: ep->e_name = savename(cp);
289: ep->e_namlen = strlen(cp);
290: if (strcmp(gentempname(ep), ep->e_name) == 0)
291: ep->e_flags |= TMPNAME;
292: else
293: ep->e_flags &= ~TMPNAME;
294: }
295:
296: /*
297: * Remove an entry in the tree structure
298: */
299: removeentry(ep)
300: register struct entry *ep;
301: {
302: register struct entry *np;
303:
304: np = ep->e_parent;
305: if (np->e_entries == ep) {
306: np->e_entries = ep->e_sibling;
307: } else {
308: for (np = np->e_entries; np != NIL; np = np->e_sibling) {
309: if (np->e_sibling == ep) {
310: np->e_sibling = ep->e_sibling;
311: break;
312: }
313: }
314: if (np == NIL)
315: badentry(ep, "cannot find entry in parent list");
316: }
317: }
318:
319: /*
320: * Table of unused string entries, sorted by length.
321: *
322: * Entries are allocated in STRTBLINCR sized pieces so that names
323: * of similar lengths can use the same entry. The value of STRTBLINCR
324: * is chosen so that every entry has at least enough space to hold
325: * a "struct strtbl" header. Thus every entry can be linked onto an
326: * apprpriate free list.
327: *
328: * NB. The macro "allocsize" below assumes that "struct strhdr"
329: * has a size that is a power of two.
330: */
331: struct strhdr {
332: struct strhdr *next;
333: };
334:
335: #define STRTBLINCR (sizeof(struct strhdr))
336: #define allocsize(size) (((size) + 1 + STRTBLINCR - 1) & ~(STRTBLINCR - 1))
337:
338: static struct strhdr strtblhdr[allocsize(MAXNAMLEN) / STRTBLINCR];
339:
340: /*
341: * Allocate space for a name. It first looks to see if it already
342: * has an appropriate sized entry, and if not allocates a new one.
343: */
344: char *
345: savename(name)
346: char *name;
347: {
348: struct strhdr *np;
349: long len;
350: char *cp;
351:
352: if (name == NULL)
353: panic("bad name\n");
354: len = strlen(name);
355: np = strtblhdr[len / STRTBLINCR].next;
356: if (np != NULL) {
357: strtblhdr[len / STRTBLINCR].next = np->next;
358: cp = (char *)np;
359: } else {
360: cp = malloc((unsigned)allocsize(len));
361: if (cp == NULL)
362: panic("no space for string table\n");
363: }
364: (void) strcpy(cp, name);
365: return (cp);
366: }
367:
368: /*
369: * Free space for a name. The resulting entry is linked onto the
370: * appropriate free list.
371: */
372: freename(name)
373: char *name;
374: {
375: struct strhdr *tp, *np;
376:
377: tp = &strtblhdr[strlen(name) / STRTBLINCR];
378: np = (struct strhdr *)name;
379: np->next = tp->next;
380: tp->next = np;
381: }
382:
383: /*
384: * Useful quantities placed at the end of a dumped symbol table.
385: */
386: struct symtableheader {
387: long volno;
388: long stringsize;
389: long entrytblsize;
390: time_t dumptime;
391: time_t dumpdate;
392: ino_t maxino;
393: long ntrec;
394: };
395:
396: /*
397: * dump a snapshot of the symbol table
398: */
399: dumpsymtable(filename, checkpt)
400: char *filename;
401: long checkpt;
402: {
403: register struct entry *ep, *tep;
404: register ino_t i;
405: struct entry temp, *tentry;
406: long mynum = 1, stroff = 0;
407: FILE *fd;
408: struct symtableheader hdr;
409:
410: vprintf(stdout, "Check pointing the restore\n");
411: if ((fd = fopen(filename, "w")) == NULL) {
412: perror("fopen");
413: panic("cannot create save file %s for symbol table\n",
414: filename);
415: }
416: clearerr(fd);
417: /*
418: * Assign indicies to each entry
419: * Write out the string entries
420: */
421: for (i = ROOTINO; i < maxino; i++) {
422: for (ep = lookupino(i); ep != NIL; ep = ep->e_links) {
423: ep->e_index = mynum++;
424: (void) fwrite(ep->e_name, sizeof(char),
425: (int)allocsize(ep->e_namlen), fd);
426: }
427: }
428: /*
429: * Convert pointers to indexes, and output
430: */
431: tep = &temp;
432: stroff = 0;
433: for (i = ROOTINO; i < maxino; i++) {
434: for (ep = lookupino(i); ep != NIL; ep = ep->e_links) {
435: bcopy((char *)ep, (char *)tep,
436: (long)sizeof(struct entry));
437: tep->e_name = (char *)stroff;
438: stroff += allocsize(ep->e_namlen);
439: tep->e_parent = (struct entry *)ep->e_parent->e_index;
440: if (ep->e_links != NIL)
441: tep->e_links =
442: (struct entry *)ep->e_links->e_index;
443: if (ep->e_sibling != NIL)
444: tep->e_sibling =
445: (struct entry *)ep->e_sibling->e_index;
446: if (ep->e_entries != NIL)
447: tep->e_entries =
448: (struct entry *)ep->e_entries->e_index;
449: if (ep->e_next != NIL)
450: tep->e_next =
451: (struct entry *)ep->e_next->e_index;
452: (void) fwrite((char *)tep, sizeof(struct entry), 1, fd);
453: }
454: }
455: /*
456: * Convert entry pointers to indexes, and output
457: */
458: for (i = 0; i < entrytblsize; i++) {
459: if (entry[i] == NIL)
460: tentry = NIL;
461: else
462: tentry = (struct entry *)entry[i]->e_index;
463: (void) fwrite((char *)&tentry, sizeof(struct entry *), 1, fd);
464: }
465: hdr.volno = checkpt;
466: hdr.maxino = maxino;
467: hdr.entrytblsize = entrytblsize;
468: hdr.stringsize = stroff;
469: hdr.dumptime = dumptime;
470: hdr.dumpdate = dumpdate;
471: hdr.ntrec = ntrec;
472: (void) fwrite((char *)&hdr, sizeof(struct symtableheader), 1, fd);
473: if (ferror(fd)) {
474: perror("fwrite");
475: panic("output error to file %s writing symbol table\n",
476: filename);
477: }
478: (void) fclose(fd);
479: }
480:
481: /*
482: * Initialize a symbol table from a file
483: */
484: initsymtable(filename)
485: char *filename;
486: {
487: char *base;
488: long tblsize;
489: register struct entry *ep;
490: struct entry *baseep, *lep;
491: struct symtableheader hdr;
492: struct stat stbuf;
493: register long i;
494: int fd;
495:
496: vprintf(stdout, "Initialize symbol table.\n");
497: if (filename == NULL) {
498: entrytblsize = maxino / HASHFACTOR;
499: entry = (struct entry **)
500: calloc((unsigned)entrytblsize, sizeof(struct entry *));
501: if (entry == (struct entry **)NIL)
502: panic("no memory for entry table\n");
503: ep = addentry(".", ROOTINO, NODE);
504: ep->e_flags |= NEW;
505: return;
506: }
507: if ((fd = open(filename, 0)) < 0) {
508: perror("open");
509: panic("cannot open symbol table file %s\n", filename);
510: }
511: if (fstat(fd, &stbuf) < 0) {
512: perror("stat");
513: panic("cannot stat symbol table file %s\n", filename);
514: }
515: tblsize = stbuf.st_size - sizeof(struct symtableheader);
516: base = calloc(sizeof(char), (unsigned)tblsize);
517: if (base == NULL)
518: panic("cannot allocate space for symbol table\n");
519: if (read(fd, base, (int)tblsize) < 0 ||
520: read(fd, (char *)&hdr, sizeof(struct symtableheader)) < 0) {
521: perror("read");
522: panic("cannot read symbol table file %s\n", filename);
523: }
524: switch (command) {
525: case 'r':
526: /*
527: * For normal continuation, insure that we are using
528: * the next incremental tape
529: */
530: if (hdr.dumpdate != dumptime) {
531: if (hdr.dumpdate < dumptime)
532: fprintf(stderr, "Incremental tape too low\n");
533: else
534: fprintf(stderr, "Incremental tape too high\n");
535: done(1);
536: }
537: break;
538: case 'R':
539: /*
540: * For restart, insure that we are using the same tape
541: */
542: curfile.action = SKIP;
543: dumptime = hdr.dumptime;
544: dumpdate = hdr.dumpdate;
545: if (!bflag)
546: newtapebuf(hdr.ntrec);
547: getvol(hdr.volno);
548: break;
549: default:
550: panic("initsymtable called from command %c\n", command);
551: break;
552: }
553: maxino = hdr.maxino;
554: entrytblsize = hdr.entrytblsize;
555: entry = (struct entry **)
556: (base + tblsize - (entrytblsize * sizeof(struct entry *)));
557: baseep = (struct entry *)(base + hdr.stringsize - sizeof(struct entry));
558: lep = (struct entry *)entry;
559: for (i = 0; i < entrytblsize; i++) {
560: if (entry[i] == NIL)
561: continue;
562: entry[i] = &baseep[(long)entry[i]];
563: }
564: for (ep = &baseep[1]; ep < lep; ep++) {
565: ep->e_name = base + (long)ep->e_name;
566: ep->e_parent = &baseep[(long)ep->e_parent];
567: if (ep->e_sibling != NIL)
568: ep->e_sibling = &baseep[(long)ep->e_sibling];
569: if (ep->e_links != NIL)
570: ep->e_links = &baseep[(long)ep->e_links];
571: if (ep->e_entries != NIL)
572: ep->e_entries = &baseep[(long)ep->e_entries];
573: if (ep->e_next != NIL)
574: ep->e_next = &baseep[(long)ep->e_next];
575: }
576: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.