GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: usr.bin/make/make.c Lines: 14 230 6.1 %
Date: 2017-11-13 Branches: 9 227 4.0 %

Line Branch Exec Source
1
/*	$OpenBSD: make.c,v 1.73 2017/06/22 17:09:10 espie 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 context variable, etc. It will
54
 *				place the parent on the toBeMade 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 "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
/* 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_unmade_predecessor(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
121
no_jobs_left()
122
{
123
	return Array_IsEmpty(&toBeMade);
124
}
125
126
static void
127
random_setup()
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
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
160
has_unmade_predecessor(GNode *gn)
161
{
162
	LstNode ln;
163
164
	if (Lst_IsEmpty(&gn->preds))
165
		return false;
166
167
168
	for (ln = Lst_First(&gn->preds); 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
182
requeue_successors(GNode *gn)
183
{
184
	LstNode ln;
185
	/* Deal with successor nodes. If any is marked for making and has an
186
	 * unmade count of 0, has not been made and isn't in the examination
187
	 * queue, it means we need to place it in the queue as it restrained
188
	 * itself before.	*/
189
753
	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->unmade == 0
193
		    && succ->built_status == UNKNOWN)
194
			Array_PushNew(&toBeMade, succ);
195
	}
196
251
}
197
198
static void
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
753
	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(&toBeMade, heldBack.a[i]);
212
			continue;
213
		}
214
		heldBack.a[j] = heldBack.a[i];
215
	}
216
251
	heldBack.n = j;
217
251
}
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 unmade field of pgn is decremented and pgn may be placed on
231
 *	the toBeMade queue if this field becomes 0.
232
 *
233
 *	If the child was made, the parent's childMade field will be set to
234
 *	true
235
 *-----------------------------------------------------------------------
236
 */
237
void
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
502
	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

753
		if (noExecute || is_out_of_date(Dir_MTime(cgn)))
264
251
			clock_gettime(CLOCK_REALTIME, &cgn->mtime);
265
251
		if (DEBUG(MAKE))
266
			printf("update time: %s\n",
267
			    time_to_string(&cgn->mtime));
268
	}
269
270
251
	requeue(cgn);
271
	/* SIB: this is where I should mark the build as finished */
272
502
	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->unmade--;
276
		if (pgn->must_make) {
277
			if (DEBUG(MAKE))
278
				printf("%s--=%d ",
279
				    pgn->name, pgn->unmade);
280
281
			if ( ! (cgn->type & (OP_EXEC|OP_USE))) {
282
				if (cgn->built_status == MADE)
283
					pgn->childMade = true;
284
				(void)Make_TimeStamp(pgn, cgn);
285
			}
286
			if (pgn->unmade == 0) {
287
				/*
288
				 * Queue the node up -- any unmade
289
				 * predecessors will be dealt with in
290
				 * MakeStartJobs.
291
				 */
292
				if (DEBUG(MAKE))
293
					printf("QUEUING ");
294
				Array_Push(&toBeMade, pgn);
295
			} else if (pgn->unmade < 0) {
296
				Error("Child %s discovered graph cycles through %s", cgn->name, pgn->name);
297
			}
298
		}
299
	}
300
251
	if (DEBUG(MAKE))
301
		printf("\n");
302
251
	requeue_successors(cgn);
303
251
}
304
305
static bool
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->unmade != 0) {
318
		if (DEBUG(MAKE))
319
			printf(" Requeuing (%d)\n", gn->unmade);
320
		add_targets_to_make(&gn->children);
321
		Array_Push(&toBeMade, 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_unmade_predecessor(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->unmade != 0) {
337
		if (DEBUG(MAKE))
338
			printf(" Requeuing (after deps: %d)\n", gn->unmade);
339
		add_targets_to_make(&gn->children);
340
		return false;
341
	}
342
	/* this is where we hold back nodes */
343
	if (gn->groupling != NULL) {
344
		GNode *gn2;
345
		for (gn2 = gn->groupling; gn2 != gn; gn2 = gn2->groupling)
346
			if (gn2->built_status == BUILDING) {
347
				gn->watched = gn2;
348
				gn->built_status = HELDBACK;
349
				if (DEBUG(HELDJOBS))
350
					printf("Holding back job %s, "
351
					    "groupling to %s\n",
352
					    gn->name, gn2->name);
353
				Array_Push(&heldBack, gn);
354
				return false;
355
			}
356
	}
357
	if (gn->sibling != gn) {
358
		GNode *gn2;
359
		for (gn2 = gn->sibling; gn2 != gn; gn2 = gn2->sibling)
360
			if (gn2->built_status == BUILDING) {
361
				gn->watched = gn2;
362
				gn->built_status = HELDBACK;
363
				if (DEBUG(HELDJOBS))
364
					printf("Holding back job %s, "
365
					    "sibling to %s\n",
366
					    gn->name, gn2->name);
367
				Array_Push(&heldBack, gn);
368
				return false;
369
			}
370
	}
371
	if (Make_OODate(gn)) {
372
		if (DEBUG(MAKE))
373
			printf("out-of-date\n");
374
		if (queryFlag)
375
			return true;
376
		/* SIB: this is where commands should get prepared */
377
		Make_DoAllVar(gn);
378
		Job_Make(gn);
379
	} else {
380
		if (DEBUG(MAKE))
381
			printf("up-to-date\n");
382
		gn->built_status = UPTODATE;
383
		if (gn->type & OP_JOIN) {
384
			/*
385
			 * Even for an up-to-date .JOIN node, we need it
386
			 * to have its context variables so references
387
			 * to it get the correct value for .TARGET when
388
			 * building up the context variables of its
389
			 * parent(s)...
390
			 */
391
			Make_DoAllVar(gn);
392
		}
393
394
		Make_Update(gn);
395
	}
396
	return false;
397
}
398
399
/*
400
 *-----------------------------------------------------------------------
401
 * MakeStartJobs --
402
 *	Start as many jobs as possible.
403
 *
404
 * Results:
405
 *	If the query flag was given to pmake, no job will be started,
406
 *	but as soon as an out-of-date target is found, this function
407
 *	returns true. At all other times, this function returns false.
408
 *
409
 * Side Effects:
410
 *	Nodes are removed from the toBeMade queue and job table slots
411
 *	are filled.
412
 *-----------------------------------------------------------------------
413
 */
414
static bool
415
MakeStartJobs(void)
416
{
417
	GNode	*gn;
418
419
	while (can_start_job() && (gn = Array_Pop(&toBeMade)) != NULL) {
420
		if (try_to_make_node(gn))
421
			return true;
422
	}
423
	return false;
424
}
425
426
static void
427
MakePrintStatus(void *gnp)
428
{
429
	GNode	*gn = gnp;
430
	if (gn->built_status == UPTODATE) {
431
		printf("`%s' is up to date.\n", gn->name);
432
	} else if (gn->unmade != 0) {
433
		printf("`%s' not remade because of errors.\n", gn->name);
434
	}
435
}
436
437
static void
438
MakeAddChild(void *to_addp, void *ap)
439
{
440
	GNode *gn = to_addp;
441
	struct growableArray *a = ap;
442
443
	if (!gn->must_make && !(gn->type & OP_USE))
444
		Array_Push(a, gn);
445
}
446
447
static void
448
MakeHandleUse(void *cgnp, void *pgnp)
449
{
450
	GNode *cgn = cgnp;
451
	GNode *pgn = pgnp;
452
453
	if (cgn->type & OP_USE)
454
		Make_HandleUse(cgn, pgn);
455
}
456
457
/* Add stuff to the toBeMade queue. we try to sort things so that stuff
458
 * that can be done directly is done right away.  This won't be perfect,
459
 * since some dependencies are only discovered later (e.g., SuffFindDeps).
460
 */
461
static void
462
add_targets_to_make(Lst todo)
463
{
464
	GNode *gn;
465
466
	unsigned int slot;
467
468
	AppendList2Array(todo, &examine);
469
470
	while ((gn = Array_Pop(&examine)) != NULL) {
471
		if (gn->must_make) 	/* already known */
472
			continue;
473
		gn->must_make = true;
474
475
		slot = ohash_qlookup(&targets, gn->name);
476
		if (!ohash_find(&targets, slot))
477
			ohash_insert(&targets, slot, gn);
478
479
480
		look_harder_for_target(gn);
481
		kludge_look_harder_for_target(gn);
482
		/*
483
		 * Apply any .USE rules before looking for implicit
484
		 * dependencies to make sure everything that should have
485
		 * commands has commands ...
486
		 */
487
		Lst_ForEach(&gn->children, MakeHandleUse, gn);
488
		Suff_FindDeps(gn);
489
		expand_all_children(gn);
490
491
		if (gn->unmade != 0) {
492
			if (DEBUG(MAKE))
493
				printf("%s: not queuing (%d unmade children)\n",
494
				    gn->name, gn->unmade);
495
			Lst_ForEach(&gn->children, MakeAddChild,
496
			    &examine);
497
		} else {
498
			if (DEBUG(MAKE))
499
				printf("%s: queuing\n", gn->name);
500
			Array_Push(&toBeMade, gn);
501
		}
502
	}
503
	if (randomize_queue)
504
		randomize_garray(&toBeMade);
505
}
506
507
/*-
508
 *-----------------------------------------------------------------------
509
 * Make_Run --
510
 *	Initialize the nodes to remake and the list of nodes which are
511
 *	ready to be made by doing a breadth-first traversal of the graph
512
 *	starting from the nodes in the given list. Once this traversal
513
 *	is finished, all the 'leaves' of the graph are in the toBeMade
514
 *	queue.
515
 *	Using this queue and the Job module, work back up the graph,
516
 *	calling on MakeStartJobs to keep the job table as full as
517
 *	possible.
518
 *
519
 * Results:
520
 *	true if work was done. false otherwise.
521
 *
522
 * Side Effects:
523
 *	The must_make field of all nodes involved in the creation of the given
524
 *	targets is set to 1. The toBeMade list is set to contain all the
525
 *	'leaves' of these subgraphs.
526
 *-----------------------------------------------------------------------
527
 */
528
bool
529
Make_Run(Lst targs)		/* the initial list of targets */
530
{
531
	bool problem;	/* errors occurred */
532
533
	/* wild guess at initial sizes */
534
	Array_Init(&toBeMade, 500);
535
	Array_Init(&examine, 150);
536
	Array_Init(&heldBack, 100);
537
	ohash_init(&targets, 10, &gnode_info);
538
	if (DEBUG(PARALLEL))
539
		random_setup();
540
541
	add_targets_to_make(targs);
542
	if (queryFlag) {
543
		/*
544
		 * We wouldn't do any work unless we could start some jobs in
545
		 * the next loop... (we won't actually start any, of course,
546
		 * this is just to see if any of the targets was out of date)
547
		 */
548
		return MakeStartJobs();
549
	} else {
550
		/*
551
		 * Initialization. At the moment, no jobs are running and until
552
		 * some get started, nothing will happen since the remaining
553
		 * upward traversal of the graph is performed by the routines
554
		 * in job.c upon the finishing of a job. So we fill the Job
555
		 * table as much as we can before going into our loop.
556
		 */
557
		(void)MakeStartJobs();
558
	}
559
560
	/*
561
	 * Main Loop: The idea here is that the ending of jobs will take
562
	 * care of the maintenance of data structures and the waiting for output
563
	 * will cause us to be idle most of the time while our children run as
564
	 * much as possible. Because the job table is kept as full as possible,
565
	 * the only time when it will be empty is when all the jobs which need
566
	 * running have been run, so that is the end condition of this loop.
567
	 * Note that the Job module will exit if there were any errors unless
568
	 * the keepgoing flag was given.
569
	 */
570
	while (!Job_Empty()) {
571
		handle_running_jobs();
572
		(void)MakeStartJobs();
573
	}
574
575
	problem = Job_Finish();
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
		problem = true;
584
	}
585
	Lst_Every(targs, MakePrintStatus);
586
	if (problem)
587
		Fatal("Errors while building");
588
589
	return true;
590
}
591
592
/* round-about detection: assume make is bug-free, if there are targets
593
 * that have not been touched, it means they never were reached, so we can
594
 * look for a cycle
595
 */
596
static bool
597
targets_contain_cycles(void)
598
{
599
	GNode *gn;
600
	unsigned int i;
601
	bool cycle = false;
602
	bool first = true;
603
604
	for (gn = ohash_first(&targets, &i); gn != NULL;
605
	    gn = ohash_next(&targets, &i)) {
606
	    	if (has_been_built(gn))
607
			continue;
608
		cycle = true;
609
		if (first)
610
			printf("Error target(s) unaccounted for: ");
611
		printf("%s ", gn->name);
612
		first = false;
613
	}
614
	if (!first)
615
		printf("\n");
616
	return cycle;
617
}
618
619
static void
620
print_unlink_cycle(struct growableArray *l, GNode *c)
621
{
622
	LstNode ln;
623
	GNode *gn = NULL;
624
	unsigned int i;
625
626
	printf("Cycle found: ");
627
628
	for (i = 0; i != l->n; i++) {
629
		gn = l->a[i];
630
		if (gn == c)
631
			printf("(");
632
		printf("%s -> ", gn->name);
633
	}
634
	printf("%s)\n", c->name);
635
	assert(gn);
636
637
	/* So the first element is tied to our node, find and kill the link */
638
	for (ln = Lst_First(&gn->children); ln != NULL; ln = Lst_Adv(ln)) {
639
		GNode *gn2 = Lst_Datum(ln);
640
		if (gn2 == c) {
641
			Lst_Remove(&gn->children, ln);
642
			return;
643
		}
644
	}
645
	/* this shouldn't happen ever */
646
	assert(0);
647
}
648
649
/* each call to find_cycle records a cycle in cycle, to break at node c.
650
 * this will stop eventually.
651
 */
652
static void
653
break_and_print_cycles(Lst t)
654
{
655
	struct growableArray cycle;
656
657
	Array_Init(&cycle, 16); /* cycles are generally shorter */
658
	while (1) {
659
		GNode *c;
660
661
		Array_Reset(&cycle);
662
		c = find_cycle(t, &cycle);
663
		if (c)
664
			print_unlink_cycle(&cycle, c);
665
		else
666
			break;
667
	}
668
	free(cycle.a);
669
}
670
671
672
static GNode *
673
find_cycle(Lst l, struct growableArray *cycle)
674
{
675
	LstNode ln;
676
677
	for (ln = Lst_First(l); ln != NULL; ln = Lst_Adv(ln)) {
678
		GNode *gn = Lst_Datum(ln);
679
		if (gn->in_cycle) {
680
			/* we should print the cycle and not do more */
681
			return gn;
682
		}
683
684
		if (gn->built_status == UPTODATE)
685
			continue;
686
		if (gn->unmade != 0) {
687
			GNode *c;
688
689
			gn->in_cycle = true;
690
			Array_Push(cycle, gn);
691
			c = find_cycle(&gn->children, cycle);
692
			gn->in_cycle = false;
693
			if (c)
694
				return c;
695
			Array_Pop(cycle);
696
		}
697
	}
698
	return NULL;
699
}