1 /* $OpenPackages$ */ 2 /* $OpenBSD: make.c,v 1.58 2008/11/04 07:22:36 espie Exp $ */ 3 /* $NetBSD: make.c,v 1.10 1996/11/06 17:59:15 christos Exp $ */ 4 5 /* 6 * Copyright (c) 1988, 1989, 1990, 1993 7 * The Regents of the University of California. All rights reserved. 8 * Copyright (c) 1989 by Berkeley Softworks 9 * All rights reserved. 10 * 11 * This code is derived from software contributed to Berkeley by 12 * Adam de Boor. 13 * 14 * Redistribution and use in source and binary forms, with or without 15 * modification, are permitted provided that the following conditions 16 * are met: 17 * 1. Redistributions of source code must retain the above copyright 18 * notice, this list of conditions and the following disclaimer. 19 * 2. Redistributions in binary form must reproduce the above copyright 20 * notice, this list of conditions and the following disclaimer in the 21 * documentation and/or other materials provided with the distribution. 22 * 3. Neither the name of the University nor the names of its contributors 23 * may be used to endorse or promote products derived from this software 24 * without specific prior written permission. 25 * 26 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 27 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 28 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 29 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 30 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 31 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 32 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 33 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 34 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 35 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 36 * SUCH DAMAGE. 37 */ 38 39 /*- 40 * make.c -- 41 * The functions which perform the examination of targets and 42 * their suitability for creation 43 * 44 * Interface: 45 * Make_Run Initialize things for the module and recreate 46 * whatever needs recreating. Returns true if 47 * work was (or would have been) done and 48 * false 49 * otherwise. 50 * 51 * Make_Update Update all parents of a given child. Performs 52 * various bookkeeping chores like the updating 53 * of the cmtime field of the parent, filling 54 * of the IMPSRC context variable, etc. It will 55 * place the parent on the toBeMade queue if it 56 * should be. 57 * 58 */ 59 60 #include <limits.h> 61 #include <stdio.h> 62 #include <signal.h> 63 #include <stddef.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 static struct ohash targets; /* stuff we must build */ 95 96 static void MakeAddChild(void *, void *); 97 static void MakeHandleUse(void *, void *); 98 static bool MakeStartJobs(void); 99 static void MakePrintStatus(void *, void *); 100 static bool try_to_make_node(GNode *); 101 static void add_targets_to_make(Lst); 102 103 static bool has_unmade_predecessor(GNode *); 104 static void requeue_successors(GNode *); 105 static void random_setup(void); 106 107 static bool randomize_queue; 108 long random_delay = 0; 109 110 bool 111 no_jobs_left() 112 { 113 return Array_IsEmpty(&toBeMade); 114 } 115 116 static void 117 random_setup() 118 { 119 randomize_queue = Var_Definedi("RANDOM_ORDER", NULL); 120 121 if (Var_Definedi("RANDOM_DELAY", NULL)) 122 random_delay = strtonum(Var_Value("RANDOM_DELAY"), 0, 1000, 123 NULL) * 1000000; 124 125 if (randomize_queue || random_delay) { 126 unsigned int random_seed; 127 char *t; 128 129 t = Var_Value("RANDOM_SEED"); 130 if (t != NULL) 131 random_seed = strtonum(t, 0, UINT_MAX, NULL); 132 else 133 random_seed = time(NULL); 134 fprintf(stderr, "RANDOM_SEED=%u\n", random_seed); 135 srandom(random_seed); 136 } 137 } 138 139 static void 140 randomize_garray(struct growableArray *g) 141 { 142 /* This is a fairly standard algorithm to randomize an array. */ 143 unsigned int i, v; 144 GNode *e; 145 146 for (i = g->n; i > 0; i--) { 147 v = random() % i; 148 if (v == i-1) 149 continue; 150 else { 151 e = g->a[i-1]; 152 g->a[i-1] = g->a[v]; 153 g->a[v] = e; 154 } 155 } 156 } 157 158 static bool 159 has_unmade_predecessor(GNode *gn) 160 { 161 LstNode ln; 162 163 if (Lst_IsEmpty(&gn->preds)) 164 return false; 165 166 167 for (ln = Lst_First(&gn->preds); ln != NULL; ln = Lst_Adv(ln)) { 168 GNode *pgn = (GNode *)Lst_Datum(ln); 169 170 if (pgn->must_make && pgn->built_status == UNKNOWN) { 171 if (DEBUG(MAKE)) 172 printf("predecessor %s not made yet.\n", 173 pgn->name); 174 return true; 175 } 176 } 177 return false; 178 } 179 180 static void 181 requeue_successors(GNode *gn) 182 { 183 LstNode ln; 184 /* Deal with successor nodes. If any is marked for making and has an 185 * unmade count of 0, has not been made and isn't in the examination 186 * queue, it means we need to place it in the queue as it restrained 187 * itself before. */ 188 for (ln = Lst_First(&gn->successors); ln != NULL; ln = Lst_Adv(ln)) { 189 GNode *succ = (GNode *)Lst_Datum(ln); 190 191 if (succ->must_make && succ->unmade == 0 192 && succ->built_status == UNKNOWN) 193 Array_PushNew(&toBeMade, succ); 194 } 195 } 196 197 /*- 198 *----------------------------------------------------------------------- 199 * Make_Update -- 200 * Perform update on the parents of a node. Used by JobFinish once 201 * a node has been dealt with and by MakeStartJobs if it finds an 202 * up-to-date node. 203 * 204 * Results: 205 * Always returns 0 206 * 207 * Side Effects: 208 * The unmade field of pgn is decremented and pgn may be placed on 209 * the toBeMade queue if this field becomes 0. 210 * 211 * If the child was made, the parent's childMade field will be set true 212 * and its cmtime set to now. 213 * 214 * If the child wasn't made, the cmtime field of the parent will be 215 * altered if the child's mtime is big enough. 216 * 217 *----------------------------------------------------------------------- 218 */ 219 void 220 Make_Update(GNode *cgn) /* the child node */ 221 { 222 GNode *pgn; /* the parent node */ 223 char *cname; /* the child's name */ 224 LstNode ln; /* Element in parents list */ 225 226 cname = Var(TARGET_INDEX, cgn); 227 228 /* 229 * If the child was actually made, see what its modification time is 230 * now -- some rules won't actually update the file. If the file still 231 * doesn't exist, make its mtime now. 232 */ 233 if (cgn->built_status != UPTODATE) { 234 /* 235 * This is what Make does and it's actually a good thing, as it 236 * allows rules like 237 * 238 * cmp -s y.tab.h parse.h || cp y.tab.h parse.h 239 * 240 * to function as intended. Unfortunately, thanks to the 241 * stateless nature of NFS, there are times when the 242 * modification time of a file created on a remote machine 243 * will not be modified before the local stat() implied by 244 * the Dir_MTime occurs, thus leading us to believe that the 245 * file is unchanged, wreaking havoc with files that depend 246 * on this one. 247 */ 248 if (noExecute || is_out_of_date(Dir_MTime(cgn))) 249 cgn->mtime = now; 250 if (DEBUG(MAKE)) 251 printf("update time: %s\n", time_to_string(cgn->mtime)); 252 } 253 254 /* SIB: this is where I should mark the build as finished */ 255 cgn->build_lock = false; 256 for (ln = Lst_First(&cgn->parents); ln != NULL; ln = Lst_Adv(ln)) { 257 pgn = (GNode *)Lst_Datum(ln); 258 /* SIB: there should be a siblings loop there */ 259 pgn->unmade--; 260 if (pgn->must_make) { 261 if (DEBUG(MAKE)) 262 printf("%s--=%d ", 263 pgn->name, pgn->unmade); 264 265 if ( ! (cgn->type & (OP_EXEC|OP_USE))) { 266 if (cgn->built_status == MADE) { 267 pgn->childMade = true; 268 if (is_strictly_before(pgn->cmtime, 269 cgn->mtime)) 270 pgn->cmtime = cgn->mtime; 271 } else { 272 (void)Make_TimeStamp(pgn, cgn); 273 } 274 } 275 if (pgn->unmade == 0) { 276 /* 277 * Queue the node up -- any unmade 278 * predecessors will be dealt with in 279 * MakeStartJobs. 280 */ 281 if (DEBUG(MAKE)) 282 printf("QUEUING "); 283 Array_Push(&toBeMade, pgn); 284 } else if (pgn->unmade < 0) { 285 Error("Child %s discovered graph cycles through %s", cgn->name, pgn->name); 286 } 287 } 288 } 289 if (DEBUG(MAKE)) 290 printf("\n"); 291 requeue_successors(cgn); 292 } 293 294 static bool 295 try_to_make_node(GNode *gn) 296 { 297 if (DEBUG(MAKE)) 298 printf("Examining %s...", gn->name); 299 300 if (gn->unmade != 0) { 301 if (DEBUG(MAKE)) 302 printf(" Requeuing (%d)\n", gn->unmade); 303 add_targets_to_make(&gn->children); 304 Array_Push(&toBeMade, gn); 305 return false; 306 } 307 if (has_been_built(gn)) { 308 if (DEBUG(MAKE)) 309 printf(" already made\n"); 310 return false; 311 } 312 if (has_unmade_predecessor(gn)) { 313 if (DEBUG(MAKE)) 314 printf(" Dropping for now\n"); 315 return false; 316 } 317 318 /* SIB: this is where there should be a siblings loop */ 319 Suff_FindDeps(gn); 320 if (gn->unmade != 0) { 321 if (DEBUG(MAKE)) 322 printf(" Requeuing (after deps: %d)\n", gn->unmade); 323 add_targets_to_make(&gn->children); 324 return false; 325 } 326 if (Make_OODate(gn)) { 327 /* SIB: if a sibling is getting built, I don't build it right now */ 328 if (DEBUG(MAKE)) 329 printf("out-of-date\n"); 330 if (queryFlag) 331 return true; 332 /* SIB: this is where commands should get prepared */ 333 Make_DoAllVar(gn); 334 /* SIB: this is where I should make the gn as `being built */ 335 gn->build_lock = true; 336 Job_Make(gn); 337 } else { 338 if (DEBUG(MAKE)) 339 printf("up-to-date\n"); 340 gn->built_status = UPTODATE; 341 if (gn->type & OP_JOIN) { 342 /* 343 * Even for an up-to-date .JOIN node, we need it 344 * to have its context variables so references 345 * to it get the correct value for .TARGET when 346 * building up the context variables of its 347 * parent(s)... 348 */ 349 Make_DoAllVar(gn); 350 } 351 352 Make_Update(gn); 353 } 354 return false; 355 } 356 357 /* 358 *----------------------------------------------------------------------- 359 * MakeStartJobs -- 360 * Start as many jobs as possible. 361 * 362 * Results: 363 * If the query flag was given to pmake, no job will be started, 364 * but as soon as an out-of-date target is found, this function 365 * returns true. At all other times, this function returns false. 366 * 367 * Side Effects: 368 * Nodes are removed from the toBeMade queue and job table slots 369 * are filled. 370 *----------------------------------------------------------------------- 371 */ 372 static bool 373 MakeStartJobs(void) 374 { 375 GNode *gn; 376 377 while (!Job_Full() && (gn = Array_Pop(&toBeMade)) != NULL) { 378 if (try_to_make_node(gn)) 379 return true; 380 } 381 return false; 382 } 383 384 /*- 385 *----------------------------------------------------------------------- 386 * MakePrintStatus -- 387 * Print the status of a top-level node, viz. it being up-to-date 388 * already or not created due to an error in a lower level. 389 * Callback function for Make_Run via Lst_ForEach. 390 * 391 * Side Effects: 392 * A message may be printed. 393 *----------------------------------------------------------------------- 394 */ 395 static void 396 MakePrintStatus( 397 void *gnp, /* Node to examine */ 398 void *cyclep) /* True if gn->unmade being non-zero implies 399 * a cycle in the graph, not an error in an 400 * inferior */ 401 { 402 GNode *gn = (GNode *)gnp; 403 bool cycle = *(bool *)cyclep; 404 if (gn->built_status == UPTODATE) { 405 printf("`%s' is up to date.\n", gn->name); 406 } else if (gn->unmade != 0) { 407 if (cycle) { 408 bool t = true; 409 /* 410 * If printing cycles and came to one that has unmade 411 * children, print out the cycle by recursing on its 412 * children. Note a cycle like: 413 * a : b 414 * b : c 415 * c : b 416 * will cause this to erroneously complain about a 417 * being in the cycle, but this is a good approximation. 418 */ 419 if (gn->built_status == CYCLE) { 420 Error("Graph cycles through `%s'", gn->name); 421 gn->built_status = ENDCYCLE; 422 Lst_ForEach(&gn->children, MakePrintStatus, &t); 423 gn->built_status = UNKNOWN; 424 } else if (gn->built_status != ENDCYCLE) { 425 gn->built_status = CYCLE; 426 Lst_ForEach(&gn->children, MakePrintStatus, &t); 427 } 428 } else { 429 printf("`%s' not remade because of errors.\n", 430 gn->name); 431 } 432 } 433 } 434 435 436 static void 437 MakeAddChild(void *to_addp, void *ap) 438 { 439 GNode *gn = (GNode *)to_addp; 440 441 if (!gn->must_make && !(gn->type & OP_USE)) 442 Array_Push((struct growableArray *)ap, gn); 443 } 444 445 static void 446 MakeHandleUse(void *cgnp, void *pgnp) 447 { 448 GNode *cgn = (GNode *)cgnp; 449 GNode *pgn = (GNode *)pgnp; 450 451 if (cgn->type & OP_USE) 452 Make_HandleUse(cgn, pgn); 453 } 454 455 /* Add stuff to the toBeMade 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 expand_all_children(gn); 487 488 if (gn->unmade != 0) { 489 if (DEBUG(MAKE)) 490 printf("%s: not queuing (%d unmade children)\n", 491 gn->name, gn->unmade); 492 Lst_ForEach(&gn->children, MakeAddChild, 493 &examine); 494 } else { 495 if (DEBUG(MAKE)) 496 printf("%s: queuing\n", gn->name); 497 Array_Push(&toBeMade, gn); 498 } 499 } 500 if (randomize_queue) 501 randomize_garray(&toBeMade); 502 } 503 504 /*- 505 *----------------------------------------------------------------------- 506 * Make_Run -- 507 * Initialize the nodes to remake and the list of nodes which are 508 * ready to be made by doing a breadth-first traversal of the graph 509 * starting from the nodes in the given list. Once this traversal 510 * is finished, all the 'leaves' of the graph are in the toBeMade 511 * queue. 512 * Using this queue and the Job module, work back up the graph, 513 * calling on MakeStartJobs to keep the job table as full as 514 * possible. 515 * 516 * Results: 517 * true if work was done. false otherwise. 518 * 519 * Side Effects: 520 * The must_make field of all nodes involved in the creation of the given 521 * targets is set to 1. The toBeMade list is set to contain all the 522 * 'leaves' of these subgraphs. 523 *----------------------------------------------------------------------- 524 */ 525 bool 526 Make_Run(Lst targs) /* the initial list of targets */ 527 { 528 int errors; /* Number of errors the Job module reports */ 529 GNode *gn; 530 unsigned int i; 531 bool cycle; 532 533 /* wild guess at initial sizes */ 534 Array_Init(&toBeMade, 500); 535 Array_Init(&examine, 150); 536 ohash_init(&targets, 10, &gnode_info); 537 if (DEBUG(PARALLEL)) 538 random_setup(); 539 540 add_targets_to_make(targs); 541 if (queryFlag) { 542 /* 543 * We wouldn't do any work unless we could start some jobs in 544 * the next loop... (we won't actually start any, of course, 545 * this is just to see if any of the targets was out of date) 546 */ 547 return MakeStartJobs(); 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 errors = Job_Finish(); 575 cycle = false; 576 577 for (gn = ohash_first(&targets, &i); gn != NULL; 578 gn = ohash_next(&targets, &i)) { 579 if (has_been_built(gn)) 580 continue; 581 cycle = true; 582 errors++; 583 printf("Error: target %s unaccounted for (%s)\n", 584 gn->name, status_to_string(gn)); 585 } 586 /* 587 * Print the final status of each target. E.g. if it wasn't made 588 * because some inferior reported an error. 589 */ 590 Lst_ForEach(targs, MakePrintStatus, &cycle); 591 if (errors) 592 Fatal("Errors while building"); 593 594 return true; 595 } 596