X-Git-Url: https://git.wh0rd.org/?p=dump.git;a=blobdiff_plain;f=restore%2Fsymtab.c;h=06548bcee6e5a84c7bbd0e8eae6c614eb877b57d;hp=740165b241631814a54eef7c65ef1ea7ea04e6c3;hb=26ce8fc8f42b8cdd92e9eaadae48be256813b001;hpb=92a9bf12543aadfcc46e7ab9c2729b4d4d1f22ee diff --git a/restore/symtab.c b/restore/symtab.c index 740165b..06548bc 100644 --- a/restore/symtab.c +++ b/restore/symtab.c @@ -2,7 +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 , 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. * @@ -40,7 +37,7 @@ #ifndef lint static const char rcsid[] = - "$Id: symtab.c,v 1.8 2000/03/01 10:16:05 stelian Exp $"; + "$Id: symtab.c,v 1.26 2005/07/07 08:47:16 stelian Exp $"; #endif /* not lint */ /* @@ -52,15 +49,27 @@ static const char rcsid[] = * 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 @@ -89,17 +98,36 @@ static const char rcsid[] = 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(ino_t inum) +lookupino(dump_ino_t inum) { - register struct entry *ep; + struct entry *ep; if (inum < WINO || inum >= maxino) return (NULL); @@ -113,7 +141,7 @@ lookupino(ino_t inum) * Add an entry into the entry table */ static void -addino(ino_t inum, struct entry *np) +addino(dump_ino_t inum, struct entry *np) { struct entry **epp; @@ -133,9 +161,9 @@ addino(ino_t inum, struct entry *np) * Delete an entry from the entry table */ void -deleteino(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 +186,51 @@ deleteino(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') @@ -209,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]; ) { @@ -234,9 +292,9 @@ static struct entry *freelist = NULL; * add an entry to the symbol table */ struct entry * -addentry(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; @@ -245,9 +303,14 @@ addentry(char *name, ino_t inum, int type) } 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) @@ -261,8 +324,8 @@ addentry(char *name, 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) @@ -284,16 +347,21 @@ addentry(char *name, ino_t inum, int type) void 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); @@ -336,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); @@ -355,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"); + } } } @@ -414,7 +502,7 @@ savename(char *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); @@ -441,11 +529,13 @@ freename(char *name) struct symtableheader { int32_t volno; int32_t stringsize; + int32_t hashsize; int32_t entrytblsize; time_t dumptime; time_t dumpdate; - ino_t maxino; + dump_ino_t maxino; int32_t ntrec; + int32_t zflag; }; /* @@ -454,17 +544,18 @@ struct symtableheader { void 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"); 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); @@ -481,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)); @@ -498,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; @@ -510,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 @@ -521,9 +630,11 @@ 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; + hdr.zflag = zflag; (void) fwrite((char *)&hdr, sizeof(struct symtableheader), 1, fd); if (ferror(fd)) { warn("fwrite"); @@ -541,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"); @@ -554,27 +665,27 @@ initsymtable(char *filename) 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) { + if ((fd = OPEN(filename, O_RDONLY, 0)) < 0) { warn("open"); - panic("cannot open symbol table file %s\n", filename); + errx(1, "cannot open symbol table file %s", filename); } - if (fstat(fd, &stbuf) < 0) { + if (FSTAT(fd, &stbuf) < 0) { warn("stat"); - panic("cannot stat symbol table file %s\n", filename); + 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) { warn("read"); - panic("cannot read symbol table file %s\n", filename); + errx(1, "cannot read symbol table file %s", filename); } switch (command) { case 'r': @@ -593,6 +704,7 @@ initsymtable(char *filename) curfile.action = SKIP; dumptime = hdr.dumptime; dumpdate = hdr.dumpdate; + zflag = hdr.zflag; if (!bflag) newtapebuf(hdr.ntrec); getvol(hdr.volno); @@ -601,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) @@ -619,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]; }