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