Home | History | Annotate | Line # | Download | only in makefs
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 
     63 static	void	 apply_specdir(const char *, NODE *, fsnode *, int);
     64 static	void	 apply_specentry(const char *, NODE *, fsnode *);
     65 static	fsnode	*create_fsnode(const char *, const char *, const char *,
     66 			       struct stat *);
     67 static	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  */
     75 static int
     76 fsnode_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 
     89 static fsnode *
     90 fsnode_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  */
    130 fsnode *
    131 walk_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 
    314 static fsnode *
    315 create_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  */
    350 void
    351 free_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  */
    400 void
    401 apply_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 
    435 static void
    436 apply_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 
    571 static void
    572 apply_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  */
    659 void
    660 dump_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  */
    699 const char *
    700 inode_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 (at) netbsd.org
    716  */
    717 static fsinode *
    718 link_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