File: [local] / src / usr.bin / make / make.c (download)
Revision 1.72, Thu Jun 22 17:08:20 2017 UTC (6 years, 11 months ago) by espie
Branch: MAIN
Changes since 1.71: +125 -60 lines
better display of cycles in -j mode.
lots of tests by krw@
review and comments by pirofti@, more tweaks to come
|
/* $OpenBSD: make.c,v 1.72 2017/06/22 17:08:20 espie Exp $ */
/* $NetBSD: make.c,v 1.10 1996/11/06 17:59:15 christos Exp $ */
/*
* Copyright (c) 1988, 1989, 1990, 1993
* The Regents of the University of California. All rights reserved.
* Copyright (c) 1989 by Berkeley Softworks
* All rights reserved.
*
* This code is derived from software contributed to Berkeley by
* Adam de Boor.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* 3. Neither the name of the University nor the names of its contributors
* may be used to endorse or promote products derived from this software
* without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*/
/*-
* make.c --
* The functions which perform the examination of targets and
* their suitability for creation
*
* Interface:
* Make_Run Initialize things for the module and recreate
* whatever needs recreating. Returns true if
* work was (or would have been) done and
* false
* otherwise.
*
* Make_Update Update all parents of a given child. Performs
* various bookkeeping chores like finding the
* youngest child of the parent, filling
* the IMPSRC context variable, etc. It will
* place the parent on the toBeMade queue if it
* should be.
*
*/
#include <limits.h>
#include <signal.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ohash.h>
#include "config.h"
#include "defines.h"
#include "dir.h"
#include "job.h"
#include "suff.h"
#include "var.h"
#include "error.h"
#include "make.h"
#include "gnode.h"
#include "extern.h"
#include "timestamp.h"
#include "engine.h"
#include "lst.h"
#include "targ.h"
#include "targequiv.h"
#include "garray.h"
#include "memory.h"
/* what gets added each time. Kept as one static array so that it doesn't
* get resized every time.
*/
static struct growableArray examine;
/* The current fringe of the graph. These are nodes which await examination by
* MakeOODate. It is added to by Make_Update and subtracted from by
* MakeStartJobs */
static struct growableArray toBeMade;
/* Hold back on nodes where equivalent stuff is already building... */
static struct growableArray heldBack;
static struct ohash targets; /* stuff we must build */
static void MakeAddChild(void *, void *);
static void MakeHandleUse(void *, void *);
static bool MakeStartJobs(void);
static void MakePrintStatus(void *);
/* Cycle detection functions */
static bool targets_contain_cycles(void);
static void print_unlink_cycle(struct growableArray *, GNode *);
static void break_and_print_cycles(Lst);
static GNode *find_cycle(Lst, struct growableArray *);
static bool try_to_make_node(GNode *);
static void add_targets_to_make(Lst);
static bool has_unmade_predecessor(GNode *);
static void requeue_successors(GNode *);
static void random_setup(void);
static bool randomize_queue;
long random_delay = 0;
bool
no_jobs_left()
{
return Array_IsEmpty(&toBeMade);
}
static void
random_setup()
{
randomize_queue = Var_Definedi("RANDOM_ORDER", NULL);
/* no random delay in the new engine for now */
#if 0
if (Var_Definedi("RANDOM_DELAY", NULL))
random_delay = strtonum(Var_Value("RANDOM_DELAY"), 0, 1000,
NULL) * 1000000;
#endif
}
static void
randomize_garray(struct growableArray *g)
{
/* This is a fairly standard algorithm to randomize an array. */
unsigned int i, v;
GNode *e;
for (i = g->n; i > 0; i--) {
v = arc4random_uniform(i);
if (v == i-1)
continue;
else {
e = g->a[i-1];
g->a[i-1] = g->a[v];
g->a[v] = e;
}
}
}
static bool
has_unmade_predecessor(GNode *gn)
{
LstNode ln;
if (Lst_IsEmpty(&gn->preds))
return false;
for (ln = Lst_First(&gn->preds); ln != NULL; ln = Lst_Adv(ln)) {
GNode *pgn = Lst_Datum(ln);
if (pgn->must_make && pgn->built_status == UNKNOWN) {
if (DEBUG(MAKE))
printf("predecessor %s not made yet.\n",
pgn->name);
return true;
}
}
return false;
}
static void
requeue_successors(GNode *gn)
{
LstNode ln;
/* Deal with successor nodes. If any is marked for making and has an
* unmade count of 0, has not been made and isn't in the examination
* queue, it means we need to place it in the queue as it restrained
* itself before. */
for (ln = Lst_First(&gn->successors); ln != NULL; ln = Lst_Adv(ln)) {
GNode *succ = Lst_Datum(ln);
if (succ->must_make && succ->unmade == 0
&& succ->built_status == UNKNOWN)
Array_PushNew(&toBeMade, succ);
}
}
static void
requeue(GNode *gn)
{
/* this is where we go inside the array and move things around */
unsigned int i, j;
for (i = 0, j = 0; i < heldBack.n; i++, j++) {
if (heldBack.a[i]->watched == gn) {
j--;
heldBack.a[i]->built_status = UNKNOWN;
if (DEBUG(HELDJOBS))
printf("%s finished, releasing: %s\n",
gn->name, heldBack.a[i]->name);
Array_Push(&toBeMade, heldBack.a[i]);
continue;
}
heldBack.a[j] = heldBack.a[i];
}
heldBack.n = j;
}
/*-
*-----------------------------------------------------------------------
* Make_Update --
* Perform update on the parents of a node. Used by JobFinish once
* a node has been dealt with and by MakeStartJobs if it finds an
* up-to-date node.
*
* Results:
* Always returns 0
*
* Side Effects:
* The unmade field of pgn is decremented and pgn may be placed on
* the toBeMade queue if this field becomes 0.
*
* If the child was made, the parent's childMade field will be set to
* true
*-----------------------------------------------------------------------
*/
void
Make_Update(GNode *cgn) /* the child node */
{
GNode *pgn; /* the parent node */
LstNode ln; /* Element in parents list */
/*
* If the child was actually made, see what its modification time is
* now -- some rules won't actually update the file. If the file still
* doesn't exist, make its mtime now.
*/
if (cgn->built_status != UPTODATE) {
/*
* This is what Make does and it's actually a good thing, as it
* allows rules like
*
* cmp -s y.tab.h parse.h || cp y.tab.h parse.h
*
* to function as intended. Unfortunately, thanks to the
* stateless nature of NFS, there are times when the
* modification time of a file created on a remote machine
* will not be modified before the local stat() implied by
* the Dir_MTime occurs, thus leading us to believe that the
* file is unchanged, wreaking havoc with files that depend
* on this one.
*/
if (noExecute || is_out_of_date(Dir_MTime(cgn)))
clock_gettime(CLOCK_REALTIME, &cgn->mtime);
if (DEBUG(MAKE))
printf("update time: %s\n",
time_to_string(&cgn->mtime));
}
requeue(cgn);
/* SIB: this is where I should mark the build as finished */
for (ln = Lst_First(&cgn->parents); ln != NULL; ln = Lst_Adv(ln)) {
pgn = Lst_Datum(ln);
/* SIB: there should be a siblings loop there */
pgn->unmade--;
if (pgn->must_make) {
if (DEBUG(MAKE))
printf("%s--=%d ",
pgn->name, pgn->unmade);
if ( ! (cgn->type & (OP_EXEC|OP_USE))) {
if (cgn->built_status == MADE)
pgn->childMade = true;
(void)Make_TimeStamp(pgn, cgn);
}
if (pgn->unmade == 0) {
/*
* Queue the node up -- any unmade
* predecessors will be dealt with in
* MakeStartJobs.
*/
if (DEBUG(MAKE))
printf("QUEUING ");
Array_Push(&toBeMade, pgn);
} else if (pgn->unmade < 0) {
Error("Child %s discovered graph cycles through %s", cgn->name, pgn->name);
}
}
}
if (DEBUG(MAKE))
printf("\n");
requeue_successors(cgn);
}
static bool
try_to_make_node(GNode *gn)
{
if (DEBUG(MAKE))
printf("Examining %s...", gn->name);
if (gn->built_status == HELDBACK) {
if (DEBUG(HELDJOBS))
printf("%s already held back ???\n", gn->name);
return false;
}
if (gn->unmade != 0) {
if (DEBUG(MAKE))
printf(" Requeuing (%d)\n", gn->unmade);
add_targets_to_make(&gn->children);
Array_Push(&toBeMade, gn);
return false;
}
if (has_been_built(gn)) {
if (DEBUG(MAKE))
printf(" already made\n");
return false;
}
if (has_unmade_predecessor(gn)) {
if (DEBUG(MAKE))
printf(" Dropping for now\n");
return false;
}
/* SIB: this is where there should be a siblings loop */
if (gn->unmade != 0) {
if (DEBUG(MAKE))
printf(" Requeuing (after deps: %d)\n", gn->unmade);
add_targets_to_make(&gn->children);
return false;
}
/* this is where we hold back nodes */
if (gn->groupling != NULL) {
GNode *gn2;
for (gn2 = gn->groupling; gn2 != gn; gn2 = gn2->groupling)
if (gn2->built_status == BUILDING) {
gn->watched = gn2;
gn->built_status = HELDBACK;
if (DEBUG(HELDJOBS))
printf("Holding back job %s, "
"groupling to %s\n",
gn->name, gn2->name);
Array_Push(&heldBack, gn);
return false;
}
}
if (gn->sibling != gn) {
GNode *gn2;
for (gn2 = gn->sibling; gn2 != gn; gn2 = gn2->sibling)
if (gn2->built_status == BUILDING) {
gn->watched = gn2;
gn->built_status = HELDBACK;
if (DEBUG(HELDJOBS))
printf("Holding back job %s, "
"sibling to %s\n",
gn->name, gn2->name);
Array_Push(&heldBack, gn);
return false;
}
}
if (Make_OODate(gn)) {
if (DEBUG(MAKE))
printf("out-of-date\n");
if (queryFlag)
return true;
/* SIB: this is where commands should get prepared */
Make_DoAllVar(gn);
Job_Make(gn);
} else {
if (DEBUG(MAKE))
printf("up-to-date\n");
gn->built_status = UPTODATE;
if (gn->type & OP_JOIN) {
/*
* Even for an up-to-date .JOIN node, we need it
* to have its context variables so references
* to it get the correct value for .TARGET when
* building up the context variables of its
* parent(s)...
*/
Make_DoAllVar(gn);
}
Make_Update(gn);
}
return false;
}
/*
*-----------------------------------------------------------------------
* MakeStartJobs --
* Start as many jobs as possible.
*
* Results:
* If the query flag was given to pmake, no job will be started,
* but as soon as an out-of-date target is found, this function
* returns true. At all other times, this function returns false.
*
* Side Effects:
* Nodes are removed from the toBeMade queue and job table slots
* are filled.
*-----------------------------------------------------------------------
*/
static bool
MakeStartJobs(void)
{
GNode *gn;
while (can_start_job() && (gn = Array_Pop(&toBeMade)) != NULL) {
if (try_to_make_node(gn))
return true;
}
return false;
}
static void
MakePrintStatus(void *gnp)
{
GNode *gn = gnp;
if (gn->built_status == UPTODATE) {
printf("`%s' is up to date.\n", gn->name);
} else if (gn->unmade != 0) {
printf("`%s' not remade because of errors.\n", gn->name);
}
}
static void
MakeAddChild(void *to_addp, void *ap)
{
GNode *gn = to_addp;
struct growableArray *a = ap;
if (!gn->must_make && !(gn->type & OP_USE))
Array_Push(a, gn);
}
static void
MakeHandleUse(void *cgnp, void *pgnp)
{
GNode *cgn = cgnp;
GNode *pgn = pgnp;
if (cgn->type & OP_USE)
Make_HandleUse(cgn, pgn);
}
/* Add stuff to the toBeMade queue. we try to sort things so that stuff
* that can be done directly is done right away. This won't be perfect,
* since some dependencies are only discovered later (e.g., SuffFindDeps).
*/
static void
add_targets_to_make(Lst todo)
{
GNode *gn;
unsigned int slot;
AppendList2Array(todo, &examine);
while ((gn = Array_Pop(&examine)) != NULL) {
if (gn->must_make) /* already known */
continue;
gn->must_make = true;
slot = ohash_qlookup(&targets, gn->name);
if (!ohash_find(&targets, slot))
ohash_insert(&targets, slot, gn);
look_harder_for_target(gn);
kludge_look_harder_for_target(gn);
/*
* Apply any .USE rules before looking for implicit
* dependencies to make sure everything that should have
* commands has commands ...
*/
Lst_ForEach(&gn->children, MakeHandleUse, gn);
Suff_FindDeps(gn);
expand_all_children(gn);
if (gn->unmade != 0) {
if (DEBUG(MAKE))
printf("%s: not queuing (%d unmade children)\n",
gn->name, gn->unmade);
Lst_ForEach(&gn->children, MakeAddChild,
&examine);
} else {
if (DEBUG(MAKE))
printf("%s: queuing\n", gn->name);
Array_Push(&toBeMade, gn);
}
}
if (randomize_queue)
randomize_garray(&toBeMade);
}
/*-
*-----------------------------------------------------------------------
* Make_Run --
* Initialize the nodes to remake and the list of nodes which are
* ready to be made by doing a breadth-first traversal of the graph
* starting from the nodes in the given list. Once this traversal
* is finished, all the 'leaves' of the graph are in the toBeMade
* queue.
* Using this queue and the Job module, work back up the graph,
* calling on MakeStartJobs to keep the job table as full as
* possible.
*
* Results:
* true if work was done. false otherwise.
*
* Side Effects:
* The must_make field of all nodes involved in the creation of the given
* targets is set to 1. The toBeMade list is set to contain all the
* 'leaves' of these subgraphs.
*-----------------------------------------------------------------------
*/
bool
Make_Run(Lst targs) /* the initial list of targets */
{
bool problem; /* errors occurred */
/* wild guess at initial sizes */
Array_Init(&toBeMade, 500);
Array_Init(&examine, 150);
Array_Init(&heldBack, 100);
ohash_init(&targets, 10, &gnode_info);
if (DEBUG(PARALLEL))
random_setup();
add_targets_to_make(targs);
if (queryFlag) {
/*
* We wouldn't do any work unless we could start some jobs in
* the next loop... (we won't actually start any, of course,
* this is just to see if any of the targets was out of date)
*/
return MakeStartJobs();
} else {
/*
* Initialization. At the moment, no jobs are running and until
* some get started, nothing will happen since the remaining
* upward traversal of the graph is performed by the routines
* in job.c upon the finishing of a job. So we fill the Job
* table as much as we can before going into our loop.
*/
(void)MakeStartJobs();
}
/*
* Main Loop: The idea here is that the ending of jobs will take
* care of the maintenance of data structures and the waiting for output
* will cause us to be idle most of the time while our children run as
* much as possible. Because the job table is kept as full as possible,
* the only time when it will be empty is when all the jobs which need
* running have been run, so that is the end condition of this loop.
* Note that the Job module will exit if there were any errors unless
* the keepgoing flag was given.
*/
while (!Job_Empty()) {
handle_running_jobs();
(void)MakeStartJobs();
}
problem = Job_Finish();
/*
* Print the final status of each target. E.g. if it wasn't made
* because some inferior reported an error.
*/
if (targets_contain_cycles()) {
break_and_print_cycles(targs);
problem = true;
}
Lst_Every(targs, MakePrintStatus);
if (problem)
Fatal("Errors while building");
return true;
}
/* round-about detection: assume make is bug-free, if there are targets
* that have not been touched, it means they never were reached, so we can
* look for a cycle
*/
static bool
targets_contain_cycles(void)
{
GNode *gn;
unsigned int i;
bool cycle = false;
bool first = true;
for (gn = ohash_first(&targets, &i); gn != NULL;
gn = ohash_next(&targets, &i)) {
if (has_been_built(gn))
continue;
cycle = true;
if (first)
printf("Error target(s) unaccounted for: ");
printf("%s ", gn->name);
first = false;
}
if (!first)
printf("\n");
return cycle;
}
static void
print_unlink_cycle(struct growableArray *l, GNode *c)
{
LstNode ln;
GNode *gn = NULL;
unsigned int i;
printf("Cycle found: ");
for (i = 0; i != l->n; i++) {
gn = l->a[i];
if (gn == c)
printf("(");
printf("%s -> ", gn->name);
}
printf("%s)\n", c->name);
assert(gn);
/* So the first element is tied to our node, find and kill the link */
for (ln = Lst_First(&gn->children); ln != NULL; ln = Lst_Adv(ln)) {
GNode *gn2 = Lst_Datum(ln);
if (gn2 == c) {
Lst_Remove(&gn->children, ln);
return;
}
}
/* this shouldn't happen ever */
assert(0);
}
/* each call to find_cycle records a cycle in cycle, to break at node c.
* this will stop eventually.
*/
static void
break_and_print_cycles(Lst t)
{
struct growableArray cycle;
Array_Init(&cycle, 16); /* cycles are generally shorter */
while (1) {
GNode *c;
Array_Reset(&cycle);
c = find_cycle(t, &cycle);
if (c)
print_unlink_cycle(&cycle, c);
else
break;
}
free(cycle.a);
}
static GNode *
find_cycle(Lst l, struct growableArray *cycle)
{
LstNode ln;
for (ln = Lst_First(l); ln != NULL; ln = Lst_Adv(ln)) {
GNode *gn = Lst_Datum(ln);
if (gn->in_cycle) {
/* we should print the cycle and not do more */
return gn;
}
if (gn->built_status == UPTODATE)
continue;
if (gn->unmade != 0) {
GNode *c;
gn->in_cycle = true;
Array_Push(cycle, gn);
c = find_cycle(&gn->children, cycle);
gn->in_cycle = false;
if (c)
return c;
Array_Pop(cycle);
}
}
return NULL;
}