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