X-Git-Url: https://git.wh0rd.org/?p=dump.git;a=blobdiff_plain;f=restore%2Fsymtab.c;h=06548bcee6e5a84c7bbd0e8eae6c614eb877b57d;hp=d9d9a2e2ca6d3776d998b5db77e2ae4561fe9dd0;hb=26ce8fc8f42b8cdd92e9eaadae48be256813b001;hpb=1227625a12a66e0ded78a1997c2d23f23202a382 diff --git a/restore/symtab.c b/restore/symtab.c index d9d9a2e..06548bc 100644 --- a/restore/symtab.c +++ b/restore/symtab.c @@ -1,8 +1,9 @@ /* * Ported to Linux's Second Extended File System as part of the * dump and restore backup suit - * Remy Card , 1994, 1995, 1996 - * + * Remy Card , 1994-1997 + * Stelian Pop , 1999-2000 + * Stelian Pop - Alcôve , 2000-2002 */ /* @@ -17,11 +18,7 @@ * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. - * 3. All advertising materials mentioning features or use of this software - * must display the following acknowledgement: - * This product includes software developed by the University of - * California, Berkeley and its contributors. - * 4. Neither the name of the University nor the names of its contributors + * 3. Neither the name of the University nor the names of its contributors * may be used to endorse or promote products derived from this software * without specific prior written permission. * @@ -39,7 +36,8 @@ */ #ifndef lint -static char sccsid[] = "@(#)symtab.c 8.3 (Berkeley) 4/28/95"; +static const char rcsid[] = + "$Id: symtab.c,v 1.26 2005/07/07 08:47:16 stelian Exp $"; #endif /* not lint */ /* @@ -51,18 +49,31 @@ static char sccsid[] = "@(#)symtab.c 8.3 (Berkeley) 4/28/95"; * are needed, by calling "myname". */ +#include +#include #include #include #ifdef __linux__ #include +#include +#ifdef HAVE_EXT2FS_EXT2_FS_H +#include +#else #include +#endif #include #else /* __linux__ */ +#ifdef sunos +#include +#include +#else #include +#endif #endif /* __linux__ */ #include +#include #include #include #include @@ -87,18 +98,36 @@ static char sccsid[] = "@(#)symtab.c 8.3 (Berkeley) 4/28/95"; static struct entry **entry; static long entrytblsize; -static void addino __P((ino_t, struct entry *)); +static void addino __P((dump_ino_t, struct entry *)); static struct entry *lookupparent __P((char *)); static void removeentry __P((struct entry *)); +static int dir_hash __P((char *)); + +/* + * Returns a hash given a file name + */ +static int +dir_hash(char *name) +{ + unsigned long hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9; + int len = strlen(name); + + while (len--) { + unsigned long hash = hash1 + (hash0 ^ (*name++ * 7152373)); + if (hash & 0x80000000) hash -= 0x7fffffff; + hash1 = hash0; + hash0 = hash; + } + return hash0 % DIRHASH_SIZE; +} /* * Look up an entry by inode number */ struct entry * -lookupino(inum) - ino_t inum; +lookupino(dump_ino_t inum) { - register struct entry *ep; + struct entry *ep; if (inum < WINO || inum >= maxino) return (NULL); @@ -112,9 +141,7 @@ lookupino(inum) * Add an entry into the entry table */ static void -addino(inum, np) - ino_t inum; - struct entry *np; +addino(dump_ino_t inum, struct entry *np) { struct entry **epp; @@ -134,10 +161,9 @@ addino(inum, np) * Delete an entry from the entry table */ void -deleteino(inum) - ino_t inum; +deleteino(dump_ino_t inum) { - register struct entry *next; + struct entry *next; struct entry **prev; if (inum < WINO || inum >= maxino) @@ -158,21 +184,53 @@ deleteino(inum) * Look up an entry by name */ struct entry * -lookupname(name) - char *name; +lookupname(char *name) { - register struct entry *ep; - register char *np, *cp; + struct entry *ep, *oldep; + char *np, *cp; char buf[MAXPATHLEN]; + ep = lookupino(ROOTINO); + cp = name; - for (ep = lookupino(ROOTINO); ep != NULL; ep = ep->e_entries) { - for (np = buf; *cp != '/' && *cp != '\0'; ) + if (*cp == '.') + ++cp; + if (*cp == '/') + ++cp; + if (*cp == '\0') + return ep; + + while (ep != NULL) { + for (np = buf; *cp != '/' && *cp != '\0' && + np < &buf[sizeof(buf)]; ) *np++ = *cp++; + if (np == &buf[sizeof(buf)]) + break; *np = '\0'; - for ( ; ep != NULL; ep = ep->e_sibling) - if (strcmp(ep->e_name, buf) == 0) - break; + + oldep = ep; + + if (ep->e_entries != NULL) { + + ep = ep->e_entries[dir_hash(buf)]; + for ( ; ep != NULL; ep = ep->e_sibling) + if (strcmp(ep->e_name, buf) == 0) + break; + + /* search all hash lists for renamed inodes */ + if (ep == NULL) { + int j; + for (j = 0; j < DIRHASH_SIZE; j++) { + ep = oldep->e_entries[j]; + for ( ; ep != NULL; ep = ep->e_sibling) + if (strcmp(ep->e_name, buf) == 0) + break; + if (ep != NULL) + break; + } + } + } + if (ep == NULL) break; if (*cp++ == '\0') @@ -185,8 +243,7 @@ lookupname(name) * Look up the parent of a pathname */ static struct entry * -lookupparent(name) - char *name; +lookupparent(char *name) { struct entry *ep; char *tailindex; @@ -208,15 +265,14 @@ lookupparent(name) * Determine the current pathname of a node or leaf */ char * -myname(ep) - register struct entry *ep; +myname(struct entry *ep) { - register char *cp; + char *cp; static char namebuf[MAXPATHLEN]; for (cp = &namebuf[MAXPATHLEN - 2]; cp > &namebuf[ep->e_namlen]; ) { cp -= ep->e_namlen; - memmove(cp, ep->e_name, (long)ep->e_namlen); + memmove(cp, ep->e_name, (size_t)ep->e_namlen); if (ep == lookupino(ROOTINO)) return (cp); *(--cp) = '/'; @@ -227,7 +283,7 @@ myname(ep) } /* - * Unused symbol table entries are linked together on a freelist + * Unused symbol table entries are linked together on a free list * headed by the following pointer. */ static struct entry *freelist = NULL; @@ -236,23 +292,25 @@ static struct entry *freelist = NULL; * add an entry to the symbol table */ struct entry * -addentry(name, inum, type) - char *name; - ino_t inum; - int type; +addentry(char *name, dump_ino_t inum, int type) { - register struct entry *np, *ep; + struct entry *np, *ep; if (freelist != NULL) { np = freelist; freelist = np->e_next; - memset(np, 0, (long)sizeof(struct entry)); + memset(np, 0, sizeof(struct entry)); } else { np = (struct entry *)calloc(1, sizeof(struct entry)); if (np == NULL) - panic("no memory to extend symbol table\n"); + errx(1, "no memory to extend symbol table"); } np->e_type = type & ~LINK; + if (type & NODE) { + np->e_entries = calloc(1, DIRHASH_SIZE * sizeof(struct entry *)); + if (np->e_entries == NULL) + panic("unable to allocate directory entries\n"); + } ep = lookupparent(name); if (ep == NULL) { if (inum != ROOTINO || lookupino(ROOTINO) != NULL) @@ -266,12 +324,12 @@ addentry(name, inum, type) np->e_name = savename(strrchr(name, '/') + 1); np->e_namlen = strlen(np->e_name); np->e_parent = ep; - np->e_sibling = ep->e_entries; - ep->e_entries = np; + np->e_sibling = ep->e_entries[dir_hash(np->e_name)]; + ep->e_entries[dir_hash(np->e_name)] = np; if (type & LINK) { ep = lookupino(inum); if (ep == NULL) - panic("link to non-existant name\n"); + panic("link to non-existent name\n"); np->e_ino = inum; np->e_links = ep->e_links; ep->e_links = np; @@ -287,19 +345,23 @@ addentry(name, inum, type) * delete an entry from the symbol table */ void -freeentry(ep) - register struct entry *ep; +freeentry(struct entry *ep) { - register struct entry *np; - ino_t inum; + struct entry *np; + dump_ino_t inum; if (ep->e_flags != REMOVED) badentry(ep, "not marked REMOVED"); if (ep->e_type == NODE) { if (ep->e_links != NULL) badentry(ep, "freeing referenced directory"); - if (ep->e_entries != NULL) - badentry(ep, "freeing non-empty directory"); + if (ep->e_entries != NULL) { + int i; + for (i = 0; i < DIRHASH_SIZE; i++) { + if (ep->e_entries[i] != NULL) + badentry(ep, "freeing non-empty directory"); + } + } } if (ep->e_ino != 0) { np = lookupino(ep->e_ino); @@ -331,9 +393,7 @@ freeentry(ep) * Relocate an entry in the tree structure */ void -moveentry(ep, newname) - register struct entry *ep; - char *newname; +moveentry(struct entry *ep, char *newname) { struct entry *np; char *cp; @@ -344,8 +404,8 @@ moveentry(ep, newname) if (np != ep->e_parent) { removeentry(ep); ep->e_parent = np; - ep->e_sibling = np->e_entries; - np->e_entries = ep; + ep->e_sibling = np->e_entries[dir_hash(ep->e_name)]; + np->e_entries[dir_hash(ep->e_name)] = ep; } cp = strrchr(newname, '/') + 1; freename(ep->e_name); @@ -361,34 +421,53 @@ moveentry(ep, newname) * Remove an entry in the tree structure */ static void -removeentry(ep) - register struct entry *ep; +removeentry(struct entry *ep) { - register struct entry *np; + struct entry *np = ep->e_parent; + struct entry *entry = np->e_entries[dir_hash(ep->e_name)]; - np = ep->e_parent; - if (np->e_entries == ep) { - np->e_entries = ep->e_sibling; + if (entry == ep) { + np->e_entries[dir_hash(ep->e_name)] = ep->e_sibling; } else { - for (np = np->e_entries; np != NULL; np = np->e_sibling) { + for (np = entry; np != NULL; np = np->e_sibling) { if (np->e_sibling == ep) { np->e_sibling = ep->e_sibling; break; } } - if (np == NULL) + if (np == NULL) { + + /* search all hash lists for renamed inodes */ + int j; + for (j = 0; j < DIRHASH_SIZE; j++) { + np = ep->e_parent; + entry = np->e_entries[j]; + if (entry == ep) { + np->e_entries[j] = ep->e_sibling; + return; + } + else { + for (np = entry; np != NULL; np = np->e_sibling) { + if (np->e_sibling == ep) { + np->e_sibling = ep->e_sibling; + return; + } + } + } + } badentry(ep, "cannot find entry in parent list"); + } } } /* * Table of unused string entries, sorted by length. - * + * * Entries are allocated in STRTBLINCR sized pieces so that names * of similar lengths can use the same entry. The value of STRTBLINCR * is chosen so that every entry has at least enough space to hold * a "struct strtbl" header. Thus every entry can be linked onto an - * apprpriate free list. + * appropriate free list. * * NB. The macro "allocsize" below assumes that "struct strhdr" * has a size that is a power of two. @@ -400,15 +479,14 @@ struct strhdr { #define STRTBLINCR (sizeof(struct strhdr)) #define allocsize(size) (((size) + 1 + STRTBLINCR - 1) & ~(STRTBLINCR - 1)) -static struct strhdr strtblhdr[allocsize(NAME_MAX) / STRTBLINCR]; +static struct strhdr strtblhdr[allocsize(MAXNAMLEN) / STRTBLINCR]; /* * Allocate space for a name. It first looks to see if it already * has an appropriate sized entry, and if not allocates a new one. */ char * -savename(name) - char *name; +savename(char *name) { struct strhdr *np; long len; @@ -424,7 +502,7 @@ savename(name) } else { cp = malloc((unsigned)allocsize(len)); if (cp == NULL) - panic("no space for string table\n"); + errx(1, "no space for string table"); } (void) strcpy(cp, name); return (cp); @@ -435,11 +513,10 @@ savename(name) * appropriate free list. */ void -freename(name) - char *name; +freename(char *name) { struct strhdr *tp, *np; - + tp = &strtblhdr[strlen(name) / STRTBLINCR]; np = (struct strhdr *)name; np->next = tp->next; @@ -450,58 +527,76 @@ freename(name) * Useful quantities placed at the end of a dumped symbol table. */ struct symtableheader { - long volno; - long stringsize; - long entrytblsize; + int32_t volno; + int32_t stringsize; + int32_t hashsize; + int32_t entrytblsize; time_t dumptime; time_t dumpdate; - ino_t maxino; - long ntrec; + dump_ino_t maxino; + int32_t ntrec; + int32_t zflag; }; /* * dump a snapshot of the symbol table */ void -dumpsymtable(filename, checkpt) - char *filename; - long checkpt; +dumpsymtable(char *filename, long checkpt) { - register struct entry *ep, *tep; - register ino_t i; + struct entry *ep, *tep; + dump_ino_t i; struct entry temp, *tentry; - long mynum = 1, stroff = 0; + long mynum = 1, stroff = 0, hashoff = 0; FILE *fd; struct symtableheader hdr; + struct entry *temphash[DIRHASH_SIZE]; - vprintf(stdout, "Check pointing the restore\n"); + Vprintf(stdout, "Check pointing the restore\n"); if (Nflag) return; - if ((fd = fopen(filename, "w")) == NULL) { - fprintf(stderr, "fopen: %s\n", strerror(errno)); + if ((fd = FOPEN(filename, "w")) == NULL) { + warn("fopen"); panic("cannot create save file %s for symbol table\n", filename); } clearerr(fd); /* - * Assign indicies to each entry + * Assign indices to each entry * Write out the string entries */ - for (i = WINO; i < maxino; i++) { + for (i = WINO; i <= maxino; i++) { for (ep = lookupino(i); ep != NULL; ep = ep->e_links) { ep->e_index = mynum++; (void) fwrite(ep->e_name, sizeof(char), (int)allocsize(ep->e_namlen), fd); } } + /* + * Write out e_entries tables + */ + for (i = WINO; i <= maxino; i++) { + for (ep = lookupino(i); ep != NULL; ep = ep->e_links) { + if (ep->e_entries != NULL) { + int j; + memcpy(temphash, ep->e_entries, DIRHASH_SIZE * sizeof(struct entry *)); + for (j = 0; j < DIRHASH_SIZE; j++) { + if (temphash[j]) + temphash[j] = (struct entry *)ep->e_entries[j]->e_index; + } + fwrite(temphash, DIRHASH_SIZE, sizeof(struct entry *), fd); + } + } + } /* * Convert pointers to indexes, and output */ tep = &temp; stroff = 0; - for (i = WINO; i < maxino; i++) { + hashoff = 0; + for (i = WINO; i <= maxino; i++) { for (ep = lookupino(i); ep != NULL; ep = ep->e_links) { - memmove(tep, ep, (long)sizeof(struct entry)); + memmove(tep, ep, sizeof(struct entry)); tep->e_name = (char *)stroff; stroff += allocsize(ep->e_namlen); tep->e_parent = (struct entry *)ep->e_parent->e_index; @@ -511,9 +606,10 @@ dumpsymtable(filename, checkpt) if (ep->e_sibling != NULL) tep->e_sibling = (struct entry *)ep->e_sibling->e_index; - if (ep->e_entries != NULL) - tep->e_entries = - (struct entry *)ep->e_entries->e_index; + if (ep->e_entries != NULL) { + tep->e_entries = (struct entry **)hashoff; + hashoff += DIRHASH_SIZE * sizeof(struct entry *); + } if (ep->e_next != NULL) tep->e_next = (struct entry *)ep->e_next->e_index; @@ -523,7 +619,7 @@ dumpsymtable(filename, checkpt) /* * Convert entry pointers to indexes, and output */ - for (i = 0; i < entrytblsize; i++) { + for (i = 0; (long)i < entrytblsize; i++) { if (entry[i] == NULL) tentry = NULL; else @@ -534,12 +630,14 @@ dumpsymtable(filename, checkpt) hdr.maxino = maxino; hdr.entrytblsize = entrytblsize; hdr.stringsize = stroff; + hdr.hashsize = hashoff; hdr.dumptime = dumptime; hdr.dumpdate = dumpdate; hdr.ntrec = ntrec; + hdr.zflag = zflag; (void) fwrite((char *)&hdr, sizeof(struct symtableheader), 1, fd); if (ferror(fd)) { - fprintf(stderr, "fwrite: %s\n", strerror(errno)); + warn("fwrite"); panic("output error to file %s writing symbol table\n", filename); } @@ -550,45 +648,44 @@ dumpsymtable(filename, checkpt) * Initialize a symbol table from a file */ void -initsymtable(filename) - char *filename; +initsymtable(char *filename) { char *base; long tblsize; - register struct entry *ep; + struct entry *ep; struct entry *baseep, *lep; struct symtableheader hdr; - struct stat stbuf; - register long i; + struct STAT stbuf; + long i; int fd; - vprintf(stdout, "Initialize symbol table.\n"); + Vprintf(stdout, "Initialize symbol table.\n"); if (filename == NULL) { entrytblsize = maxino / HASHFACTOR; entry = (struct entry **) calloc((unsigned)entrytblsize, sizeof(struct entry *)); if (entry == (struct entry **)NULL) - panic("no memory for entry table\n"); + errx(1, "no memory for entry table"); ep = addentry(".", ROOTINO, NODE); ep->e_flags |= NEW; return; } - if ((fd = open(filename, O_RDONLY, 0)) < 0) { - fprintf(stderr, "open: %s\n", strerror(errno)); - panic("cannot open symbol table file %s\n", filename); + if ((fd = OPEN(filename, O_RDONLY, 0)) < 0) { + warn("open"); + errx(1, "cannot open symbol table file %s", filename); } - if (fstat(fd, &stbuf) < 0) { - fprintf(stderr, "stat: %s\n", strerror(errno)); - panic("cannot stat symbol table file %s\n", filename); + if (FSTAT(fd, &stbuf) < 0) { + warn("stat"); + errx(1, "cannot stat symbol table file %s", filename); } tblsize = stbuf.st_size - sizeof(struct symtableheader); base = calloc(sizeof(char), (unsigned)tblsize); if (base == NULL) - panic("cannot allocate space for symbol table\n"); + errx(1, "cannot allocate space for symbol table"); if (read(fd, base, (int)tblsize) < 0 || read(fd, (char *)&hdr, sizeof(struct symtableheader)) < 0) { - fprintf(stderr, "read: %s\n", strerror(errno)); - panic("cannot read symbol table file %s\n", filename); + warn("read"); + errx(1, "cannot read symbol table file %s", filename); } switch (command) { case 'r': @@ -596,13 +693,9 @@ initsymtable(filename) * For normal continuation, insure that we are using * the next incremental tape */ - if (hdr.dumpdate != dumptime) { - if (hdr.dumpdate < dumptime) - fprintf(stderr, "Incremental tape too low\n"); - else - fprintf(stderr, "Incremental tape too high\n"); - done(1); - } + if (hdr.dumpdate != dumptime) + errx(1, "Incremental tape too %s", + (hdr.dumpdate < dumptime) ? "low" : "high"); break; case 'R': /* @@ -611,6 +704,7 @@ initsymtable(filename) curfile.action = SKIP; dumptime = hdr.dumptime; dumpdate = hdr.dumpdate; + zflag = hdr.zflag; if (!bflag) newtapebuf(hdr.ntrec); getvol(hdr.volno); @@ -619,11 +713,14 @@ initsymtable(filename) panic("initsymtable called from command %c\n", command); break; } - maxino = hdr.maxino; + if (hdr.maxino > maxino) { + resizemaps(maxino, hdr.maxino); + maxino = hdr.maxino; + } entrytblsize = hdr.entrytblsize; entry = (struct entry **) (base + tblsize - (entrytblsize * sizeof(struct entry *))); - baseep = (struct entry *)(base + hdr.stringsize - sizeof(struct entry)); + baseep = (struct entry *)(base + hdr.stringsize + hdr.hashsize - sizeof(struct entry)); lep = (struct entry *)entry; for (i = 0; i < entrytblsize; i++) { if (entry[i] == NULL) @@ -637,8 +734,16 @@ initsymtable(filename) ep->e_sibling = &baseep[(long)ep->e_sibling]; if (ep->e_links != NULL) ep->e_links = &baseep[(long)ep->e_links]; - if (ep->e_entries != NULL) - ep->e_entries = &baseep[(long)ep->e_entries]; + if (ep->e_type == NODE) { + int i; + ep->e_entries = (struct entry **)(base + hdr.stringsize + (long)ep->e_entries); + for (i = 0; i < DIRHASH_SIZE; i++) { + if (ep->e_entries[i]) + ep->e_entries[i] = &baseep[(long)ep->e_entries[i]]; + } + } + else + ep->e_entries = NULL; if (ep->e_next != NULL) ep->e_next = &baseep[(long)ep->e_next]; }