1/*- 2 * Copyright (c) 1988, 1989, 1990, 1993 3 * The Regents of the University of California. All rights reserved. 4 * Copyright (c) 1988, 1989 by Adam de Boor 5 * Copyright (c) 1989 by Berkeley Softworks 6 * All rights reserved. 7 * 8 * This code is derived from software contributed to Berkeley by 9 * Adam de Boor. 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 by the University of 22 * California, Berkeley and its contributors. 23 * 4. Neither the name of the University nor the names of its contributors 24 * may be used to endorse or promote products derived from this software 25 * without specific prior written permission. 26 * 27 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 28 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 29 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 30 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 31 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 32 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 33 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 34 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 35 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 36 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 37 * SUCH DAMAGE. 38 * 39 * @(#)dir.c 8.2 (Berkeley) 1/2/94 40 */ 41 42#include <sys/cdefs.h> 43__FBSDID("$FreeBSD$"); 44 45/*- 46 * dir.c -- 47 * Directory searching using wildcards and/or normal names... 48 * Used both for source wildcarding in the Makefile and for finding 49 * implicit sources. 50 * 51 * The interface for this module is: 52 * Dir_Init Initialize the module. 53 * 54 * Dir_HasWildcards Returns TRUE if the name given it needs to 55 * be wildcard-expanded. 56 * 57 * Path_Expand Given a pattern and a path, return a Lst of names 58 * which match the pattern on the search path. 59 * 60 * Path_FindFile Searches for a file on a given search path. 61 * If it exists, the entire path is returned. 62 * Otherwise NULL is returned. 63 * 64 * Dir_FindHereOrAbove Search for a path in the current directory and 65 * then all the directories above it in turn until 66 * the path is found or we reach the root ("/"). 67 * 68 * Dir_MTime Return the modification time of a node. The file 69 * is searched for along the default search path. 70 * The path and mtime fields of the node are filled in. 71 * 72 * Path_AddDir Add a directory to a search path. 73 * 74 * Dir_MakeFlags Given a search path and a command flag, create 75 * a string with each of the directories in the path 76 * preceded by the command flag and all of them 77 * separated by a space. 78 * 79 * Dir_Destroy Destroy an element of a search path. Frees up all 80 * things that can be freed for the element as long 81 * as the element is no longer referenced by any other 82 * search path. 83 * 84 * Dir_ClearPath Resets a search path to the empty list. 85 * 86 * For debugging: 87 * Dir_PrintDirectories Print stats about the directory cache. 88 */ 89 90#include <sys/param.h> 91#include <sys/stat.h> 92#include <dirent.h> 93#include <err.h> 94#include <stdio.h> 95#include <stdlib.h> 96#include <string.h> 97 98#include "arch.h" 99#include "dir.h" 100#include "globals.h" 101#include "GNode.h" 102#include "hash.h" 103#include "lst.h" 104#include "str.h" 105#include "targ.h" 106#include "util.h" 107 108/* 109 * A search path consists of a list of Dir structures. A Dir structure 110 * has in it the name of the directory and a hash table of all the files 111 * in the directory. This is used to cut down on the number of system 112 * calls necessary to find implicit dependents and their like. Since 113 * these searches are made before any actions are taken, we need not 114 * worry about the directory changing due to creation commands. If this 115 * hampers the style of some makefiles, they must be changed. 116 * 117 * A list of all previously-read directories is kept in the 118 * openDirectories list. This list is checked first before a directory 119 * is opened. 120 * 121 * The need for the caching of whole directories is brought about by 122 * the multi-level transformation code in suff.c, which tends to search 123 * for far more files than regular make does. In the initial 124 * implementation, the amount of time spent performing "stat" calls was 125 * truly astronomical. The problem with hashing at the start is, 126 * of course, that pmake doesn't then detect changes to these directories 127 * during the course of the make. Three possibilities suggest themselves: 128 * 129 * 1) just use stat to test for a file's existence. As mentioned 130 * above, this is very inefficient due to the number of checks 131 * engendered by the multi-level transformation code. 132 * 2) use readdir() and company to search the directories, keeping 133 * them open between checks. I have tried this and while it 134 * didn't slow down the process too much, it could severely 135 * affect the amount of parallelism available as each directory 136 * open would take another file descriptor out of play for 137 * handling I/O for another job. Given that it is only recently 138 * that UNIX OS's have taken to allowing more than 20 or 32 139 * file descriptors for a process, this doesn't seem acceptable 140 * to me. 141 * 3) record the mtime of the directory in the Dir structure and 142 * verify the directory hasn't changed since the contents were 143 * hashed. This will catch the creation or deletion of files, 144 * but not the updating of files. However, since it is the 145 * creation and deletion that is the problem, this could be 146 * a good thing to do. Unfortunately, if the directory (say ".") 147 * were fairly large and changed fairly frequently, the constant 148 * rehashing could seriously degrade performance. It might be 149 * good in such cases to keep track of the number of rehashes 150 * and if the number goes over a (small) limit, resort to using 151 * stat in its place. 152 * 153 * An additional thing to consider is that pmake is used primarily 154 * to create C programs and until recently pcc-based compilers refused 155 * to allow you to specify where the resulting object file should be 156 * placed. This forced all objects to be created in the current 157 * directory. This isn't meant as a full excuse, just an explanation of 158 * some of the reasons for the caching used here. 159 * 160 * One more note: the location of a target's file is only performed 161 * on the downward traversal of the graph and then only for terminal 162 * nodes in the graph. This could be construed as wrong in some cases, 163 * but prevents inadvertent modification of files when the "installed" 164 * directory for a file is provided in the search path. 165 * 166 * Another data structure maintained by this module is an mtime 167 * cache used when the searching of cached directories fails to find 168 * a file. In the past, Path_FindFile would simply perform an access() 169 * call in such a case to determine if the file could be found using 170 * just the name given. When this hit, however, all that was gained 171 * was the knowledge that the file existed. Given that an access() is 172 * essentially a stat() without the copyout() call, and that the same 173 * filesystem overhead would have to be incurred in Dir_MTime, it made 174 * sense to replace the access() with a stat() and record the mtime 175 * in a cache for when Dir_MTime was actually called. 176 */ 177 178typedef struct Dir { 179 char *name; /* Name of directory */ 180 int refCount; /* No. of paths with this directory */ 181 int hits; /* No. of times a file has been found here */ 182 Hash_Table files; /* Hash table of files in directory */ 183 TAILQ_ENTRY(Dir) link; /* allDirs link */ 184} Dir; 185 186/* 187 * A path is a list of pointers to directories. These directories are 188 * reference counted so a directory can be on more than one path. 189 */ 190struct PathElement { 191 struct Dir *dir; /* pointer to the directory */ 192 TAILQ_ENTRY(PathElement) link; /* path link */ 193}; 194 195/* main search path */ 196struct Path dirSearchPath = TAILQ_HEAD_INITIALIZER(dirSearchPath); 197 198/* the list of all open directories */ 199static TAILQ_HEAD(, Dir) openDirectories = 200 TAILQ_HEAD_INITIALIZER(openDirectories); 201 202/* 203 * Variables for gathering statistics on the efficiency of the hashing 204 * mechanism. 205 */ 206static int hits; /* Found in directory cache */ 207static int misses; /* Sad, but not evil misses */ 208static int nearmisses; /* Found under search path */ 209static int bigmisses; /* Sought by itself */ 210 211static Dir *dot; /* contents of current directory */ 212 213/* Results of doing a last-resort stat in Path_FindFile -- 214 * if we have to go to the system to find the file, we might as well 215 * have its mtime on record. 216 * XXX: If this is done way early, there's a chance other rules will 217 * have already updated the file, in which case we'll update it again. 218 * Generally, there won't be two rules to update a single file, so this 219 * should be ok, but... 220 */ 221static Hash_Table mtimes; 222 223/*- 224 *----------------------------------------------------------------------- 225 * Dir_Init -- 226 * initialize things for this module 227 * 228 * Results: 229 * none 230 * 231 * Side Effects: 232 * none 233 *----------------------------------------------------------------------- 234 */ 235void 236Dir_Init(void) 237{ 238 239 Hash_InitTable(&mtimes, 0); 240} 241 242/*- 243 *----------------------------------------------------------------------- 244 * Dir_InitDot -- 245 * initialize the "." directory 246 * 247 * Results: 248 * none 249 * 250 * Side Effects: 251 * some directories may be opened. 252 *----------------------------------------------------------------------- 253 */ 254void 255Dir_InitDot(void) 256{ 257 258 dot = Path_AddDir(NULL, "."); 259 if (dot == NULL) 260 err(1, "cannot open current directory"); 261 262 /* 263 * We always need to have dot around, so we increment its 264 * reference count to make sure it's not destroyed. 265 */ 266 dot->refCount += 1; 267} 268 269/*- 270 *----------------------------------------------------------------------- 271 * Dir_HasWildcards -- 272 * See if the given name has any wildcard characters in it. 273 * 274 * Results: 275 * returns TRUE if the word should be expanded, FALSE otherwise 276 * 277 * Side Effects: 278 * none 279 *----------------------------------------------------------------------- 280 */ 281Boolean 282Dir_HasWildcards(const char *name) 283{ 284 const char *cp; 285 int wild = 0, brace = 0, bracket = 0; 286 287 for (cp = name; *cp; cp++) { 288 switch (*cp) { 289 case '{': 290 brace++; 291 wild = 1; 292 break; 293 case '}': 294 brace--; 295 break; 296 case '[': 297 bracket++; 298 wild = 1; 299 break; 300 case ']': 301 bracket--; 302 break; 303 case '?': 304 case '*': 305 wild = 1; 306 break; 307 default: 308 break; 309 } 310 } 311 return (wild && bracket == 0 && brace == 0); 312} 313 314/*- 315 *----------------------------------------------------------------------- 316 * DirMatchFiles -- 317 * Given a pattern and a Dir structure, see if any files 318 * match the pattern and add their names to the 'expansions' list if 319 * any do. This is incomplete -- it doesn't take care of patterns like 320 * src / *src / *.c properly (just *.c on any of the directories), but it 321 * will do for now. 322 * 323 * Results: 324 * Always returns 0 325 * 326 * Side Effects: 327 * File names are added to the expansions lst. The directory will be 328 * fully hashed when this is done. 329 *----------------------------------------------------------------------- 330 */ 331static int 332DirMatchFiles(const char *pattern, const Dir *p, Lst *expansions) 333{ 334 Hash_Search search; /* Index into the directory's table */ 335 Hash_Entry *entry; /* Current entry in the table */ 336 Boolean isDot; /* TRUE if the directory being searched is . */ 337 338 isDot = (*p->name == '.' && p->name[1] == '\0'); 339 340 for (entry = Hash_EnumFirst(&p->files, &search); 341 entry != NULL; 342 entry = Hash_EnumNext(&search)) { 343 /* 344 * See if the file matches the given pattern. Note we follow 345 * the UNIX convention that dot files will only be found if 346 * the pattern begins with a dot (note also that as a side 347 * effect of the hashing scheme, .* won't match . or .. 348 * since they aren't hashed). 349 */ 350 if (Str_Match(entry->name, pattern) && 351 ((entry->name[0] != '.') || 352 (pattern[0] == '.'))) { 353 Lst_AtEnd(expansions, (isDot ? estrdup(entry->name) : 354 str_concat(p->name, entry->name, STR_ADDSLASH))); 355 } 356 } 357 return (0); 358} 359 360/*- 361 *----------------------------------------------------------------------- 362 * DirExpandCurly -- 363 * Expand curly braces like the C shell. Does this recursively. 364 * Note the special case: if after the piece of the curly brace is 365 * done there are no wildcard characters in the result, the result is 366 * placed on the list WITHOUT CHECKING FOR ITS EXISTENCE. The 367 * given arguments are the entire word to expand, the first curly 368 * brace in the word, the search path, and the list to store the 369 * expansions in. 370 * 371 * Results: 372 * None. 373 * 374 * Side Effects: 375 * The given list is filled with the expansions... 376 * 377 *----------------------------------------------------------------------- 378 */ 379static void 380DirExpandCurly(const char *word, const char *brace, struct Path *path, 381 Lst *expansions) 382{ 383 const char *end; /* Character after the closing brace */ 384 const char *cp; /* Current position in brace clause */ 385 const char *start; /* Start of current piece of brace clause */ 386 int bracelevel; /* Number of braces we've seen. If we see a right brace 387 * when this is 0, we've hit the end of the clause. */ 388 char *file; /* Current expansion */ 389 int otherLen; /* The length of the other pieces of the expansion 390 * (chars before and after the clause in 'word') */ 391 char *cp2; /* Pointer for checking for wildcards in 392 * expansion before calling Dir_Expand */ 393 394 start = brace + 1; 395 396 /* 397 * Find the end of the brace clause first, being wary of nested brace 398 * clauses. 399 */ 400 for (end = start, bracelevel = 0; *end != '\0'; end++) { 401 if (*end == '{') 402 bracelevel++; 403 else if ((*end == '}') && (bracelevel-- == 0)) 404 break; 405 } 406 if (*end == '\0') { 407 Error("Unterminated {} clause \"%s\"", start); 408 return; 409 } else 410 end++; 411 412 otherLen = brace - word + strlen(end); 413 414 for (cp = start; cp < end; cp++) { 415 /* 416 * Find the end of this piece of the clause. 417 */ 418 bracelevel = 0; 419 while (*cp != ',') { 420 if (*cp == '{') 421 bracelevel++; 422 else if ((*cp == '}') && (bracelevel-- <= 0)) 423 break; 424 cp++; 425 } 426 /* 427 * Allocate room for the combination and install the 428 * three pieces. 429 */ 430 file = emalloc(otherLen + cp - start + 1); 431 if (brace != word) 432 strncpy(file, word, brace - word); 433 if (cp != start) 434 strncpy(&file[brace - word], start, cp - start); 435 strcpy(&file[(brace - word) + (cp - start)], end); 436 437 /* 438 * See if the result has any wildcards in it. If we find one, 439 * call Dir_Expand right away, telling it to place the result 440 * on our list of expansions. 441 */ 442 for (cp2 = file; *cp2 != '\0'; cp2++) { 443 switch (*cp2) { 444 case '*': 445 case '?': 446 case '{': 447 case '[': 448 Path_Expand(file, path, expansions); 449 goto next; 450 default: 451 break; 452 } 453 } 454 if (*cp2 == '\0') { 455 /* 456 * Hit the end w/o finding any wildcards, so stick 457 * the expansion on the end of the list. 458 */ 459 Lst_AtEnd(expansions, file); 460 } else { 461 next: 462 free(file); 463 } 464 start = cp + 1; 465 } 466} 467 468/*- 469 *----------------------------------------------------------------------- 470 * DirExpandInt -- 471 * Internal expand routine. Passes through the directories in the 472 * path one by one, calling DirMatchFiles for each. NOTE: This still 473 * doesn't handle patterns in directories... Works given a word to 474 * expand, a path to look in, and a list to store expansions in. 475 * 476 * Results: 477 * None. 478 * 479 * Side Effects: 480 * Things are added to the expansions list. 481 * 482 *----------------------------------------------------------------------- 483 */ 484static void 485DirExpandInt(const char *word, const struct Path *path, Lst *expansions) 486{ 487 struct PathElement *pe; 488 489 TAILQ_FOREACH(pe, path, link) 490 DirMatchFiles(word, pe->dir, expansions); 491} 492 493/*- 494 *----------------------------------------------------------------------- 495 * Dir_Expand -- 496 * Expand the given word into a list of words by globbing it looking 497 * in the directories on the given search path. 498 * 499 * Results: 500 * A list of words consisting of the files which exist along the search 501 * path matching the given pattern is placed in expansions. 502 * 503 * Side Effects: 504 * Directories may be opened. Who knows? 505 *----------------------------------------------------------------------- 506 */ 507void 508Path_Expand(char *word, struct Path *path, Lst *expansions) 509{ 510 LstNode *ln; 511 char *cp; 512 513 DEBUGF(DIR, ("expanding \"%s\"...", word)); 514 515 cp = strchr(word, '{'); 516 if (cp != NULL) 517 DirExpandCurly(word, cp, path, expansions); 518 else { 519 cp = strchr(word, '/'); 520 if (cp != NULL) { 521 /* 522 * The thing has a directory component -- find the 523 * first wildcard in the string. 524 */ 525 for (cp = word; *cp != '\0'; cp++) { 526 if (*cp == '?' || *cp == '[' || 527 *cp == '*' || *cp == '{') { 528 break; 529 } 530 } 531 if (*cp == '{') { 532 /* 533 * This one will be fun. 534 */ 535 DirExpandCurly(word, cp, path, expansions); 536 return; 537 } else if (*cp != '\0') { 538 /* 539 * Back up to the start of the component 540 */ 541 char *dirpath; 542 543 while (cp > word && *cp != '/') 544 cp--; 545 if (cp != word) { 546 char sc; 547 548 /* 549 * If the glob isn't in the first 550 * component, try and find all the 551 * components up to the one with a 552 * wildcard. 553 */ 554 sc = cp[1]; 555 cp[1] = '\0'; 556 dirpath = Path_FindFile(word, path); 557 cp[1] = sc; 558 /* 559 * dirpath is null if can't find the 560 * leading component 561 * XXX: Path_FindFile won't find internal 562 * components. i.e. if the path contains 563 * ../Etc/Object and we're looking for 564 * Etc, * it won't be found. Ah well. 565 * Probably not important. 566 */ 567 if (dirpath != NULL) { 568 char *dp = 569 &dirpath[strlen(dirpath) 570 - 1]; 571 struct Path tp = 572 TAILQ_HEAD_INITIALIZER(tp); 573 574 if (*dp == '/') 575 *dp = '\0'; 576 Path_AddDir(&tp, dirpath); 577 DirExpandInt(cp + 1, &tp, 578 expansions); 579 Path_Clear(&tp); 580 } 581 } else { 582 /* 583 * Start the search from the local 584 * directory 585 */ 586 DirExpandInt(word, path, expansions); 587 } 588 } else { 589 /* 590 * Return the file -- this should never happen. 591 */ 592 DirExpandInt(word, path, expansions); 593 } 594 } else { 595 /* 596 * First the files in dot 597 */ 598 DirMatchFiles(word, dot, expansions); 599 600 /* 601 * Then the files in every other directory on the path. 602 */ 603 DirExpandInt(word, path, expansions); 604 } 605 } 606 if (DEBUG(DIR)) { 607 LST_FOREACH(ln, expansions) 608 DEBUGF(DIR, ("%s ", (const char *)Lst_Datum(ln))); 609 DEBUGF(DIR, ("\n")); 610 } 611} 612 613/** 614 * Path_FindFile 615 * Find the file with the given name along the given search path. 616 * 617 * Results: 618 * The path to the file or NULL. This path is guaranteed to be in a 619 * different part of memory than name and so may be safely free'd. 620 * 621 * Side Effects: 622 * If the file is found in a directory which is not on the path 623 * already (either 'name' is absolute or it is a relative path 624 * [ dir1/.../dirn/file ] which exists below one of the directories 625 * already on the search path), its directory is added to the end 626 * of the path on the assumption that there will be more files in 627 * that directory later on. Sometimes this is true. Sometimes not. 628 */ 629char * 630Path_FindFile(char *name, struct Path *path) 631{ 632 char *p1; /* pointer into p->name */ 633 char *p2; /* pointer into name */ 634 char *file; /* the current filename to check */ 635 const struct PathElement *pe; /* current path member */ 636 char *cp; /* final component of the name */ 637 Boolean hasSlash; /* true if 'name' contains a / */ 638 struct stat stb; /* Buffer for stat, if necessary */ 639 Hash_Entry *entry; /* Entry for mtimes table */ 640 641 /* 642 * Find the final component of the name and note whether it has a 643 * slash in it (the name, I mean) 644 */ 645 cp = strrchr(name, '/'); 646 if (cp != NULL) { 647 hasSlash = TRUE; 648 cp += 1; 649 } else { 650 hasSlash = FALSE; 651 cp = name; 652 } 653 654 DEBUGF(DIR, ("Searching for %s...", name)); 655 /* 656 * No matter what, we always look for the file in the current directory 657 * before anywhere else and we *do not* add the ./ to it if it exists. 658 * This is so there are no conflicts between what the user specifies 659 * (fish.c) and what pmake finds (./fish.c). 660 */ 661 if ((!hasSlash || (cp - name == 2 && *name == '.')) && 662 (Hash_FindEntry(&dot->files, cp) != NULL)) { 663 DEBUGF(DIR, ("in '.'\n")); 664 hits += 1; 665 dot->hits += 1; 666 return (estrdup(name)); 667 } 668 669 /* 670 * We look through all the directories on the path seeking one which 671 * contains the final component of the given name and whose final 672 * component(s) match the name's initial component(s). If such a beast 673 * is found, we concatenate the directory name and the final component 674 * and return the resulting string. If we don't find any such thing, 675 * we go on to phase two... 676 */ 677 TAILQ_FOREACH(pe, path, link) { 678 DEBUGF(DIR, ("%s...", pe->dir->name)); 679 if (Hash_FindEntry(&pe->dir->files, cp) != NULL) { 680 DEBUGF(DIR, ("here...")); 681 if (hasSlash) { 682 /* 683 * If the name had a slash, its initial 684 * components and p's final components must 685 * match. This is false if a mismatch is 686 * encountered before all of the initial 687 * components have been checked (p2 > name at 688 * the end of the loop), or we matched only 689 * part of one of the components of p 690 * along with all the rest of them (*p1 != '/'). 691 */ 692 p1 = pe->dir->name + strlen(pe->dir->name) - 1; 693 p2 = cp - 2; 694 while (p2 >= name && p1 >= pe->dir->name && 695 *p1 == *p2) { 696 p1 -= 1; p2 -= 1; 697 } 698 if (p2 >= name || (p1 >= pe->dir->name && 699 *p1 != '/')) { 700 DEBUGF(DIR, ("component mismatch -- " 701 "continuing...")); 702 continue; 703 } 704 } 705 file = str_concat(pe->dir->name, cp, STR_ADDSLASH); 706 DEBUGF(DIR, ("returning %s\n", file)); 707 pe->dir->hits += 1; 708 hits += 1; 709 return (file); 710 } else if (hasSlash) { 711 /* 712 * If the file has a leading path component and that 713 * component exactly matches the entire name of the 714 * current search directory, we assume the file 715 * doesn't exist and return NULL. 716 */ 717 for (p1 = pe->dir->name, p2 = name; *p1 && *p1 == *p2; 718 p1++, p2++) 719 continue; 720 if (*p1 == '\0' && p2 == cp - 1) { 721 if (*cp == '\0' || ISDOT(cp) || ISDOTDOT(cp)) { 722 DEBUGF(DIR, ("returning %s\n", name)); 723 return (estrdup(name)); 724 } else { 725 DEBUGF(DIR, ("must be here but isn't --" 726 " returning NULL\n")); 727 return (NULL); 728 } 729 } 730 } 731 } 732 733 /* 734 * We didn't find the file on any existing members of the directory. 735 * If the name doesn't contain a slash, that means it doesn't exist. 736 * If it *does* contain a slash, however, there is still hope: it 737 * could be in a subdirectory of one of the members of the search 738 * path. (eg. /usr/include and sys/types.h. The above search would 739 * fail to turn up types.h in /usr/include, but it *is* in 740 * /usr/include/sys/types.h) If we find such a beast, we assume there 741 * will be more (what else can we assume?) and add all but the last 742 * component of the resulting name onto the search path (at the 743 * end). This phase is only performed if the file is *not* absolute. 744 */ 745 if (!hasSlash) { 746 DEBUGF(DIR, ("failed.\n")); 747 misses += 1; 748 return (NULL); 749 } 750 751 if (*name != '/') { 752 Boolean checkedDot = FALSE; 753 754 DEBUGF(DIR, ("failed. Trying subdirectories...")); 755 TAILQ_FOREACH(pe, path, link) { 756 if (pe->dir != dot) { 757 file = str_concat(pe->dir->name, 758 name, STR_ADDSLASH); 759 } else { 760 /* 761 * Checking in dot -- DON'T put a leading ./ 762 * on the thing. 763 */ 764 file = estrdup(name); 765 checkedDot = TRUE; 766 } 767 DEBUGF(DIR, ("checking %s...", file)); 768 769 if (stat(file, &stb) == 0) { 770 DEBUGF(DIR, ("got it.\n")); 771 772 /* 773 * We've found another directory to search. We 774 * know there's a slash in 'file' because we put 775 * one there. We nuke it after finding it and 776 * call Path_AddDir to add this new directory 777 * onto the existing search path. Once that's 778 * done, we restore the slash and triumphantly 779 * return the file name, knowing that should a 780 * file in this directory every be referenced 781 * again in such a manner, we will find it 782 * without having to do numerous numbers of 783 * access calls. Hurrah! 784 */ 785 cp = strrchr(file, '/'); 786 *cp = '\0'; 787 Path_AddDir(path, file); 788 *cp = '/'; 789 790 /* 791 * Save the modification time so if 792 * it's needed, we don't have to fetch it again. 793 */ 794 DEBUGF(DIR, ("Caching %s for %s\n", 795 Targ_FmtTime(stb.st_mtime), file)); 796 entry = Hash_CreateEntry(&mtimes, file, 797 (Boolean *)NULL); 798 Hash_SetValue(entry, 799 (void *)(long)stb.st_mtime); 800 nearmisses += 1; 801 return (file); 802 } else { 803 free(file); 804 } 805 } 806 807 DEBUGF(DIR, ("failed. ")); 808 809 if (checkedDot) { 810 /* 811 * Already checked by the given name, since . was in 812 * the path, so no point in proceeding... 813 */ 814 DEBUGF(DIR, ("Checked . already, returning NULL\n")); 815 return (NULL); 816 } 817 } 818 819 /* 820 * Didn't find it that way, either. Sigh. Phase 3. Add its directory 821 * onto the search path in any case, just in case, then look for the 822 * thing in the hash table. If we find it, grand. We return a new 823 * copy of the name. Otherwise we sadly return a NULL pointer. Sigh. 824 * Note that if the directory holding the file doesn't exist, this will 825 * do an extra search of the final directory on the path. Unless 826 * something weird happens, this search won't succeed and life will 827 * be groovy. 828 * 829 * Sigh. We cannot add the directory onto the search path because 830 * of this amusing case: 831 * $(INSTALLDIR)/$(FILE): $(FILE) 832 * 833 * $(FILE) exists in $(INSTALLDIR) but not in the current one. 834 * When searching for $(FILE), we will find it in $(INSTALLDIR) 835 * b/c we added it here. This is not good... 836 */ 837 DEBUGF(DIR, ("Looking for \"%s\"...", name)); 838 839 bigmisses += 1; 840 entry = Hash_FindEntry(&mtimes, name); 841 if (entry != NULL) { 842 DEBUGF(DIR, ("got it (in mtime cache)\n")); 843 return (estrdup(name)); 844 } else if (stat (name, &stb) == 0) { 845 entry = Hash_CreateEntry(&mtimes, name, (Boolean *)NULL); 846 DEBUGF(DIR, ("Caching %s for %s\n", 847 Targ_FmtTime(stb.st_mtime), name)); 848 Hash_SetValue(entry, (void *)(long)stb.st_mtime); 849 return (estrdup(name)); 850 } else { 851 DEBUGF(DIR, ("failed. Returning NULL\n")); 852 return (NULL); 853 } 854} 855 856/*- 857 *----------------------------------------------------------------------- 858 * Dir_FindHereOrAbove -- 859 * search for a path starting at a given directory and then working 860 * our way up towards the root. 861 * 862 * Input: 863 * here starting directory 864 * search_path the path we are looking for 865 * result the result of a successful search is placed here 866 * rlen the length of the result buffer 867 * (typically MAXPATHLEN + 1) 868 * 869 * Results: 870 * 0 on failure, 1 on success [in which case the found path is put 871 * in the result buffer]. 872 * 873 * Side Effects: 874 *----------------------------------------------------------------------- 875 */ 876int 877Dir_FindHereOrAbove(char *here, char *search_path, char *result, int rlen) 878{ 879 struct stat st; 880 char dirbase[MAXPATHLEN + 1], *db_end; 881 char try[MAXPATHLEN + 1], *try_end; 882 883 /* copy out our starting point */ 884 snprintf(dirbase, sizeof(dirbase), "%s", here); 885 db_end = dirbase + strlen(dirbase); 886 887 /* loop until we determine a result */ 888 while (1) { 889 /* try and stat(2) it ... */ 890 snprintf(try, sizeof(try), "%s/%s", dirbase, search_path); 891 if (stat(try, &st) != -1) { 892 /* 893 * Success! If we found a file, chop off 894 * the filename so we return a directory. 895 */ 896 if ((st.st_mode & S_IFMT) != S_IFDIR) { 897 try_end = try + strlen(try); 898 while (try_end > try && *try_end != '/') 899 try_end--; 900 if (try_end > try) 901 *try_end = 0; /* chop! */ 902 } 903 904 /* 905 * Done! 906 */ 907 snprintf(result, rlen, "%s", try); 908 return(1); 909 } 910 911 /* 912 * Nope, we didn't find it. If we used up dirbase we've 913 * reached the root and failed. 914 */ 915 if (db_end == dirbase) 916 break; /* Failed! */ 917 918 /* 919 * truncate dirbase from the end to move up a dir 920 */ 921 while (db_end > dirbase && *db_end != '/') 922 db_end--; 923 *db_end = 0; /* chop! */ 924 925 } /* while (1) */ 926 927 /* 928 * We failed... 929 */ 930 return(0); 931} 932 933/*- 934 *----------------------------------------------------------------------- 935 * Dir_MTime -- 936 * Find the modification time of the file described by gn along the 937 * search path dirSearchPath. 938 * 939 * Results: 940 * The modification time or 0 if it doesn't exist 941 * 942 * Side Effects: 943 * The modification time is placed in the node's mtime slot. 944 * If the node didn't have a path entry before, and Path_FindFile 945 * found one for it, the full name is placed in the path slot. 946 *----------------------------------------------------------------------- 947 */ 948int 949Dir_MTime(GNode *gn) 950{ 951 char *fullName; /* the full pathname of name */ 952 struct stat stb; /* buffer for finding the mod time */ 953 Hash_Entry *entry; 954 955 if (gn->type & OP_ARCHV) 956 return (Arch_MTime(gn)); 957 958 else if (gn->path == NULL) 959 fullName = Path_FindFile(gn->name, &dirSearchPath); 960 else 961 fullName = gn->path; 962 963 if (fullName == NULL) 964 fullName = estrdup(gn->name); 965 966 entry = Hash_FindEntry(&mtimes, fullName); 967 if (entry != NULL) { 968 /* 969 * Only do this once -- the second time folks are checking to 970 * see if the file was actually updated, so we need to 971 * actually go to the filesystem. 972 */ 973 DEBUGF(DIR, ("Using cached time %s for %s\n", 974 Targ_FmtTime((time_t)(long)Hash_GetValue(entry)), 975 fullName)); 976 stb.st_mtime = (time_t)(long)Hash_GetValue(entry); 977 Hash_DeleteEntry(&mtimes, entry); 978 } else if (stat(fullName, &stb) < 0) { 979 if (gn->type & OP_MEMBER) { 980 if (fullName != gn->path) 981 free(fullName); 982 return (Arch_MemMTime(gn)); 983 } else { 984 stb.st_mtime = 0; 985 } 986 } 987 if (fullName && gn->path == (char *)NULL) 988 gn->path = fullName; 989 990 gn->mtime = stb.st_mtime; 991 return (gn->mtime); 992} 993 994/*- 995 *----------------------------------------------------------------------- 996 * Path_AddDir -- 997 * Add the given name to the end of the given path. 998 * 999 * Results: 1000 * none 1001 * 1002 * Side Effects: 1003 * A structure is added to the list and the directory is 1004 * read and hashed. 1005 *----------------------------------------------------------------------- 1006 */ 1007struct Dir * 1008Path_AddDir(struct Path *path, const char *name) 1009{ 1010 Dir *d; /* pointer to new Path structure */ 1011 DIR *dir; /* for reading directory */ 1012 struct PathElement *pe; 1013 struct dirent *dp; /* entry in directory */ 1014 1015 /* check whether we know this directory */ 1016 TAILQ_FOREACH(d, &openDirectories, link) { 1017 if (strcmp(d->name, name) == 0) { 1018 /* Found it. */ 1019 if (path == NULL) 1020 return (d); 1021 1022 /* Check whether its already on the path. */ 1023 TAILQ_FOREACH(pe, path, link) { 1024 if (pe->dir == d) 1025 return (d); 1026 } 1027 /* Add it to the path */ 1028 d->refCount += 1; 1029 pe = emalloc(sizeof(*pe)); 1030 pe->dir = d; 1031 TAILQ_INSERT_TAIL(path, pe, link); 1032 return (d); 1033 } 1034 } 1035 1036 DEBUGF(DIR, ("Caching %s...", name)); 1037 1038 if ((dir = opendir(name)) == NULL) { 1039 DEBUGF(DIR, (" cannot open\n")); 1040 return (NULL); 1041 } 1042 1043 d = emalloc(sizeof(*d)); 1044 d->name = estrdup(name); 1045 d->hits = 0; 1046 d->refCount = 1; 1047 Hash_InitTable(&d->files, -1); 1048 1049 while ((dp = readdir(dir)) != NULL) { 1050#if defined(sun) && defined(d_ino) /* d_ino is a sunos4 #define for d_fileno */ 1051 /* 1052 * The sun directory library doesn't check for 1053 * a 0 inode (0-inode slots just take up space), 1054 * so we have to do it ourselves. 1055 */ 1056 if (dp->d_fileno == 0) 1057 continue; 1058#endif /* sun && d_ino */ 1059 1060 /* Skip the '.' and '..' entries by checking 1061 * for them specifically instead of assuming 1062 * readdir() reuturns them in that order when 1063 * first going through a directory. This is 1064 * needed for XFS over NFS filesystems since 1065 * SGI does not guarantee that these are the 1066 * first two entries returned from readdir(). 1067 */ 1068 if (ISDOT(dp->d_name) || ISDOTDOT(dp->d_name)) 1069 continue; 1070 1071 Hash_CreateEntry(&d->files, dp->d_name, (Boolean *)NULL); 1072 } 1073 closedir(dir); 1074 1075 if (path != NULL) { 1076 /* Add it to the path */ 1077 d->refCount += 1; 1078 pe = emalloc(sizeof(*pe)); 1079 pe->dir = d; 1080 TAILQ_INSERT_TAIL(path, pe, link); 1081 } 1082 1083 /* Add to list of all directories */ 1084 TAILQ_INSERT_TAIL(&openDirectories, d, link); 1085 1086 DEBUGF(DIR, ("done\n")); 1087 1088 return (d); 1089} 1090 1091/** 1092 * Path_Duplicate 1093 * Duplicate a path. Ups the reference count for the directories. 1094 */ 1095void 1096Path_Duplicate(struct Path *dst, const struct Path *src) 1097{ 1098 struct PathElement *ped, *pes; 1099 1100 TAILQ_FOREACH(pes, src, link) { 1101 ped = emalloc(sizeof(*ped)); 1102 ped->dir = pes->dir; 1103 ped->dir->refCount++; 1104 TAILQ_INSERT_TAIL(dst, ped, link); 1105 } 1106} 1107 1108/** 1109 * Path_MakeFlags 1110 * Make a string by taking all the directories in the given search 1111 * path and preceding them by the given flag. Used by the suffix 1112 * module to create variables for compilers based on suffix search 1113 * paths. 1114 * 1115 * Results: 1116 * The string mentioned above. Note that there is no space between 1117 * the given flag and each directory. The empty string is returned if 1118 * Things don't go well. 1119 */ 1120char * 1121Path_MakeFlags(const char *flag, const struct Path *path) 1122{ 1123 char *str; /* the string which will be returned */ 1124 char *tstr; /* the current directory preceded by 'flag' */ 1125 char *nstr; 1126 const struct PathElement *pe; 1127 1128 str = estrdup(""); 1129 1130 TAILQ_FOREACH(pe, path, link) { 1131 tstr = str_concat(flag, pe->dir->name, 0); 1132 nstr = str_concat(str, tstr, STR_ADDSPACE); 1133 free(str); 1134 free(tstr); 1135 str = nstr; 1136 } 1137 1138 return (str); 1139} 1140 1141/** 1142 * Path_Clear 1143 * 1144 * Destroy a path. This decrements the reference counts of all 1145 * directories of this path and, if a reference count goes 0, 1146 * destroys the directory object. 1147 */ 1148void 1149Path_Clear(struct Path *path) 1150{ 1151 struct PathElement *pe; 1152 1153 while ((pe = TAILQ_FIRST(path)) != NULL) { 1154 pe->dir->refCount--; 1155 TAILQ_REMOVE(path, pe, link); 1156 if (pe->dir->refCount == 0) { 1157 TAILQ_REMOVE(&openDirectories, pe->dir, link); 1158 Hash_DeleteTable(&pe->dir->files); 1159 free(pe->dir->name); 1160 free(pe->dir); 1161 } 1162 free(pe); 1163 } 1164} 1165 1166/** 1167 * Path_Concat 1168 * 1169 * Concatenate two paths, adding the second to the end of the first. 1170 * Make sure to avoid duplicates. 1171 * 1172 * Side Effects: 1173 * Reference counts for added dirs are upped. 1174 */ 1175void 1176Path_Concat(struct Path *path1, const struct Path *path2) 1177{ 1178 struct PathElement *p1, *p2; 1179 1180 TAILQ_FOREACH(p2, path2, link) { 1181 TAILQ_FOREACH(p1, path1, link) { 1182 if (p1->dir == p2->dir) 1183 break; 1184 } 1185 if (p1 == NULL) { 1186 p1 = emalloc(sizeof(*p1)); 1187 p1->dir = p2->dir; 1188 p1->dir->refCount++; 1189 TAILQ_INSERT_TAIL(path1, p1, link); 1190 } 1191 } 1192} 1193 1194/********** DEBUG INFO **********/ 1195void 1196Dir_PrintDirectories(void) 1197{ 1198 const Dir *d; 1199 1200 printf("#*** Directory Cache:\n"); 1201 printf("# Stats: %d hits %d misses %d near misses %d losers (%d%%)\n", 1202 hits, misses, nearmisses, bigmisses, 1203 (hits + bigmisses + nearmisses ? 1204 hits * 100 / (hits + bigmisses + nearmisses) : 0)); 1205 printf("# %-20s referenced\thits\n", "directory"); 1206 TAILQ_FOREACH(d, &openDirectories, link) 1207 printf("# %-20s %10d\t%4d\n", d->name, d->refCount, d->hits); 1208} 1209 1210void 1211Path_Print(const struct Path *path) 1212{ 1213 const struct PathElement *p; 1214 1215 TAILQ_FOREACH(p, path, link) 1216 printf("%s ", p->dir->name); 1217} 1218