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