usr.sbin/makefs/walk.c

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