1 /* $OpenBSD: walk.c,v 1.12 2023/08/19 04:21:06 guenther 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/types.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 <limits.h>
47 #include <string.h>
48 #include <unistd.h>
49
50 #include "makefs.h"
51
52 static fsnode *create_fsnode(const char *, const char *, const char *,
53 struct stat *);
54 static fsinode *link_check(fsinode *);
55
56
57 /*
58 * walk_dir --
59 * build a tree of fsnodes from `root' and `dir', with a parent
60 * fsnode of `parent' (which may be NULL for the root of the tree).
61 * append the tree to a fsnode of `join' if it is not NULL.
62 * each "level" is a directory, with the "." entry guaranteed to be
63 * at the start of the list, and without ".." entries.
64 */
65 fsnode *
walk_dir(const char * root,const char * dir,fsnode * parent,fsnode * join)66 walk_dir(const char *root, const char *dir, fsnode *parent, fsnode *join)
67 {
68 fsnode *first, *cur, *prev, *last;
69 DIR *dirp;
70 struct dirent *dent;
71 char path[PATH_MAX+1];
72 struct stat stbuf;
73 char *name, *rp;
74 int dot, len;
75
76 assert(root != NULL);
77 assert(dir != NULL);
78
79 len = snprintf(path, sizeof(path), "%s/%s", root, dir);
80 if (len >= (int)sizeof(path))
81 errx(1, "Pathname too long.");
82 if ((dirp = opendir(path)) == NULL)
83 err(1, "Can't opendir `%s'", path);
84 rp = path + strlen(root) + 1;
85 if (join != NULL) {
86 first = cur = join;
87 while (cur->next != NULL)
88 cur = cur->next;
89 prev = last = cur;
90 } else
91 last = first = prev = NULL;
92 while ((dent = readdir(dirp)) != NULL) {
93 name = dent->d_name;
94 dot = 0;
95 if (name[0] == '.')
96 switch (name[1]) {
97 case '\0': /* "." */
98 if (join != NULL)
99 continue;
100 dot = 1;
101 break;
102 case '.': /* ".." */
103 if (name[2] == '\0')
104 continue;
105 /* FALLTHROUGH */
106 default:
107 dot = 0;
108 }
109 if (snprintf(path + len, sizeof(path) - len, "/%s", name) >=
110 (int)sizeof(path) - len)
111 errx(1, "Pathname too long.");
112 if (lstat(path, &stbuf) == -1)
113 err(1, "Can't lstat `%s'", path);
114 if (S_ISSOCK(stbuf.st_mode & S_IFMT))
115 continue;
116
117 if (join != NULL) {
118 cur = join->next;
119 for (;;) {
120 if (cur == NULL || strcmp(cur->name, name) == 0)
121 break;
122 if (cur == last) {
123 cur = NULL;
124 break;
125 }
126 cur = cur->next;
127 }
128 if (cur != NULL) {
129 if (S_ISDIR(cur->type) &&
130 S_ISDIR(stbuf.st_mode)) {
131 cur->child = walk_dir(root, rp, cur,
132 cur->child);
133 continue;
134 }
135 errx(1, "Can't merge %s `%s' with "
136 "existing %s",
137 inode_type(stbuf.st_mode), path,
138 inode_type(cur->type));
139 }
140 }
141
142 cur = create_fsnode(root, dir, name, &stbuf);
143 cur->parent = parent;
144 if (dot) {
145 /* ensure "." is at the start of the list */
146 cur->next = first;
147 first = cur;
148 if (! prev)
149 prev = cur;
150 cur->first = first;
151 } else { /* not "." */
152 if (prev)
153 prev->next = cur;
154 prev = cur;
155 if (!first)
156 first = cur;
157 cur->first = first;
158 if (S_ISDIR(cur->type)) {
159 cur->child = walk_dir(root, rp, cur, NULL);
160 continue;
161 }
162 }
163 if (stbuf.st_nlink > 1) {
164 fsinode *curino;
165
166 curino = link_check(cur->inode);
167 if (curino != NULL) {
168 free(cur->inode);
169 cur->inode = curino;
170 cur->inode->nlink++;
171 }
172 }
173 if (S_ISLNK(cur->type)) {
174 char slink[PATH_MAX+1];
175 int llen;
176
177 llen = readlink(path, slink, sizeof(slink) - 1);
178 if (llen == -1)
179 err(1, "Readlink `%s'", path);
180 slink[llen] = '\0';
181 cur->symlink = estrdup(slink);
182 }
183 }
184 assert(first != NULL);
185 if (join == NULL)
186 for (cur = first->next; cur != NULL; cur = cur->next)
187 cur->first = first;
188 if (closedir(dirp) == -1)
189 err(1, "Can't closedir `%s/%s'", root, dir);
190 return (first);
191 }
192
193 static fsnode *
create_fsnode(const char * root,const char * path,const char * name,struct stat * stbuf)194 create_fsnode(const char *root, const char *path, const char *name,
195 struct stat *stbuf)
196 {
197 fsnode *cur;
198
199 cur = ecalloc(1, sizeof(*cur));
200 cur->path = estrdup(path);
201 cur->name = estrdup(name);
202 cur->inode = ecalloc(1, sizeof(*cur->inode));
203 cur->root = root;
204 cur->type = stbuf->st_mode & S_IFMT;
205 cur->inode->nlink = 1;
206 cur->inode->st = *stbuf;
207 if (Tflag) {
208 cur->inode->st.st_atim.tv_sec = stampts;
209 cur->inode->st.st_atim.tv_nsec = 0;
210 cur->inode->st.st_mtim = cur->inode->st.st_ctim =
211 cur->inode->st.st_atim;
212 }
213 return (cur);
214 }
215
216 /*
217 * free_fsnodes --
218 * Removes node from tree and frees it and all of
219 * its descendants.
220 */
221 void
free_fsnodes(fsnode * node)222 free_fsnodes(fsnode *node)
223 {
224 fsnode *cur, *next;
225
226 assert(node != NULL);
227
228 /* for ".", start with actual parent node */
229 if (node->first == node) {
230 assert(node->name[0] == '.' && node->name[1] == '\0');
231 if (node->parent) {
232 assert(node->parent->child == node);
233 node = node->parent;
234 }
235 }
236
237 /* Find ourselves in our sibling list and unlink */
238 if (node->first != node) {
239 for (cur = node->first; cur->next; cur = cur->next) {
240 if (cur->next == node) {
241 cur->next = node->next;
242 node->next = NULL;
243 break;
244 }
245 }
246 }
247
248 for (cur = node; cur != NULL; cur = next) {
249 next = cur->next;
250 if (cur->child) {
251 cur->child->parent = NULL;
252 free_fsnodes(cur->child);
253 }
254 if (cur->inode->nlink-- == 1)
255 free(cur->inode);
256 if (cur->symlink)
257 free(cur->symlink);
258 free(cur->path);
259 free(cur->name);
260 free(cur);
261 }
262 }
263
264
265 /*
266 * inode_type --
267 * for a given inode type `mode', return a descriptive string.
268 * for most cases, uses inotype() from mtree/misc.c
269 */
270 const char *
inode_type(mode_t mode)271 inode_type(mode_t mode)
272 {
273 switch (mode & S_IFMT) {
274 case S_IFBLK:
275 return ("block");
276 case S_IFCHR:
277 return ("char");
278 case S_IFDIR:
279 return ("dir");
280 case S_IFIFO:
281 return ("fifo");
282 case S_IFREG:
283 return ("file");
284 case S_IFLNK:
285 return ("symlink");
286 case S_IFSOCK:
287 return ("socket");
288 default:
289 return ("unknown");
290 }
291 }
292
293
294 /*
295 * link_check --
296 * return pointer to fsinode matching `entry's st_ino & st_dev if it exists,
297 * otherwise add `entry' to table and return NULL
298 */
299 /* This was borrowed from du.c and tweaked to keep an fsnode
300 * pointer instead. -- dbj@netbsd.org
301 */
302 static fsinode *
link_check(fsinode * entry)303 link_check(fsinode *entry)
304 {
305 static struct entry {
306 fsinode *data;
307 } *htable;
308 static int htshift; /* log(allocated size) */
309 static int htmask; /* allocated size - 1 */
310 static int htused; /* 2*number of insertions */
311 int h, h2;
312 uint64_t tmp;
313 /* this constant is (1<<64)/((1+sqrt(5))/2)
314 * aka (word size)/(golden ratio)
315 */
316 const uint64_t HTCONST = 11400714819323198485ULL;
317 const int HTBITS = 64;
318
319 /* Never store zero in hashtable */
320 assert(entry);
321
322 /* Extend hash table if necessary, keep load under 0.5 */
323 if (htused<<1 >= htmask) {
324 struct entry *ohtable;
325
326 if (!htable)
327 htshift = 10; /* starting hashtable size */
328 else
329 htshift++; /* exponential hashtable growth */
330
331 htmask = (1 << htshift) - 1;
332 htused = 0;
333
334 ohtable = htable;
335 htable = ecalloc(htmask+1, sizeof(*htable));
336 /* populate newly allocated hashtable */
337 if (ohtable) {
338 int i;
339 for (i = 0; i <= htmask>>1; i++)
340 if (ohtable[i].data)
341 link_check(ohtable[i].data);
342 free(ohtable);
343 }
344 }
345
346 /* multiplicative hashing */
347 tmp = entry->st.st_dev;
348 tmp <<= HTBITS>>1;
349 tmp |= entry->st.st_ino;
350 tmp *= HTCONST;
351 h = tmp >> (HTBITS - htshift);
352 h2 = 1 | ( tmp >> (HTBITS - (htshift<<1) - 1)); /* must be odd */
353
354 /* open address hashtable search with double hash probing */
355 while (htable[h].data) {
356 if ((htable[h].data->st.st_ino == entry->st.st_ino) &&
357 (htable[h].data->st.st_dev == entry->st.st_dev)) {
358 return htable[h].data;
359 }
360 h = (h + h2) & htmask;
361 }
362
363 /* Insert the current entry into hashtable */
364 htable[h].data = entry;
365 htused++;
366 return NULL;
367 }
368