1 /* $OpenBSD: symtab.c,v 1.5 1997/07/05 20:51:25 millert Exp $ */ 2 /* $NetBSD: symtab.c,v 1.10 1997/03/19 08:42:54 lukem 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.5 1997/07/05 20:51:25 millert 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 <err.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; 161 *cp != '/' && *cp != '\0' && np < &buf[sizeof(buf)]; ) 162 *np++ = *cp++; 163 if (np == &buf[sizeof(buf)]) 164 break; 165 *np = '\0'; 166 for ( ; ep != NULL; ep = ep->e_sibling) 167 if (strcmp(ep->e_name, buf) == 0) 168 break; 169 if (ep == NULL) 170 break; 171 if (*cp++ == '\0') 172 return (ep); 173 } 174 return (NULL); 175 } 176 177 /* 178 * Look up the parent of a pathname 179 */ 180 static struct entry * 181 lookupparent(name) 182 char *name; 183 { 184 struct entry *ep; 185 char *tailindex; 186 187 tailindex = strrchr(name, '/'); 188 if (tailindex == NULL) 189 return (NULL); 190 *tailindex = '\0'; 191 ep = lookupname(name); 192 *tailindex = '/'; 193 if (ep == NULL) 194 return (NULL); 195 if (ep->e_type != NODE) 196 panic("%s is not a directory\n", name); 197 return (ep); 198 } 199 200 /* 201 * Determine the current pathname of a node or leaf 202 */ 203 char * 204 myname(ep) 205 register struct entry *ep; 206 { 207 register char *cp; 208 static char namebuf[MAXPATHLEN]; 209 210 for (cp = &namebuf[MAXPATHLEN - 2]; cp > &namebuf[ep->e_namlen]; ) { 211 cp -= ep->e_namlen; 212 memcpy(cp, ep->e_name, (long)ep->e_namlen); 213 if (ep == lookupino(ROOTINO)) 214 return (cp); 215 *(--cp) = '/'; 216 ep = ep->e_parent; 217 } 218 panic("%s: pathname too long\n", cp); 219 return(cp); 220 } 221 222 /* 223 * Unused symbol table entries are linked together on a freelist 224 * headed by the following pointer. 225 */ 226 static struct entry *freelist = NULL; 227 228 /* 229 * add an entry to the symbol table 230 */ 231 struct entry * 232 addentry(name, inum, type) 233 char *name; 234 ino_t inum; 235 int type; 236 { 237 register struct entry *np, *ep; 238 239 if (freelist != NULL) { 240 np = freelist; 241 freelist = np->e_next; 242 memset(np, 0, (long)sizeof(struct entry)); 243 } else { 244 np = (struct entry *)calloc(1, sizeof(struct entry)); 245 if (np == NULL) 246 panic("no memory to extend symbol table\n"); 247 } 248 np->e_type = type & ~LINK; 249 ep = lookupparent(name); 250 if (ep == NULL) { 251 if (inum != ROOTINO || lookupino(ROOTINO) != NULL) 252 panic("bad name to addentry %s\n", name); 253 np->e_name = savename(name); 254 np->e_namlen = strlen(name); 255 np->e_parent = np; 256 addino(ROOTINO, np); 257 return (np); 258 } 259 np->e_name = savename(strrchr(name, '/') + 1); 260 np->e_namlen = strlen(np->e_name); 261 np->e_parent = ep; 262 np->e_sibling = ep->e_entries; 263 ep->e_entries = np; 264 if (type & LINK) { 265 ep = lookupino(inum); 266 if (ep == NULL) 267 panic("link to non-existant name\n"); 268 np->e_ino = inum; 269 np->e_links = ep->e_links; 270 ep->e_links = np; 271 } else if (inum != 0) { 272 if (lookupino(inum) != NULL) 273 panic("duplicate entry\n"); 274 addino(inum, np); 275 } 276 return (np); 277 } 278 279 /* 280 * delete an entry from the symbol table 281 */ 282 void 283 freeentry(ep) 284 register struct entry *ep; 285 { 286 register struct entry *np; 287 ino_t inum; 288 289 if (ep->e_flags != REMOVED) 290 badentry(ep, "not marked REMOVED"); 291 if (ep->e_type == NODE) { 292 if (ep->e_links != NULL) 293 badentry(ep, "freeing referenced directory"); 294 if (ep->e_entries != NULL) 295 badentry(ep, "freeing non-empty directory"); 296 } 297 if (ep->e_ino != 0) { 298 np = lookupino(ep->e_ino); 299 if (np == NULL) 300 badentry(ep, "lookupino failed"); 301 if (np == ep) { 302 inum = ep->e_ino; 303 deleteino(inum); 304 if (ep->e_links != NULL) 305 addino(inum, ep->e_links); 306 } else { 307 for (; np != NULL; np = np->e_links) { 308 if (np->e_links == ep) { 309 np->e_links = ep->e_links; 310 break; 311 } 312 } 313 if (np == NULL) 314 badentry(ep, "link not found"); 315 } 316 } 317 removeentry(ep); 318 freename(ep->e_name); 319 ep->e_next = freelist; 320 freelist = ep; 321 } 322 323 /* 324 * Relocate an entry in the tree structure 325 */ 326 void 327 moveentry(ep, newname) 328 register struct entry *ep; 329 char *newname; 330 { 331 struct entry *np; 332 char *cp; 333 334 np = lookupparent(newname); 335 if (np == NULL) 336 badentry(ep, "cannot move ROOT"); 337 if (np != ep->e_parent) { 338 removeentry(ep); 339 ep->e_parent = np; 340 ep->e_sibling = np->e_entries; 341 np->e_entries = ep; 342 } 343 cp = strrchr(newname, '/') + 1; 344 freename(ep->e_name); 345 ep->e_name = savename(cp); 346 ep->e_namlen = strlen(cp); 347 if (strcmp(gentempname(ep), ep->e_name) == 0) 348 ep->e_flags |= TMPNAME; 349 else 350 ep->e_flags &= ~TMPNAME; 351 } 352 353 /* 354 * Remove an entry in the tree structure 355 */ 356 static void 357 removeentry(ep) 358 register struct entry *ep; 359 { 360 register struct entry *np; 361 362 np = ep->e_parent; 363 if (np->e_entries == ep) { 364 np->e_entries = ep->e_sibling; 365 } else { 366 for (np = np->e_entries; np != NULL; np = np->e_sibling) { 367 if (np->e_sibling == ep) { 368 np->e_sibling = ep->e_sibling; 369 break; 370 } 371 } 372 if (np == NULL) 373 badentry(ep, "cannot find entry in parent list"); 374 } 375 } 376 377 /* 378 * Table of unused string entries, sorted by length. 379 * 380 * Entries are allocated in STRTBLINCR sized pieces so that names 381 * of similar lengths can use the same entry. The value of STRTBLINCR 382 * is chosen so that every entry has at least enough space to hold 383 * a "struct strtbl" header. Thus every entry can be linked onto an 384 * apprpriate free list. 385 * 386 * NB. The macro "allocsize" below assumes that "struct strhdr" 387 * has a size that is a power of two. 388 */ 389 struct strhdr { 390 struct strhdr *next; 391 }; 392 393 #define STRTBLINCR (sizeof(struct strhdr)) 394 #define allocsize(size) (((size) + 1 + STRTBLINCR - 1) & ~(STRTBLINCR - 1)) 395 396 static struct strhdr strtblhdr[allocsize(NAME_MAX) / STRTBLINCR]; 397 398 /* 399 * Allocate space for a name. It first looks to see if it already 400 * has an appropriate sized entry, and if not allocates a new one. 401 */ 402 char * 403 savename(name) 404 char *name; 405 { 406 struct strhdr *np; 407 long len; 408 char *cp; 409 410 if (name == NULL) 411 panic("bad name\n"); 412 len = strlen(name); 413 np = strtblhdr[len / STRTBLINCR].next; 414 if (np != NULL) { 415 strtblhdr[len / STRTBLINCR].next = np->next; 416 cp = (char *)np; 417 } else { 418 cp = malloc((unsigned)allocsize(len)); 419 if (cp == NULL) 420 panic("no space for string table\n"); 421 } 422 (void)strcpy(cp, name); 423 return (cp); 424 } 425 426 /* 427 * Free space for a name. The resulting entry is linked onto the 428 * appropriate free list. 429 */ 430 void 431 freename(name) 432 char *name; 433 { 434 struct strhdr *tp, *np; 435 436 tp = &strtblhdr[strlen(name) / STRTBLINCR]; 437 np = (struct strhdr *)name; 438 np->next = tp->next; 439 tp->next = np; 440 } 441 442 /* 443 * Useful quantities placed at the end of a dumped symbol table. 444 */ 445 struct symtableheader { 446 int32_t volno; 447 int32_t stringsize; 448 int32_t entrytblsize; 449 time_t dumptime; 450 time_t dumpdate; 451 ino_t maxino; 452 int32_t ntrec; 453 }; 454 455 /* 456 * dump a snapshot of the symbol table 457 */ 458 void 459 dumpsymtable(filename, checkpt) 460 char *filename; 461 long checkpt; 462 { 463 register struct entry *ep, *tep; 464 register ino_t i; 465 struct entry temp, *tentry; 466 long mynum = 1, stroff = 0; 467 FILE *fd; 468 struct symtableheader hdr; 469 470 Vprintf(stdout, "Check pointing the restore\n"); 471 if (Nflag) 472 return; 473 if ((fd = fopen(filename, "w")) == NULL) { 474 warn("fopen"); 475 panic("cannot create save file %s for symbol table\n", 476 filename); 477 } 478 clearerr(fd); 479 /* 480 * Assign indicies to each entry 481 * Write out the string entries 482 */ 483 for (i = WINO; i <= maxino; i++) { 484 for (ep = lookupino(i); ep != NULL; ep = ep->e_links) { 485 ep->e_index = mynum++; 486 (void)fwrite(ep->e_name, sizeof(char), 487 (int)allocsize(ep->e_namlen), fd); 488 } 489 } 490 /* 491 * Convert pointers to indexes, and output 492 */ 493 tep = &temp; 494 stroff = 0; 495 for (i = WINO; i <= maxino; i++) { 496 for (ep = lookupino(i); ep != NULL; ep = ep->e_links) { 497 memcpy(tep, ep, (long)sizeof(struct entry)); 498 tep->e_name = (char *)stroff; 499 stroff += allocsize(ep->e_namlen); 500 tep->e_parent = (struct entry *)ep->e_parent->e_index; 501 if (ep->e_links != NULL) 502 tep->e_links = 503 (struct entry *)ep->e_links->e_index; 504 if (ep->e_sibling != NULL) 505 tep->e_sibling = 506 (struct entry *)ep->e_sibling->e_index; 507 if (ep->e_entries != NULL) 508 tep->e_entries = 509 (struct entry *)ep->e_entries->e_index; 510 if (ep->e_next != NULL) 511 tep->e_next = 512 (struct entry *)ep->e_next->e_index; 513 (void)fwrite((char *)tep, sizeof(struct entry), 1, fd); 514 } 515 } 516 /* 517 * Convert entry pointers to indexes, and output 518 */ 519 for (i = 0; i < entrytblsize; i++) { 520 if (entry[i] == NULL) 521 tentry = NULL; 522 else 523 tentry = (struct entry *)entry[i]->e_index; 524 (void)fwrite((char *)&tentry, sizeof(struct entry *), 1, fd); 525 } 526 hdr.volno = checkpt; 527 hdr.maxino = maxino; 528 hdr.entrytblsize = entrytblsize; 529 hdr.stringsize = stroff; 530 hdr.dumptime = dumptime; 531 hdr.dumpdate = dumpdate; 532 hdr.ntrec = ntrec; 533 (void)fwrite((char *)&hdr, sizeof(struct symtableheader), 1, fd); 534 if (ferror(fd)) { 535 warn("fwrite"); 536 panic("output error to file %s writing symbol table\n", 537 filename); 538 } 539 (void)fclose(fd); 540 } 541 542 /* 543 * Initialize a symbol table from a file 544 */ 545 void 546 initsymtable(filename) 547 char *filename; 548 { 549 char *base; 550 long tblsize; 551 register struct entry *ep; 552 struct entry *baseep, *lep; 553 struct symtableheader hdr; 554 struct stat stbuf; 555 register long i; 556 int fd; 557 558 Vprintf(stdout, "Initialize symbol table.\n"); 559 if (filename == NULL) { 560 entrytblsize = maxino / HASHFACTOR; 561 entry = (struct entry **) 562 calloc((unsigned)entrytblsize, sizeof(struct entry *)); 563 if (entry == (struct entry **)NULL) 564 panic("no memory for entry table\n"); 565 ep = addentry(".", ROOTINO, NODE); 566 ep->e_flags |= NEW; 567 return; 568 } 569 if ((fd = open(filename, O_RDONLY, 0)) < 0) { 570 warn("open"); 571 panic("cannot open symbol table file %s\n", filename); 572 } 573 if (fstat(fd, &stbuf) < 0) { 574 warn("stat"); 575 panic("cannot stat symbol table file %s\n", filename); 576 } 577 tblsize = stbuf.st_size - sizeof(struct symtableheader); 578 base = calloc(sizeof(char), (unsigned)tblsize); 579 if (base == NULL) 580 panic("cannot allocate space for symbol table\n"); 581 if (read(fd, base, (int)tblsize) < 0 || 582 read(fd, (char *)&hdr, sizeof(struct symtableheader)) < 0) { 583 warn("read"); 584 panic("cannot read symbol table file %s\n", filename); 585 } 586 switch (command) { 587 case 'r': 588 /* 589 * For normal continuation, insure that we are using 590 * the next incremental tape 591 */ 592 if (hdr.dumpdate != dumptime) 593 errx(1, "Incremental tape too %s", 594 (hdr.dumpdate < dumptime) ? "low" : "high"); 595 break; 596 case 'R': 597 /* 598 * For restart, insure that we are using the same tape 599 */ 600 curfile.action = SKIP; 601 dumptime = hdr.dumptime; 602 dumpdate = hdr.dumpdate; 603 if (!bflag) 604 newtapebuf(hdr.ntrec); 605 getvol(hdr.volno); 606 break; 607 default: 608 panic("initsymtable called from command %c\n", command); 609 break; 610 } 611 maxino = hdr.maxino; 612 entrytblsize = hdr.entrytblsize; 613 entry = (struct entry **) 614 (base + tblsize - (entrytblsize * sizeof(struct entry *))); 615 baseep = (struct entry *)(base + hdr.stringsize - sizeof(struct entry)); 616 lep = (struct entry *)entry; 617 for (i = 0; i < entrytblsize; i++) { 618 if (entry[i] == NULL) 619 continue; 620 entry[i] = &baseep[(long)entry[i]]; 621 } 622 for (ep = &baseep[1]; ep < lep; ep++) { 623 ep->e_name = base + (long)ep->e_name; 624 ep->e_parent = &baseep[(long)ep->e_parent]; 625 if (ep->e_sibling != NULL) 626 ep->e_sibling = &baseep[(long)ep->e_sibling]; 627 if (ep->e_links != NULL) 628 ep->e_links = &baseep[(long)ep->e_links]; 629 if (ep->e_entries != NULL) 630 ep->e_entries = &baseep[(long)ep->e_entries]; 631 if (ep->e_next != NULL) 632 ep->e_next = &baseep[(long)ep->e_next]; 633 } 634 } 635