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