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