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