1 /* $OpenBSD: make.c,v 1.82 2020/01/26 12:41:21 espie Exp $ */ 2 /* $NetBSD: make.c,v 1.10 1996/11/06 17:59:15 christos Exp $ */ 3 4 /* 5 * Copyright (c) 1988, 1989, 1990, 1993 6 * The Regents of the University of California. All rights reserved. 7 * Copyright (c) 1989 by Berkeley Softworks 8 * All rights reserved. 9 * 10 * This code is derived from software contributed to Berkeley by 11 * Adam de Boor. 12 * 13 * Redistribution and use in source and binary forms, with or without 14 * modification, are permitted provided that the following conditions 15 * are met: 16 * 1. Redistributions of source code must retain the above copyright 17 * notice, this list of conditions and the following disclaimer. 18 * 2. Redistributions in binary form must reproduce the above copyright 19 * notice, this list of conditions and the following disclaimer in the 20 * documentation and/or other materials provided with the distribution. 21 * 3. Neither the name of the University nor the names of its contributors 22 * may be used to endorse or promote products derived from this software 23 * without specific prior written permission. 24 * 25 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 26 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 27 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 28 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 29 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 30 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 31 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 32 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 33 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 34 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 35 * SUCH DAMAGE. 36 */ 37 38 /*- 39 * make.c -- 40 * The functions which perform the examination of targets and 41 * their suitability for creation 42 * 43 * Interface: 44 * Make_Run Initialize things for the module and recreate 45 * whatever needs recreating. Returns true if 46 * work was (or would have been) done and 47 * false 48 * otherwise. 49 * 50 * Make_Update Update all parents of a given child. Performs 51 * various bookkeeping chores like finding the 52 * youngest child of the parent, filling 53 * the IMPSRC local variable, etc. It will 54 * place the parent on the to_build queue if it 55 * should be. 56 * 57 */ 58 59 #include <limits.h> 60 #include <signal.h> 61 #include <stddef.h> 62 #include <stdint.h> 63 #include <stdio.h> 64 #include <stdlib.h> 65 #include <string.h> 66 #include <ohash.h> 67 #include "config.h" 68 #include "defines.h" 69 #include "dir.h" 70 #include "job.h" 71 #include "suff.h" 72 #include "var.h" 73 #include "error.h" 74 #include "expandchildren.h" 75 #include "make.h" 76 #include "gnode.h" 77 #include "extern.h" 78 #include "timestamp.h" 79 #include "engine.h" 80 #include "lst.h" 81 #include "targ.h" 82 #include "targequiv.h" 83 #include "garray.h" 84 #include "memory.h" 85 86 /* what gets added each time. Kept as one static array so that it doesn't 87 * get resized every time. 88 */ 89 static struct growableArray examine; 90 /* The current fringe of the graph. These are nodes which await examination by 91 * MakeOODate. It is added to by Make_Update and subtracted from by 92 * MakeStartJobs */ 93 static struct growableArray to_build; 94 95 /* Hold back on nodes where equivalent stuff is already building... */ 96 static struct growableArray heldBack; 97 98 static struct ohash targets; /* stuff we must build */ 99 100 static void MakeAddChild(void *, void *); 101 static void MakeHandleUse(void *, void *); 102 static bool MakeStartJobs(void); 103 static void MakePrintStatus(void *); 104 105 /* Cycle detection functions */ 106 static bool targets_contain_cycles(void); 107 static void print_unlink_cycle(struct growableArray *, GNode *); 108 static void break_and_print_cycles(Lst); 109 static GNode *find_cycle(Lst, struct growableArray *); 110 111 static bool try_to_make_node(GNode *); 112 static void add_targets_to_make(Lst); 113 114 static bool has_predecessor_left_to_build(GNode *); 115 static void requeue_successors(GNode *); 116 static void random_setup(void); 117 118 static bool randomize_queue; 119 long random_delay = 0; 120 121 bool 122 nothing_left_to_build() 123 { 124 return Array_IsEmpty(&to_build); 125 } 126 127 static void 128 random_setup() 129 { 130 randomize_queue = Var_Definedi("RANDOM_ORDER", NULL); 131 132 /* no random delay in the new engine for now */ 133 #if 0 134 if (Var_Definedi("RANDOM_DELAY", NULL)) 135 random_delay = strtonum(Var_Value("RANDOM_DELAY"), 0, 1000, 136 NULL) * 1000000; 137 #endif 138 139 } 140 141 static void 142 randomize_garray(struct growableArray *g) 143 { 144 /* This is a fairly standard algorithm to randomize an array. */ 145 unsigned int i, v; 146 GNode *e; 147 148 for (i = g->n; i > 0; i--) { 149 v = arc4random_uniform(i); 150 if (v == i-1) 151 continue; 152 else { 153 e = g->a[i-1]; 154 g->a[i-1] = g->a[v]; 155 g->a[v] = e; 156 } 157 } 158 } 159 160 static bool 161 has_predecessor_left_to_build(GNode *gn) 162 { 163 LstNode ln; 164 165 if (Lst_IsEmpty(&gn->predecessors)) 166 return false; 167 168 169 for (ln = Lst_First(&gn->predecessors); ln != NULL; ln = Lst_Adv(ln)) { 170 GNode *pgn = Lst_Datum(ln); 171 172 if (pgn->must_make && pgn->built_status == UNKNOWN) { 173 if (DEBUG(MAKE)) 174 printf("predecessor %s not made yet.\n", 175 pgn->name); 176 return true; 177 } 178 } 179 return false; 180 } 181 182 static void 183 requeue_successors(GNode *gn) 184 { 185 LstNode ln; 186 /* Deal with successor nodes. If any is marked for making and has an 187 * children_left count of 0, has not been made and isn't in the 188 * examination queue, it means we need to place it in the queue as 189 * it restrained itself before. */ 190 for (ln = Lst_First(&gn->successors); ln != NULL; ln = Lst_Adv(ln)) { 191 GNode *succ = Lst_Datum(ln); 192 193 if (succ->must_make && succ->children_left == 0 194 && succ->built_status == UNKNOWN) 195 Array_PushNew(&to_build, succ); 196 } 197 } 198 199 static void 200 requeue(GNode *gn) 201 { 202 /* this is where we go inside the array and move things around */ 203 unsigned int i, j; 204 205 for (i = 0, j = 0; i < heldBack.n; i++, j++) { 206 if (heldBack.a[i]->watched == gn) { 207 j--; 208 heldBack.a[i]->built_status = UNKNOWN; 209 if (DEBUG(HELDJOBS)) 210 printf("%s finished, releasing: %s\n", 211 gn->name, heldBack.a[i]->name); 212 Array_Push(&to_build, heldBack.a[i]); 213 continue; 214 } 215 heldBack.a[j] = heldBack.a[i]; 216 } 217 heldBack.n = j; 218 } 219 220 /*- 221 *----------------------------------------------------------------------- 222 * Make_Update -- 223 * Perform update on the parents of a node. Used by JobFinish once 224 * a node has been dealt with and by MakeStartJobs if it finds an 225 * up-to-date node. 226 * 227 * Results: 228 * Always returns 0 229 * 230 * Side Effects: 231 * The children_left field of pgn is decremented and pgn may be placed on 232 * the to_build queue if this field becomes 0. 233 * 234 * If the child got built, the parent's child_rebuilt field will be set to 235 * true 236 *----------------------------------------------------------------------- 237 */ 238 void 239 Make_Update(GNode *cgn) /* the child node */ 240 { 241 GNode *pgn; /* the parent node */ 242 LstNode ln; /* Element in parents list */ 243 244 /* 245 * If the child was actually made, see what its modification time is 246 * now -- some rules won't actually update the file. If the file still 247 * doesn't exist, make its mtime now. 248 */ 249 if (cgn->built_status != UPTODATE) { 250 /* 251 * This is what Make does and it's actually a good thing, as it 252 * allows rules like 253 * 254 * cmp -s y.tab.h parse.h || cp y.tab.h parse.h 255 * 256 * to function as intended. Unfortunately, thanks to the 257 * stateless nature of NFS, there are times when the 258 * modification time of a file created on a remote machine 259 * will not be modified before the local stat() implied by 260 * the Dir_MTime occurs, thus leading us to believe that the 261 * file is unchanged, wreaking havoc with files that depend 262 * on this one. 263 */ 264 if (noExecute || is_out_of_date(Dir_MTime(cgn))) 265 clock_gettime(CLOCK_REALTIME, &cgn->mtime); 266 if (DEBUG(MAKE)) 267 printf("update time: %s\n", 268 time_to_string(&cgn->mtime)); 269 } 270 271 requeue(cgn); 272 /* SIB: this is where I should mark the build as finished */ 273 for (ln = Lst_First(&cgn->parents); ln != NULL; ln = Lst_Adv(ln)) { 274 pgn = Lst_Datum(ln); 275 /* SIB: there should be a siblings loop there */ 276 pgn->children_left--; 277 if (pgn->must_make) { 278 if (DEBUG(MAKE)) 279 printf("%s--=%d ", 280 pgn->name, pgn->children_left); 281 282 if ( ! (cgn->type & OP_USE)) { 283 if (cgn->built_status == REBUILT) 284 pgn->child_rebuilt = true; 285 (void)Make_TimeStamp(pgn, cgn); 286 } 287 if (pgn->children_left == 0) { 288 /* 289 * Queue the node up -- any yet-to-build 290 * predecessors will be dealt with in 291 * MakeStartJobs. 292 */ 293 if (DEBUG(MAKE)) 294 printf("QUEUING "); 295 Array_Push(&to_build, pgn); 296 } else if (pgn->children_left < 0) { 297 Error("Child %s discovered graph cycles through %s", cgn->name, pgn->name); 298 } 299 } 300 } 301 if (DEBUG(MAKE)) 302 printf("\n"); 303 requeue_successors(cgn); 304 } 305 306 static bool 307 try_to_make_node(GNode *gn) 308 { 309 if (DEBUG(MAKE)) 310 printf("Examining %s...", gn->name); 311 312 if (gn->built_status == HELDBACK) { 313 if (DEBUG(HELDJOBS)) 314 printf("%s already held back ???\n", gn->name); 315 return false; 316 } 317 318 if (gn->children_left != 0) { 319 if (DEBUG(MAKE)) 320 printf(" Requeuing (%d)\n", gn->children_left); 321 add_targets_to_make(&gn->children); 322 Array_Push(&to_build, gn); 323 return false; 324 } 325 if (has_been_built(gn)) { 326 if (DEBUG(MAKE)) 327 printf(" already made\n"); 328 return false; 329 } 330 if (has_predecessor_left_to_build(gn)) { 331 if (DEBUG(MAKE)) 332 printf(" Dropping for now\n"); 333 return false; 334 } 335 336 /* SIB: this is where there should be a siblings loop */ 337 if (gn->children_left != 0) { 338 if (DEBUG(MAKE)) 339 printf(" Requeuing (after deps: %d)\n", 340 gn->children_left); 341 add_targets_to_make(&gn->children); 342 return false; 343 } 344 /* this is where we hold back nodes */ 345 if (gn->groupling != NULL) { 346 GNode *gn2; 347 for (gn2 = gn->groupling; gn2 != gn; gn2 = gn2->groupling) 348 if (gn2->built_status == BUILDING) { 349 gn->watched = gn2; 350 gn->built_status = HELDBACK; 351 if (DEBUG(HELDJOBS)) 352 printf("Holding back job %s, " 353 "groupling to %s\n", 354 gn->name, gn2->name); 355 Array_Push(&heldBack, gn); 356 return false; 357 } 358 } 359 if (gn->sibling != gn) { 360 GNode *gn2; 361 for (gn2 = gn->sibling; gn2 != gn; gn2 = gn2->sibling) 362 if (gn2->built_status == BUILDING) { 363 gn->watched = gn2; 364 gn->built_status = HELDBACK; 365 if (DEBUG(HELDJOBS)) 366 printf("Holding back job %s, " 367 "sibling to %s\n", 368 gn->name, gn2->name); 369 Array_Push(&heldBack, gn); 370 return false; 371 } 372 } 373 if (Make_OODate(gn)) { 374 if (DEBUG(MAKE)) 375 printf("out-of-date\n"); 376 if (queryFlag) 377 return true; 378 /* SIB: this is where commands should get prepared */ 379 Make_DoAllVar(gn); 380 if (node_find_valid_commands(gn)) { 381 if (touchFlag) 382 Job_Touch(gn); 383 else 384 Job_Make(gn); 385 } else 386 node_failure(gn); 387 } else { 388 if (DEBUG(MAKE)) 389 printf("up-to-date\n"); 390 gn->built_status = UPTODATE; 391 392 Make_Update(gn); 393 } 394 return false; 395 } 396 397 /* 398 *----------------------------------------------------------------------- 399 * MakeStartJobs -- 400 * Start as many jobs as possible. 401 * 402 * Results: 403 * If the query flag was given to pmake, no job will be started, 404 * but as soon as an out-of-date target is found, this function 405 * returns true. At all other times, this function returns false. 406 * 407 * Side Effects: 408 * Nodes are removed from the to_build queue and job table slots 409 * are filled. 410 *----------------------------------------------------------------------- 411 */ 412 static bool 413 MakeStartJobs(void) 414 { 415 GNode *gn; 416 417 while (can_start_job() && (gn = Array_Pop(&to_build)) != NULL) { 418 if (try_to_make_node(gn)) 419 return true; 420 } 421 return false; 422 } 423 424 static void 425 MakePrintStatus(void *gnp) 426 { 427 GNode *gn = gnp; 428 if (gn->built_status == UPTODATE) { 429 printf("`%s' is up to date.\n", gn->name); 430 } else if (gn->children_left != 0) { 431 printf("`%s' not remade because of errors.\n", gn->name); 432 } 433 } 434 435 static void 436 MakeAddChild(void *to_addp, void *ap) 437 { 438 GNode *gn = to_addp; 439 struct growableArray *a = ap; 440 441 if (!gn->must_make && !(gn->type & OP_USE)) 442 Array_Push(a, gn); 443 } 444 445 static void 446 MakeHandleUse(void *cgnp, void *pgnp) 447 { 448 GNode *cgn = cgnp; 449 GNode *pgn = pgnp; 450 451 if (cgn->type & OP_USE) 452 Make_HandleUse(cgn, pgn); 453 } 454 455 /* Add stuff to the to_build queue. we try to sort things so that stuff 456 * that can be done directly is done right away. This won't be perfect, 457 * since some dependencies are only discovered later (e.g., SuffFindDeps). 458 */ 459 static void 460 add_targets_to_make(Lst todo) 461 { 462 GNode *gn; 463 464 unsigned int slot; 465 466 AppendList2Array(todo, &examine); 467 468 while ((gn = Array_Pop(&examine)) != NULL) { 469 if (gn->must_make) /* already known */ 470 continue; 471 gn->must_make = true; 472 473 slot = ohash_qlookup(&targets, gn->name); 474 if (!ohash_find(&targets, slot)) 475 ohash_insert(&targets, slot, gn); 476 477 478 look_harder_for_target(gn); 479 kludge_look_harder_for_target(gn); 480 /* 481 * Apply any .USE rules before looking for implicit 482 * dependencies to make sure everything that should have 483 * commands has commands ... 484 */ 485 Lst_ForEach(&gn->children, MakeHandleUse, gn); 486 Suff_FindDeps(gn); 487 expand_all_children(gn); 488 489 if (gn->children_left != 0) { 490 if (DEBUG(MAKE)) 491 printf("%s: not queuing (%d children left to build)\n", 492 gn->name, gn->children_left); 493 Lst_ForEach(&gn->children, MakeAddChild, 494 &examine); 495 } else { 496 if (DEBUG(MAKE)) 497 printf("%s: queuing\n", gn->name); 498 Array_Push(&to_build, gn); 499 } 500 } 501 if (randomize_queue) 502 randomize_garray(&to_build); 503 } 504 505 void 506 Make_Init() 507 { 508 /* wild guess at initial sizes */ 509 Array_Init(&to_build, 500); 510 Array_Init(&examine, 150); 511 Array_Init(&heldBack, 100); 512 ohash_init(&targets, 10, &gnode_info); 513 } 514 515 /*- 516 *----------------------------------------------------------------------- 517 * Make_Run -- 518 * Initialize the nodes to remake and the list of nodes which are 519 * ready to be made by doing a breadth-first traversal of the graph 520 * starting from the nodes in the given list. Once this traversal 521 * is finished, all the 'leaves' of the graph are in the to_build 522 * queue. 523 * Using this queue and the Job module, work back up the graph, 524 * calling on MakeStartJobs to keep the job table as full as 525 * possible. 526 * 527 * Side Effects: 528 * The must_make field of all nodes involved in the creation of the given 529 * targets is set to 1. The to_build list is set to contain all the 530 * 'leaves' of these subgraphs. 531 *----------------------------------------------------------------------- 532 */ 533 void 534 Make_Run(Lst targs, bool *has_errors, bool *out_of_date) 535 { 536 if (DEBUG(PARALLEL)) 537 random_setup(); 538 539 add_targets_to_make(targs); 540 if (queryFlag) { 541 /* 542 * We wouldn't do any work unless we could start some jobs in 543 * the next loop... (we won't actually start any, of course, 544 * this is just to see if any of the targets was out of date) 545 */ 546 if (MakeStartJobs()) 547 *out_of_date = true; 548 } else { 549 /* 550 * Initialization. At the moment, no jobs are running and until 551 * some get started, nothing will happen since the remaining 552 * upward traversal of the graph is performed by the routines 553 * in job.c upon the finishing of a job. So we fill the Job 554 * table as much as we can before going into our loop. 555 */ 556 (void)MakeStartJobs(); 557 } 558 559 /* 560 * Main Loop: The idea here is that the ending of jobs will take 561 * care of the maintenance of data structures and the waiting for output 562 * will cause us to be idle most of the time while our children run as 563 * much as possible. Because the job table is kept as full as possible, 564 * the only time when it will be empty is when all the jobs which need 565 * running have been run, so that is the end condition of this loop. 566 * Note that the Job module will exit if there were any errors unless 567 * the keepgoing flag was given. 568 */ 569 while (!Job_Empty()) { 570 handle_running_jobs(); 571 (void)MakeStartJobs(); 572 } 573 574 if (errorJobs != NULL) 575 *has_errors = true; 576 577 /* 578 * Print the final status of each target. E.g. if it wasn't made 579 * because some inferior reported an error. 580 */ 581 if (targets_contain_cycles()) { 582 break_and_print_cycles(targs); 583 *has_errors = true; 584 } 585 Lst_Every(targs, MakePrintStatus); 586 } 587 588 /* round-about detection: assume make is bug-free, if there are targets 589 * that have not been touched, it means they never were reached, so we can 590 * look for a cycle 591 */ 592 static bool 593 targets_contain_cycles(void) 594 { 595 GNode *gn; 596 unsigned int i; 597 bool cycle = false; 598 bool first = true; 599 600 for (gn = ohash_first(&targets, &i); gn != NULL; 601 gn = ohash_next(&targets, &i)) { 602 if (has_been_built(gn)) 603 continue; 604 cycle = true; 605 if (first) 606 printf("Error target(s) unaccounted for: "); 607 printf("%s ", gn->name); 608 first = false; 609 } 610 if (!first) 611 printf("\n"); 612 return cycle; 613 } 614 615 static void 616 print_unlink_cycle(struct growableArray *l, GNode *c) 617 { 618 LstNode ln; 619 GNode *gn = NULL; 620 unsigned int i; 621 622 printf("Cycle found: "); 623 624 for (i = 0; i != l->n; i++) { 625 gn = l->a[i]; 626 if (gn == c) 627 printf("("); 628 printf("%s -> ", gn->name); 629 } 630 printf("%s)\n", c->name); 631 assert(gn); 632 633 /* So the first element is tied to our node, find and kill the link */ 634 for (ln = Lst_First(&gn->children); ln != NULL; ln = Lst_Adv(ln)) { 635 GNode *gn2 = Lst_Datum(ln); 636 if (gn2 == c) { 637 Lst_Remove(&gn->children, ln); 638 return; 639 } 640 } 641 /* this shouldn't happen ever */ 642 assert(0); 643 } 644 645 /* each call to find_cycle records a cycle in cycle, to break at node c. 646 * this will stop eventually. 647 */ 648 static void 649 break_and_print_cycles(Lst t) 650 { 651 struct growableArray cycle; 652 653 Array_Init(&cycle, 16); /* cycles are generally shorter */ 654 while (1) { 655 GNode *c; 656 657 Array_Reset(&cycle); 658 c = find_cycle(t, &cycle); 659 if (c) 660 print_unlink_cycle(&cycle, c); 661 else 662 break; 663 } 664 free(cycle.a); 665 } 666 667 668 static GNode * 669 find_cycle(Lst l, struct growableArray *cycle) 670 { 671 LstNode ln; 672 673 for (ln = Lst_First(l); ln != NULL; ln = Lst_Adv(ln)) { 674 GNode *gn = Lst_Datum(ln); 675 if (gn->in_cycle) { 676 /* we should print the cycle and not do more */ 677 return gn; 678 } 679 680 if (gn->built_status == UPTODATE) 681 continue; 682 if (gn->children_left != 0) { 683 GNode *c; 684 685 gn->in_cycle = true; 686 Array_Push(cycle, gn); 687 c = find_cycle(&gn->children, cycle); 688 gn->in_cycle = false; 689 if (c) 690 return c; 691 Array_Pop(cycle); 692 } 693 } 694 return NULL; 695 } 696