Annotation of src/usr.bin/make/make.c, Revision 1.60
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.58 espie 81: #include "targequiv.h"
1.56 espie 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;
1.25 espie 93:
1.52 espie 94: static struct ohash targets; /* stuff we must build */
1.1 deraadt 95:
1.25 espie 96: static void MakeAddChild(void *, void *);
97: static void MakeHandleUse(void *, void *);
1.26 espie 98: static bool MakeStartJobs(void);
1.25 espie 99: static void MakePrintStatus(void *, void *);
1.46 espie 100: static bool try_to_make_node(GNode *);
101: static void add_targets_to_make(Lst);
1.40 espie 102:
1.52 espie 103: static bool has_unmade_predecessor(GNode *);
104: static void requeue_successors(GNode *);
1.54 espie 105: static void random_setup(void);
106:
107: static bool randomize_queue;
108: long random_delay = 0;
109:
1.56 espie 110: bool
111: no_jobs_left()
112: {
113: return Array_IsEmpty(&toBeMade);
114: }
115:
1.54 espie 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: }
1.52 espie 138:
1.56 espie 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:
1.52 espie 158: static bool
159: has_unmade_predecessor(GNode *gn)
1.1 deraadt 160: {
1.52 espie 161: LstNode ln;
162:
163: if (Lst_IsEmpty(&gn->preds))
164: return false;
1.5 millert 165:
1.52 espie 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;
1.1 deraadt 178: }
1.25 espie 179:
1.15 espie 180: static void
1.52 espie 181: requeue_successors(GNode *gn)
1.1 deraadt 182: {
1.52 espie 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)
1.56 espie 193: Array_PushNew(&toBeMade, succ);
1.52 espie 194: }
1.1 deraadt 195: }
1.25 espie 196:
1.1 deraadt 197: /*-
198: *-----------------------------------------------------------------------
1.25 espie 199: * Make_Update --
1.1 deraadt 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
1.4 millert 202: * up-to-date node.
1.1 deraadt 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: *
1.25 espie 211: * If the child was made, the parent's childMade field will be set true
1.1 deraadt 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
1.35 espie 220: Make_Update(GNode *cgn) /* the child node */
1.1 deraadt 221: {
1.40 espie 222: GNode *pgn; /* the parent node */
223: char *cname; /* the child's name */
1.47 espie 224: LstNode ln; /* Element in parents list */
1.40 espie 225:
1.50 espie 226: cname = Var(TARGET_INDEX, cgn);
1.40 espie 227:
1.1 deraadt 228: /*
1.40 espie 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.
1.1 deraadt 232: */
1.48 espie 233: if (cgn->built_status != UPTODATE) {
1.40 espie 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: *
1.41 espie 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
1.40 espie 243: * will not be modified before the local stat() implied by
1.41 espie 244: * the Dir_MTime occurs, thus leading us to believe that the
245: * file is unchanged, wreaking havoc with files that depend
1.40 espie 246: * on this one.
247: */
1.43 espie 248: if (noExecute || is_out_of_date(Dir_MTime(cgn)))
1.60 ! espie 249: ts_set_from_now(cgn->mtime);
1.40 espie 250: if (DEBUG(MAKE))
251: printf("update time: %s\n", time_to_string(cgn->mtime));
252: }
253:
1.58 espie 254: /* SIB: this is where I should mark the build as finished */
255: cgn->build_lock = false;
1.40 espie 256: for (ln = Lst_First(&cgn->parents); ln != NULL; ln = Lst_Adv(ln)) {
257: pgn = (GNode *)Lst_Datum(ln);
1.58 espie 258: /* SIB: there should be a siblings loop there */
1.55 espie 259: pgn->unmade--;
1.48 espie 260: if (pgn->must_make) {
1.52 espie 261: if (DEBUG(MAKE))
262: printf("%s--=%d ",
263: pgn->name, pgn->unmade);
1.40 espie 264:
265: if ( ! (cgn->type & (OP_EXEC|OP_USE))) {
1.48 espie 266: if (cgn->built_status == MADE) {
1.40 espie 267: pgn->childMade = true;
1.41 espie 268: if (is_strictly_before(pgn->cmtime,
1.40 espie 269: cgn->mtime))
270: pgn->cmtime = cgn->mtime;
271: } else {
272: (void)Make_TimeStamp(pgn, cgn);
273: }
274: }
275: if (pgn->unmade == 0) {
276: /*
1.41 espie 277: * Queue the node up -- any unmade
278: * predecessors will be dealt with in
1.40 espie 279: * MakeStartJobs.
280: */
1.52 espie 281: if (DEBUG(MAKE))
282: printf("QUEUING ");
1.56 espie 283: Array_Push(&toBeMade, pgn);
1.40 espie 284: } else if (pgn->unmade < 0) {
1.52 espie 285: Error("Child %s discovered graph cycles through %s", cgn->name, pgn->name);
1.40 espie 286: }
287: }
1.1 deraadt 288: }
1.52 espie 289: if (DEBUG(MAKE))
290: printf("\n");
291: requeue_successors(cgn);
1.1 deraadt 292: }
1.25 espie 293:
1.46 espie 294: static bool
295: try_to_make_node(GNode *gn)
296: {
297: if (DEBUG(MAKE))
298: printf("Examining %s...", gn->name);
1.52 espie 299:
300: if (gn->unmade != 0) {
301: if (DEBUG(MAKE))
302: printf(" Requeuing (%d)\n", gn->unmade);
303: add_targets_to_make(&gn->children);
1.56 espie 304: Array_Push(&toBeMade, gn);
1.52 espie 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: }
1.46 espie 317:
1.58 espie 318: /* SIB: this is where there should be a siblings loop */
1.52 espie 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;
1.46 espie 325: }
326: if (Make_OODate(gn)) {
1.58 espie 327: /* SIB: if a sibling is getting built, I don't build it right now */
1.46 espie 328: if (DEBUG(MAKE))
329: printf("out-of-date\n");
330: if (queryFlag)
331: return true;
1.58 espie 332: /* SIB: this is where commands should get prepared */
1.46 espie 333: Make_DoAllVar(gn);
1.58 espie 334: /* SIB: this is where I should make the gn as `being built */
335: gn->build_lock = true;
1.46 espie 336: Job_Make(gn);
337: } else {
338: if (DEBUG(MAKE))
339: printf("up-to-date\n");
1.48 espie 340: gn->built_status = UPTODATE;
1.46 espie 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:
1.40 espie 357: /*
1.1 deraadt 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
1.26 espie 365: * returns true. At all other times, this function returns false.
1.1 deraadt 366: *
367: * Side Effects:
368: * Nodes are removed from the toBeMade queue and job table slots
369: * are filled.
370: *-----------------------------------------------------------------------
371: */
1.26 espie 372: static bool
1.35 espie 373: MakeStartJobs(void)
1.1 deraadt 374: {
1.40 espie 375: GNode *gn;
1.4 millert 376:
1.59 espie 377: while (can_start_job() && (gn = Array_Pop(&toBeMade)) != NULL) {
1.46 espie 378: if (try_to_make_node(gn))
379: return true;
1.1 deraadt 380: }
1.40 espie 381: return false;
1.1 deraadt 382: }
1.25 espie 383:
1.1 deraadt 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.
1.25 espie 390: *
391: * Side Effects:
392: * A message may be printed.
1.1 deraadt 393: *-----------------------------------------------------------------------
394: */
1.15 espie 395: static void
1.35 espie 396: MakePrintStatus(
397: void *gnp, /* Node to examine */
398: void *cyclep) /* True if gn->unmade being non-zero implies
1.1 deraadt 399: * a cycle in the graph, not an error in an
400: * inferior */
401: {
1.40 espie 402: GNode *gn = (GNode *)gnp;
403: bool cycle = *(bool *)cyclep;
1.48 espie 404: if (gn->built_status == UPTODATE) {
1.40 espie 405: printf("`%s' is up to date.\n", gn->name);
406: } else if (gn->unmade != 0) {
407: if (cycle) {
408: bool t = true;
409: /*
1.41 espie 410: * If printing cycles and came to one that has unmade
411: * children, print out the cycle by recursing on its
1.40 espie 412: * children. Note a cycle like:
413: * a : b
414: * b : c
415: * c : b
1.41 espie 416: * will cause this to erroneously complain about a
1.40 espie 417: * being in the cycle, but this is a good approximation.
418: */
1.48 espie 419: if (gn->built_status == CYCLE) {
1.40 espie 420: Error("Graph cycles through `%s'", gn->name);
1.48 espie 421: gn->built_status = ENDCYCLE;
1.40 espie 422: Lst_ForEach(&gn->children, MakePrintStatus, &t);
1.49 espie 423: gn->built_status = UNKNOWN;
1.48 espie 424: } else if (gn->built_status != ENDCYCLE) {
425: gn->built_status = CYCLE;
1.40 espie 426: Lst_ForEach(&gn->children, MakePrintStatus, &t);
427: }
428: } else {
1.41 espie 429: printf("`%s' not remade because of errors.\n",
1.40 espie 430: gn->name);
431: }
1.1 deraadt 432: }
433: }
1.25 espie 434:
1.5 millert 435:
1.52 espie 436: static void
1.56 espie 437: MakeAddChild(void *to_addp, void *ap)
1.52 espie 438: {
439: GNode *gn = (GNode *)to_addp;
440:
441: if (!gn->must_make && !(gn->type & OP_USE))
1.56 espie 442: Array_Push((struct growableArray *)ap, gn);
1.52 espie 443: }
444:
445: static void
1.58 espie 446: MakeHandleUse(void *cgnp, void *pgnp)
1.52 espie 447: {
1.58 espie 448: GNode *cgn = (GNode *)cgnp;
449: GNode *pgn = (GNode *)pgnp;
450:
451: if (cgn->type & OP_USE)
452: Make_HandleUse(cgn, pgn);
1.52 espie 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).
1.46 espie 458: */
459: static void
1.52 espie 460: add_targets_to_make(Lst todo)
1.46 espie 461: {
462: GNode *gn;
1.56 espie 463:
1.52 espie 464: unsigned int slot;
465:
1.56 espie 466: AppendList2Array(todo, &examine);
1.46 espie 467:
1.56 espie 468: while ((gn = Array_Pop(&examine)) != NULL) {
1.52 espie 469: if (gn->must_make) /* already known */
470: continue;
471: gn->must_make = true;
1.46 espie 472:
1.52 espie 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);
1.58 espie 479: kludge_look_harder_for_target(gn);
1.52 espie 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);
1.46 espie 487:
1.52 espie 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);
1.56 espie 497: Array_Push(&toBeMade, gn);
1.46 espie 498: }
499: }
1.56 espie 500: if (randomize_queue)
501: randomize_garray(&toBeMade);
1.46 espie 502: }
503:
1.1 deraadt 504: /*-
505: *-----------------------------------------------------------------------
1.6 millert 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: *
1.1 deraadt 516: * Results:
1.26 espie 517: * true if work was done. false otherwise.
1.1 deraadt 518: *
519: * Side Effects:
1.48 espie 520: * The must_make field of all nodes involved in the creation of the given
1.6 millert 521: * targets is set to 1. The toBeMade list is set to contain all the
522: * 'leaves' of these subgraphs.
1.1 deraadt 523: *-----------------------------------------------------------------------
524: */
1.26 espie 525: bool
1.35 espie 526: Make_Run(Lst targs) /* the initial list of targets */
1.1 deraadt 527: {
1.52 espie 528: int errors; /* Number of errors the Job module reports */
529: GNode *gn;
530: unsigned int i;
531: bool cycle;
1.40 espie 532:
1.54 espie 533: /* wild guess at initial sizes */
1.56 espie 534: Array_Init(&toBeMade, 500);
535: Array_Init(&examine, 150);
1.52 espie 536: ohash_init(&targets, 10, &gnode_info);
1.54 espie 537: if (DEBUG(PARALLEL))
538: random_setup();
1.40 espie 539:
1.46 espie 540: add_targets_to_make(targs);
1.40 espie 541: if (queryFlag) {
542: /*
1.41 espie 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,
1.40 espie 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
1.41 espie 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
1.40 espie 554: * table as much as we can before going into our loop.
555: */
556: (void)MakeStartJobs();
1.1 deraadt 557: }
1.4 millert 558:
1.1 deraadt 559: /*
1.40 espie 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.
1.41 espie 566: * Note that the Job module will exit if there were any errors unless
1.40 espie 567: * the keepgoing flag was given.
1.1 deraadt 568: */
1.40 espie 569: while (!Job_Empty()) {
1.57 espie 570: handle_running_jobs();
1.40 espie 571: (void)MakeStartJobs();
572: }
573:
574: errors = Job_Finish();
1.52 espie 575: cycle = false;
1.40 espie 576:
1.52 espie 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: }
1.1 deraadt 586: /*
1.40 espie 587: * Print the final status of each target. E.g. if it wasn't made
588: * because some inferior reported an error.
1.1 deraadt 589: */
1.52 espie 590: Lst_ForEach(targs, MakePrintStatus, &cycle);
591: if (errors)
592: Fatal("Errors while building");
1.4 millert 593:
1.40 espie 594: return true;
1.1 deraadt 595: }
![[BACK]](/icons/back.gif){kind=icon}
Return to make.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / src / usr.bin / make