![[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.