| 1 | #ifndef lint |
| 2 | static char sccsid[] = "@(#)symtab.c 3.17 (Berkeley) 85/03/24"; |
| 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 | |
| 19 | /* |
| 20 | * The following variables define the inode symbol table. |
| 21 | * The primary hash table is dynamically allocated based on |
| 22 | * the number of inodes in the file system (maxino), scaled by |
| 23 | * HASHFACTOR. The variable "entry" points to the hash table; |
| 24 | * the variable "entrytblsize" indicates its size (in entries). |
| 25 | */ |
| 26 | #define HASHFACTOR 5 |
| 27 | static struct entry **entry; |
| 28 | static long entrytblsize; |
| 29 | |
| 30 | /* |
| 31 | * Look up an entry by inode number |
| 32 | */ |
| 33 | struct entry * |
| 34 | lookupino(inum) |
| 35 | ino_t inum; |
| 36 | { |
| 37 | register struct entry *ep; |
| 38 | |
| 39 | if (inum < ROOTINO || inum >= maxino) |
| 40 | return (NIL); |
| 41 | for (ep = entry[inum % entrytblsize]; ep != NIL; ep = ep->e_next) |
| 42 | if (ep->e_ino == inum) |
| 43 | return (ep); |
| 44 | return (NIL); |
| 45 | } |
| 46 | |
| 47 | /* |
| 48 | * Add an entry into the entry table |
| 49 | */ |
| 50 | addino(inum, np) |
| 51 | ino_t inum; |
| 52 | struct entry *np; |
| 53 | { |
| 54 | struct entry **epp; |
| 55 | |
| 56 | if (inum < ROOTINO || inum >= maxino) |
| 57 | panic("addino: out of range %d\n", inum); |
| 58 | epp = &entry[inum % entrytblsize]; |
| 59 | np->e_ino = inum; |
| 60 | np->e_next = *epp; |
| 61 | *epp = np; |
| 62 | if (dflag) |
| 63 | for (np = np->e_next; np != NIL; np = np->e_next) |
| 64 | if (np->e_ino == inum) |
| 65 | badentry(np, "duplicate inum"); |
| 66 | } |
| 67 | |
| 68 | /* |
| 69 | * Delete an entry from the entry table |
| 70 | */ |
| 71 | deleteino(inum) |
| 72 | ino_t inum; |
| 73 | { |
| 74 | register struct entry *next; |
| 75 | struct entry **prev; |
| 76 | |
| 77 | if (inum < ROOTINO || inum >= maxino) |
| 78 | panic("deleteino: out of range %d\n", inum); |
| 79 | prev = &entry[inum % entrytblsize]; |
| 80 | for (next = *prev; next != NIL; next = next->e_next) { |
| 81 | if (next->e_ino == inum) { |
| 82 | next->e_ino = 0; |
| 83 | *prev = next->e_next; |
| 84 | return; |
| 85 | } |
| 86 | prev = &next->e_next; |
| 87 | } |
| 88 | panic("deleteino: %d not found\n", inum); |
| 89 | } |
| 90 | |
| 91 | /* |
| 92 | * Look up an entry by name |
| 93 | */ |
| 94 | struct entry * |
| 95 | lookupname(name) |
| 96 | char *name; |
| 97 | { |
| 98 | register struct entry *ep; |
| 99 | register char *np, *cp; |
| 100 | char buf[MAXPATHLEN]; |
| 101 | |
| 102 | cp = name; |
| 103 | for (ep = lookupino(ROOTINO); ep != NIL; ep = ep->e_entries) { |
| 104 | for (np = buf; *cp != '/' && *cp != '\0'; ) |
| 105 | *np++ = *cp++; |
| 106 | *np = '\0'; |
| 107 | for ( ; ep != NIL; ep = ep->e_sibling) |
| 108 | if (strcmp(ep->e_name, buf) == 0) |
| 109 | break; |
| 110 | if (ep == NIL) |
| 111 | break; |
| 112 | if (*cp++ == '\0') |
| 113 | return (ep); |
| 114 | } |
| 115 | return (NIL); |
| 116 | } |
| 117 | |
| 118 | /* |
| 119 | * Look up the parent of a pathname |
| 120 | */ |
| 121 | struct entry * |
| 122 | lookupparent(name) |
| 123 | char *name; |
| 124 | { |
| 125 | struct entry *ep; |
| 126 | char *tailindex; |
| 127 | |
| 128 | tailindex = rindex(name, '/'); |
| 129 | if (tailindex == 0) |
| 130 | return (NIL); |
| 131 | *tailindex = '\0'; |
| 132 | ep = lookupname(name); |
| 133 | *tailindex = '/'; |
| 134 | if (ep == NIL) |
| 135 | return (NIL); |
| 136 | if (ep->e_type != NODE) |
| 137 | panic("%s is not a directory\n", name); |
| 138 | return (ep); |
| 139 | } |
| 140 | |
| 141 | /* |
| 142 | * Determine the current pathname of a node or leaf |
| 143 | */ |
| 144 | char * |
| 145 | myname(ep) |
| 146 | register struct entry *ep; |
| 147 | { |
| 148 | register char *cp; |
| 149 | static char namebuf[MAXPATHLEN]; |
| 150 | |
| 151 | for (cp = &namebuf[MAXPATHLEN - 2]; cp > &namebuf[ep->e_namlen]; ) { |
| 152 | cp -= ep->e_namlen; |
| 153 | bcopy(ep->e_name, cp, (long)ep->e_namlen); |
| 154 | if (ep == lookupino(ROOTINO)) |
| 155 | return (cp); |
| 156 | *(--cp) = '/'; |
| 157 | ep = ep->e_parent; |
| 158 | } |
| 159 | panic("%s: pathname too long\n", cp); |
| 160 | return(cp); |
| 161 | } |
| 162 | |
| 163 | /* |
| 164 | * Unused symbol table entries are linked together on a freelist |
| 165 | * headed by the following pointer. |
| 166 | */ |
| 167 | static struct entry *freelist = NIL; |
| 168 | |
| 169 | /* |
| 170 | * add an entry to the symbol table |
| 171 | */ |
| 172 | struct entry * |
| 173 | addentry(name, inum, type) |
| 174 | char *name; |
| 175 | ino_t inum; |
| 176 | int type; |
| 177 | { |
| 178 | register struct entry *np, *ep; |
| 179 | |
| 180 | if (freelist != NIL) { |
| 181 | np = freelist; |
| 182 | freelist = np->e_next; |
| 183 | bzero((char *)np, (long)sizeof(struct entry)); |
| 184 | } else { |
| 185 | np = (struct entry *)calloc(1, sizeof(struct entry)); |
| 186 | if (np == NIL) |
| 187 | panic("no memory to extend symbol table\n"); |
| 188 | } |
| 189 | np->e_type = type & ~LINK; |
| 190 | ep = lookupparent(name); |
| 191 | if (ep == NIL) { |
| 192 | if (inum != ROOTINO || lookupino(ROOTINO) != NIL) |
| 193 | panic("bad name to addentry %s\n", name); |
| 194 | np->e_name = savename(name); |
| 195 | np->e_namlen = strlen(name); |
| 196 | np->e_parent = np; |
| 197 | addino(ROOTINO, np); |
| 198 | return (np); |
| 199 | } |
| 200 | np->e_name = savename(rindex(name, '/') + 1); |
| 201 | np->e_namlen = strlen(np->e_name); |
| 202 | np->e_parent = ep; |
| 203 | np->e_sibling = ep->e_entries; |
| 204 | ep->e_entries = np; |
| 205 | if (type & LINK) { |
| 206 | ep = lookupino(inum); |
| 207 | if (ep == NIL) |
| 208 | panic("link to non-existant name\n"); |
| 209 | np->e_ino = inum; |
| 210 | np->e_links = ep->e_links; |
| 211 | ep->e_links = np; |
| 212 | } else if (inum != 0) { |
| 213 | if (lookupino(inum) != NIL) |
| 214 | panic("duplicate entry\n"); |
| 215 | addino(inum, np); |
| 216 | } |
| 217 | return (np); |
| 218 | } |
| 219 | |
| 220 | /* |
| 221 | * delete an entry from the symbol table |
| 222 | */ |
| 223 | freeentry(ep) |
| 224 | register struct entry *ep; |
| 225 | { |
| 226 | register struct entry *np; |
| 227 | ino_t inum; |
| 228 | |
| 229 | if (ep->e_flags != REMOVED) |
| 230 | badentry(ep, "not marked REMOVED"); |
| 231 | if (ep->e_type == NODE) { |
| 232 | if (ep->e_links != NIL) |
| 233 | badentry(ep, "freeing referenced directory"); |
| 234 | if (ep->e_entries != NIL) |
| 235 | badentry(ep, "freeing non-empty directory"); |
| 236 | } |
| 237 | if (ep->e_ino != 0) { |
| 238 | np = lookupino(ep->e_ino); |
| 239 | if (np == NIL) |
| 240 | badentry(ep, "lookupino failed"); |
| 241 | if (np == ep) { |
| 242 | inum = ep->e_ino; |
| 243 | deleteino(inum); |
| 244 | if (ep->e_links != NIL) |
| 245 | addino(inum, ep->e_links); |
| 246 | } else { |
| 247 | for (; np != NIL; np = np->e_links) { |
| 248 | if (np->e_links == ep) { |
| 249 | np->e_links = ep->e_links; |
| 250 | break; |
| 251 | } |
| 252 | } |
| 253 | if (np == NIL) |
| 254 | badentry(ep, "link not found"); |
| 255 | } |
| 256 | } |
| 257 | removeentry(ep); |
| 258 | freename(ep->e_name); |
| 259 | ep->e_next = freelist; |
| 260 | freelist = ep; |
| 261 | } |
| 262 | |
| 263 | /* |
| 264 | * Relocate an entry in the tree structure |
| 265 | */ |
| 266 | moveentry(ep, newname) |
| 267 | register struct entry *ep; |
| 268 | char *newname; |
| 269 | { |
| 270 | struct entry *np; |
| 271 | char *cp; |
| 272 | |
| 273 | np = lookupparent(newname); |
| 274 | if (np == NIL) |
| 275 | badentry(ep, "cannot move ROOT"); |
| 276 | if (np != ep->e_parent) { |
| 277 | removeentry(ep); |
| 278 | ep->e_parent = np; |
| 279 | ep->e_sibling = np->e_entries; |
| 280 | np->e_entries = ep; |
| 281 | } |
| 282 | cp = rindex(newname, '/') + 1; |
| 283 | freename(ep->e_name); |
| 284 | ep->e_name = savename(cp); |
| 285 | ep->e_namlen = strlen(cp); |
| 286 | if (strcmp(gentempname(ep), ep->e_name) == 0) |
| 287 | ep->e_flags |= TMPNAME; |
| 288 | else |
| 289 | ep->e_flags &= ~TMPNAME; |
| 290 | } |
| 291 | |
| 292 | /* |
| 293 | * Remove an entry in the tree structure |
| 294 | */ |
| 295 | removeentry(ep) |
| 296 | register struct entry *ep; |
| 297 | { |
| 298 | register struct entry *np; |
| 299 | |
| 300 | np = ep->e_parent; |
| 301 | if (np->e_entries == ep) { |
| 302 | np->e_entries = ep->e_sibling; |
| 303 | } else { |
| 304 | for (np = np->e_entries; np != NIL; np = np->e_sibling) { |
| 305 | if (np->e_sibling == ep) { |
| 306 | np->e_sibling = ep->e_sibling; |
| 307 | break; |
| 308 | } |
| 309 | } |
| 310 | if (np == NIL) |
| 311 | badentry(ep, "cannot find entry in parent list"); |
| 312 | } |
| 313 | } |
| 314 | |
| 315 | /* |
| 316 | * Table of unused string entries, sorted by length. |
| 317 | * |
| 318 | * Entries are allocated in STRTBLINCR sized pieces so that names |
| 319 | * of similar lengths can use the same entry. The value of STRTBLINCR |
| 320 | * is chosen so that every entry has at least enough space to hold |
| 321 | * a "struct strtbl" header. Thus every entry can be linked onto an |
| 322 | * apprpriate free list. |
| 323 | * |
| 324 | * NB. The macro "allocsize" below assumes that "struct strhdr" |
| 325 | * has a size that is a power of two. |
| 326 | */ |
| 327 | struct strhdr { |
| 328 | struct strhdr *next; |
| 329 | }; |
| 330 | |
| 331 | #define STRTBLINCR (sizeof(struct strhdr)) |
| 332 | #define allocsize(size) (((size) + 1 + STRTBLINCR - 1) & ~(STRTBLINCR - 1)) |
| 333 | |
| 334 | static struct strhdr strtblhdr[allocsize(MAXNAMLEN) / STRTBLINCR]; |
| 335 | |
| 336 | /* |
| 337 | * Allocate space for a name. It first looks to see if it already |
| 338 | * has an appropriate sized entry, and if not allocates a new one. |
| 339 | */ |
| 340 | char * |
| 341 | savename(name) |
| 342 | char *name; |
| 343 | { |
| 344 | struct strhdr *np; |
| 345 | long len; |
| 346 | char *cp; |
| 347 | |
| 348 | if (name == NULL) |
| 349 | panic("bad name\n"); |
| 350 | len = strlen(name); |
| 351 | np = strtblhdr[len / STRTBLINCR].next; |
| 352 | if (np != NULL) { |
| 353 | strtblhdr[len / STRTBLINCR].next = np->next; |
| 354 | cp = (char *)np; |
| 355 | } else { |
| 356 | cp = malloc((unsigned)allocsize(len)); |
| 357 | if (cp == NULL) |
| 358 | panic("no space for string table\n"); |
| 359 | } |
| 360 | (void) strcpy(cp, name); |
| 361 | return (cp); |
| 362 | } |
| 363 | |
| 364 | /* |
| 365 | * Free space for a name. The resulting entry is linked onto the |
| 366 | * appropriate free list. |
| 367 | */ |
| 368 | freename(name) |
| 369 | char *name; |
| 370 | { |
| 371 | struct strhdr *tp, *np; |
| 372 | |
| 373 | tp = &strtblhdr[strlen(name) / STRTBLINCR]; |
| 374 | np = (struct strhdr *)name; |
| 375 | np->next = tp->next; |
| 376 | tp->next = np; |
| 377 | } |
| 378 | |
| 379 | /* |
| 380 | * Useful quantities placed at the end of a dumped symbol table. |
| 381 | */ |
| 382 | struct symtableheader { |
| 383 | long volno; |
| 384 | long stringsize; |
| 385 | long entrytblsize; |
| 386 | time_t dumptime; |
| 387 | time_t dumpdate; |
| 388 | ino_t maxino; |
| 389 | long ntrec; |
| 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 | hdr.ntrec = ntrec; |
| 468 | (void) fwrite((char *)&hdr, sizeof(struct symtableheader), 1, fd); |
| 469 | if (ferror(fd)) { |
| 470 | perror("fwrite"); |
| 471 | panic("output error to file %s writing symbol table\n", |
| 472 | filename); |
| 473 | } |
| 474 | (void) fclose(fd); |
| 475 | } |
| 476 | |
| 477 | /* |
| 478 | * Initialize a symbol table from a file |
| 479 | */ |
| 480 | initsymtable(filename) |
| 481 | char *filename; |
| 482 | { |
| 483 | char *base; |
| 484 | long tblsize; |
| 485 | register struct entry *ep; |
| 486 | struct entry *baseep, *lep; |
| 487 | struct symtableheader hdr; |
| 488 | struct stat stbuf; |
| 489 | register long i; |
| 490 | int fd; |
| 491 | |
| 492 | vprintf(stdout, "Initialize symbol table.\n"); |
| 493 | if (filename == NULL) { |
| 494 | entrytblsize = maxino / HASHFACTOR; |
| 495 | entry = (struct entry **) |
| 496 | calloc((unsigned)entrytblsize, sizeof(struct entry *)); |
| 497 | if (entry == (struct entry **)NIL) |
| 498 | panic("no memory for entry table\n"); |
| 499 | ep = addentry(".", ROOTINO, NODE); |
| 500 | ep->e_flags |= NEW; |
| 501 | return; |
| 502 | } |
| 503 | if ((fd = open(filename, 0)) < 0) { |
| 504 | perror("open"); |
| 505 | panic("cannot open symbol table file %s\n", filename); |
| 506 | } |
| 507 | if (fstat(fd, &stbuf) < 0) { |
| 508 | perror("stat"); |
| 509 | panic("cannot stat symbol table file %s\n", filename); |
| 510 | } |
| 511 | tblsize = stbuf.st_size - sizeof(struct symtableheader); |
| 512 | base = calloc(sizeof(char), (unsigned)tblsize); |
| 513 | if (base == NULL) |
| 514 | panic("cannot allocate space for symbol table\n"); |
| 515 | if (read(fd, base, (int)tblsize) < 0 || |
| 516 | read(fd, (char *)&hdr, sizeof(struct symtableheader)) < 0) { |
| 517 | perror("read"); |
| 518 | panic("cannot read symbol table file %s\n", filename); |
| 519 | } |
| 520 | switch (command) { |
| 521 | case 'r': |
| 522 | /* |
| 523 | * For normal continuation, insure that we are using |
| 524 | * the next incremental tape |
| 525 | */ |
| 526 | if (hdr.dumpdate != dumptime) { |
| 527 | if (hdr.dumpdate < dumptime) |
| 528 | fprintf(stderr, "Incremental tape too low\n"); |
| 529 | else |
| 530 | fprintf(stderr, "Incremental tape too high\n"); |
| 531 | done(1); |
| 532 | } |
| 533 | break; |
| 534 | case 'R': |
| 535 | /* |
| 536 | * For restart, insure that we are using the same tape |
| 537 | */ |
| 538 | curfile.action = SKIP; |
| 539 | dumptime = hdr.dumptime; |
| 540 | dumpdate = hdr.dumpdate; |
| 541 | if (!bflag) |
| 542 | newtapebuf(hdr.ntrec); |
| 543 | getvol(hdr.volno); |
| 544 | break; |
| 545 | default: |
| 546 | panic("initsymtable called from command %c\n", command); |
| 547 | break; |
| 548 | } |
| 549 | maxino = hdr.maxino; |
| 550 | entrytblsize = hdr.entrytblsize; |
| 551 | entry = (struct entry **) |
| 552 | (base + tblsize - (entrytblsize * sizeof(struct entry *))); |
| 553 | baseep = (struct entry *)(base + hdr.stringsize - sizeof(struct entry)); |
| 554 | lep = (struct entry *)entry; |
| 555 | for (i = 0; i < entrytblsize; i++) { |
| 556 | if (entry[i] == NIL) |
| 557 | continue; |
| 558 | entry[i] = &baseep[(long)entry[i]]; |
| 559 | } |
| 560 | for (ep = &baseep[1]; ep < lep; ep++) { |
| 561 | ep->e_name = base + (long)ep->e_name; |
| 562 | ep->e_parent = &baseep[(long)ep->e_parent]; |
| 563 | if (ep->e_sibling != NIL) |
| 564 | ep->e_sibling = &baseep[(long)ep->e_sibling]; |
| 565 | if (ep->e_links != NIL) |
| 566 | ep->e_links = &baseep[(long)ep->e_links]; |
| 567 | if (ep->e_entries != NIL) |
| 568 | ep->e_entries = &baseep[(long)ep->e_entries]; |
| 569 | if (ep->e_next != NIL) |
| 570 | ep->e_next = &baseep[(long)ep->e_next]; |
| 571 | } |
| 572 | } |