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