walk.c revision 1.38 
1/*	$NetBSD: walk.c,v 1.38 2024/04/24 14:23:37 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.38 2024/04/24 14:23:37 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 *vleft, const void *vright)
77{
78	const fsnode * const *left  = vleft;
79	const fsnode * const *right = vright;
80	const char *lname = (*left)->name, *rname = (*right)->name;
81
82	if (strcmp(lname, ".") == 0)
83		return -1;
84	if (strcmp(rname, ".") == 0)
85		return 1;
86	return strcmp(lname, rname);
87}
88
89static fsnode *
90fsnode_sort(fsnode *first, const char *root, const char *dir)
91{
92	fsnode **list, **listptr;
93	size_t num = 0;
94
95	for (fsnode *tmp = first; tmp; tmp = tmp->next, num++) {
96		num++;
97		if (debug & DEBUG_DUMP_FSNODES_VERBOSE)
98			printf("%s: pre sort: %s %s %s\n",
99			    __func__, root, dir, tmp->name);
100	}
101
102	list = listptr = ecalloc(num, sizeof(*list));
103	for (fsnode *tmp = first; tmp; tmp = tmp->next)
104		*listptr++ = tmp;
105
106	qsort (list, num, sizeof(*list), fsnode_cmp);
107
108	for (size_t i = 0; i < num - 1; ++i)
109		list[i]->next = list[i + 1];
110	list[num - 1]->next = NULL;
111	first = list[0];
112	assert(strcmp(first->name, ".") == 0);
113	free(list);
114	if (debug & DEBUG_DUMP_FSNODES_VERBOSE)
115		for (fsnode *tmp = first; tmp; tmp = tmp->next)
116			printf("%s: post sort: %s %s %s\n",
117			    __func__, root, dir, tmp->name);
118
119	return first;
120}
121
122/*
123 * walk_dir --
124 *	build a tree of fsnodes from `root' and `dir', with a parent
125 *	fsnode of `parent' (which may be NULL for the root of the tree).
126 *	append the tree to a fsnode of `join' if it is not NULL.
127 *	each "level" is a directory, with the "." entry guaranteed to be
128 *	at the start of the list, and without ".." entries.
129 */
130fsnode *
131walk_dir(const char *root, const char *dir, fsnode *parent, fsnode *join,
132    int replace, int follow)
133{
134	fsnode		*first, *cur, *prev, *last;
135	DIR		*dirp;
136	struct dirent	*dent;
137	char		path[MAXPATHLEN + 1];
138	struct stat	stbuf;
139	char		*name, *rp;
140	int		dot, len;
141
142	assert(root != NULL);
143	assert(dir != NULL);
144
145	len = snprintf(path, sizeof(path), "%s/%s", root, dir);
146	if ((size_t)len >= sizeof(path))
147		errx(EXIT_FAILURE, "Pathname too long.");
148	if (debug & DEBUG_WALK_DIR)
149		printf("%s: %s %p\n", __func__, path, parent);
150	if ((dirp = opendir(path)) == NULL)
151		err(EXIT_FAILURE, "Can't opendir `%s'", path);
152	rp = path + strlen(root) + 1;
153	if (join != NULL) {
154		first = cur = join;
155		while (cur->next != NULL)
156			cur = cur->next;
157		prev = last = cur;
158	} else
159		last = first = prev = NULL;
160	while ((dent = readdir(dirp)) != NULL) {
161		name = dent->d_name;
162		dot = 0;
163		if (name[0] == '.')
164			switch (name[1]) {
165			case '\0':	/* "." */
166				if (join != NULL)
167					continue;
168				dot = 1;
169				break;
170			case '.':	/* ".." */
171				if (name[2] == '\0')
172					continue;
173				/* FALLTHROUGH */
174			default:
175				dot = 0;
176			}
177		if (debug & DEBUG_WALK_DIR_NODE)
178			printf("%s: scanning %s/%s/%s\n",
179			    __func__, root, dir, name);
180		if (snprintf(path + len, sizeof(path) - len, "/%s", name) >=
181		    (int)sizeof(path) - len)
182			errx(EXIT_FAILURE, "Pathname too long.");
183		if (follow) {
184			if (stat(path, &stbuf) == -1)
185				err(EXIT_FAILURE, "Can't stat `%s'", path);
186		} else {
187			if (lstat(path, &stbuf) == -1)
188				err(EXIT_FAILURE, "Can't lstat `%s'", path);
189			/*
190			 * Symlink permission bits vary between filesystems/OSs
191			 * (ie. 0755 on FFS/NetBSD, 0777 for ext[234]/Linux),
192			 * force them to 0755.
193			 */
194			if (S_ISLNK(stbuf.st_mode)) {
195				stbuf.st_mode &= ~(S_IRWXU | S_IRWXG | S_IRWXO);
196				stbuf.st_mode |= S_IRWXU
197				    | S_IRGRP | S_IXGRP
198				    | S_IROTH | S_IXOTH;
199			}
200		}
201#ifdef S_ISSOCK
202		if (S_ISSOCK(stbuf.st_mode & S_IFMT)) {
203			if (debug & DEBUG_WALK_DIR_NODE)
204				printf("%s: skipping socket %s\n", __func__, path);
205			continue;
206		}
207#endif
208
209		if (join != NULL) {
210			cur = join->next;
211			for (;;) {
212				if (cur == NULL || strcmp(cur->name, name) == 0)
213					break;
214				if (cur == last) {
215					cur = NULL;
216					break;
217				}
218				cur = cur->next;
219			}
220			if (cur != NULL) {
221				if (S_ISDIR(cur->type) &&
222				    S_ISDIR(stbuf.st_mode)) {
223					if (debug & DEBUG_WALK_DIR_NODE)
224						printf("%s: merging %s with %p\n",
225						    __func__, path, cur->child);
226					cur->child = walk_dir(root, rp, cur,
227					    cur->child, replace, follow);
228					continue;
229				}
230				if (!replace)
231					errx(EXIT_FAILURE,
232					    "Can't merge %s `%s' with "
233					    "existing %s",
234					    inode_type(stbuf.st_mode), path,
235					    inode_type(cur->type));
236				else {
237					if (debug & DEBUG_WALK_DIR_NODE)
238						printf("%s: replacing %s %s\n",
239						    __func__,
240						    inode_type(stbuf.st_mode),
241						    path);
242					if (cur == join->next)
243						join->next = cur->next;
244					else {
245						fsnode *p;
246						for (p = join->next;
247						    p->next != cur; p = p->next)
248							continue;
249						p->next = cur->next;
250					}
251					free(cur);
252				}
253			}
254		}
255
256		cur = create_fsnode(root, dir, name, &stbuf);
257		cur->parent = parent;
258		if (dot) {
259				/* ensure "." is at the start of the list */
260			cur->next = first;
261			first = cur;
262			if (! prev)
263				prev = cur;
264			cur->first = first;
265		} else {			/* not "." */
266			if (prev)
267				prev->next = cur;
268			prev = cur;
269			if (!first)
270				first = cur;
271			cur->first = first;
272			if (S_ISDIR(cur->type)) {
273				cur->child = walk_dir(root, rp, cur, NULL,
274				    replace, follow);
275				continue;
276			}
277		}
278		if (stbuf.st_nlink > 1) {
279			fsinode	*curino;
280
281			curino = link_check(cur->inode);
282			if (curino != NULL) {
283				free(cur->inode);
284				cur->inode = curino;
285				cur->inode->nlink++;
286				if (debug & DEBUG_WALK_DIR_LINKCHECK)
287					printf("%s: link check found [%ju, %ju]\n",
288					    __func__,
289					    (uintmax_t)curino->st.st_dev,
290					    (uintmax_t)curino->st.st_ino);
291			}
292		}
293		if (S_ISLNK(cur->type)) {
294			char	slink[PATH_MAX+1];
295			ssize_t	llen;
296
297			llen = readlink(path, slink, sizeof(slink) - 1);
298			if (llen == -1)
299				err(EXIT_FAILURE, "Readlink `%s'", path);
300			slink[llen] = '\0';
301			cur->symlink = estrdup(slink);
302		}
303	}
304	assert(first != NULL);
305	if (join == NULL)
306		for (cur = first->next; cur != NULL; cur = cur->next)
307			cur->first = first;
308	if (closedir(dirp) == -1)
309		err(EXIT_FAILURE, "Can't closedir `%s/%s'", root, dir);
310
311	return fsnode_sort(first, root, dir);
312}
313
314static fsnode *
315create_fsnode(const char *root, const char *path, const char *name,
316    struct stat *stbuf)
317{
318	fsnode *cur;
319
320	cur = ecalloc(1, sizeof(*cur));
321	cur->path = estrdup(path);
322	cur->name = estrdup(name);
323	cur->inode = ecalloc(1, sizeof(*cur->inode));
324	cur->root = root;
325	cur->type = stbuf->st_mode & S_IFMT;
326	cur->inode->nlink = 1;
327	cur->inode->st = *stbuf;
328	if (stampst.st_ino) {
329		cur->inode->st.st_atime = stampst.st_atime;
330		cur->inode->st.st_mtime = stampst.st_mtime;
331		cur->inode->st.st_ctime = stampst.st_ctime;
332#if HAVE_STRUCT_STAT_ST_MTIMENSEC
333		cur->inode->st.st_atimensec = stampst.st_atimensec;
334		cur->inode->st.st_mtimensec = stampst.st_mtimensec;
335		cur->inode->st.st_ctimensec = stampst.st_ctimensec;
336#endif
337#if HAVE_STRUCT_STAT_BIRTHTIME
338		cur->inode->st.st_birthtime = stampst.st_birthtime;
339		cur->inode->st.st_birthtimensec = stampst.st_birthtimensec;
340#endif
341	}
342	return (cur);
343}
344
345/*
346 * free_fsnodes --
347 *	Removes node from tree and frees it and all of
348 *   its descendents.
349 */
350void
351free_fsnodes(fsnode *node)
352{
353	fsnode	*cur, *next;
354
355	assert(node != NULL);
356
357	/* for ".", start with actual parent node */
358	if (node->first == node) {
359		assert(node->name[0] == '.' && node->name[1] == '\0');
360		if (node->parent) {
361			assert(node->parent->child == node);
362			node = node->parent;
363		}
364	}
365
366	/* Find ourselves in our sibling list and unlink */
367	if (node->first != node) {
368		for (cur = node->first; cur->next; cur = cur->next) {
369			if (cur->next == node) {
370				cur->next = node->next;
371				node->next = NULL;
372				break;
373			}
374		}
375	}
376
377	for (cur = node; cur != NULL; cur = next) {
378		next = cur->next;
379		if (cur->child) {
380			cur->child->parent = NULL;
381			free_fsnodes(cur->child);
382		}
383		if (cur->inode->nlink-- == 1)
384			free(cur->inode);
385		if (cur->symlink)
386			free(cur->symlink);
387		free(cur->path);
388		free(cur->name);
389		free(cur);
390	}
391}
392
393/*
394 * apply_specfile --
395 *	read in the mtree(8) specfile, and apply it to the tree
396 *	at dir,parent. parameters in parent on equivalent types
397 *	will be changed to those found in specfile, and missing
398 *	entries will be added.
399 */
400void
401apply_specfile(const char *specfile, const char *dir, fsnode *parent, int speconly)
402{
403	struct timeval	 start;
404	FILE	*fp;
405	NODE	*root;
406
407	assert(specfile != NULL);
408	assert(parent != NULL);
409
410	if (debug & DEBUG_APPLY_SPECFILE)
411		printf("%s: %s, %s %p\n", __func__, specfile, dir, parent);
412
413				/* read in the specfile */
414	if ((fp = fopen(specfile, "r")) == NULL)
415		err(EXIT_FAILURE, "Can't open `%s'", specfile);
416	TIMER_START(start);
417	root = spec(fp);
418	TIMER_RESULTS(start, "spec");
419	if (fclose(fp) == EOF)
420		err(EXIT_FAILURE, "Can't close `%s'", specfile);
421
422				/* perform some sanity checks */
423	if (root == NULL)
424		errx(EXIT_FAILURE,
425		    "Specfile `%s' did not contain a tree", specfile);
426	assert(strcmp(root->name, ".") == 0);
427	assert(root->type == F_DIR);
428
429				/* merge in the changes */
430	apply_specdir(dir, root, parent, speconly);
431
432	free_nodes(root);
433}
434
435static void
436apply_specdir(const char *dir, NODE *specnode, fsnode *dirnode, int speconly)
437{
438	char	 path[MAXPATHLEN + 1];
439	NODE	*curnode;
440	fsnode	*curfsnode;
441
442	assert(specnode != NULL);
443	assert(dirnode != NULL);
444
445	if (debug & DEBUG_APPLY_SPECFILE)
446		printf("%s: %s %p %p\n", __func__, dir, specnode, dirnode);
447
448	if (specnode->type != F_DIR)
449		errx(EXIT_FAILURE, "Specfile node `%s/%s' is not a directory",
450		    dir, specnode->name);
451	if (dirnode->type != S_IFDIR)
452		errx(EXIT_FAILURE, "Directory node `%s/%s' is not a directory",
453		    dir, dirnode->name);
454
455	apply_specentry(dir, specnode, dirnode);
456
457	/* Remove any filesystem nodes not found in specfile */
458	/* XXX inefficient.  This is O^2 in each dir and it would
459	 * have been better never to have walked this part of the tree
460	 * to begin with
461	 */
462	if (speconly) {
463		fsnode *next;
464		assert(dirnode->name[0] == '.' && dirnode->name[1] == '\0');
465		for (curfsnode = dirnode->next; curfsnode != NULL; curfsnode = next) {
466			next = curfsnode->next;
467			for (curnode = specnode->child; curnode != NULL;
468			     curnode = curnode->next) {
469				if (strcmp(curnode->name, curfsnode->name) == 0)
470					break;
471			}
472			if (curnode == NULL) {
473				if (debug & DEBUG_APPLY_SPECONLY) {
474					printf("%s: trimming %s/%s %p\n",
475					    __func__, dir, curfsnode->name,
476					    curfsnode);
477				}
478				free_fsnodes(curfsnode);
479			}
480		}
481	}
482
483			/* now walk specnode->child matching up with dirnode */
484	for (curnode = specnode->child; curnode != NULL;
485	    curnode = curnode->next) {
486		if (debug & DEBUG_APPLY_SPECENTRY)
487			printf("%s:  spec %s\n", __func__, curnode->name);
488		for (curfsnode = dirnode->next; curfsnode != NULL;
489		    curfsnode = curfsnode->next) {
490#if 0	/* too verbose for now */
491			if (debug & DEBUG_APPLY_SPECENTRY)
492				printf("%s: dirent %s\n", __func__,
493				    curfsnode->name);
494#endif
495			if (strcmp(curnode->name, curfsnode->name) == 0)
496				break;
497		}
498		if ((size_t)snprintf(path, sizeof(path), "%s/%s",
499		    dir, curnode->name) >= sizeof(path))
500			errx(EXIT_FAILURE, "Pathname too long.");
501		if (curfsnode == NULL) {	/* need new entry */
502			struct stat	stbuf;
503
504					    /*
505					     * don't add optional spec entries
506					     * that lack an existing fs entry
507					     */
508			if ((curnode->flags & F_OPT) &&
509			    lstat(path, &stbuf) == -1)
510					continue;
511
512					/* check that enough info is provided */
513#define NODETEST(t, m)							\
514			if (!(t))					\
515				errx(EXIT_FAILURE,			\
516				    "`%s': %s not provided", path, m)
517			NODETEST(curnode->flags & F_TYPE, "type");
518			NODETEST(curnode->flags & F_MODE, "mode");
519				/* XXX: require F_TIME ? */
520			NODETEST(curnode->flags & F_GID ||
521			    curnode->flags & F_GNAME, "group");
522			NODETEST(curnode->flags & F_UID ||
523			    curnode->flags & F_UNAME, "user");
524			if (curnode->type == F_BLOCK || curnode->type == F_CHAR)
525				NODETEST(curnode->flags & F_DEV,
526				    "device number");
527#undef NODETEST
528
529			if (debug & DEBUG_APPLY_SPECFILE)
530				printf("%s: adding %s\n", __func__, curnode->name);
531					/* build minimal fsnode */
532			memset(&stbuf, 0, sizeof(stbuf));
533			stbuf.st_mode = nodetoino(curnode->type);
534			stbuf.st_nlink = 1;
535			stbuf.st_mtime = stbuf.st_atime =
536			    stbuf.st_ctime = start_time.tv_sec;
537#if HAVE_STRUCT_STAT_ST_MTIMENSEC
538			stbuf.st_mtimensec = stbuf.st_atimensec =
539			    stbuf.st_ctimensec = start_time.tv_nsec;
540#endif
541			curfsnode = create_fsnode(".", ".", curnode->name,
542			    &stbuf);
543			curfsnode->parent = dirnode->parent;
544			curfsnode->first = dirnode;
545			curfsnode->next = dirnode->next;
546			dirnode->next = curfsnode;
547			if (curfsnode->type == S_IFDIR) {
548					/* for dirs, make "." entry as well */
549				curfsnode->child = create_fsnode(".", ".", ".",
550				    &stbuf);
551				curfsnode->child->parent = curfsnode;
552				curfsnode->child->first = curfsnode->child;
553			}
554			if (curfsnode->type == S_IFLNK) {
555				assert(curnode->slink != NULL);
556					/* for symlinks, copy the target */
557				curfsnode->symlink = estrdup(curnode->slink);
558			}
559		}
560		apply_specentry(dir, curnode, curfsnode);
561		if (curnode->type == F_DIR) {
562			if (curfsnode->type != S_IFDIR)
563				errx(EXIT_FAILURE,
564				    "`%s' is not a directory", path);
565			assert (curfsnode->child != NULL);
566			apply_specdir(path, curnode, curfsnode->child, speconly);
567		}
568	}
569}
570
571static void
572apply_specentry(const char *dir, NODE *specnode, fsnode *dirnode)
573{
574
575	assert(specnode != NULL);
576	assert(dirnode != NULL);
577
578	if (nodetoino(specnode->type) != dirnode->type)
579		errx(EXIT_FAILURE,
580		    "`%s/%s' type mismatch: specfile %s, tree %s",
581		    dir, specnode->name, inode_type(nodetoino(specnode->type)),
582		    inode_type(dirnode->type));
583
584	if (debug & DEBUG_APPLY_SPECENTRY)
585		printf("%s: %s/%s\n", dir, __func__, dirnode->name);
586
587#define ASEPRINT(t, b, o, n) \
588		if (debug & DEBUG_APPLY_SPECENTRY) \
589			printf("\t\t\tchanging %s from " b " to " b "\n", \
590			    t, o, n)
591
592	if (specnode->flags & (F_GID | F_GNAME)) {
593		ASEPRINT("gid", "%d",
594		    dirnode->inode->st.st_gid, specnode->st_gid);
595		dirnode->inode->st.st_gid = specnode->st_gid;
596	}
597	if (specnode->flags & F_MODE) {
598		ASEPRINT("mode", "%#o",
599		    dirnode->inode->st.st_mode & ALLPERMS, specnode->st_mode);
600		dirnode->inode->st.st_mode &= ~ALLPERMS;
601		dirnode->inode->st.st_mode |= (specnode->st_mode & ALLPERMS);
602	}
603		/* XXX: ignoring F_NLINK for now */
604	if (specnode->flags & F_SIZE) {
605		ASEPRINT("size", "%jd",
606		    (intmax_t)dirnode->inode->st.st_size,
607		    (intmax_t)specnode->st_size);
608		dirnode->inode->st.st_size = specnode->st_size;
609	}
610	if (specnode->flags & F_SLINK) {
611		assert(dirnode->symlink != NULL);
612		assert(specnode->slink != NULL);
613		ASEPRINT("symlink", "%s", dirnode->symlink, specnode->slink);
614		free(dirnode->symlink);
615		dirnode->symlink = estrdup(specnode->slink);
616	}
617	if (specnode->flags & F_TIME) {
618		ASEPRINT("time", "%ld",
619		    (long)dirnode->inode->st.st_mtime,
620		    (long)specnode->st_mtimespec.tv_sec);
621		dirnode->inode->st.st_mtime =		specnode->st_mtimespec.tv_sec;
622		dirnode->inode->st.st_atime =		specnode->st_mtimespec.tv_sec;
623		dirnode->inode->st.st_ctime =		start_time.tv_sec;
624#if HAVE_STRUCT_STAT_ST_MTIMENSEC
625		dirnode->inode->st.st_mtimensec =	specnode->st_mtimespec.tv_nsec;
626		dirnode->inode->st.st_atimensec =	specnode->st_mtimespec.tv_nsec;
627		dirnode->inode->st.st_ctimensec =	start_time.tv_nsec;
628#endif
629	}
630	if (specnode->flags & (F_UID | F_UNAME)) {
631		ASEPRINT("uid", "%d",
632		    dirnode->inode->st.st_uid, specnode->st_uid);
633		dirnode->inode->st.st_uid = specnode->st_uid;
634	}
635#if HAVE_STRUCT_STAT_ST_FLAGS
636	if (specnode->flags & F_FLAGS) {
637		ASEPRINT("flags", "%#lX",
638		    (unsigned long)dirnode->inode->st.st_flags,
639		    (unsigned long)specnode->st_flags);
640		dirnode->inode->st.st_flags = (unsigned int)specnode->st_flags;
641	}
642#endif
643	if (specnode->flags & F_DEV) {
644		ASEPRINT("rdev", "%#jx",
645		    (uintmax_t)dirnode->inode->st.st_rdev,
646		    (uintmax_t)specnode->st_rdev);
647		dirnode->inode->st.st_rdev = specnode->st_rdev;
648	}
649#undef ASEPRINT
650
651	dirnode->flags |= FSNODE_F_HASSPEC;
652}
653
654
655/*
656 * dump_fsnodes --
657 *	dump the fsnodes from `cur'
658 */
659void
660dump_fsnodes(fsnode *root)
661{
662	fsnode	*cur;
663	char	path[MAXPATHLEN + 1];
664
665	printf("%s: %s %p\n", __func__, root->path, root);
666	for (cur = root; cur != NULL; cur = cur->next) {
667		if (snprintf(path, sizeof(path), "%s/%s", cur->path,
668		    cur->name) >= (int)sizeof(path))
669			errx(EXIT_FAILURE, "Pathname too long.");
670
671		if (debug & DEBUG_DUMP_FSNODES_VERBOSE)
672			printf("%s: cur=%8p parent=%8p first=%8p ", __func__,
673			    cur, cur->parent, cur->first);
674		printf("%7s: %s", inode_type(cur->type), path);
675		if (S_ISLNK(cur->type)) {
676			assert(cur->symlink != NULL);
677			printf(" -> %s", cur->symlink);
678		} else {
679			assert (cur->symlink == NULL);
680		}
681		if (cur->inode->nlink > 1)
682			printf(", nlinks=%d", cur->inode->nlink);
683		putchar('\n');
684
685		if (cur->child) {
686			assert (cur->type == S_IFDIR);
687			dump_fsnodes(cur->child);
688		}
689	}
690	printf("%s: finished %s/%s\n", __func__, root->path, root->name);
691}
692
693
694/*
695 * inode_type --
696 *	for a given inode type `mode', return a descriptive string.
697 *	for most cases, uses inotype() from mtree/misc.c
698 */
699const char *
700inode_type(mode_t mode)
701{
702
703	if (S_ISLNK(mode))
704		return ("symlink");	/* inotype() returns "link"...  */
705	return (inotype(mode));
706}
707
708
709/*
710 * link_check --
711 *	return pointer to fsinode matching `entry's st_ino & st_dev if it exists,
712 *	otherwise add `entry' to table and return NULL
713 */
714/* This was borrowed from du.c and tweaked to keep an fsnode
715 * pointer instead. -- dbj@netbsd.org
716 */
717static fsinode *
718link_check(fsinode *entry)
719{
720	static struct entry {
721		fsinode *data;
722	} *htable;
723	static size_t htshift;  /* log(allocated size) */
724	static size_t htmask;   /* allocated size - 1 */
725	static size_t htused;   /* 2*number of insertions */
726	size_t h, h2;
727	uint64_t tmp;
728	/* this constant is (1<<64)/((1+sqrt(5))/2)
729	 * aka (word size)/(golden ratio)
730	 */
731	const uint64_t HTCONST = 11400714819323198485ULL;
732	const size_t HTBITS = 64;
733
734	/* Never store zero in hashtable */
735	assert(entry);
736
737	/* Extend hash table if necessary, keep load under 0.5 */
738	if (htused<<1 >= htmask) {
739		struct entry *ohtable;
740
741		if (!htable)
742			htshift = 10;   /* starting hashtable size */
743		else
744			htshift++;   /* exponential hashtable growth */
745
746		htmask  = (1 << htshift) - 1;
747		htused = 0;
748
749		ohtable = htable;
750		htable = ecalloc(htmask+1, sizeof(*htable));
751		/* populate newly allocated hashtable */
752		if (ohtable) {
753			for (size_t i = 0; i <= htmask>>1; i++)
754				if (ohtable[i].data)
755					link_check(ohtable[i].data);
756			free(ohtable);
757		}
758	}
759
760	/* multiplicative hashing */
761	tmp = entry->st.st_dev;
762	tmp <<= HTBITS>>1;
763	tmp |=  entry->st.st_ino;
764	tmp *= HTCONST;
765	h  = tmp >> (HTBITS - htshift);
766	h2 = 1 | ( tmp >> (HTBITS - (htshift<<1) - 1)); /* must be odd */
767
768	/* open address hashtable search with double hash probing */
769	while (htable[h].data) {
770		if ((htable[h].data->st.st_ino == entry->st.st_ino) &&
771		    (htable[h].data->st.st_dev == entry->st.st_dev)) {
772			return htable[h].data;
773		}
774		h = (h + h2) & htmask;
775	}
776
777	/* Insert the current entry into hashtable */
778	htable[h].data = entry;
779	htused++;
780	return NULL;
781}
782