restore/symtab.c

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