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