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