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