X-Git-Url: https://git.wh0rd.org/?p=dump.git;a=blobdiff_plain;f=restore%2Fsymtab.c;h=06548bcee6e5a84c7bbd0e8eae6c614eb877b57d;hp=2e157f4ab4814903bf1f044bdcafc46ca625234f;hb=26ce8fc8f42b8cdd92e9eaadae48be256813b001;hpb=86fab47e75fc141db053271654a2570fddcd0f46 diff --git a/restore/symtab.c b/restore/symtab.c index 2e157f4..06548bc 100644 --- a/restore/symtab.c +++ b/restore/symtab.c @@ -2,8 +2,8 @@ * Ported to Linux's Second Extended File System as part of the * dump and restore backup suit * Remy Card , 1994-1997 - * Stelian Pop , 1999-2000 - * Stelian Pop - Alcôve , 2000 + * Stelian Pop , 1999-2000 + * Stelian Pop - Alcôve , 2000-2002 */ /* @@ -18,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. * @@ -41,7 +37,7 @@ #ifndef lint static const char rcsid[] = - "$Id: symtab.c,v 1.15 2001/05/12 11:36:12 stelian Exp $"; + "$Id: symtab.c,v 1.26 2005/07/07 08:47:16 stelian Exp $"; #endif /* not lint */ /* @@ -54,16 +50,26 @@ static const char rcsid[] = */ #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 @@ -95,6 +101,25 @@ static long entrytblsize; 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 @@ -102,7 +127,7 @@ static void removeentry __P((struct entry *)); struct entry * lookupino(dump_ino_t inum) { - register struct entry *ep; + struct entry *ep; if (inum < WINO || inum >= maxino) return (NULL); @@ -138,7 +163,7 @@ addino(dump_ino_t inum, struct entry *np) void deleteino(dump_ino_t inum) { - register struct entry *next; + struct entry *next; struct entry **prev; if (inum < WINO || inum >= maxino) @@ -161,21 +186,51 @@ deleteino(dump_ino_t inum) struct entry * 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) { + 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') @@ -212,7 +267,7 @@ lookupparent(char *name) char * myname(struct entry *ep) { - register char *cp; + char *cp; static char namebuf[MAXPATHLEN]; for (cp = &namebuf[MAXPATHLEN - 2]; cp > &namebuf[ep->e_namlen]; ) { @@ -239,7 +294,7 @@ static struct entry *freelist = NULL; struct entry * addentry(char *name, dump_ino_t inum, int type) { - register struct entry *np, *ep; + struct entry *np, *ep; if (freelist != NULL) { np = freelist; @@ -251,6 +306,11 @@ addentry(char *name, dump_ino_t inum, int type) 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) @@ -264,8 +324,8 @@ addentry(char *name, dump_ino_t inum, int 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) @@ -287,7 +347,7 @@ addentry(char *name, dump_ino_t inum, int type) void freeentry(struct entry *ep) { - register struct entry *np; + struct entry *np; dump_ino_t inum; if (ep->e_flags != REMOVED) @@ -295,8 +355,13 @@ freeentry(struct entry *ep) 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); @@ -339,8 +404,8 @@ moveentry(struct entry *ep, char *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); @@ -358,20 +423,40 @@ moveentry(struct entry *ep, char *newname) static void 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"); + } } } @@ -444,6 +529,7 @@ freename(char *name) struct symtableheader { int32_t volno; int32_t stringsize; + int32_t hashsize; int32_t entrytblsize; time_t dumptime; time_t dumpdate; @@ -458,17 +544,18 @@ struct symtableheader { void dumpsymtable(char *filename, long checkpt) { - register struct entry *ep, *tep; - register dump_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"); if (Nflag) return; - if ((fd = fopen(filename, "w")) == NULL) { + if ((fd = FOPEN(filename, "w")) == NULL) { warn("fopen"); panic("cannot create save file %s for symbol table\n", filename); @@ -485,11 +572,28 @@ dumpsymtable(char *filename, long checkpt) (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; + hashoff = 0; for (i = WINO; i <= maxino; i++) { for (ep = lookupino(i); ep != NULL; ep = ep->e_links) { memmove(tep, ep, sizeof(struct entry)); @@ -502,9 +606,10 @@ dumpsymtable(char *filename, long 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; @@ -514,7 +619,7 @@ dumpsymtable(char *filename, long 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 @@ -525,6 +630,7 @@ dumpsymtable(char *filename, long checkpt) hdr.maxino = maxino; hdr.entrytblsize = entrytblsize; hdr.stringsize = stroff; + hdr.hashsize = hashoff; hdr.dumptime = dumptime; hdr.dumpdate = dumpdate; hdr.ntrec = ntrec; @@ -546,11 +652,11 @@ 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"); @@ -564,11 +670,11 @@ initsymtable(char *filename) ep->e_flags |= NEW; return; } - if ((fd = open(filename, O_RDONLY, 0)) < 0) { + if ((fd = OPEN(filename, O_RDONLY, 0)) < 0) { warn("open"); errx(1, "cannot open symbol table file %s", filename); } - if (fstat(fd, &stbuf) < 0) { + if (FSTAT(fd, &stbuf) < 0) { warn("stat"); errx(1, "cannot stat symbol table file %s", filename); } @@ -607,11 +713,14 @@ initsymtable(char *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) @@ -625,8 +734,16 @@ initsymtable(char *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]; }