Sync with the latest version from NetBSD. It notably addds ISO9660 support.

Submitted by:	bapt

1 files changed, 159 insertions, 78 deletions

diff --git a/usr.sbin/makefs/walk.c b/usr.sbin/makefs/walk.c
index e485787..0d7bd8e 100644
--- a/usr.sbin/makefs/walk.c
+++ b/usr.sbin/makefs/walk.c
@@ -1,4 +1,4 @@
-/*	$NetBSD: walk.c,v 1.17 2004/06/20 22:20:18 jmc Exp $	*/
+/*	$NetBSD: walk.c,v 1.24 2008/12/28 21:51:46 christos Exp $	*/
 
 /*
  * Copyright (c) 2001 Wasabi Systems, Inc.
@@ -35,41 +35,6 @@
  * POSSIBILITY OF SUCH DAMAGE.
  */
 
-/*
- * The function link_check() was inspired from NetBSD's usr.bin/du/du.c,
- * which has the following copyright notice:
- *
- *
- * Copyright (c) 1989, 1993, 1994
- *	The Regents of the University of California.  All rights reserved.
- *
- * This code is derived from software contributed to Berkeley by
- * Chris Newcomb.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 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. 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.
- *
- * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- */
 
 #include <sys/cdefs.h>
 __FBSDID("$FreeBSD$");
@@ -84,13 +49,13 @@ __FBSDID("$FreeBSD$");
 #include <stdlib.h>
 #include <string.h>
 #include <unistd.h>
+#include <sys/stat.h>
 
 #include "makefs.h"
-
 #include "mtree.h"
-#include "extern.h"		/* NB: mtree */
+#include "extern.h"
 
-static	void	 apply_specdir(const char *, NODE *, fsnode *);
+static	void	 apply_specdir(const char *, NODE *, fsnode *, int);
 static	void	 apply_specentry(const char *, NODE *, fsnode *);
 static	fsnode	*create_fsnode(const char *, struct stat *);
 static	fsinode	*link_check(fsinode *);
@@ -164,6 +129,10 @@ walk_dir(const char *dir, fsnode *parent)
 				free(cur->inode);
 				cur->inode = curino;
 				cur->inode->nlink++;
+				if (debug & DEBUG_WALK_DIR_LINKCHECK)
+					printf("link_check: found [%llu, %llu]\n",
+					    (unsigned long long)curino->st.st_dev,
+					    (unsigned long long)curino->st.st_ino);
 			}
 		}
 		if (S_ISLNK(cur->type)) {
@@ -201,6 +170,53 @@ create_fsnode(const char *name, struct stat *stbuf)
 }
 
 /*
+ * free_fsnodes --
+ *	Removes node from tree and frees it and all of
+ *   its decendents.
+ */
+void
+free_fsnodes(fsnode *node)
+{
+	fsnode	*cur, *next;
+
+	assert(node != NULL);
+
+	/* for ".", start with actual parent node */
+	if (node->first == node) {
+		assert(node->name[0] == '.' && node->name[1] == '\0');
+		if (node->parent) {
+			assert(node->parent->child == node);
+			node = node->parent;
+		}
+	}
+
+	/* Find ourselves in our sibling list and unlink */
+	if (node->first != node) {
+		for (cur = node->first; cur->next; cur = cur->next) {
+			if (cur->next == node) {
+				cur->next = node->next;
+				node->next = NULL;
+				break;
+			}
+		}
+	}
+
+	for (cur = node; cur != NULL; cur = next) {
+		next = cur->next;
+		if (cur->child) {
+			cur->child->parent = NULL;
+			free_fsnodes(cur->child);
+		}
+		if (cur->inode->nlink-- == 1)
+			free(cur->inode);
+		if (cur->symlink)
+			free(cur->symlink);
+		free(cur->name);
+		free(cur);
+	}
+}
+
+/*
  * apply_specfile --
  *	read in the mtree(8) specfile, and apply it to the tree
  *	at dir,parent. parameters in parent on equivalent types
@@ -208,7 +224,7 @@ create_fsnode(const char *name, struct stat *stbuf)
  *	entries will be added.
  */
 void
-apply_specfile(const char *specfile, const char *dir, fsnode *parent)
+apply_specfile(const char *specfile, const char *dir, fsnode *parent, int speconly)
 {
 	struct timeval	 start;
 	FILE	*fp;
@@ -236,7 +252,8 @@ apply_specfile(const char *specfile, const char *dir, fsnode *parent)
 	assert(root->type == F_DIR);
 
 				/* merge in the changes */
-	apply_specdir(dir, root, parent);
+	apply_specdir(dir, root, parent, speconly);
+
 }
 
 static u_int
@@ -265,8 +282,9 @@ nodetoino(u_int type)
 	/* NOTREACHED */
 }
 
+
 static void
-apply_specdir(const char *dir, NODE *specnode, fsnode *dirnode)
+apply_specdir(const char *dir, NODE *specnode, fsnode *dirnode, int speconly)
 {
 	char	 path[MAXPATHLEN + 1];
 	NODE	*curnode;
@@ -287,6 +305,30 @@ apply_specdir(const char *dir, NODE *specnode, fsnode *dirnode)
 
 	apply_specentry(dir, specnode, dirnode);
 
+	/* Remove any filesystem nodes not found in specfile */
+	/* XXX inefficient.  This is O^2 in each dir and it would
+	 * have been better never to have walked this part of the tree
+	 * to begin with
+	 */
+	if (speconly) {
+		fsnode *next;
+		assert(dirnode->name[0] == '.' && dirnode->name[1] == '\0');
+		for (curfsnode = dirnode->next; curfsnode != NULL; curfsnode = next) {
+			next = curfsnode->next;
+			for (curnode = specnode->child; curnode != NULL;
+			     curnode = curnode->next) {
+				if (strcmp(curnode->name, curfsnode->name) == 0)
+					break;
+			}
+			if (curnode == NULL) {
+				if (debug & DEBUG_APPLY_SPECONLY) {
+					printf("apply_specdir: trimming %s/%s %p\n", dir, curfsnode->name, curfsnode);
+				}
+				free_fsnodes(curfsnode);
+			}
+		}
+	}
+
 			/* now walk specnode->child matching up with dirnode */
 	for (curnode = specnode->child; curnode != NULL;
 	    curnode = curnode->next) {
@@ -328,6 +370,9 @@ apply_specdir(const char *dir, NODE *specnode, fsnode *dirnode)
 			    curnode->flags & F_GNAME, "group");
 			NODETEST(curnode->flags & F_UID ||
 			    curnode->flags & F_UNAME, "user");
+/*			if (curnode->type == F_BLOCK || curnode->type == F_CHAR)
+				NODETEST(curnode->flags & F_DEV,
+				    "device number");*/
 #undef NODETEST
 
 			if (debug & DEBUG_APPLY_SPECFILE)
@@ -367,7 +412,7 @@ apply_specdir(const char *dir, NODE *specnode, fsnode *dirnode)
 			if (curfsnode->type != S_IFDIR)
 				errx(1, "`%s' is not a directory", path);
 			assert (curfsnode->child != NULL);
-			apply_specdir(path, curnode, curfsnode->child);
+			apply_specdir(path, curnode, curfsnode->child, speconly);
 		}
 	}
 }
@@ -444,6 +489,12 @@ apply_specentry(const char *dir, NODE *specnode, fsnode *dirnode)
 		dirnode->inode->st.st_flags = specnode->st_flags;
 	}
 #endif
+/*	if (specnode->flags & F_DEV) {
+		ASEPRINT("rdev", "%#llx",
+		    (unsigned long long)dirnode->inode->st.st_rdev,
+		    (unsigned long long)specnode->st_rdev);
+		dirnode->inode->st.st_rdev = specnode->st_rdev;
+	}*/
 #undef ASEPRINT
 
 	dirnode->flags |= FSNODE_F_HASSPEC;
@@ -493,11 +544,11 @@ dump_fsnodes(const char *dir, fsnode *root)
 /*
  * inode_type --
  *	for a given inode type `mode', return a descriptive string.
+ *	for most cases, uses inotype() from mtree/misc.c
  */
 const char *
 inode_type(mode_t mode)
 {
-
 	if (S_ISREG(mode))
 		return ("file");
 	if (S_ISLNK(mode))
@@ -521,48 +572,78 @@ inode_type(mode_t mode)
 
 /*
  * link_check --
- *	return pointer to fsnode matching `entry's st_ino & st_dev if it exists,
+ *	return pointer to fsinode matching `entry's st_ino & st_dev if it exists,
  *	otherwise add `entry' to table and return NULL
  */
+/* This was borrowed from du.c and tweaked to keep an fsnode 
+ * pointer instead. -- dbj@netbsd.org
+ */
 static fsinode *
 link_check(fsinode *entry)
 {
-	static	struct dupnode {
-		uint32_t	dev;
-		uint64_t	ino;
-		fsinode		*dup;
-	} *dups, *newdups;
-	static	int	ndups, maxdups;
-
-	int	i;
-
-	assert (entry != NULL);
-
-		/* XXX; maybe traverse in reverse for speed? */
-	for (i = 0; i < ndups; i++) {
-		if (dups[i].dev == entry->st.st_dev &&
-		    dups[i].ino == entry->st.st_ino) {
-			if (debug & DEBUG_WALK_DIR_LINKCHECK)
-				printf("link_check: found [%d,%d]\n",
-				    entry->st.st_dev, entry->st.st_ino);
-			return (dups[i].dup);
+	static struct entry {
+		fsinode *data;
+	} *htable;
+	static int htshift;  /* log(allocated size) */
+	static int htmask;   /* allocated size - 1 */
+	static int htused;   /* 2*number of insertions */
+	int h, h2;
+	uint64_t tmp;
+	/* this constant is (1<<64)/((1+sqrt(5))/2)
+	 * aka (word size)/(golden ratio)
+	 */
+	const uint64_t HTCONST = 11400714819323198485ULL;
+	const int HTBITS = 64;
+	
+	/* Never store zero in hashtable */
+	assert(entry);
+
+	/* Extend hash table if necessary, keep load under 0.5 */
+	if (htused<<1 >= htmask) {
+		struct entry *ohtable;
+
+		if (!htable)
+			htshift = 10;   /* starting hashtable size */
+		else
+			htshift++;   /* exponential hashtable growth */
+
+		htmask  = (1 << htshift) - 1;
+		htused = 0;
+
+		ohtable = htable;
+		htable = calloc(htmask+1, sizeof(*htable));
+		if (!htable)
+			err(1, "Memory allocation error");
+
+		/* populate newly allocated hashtable */
+		if (ohtable) {
+			int i;
+			for (i = 0; i <= htmask>>1; i++)
+				if (ohtable[i].data)
+					link_check(ohtable[i].data);
+			free(ohtable);
 		}
 	}
 
-	if (debug & DEBUG_WALK_DIR_LINKCHECK)
-		printf("link_check: no match for [%d, %d]\n",
-		    entry->st.st_dev, entry->st.st_ino);
-	if (ndups == maxdups) {
-		if ((newdups = realloc(dups, sizeof(struct dupnode) * (maxdups + 128)))
-		    == NULL)
-			err(1, "Memory allocation error");
-		dups = newdups;
-		maxdups += 128;
+	/* multiplicative hashing */
+	tmp = entry->st.st_dev;
+	tmp <<= HTBITS>>1;
+	tmp |=  entry->st.st_ino;
+	tmp *= HTCONST;
+	h  = tmp >> (HTBITS - htshift);
+	h2 = 1 | ( tmp >> (HTBITS - (htshift<<1) - 1)); /* must be odd */
+	
+	/* open address hashtable search with double hash probing */
+	while (htable[h].data) {
+		if ((htable[h].data->st.st_ino == entry->st.st_ino) &&
+		    (htable[h].data->st.st_dev == entry->st.st_dev)) {
+			return htable[h].data;
+		}
+		h = (h + h2) & htmask;
 	}
-	dups[ndups].dev = entry->st.st_dev;
-	dups[ndups].ino = entry->st.st_ino;
-	dups[ndups].dup = entry;
-	ndups++;
 
-	return (NULL);
+	/* Insert the current entry into hashtable */
+	htable[h].data = entry;
+	htused++;
+	return NULL;
 }