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