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