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