1 /* $OpenBSD: symtab.c,v 1.3 1996/12/04 01:41:53 deraadt Exp $ */ 2 /* $NetBSD: symtab.c,v 1.9 1996/11/30 18:04:47 cgd Exp $ */ 3 4 /* 5 * Copyright (c) 1983, 1993 6 * The Regents of the University of California. All rights reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in the 15 * documentation and/or other materials provided with the distribution. 16 * 3. All advertising materials mentioning features or use of this software 17 * must display the following acknowledgement: 18 * This product includes software developed by the University of 19 * California, Berkeley and its contributors. 20 * 4. Neither the name of the University nor the names of its contributors 21 * may be used to endorse or promote products derived from this software 22 * without specific prior written permission. 23 * 24 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 27 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 34 * SUCH DAMAGE. 35 */ 36 37 #ifndef lint 38 #if 0 39 static char sccsid[] = "@(#)symtab.c 8.2 (Berkeley) 9/13/94"; 40 #else 41 static char rcsid[] = "$OpenBSD: symtab.c,v 1.3 1996/12/04 01:41:53 deraadt 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 register 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 register 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 register struct entry *ep; 155 register 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 register struct entry *ep; 203 { 204 register 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 memcpy(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 register 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-existant 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 register struct entry *ep; 282 { 283 register 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 register 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 register struct entry *ep; 356 { 357 register 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 long checkpt; 459 { 460 register struct entry *ep, *tep; 461 register 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 memcpy(tep, ep, (long)sizeof(struct entry)); 495 tep->e_name = (char *)stroff; 496 stroff += allocsize(ep->e_namlen); 497 tep->e_parent = (struct entry *)ep->e_parent->e_index; 498 if (ep->e_links != NULL) 499 tep->e_links = 500 (struct entry *)ep->e_links->e_index; 501 if (ep->e_sibling != NULL) 502 tep->e_sibling = 503 (struct entry *)ep->e_sibling->e_index; 504 if (ep->e_entries != NULL) 505 tep->e_entries = 506 (struct entry *)ep->e_entries->e_index; 507 if (ep->e_next != NULL) 508 tep->e_next = 509 (struct entry *)ep->e_next->e_index; 510 (void) fwrite((char *)tep, sizeof(struct entry), 1, fd); 511 } 512 } 513 /* 514 * Convert entry pointers to indexes, and output 515 */ 516 for (i = 0; i < entrytblsize; i++) { 517 if (entry[i] == NULL) 518 tentry = NULL; 519 else 520 tentry = (struct entry *)entry[i]->e_index; 521 (void) fwrite((char *)&tentry, sizeof(struct entry *), 1, fd); 522 } 523 hdr.volno = checkpt; 524 hdr.maxino = maxino; 525 hdr.entrytblsize = entrytblsize; 526 hdr.stringsize = stroff; 527 hdr.dumptime = dumptime; 528 hdr.dumpdate = dumpdate; 529 hdr.ntrec = ntrec; 530 (void) fwrite((char *)&hdr, sizeof(struct symtableheader), 1, fd); 531 if (ferror(fd)) { 532 fprintf(stderr, "fwrite: %s\n", strerror(errno)); 533 panic("output error to file %s writing symbol table\n", 534 filename); 535 } 536 (void) fclose(fd); 537 } 538 539 /* 540 * Initialize a symbol table from a file 541 */ 542 void 543 initsymtable(filename) 544 char *filename; 545 { 546 char *base; 547 long tblsize; 548 register struct entry *ep; 549 struct entry *baseep, *lep; 550 struct symtableheader hdr; 551 struct stat stbuf; 552 register long i; 553 int fd; 554 555 vprintf(stdout, "Initialize symbol table.\n"); 556 if (filename == NULL) { 557 entrytblsize = maxino / HASHFACTOR; 558 entry = (struct entry **) 559 calloc((unsigned)entrytblsize, sizeof(struct entry *)); 560 if (entry == (struct entry **)NULL) 561 panic("no memory for entry table\n"); 562 ep = addentry(".", ROOTINO, NODE); 563 ep->e_flags |= NEW; 564 return; 565 } 566 if ((fd = open(filename, O_RDONLY, 0)) < 0) { 567 fprintf(stderr, "open: %s\n", strerror(errno)); 568 panic("cannot open symbol table file %s\n", filename); 569 } 570 if (fstat(fd, &stbuf) < 0) { 571 fprintf(stderr, "stat: %s\n", strerror(errno)); 572 panic("cannot stat symbol table file %s\n", filename); 573 } 574 tblsize = stbuf.st_size - sizeof(struct symtableheader); 575 base = calloc(sizeof(char), (unsigned)tblsize); 576 if (base == NULL) 577 panic("cannot allocate space for symbol table\n"); 578 if (read(fd, base, (int)tblsize) < 0 || 579 read(fd, (char *)&hdr, sizeof(struct symtableheader)) < 0) { 580 fprintf(stderr, "read: %s\n", strerror(errno)); 581 panic("cannot read symbol table file %s\n", filename); 582 } 583 switch (command) { 584 case 'r': 585 /* 586 * For normal continuation, insure that we are using 587 * the next incremental tape 588 */ 589 if (hdr.dumpdate != dumptime) { 590 if (hdr.dumpdate < dumptime) 591 fprintf(stderr, "Incremental tape too low\n"); 592 else 593 fprintf(stderr, "Incremental tape too high\n"); 594 exit(1); 595 } 596 break; 597 case 'R': 598 /* 599 * For restart, insure that we are using the same tape 600 */ 601 curfile.action = SKIP; 602 dumptime = hdr.dumptime; 603 dumpdate = hdr.dumpdate; 604 if (!bflag) 605 newtapebuf(hdr.ntrec); 606 getvol(hdr.volno); 607 break; 608 default: 609 panic("initsymtable called from command %c\n", command); 610 break; 611 } 612 maxino = hdr.maxino; 613 entrytblsize = hdr.entrytblsize; 614 entry = (struct entry **) 615 (base + tblsize - (entrytblsize * sizeof(struct entry *))); 616 baseep = (struct entry *)(base + hdr.stringsize - sizeof(struct entry)); 617 lep = (struct entry *)entry; 618 for (i = 0; i < entrytblsize; i++) { 619 if (entry[i] == NULL) 620 continue; 621 entry[i] = &baseep[(long)entry[i]]; 622 } 623 for (ep = &baseep[1]; ep < lep; ep++) { 624 ep->e_name = base + (long)ep->e_name; 625 ep->e_parent = &baseep[(long)ep->e_parent]; 626 if (ep->e_sibling != NULL) 627 ep->e_sibling = &baseep[(long)ep->e_sibling]; 628 if (ep->e_links != NULL) 629 ep->e_links = &baseep[(long)ep->e_links]; 630 if (ep->e_entries != NULL) 631 ep->e_entries = &baseep[(long)ep->e_entries]; 632 if (ep->e_next != NULL) 633 ep->e_next = &baseep[(long)ep->e_next]; 634 } 635 } 636