1 /* $OpenBSD: make.c,v 1.73 2017/06/22 17:09:10 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 context variable, etc. It will 54 * place the parent on the toBeMade 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 "make.h" 75 #include "gnode.h" 76 #include "extern.h" 77 #include "timestamp.h" 78 #include "engine.h" 79 #include "lst.h" 80 #include "targ.h" 81 #include "targequiv.h" 82 #include "garray.h" 83 #include "memory.h" 84 85 /* what gets added each time. Kept as one static array so that it doesn't 86 * get resized every time. 87 */ 88 static struct growableArray examine; 89 /* The current fringe of the graph. These are nodes which await examination by 90 * MakeOODate. It is added to by Make_Update and subtracted from by 91 * MakeStartJobs */ 92 static struct growableArray toBeMade; 93 94 /* Hold back on nodes where equivalent stuff is already building... */ 95 static struct growableArray heldBack; 96 97 static struct ohash targets; /* stuff we must build */ 98 99 static void MakeAddChild(void *, void *); 100 static void MakeHandleUse(void *, void *); 101 static bool MakeStartJobs(void); 102 static void MakePrintStatus(void *); 103 104 /* Cycle detection functions */ 105 static bool targets_contain_cycles(void); 106 static void print_unlink_cycle(struct growableArray *, GNode *); 107 static void break_and_print_cycles(Lst); 108 static GNode *find_cycle(Lst, struct growableArray *); 109 110 static bool try_to_make_node(GNode *); 111 static void add_targets_to_make(Lst); 112 113 static bool has_unmade_predecessor(GNode *); 114 static void requeue_successors(GNode *); 115 static void random_setup(void); 116 117 static bool randomize_queue; 118 long random_delay = 0; 119 120 bool 121 no_jobs_left() 122 { 123 return Array_IsEmpty(&toBeMade); 124 } 125 126 static void 127 random_setup() 128 { 129 randomize_queue = Var_Definedi("RANDOM_ORDER", NULL); 130 131 /* no random delay in the new engine for now */ 132 #if 0 133 if (Var_Definedi("RANDOM_DELAY", NULL)) 134 random_delay = strtonum(Var_Value("RANDOM_DELAY"), 0, 1000, 135 NULL) * 1000000; 136 #endif 137 138 } 139 140 static void 141 randomize_garray(struct growableArray *g) 142 { 143 /* This is a fairly standard algorithm to randomize an array. */ 144 unsigned int i, v; 145 GNode *e; 146 147 for (i = g->n; i > 0; i--) { 148 v = arc4random_uniform(i); 149 if (v == i-1) 150 continue; 151 else { 152 e = g->a[i-1]; 153 g->a[i-1] = g->a[v]; 154 g->a[v] = e; 155 } 156 } 157 } 158 159 static bool 160 has_unmade_predecessor(GNode *gn) 161 { 162 LstNode ln; 163 164 if (Lst_IsEmpty(&gn->preds)) 165 return false; 166 167 168 for (ln = Lst_First(&gn->preds); ln != NULL; ln = Lst_Adv(ln)) { 169 GNode *pgn = Lst_Datum(ln); 170 171 if (pgn->must_make && pgn->built_status == UNKNOWN) { 172 if (DEBUG(MAKE)) 173 printf("predecessor %s not made yet.\n", 174 pgn->name); 175 return true; 176 } 177 } 178 return false; 179 } 180 181 static void 182 requeue_successors(GNode *gn) 183 { 184 LstNode ln; 185 /* Deal with successor nodes. If any is marked for making and has an 186 * unmade count of 0, has not been made and isn't in the examination 187 * queue, it means we need to place it in the queue as it restrained 188 * itself before. */ 189 for (ln = Lst_First(&gn->successors); ln != NULL; ln = Lst_Adv(ln)) { 190 GNode *succ = Lst_Datum(ln); 191 192 if (succ->must_make && succ->unmade == 0 193 && succ->built_status == UNKNOWN) 194 Array_PushNew(&toBeMade, succ); 195 } 196 } 197 198 static void 199 requeue(GNode *gn) 200 { 201 /* this is where we go inside the array and move things around */ 202 unsigned int i, j; 203 204 for (i = 0, j = 0; i < heldBack.n; i++, j++) { 205 if (heldBack.a[i]->watched == gn) { 206 j--; 207 heldBack.a[i]->built_status = UNKNOWN; 208 if (DEBUG(HELDJOBS)) 209 printf("%s finished, releasing: %s\n", 210 gn->name, heldBack.a[i]->name); 211 Array_Push(&toBeMade, heldBack.a[i]); 212 continue; 213 } 214 heldBack.a[j] = heldBack.a[i]; 215 } 216 heldBack.n = j; 217 } 218 219 /*- 220 *----------------------------------------------------------------------- 221 * Make_Update -- 222 * Perform update on the parents of a node. Used by JobFinish once 223 * a node has been dealt with and by MakeStartJobs if it finds an 224 * up-to-date node. 225 * 226 * Results: 227 * Always returns 0 228 * 229 * Side Effects: 230 * The unmade field of pgn is decremented and pgn may be placed on 231 * the toBeMade queue if this field becomes 0. 232 * 233 * If the child was made, the parent's childMade field will be set to 234 * true 235 *----------------------------------------------------------------------- 236 */ 237 void 238 Make_Update(GNode *cgn) /* the child node */ 239 { 240 GNode *pgn; /* the parent node */ 241 LstNode ln; /* Element in parents list */ 242 243 /* 244 * If the child was actually made, see what its modification time is 245 * now -- some rules won't actually update the file. If the file still 246 * doesn't exist, make its mtime now. 247 */ 248 if (cgn->built_status != UPTODATE) { 249 /* 250 * This is what Make does and it's actually a good thing, as it 251 * allows rules like 252 * 253 * cmp -s y.tab.h parse.h || cp y.tab.h parse.h 254 * 255 * to function as intended. Unfortunately, thanks to the 256 * stateless nature of NFS, there are times when the 257 * modification time of a file created on a remote machine 258 * will not be modified before the local stat() implied by 259 * the Dir_MTime occurs, thus leading us to believe that the 260 * file is unchanged, wreaking havoc with files that depend 261 * on this one. 262 */ 263 if (noExecute || is_out_of_date(Dir_MTime(cgn))) 264 clock_gettime(CLOCK_REALTIME, &cgn->mtime); 265 if (DEBUG(MAKE)) 266 printf("update time: %s\n", 267 time_to_string(&cgn->mtime)); 268 } 269 270 requeue(cgn); 271 /* SIB: this is where I should mark the build as finished */ 272 for (ln = Lst_First(&cgn->parents); ln != NULL; ln = Lst_Adv(ln)) { 273 pgn = Lst_Datum(ln); 274 /* SIB: there should be a siblings loop there */ 275 pgn->unmade--; 276 if (pgn->must_make) { 277 if (DEBUG(MAKE)) 278 printf("%s--=%d ", 279 pgn->name, pgn->unmade); 280 281 if ( ! (cgn->type & (OP_EXEC|OP_USE))) { 282 if (cgn->built_status == MADE) 283 pgn->childMade = true; 284 (void)Make_TimeStamp(pgn, cgn); 285 } 286 if (pgn->unmade == 0) { 287 /* 288 * Queue the node up -- any unmade 289 * predecessors will be dealt with in 290 * MakeStartJobs. 291 */ 292 if (DEBUG(MAKE)) 293 printf("QUEUING "); 294 Array_Push(&toBeMade, pgn); 295 } else if (pgn->unmade < 0) { 296 Error("Child %s discovered graph cycles through %s", cgn->name, pgn->name); 297 } 298 } 299 } 300 if (DEBUG(MAKE)) 301 printf("\n"); 302 requeue_successors(cgn); 303 } 304 305 static bool 306 try_to_make_node(GNode *gn) 307 { 308 if (DEBUG(MAKE)) 309 printf("Examining %s...", gn->name); 310 311 if (gn->built_status == HELDBACK) { 312 if (DEBUG(HELDJOBS)) 313 printf("%s already held back ???\n", gn->name); 314 return false; 315 } 316 317 if (gn->unmade != 0) { 318 if (DEBUG(MAKE)) 319 printf(" Requeuing (%d)\n", gn->unmade); 320 add_targets_to_make(&gn->children); 321 Array_Push(&toBeMade, gn); 322 return false; 323 } 324 if (has_been_built(gn)) { 325 if (DEBUG(MAKE)) 326 printf(" already made\n"); 327 return false; 328 } 329 if (has_unmade_predecessor(gn)) { 330 if (DEBUG(MAKE)) 331 printf(" Dropping for now\n"); 332 return false; 333 } 334 335 /* SIB: this is where there should be a siblings loop */ 336 if (gn->unmade != 0) { 337 if (DEBUG(MAKE)) 338 printf(" Requeuing (after deps: %d)\n", gn->unmade); 339 add_targets_to_make(&gn->children); 340 return false; 341 } 342 /* this is where we hold back nodes */ 343 if (gn->groupling != NULL) { 344 GNode *gn2; 345 for (gn2 = gn->groupling; gn2 != gn; gn2 = gn2->groupling) 346 if (gn2->built_status == BUILDING) { 347 gn->watched = gn2; 348 gn->built_status = HELDBACK; 349 if (DEBUG(HELDJOBS)) 350 printf("Holding back job %s, " 351 "groupling to %s\n", 352 gn->name, gn2->name); 353 Array_Push(&heldBack, gn); 354 return false; 355 } 356 } 357 if (gn->sibling != gn) { 358 GNode *gn2; 359 for (gn2 = gn->sibling; gn2 != gn; gn2 = gn2->sibling) 360 if (gn2->built_status == BUILDING) { 361 gn->watched = gn2; 362 gn->built_status = HELDBACK; 363 if (DEBUG(HELDJOBS)) 364 printf("Holding back job %s, " 365 "sibling to %s\n", 366 gn->name, gn2->name); 367 Array_Push(&heldBack, gn); 368 return false; 369 } 370 } 371 if (Make_OODate(gn)) { 372 if (DEBUG(MAKE)) 373 printf("out-of-date\n"); 374 if (queryFlag) 375 return true; 376 /* SIB: this is where commands should get prepared */ 377 Make_DoAllVar(gn); 378 Job_Make(gn); 379 } else { 380 if (DEBUG(MAKE)) 381 printf("up-to-date\n"); 382 gn->built_status = UPTODATE; 383 if (gn->type & OP_JOIN) { 384 /* 385 * Even for an up-to-date .JOIN node, we need it 386 * to have its context variables so references 387 * to it get the correct value for .TARGET when 388 * building up the context variables of its 389 * parent(s)... 390 */ 391 Make_DoAllVar(gn); 392 } 393 394 Make_Update(gn); 395 } 396 return false; 397 } 398 399 /* 400 *----------------------------------------------------------------------- 401 * MakeStartJobs -- 402 * Start as many jobs as possible. 403 * 404 * Results: 405 * If the query flag was given to pmake, no job will be started, 406 * but as soon as an out-of-date target is found, this function 407 * returns true. At all other times, this function returns false. 408 * 409 * Side Effects: 410 * Nodes are removed from the toBeMade queue and job table slots 411 * are filled. 412 *----------------------------------------------------------------------- 413 */ 414 static bool 415 MakeStartJobs(void) 416 { 417 GNode *gn; 418 419 while (can_start_job() && (gn = Array_Pop(&toBeMade)) != NULL) { 420 if (try_to_make_node(gn)) 421 return true; 422 } 423 return false; 424 } 425 426 static void 427 MakePrintStatus(void *gnp) 428 { 429 GNode *gn = gnp; 430 if (gn->built_status == UPTODATE) { 431 printf("`%s' is up to date.\n", gn->name); 432 } else if (gn->unmade != 0) { 433 printf("`%s' not remade because of errors.\n", gn->name); 434 } 435 } 436 437 static void 438 MakeAddChild(void *to_addp, void *ap) 439 { 440 GNode *gn = to_addp; 441 struct growableArray *a = ap; 442 443 if (!gn->must_make && !(gn->type & OP_USE)) 444 Array_Push(a, gn); 445 } 446 447 static void 448 MakeHandleUse(void *cgnp, void *pgnp) 449 { 450 GNode *cgn = cgnp; 451 GNode *pgn = pgnp; 452 453 if (cgn->type & OP_USE) 454 Make_HandleUse(cgn, pgn); 455 } 456 457 /* Add stuff to the toBeMade queue. we try to sort things so that stuff 458 * that can be done directly is done right away. This won't be perfect, 459 * since some dependencies are only discovered later (e.g., SuffFindDeps). 460 */ 461 static void 462 add_targets_to_make(Lst todo) 463 { 464 GNode *gn; 465 466 unsigned int slot; 467 468 AppendList2Array(todo, &examine); 469 470 while ((gn = Array_Pop(&examine)) != NULL) { 471 if (gn->must_make) /* already known */ 472 continue; 473 gn->must_make = true; 474 475 slot = ohash_qlookup(&targets, gn->name); 476 if (!ohash_find(&targets, slot)) 477 ohash_insert(&targets, slot, gn); 478 479 480 look_harder_for_target(gn); 481 kludge_look_harder_for_target(gn); 482 /* 483 * Apply any .USE rules before looking for implicit 484 * dependencies to make sure everything that should have 485 * commands has commands ... 486 */ 487 Lst_ForEach(&gn->children, MakeHandleUse, gn); 488 Suff_FindDeps(gn); 489 expand_all_children(gn); 490 491 if (gn->unmade != 0) { 492 if (DEBUG(MAKE)) 493 printf("%s: not queuing (%d unmade children)\n", 494 gn->name, gn->unmade); 495 Lst_ForEach(&gn->children, MakeAddChild, 496 &examine); 497 } else { 498 if (DEBUG(MAKE)) 499 printf("%s: queuing\n", gn->name); 500 Array_Push(&toBeMade, gn); 501 } 502 } 503 if (randomize_queue) 504 randomize_garray(&toBeMade); 505 } 506 507 /*- 508 *----------------------------------------------------------------------- 509 * Make_Run -- 510 * Initialize the nodes to remake and the list of nodes which are 511 * ready to be made by doing a breadth-first traversal of the graph 512 * starting from the nodes in the given list. Once this traversal 513 * is finished, all the 'leaves' of the graph are in the toBeMade 514 * queue. 515 * Using this queue and the Job module, work back up the graph, 516 * calling on MakeStartJobs to keep the job table as full as 517 * possible. 518 * 519 * Results: 520 * true if work was done. false otherwise. 521 * 522 * Side Effects: 523 * The must_make field of all nodes involved in the creation of the given 524 * targets is set to 1. The toBeMade list is set to contain all the 525 * 'leaves' of these subgraphs. 526 *----------------------------------------------------------------------- 527 */ 528 bool 529 Make_Run(Lst targs) /* the initial list of targets */ 530 { 531 bool problem; /* errors occurred */ 532 533 /* wild guess at initial sizes */ 534 Array_Init(&toBeMade, 500); 535 Array_Init(&examine, 150); 536 Array_Init(&heldBack, 100); 537 ohash_init(&targets, 10, &gnode_info); 538 if (DEBUG(PARALLEL)) 539 random_setup(); 540 541 add_targets_to_make(targs); 542 if (queryFlag) { 543 /* 544 * We wouldn't do any work unless we could start some jobs in 545 * the next loop... (we won't actually start any, of course, 546 * this is just to see if any of the targets was out of date) 547 */ 548 return MakeStartJobs(); 549 } else { 550 /* 551 * Initialization. At the moment, no jobs are running and until 552 * some get started, nothing will happen since the remaining 553 * upward traversal of the graph is performed by the routines 554 * in job.c upon the finishing of a job. So we fill the Job 555 * table as much as we can before going into our loop. 556 */ 557 (void)MakeStartJobs(); 558 } 559 560 /* 561 * Main Loop: The idea here is that the ending of jobs will take 562 * care of the maintenance of data structures and the waiting for output 563 * will cause us to be idle most of the time while our children run as 564 * much as possible. Because the job table is kept as full as possible, 565 * the only time when it will be empty is when all the jobs which need 566 * running have been run, so that is the end condition of this loop. 567 * Note that the Job module will exit if there were any errors unless 568 * the keepgoing flag was given. 569 */ 570 while (!Job_Empty()) { 571 handle_running_jobs(); 572 (void)MakeStartJobs(); 573 } 574 575 problem = Job_Finish(); 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 problem = true; 584 } 585 Lst_Every(targs, MakePrintStatus); 586 if (problem) 587 Fatal("Errors while building"); 588 589 return true; 590 } 591 592 /* round-about detection: assume make is bug-free, if there are targets 593 * that have not been touched, it means they never were reached, so we can 594 * look for a cycle 595 */ 596 static bool 597 targets_contain_cycles(void) 598 { 599 GNode *gn; 600 unsigned int i; 601 bool cycle = false; 602 bool first = true; 603 604 for (gn = ohash_first(&targets, &i); gn != NULL; 605 gn = ohash_next(&targets, &i)) { 606 if (has_been_built(gn)) 607 continue; 608 cycle = true; 609 if (first) 610 printf("Error target(s) unaccounted for: "); 611 printf("%s ", gn->name); 612 first = false; 613 } 614 if (!first) 615 printf("\n"); 616 return cycle; 617 } 618 619 static void 620 print_unlink_cycle(struct growableArray *l, GNode *c) 621 { 622 LstNode ln; 623 GNode *gn = NULL; 624 unsigned int i; 625 626 printf("Cycle found: "); 627 628 for (i = 0; i != l->n; i++) { 629 gn = l->a[i]; 630 if (gn == c) 631 printf("("); 632 printf("%s -> ", gn->name); 633 } 634 printf("%s)\n", c->name); 635 assert(gn); 636 637 /* So the first element is tied to our node, find and kill the link */ 638 for (ln = Lst_First(&gn->children); ln != NULL; ln = Lst_Adv(ln)) { 639 GNode *gn2 = Lst_Datum(ln); 640 if (gn2 == c) { 641 Lst_Remove(&gn->children, ln); 642 return; 643 } 644 } 645 /* this shouldn't happen ever */ 646 assert(0); 647 } 648 649 /* each call to find_cycle records a cycle in cycle, to break at node c. 650 * this will stop eventually. 651 */ 652 static void 653 break_and_print_cycles(Lst t) 654 { 655 struct growableArray cycle; 656 657 Array_Init(&cycle, 16); /* cycles are generally shorter */ 658 while (1) { 659 GNode *c; 660 661 Array_Reset(&cycle); 662 c = find_cycle(t, &cycle); 663 if (c) 664 print_unlink_cycle(&cycle, c); 665 else 666 break; 667 } 668 free(cycle.a); 669 } 670 671 672 static GNode * 673 find_cycle(Lst l, struct growableArray *cycle) 674 { 675 LstNode ln; 676 677 for (ln = Lst_First(l); ln != NULL; ln = Lst_Adv(ln)) { 678 GNode *gn = Lst_Datum(ln); 679 if (gn->in_cycle) { 680 /* we should print the cycle and not do more */ 681 return gn; 682 } 683 684 if (gn->built_status == UPTODATE) 685 continue; 686 if (gn->unmade != 0) { 687 GNode *c; 688 689 gn->in_cycle = true; 690 Array_Push(cycle, gn); 691 c = find_cycle(&gn->children, cycle); 692 gn->in_cycle = false; 693 if (c) 694 return c; 695 Array_Pop(cycle); 696 } 697 } 698 return NULL; 699 } 700