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