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