1 /* $OpenBSD: make.c,v 1.85 2024/06/18 02:11:03 millert 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 "defines.h"
68 #include "dir.h"
69 #include "job.h"
70 #include "suff.h"
71 #include "var.h"
72 #include "error.h"
73 #include "expandchildren.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 to_build;
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_predecessor_left_to_build(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
nothing_left_to_build(void)121 nothing_left_to_build(void)
122 {
123 return Array_IsEmpty(&to_build);
124 }
125
126 static void
random_setup(void)127 random_setup(void)
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
randomize_garray(struct growableArray * g)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
has_predecessor_left_to_build(GNode * gn)160 has_predecessor_left_to_build(GNode *gn)
161 {
162 LstNode ln;
163
164 if (Lst_IsEmpty(&gn->predecessors))
165 return false;
166
167
168 for (ln = Lst_First(&gn->predecessors); 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
requeue_successors(GNode * gn)182 requeue_successors(GNode *gn)
183 {
184 LstNode ln;
185 /* Deal with successor nodes. If any is marked for making and has an
186 * children_left count of 0, has not been made and isn't in the
187 * examination queue, it means we need to place it in the queue as
188 * it restrained 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->children_left == 0
193 && succ->built_status == UNKNOWN)
194 Array_PushNew(&to_build, succ);
195 }
196 }
197
198 static void
requeue(GNode * gn)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(&to_build, 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 children_left field of pgn is decremented and pgn may be placed on
231 * the to_build queue if this field becomes 0.
232 *
233 * If the child got built, the parent's child_rebuilt field will be set to
234 * true
235 *-----------------------------------------------------------------------
236 */
237 void
Make_Update(GNode * cgn)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->children_left--;
276 if (pgn->must_make) {
277 if (DEBUG(MAKE))
278 printf("%s--=%d ",
279 pgn->name, pgn->children_left);
280
281 if ( ! (cgn->type & OP_USE)) {
282 if (cgn->built_status == REBUILT)
283 pgn->child_rebuilt = true;
284 (void)Make_TimeStamp(pgn, cgn);
285 }
286 if (pgn->children_left == 0) {
287 /*
288 * Queue the node up -- any yet-to-build
289 * predecessors will be dealt with in
290 * MakeStartJobs.
291 */
292 if (DEBUG(MAKE))
293 printf("QUEUING ");
294 Array_Push(&to_build, pgn);
295 } else if (pgn->children_left < 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
try_to_make_node(GNode * gn)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->children_left != 0) {
318 if (DEBUG(MAKE))
319 printf(" Requeuing (%d)\n", gn->children_left);
320 add_targets_to_make(&gn->children);
321 Array_Push(&to_build, 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_predecessor_left_to_build(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->children_left != 0) {
337 if (DEBUG(MAKE))
338 printf(" Requeuing (after deps: %d)\n",
339 gn->children_left);
340 add_targets_to_make(&gn->children);
341 return false;
342 }
343 /* this is where we hold back nodes */
344 if (gn->groupling != NULL) {
345 GNode *gn2;
346 for (gn2 = gn->groupling; gn2 != gn; gn2 = gn2->groupling)
347 if (gn2->built_status == BUILDING) {
348 gn->watched = gn2;
349 gn->built_status = HELDBACK;
350 if (DEBUG(HELDJOBS))
351 printf("Holding back job %s, "
352 "groupling to %s\n",
353 gn->name, gn2->name);
354 Array_Push(&heldBack, gn);
355 return false;
356 }
357 }
358 if (gn->sibling != gn) {
359 GNode *gn2;
360 for (gn2 = gn->sibling; gn2 != gn; gn2 = gn2->sibling)
361 if (gn2->built_status == BUILDING) {
362 gn->watched = gn2;
363 gn->built_status = HELDBACK;
364 if (DEBUG(HELDJOBS))
365 printf("Holding back job %s, "
366 "sibling to %s\n",
367 gn->name, gn2->name);
368 Array_Push(&heldBack, gn);
369 return false;
370 }
371 }
372 if (Make_OODate(gn)) {
373 if (DEBUG(MAKE))
374 printf("out-of-date\n");
375 if (queryFlag)
376 return true;
377 /* SIB: this is where commands should get prepared */
378 Make_DoAllVar(gn);
379 if (node_find_valid_commands(gn)) {
380 if (touchFlag)
381 Job_Touch(gn);
382 else
383 Job_Make(gn);
384 } else
385 node_failure(gn);
386 } else {
387 if (DEBUG(MAKE))
388 printf("up-to-date\n");
389 gn->built_status = UPTODATE;
390
391 Make_Update(gn);
392 }
393 return false;
394 }
395
396 /*
397 *-----------------------------------------------------------------------
398 * MakeStartJobs --
399 * Start as many jobs as possible.
400 *
401 * Results:
402 * If the query flag was given to pmake, no job will be started,
403 * but as soon as an out-of-date target is found, this function
404 * returns true. At all other times, this function returns false.
405 *
406 * Side Effects:
407 * Nodes are removed from the to_build queue and job table slots
408 * are filled.
409 *-----------------------------------------------------------------------
410 */
411 static bool
MakeStartJobs(void)412 MakeStartJobs(void)
413 {
414 GNode *gn;
415
416 while (can_start_job() && (gn = Array_Pop(&to_build)) != NULL) {
417 if (try_to_make_node(gn))
418 return true;
419 }
420 return false;
421 }
422
423 static void
MakePrintStatus(void * gnp)424 MakePrintStatus(void *gnp)
425 {
426 GNode *gn = gnp;
427 if (gn->built_status == UPTODATE) {
428 printf("`%s' is up to date.\n", gn->name);
429 } else if (gn->children_left != 0) {
430 printf("`%s' not remade because of errors.\n", gn->name);
431 }
432 }
433
434 static void
MakeAddChild(void * to_addp,void * ap)435 MakeAddChild(void *to_addp, void *ap)
436 {
437 GNode *gn = to_addp;
438 struct growableArray *a = ap;
439
440 if (!gn->must_make && !(gn->type & OP_USE))
441 Array_Push(a, gn);
442 }
443
444 static void
MakeHandleUse(void * cgnp,void * pgnp)445 MakeHandleUse(void *cgnp, void *pgnp)
446 {
447 GNode *cgn = cgnp;
448 GNode *pgn = pgnp;
449
450 if (cgn->type & OP_USE)
451 Make_HandleUse(cgn, pgn);
452 }
453
454 /* Add stuff to the to_build 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
add_targets_to_make(Lst todo)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 Suff_FindDeps(gn);
486 expand_all_children(gn);
487
488 if (gn->children_left != 0) {
489 if (DEBUG(MAKE))
490 printf("%s: not queuing (%d child%s left to build)\n",
491 gn->name, gn->children_left,
492 gn->children_left > 1 ? "ren" : "");
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
Make_Init(void)506 Make_Init(void)
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
Make_Run(Lst targs,bool * has_errors,bool * out_of_date)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
targets_contain_cycles(void)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
print_unlink_cycle(struct growableArray * l,GNode * c)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
break_and_print_cycles(Lst t)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 *
find_cycle(Lst l,struct growableArray * cycle)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