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