Deleted Added
sdiff udiff text old ( 186335 ) new ( 214921 )
full compact
walk.c (186335) walk.c (214921)
1/* $NetBSD: walk.c,v 1.17 2004/06/20 22:20:18 jmc Exp $ */
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

--- 20 unchanged lines hidden (view full) ---

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
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

--- 20 unchanged lines hidden (view full) ---

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 * The function link_check() was inspired from NetBSD's usr.bin/du/du.c,
40 * which has the following copyright notice:
41 *
42 *
43 * Copyright (c) 1989, 1993, 1994
44 * The Regents of the University of California. All rights reserved.
45 *
46 * This code is derived from software contributed to Berkeley by
47 * Chris Newcomb.
48 *
49 * Redistribution and use in source and binary forms, with or without
50 * modification, are permitted provided that the following conditions
51 * are met:
52 * 1. Redistributions of source code must retain the above copyright
53 * notice, this list of conditions and the following disclaimer.
54 * 2. Redistributions in binary form must reproduce the above copyright
55 * notice, this list of conditions and the following disclaimer in the
56 * documentation and/or other materials provided with the distribution.
57 * 3. Neither the name of the University nor the names of its contributors
58 * may be used to endorse or promote products derived from this software
59 * without specific prior written permission.
60 *
61 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
62 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
63 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
64 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
65 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
66 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
67 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
68 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
69 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
70 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
71 * SUCH DAMAGE.
72 */
73
74#include <sys/cdefs.h>
38
39#include <sys/cdefs.h>
75__FBSDID("$FreeBSD: head/usr.sbin/makefs/walk.c 186334 2008-12-19 18:45:43Z sam $");
40__FBSDID("$FreeBSD: head/usr.sbin/makefs/walk.c 214921 2010-11-07 16:05:04Z cognet $");
76
77#include <sys/param.h>
78
79#include <assert.h>
80#include <errno.h>
81#include <fcntl.h>
82#include <stdio.h>
83#include <dirent.h>
84#include <stdlib.h>
85#include <string.h>
86#include <unistd.h>
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>
87
88#include "makefs.h"
53
54#include "makefs.h"
89
90#include "mtree.h"
55#include "mtree.h"
91#include "extern.h" /* NB: mtree */
56#include "extern.h"
92
57
93static void apply_specdir(const char *, NODE *, fsnode *);
58static void apply_specdir(const char *, NODE *, fsnode *, int);
94static void apply_specentry(const char *, NODE *, fsnode *);
95static fsnode *create_fsnode(const char *, struct stat *);
96static fsinode *link_check(fsinode *);
97
98
99/*
100 * walk_dir --
101 * build a tree of fsnodes from `dir', with a parent fsnode of `parent'

--- 57 unchanged lines hidden (view full) ---

159 if (stbuf.st_nlink > 1) {
160 fsinode *curino;
161
162 curino = link_check(cur->inode);
163 if (curino != NULL) {
164 free(cur->inode);
165 cur->inode = curino;
166 cur->inode->nlink++;
59static void apply_specentry(const char *, NODE *, fsnode *);
60static fsnode *create_fsnode(const char *, struct stat *);
61static fsinode *link_check(fsinode *);
62
63
64/*
65 * walk_dir --
66 * build a tree of fsnodes from `dir', with a parent fsnode of `parent'

--- 57 unchanged lines hidden (view full) ---

124 if (stbuf.st_nlink > 1) {
125 fsinode *curino;
126
127 curino = link_check(cur->inode);
128 if (curino != NULL) {
129 free(cur->inode);
130 cur->inode = curino;
131 cur->inode->nlink++;
132 if (debug & DEBUG_WALK_DIR_LINKCHECK)
133 printf("link_check: found [%llu, %llu]\n",
134 (unsigned long long)curino->st.st_dev,
135 (unsigned long long)curino->st.st_ino);
167 }
168 }
169 if (S_ISLNK(cur->type)) {
170 char slink[PATH_MAX+1];
171 int llen;
172
173 llen = readlink(path, slink, sizeof(slink) - 1);
174 if (llen == -1)

--- 21 unchanged lines hidden (view full) ---

196 err(1, "Memory allocation error");
197 cur->type = stbuf->st_mode & S_IFMT;
198 cur->inode->nlink = 1;
199 cur->inode->st = *stbuf;
200 return (cur);
201}
202
203/*
136 }
137 }
138 if (S_ISLNK(cur->type)) {
139 char slink[PATH_MAX+1];
140 int llen;
141
142 llen = readlink(path, slink, sizeof(slink) - 1);
143 if (llen == -1)

--- 21 unchanged lines hidden (view full) ---

165 err(1, "Memory allocation error");
166 cur->type = stbuf->st_mode & S_IFMT;
167 cur->inode->nlink = 1;
168 cur->inode->st = *stbuf;
169 return (cur);
170}
171
172/*
173 * free_fsnodes --
174 * Removes node from tree and frees it and all of
175 * its decendents.
176 */
177void
178free_fsnodes(fsnode *node)
179{
180 fsnode *cur, *next;
181
182 assert(node != NULL);
183
184 /* for ".", start with actual parent node */
185 if (node->first == node) {
186 assert(node->name[0] == '.' && node->name[1] == '\0');
187 if (node->parent) {
188 assert(node->parent->child == node);
189 node = node->parent;
190 }
191 }
192
193 /* Find ourselves in our sibling list and unlink */
194 if (node->first != node) {
195 for (cur = node->first; cur->next; cur = cur->next) {
196 if (cur->next == node) {
197 cur->next = node->next;
198 node->next = NULL;
199 break;
200 }
201 }
202 }
203
204 for (cur = node; cur != NULL; cur = next) {
205 next = cur->next;
206 if (cur->child) {
207 cur->child->parent = NULL;
208 free_fsnodes(cur->child);
209 }
210 if (cur->inode->nlink-- == 1)
211 free(cur->inode);
212 if (cur->symlink)
213 free(cur->symlink);
214 free(cur->name);
215 free(cur);
216 }
217}
218
219/*
204 * apply_specfile --
205 * read in the mtree(8) specfile, and apply it to the tree
206 * at dir,parent. parameters in parent on equivalent types
207 * will be changed to those found in specfile, and missing
208 * entries will be added.
209 */
210void
220 * apply_specfile --
221 * read in the mtree(8) specfile, and apply it to the tree
222 * at dir,parent. parameters in parent on equivalent types
223 * will be changed to those found in specfile, and missing
224 * entries will be added.
225 */
226void
211apply_specfile(const char *specfile, const char *dir, fsnode *parent)
227apply_specfile(const char *specfile, const char *dir, fsnode *parent, int speconly)
212{
213 struct timeval start;
214 FILE *fp;
215 NODE *root;
216
217 assert(specfile != NULL);
218 assert(parent != NULL);
219

--- 11 unchanged lines hidden (view full) ---

231
232 /* perform some sanity checks */
233 if (root == NULL)
234 errx(1, "Specfile `%s' did not contain a tree", specfile);
235 assert(strcmp(root->name, ".") == 0);
236 assert(root->type == F_DIR);
237
238 /* merge in the changes */
228{
229 struct timeval start;
230 FILE *fp;
231 NODE *root;
232
233 assert(specfile != NULL);
234 assert(parent != NULL);
235

--- 11 unchanged lines hidden (view full) ---

247
248 /* perform some sanity checks */
249 if (root == NULL)
250 errx(1, "Specfile `%s' did not contain a tree", specfile);
251 assert(strcmp(root->name, ".") == 0);
252 assert(root->type == F_DIR);
253
254 /* merge in the changes */
239 apply_specdir(dir, root, parent);
255 apply_specdir(dir, root, parent, speconly);
256
240}
241
242static u_int
243nodetoino(u_int type)
244{
245
246 switch (type) {
247 case F_BLOCK:

--- 12 unchanged lines hidden (view full) ---

260 return S_IFSOCK;
261 default:
262 printf("unknown type %d", type);
263 abort();
264 }
265 /* NOTREACHED */
266}
267
257}
258
259static u_int
260nodetoino(u_int type)
261{
262
263 switch (type) {
264 case F_BLOCK:

--- 12 unchanged lines hidden (view full) ---

277 return S_IFSOCK;
278 default:
279 printf("unknown type %d", type);
280 abort();
281 }
282 /* NOTREACHED */
283}
284
285
268static void
286static void
269apply_specdir(const char *dir, NODE *specnode, fsnode *dirnode)
287apply_specdir(const char *dir, NODE *specnode, fsnode *dirnode, int speconly)
270{
271 char path[MAXPATHLEN + 1];
272 NODE *curnode;
273 fsnode *curfsnode;
274
275 assert(specnode != NULL);
276 assert(dirnode != NULL);
277

--- 4 unchanged lines hidden (view full) ---

282 errx(1, "Specfile node `%s/%s' is not a directory",
283 dir, specnode->name);
284 if (dirnode->type != S_IFDIR)
285 errx(1, "Directory node `%s/%s' is not a directory",
286 dir, dirnode->name);
287
288 apply_specentry(dir, specnode, dirnode);
289
288{
289 char path[MAXPATHLEN + 1];
290 NODE *curnode;
291 fsnode *curfsnode;
292
293 assert(specnode != NULL);
294 assert(dirnode != NULL);
295

--- 4 unchanged lines hidden (view full) ---

300 errx(1, "Specfile node `%s/%s' is not a directory",
301 dir, specnode->name);
302 if (dirnode->type != S_IFDIR)
303 errx(1, "Directory node `%s/%s' is not a directory",
304 dir, dirnode->name);
305
306 apply_specentry(dir, specnode, dirnode);
307
308 /* Remove any filesystem nodes not found in specfile */
309 /* XXX inefficient. This is O^2 in each dir and it would
310 * have been better never to have walked this part of the tree
311 * to begin with
312 */
313 if (speconly) {
314 fsnode *next;
315 assert(dirnode->name[0] == '.' && dirnode->name[1] == '\0');
316 for (curfsnode = dirnode->next; curfsnode != NULL; curfsnode = next) {
317 next = curfsnode->next;
318 for (curnode = specnode->child; curnode != NULL;
319 curnode = curnode->next) {
320 if (strcmp(curnode->name, curfsnode->name) == 0)
321 break;
322 }
323 if (curnode == NULL) {
324 if (debug & DEBUG_APPLY_SPECONLY) {
325 printf("apply_specdir: trimming %s/%s %p\n", dir, curfsnode->name, curfsnode);
326 }
327 free_fsnodes(curfsnode);
328 }
329 }
330 }
331
290 /* now walk specnode->child matching up with dirnode */
291 for (curnode = specnode->child; curnode != NULL;
292 curnode = curnode->next) {
293 if (debug & DEBUG_APPLY_SPECENTRY)
294 printf("apply_specdir: spec %s\n",
295 curnode->name);
296 for (curfsnode = dirnode->next; curfsnode != NULL;
297 curfsnode = curfsnode->next) {

--- 25 unchanged lines hidden (view full) ---

323 errx(1, "`%s': %s not provided", path, m)
324 NODETEST(curnode->flags & F_TYPE, "type");
325 NODETEST(curnode->flags & F_MODE, "mode");
326 /* XXX: require F_TIME ? */
327 NODETEST(curnode->flags & F_GID ||
328 curnode->flags & F_GNAME, "group");
329 NODETEST(curnode->flags & F_UID ||
330 curnode->flags & F_UNAME, "user");
332 /* now walk specnode->child matching up with dirnode */
333 for (curnode = specnode->child; curnode != NULL;
334 curnode = curnode->next) {
335 if (debug & DEBUG_APPLY_SPECENTRY)
336 printf("apply_specdir: spec %s\n",
337 curnode->name);
338 for (curfsnode = dirnode->next; curfsnode != NULL;
339 curfsnode = curfsnode->next) {

--- 25 unchanged lines hidden (view full) ---

365 errx(1, "`%s': %s not provided", path, m)
366 NODETEST(curnode->flags & F_TYPE, "type");
367 NODETEST(curnode->flags & F_MODE, "mode");
368 /* XXX: require F_TIME ? */
369 NODETEST(curnode->flags & F_GID ||
370 curnode->flags & F_GNAME, "group");
371 NODETEST(curnode->flags & F_UID ||
372 curnode->flags & F_UNAME, "user");
373/* if (curnode->type == F_BLOCK || curnode->type == F_CHAR)
374 NODETEST(curnode->flags & F_DEV,
375 "device number");*/
331#undef NODETEST
332
333 if (debug & DEBUG_APPLY_SPECFILE)
334 printf("apply_specdir: adding %s\n",
335 curnode->name);
336 /* build minimal fsnode */
337 memset(&stbuf, 0, sizeof(stbuf));
338 stbuf.st_mode = nodetoino(curnode->type);

--- 23 unchanged lines hidden (view full) ---

362 err(1, "Memory allocation error");
363 }
364 }
365 apply_specentry(dir, curnode, curfsnode);
366 if (curnode->type == F_DIR) {
367 if (curfsnode->type != S_IFDIR)
368 errx(1, "`%s' is not a directory", path);
369 assert (curfsnode->child != NULL);
376#undef NODETEST
377
378 if (debug & DEBUG_APPLY_SPECFILE)
379 printf("apply_specdir: adding %s\n",
380 curnode->name);
381 /* build minimal fsnode */
382 memset(&stbuf, 0, sizeof(stbuf));
383 stbuf.st_mode = nodetoino(curnode->type);

--- 23 unchanged lines hidden (view full) ---

407 err(1, "Memory allocation error");
408 }
409 }
410 apply_specentry(dir, curnode, curfsnode);
411 if (curnode->type == F_DIR) {
412 if (curfsnode->type != S_IFDIR)
413 errx(1, "`%s' is not a directory", path);
414 assert (curfsnode->child != NULL);
370 apply_specdir(path, curnode, curfsnode->child);
415 apply_specdir(path, curnode, curfsnode->child, speconly);
371 }
372 }
373}
374
375static void
376apply_specentry(const char *dir, NODE *specnode, fsnode *dirnode)
377{
378

--- 60 unchanged lines hidden (view full) ---

439#if HAVE_STRUCT_STAT_ST_FLAGS
440 if (specnode->flags & F_FLAGS) {
441 ASEPRINT("flags", "%#lX",
442 (unsigned long)dirnode->inode->st.st_flags,
443 (unsigned long)specnode->st_flags);
444 dirnode->inode->st.st_flags = specnode->st_flags;
445 }
446#endif
416 }
417 }
418}
419
420static void
421apply_specentry(const char *dir, NODE *specnode, fsnode *dirnode)
422{
423

--- 60 unchanged lines hidden (view full) ---

484#if HAVE_STRUCT_STAT_ST_FLAGS
485 if (specnode->flags & F_FLAGS) {
486 ASEPRINT("flags", "%#lX",
487 (unsigned long)dirnode->inode->st.st_flags,
488 (unsigned long)specnode->st_flags);
489 dirnode->inode->st.st_flags = specnode->st_flags;
490 }
491#endif
492/* if (specnode->flags & F_DEV) {
493 ASEPRINT("rdev", "%#llx",
494 (unsigned long long)dirnode->inode->st.st_rdev,
495 (unsigned long long)specnode->st_rdev);
496 dirnode->inode->st.st_rdev = specnode->st_rdev;
497 }*/
447#undef ASEPRINT
448
449 dirnode->flags |= FSNODE_F_HASSPEC;
450}
451
452
453/*
454 * dump_fsnodes --

--- 33 unchanged lines hidden (view full) ---

488 }
489 printf("dump_fsnodes: finished %s\n", dir);
490}
491
492
493/*
494 * inode_type --
495 * for a given inode type `mode', return a descriptive string.
498#undef ASEPRINT
499
500 dirnode->flags |= FSNODE_F_HASSPEC;
501}
502
503
504/*
505 * dump_fsnodes --

--- 33 unchanged lines hidden (view full) ---

539 }
540 printf("dump_fsnodes: finished %s\n", dir);
541}
542
543
544/*
545 * inode_type --
546 * for a given inode type `mode', return a descriptive string.
547 * for most cases, uses inotype() from mtree/misc.c
496 */
497const char *
498inode_type(mode_t mode)
499{
548 */
549const char *
550inode_type(mode_t mode)
551{
500
501 if (S_ISREG(mode))
502 return ("file");
503 if (S_ISLNK(mode))
504 return ("symlink");
505 if (S_ISDIR(mode))
506 return ("dir");
507 if (S_ISLNK(mode))
508 return ("link");

--- 7 unchanged lines hidden (view full) ---

516 if (S_ISBLK(mode))
517 return ("block");
518 return ("unknown");
519}
520
521
522/*
523 * link_check --
552 if (S_ISREG(mode))
553 return ("file");
554 if (S_ISLNK(mode))
555 return ("symlink");
556 if (S_ISDIR(mode))
557 return ("dir");
558 if (S_ISLNK(mode))
559 return ("link");

--- 7 unchanged lines hidden (view full) ---

567 if (S_ISBLK(mode))
568 return ("block");
569 return ("unknown");
570}
571
572
573/*
574 * link_check --
524 * return pointer to fsnode matching `entry's st_ino & st_dev if it exists,
575 * return pointer to fsinode matching `entry's st_ino & st_dev if it exists,
525 * otherwise add `entry' to table and return NULL
526 */
576 * otherwise add `entry' to table and return NULL
577 */
578/* This was borrowed from du.c and tweaked to keep an fsnode
579 * pointer instead. -- dbj@netbsd.org
580 */
527static fsinode *
528link_check(fsinode *entry)
529{
581static fsinode *
582link_check(fsinode *entry)
583{
530 static struct dupnode {
531 uint32_t dev;
532 uint64_t ino;
533 fsinode *dup;
534 } *dups, *newdups;
535 static int ndups, maxdups;
584 static struct entry {
585 fsinode *data;
586 } *htable;
587 static int htshift; /* log(allocated size) */
588 static int htmask; /* allocated size - 1 */
589 static int htused; /* 2*number of insertions */
590 int h, h2;
591 uint64_t tmp;
592 /* this constant is (1<<64)/((1+sqrt(5))/2)
593 * aka (word size)/(golden ratio)
594 */
595 const uint64_t HTCONST = 11400714819323198485ULL;
596 const int HTBITS = 64;
597
598 /* Never store zero in hashtable */
599 assert(entry);
536
600
537 int i;
601 /* Extend hash table if necessary, keep load under 0.5 */
602 if (htused<<1 >= htmask) {
603 struct entry *ohtable;
538
604
539 assert (entry != NULL);
605 if (!htable)
606 htshift = 10; /* starting hashtable size */
607 else
608 htshift++; /* exponential hashtable growth */
540
609
541 /* XXX; maybe traverse in reverse for speed? */
542 for (i = 0; i < ndups; i++) {
543 if (dups[i].dev == entry->st.st_dev &&
544 dups[i].ino == entry->st.st_ino) {
545 if (debug & DEBUG_WALK_DIR_LINKCHECK)
546 printf("link_check: found [%d,%d]\n",
547 entry->st.st_dev, entry->st.st_ino);
548 return (dups[i].dup);
610 htmask = (1 << htshift) - 1;
611 htused = 0;
612
613 ohtable = htable;
614 htable = calloc(htmask+1, sizeof(*htable));
615 if (!htable)
616 err(1, "Memory allocation error");
617
618 /* populate newly allocated hashtable */
619 if (ohtable) {
620 int i;
621 for (i = 0; i <= htmask>>1; i++)
622 if (ohtable[i].data)
623 link_check(ohtable[i].data);
624 free(ohtable);
549 }
550 }
551
625 }
626 }
627
552 if (debug & DEBUG_WALK_DIR_LINKCHECK)
553 printf("link_check: no match for [%d, %d]\n",
554 entry->st.st_dev, entry->st.st_ino);
555 if (ndups == maxdups) {
556 if ((newdups = realloc(dups, sizeof(struct dupnode) * (maxdups + 128)))
557 == NULL)
558 err(1, "Memory allocation error");
559 dups = newdups;
560 maxdups += 128;
628 /* multiplicative hashing */
629 tmp = entry->st.st_dev;
630 tmp <<= HTBITS>>1;
631 tmp |= entry->st.st_ino;
632 tmp *= HTCONST;
633 h = tmp >> (HTBITS - htshift);
634 h2 = 1 | ( tmp >> (HTBITS - (htshift<<1) - 1)); /* must be odd */
635
636 /* open address hashtable search with double hash probing */
637 while (htable[h].data) {
638 if ((htable[h].data->st.st_ino == entry->st.st_ino) &&
639 (htable[h].data->st.st_dev == entry->st.st_dev)) {
640 return htable[h].data;
641 }
642 h = (h + h2) & htmask;
561 }
643 }
562 dups[ndups].dev = entry->st.st_dev;
563 dups[ndups].ino = entry->st.st_ino;
564 dups[ndups].dup = entry;
565 ndups++;
566
644
567 return (NULL);
645 /* Insert the current entry into hashtable */
646 htable[h].data = entry;
647 htused++;
648 return NULL;
568}
649}