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