![[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] / 43BSDTahoe / etc / restore|
Return to symtab.c CVS log | Up to [CSRG BSD Unix] / 43BSDTahoe / 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.2 (Berkeley) 5/13/88";
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 (Nflag)
412: return;
413: if ((fd = fopen(filename, "w")) == NULL) {
414: perror("fopen");
415: panic("cannot create save file %s for symbol table\n",
416: filename);
417: }
418: clearerr(fd);
419: /*
420: * Assign indicies to each entry
421: * Write out the string entries
422: */
423: for (i = ROOTINO; i < maxino; i++) {
424: for (ep = lookupino(i); ep != NIL; ep = ep->e_links) {
425: ep->e_index = mynum++;
426: (void) fwrite(ep->e_name, sizeof(char),
427: (int)allocsize(ep->e_namlen), fd);
428: }
429: }
430: /*
431: * Convert pointers to indexes, and output
432: */
433: tep = &temp;
434: stroff = 0;
435: for (i = ROOTINO; i < maxino; i++) {
436: for (ep = lookupino(i); ep != NIL; ep = ep->e_links) {
437: bcopy((char *)ep, (char *)tep,
438: (long)sizeof(struct entry));
439: tep->e_name = (char *)stroff;
440: stroff += allocsize(ep->e_namlen);
441: tep->e_parent = (struct entry *)ep->e_parent->e_index;
442: if (ep->e_links != NIL)
443: tep->e_links =
444: (struct entry *)ep->e_links->e_index;
445: if (ep->e_sibling != NIL)
446: tep->e_sibling =
447: (struct entry *)ep->e_sibling->e_index;
448: if (ep->e_entries != NIL)
449: tep->e_entries =
450: (struct entry *)ep->e_entries->e_index;
451: if (ep->e_next != NIL)
452: tep->e_next =
453: (struct entry *)ep->e_next->e_index;
454: (void) fwrite((char *)tep, sizeof(struct entry), 1, fd);
455: }
456: }
457: /*
458: * Convert entry pointers to indexes, and output
459: */
460: for (i = 0; i < entrytblsize; i++) {
461: if (entry[i] == NIL)
462: tentry = NIL;
463: else
464: tentry = (struct entry *)entry[i]->e_index;
465: (void) fwrite((char *)&tentry, sizeof(struct entry *), 1, fd);
466: }
467: hdr.volno = checkpt;
468: hdr.maxino = maxino;
469: hdr.entrytblsize = entrytblsize;
470: hdr.stringsize = stroff;
471: hdr.dumptime = dumptime;
472: hdr.dumpdate = dumpdate;
473: hdr.ntrec = ntrec;
474: (void) fwrite((char *)&hdr, sizeof(struct symtableheader), 1, fd);
475: if (ferror(fd)) {
476: perror("fwrite");
477: panic("output error to file %s writing symbol table\n",
478: filename);
479: }
480: (void) fclose(fd);
481: }
482:
483: /*
484: * Initialize a symbol table from a file
485: */
486: initsymtable(filename)
487: char *filename;
488: {
489: char *base;
490: long tblsize;
491: register struct entry *ep;
492: struct entry *baseep, *lep;
493: struct symtableheader hdr;
494: struct stat stbuf;
495: register long i;
496: int fd;
497:
498: vprintf(stdout, "Initialize symbol table.\n");
499: if (filename == NULL) {
500: entrytblsize = maxino / HASHFACTOR;
501: entry = (struct entry **)
502: calloc((unsigned)entrytblsize, sizeof(struct entry *));
503: if (entry == (struct entry **)NIL)
504: panic("no memory for entry table\n");
505: ep = addentry(".", ROOTINO, NODE);
506: ep->e_flags |= NEW;
507: return;
508: }
509: if ((fd = open(filename, 0)) < 0) {
510: perror("open");
511: panic("cannot open symbol table file %s\n", filename);
512: }
513: if (fstat(fd, &stbuf) < 0) {
514: perror("stat");
515: panic("cannot stat symbol table file %s\n", filename);
516: }
517: tblsize = stbuf.st_size - sizeof(struct symtableheader);
518: base = calloc(sizeof(char), (unsigned)tblsize);
519: if (base == NULL)
520: panic("cannot allocate space for symbol table\n");
521: if (read(fd, base, (int)tblsize) < 0 ||
522: read(fd, (char *)&hdr, sizeof(struct symtableheader)) < 0) {
523: perror("read");
524: panic("cannot read symbol table file %s\n", filename);
525: }
526: switch (command) {
527: case 'r':
528: /*
529: * For normal continuation, insure that we are using
530: * the next incremental tape
531: */
532: if (hdr.dumpdate != dumptime) {
533: if (hdr.dumpdate < dumptime)
534: fprintf(stderr, "Incremental tape too low\n");
535: else
536: fprintf(stderr, "Incremental tape too high\n");
537: done(1);
538: }
539: break;
540: case 'R':
541: /*
542: * For restart, insure that we are using the same tape
543: */
544: curfile.action = SKIP;
545: dumptime = hdr.dumptime;
546: dumpdate = hdr.dumpdate;
547: if (!bflag)
548: newtapebuf(hdr.ntrec);
549: getvol(hdr.volno);
550: break;
551: default:
552: panic("initsymtable called from command %c\n", command);
553: break;
554: }
555: maxino = hdr.maxino;
556: entrytblsize = hdr.entrytblsize;
557: entry = (struct entry **)
558: (base + tblsize - (entrytblsize * sizeof(struct entry *)));
559: baseep = (struct entry *)(base + hdr.stringsize - sizeof(struct entry));
560: lep = (struct entry *)entry;
561: for (i = 0; i < entrytblsize; i++) {
562: if (entry[i] == NIL)
563: continue;
564: entry[i] = &baseep[(long)entry[i]];
565: }
566: for (ep = &baseep[1]; ep < lep; ep++) {
567: ep->e_name = base + (long)ep->e_name;
568: ep->e_parent = &baseep[(long)ep->e_parent];
569: if (ep->e_sibling != NIL)
570: ep->e_sibling = &baseep[(long)ep->e_sibling];
571: if (ep->e_links != NIL)
572: ep->e_links = &baseep[(long)ep->e_links];
573: if (ep->e_entries != NIL)
574: ep->e_entries = &baseep[(long)ep->e_entries];
575: if (ep->e_next != NIL)
576: ep->e_next = &baseep[(long)ep->e_next];
577: }
578: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.