GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: usr.sbin/makefs/walk.c Lines: 0 156 0.0 %
Date: 2017-11-13 Branches: 0 121 0.0 %

Line Branch Exec Source
1
/*	$OpenBSD: walk.c,v 1.9 2016/12/17 16:12:15 krw Exp $	*/
2
/*	$NetBSD: walk.c,v 1.29 2015/11/25 00:48:49 christos Exp $	*/
3
4
/*
5
 * Copyright (c) 2001 Wasabi Systems, Inc.
6
 * All rights reserved.
7
 *
8
 * Written by Luke Mewburn for Wasabi Systems, Inc.
9
 *
10
 * Redistribution and use in source and binary forms, with or without
11
 * modification, are permitted provided that the following conditions
12
 * are met:
13
 * 1. Redistributions of source code must retain the above copyright
14
 *    notice, this list of conditions and the following disclaimer.
15
 * 2. Redistributions in binary form must reproduce the above copyright
16
 *    notice, this list of conditions and the following disclaimer in the
17
 *    documentation and/or other materials provided with the distribution.
18
 * 3. All advertising materials mentioning features or use of this software
19
 *    must display the following acknowledgement:
20
 *      This product includes software developed for the NetBSD Project by
21
 *      Wasabi Systems, Inc.
22
 * 4. The name of Wasabi Systems, Inc. may not be used to endorse
23
 *    or promote products derived from this software without specific prior
24
 *    written permission.
25
 *
26
 * THIS SOFTWARE IS PROVIDED BY WASABI SYSTEMS, INC. ``AS IS'' AND
27
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
28
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
29
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL WASABI SYSTEMS, INC
30
 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
31
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
32
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
33
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
34
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
35
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
36
 * POSSIBILITY OF SUCH DAMAGE.
37
 */
38
39
#include <sys/param.h>
40
#include <sys/stat.h>
41
42
#include <assert.h>
43
#include <stdio.h>
44
#include <dirent.h>
45
#include <stdlib.h>
46
#include <string.h>
47
#include <unistd.h>
48
49
#include "makefs.h"
50
51
static	fsnode	*create_fsnode(const char *, const char *, const char *,
52
			       struct stat *);
53
static	fsinode	*link_check(fsinode *);
54
55
56
/*
57
 * walk_dir --
58
 *	build a tree of fsnodes from `root' and `dir', with a parent
59
 *	fsnode of `parent' (which may be NULL for the root of the tree).
60
 *	append the tree to a fsnode of `join' if it is not NULL.
61
 *	each "level" is a directory, with the "." entry guaranteed to be
62
 *	at the start of the list, and without ".." entries.
63
 */
64
fsnode *
65
walk_dir(const char *root, const char *dir, fsnode *parent, fsnode *join)
66
{
67
	fsnode		*first, *cur, *prev, *last;
68
	DIR		*dirp;
69
	struct dirent	*dent;
70
	char		path[MAXPATHLEN + 1];
71
	struct stat	stbuf;
72
	char		*name, *rp;
73
	int		dot, len;
74
75
	assert(root != NULL);
76
	assert(dir != NULL);
77
78
	len = snprintf(path, sizeof(path), "%s/%s", root, dir);
79
	if (len >= (int)sizeof(path))
80
		errx(1, "Pathname too long.");
81
	if ((dirp = opendir(path)) == NULL)
82
		err(1, "Can't opendir `%s'", path);
83
	rp = path + strlen(root) + 1;
84
	if (join != NULL) {
85
		first = cur = join;
86
		while (cur->next != NULL)
87
			cur = cur->next;
88
		prev = last = cur;
89
	} else
90
		last = first = prev = NULL;
91
	while ((dent = readdir(dirp)) != NULL) {
92
		name = dent->d_name;
93
		dot = 0;
94
		if (name[0] == '.')
95
			switch (name[1]) {
96
			case '\0':	/* "." */
97
				if (join != NULL)
98
					continue;
99
				dot = 1;
100
				break;
101
			case '.':	/* ".." */
102
				if (name[2] == '\0')
103
					continue;
104
				/* FALLTHROUGH */
105
			default:
106
				dot = 0;
107
			}
108
		if (snprintf(path + len, sizeof(path) - len, "/%s", name) >=
109
		    (int)sizeof(path) - len)
110
			errx(1, "Pathname too long.");
111
		if (lstat(path, &stbuf) == -1)
112
			err(1, "Can't lstat `%s'", path);
113
		if (S_ISSOCK(stbuf.st_mode & S_IFMT))
114
			continue;
115
116
		if (join != NULL) {
117
			cur = join->next;
118
			for (;;) {
119
				if (cur == NULL || strcmp(cur->name, name) == 0)
120
					break;
121
				if (cur == last) {
122
					cur = NULL;
123
					break;
124
				}
125
				cur = cur->next;
126
			}
127
			if (cur != NULL) {
128
				if (S_ISDIR(cur->type) &&
129
				    S_ISDIR(stbuf.st_mode)) {
130
					cur->child = walk_dir(root, rp, cur,
131
					    cur->child);
132
					continue;
133
				}
134
				errx(1, "Can't merge %s `%s' with "
135
				    "existing %s",
136
				    inode_type(stbuf.st_mode), path,
137
				    inode_type(cur->type));
138
			}
139
		}
140
141
		cur = create_fsnode(root, dir, name, &stbuf);
142
		cur->parent = parent;
143
		if (dot) {
144
				/* ensure "." is at the start of the list */
145
			cur->next = first;
146
			first = cur;
147
			if (! prev)
148
				prev = cur;
149
			cur->first = first;
150
		} else {			/* not "." */
151
			if (prev)
152
				prev->next = cur;
153
			prev = cur;
154
			if (!first)
155
				first = cur;
156
			cur->first = first;
157
			if (S_ISDIR(cur->type)) {
158
				cur->child = walk_dir(root, rp, cur, NULL);
159
				continue;
160
			}
161
		}
162
		if (stbuf.st_nlink > 1) {
163
			fsinode	*curino;
164
165
			curino = link_check(cur->inode);
166
			if (curino != NULL) {
167
				free(cur->inode);
168
				cur->inode = curino;
169
				cur->inode->nlink++;
170
			}
171
		}
172
		if (S_ISLNK(cur->type)) {
173
			char	slink[PATH_MAX+1];
174
			int	llen;
175
176
			llen = readlink(path, slink, sizeof(slink) - 1);
177
			if (llen == -1)
178
				err(1, "Readlink `%s'", path);
179
			slink[llen] = '\0';
180
			cur->symlink = estrdup(slink);
181
		}
182
	}
183
	assert(first != NULL);
184
	if (join == NULL)
185
		for (cur = first->next; cur != NULL; cur = cur->next)
186
			cur->first = first;
187
	if (closedir(dirp) == -1)
188
		err(1, "Can't closedir `%s/%s'", root, dir);
189
	return (first);
190
}
191
192
static fsnode *
193
create_fsnode(const char *root, const char *path, const char *name,
194
    struct stat *stbuf)
195
{
196
	fsnode *cur;
197
198
	cur = ecalloc(1, sizeof(*cur));
199
	cur->path = estrdup(path);
200
	cur->name = estrdup(name);
201
	cur->inode = ecalloc(1, sizeof(*cur->inode));
202
	cur->root = root;
203
	cur->type = stbuf->st_mode & S_IFMT;
204
	cur->inode->nlink = 1;
205
	cur->inode->st = *stbuf;
206
	if (Tflag) {
207
		cur->inode->st.st_atime = stampts;
208
		cur->inode->st.st_mtime = stampts;
209
		cur->inode->st.st_ctime = stampts;
210
		cur->inode->st.st_atimensec = 0;
211
		cur->inode->st.st_mtimensec = 0;
212
		cur->inode->st.st_ctimensec = 0;
213
	}
214
	return (cur);
215
}
216
217
/*
218
 * free_fsnodes --
219
 *	Removes node from tree and frees it and all of
220
 *   its decendents.
221
 */
222
void
223
free_fsnodes(fsnode *node)
224
{
225
	fsnode	*cur, *next;
226
227
	assert(node != NULL);
228
229
	/* for ".", start with actual parent node */
230
	if (node->first == node) {
231
		assert(node->name[0] == '.' && node->name[1] == '\0');
232
		if (node->parent) {
233
			assert(node->parent->child == node);
234
			node = node->parent;
235
		}
236
	}
237
238
	/* Find ourselves in our sibling list and unlink */
239
	if (node->first != node) {
240
		for (cur = node->first; cur->next; cur = cur->next) {
241
			if (cur->next == node) {
242
				cur->next = node->next;
243
				node->next = NULL;
244
				break;
245
			}
246
		}
247
	}
248
249
	for (cur = node; cur != NULL; cur = next) {
250
		next = cur->next;
251
		if (cur->child) {
252
			cur->child->parent = NULL;
253
			free_fsnodes(cur->child);
254
		}
255
		if (cur->inode->nlink-- == 1)
256
			free(cur->inode);
257
		if (cur->symlink)
258
			free(cur->symlink);
259
		free(cur->path);
260
		free(cur->name);
261
		free(cur);
262
	}
263
}
264
265
266
/*
267
 * inode_type --
268
 *	for a given inode type `mode', return a descriptive string.
269
 *	for most cases, uses inotype() from mtree/misc.c
270
 */
271
const char *
272
inode_type(mode_t mode)
273
{
274
	switch (mode & S_IFMT) {
275
	case S_IFBLK:
276
		return ("block");
277
	case S_IFCHR:
278
		return ("char");
279
	case S_IFDIR:
280
		return ("dir");
281
	case S_IFIFO:
282
		return ("fifo");
283
	case S_IFREG:
284
		return ("file");
285
	case S_IFLNK:
286
		return ("symlink");
287
	case S_IFSOCK:
288
		return ("socket");
289
	default:
290
		return ("unknown");
291
	}
292
}
293
294
295
/*
296
 * link_check --
297
 *	return pointer to fsinode matching `entry's st_ino & st_dev if it exists,
298
 *	otherwise add `entry' to table and return NULL
299
 */
300
/* This was borrowed from du.c and tweaked to keep an fsnode
301
 * pointer instead. -- dbj@netbsd.org
302
 */
303
static fsinode *
304
link_check(fsinode *entry)
305
{
306
	static struct entry {
307
		fsinode *data;
308
	} *htable;
309
	static int htshift;  /* log(allocated size) */
310
	static int htmask;   /* allocated size - 1 */
311
	static int htused;   /* 2*number of insertions */
312
	int h, h2;
313
	uint64_t tmp;
314
	/* this constant is (1<<64)/((1+sqrt(5))/2)
315
	 * aka (word size)/(golden ratio)
316
	 */
317
	const uint64_t HTCONST = 11400714819323198485ULL;
318
	const int HTBITS = 64;
319
320
	/* Never store zero in hashtable */
321
	assert(entry);
322
323
	/* Extend hash table if necessary, keep load under 0.5 */
324
	if (htused<<1 >= htmask) {
325
		struct entry *ohtable;
326
327
		if (!htable)
328
			htshift = 10;   /* starting hashtable size */
329
		else
330
			htshift++;   /* exponential hashtable growth */
331
332
		htmask  = (1 << htshift) - 1;
333
		htused = 0;
334
335
		ohtable = htable;
336
		htable = ecalloc(htmask+1, sizeof(*htable));
337
		/* populate newly allocated hashtable */
338
		if (ohtable) {
339
			int i;
340
			for (i = 0; i <= htmask>>1; i++)
341
				if (ohtable[i].data)
342
					link_check(ohtable[i].data);
343
			free(ohtable);
344
		}
345
	}
346
347
	/* multiplicative hashing */
348
	tmp = entry->st.st_dev;
349
	tmp <<= HTBITS>>1;
350
	tmp |=  entry->st.st_ino;
351
	tmp *= HTCONST;
352
	h  = tmp >> (HTBITS - htshift);
353
	h2 = 1 | ( tmp >> (HTBITS - (htshift<<1) - 1)); /* must be odd */
354
355
	/* open address hashtable search with double hash probing */
356
	while (htable[h].data) {
357
		if ((htable[h].data->st.st_ino == entry->st.st_ino) &&
358
		    (htable[h].data->st.st_dev == entry->st.st_dev)) {
359
			return htable[h].data;
360
		}
361
		h = (h + h2) & htmask;
362
	}
363
364
	/* Insert the current entry into hashtable */
365
	htable[h].data = entry;
366
	htused++;
367
	return NULL;
368
}