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