X-Git-Url: https://git.wh0rd.org/?p=dump.git;a=blobdiff_plain;f=restore%2Fsymtab.c;h=7e5605730db48ce73ca6472178b1bcd6f5b668cd;hp=3a6b1fbc6b31345577031e8fd7c8f6f7011be575;hb=df3d2ef98b911ebb7a7b7c6137e60e28eb39e5f1;hpb=e531c44203905d5554118c09c8d0267f17879ee6

diff --git a/restore/symtab.c b/restore/symtab.c
index 3a6b1fb..7e56057 100644
--- a/restore/symtab.c
+++ b/restore/symtab.c
@@ -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.20 2002/11/15 09:25:42 stelian Exp $";
+	"$Id: symtab.c,v 1.27 2005/07/07 09:16:08 stelian Exp $";
 #endif /* not lint */
 
 /*
@@ -54,6 +50,7 @@ static const char rcsid[] =
  */
 
 #include <config.h>
+#include <compatlfs.h>
 #include <sys/param.h>
 #include <sys/stat.h>
 
@@ -67,7 +64,12 @@ static const char rcsid[] =
 #endif
 #include <bsdcompat.h>
 #else	/* __linux__ */
+#ifdef sunos
+#include <sys/fcntl.h>
+#include <bsdcompat.h>
+#else
 #include <ufs/ufs/dinode.h>
+#endif
 #endif	/* __linux__ */
 
 #include <errno.h>
@@ -99,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
@@ -165,21 +186,51 @@ deleteino(dump_ino_t inum)
 struct entry *
 lookupname(char *name)
 {
-	struct entry *ep;
+	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')
@@ -255,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)
@@ -268,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)
@@ -299,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);
@@ -343,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);
@@ -362,20 +423,40 @@ moveentry(struct entry *ep, char *newname)
 static void
 removeentry(struct entry *ep)
 {
-	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");
+		}
 	}
 }
 
@@ -448,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;
@@ -465,14 +547,15 @@ dumpsymtable(char *filename, long checkpt)
 	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;
 
 	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);
@@ -489,11 +572,33 @@ dumpsymtable(char *filename, long checkpt)
 			       (int)allocsize(ep->e_namlen), fd);
 		}
 	}
+	/*
+	 * Write out e_entries tables
+	 */
+	temphash = calloc(1, dirhash_size * sizeof(struct entry *));
+	if (temphash == NULL)
+		errx(1, "no memory for saving hashtable");
+	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);
+			}
+		}
+	}
+	free(temphash);
+
 	/*
 	 * 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));
@@ -506,9 +611,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;
@@ -529,6 +635,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;
@@ -553,7 +660,7 @@ initsymtable(char *filename)
 	struct entry *ep;
 	struct entry *baseep, *lep;
 	struct symtableheader hdr;
-	struct stat stbuf;
+	struct STAT stbuf;
 	long i;
 	int fd;
 
@@ -568,11 +675,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);
 	}
@@ -611,12 +718,14 @@ initsymtable(char *filename)
 		panic("initsymtable called from command %c\n", command);
 		break;
 	}
-	resizemaps(maxino, hdr.maxino);
-	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)
@@ -630,8 +739,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];
 	}