Annotation of src/usr.bin/make/make.c, Revision 1.62
1.62 ! schwarze 1: /* $OpenBSD: make.c,v 1.61 2010/07/19 19:46:44 espie Exp $ */
1.6 millert 2: /* $NetBSD: make.c,v 1.10 1996/11/06 17:59:15 christos Exp $ */
1.1 deraadt 3:
4: /*
1.4 millert 5: * Copyright (c) 1988, 1989, 1990, 1993
6: * The Regents of the University of California. All rights reserved.
1.1 deraadt 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.
1.33 millert 21: * 3. Neither the name of the University nor the names of its contributors
1.1 deraadt 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:
1.25 espie 44: * Make_Run Initialize things for the module and recreate
1.26 espie 45: * whatever needs recreating. Returns true if
46: * work was (or would have been) done and
47: * false
1.25 espie 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: *
1.1 deraadt 57: */
58:
1.27 espie 59: #include <limits.h>
1.26 espie 60: #include <stdio.h>
1.43 espie 61: #include <signal.h>
1.52 espie 62: #include <stddef.h>
1.54 espie 63: #include <stdlib.h>
1.52 espie 64: #include <string.h>
65: #include <ohash.h>
1.26 espie 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"
1.37 espie 77: #include "engine.h"
1.26 espie 78: #include "lst.h"
1.43 espie 79: #include "targ.h"
1.58 espie 80: #include "targequiv.h"
1.56 espie 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;
1.25 espie 92:
1.52 espie 93: static struct ohash targets; /* stuff we must build */
1.1 deraadt 94:
1.25 espie 95: static void MakeAddChild(void *, void *);
96: static void MakeHandleUse(void *, void *);
1.26 espie 97: static bool MakeStartJobs(void);
1.25 espie 98: static void MakePrintStatus(void *, void *);
1.46 espie 99: static bool try_to_make_node(GNode *);
100: static void add_targets_to_make(Lst);
1.40 espie 101:
1.52 espie 102: static bool has_unmade_predecessor(GNode *);
103: static void requeue_successors(GNode *);
1.54 espie 104: static void random_setup(void);
105:
106: static bool randomize_queue;
107: long random_delay = 0;
108:
1.56 espie 109: bool
110: no_jobs_left()
111: {
112: return Array_IsEmpty(&toBeMade);
113: }
114:
1.54 espie 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: }
1.52 espie 137:
1.56 espie 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:
1.52 espie 157: static bool
158: has_unmade_predecessor(GNode *gn)
1.1 deraadt 159: {
1.52 espie 160: LstNode ln;
161:
162: if (Lst_IsEmpty(&gn->preds))
163: return false;
1.5 millert 164:
1.52 espie 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;
1.1 deraadt 177: }
1.25 espie 178:
1.15 espie 179: static void
1.52 espie 180: requeue_successors(GNode *gn)
1.1 deraadt 181: {
1.52 espie 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)
1.56 espie 192: Array_PushNew(&toBeMade, succ);
1.52 espie 193: }
1.1 deraadt 194: }
1.25 espie 195:
1.1 deraadt 196: /*-
197: *-----------------------------------------------------------------------
1.25 espie 198: * Make_Update --
1.1 deraadt 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
1.4 millert 201: * up-to-date node.
1.1 deraadt 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: *
1.25 espie 210: * If the child was made, the parent's childMade field will be set true
1.1 deraadt 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
1.35 espie 219: Make_Update(GNode *cgn) /* the child node */
1.1 deraadt 220: {
1.40 espie 221: GNode *pgn; /* the parent node */
1.47 espie 222: LstNode ln; /* Element in parents list */
1.40 espie 223:
1.1 deraadt 224: /*
1.40 espie 225: * If the child was actually made, see what its modification time is
226: * now -- some rules won't actually update the file. If the file still
227: * doesn't exist, make its mtime now.
1.1 deraadt 228: */
1.48 espie 229: if (cgn->built_status != UPTODATE) {
1.40 espie 230: /*
231: * This is what Make does and it's actually a good thing, as it
232: * allows rules like
233: *
234: * cmp -s y.tab.h parse.h || cp y.tab.h parse.h
235: *
1.41 espie 236: * to function as intended. Unfortunately, thanks to the
237: * stateless nature of NFS, there are times when the
238: * modification time of a file created on a remote machine
1.40 espie 239: * will not be modified before the local stat() implied by
1.41 espie 240: * the Dir_MTime occurs, thus leading us to believe that the
241: * file is unchanged, wreaking havoc with files that depend
1.40 espie 242: * on this one.
243: */
1.43 espie 244: if (noExecute || is_out_of_date(Dir_MTime(cgn)))
1.60 espie 245: ts_set_from_now(cgn->mtime);
1.40 espie 246: if (DEBUG(MAKE))
247: printf("update time: %s\n", time_to_string(cgn->mtime));
248: }
249:
1.58 espie 250: /* SIB: this is where I should mark the build as finished */
251: cgn->build_lock = false;
1.40 espie 252: for (ln = Lst_First(&cgn->parents); ln != NULL; ln = Lst_Adv(ln)) {
253: pgn = (GNode *)Lst_Datum(ln);
1.58 espie 254: /* SIB: there should be a siblings loop there */
1.55 espie 255: pgn->unmade--;
1.48 espie 256: if (pgn->must_make) {
1.52 espie 257: if (DEBUG(MAKE))
258: printf("%s--=%d ",
259: pgn->name, pgn->unmade);
1.40 espie 260:
261: if ( ! (cgn->type & (OP_EXEC|OP_USE))) {
1.48 espie 262: if (cgn->built_status == MADE) {
1.40 espie 263: pgn->childMade = true;
1.41 espie 264: if (is_strictly_before(pgn->cmtime,
1.40 espie 265: cgn->mtime))
266: pgn->cmtime = cgn->mtime;
267: } else {
268: (void)Make_TimeStamp(pgn, cgn);
269: }
270: }
271: if (pgn->unmade == 0) {
272: /*
1.41 espie 273: * Queue the node up -- any unmade
274: * predecessors will be dealt with in
1.40 espie 275: * MakeStartJobs.
276: */
1.52 espie 277: if (DEBUG(MAKE))
278: printf("QUEUING ");
1.56 espie 279: Array_Push(&toBeMade, pgn);
1.40 espie 280: } else if (pgn->unmade < 0) {
1.52 espie 281: Error("Child %s discovered graph cycles through %s", cgn->name, pgn->name);
1.40 espie 282: }
283: }
1.1 deraadt 284: }
1.52 espie 285: if (DEBUG(MAKE))
286: printf("\n");
287: requeue_successors(cgn);
1.1 deraadt 288: }
1.25 espie 289:
1.46 espie 290: static bool
291: try_to_make_node(GNode *gn)
292: {
293: if (DEBUG(MAKE))
294: printf("Examining %s...", gn->name);
1.52 espie 295:
296: if (gn->unmade != 0) {
297: if (DEBUG(MAKE))
298: printf(" Requeuing (%d)\n", gn->unmade);
299: add_targets_to_make(&gn->children);
1.56 espie 300: Array_Push(&toBeMade, gn);
1.52 espie 301: return false;
302: }
303: if (has_been_built(gn)) {
304: if (DEBUG(MAKE))
305: printf(" already made\n");
306: return false;
307: }
308: if (has_unmade_predecessor(gn)) {
309: if (DEBUG(MAKE))
310: printf(" Dropping for now\n");
311: return false;
312: }
1.46 espie 313:
1.58 espie 314: /* SIB: this is where there should be a siblings loop */
1.52 espie 315: Suff_FindDeps(gn);
316: if (gn->unmade != 0) {
317: if (DEBUG(MAKE))
318: printf(" Requeuing (after deps: %d)\n", gn->unmade);
319: add_targets_to_make(&gn->children);
320: return false;
1.46 espie 321: }
322: if (Make_OODate(gn)) {
1.58 espie 323: /* SIB: if a sibling is getting built, I don't build it right now */
1.46 espie 324: if (DEBUG(MAKE))
325: printf("out-of-date\n");
326: if (queryFlag)
327: return true;
1.58 espie 328: /* SIB: this is where commands should get prepared */
1.46 espie 329: Make_DoAllVar(gn);
1.58 espie 330: /* SIB: this is where I should make the gn as `being built */
331: gn->build_lock = true;
1.46 espie 332: Job_Make(gn);
333: } else {
334: if (DEBUG(MAKE))
335: printf("up-to-date\n");
1.48 espie 336: gn->built_status = UPTODATE;
1.46 espie 337: if (gn->type & OP_JOIN) {
338: /*
339: * Even for an up-to-date .JOIN node, we need it
340: * to have its context variables so references
341: * to it get the correct value for .TARGET when
342: * building up the context variables of its
343: * parent(s)...
344: */
345: Make_DoAllVar(gn);
346: }
347:
348: Make_Update(gn);
349: }
350: return false;
351: }
352:
1.40 espie 353: /*
1.1 deraadt 354: *-----------------------------------------------------------------------
355: * MakeStartJobs --
356: * Start as many jobs as possible.
357: *
358: * Results:
359: * If the query flag was given to pmake, no job will be started,
360: * but as soon as an out-of-date target is found, this function
1.26 espie 361: * returns true. At all other times, this function returns false.
1.1 deraadt 362: *
363: * Side Effects:
364: * Nodes are removed from the toBeMade queue and job table slots
365: * are filled.
366: *-----------------------------------------------------------------------
367: */
1.26 espie 368: static bool
1.35 espie 369: MakeStartJobs(void)
1.1 deraadt 370: {
1.40 espie 371: GNode *gn;
1.4 millert 372:
1.59 espie 373: while (can_start_job() && (gn = Array_Pop(&toBeMade)) != NULL) {
1.46 espie 374: if (try_to_make_node(gn))
375: return true;
1.1 deraadt 376: }
1.40 espie 377: return false;
1.1 deraadt 378: }
1.25 espie 379:
1.1 deraadt 380: /*-
381: *-----------------------------------------------------------------------
382: * MakePrintStatus --
383: * Print the status of a top-level node, viz. it being up-to-date
384: * already or not created due to an error in a lower level.
385: * Callback function for Make_Run via Lst_ForEach.
1.25 espie 386: *
387: * Side Effects:
388: * A message may be printed.
1.1 deraadt 389: *-----------------------------------------------------------------------
390: */
1.15 espie 391: static void
1.35 espie 392: MakePrintStatus(
393: void *gnp, /* Node to examine */
394: void *cyclep) /* True if gn->unmade being non-zero implies
1.1 deraadt 395: * a cycle in the graph, not an error in an
396: * inferior */
397: {
1.40 espie 398: GNode *gn = (GNode *)gnp;
399: bool cycle = *(bool *)cyclep;
1.48 espie 400: if (gn->built_status == UPTODATE) {
1.40 espie 401: printf("`%s' is up to date.\n", gn->name);
402: } else if (gn->unmade != 0) {
403: if (cycle) {
404: bool t = true;
405: /*
1.41 espie 406: * If printing cycles and came to one that has unmade
407: * children, print out the cycle by recursing on its
1.40 espie 408: * children. Note a cycle like:
409: * a : b
410: * b : c
411: * c : b
1.41 espie 412: * will cause this to erroneously complain about a
1.40 espie 413: * being in the cycle, but this is a good approximation.
414: */
1.48 espie 415: if (gn->built_status == CYCLE) {
1.40 espie 416: Error("Graph cycles through `%s'", gn->name);
1.48 espie 417: gn->built_status = ENDCYCLE;
1.40 espie 418: Lst_ForEach(&gn->children, MakePrintStatus, &t);
1.49 espie 419: gn->built_status = UNKNOWN;
1.48 espie 420: } else if (gn->built_status != ENDCYCLE) {
421: gn->built_status = CYCLE;
1.40 espie 422: Lst_ForEach(&gn->children, MakePrintStatus, &t);
423: }
424: } else {
1.41 espie 425: printf("`%s' not remade because of errors.\n",
1.40 espie 426: gn->name);
427: }
1.1 deraadt 428: }
429: }
1.25 espie 430:
1.5 millert 431:
1.52 espie 432: static void
1.56 espie 433: MakeAddChild(void *to_addp, void *ap)
1.52 espie 434: {
435: GNode *gn = (GNode *)to_addp;
436:
437: if (!gn->must_make && !(gn->type & OP_USE))
1.56 espie 438: Array_Push((struct growableArray *)ap, gn);
1.52 espie 439: }
440:
441: static void
1.58 espie 442: MakeHandleUse(void *cgnp, void *pgnp)
1.52 espie 443: {
1.58 espie 444: GNode *cgn = (GNode *)cgnp;
445: GNode *pgn = (GNode *)pgnp;
446:
447: if (cgn->type & OP_USE)
448: Make_HandleUse(cgn, pgn);
1.52 espie 449: }
450:
451: /* Add stuff to the toBeMade queue. we try to sort things so that stuff
452: * that can be done directly is done right away. This won't be perfect,
453: * since some dependencies are only discovered later (e.g., SuffFindDeps).
1.46 espie 454: */
455: static void
1.52 espie 456: add_targets_to_make(Lst todo)
1.46 espie 457: {
458: GNode *gn;
1.56 espie 459:
1.52 espie 460: unsigned int slot;
461:
1.56 espie 462: AppendList2Array(todo, &examine);
1.46 espie 463:
1.56 espie 464: while ((gn = Array_Pop(&examine)) != NULL) {
1.52 espie 465: if (gn->must_make) /* already known */
466: continue;
467: gn->must_make = true;
1.46 espie 468:
1.52 espie 469: slot = ohash_qlookup(&targets, gn->name);
470: if (!ohash_find(&targets, slot))
471: ohash_insert(&targets, slot, gn);
472:
473:
474: look_harder_for_target(gn);
1.58 espie 475: kludge_look_harder_for_target(gn);
1.52 espie 476: /*
477: * Apply any .USE rules before looking for implicit
478: * dependencies to make sure everything that should have
479: * commands has commands ...
480: */
481: Lst_ForEach(&gn->children, MakeHandleUse, gn);
482: expand_all_children(gn);
1.46 espie 483:
1.52 espie 484: if (gn->unmade != 0) {
485: if (DEBUG(MAKE))
486: printf("%s: not queuing (%d unmade children)\n",
487: gn->name, gn->unmade);
488: Lst_ForEach(&gn->children, MakeAddChild,
489: &examine);
490: } else {
491: if (DEBUG(MAKE))
492: printf("%s: queuing\n", gn->name);
1.56 espie 493: Array_Push(&toBeMade, gn);
1.46 espie 494: }
495: }
1.56 espie 496: if (randomize_queue)
497: randomize_garray(&toBeMade);
1.46 espie 498: }
499:
1.1 deraadt 500: /*-
501: *-----------------------------------------------------------------------
1.6 millert 502: * Make_Run --
503: * Initialize the nodes to remake and the list of nodes which are
504: * ready to be made by doing a breadth-first traversal of the graph
505: * starting from the nodes in the given list. Once this traversal
506: * is finished, all the 'leaves' of the graph are in the toBeMade
507: * queue.
508: * Using this queue and the Job module, work back up the graph,
509: * calling on MakeStartJobs to keep the job table as full as
510: * possible.
511: *
1.1 deraadt 512: * Results:
1.26 espie 513: * true if work was done. false otherwise.
1.1 deraadt 514: *
515: * Side Effects:
1.48 espie 516: * The must_make field of all nodes involved in the creation of the given
1.6 millert 517: * targets is set to 1. The toBeMade list is set to contain all the
518: * 'leaves' of these subgraphs.
1.1 deraadt 519: *-----------------------------------------------------------------------
520: */
1.26 espie 521: bool
1.35 espie 522: Make_Run(Lst targs) /* the initial list of targets */
1.1 deraadt 523: {
1.52 espie 524: int errors; /* Number of errors the Job module reports */
525: GNode *gn;
526: unsigned int i;
527: bool cycle;
1.40 espie 528:
1.54 espie 529: /* wild guess at initial sizes */
1.56 espie 530: Array_Init(&toBeMade, 500);
531: Array_Init(&examine, 150);
1.52 espie 532: ohash_init(&targets, 10, &gnode_info);
1.54 espie 533: if (DEBUG(PARALLEL))
534: random_setup();
1.40 espie 535:
1.46 espie 536: add_targets_to_make(targs);
1.40 espie 537: if (queryFlag) {
538: /*
1.41 espie 539: * We wouldn't do any work unless we could start some jobs in
540: * the next loop... (we won't actually start any, of course,
1.40 espie 541: * this is just to see if any of the targets was out of date)
542: */
543: return MakeStartJobs();
544: } else {
545: /*
546: * Initialization. At the moment, no jobs are running and until
547: * some get started, nothing will happen since the remaining
1.41 espie 548: * upward traversal of the graph is performed by the routines
549: * in job.c upon the finishing of a job. So we fill the Job
1.40 espie 550: * table as much as we can before going into our loop.
551: */
552: (void)MakeStartJobs();
1.1 deraadt 553: }
1.4 millert 554:
1.1 deraadt 555: /*
1.40 espie 556: * Main Loop: The idea here is that the ending of jobs will take
557: * care of the maintenance of data structures and the waiting for output
558: * will cause us to be idle most of the time while our children run as
559: * much as possible. Because the job table is kept as full as possible,
560: * the only time when it will be empty is when all the jobs which need
561: * running have been run, so that is the end condition of this loop.
1.41 espie 562: * Note that the Job module will exit if there were any errors unless
1.40 espie 563: * the keepgoing flag was given.
1.1 deraadt 564: */
1.40 espie 565: while (!Job_Empty()) {
1.57 espie 566: handle_running_jobs();
1.40 espie 567: (void)MakeStartJobs();
568: }
569:
570: errors = Job_Finish();
1.52 espie 571: cycle = false;
1.40 espie 572:
1.52 espie 573: for (gn = ohash_first(&targets, &i); gn != NULL;
574: gn = ohash_next(&targets, &i)) {
575: if (has_been_built(gn))
576: continue;
577: cycle = true;
578: errors++;
579: printf("Error: target %s unaccounted for (%s)\n",
580: gn->name, status_to_string(gn));
581: }
1.1 deraadt 582: /*
1.40 espie 583: * Print the final status of each target. E.g. if it wasn't made
584: * because some inferior reported an error.
1.1 deraadt 585: */
1.52 espie 586: Lst_ForEach(targs, MakePrintStatus, &cycle);
587: if (errors)
588: Fatal("Errors while building");
1.4 millert 589:
1.40 espie 590: return true;
1.1 deraadt 591: }
![[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