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