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