walk.c revision 1.34 
1/*	$NetBSD: walk.c,v 1.34 2024/04/23 22:12:16 christos Exp $	*/
2
3/*
4 * Copyright (c) 2001 Wasabi Systems, Inc.
5 * All rights reserved.
6 *
7 * Written by Luke Mewburn for Wasabi Systems, Inc.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 * 1. Redistributions of source code must retain the above copyright
13 *    notice, this list of conditions and the following disclaimer.
14 * 2. Redistributions in binary form must reproduce the above copyright
15 *    notice, this list of conditions and the following disclaimer in the
16 *    documentation and/or other materials provided with the distribution.
17 * 3. All advertising materials mentioning features or use of this software
18 *    must display the following acknowledgement:
19 *      This product includes software developed for the NetBSD Project by
20 *      Wasabi Systems, Inc.
21 * 4. The name of Wasabi Systems, Inc. may not be used to endorse
22 *    or promote products derived from this software without specific prior
23 *    written permission.
24 *
25 * THIS SOFTWARE IS PROVIDED BY WASABI SYSTEMS, INC. ``AS IS'' AND
26 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
27 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
28 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL WASABI SYSTEMS, INC
29 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
30 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
31 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
32 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
33 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
34 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
35 * POSSIBILITY OF SUCH DAMAGE.
36 */
37
38#if HAVE_NBTOOL_CONFIG_H
39#include "nbtool_config.h"
40#endif
41
42#include <sys/cdefs.h>
43#if defined(__RCSID) && !defined(__lint)
44__RCSID("$NetBSD: walk.c,v 1.34 2024/04/23 22:12:16 christos Exp $");
45#endif	/* !__lint */
46
47#include <sys/param.h>
48#include <sys/stat.h>
49
50#include <assert.h>
51#include <errno.h>
52#include <fcntl.h>
53#include <stdio.h>
54#include <dirent.h>
55#include <stdlib.h>
56#include <string.h>
57#include <unistd.h>
58#include <util.h>
59
60#include "makefs.h"
61#include "mtree.h"
62
63static	void	 apply_specdir(const char *, NODE *, fsnode *, int);
64static	void	 apply_specentry(const char *, NODE *, fsnode *);
65static	fsnode	*create_fsnode(const char *, const char *, const char *,
66			       struct stat *);
67static	fsinode	*link_check(fsinode *);
68
69/*
70 * fsnode_cmp --
71 *	This function is used by `qsort` so sort one directory's
72 *	entries.  `.` is always first, sollowed by anything else
73 *	as compared by `strcmp()`.
74 */
75static int
76fsnode_cmp (const void *_left, const void *_right)
77{
78	const fsnode * const left  = *(const fsnode * const *)_left;
79	const fsnode * const right = *(const fsnode * const *)_right;
80
81	if (strcmp (left->name, ".") == 0)
82		return -1;
83	if (strcmp (right->name, ".") == 0)
84		return 1;
85	return strcmp (left->name, right->name);
86}
87
88/*
89 * walk_dir --
90 *	build a tree of fsnodes from `root' and `dir', with a parent
91 *	fsnode of `parent' (which may be NULL for the root of the tree).
92 *	append the tree to a fsnode of `join' if it is not NULL.
93 *	each "level" is a directory, with the "." entry guaranteed to be
94 *	at the start of the list, and without ".." entries.
95 */
96fsnode *
97walk_dir(const char *root, const char *dir, fsnode *parent, fsnode *join,
98    int replace, int follow)
99{
100	fsnode		*first, *cur, *prev, *last;
101	DIR		*dirp;
102	struct dirent	*dent;
103	char		path[MAXPATHLEN + 1];
104	struct stat	stbuf;
105	char		*name, *rp;
106	int		dot, len;
107
108	fsnode **list, **listptr;
109	int num = 0;
110
111	assert(root != NULL);
112	assert(dir != NULL);
113
114	len = snprintf(path, sizeof(path), "%s/%s", root, dir);
115	if (len >= (int)sizeof(path))
116		errx(EXIT_FAILURE, "Pathname too long.");
117	if (debug & DEBUG_WALK_DIR)
118		printf("walk_dir: %s %p\n", path, parent);
119	if ((dirp = opendir(path)) == NULL)
120		err(EXIT_FAILURE, "Can't opendir `%s'", path);
121	rp = path + strlen(root) + 1;
122	if (join != NULL) {
123		first = cur = join;
124		while (cur->next != NULL)
125			cur = cur->next;
126		prev = last = cur;
127	} else
128		last = first = prev = NULL;
129	while ((dent = readdir(dirp)) != NULL) {
130		name = dent->d_name;
131		dot = 0;
132		if (name[0] == '.')
133			switch (name[1]) {
134			case '\0':	/* "." */
135				if (join != NULL)
136					continue;
137				dot = 1;
138				break;
139			case '.':	/* ".." */
140				if (name[2] == '\0')
141					continue;
142				/* FALLTHROUGH */
143			default:
144				dot = 0;
145			}
146		if (debug & DEBUG_WALK_DIR_NODE)
147			printf("scanning %s/%s/%s\n", root, dir, name);
148		if (snprintf(path + len, sizeof(path) - len, "/%s", name) >=
149		    (int)sizeof(path) - len)
150			errx(EXIT_FAILURE, "Pathname too long.");
151		if (follow) {
152			if (stat(path, &stbuf) == -1)
153				err(EXIT_FAILURE, "Can't stat `%s'", path);
154		} else {
155			if (lstat(path, &stbuf) == -1)
156				err(EXIT_FAILURE, "Can't lstat `%s'", path);
157		}
158#ifdef S_ISSOCK
159		if (S_ISSOCK(stbuf.st_mode & S_IFMT)) {
160			if (debug & DEBUG_WALK_DIR_NODE)
161				printf("  skipping socket %s\n", path);
162			continue;
163		}
164#endif
165
166		if (join != NULL) {
167			cur = join->next;
168			for (;;) {
169				if (cur == NULL || strcmp(cur->name, name) == 0)
170					break;
171				if (cur == last) {
172					cur = NULL;
173					break;
174				}
175				cur = cur->next;
176			}
177			if (cur != NULL) {
178				if (S_ISDIR(cur->type) &&
179				    S_ISDIR(stbuf.st_mode)) {
180					if (debug & DEBUG_WALK_DIR_NODE)
181						printf("merging %s with %p\n",
182						    path, cur->child);
183					cur->child = walk_dir(root, rp, cur,
184					    cur->child, replace, follow);
185					continue;
186				}
187				if (!replace)
188					errx(EXIT_FAILURE,
189					    "Can't merge %s `%s' with "
190					    "existing %s",
191					    inode_type(stbuf.st_mode), path,
192					    inode_type(cur->type));
193				else {
194					if (debug & DEBUG_WALK_DIR_NODE)
195						printf("replacing %s %s\n",
196						    inode_type(stbuf.st_mode),
197						    path);
198					if (cur == join->next)
199						join->next = cur->next;
200					else {
201						fsnode *p;
202						for (p = join->next;
203						    p->next != cur; p = p->next)
204							continue;
205						p->next = cur->next;
206					}
207					free(cur);
208				}
209			}
210		}
211
212		cur = create_fsnode(root, dir, name, &stbuf);
213		cur->parent = parent;
214		if (dot) {
215				/* ensure "." is at the start of the list */
216			cur->next = first;
217			first = cur;
218			if (! prev)
219				prev = cur;
220			cur->first = first;
221		} else {			/* not "." */
222			if (prev)
223				prev->next = cur;
224			prev = cur;
225			if (!first)
226				first = cur;
227			cur->first = first;
228			if (S_ISDIR(cur->type)) {
229				cur->child = walk_dir(root, rp, cur, NULL,
230				    replace, follow);
231				continue;
232			}
233		}
234		if (stbuf.st_nlink > 1) {
235			fsinode	*curino;
236
237			curino = link_check(cur->inode);
238			if (curino != NULL) {
239				free(cur->inode);
240				cur->inode = curino;
241				cur->inode->nlink++;
242				if (debug & DEBUG_WALK_DIR_LINKCHECK)
243					printf("link_check: found [%llu, %llu]\n",
244					    (unsigned long long)curino->st.st_dev,
245					    (unsigned long long)curino->st.st_ino);
246			}
247		}
248		if (S_ISLNK(cur->type)) {
249			char	slink[PATH_MAX+1];
250			int	llen;
251
252			llen = readlink(path, slink, sizeof(slink) - 1);
253			if (llen == -1)
254				err(EXIT_FAILURE, "Readlink `%s'", path);
255			slink[llen] = '\0';
256			cur->symlink = estrdup(slink);
257		}
258	}
259	assert(first != NULL);
260	if (join == NULL)
261		for (cur = first->next; cur != NULL; cur = cur->next)
262			cur->first = first;
263	if (closedir(dirp) == -1)
264		err(EXIT_FAILURE, "Can't closedir `%s/%s'", root, dir);
265
266	/*
267	 * Sort entries.
268	 */
269	/* Create a plain list: Count, alloc, add.  */
270	for (fsnode *tmp = first; tmp; tmp = tmp->next) {
271		num++;
272		if (debug & DEBUG_DUMP_FSNODES_VERBOSE)
273			printf ("pre sort: %s %s %s\n", root, dir, tmp->name);
274	}
275	list = listptr = ecalloc (num, sizeof (*list));
276	for (fsnode *tmp = first; tmp; tmp = tmp->next)
277		*listptr++ = tmp;
278	/* Sort plain list.  */
279	qsort (list, num, sizeof (*list), &fsnode_cmp);
280	/* Rewire.  */
281	for (int i = 0; i < num - 1; ++i)
282		list[i]->next = list[i+1];
283	list[num - 1]->next = NULL;
284	first = list[0];
285	/* Check `first` to be ".".  */
286	assert (strcmp (first->name, ".") == 0);
287	/* Free.  */
288	free (list);
289	/* Dump sorted state.  */
290	if (debug & DEBUG_DUMP_FSNODES_VERBOSE)
291		for (fsnode *tmp = first; tmp; tmp = tmp->next)
292			printf ("post sort: %s %s %s\n", root, dir, tmp->name);
293
294	return first;
295}
296
297static fsnode *
298create_fsnode(const char *root, const char *path, const char *name,
299    struct stat *stbuf)
300{
301	fsnode *cur;
302
303	cur = ecalloc(1, sizeof(*cur));
304	cur->path = estrdup(path);
305	cur->name = estrdup(name);
306	cur->inode = ecalloc(1, sizeof(*cur->inode));
307	cur->root = root;
308	cur->type = stbuf->st_mode & S_IFMT;
309	cur->inode->nlink = 1;
310	cur->inode->st = *stbuf;
311	if (stampst.st_ino) {
312		cur->inode->st.st_atime = stampst.st_atime;
313		cur->inode->st.st_mtime = stampst.st_mtime;
314		cur->inode->st.st_ctime = stampst.st_ctime;
315#if HAVE_STRUCT_STAT_ST_MTIMENSEC
316		cur->inode->st.st_atimensec = stampst.st_atimensec;
317		cur->inode->st.st_mtimensec = stampst.st_mtimensec;
318		cur->inode->st.st_ctimensec = stampst.st_ctimensec;
319#endif
320#if HAVE_STRUCT_STAT_BIRTHTIME
321		cur->inode->st.st_birthtime = stampst.st_birthtime;
322		cur->inode->st.st_birthtimensec = stampst.st_birthtimensec;
323#endif
324	}
325	return (cur);
326}
327
328/*
329 * free_fsnodes --
330 *	Removes node from tree and frees it and all of
331 *   its descendents.
332 */
333void
334free_fsnodes(fsnode *node)
335{
336	fsnode	*cur, *next;
337
338	assert(node != NULL);
339
340	/* for ".", start with actual parent node */
341	if (node->first == node) {
342		assert(node->name[0] == '.' && node->name[1] == '\0');
343		if (node->parent) {
344			assert(node->parent->child == node);
345			node = node->parent;
346		}
347	}
348
349	/* Find ourselves in our sibling list and unlink */
350	if (node->first != node) {
351		for (cur = node->first; cur->next; cur = cur->next) {
352			if (cur->next == node) {
353				cur->next = node->next;
354				node->next = NULL;
355				break;
356			}
357		}
358	}
359
360	for (cur = node; cur != NULL; cur = next) {
361		next = cur->next;
362		if (cur->child) {
363			cur->child->parent = NULL;
364			free_fsnodes(cur->child);
365		}
366		if (cur->inode->nlink-- == 1)
367			free(cur->inode);
368		if (cur->symlink)
369			free(cur->symlink);
370		free(cur->path);
371		free(cur->name);
372		free(cur);
373	}
374}
375
376/*
377 * apply_specfile --
378 *	read in the mtree(8) specfile, and apply it to the tree
379 *	at dir,parent. parameters in parent on equivalent types
380 *	will be changed to those found in specfile, and missing
381 *	entries will be added.
382 */
383void
384apply_specfile(const char *specfile, const char *dir, fsnode *parent, int speconly)
385{
386	struct timeval	 start;
387	FILE	*fp;
388	NODE	*root;
389
390	assert(specfile != NULL);
391	assert(parent != NULL);
392
393	if (debug & DEBUG_APPLY_SPECFILE)
394		printf("apply_specfile: %s, %s %p\n", specfile, dir, parent);
395
396				/* read in the specfile */
397	if ((fp = fopen(specfile, "r")) == NULL)
398		err(EXIT_FAILURE, "Can't open `%s'", specfile);
399	TIMER_START(start);
400	root = spec(fp);
401	TIMER_RESULTS(start, "spec");
402	if (fclose(fp) == EOF)
403		err(EXIT_FAILURE, "Can't close `%s'", specfile);
404
405				/* perform some sanity checks */
406	if (root == NULL)
407		errx(EXIT_FAILURE,
408		    "Specfile `%s' did not contain a tree", specfile);
409	assert(strcmp(root->name, ".") == 0);
410	assert(root->type == F_DIR);
411
412				/* merge in the changes */
413	apply_specdir(dir, root, parent, speconly);
414
415	free_nodes(root);
416}
417
418static void
419apply_specdir(const char *dir, NODE *specnode, fsnode *dirnode, int speconly)
420{
421	char	 path[MAXPATHLEN + 1];
422	NODE	*curnode;
423	fsnode	*curfsnode;
424
425	assert(specnode != NULL);
426	assert(dirnode != NULL);
427
428	if (debug & DEBUG_APPLY_SPECFILE)
429		printf("apply_specdir: %s %p %p\n", dir, specnode, dirnode);
430
431	if (specnode->type != F_DIR)
432		errx(EXIT_FAILURE, "Specfile node `%s/%s' is not a directory",
433		    dir, specnode->name);
434	if (dirnode->type != S_IFDIR)
435		errx(EXIT_FAILURE, "Directory node `%s/%s' is not a directory",
436		    dir, dirnode->name);
437
438	apply_specentry(dir, specnode, dirnode);
439
440	/* Remove any filesystem nodes not found in specfile */
441	/* XXX inefficient.  This is O^2 in each dir and it would
442	 * have been better never to have walked this part of the tree
443	 * to begin with
444	 */
445	if (speconly) {
446		fsnode *next;
447		assert(dirnode->name[0] == '.' && dirnode->name[1] == '\0');
448		for (curfsnode = dirnode->next; curfsnode != NULL; curfsnode = next) {
449			next = curfsnode->next;
450			for (curnode = specnode->child; curnode != NULL;
451			     curnode = curnode->next) {
452				if (strcmp(curnode->name, curfsnode->name) == 0)
453					break;
454			}
455			if (curnode == NULL) {
456				if (debug & DEBUG_APPLY_SPECONLY) {
457					printf("apply_specdir: trimming %s/%s %p\n", dir, curfsnode->name, curfsnode);
458				}
459				free_fsnodes(curfsnode);
460			}
461		}
462	}
463
464			/* now walk specnode->child matching up with dirnode */
465	for (curnode = specnode->child; curnode != NULL;
466	    curnode = curnode->next) {
467		if (debug & DEBUG_APPLY_SPECENTRY)
468			printf("apply_specdir:  spec %s\n",
469			    curnode->name);
470		for (curfsnode = dirnode->next; curfsnode != NULL;
471		    curfsnode = curfsnode->next) {
472#if 0	/* too verbose for now */
473			if (debug & DEBUG_APPLY_SPECENTRY)
474				printf("apply_specdir:  dirent %s\n",
475				    curfsnode->name);
476#endif
477			if (strcmp(curnode->name, curfsnode->name) == 0)
478				break;
479		}
480		if ((size_t)snprintf(path, sizeof(path), "%s/%s",
481		    dir, curnode->name) >= sizeof(path))
482			errx(EXIT_FAILURE, "Pathname too long.");
483		if (curfsnode == NULL) {	/* need new entry */
484			struct stat	stbuf;
485
486					    /*
487					     * don't add optional spec entries
488					     * that lack an existing fs entry
489					     */
490			if ((curnode->flags & F_OPT) &&
491			    lstat(path, &stbuf) == -1)
492					continue;
493
494					/* check that enough info is provided */
495#define NODETEST(t, m)							\
496			if (!(t))					\
497				errx(EXIT_FAILURE,			\
498				    "`%s': %s not provided", path, m)
499			NODETEST(curnode->flags & F_TYPE, "type");
500			NODETEST(curnode->flags & F_MODE, "mode");
501				/* XXX: require F_TIME ? */
502			NODETEST(curnode->flags & F_GID ||
503			    curnode->flags & F_GNAME, "group");
504			NODETEST(curnode->flags & F_UID ||
505			    curnode->flags & F_UNAME, "user");
506			if (curnode->type == F_BLOCK || curnode->type == F_CHAR)
507				NODETEST(curnode->flags & F_DEV,
508				    "device number");
509#undef NODETEST
510
511			if (debug & DEBUG_APPLY_SPECFILE)
512				printf("apply_specdir: adding %s\n",
513				    curnode->name);
514					/* build minimal fsnode */
515			memset(&stbuf, 0, sizeof(stbuf));
516			stbuf.st_mode = nodetoino(curnode->type);
517			stbuf.st_nlink = 1;
518			stbuf.st_mtime = stbuf.st_atime =
519			    stbuf.st_ctime = start_time.tv_sec;
520#if HAVE_STRUCT_STAT_ST_MTIMENSEC
521			stbuf.st_mtimensec = stbuf.st_atimensec =
522			    stbuf.st_ctimensec = start_time.tv_nsec;
523#endif
524			curfsnode = create_fsnode(".", ".", curnode->name,
525			    &stbuf);
526			curfsnode->parent = dirnode->parent;
527			curfsnode->first = dirnode;
528			curfsnode->next = dirnode->next;
529			dirnode->next = curfsnode;
530			if (curfsnode->type == S_IFDIR) {
531					/* for dirs, make "." entry as well */
532				curfsnode->child = create_fsnode(".", ".", ".",
533				    &stbuf);
534				curfsnode->child->parent = curfsnode;
535				curfsnode->child->first = curfsnode->child;
536			}
537			if (curfsnode->type == S_IFLNK) {
538				assert(curnode->slink != NULL);
539					/* for symlinks, copy the target */
540				curfsnode->symlink = estrdup(curnode->slink);
541			}
542		}
543		apply_specentry(dir, curnode, curfsnode);
544		if (curnode->type == F_DIR) {
545			if (curfsnode->type != S_IFDIR)
546				errx(EXIT_FAILURE,
547				    "`%s' is not a directory", path);
548			assert (curfsnode->child != NULL);
549			apply_specdir(path, curnode, curfsnode->child, speconly);
550		}
551	}
552}
553
554static void
555apply_specentry(const char *dir, NODE *specnode, fsnode *dirnode)
556{
557
558	assert(specnode != NULL);
559	assert(dirnode != NULL);
560
561	if (nodetoino(specnode->type) != dirnode->type)
562		errx(EXIT_FAILURE,
563		    "`%s/%s' type mismatch: specfile %s, tree %s",
564		    dir, specnode->name, inode_type(nodetoino(specnode->type)),
565		    inode_type(dirnode->type));
566
567	if (debug & DEBUG_APPLY_SPECENTRY)
568		printf("apply_specentry: %s/%s\n", dir, dirnode->name);
569
570#define ASEPRINT(t, b, o, n) \
571		if (debug & DEBUG_APPLY_SPECENTRY) \
572			printf("\t\t\tchanging %s from " b " to " b "\n", \
573			    t, o, n)
574
575	if (specnode->flags & (F_GID | F_GNAME)) {
576		ASEPRINT("gid", "%d",
577		    dirnode->inode->st.st_gid, specnode->st_gid);
578		dirnode->inode->st.st_gid = specnode->st_gid;
579	}
580	if (specnode->flags & F_MODE) {
581		ASEPRINT("mode", "%#o",
582		    dirnode->inode->st.st_mode & ALLPERMS, specnode->st_mode);
583		dirnode->inode->st.st_mode &= ~ALLPERMS;
584		dirnode->inode->st.st_mode |= (specnode->st_mode & ALLPERMS);
585	}
586		/* XXX: ignoring F_NLINK for now */
587	if (specnode->flags & F_SIZE) {
588		ASEPRINT("size", "%lld",
589		    (long long)dirnode->inode->st.st_size,
590		    (long long)specnode->st_size);
591		dirnode->inode->st.st_size = specnode->st_size;
592	}
593	if (specnode->flags & F_SLINK) {
594		assert(dirnode->symlink != NULL);
595		assert(specnode->slink != NULL);
596		ASEPRINT("symlink", "%s", dirnode->symlink, specnode->slink);
597		free(dirnode->symlink);
598		dirnode->symlink = estrdup(specnode->slink);
599	}
600	if (specnode->flags & F_TIME) {
601		ASEPRINT("time", "%ld",
602		    (long)dirnode->inode->st.st_mtime,
603		    (long)specnode->st_mtimespec.tv_sec);
604		dirnode->inode->st.st_mtime =		specnode->st_mtimespec.tv_sec;
605		dirnode->inode->st.st_atime =		specnode->st_mtimespec.tv_sec;
606		dirnode->inode->st.st_ctime =		start_time.tv_sec;
607#if HAVE_STRUCT_STAT_ST_MTIMENSEC
608		dirnode->inode->st.st_mtimensec =	specnode->st_mtimespec.tv_nsec;
609		dirnode->inode->st.st_atimensec =	specnode->st_mtimespec.tv_nsec;
610		dirnode->inode->st.st_ctimensec =	start_time.tv_nsec;
611#endif
612	}
613	if (specnode->flags & (F_UID | F_UNAME)) {
614		ASEPRINT("uid", "%d",
615		    dirnode->inode->st.st_uid, specnode->st_uid);
616		dirnode->inode->st.st_uid = specnode->st_uid;
617	}
618#if HAVE_STRUCT_STAT_ST_FLAGS
619	if (specnode->flags & F_FLAGS) {
620		ASEPRINT("flags", "%#lX",
621		    (unsigned long)dirnode->inode->st.st_flags,
622		    (unsigned long)specnode->st_flags);
623		dirnode->inode->st.st_flags = specnode->st_flags;
624	}
625#endif
626	if (specnode->flags & F_DEV) {
627		ASEPRINT("rdev", "%#llx",
628		    (unsigned long long)dirnode->inode->st.st_rdev,
629		    (unsigned long long)specnode->st_rdev);
630		dirnode->inode->st.st_rdev = specnode->st_rdev;
631	}
632#undef ASEPRINT
633
634	dirnode->flags |= FSNODE_F_HASSPEC;
635}
636
637
638/*
639 * dump_fsnodes --
640 *	dump the fsnodes from `cur'
641 */
642void
643dump_fsnodes(fsnode *root)
644{
645	fsnode	*cur;
646	char	path[MAXPATHLEN + 1];
647
648	printf("dump_fsnodes: %s %p\n", root->path, root);
649	for (cur = root; cur != NULL; cur = cur->next) {
650		if (snprintf(path, sizeof(path), "%s/%s", cur->path,
651		    cur->name) >= (int)sizeof(path))
652			errx(EXIT_FAILURE, "Pathname too long.");
653
654		if (debug & DEBUG_DUMP_FSNODES_VERBOSE)
655			printf("cur=%8p parent=%8p first=%8p ",
656			    cur, cur->parent, cur->first);
657		printf("%7s: %s", inode_type(cur->type), path);
658		if (S_ISLNK(cur->type)) {
659			assert(cur->symlink != NULL);
660			printf(" -> %s", cur->symlink);
661		} else {
662			assert (cur->symlink == NULL);
663		}
664		if (cur->inode->nlink > 1)
665			printf(", nlinks=%d", cur->inode->nlink);
666		putchar('\n');
667
668		if (cur->child) {
669			assert (cur->type == S_IFDIR);
670			dump_fsnodes(cur->child);
671		}
672	}
673	printf("dump_fsnodes: finished %s/%s\n", root->path, root->name);
674}
675
676
677/*
678 * inode_type --
679 *	for a given inode type `mode', return a descriptive string.
680 *	for most cases, uses inotype() from mtree/misc.c
681 */
682const char *
683inode_type(mode_t mode)
684{
685
686	if (S_ISLNK(mode))
687		return ("symlink");	/* inotype() returns "link"...  */
688	return (inotype(mode));
689}
690
691
692/*
693 * link_check --
694 *	return pointer to fsinode matching `entry's st_ino & st_dev if it exists,
695 *	otherwise add `entry' to table and return NULL
696 */
697/* This was borrowed from du.c and tweaked to keep an fsnode
698 * pointer instead. -- dbj@netbsd.org
699 */
700static fsinode *
701link_check(fsinode *entry)
702{
703	static struct entry {
704		fsinode *data;
705	} *htable;
706	static int htshift;  /* log(allocated size) */
707	static int htmask;   /* allocated size - 1 */
708	static int htused;   /* 2*number of insertions */
709	int h, h2;
710	uint64_t tmp;
711	/* this constant is (1<<64)/((1+sqrt(5))/2)
712	 * aka (word size)/(golden ratio)
713	 */
714	const uint64_t HTCONST = 11400714819323198485ULL;
715	const int HTBITS = 64;
716
717	/* Never store zero in hashtable */
718	assert(entry);
719
720	/* Extend hash table if necessary, keep load under 0.5 */
721	if (htused<<1 >= htmask) {
722		struct entry *ohtable;
723
724		if (!htable)
725			htshift = 10;   /* starting hashtable size */
726		else
727			htshift++;   /* exponential hashtable growth */
728
729		htmask  = (1 << htshift) - 1;
730		htused = 0;
731
732		ohtable = htable;
733		htable = ecalloc(htmask+1, sizeof(*htable));
734		/* populate newly allocated hashtable */
735		if (ohtable) {
736			int i;
737			for (i = 0; i <= htmask>>1; i++)
738				if (ohtable[i].data)
739					link_check(ohtable[i].data);
740			free(ohtable);
741		}
742	}
743
744	/* multiplicative hashing */
745	tmp = entry->st.st_dev;
746	tmp <<= HTBITS>>1;
747	tmp |=  entry->st.st_ino;
748	tmp *= HTCONST;
749	h  = tmp >> (HTBITS - htshift);
750	h2 = 1 | ( tmp >> (HTBITS - (htshift<<1) - 1)); /* must be odd */
751
752	/* open address hashtable search with double hash probing */
753	while (htable[h].data) {
754		if ((htable[h].data->st.st_ino == entry->st.st_ino) &&
755		    (htable[h].data->st.st_dev == entry->st.st_dev)) {
756			return htable[h].data;
757		}
758		h = (h + h2) & htmask;
759	}
760
761	/* Insert the current entry into hashtable */
762	htable[h].data = entry;
763	htused++;
764	return NULL;
765}
766