![[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 [Power 6/32 Unix Tahoe 4.2BSD] / cci / usr / src / etc / restore|
Return to symtab.c CVS log | Up to [Power 6/32 Unix Tahoe 4.2BSD] / cci / usr / src / etc / restore |
1.1.1.2 ! 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: */ 1.1 root 6: 1.1.1.2 ! root 7: #ifndef lint ! 8: static char sccsid[] = "@(#)symtab.c 5.1 (Berkeley) 5/28/85"; ! 9: #endif not lint 1.1 root 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; 1.1.1.2 ! root 393: long ntrec; 1.1 root 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; 1.1.1.2 ! root 471: hdr.ntrec = ntrec; 1.1 root 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; 1.1.1.2 ! root 545: if (!bflag) ! 546: newtapebuf(hdr.ntrec); 1.1 root 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.