X-Git-Url: https://git.wh0rd.org/?p=dump.git;a=blobdiff_plain;f=restore%2Fsymtab.c;h=b69259a7fe9185986fddbe54477cac1c6ace6dfc;hp=96dee35b32ef44d5d10b898ec6fae81b0d36b52b;hb=a4bfc6ca5a01f2cef94fb6a147024e8b52101b6e;hpb=a18d599791e977f3e3d26123031e6ed4e64d6d08

diff --git a/restore/symtab.c b/restore/symtab.c
index 96dee35..b69259a 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.19 2002/07/19 14:57:40 stelian Exp $";
+	"$Id: symtab.c,v 1.25 2005/03/30 13:34:00 stelian Exp $";
 #endif /* not lint */
 
 /*
@@ -67,7 +63,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 +100,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 +185,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 +305,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 +323,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 +354,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 +403,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 +422,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 +528,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,9 +546,10 @@ 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[DIRHASH_SIZE];
 
 	Vprintf(stdout, "Check pointing the restore\n");
 	if (Nflag)
@@ -489,11 +571,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));
@@ -506,9 +605,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 +629,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;
@@ -611,11 +712,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)
@@ -629,8 +733,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];
 	}