4.3BSD - /usr/src/etc/restore/symtab.c

   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: }

Defined functions

Defined variables

Defined struct's

Defined macros