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