[BACK]Return to make.c CVS log [TXT][DIR] Up to [local] / src / usr.bin / make

Annotation of src/usr.bin/make/make.c, Revision 1.68

1.68    ! espie       1: /*     $OpenBSD: make.c,v 1.67 2013/05/22 12:14:08 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
1.67      espie      51:  *                             various bookkeeping chores like finding the
                     52:  *                             youngest child of the parent, filling
                     53:  *                             the IMPSRC context variable, etc. It will
1.25      espie      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.43      espie      60: #include <signal.h>
1.52      espie      61: #include <stddef.h>
1.66      espie      62: #include <stdint.h>
                     63: #include <stdio.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.64      espie      94: /* Hold back on nodes where equivalent stuff is already building... */
                     95: static struct growableArray heldBack;
                     96:
1.52      espie      97: static struct ohash targets;   /* stuff we must build */
1.1       deraadt    98:
1.25      espie      99: static void MakeAddChild(void *, void *);
                    100: static void MakeHandleUse(void *, void *);
1.26      espie     101: static bool MakeStartJobs(void);
1.25      espie     102: static void MakePrintStatus(void *, void *);
1.46      espie     103: static bool try_to_make_node(GNode *);
                    104: static void add_targets_to_make(Lst);
1.40      espie     105:
1.52      espie     106: static bool has_unmade_predecessor(GNode *);
                    107: static void requeue_successors(GNode *);
1.54      espie     108: static void random_setup(void);
                    109:
                    110: static bool randomize_queue;
                    111: long random_delay = 0;
                    112:
1.56      espie     113: bool
                    114: no_jobs_left()
                    115: {
                    116:        return Array_IsEmpty(&toBeMade);
                    117: }
                    118:
1.54      espie     119: static void
                    120: random_setup()
                    121: {
                    122:        randomize_queue = Var_Definedi("RANDOM_ORDER", NULL);
                    123:
1.67      espie     124: /* no random delay in the new engine for now */
                    125: #if 0
1.54      espie     126:        if (Var_Definedi("RANDOM_DELAY", NULL))
                    127:                random_delay = strtonum(Var_Value("RANDOM_DELAY"), 0, 1000,
                    128:                    NULL) * 1000000;
1.67      espie     129: #endif
1.54      espie     130:
                    131: }
1.52      espie     132:
1.56      espie     133: static void
                    134: randomize_garray(struct growableArray *g)
                    135: {
                    136:        /* This is a fairly standard algorithm to randomize an array. */
                    137:        unsigned int i, v;
                    138:        GNode *e;
                    139:
                    140:        for (i = g->n; i > 0; i--) {
1.67      espie     141:                v = arc4random_uniform(i);
1.56      espie     142:                if (v == i-1)
                    143:                        continue;
                    144:                else {
                    145:                        e = g->a[i-1];
                    146:                        g->a[i-1] = g->a[v];
                    147:                        g->a[v] = e;
                    148:                }
                    149:        }
                    150: }
                    151:
1.52      espie     152: static bool
                    153: has_unmade_predecessor(GNode *gn)
1.1       deraadt   154: {
1.52      espie     155:        LstNode ln;
                    156:
                    157:        if (Lst_IsEmpty(&gn->preds))
                    158:                return false;
1.5       millert   159:
1.52      espie     160:
                    161:        for (ln = Lst_First(&gn->preds); ln != NULL; ln = Lst_Adv(ln)) {
                    162:                GNode   *pgn = (GNode *)Lst_Datum(ln);
                    163:
                    164:                if (pgn->must_make && pgn->built_status == UNKNOWN) {
                    165:                        if (DEBUG(MAKE))
                    166:                                printf("predecessor %s not made yet.\n",
                    167:                                    pgn->name);
                    168:                        return true;
                    169:                }
                    170:        }
                    171:        return false;
1.1       deraadt   172: }
1.25      espie     173:
1.15      espie     174: static void
1.52      espie     175: requeue_successors(GNode *gn)
1.1       deraadt   176: {
1.52      espie     177:        LstNode ln;
                    178:        /* Deal with successor nodes. If any is marked for making and has an
                    179:         * unmade count of 0, has not been made and isn't in the examination
                    180:         * queue, it means we need to place it in the queue as it restrained
                    181:         * itself before.       */
                    182:        for (ln = Lst_First(&gn->successors); ln != NULL; ln = Lst_Adv(ln)) {
                    183:                GNode   *succ = (GNode *)Lst_Datum(ln);
                    184:
                    185:                if (succ->must_make && succ->unmade == 0
                    186:                    && succ->built_status == UNKNOWN)
1.56      espie     187:                        Array_PushNew(&toBeMade, succ);
1.52      espie     188:        }
1.1       deraadt   189: }
1.25      espie     190:
1.64      espie     191: static void
                    192: requeue(GNode *gn)
                    193: {
                    194:        /* this is where we go inside the array and move things around */
                    195:        unsigned int i, j;
                    196:
                    197:        for (i = 0, j = 0; i < heldBack.n; i++, j++) {
                    198:                if (heldBack.a[i]->watched == gn) {
                    199:                        j--;
                    200:                        heldBack.a[i]->built_status = UNKNOWN;
                    201:                        if (DEBUG(HELDJOBS))
                    202:                                printf("%s finished, releasing: %s\n",
                    203:                                    gn->name, heldBack.a[i]->name);
                    204:                        Array_Push(&toBeMade, heldBack.a[i]);
                    205:                        continue;
                    206:                }
                    207:                heldBack.a[j] = heldBack.a[i];
                    208:        }
                    209:        heldBack.n = j;
                    210: }
                    211:
1.1       deraadt   212: /*-
                    213:  *-----------------------------------------------------------------------
1.25      espie     214:  * Make_Update --
1.1       deraadt   215:  *     Perform update on the parents of a node. Used by JobFinish once
                    216:  *     a node has been dealt with and by MakeStartJobs if it finds an
1.4       millert   217:  *     up-to-date node.
1.1       deraadt   218:  *
                    219:  * Results:
                    220:  *     Always returns 0
                    221:  *
                    222:  * Side Effects:
                    223:  *     The unmade field of pgn is decremented and pgn may be placed on
                    224:  *     the toBeMade queue if this field becomes 0.
                    225:  *
1.67      espie     226:  *     If the child was made, the parent's childMade field will be set to
                    227:  *     true
1.1       deraadt   228:  *-----------------------------------------------------------------------
                    229:  */
                    230: void
1.35      espie     231: Make_Update(GNode *cgn)        /* the child node */
1.1       deraadt   232: {
1.40      espie     233:        GNode   *pgn;   /* the parent node */
1.47      espie     234:        LstNode ln;     /* Element in parents list */
1.40      espie     235:
1.1       deraadt   236:        /*
1.40      espie     237:         * If the child was actually made, see what its modification time is
                    238:         * now -- some rules won't actually update the file. If the file still
                    239:         * doesn't exist, make its mtime now.
1.1       deraadt   240:         */
1.48      espie     241:        if (cgn->built_status != UPTODATE) {
1.40      espie     242:                /*
                    243:                 * This is what Make does and it's actually a good thing, as it
                    244:                 * allows rules like
                    245:                 *
                    246:                 *      cmp -s y.tab.h parse.h || cp y.tab.h parse.h
                    247:                 *
1.41      espie     248:                 * to function as intended. Unfortunately, thanks to the
                    249:                 * stateless nature of NFS, there are times when the
                    250:                 * modification time of a file created on a remote machine
1.40      espie     251:                 * will not be modified before the local stat() implied by
1.41      espie     252:                 * the Dir_MTime occurs, thus leading us to believe that the
                    253:                 * file is unchanged, wreaking havoc with files that depend
1.40      espie     254:                 * on this one.
                    255:                 */
1.43      espie     256:                if (noExecute || is_out_of_date(Dir_MTime(cgn)))
1.67      espie     257:                        clock_gettime(CLOCK_REALTIME, &cgn->mtime);
1.40      espie     258:                if (DEBUG(MAKE))
1.67      espie     259:                        printf("update time: %s\n",
                    260:                            time_to_string(&cgn->mtime));
1.40      espie     261:        }
                    262:
1.64      espie     263:        requeue(cgn);
1.58      espie     264:        /* SIB: this is where I should mark the build as finished */
1.40      espie     265:        for (ln = Lst_First(&cgn->parents); ln != NULL; ln = Lst_Adv(ln)) {
                    266:                pgn = (GNode *)Lst_Datum(ln);
1.58      espie     267:                /* SIB: there should be a siblings loop there */
1.55      espie     268:                pgn->unmade--;
1.48      espie     269:                if (pgn->must_make) {
1.52      espie     270:                        if (DEBUG(MAKE))
                    271:                                printf("%s--=%d ",
                    272:                                    pgn->name, pgn->unmade);
1.40      espie     273:
                    274:                        if ( ! (cgn->type & (OP_EXEC|OP_USE))) {
1.63      guenther  275:                                if (cgn->built_status == MADE)
1.40      espie     276:                                        pgn->childMade = true;
1.63      guenther  277:                                (void)Make_TimeStamp(pgn, cgn);
1.40      espie     278:                        }
                    279:                        if (pgn->unmade == 0) {
                    280:                                /*
1.41      espie     281:                                 * Queue the node up -- any unmade
                    282:                                 * predecessors will be dealt with in
1.40      espie     283:                                 * MakeStartJobs.
                    284:                                 */
1.52      espie     285:                                if (DEBUG(MAKE))
                    286:                                        printf("QUEUING ");
1.56      espie     287:                                Array_Push(&toBeMade, pgn);
1.40      espie     288:                        } else if (pgn->unmade < 0) {
1.52      espie     289:                                Error("Child %s discovered graph cycles through %s", cgn->name, pgn->name);
1.40      espie     290:                        }
                    291:                }
1.1       deraadt   292:        }
1.52      espie     293:        if (DEBUG(MAKE))
                    294:                printf("\n");
                    295:        requeue_successors(cgn);
1.1       deraadt   296: }
1.25      espie     297:
1.46      espie     298: static bool
                    299: try_to_make_node(GNode *gn)
                    300: {
                    301:        if (DEBUG(MAKE))
                    302:                printf("Examining %s...", gn->name);
1.52      espie     303:
1.64      espie     304:        if (gn->built_status == HELDBACK) {
                    305:                if (DEBUG(HELDJOBS))
                    306:                        printf("%s already held back ???\n", gn->name);
                    307:                return false;
                    308:        }
                    309:
1.52      espie     310:        if (gn->unmade != 0) {
                    311:                if (DEBUG(MAKE))
                    312:                        printf(" Requeuing (%d)\n", gn->unmade);
                    313:                add_targets_to_make(&gn->children);
1.56      espie     314:                Array_Push(&toBeMade, gn);
1.52      espie     315:                return false;
                    316:        }
                    317:        if (has_been_built(gn)) {
                    318:                if (DEBUG(MAKE))
                    319:                        printf(" already made\n");
                    320:                        return false;
                    321:        }
                    322:        if (has_unmade_predecessor(gn)) {
                    323:                if (DEBUG(MAKE))
                    324:                        printf(" Dropping for now\n");
                    325:                return false;
                    326:        }
1.46      espie     327:
1.58      espie     328:        /* SIB: this is where there should be a siblings loop */
1.52      espie     329:        if (gn->unmade != 0) {
                    330:                if (DEBUG(MAKE))
                    331:                        printf(" Requeuing (after deps: %d)\n", gn->unmade);
                    332:                add_targets_to_make(&gn->children);
                    333:                return false;
1.46      espie     334:        }
1.64      espie     335:        /* this is where we hold back nodes */
                    336:        if (gn->groupling != NULL) {
                    337:                GNode *gn2;
                    338:                for (gn2 = gn->groupling; gn2 != gn; gn2 = gn2->groupling)
                    339:                        if (gn2->built_status == BUILDING) {
                    340:                                gn->watched = gn2;
                    341:                                gn->built_status = HELDBACK;
                    342:                                if (DEBUG(HELDJOBS))
                    343:                                        printf("Holding back job %s, "
                    344:                                            "groupling to %s\n",
                    345:                                            gn->name, gn2->name);
                    346:                                Array_Push(&heldBack, gn);
                    347:                                return false;
                    348:                        }
                    349:        }
                    350:        if (gn->sibling != gn) {
                    351:                GNode *gn2;
                    352:                for (gn2 = gn->sibling; gn2 != gn; gn2 = gn2->sibling)
                    353:                        if (gn2->built_status == BUILDING) {
                    354:                                gn->watched = gn2;
                    355:                                gn->built_status = HELDBACK;
                    356:                                if (DEBUG(HELDJOBS))
                    357:                                        printf("Holding back job %s, "
                    358:                                            "sibling to %s\n",
                    359:                                            gn->name, gn2->name);
                    360:                                Array_Push(&heldBack, gn);
                    361:                                return false;
                    362:                        }
                    363:        }
1.46      espie     364:        if (Make_OODate(gn)) {
                    365:                if (DEBUG(MAKE))
                    366:                        printf("out-of-date\n");
                    367:                if (queryFlag)
                    368:                        return true;
1.58      espie     369:                /* SIB: this is where commands should get prepared */
1.46      espie     370:                Make_DoAllVar(gn);
                    371:                Job_Make(gn);
                    372:        } else {
                    373:                if (DEBUG(MAKE))
                    374:                        printf("up-to-date\n");
1.48      espie     375:                gn->built_status = UPTODATE;
1.46      espie     376:                if (gn->type & OP_JOIN) {
                    377:                        /*
                    378:                         * Even for an up-to-date .JOIN node, we need it
                    379:                         * to have its context variables so references
                    380:                         * to it get the correct value for .TARGET when
                    381:                         * building up the context variables of its
                    382:                         * parent(s)...
                    383:                         */
                    384:                        Make_DoAllVar(gn);
                    385:                }
                    386:
                    387:                Make_Update(gn);
                    388:        }
                    389:        return false;
                    390: }
                    391:
1.40      espie     392: /*
1.1       deraadt   393:  *-----------------------------------------------------------------------
                    394:  * MakeStartJobs --
                    395:  *     Start as many jobs as possible.
                    396:  *
                    397:  * Results:
                    398:  *     If the query flag was given to pmake, no job will be started,
                    399:  *     but as soon as an out-of-date target is found, this function
1.26      espie     400:  *     returns true. At all other times, this function returns false.
1.1       deraadt   401:  *
                    402:  * Side Effects:
                    403:  *     Nodes are removed from the toBeMade queue and job table slots
                    404:  *     are filled.
                    405:  *-----------------------------------------------------------------------
                    406:  */
1.26      espie     407: static bool
1.35      espie     408: MakeStartJobs(void)
1.1       deraadt   409: {
1.40      espie     410:        GNode   *gn;
1.4       millert   411:
1.59      espie     412:        while (can_start_job() && (gn = Array_Pop(&toBeMade)) != NULL) {
1.46      espie     413:                if (try_to_make_node(gn))
                    414:                        return true;
1.1       deraadt   415:        }
1.40      espie     416:        return false;
1.1       deraadt   417: }
1.25      espie     418:
1.1       deraadt   419: /*-
                    420:  *-----------------------------------------------------------------------
                    421:  * MakePrintStatus --
                    422:  *     Print the status of a top-level node, viz. it being up-to-date
                    423:  *     already or not created due to an error in a lower level.
                    424:  *     Callback function for Make_Run via Lst_ForEach.
1.25      espie     425:  *
                    426:  * Side Effects:
                    427:  *     A message may be printed.
1.1       deraadt   428:  *-----------------------------------------------------------------------
                    429:  */
1.15      espie     430: static void
1.35      espie     431: MakePrintStatus(
                    432:     void *gnp,             /* Node to examine */
                    433:     void *cyclep)          /* True if gn->unmade being non-zero implies
1.1       deraadt   434:                             * a cycle in the graph, not an error in an
                    435:                             * inferior */
                    436: {
1.40      espie     437:        GNode   *gn = (GNode *)gnp;
                    438:        bool    cycle = *(bool *)cyclep;
1.48      espie     439:        if (gn->built_status == UPTODATE) {
1.40      espie     440:                printf("`%s' is up to date.\n", gn->name);
                    441:        } else if (gn->unmade != 0) {
                    442:                if (cycle) {
                    443:                        bool t = true;
                    444:                        /*
1.41      espie     445:                         * If printing cycles and came to one that has unmade
                    446:                         * children, print out the cycle by recursing on its
1.40      espie     447:                         * children. Note a cycle like:
                    448:                         *      a : b
                    449:                         *      b : c
                    450:                         *      c : b
1.41      espie     451:                         * will cause this to erroneously complain about a
1.40      espie     452:                         * being in the cycle, but this is a good approximation.
                    453:                         */
1.48      espie     454:                        if (gn->built_status == CYCLE) {
1.40      espie     455:                                Error("Graph cycles through `%s'", gn->name);
1.48      espie     456:                                gn->built_status = ENDCYCLE;
1.40      espie     457:                                Lst_ForEach(&gn->children, MakePrintStatus, &t);
1.49      espie     458:                                gn->built_status = UNKNOWN;
1.48      espie     459:                        } else if (gn->built_status != ENDCYCLE) {
                    460:                                gn->built_status = CYCLE;
1.40      espie     461:                                Lst_ForEach(&gn->children, MakePrintStatus, &t);
                    462:                        }
                    463:                } else {
1.41      espie     464:                        printf("`%s' not remade because of errors.\n",
1.40      espie     465:                            gn->name);
                    466:                }
1.1       deraadt   467:        }
                    468: }
1.25      espie     469:
1.5       millert   470:
1.52      espie     471: static void
1.56      espie     472: MakeAddChild(void *to_addp, void *ap)
1.52      espie     473: {
                    474:        GNode *gn = (GNode *)to_addp;
                    475:
                    476:        if (!gn->must_make && !(gn->type & OP_USE))
1.56      espie     477:                Array_Push((struct growableArray *)ap, gn);
1.52      espie     478: }
                    479:
                    480: static void
1.58      espie     481: MakeHandleUse(void *cgnp, void *pgnp)
1.52      espie     482: {
1.58      espie     483:        GNode *cgn = (GNode *)cgnp;
                    484:        GNode *pgn = (GNode *)pgnp;
                    485:
                    486:        if (cgn->type & OP_USE)
                    487:                Make_HandleUse(cgn, pgn);
1.52      espie     488: }
                    489:
                    490: /* Add stuff to the toBeMade queue. we try to sort things so that stuff
                    491:  * that can be done directly is done right away.  This won't be perfect,
                    492:  * since some dependencies are only discovered later (e.g., SuffFindDeps).
1.46      espie     493:  */
                    494: static void
1.52      espie     495: add_targets_to_make(Lst todo)
1.46      espie     496: {
                    497:        GNode *gn;
1.56      espie     498:
1.52      espie     499:        unsigned int slot;
                    500:
1.56      espie     501:        AppendList2Array(todo, &examine);
1.46      espie     502:
1.56      espie     503:        while ((gn = Array_Pop(&examine)) != NULL) {
1.52      espie     504:                if (gn->must_make)      /* already known */
                    505:                        continue;
                    506:                gn->must_make = true;
1.46      espie     507:
1.52      espie     508:                slot = ohash_qlookup(&targets, gn->name);
                    509:                if (!ohash_find(&targets, slot))
                    510:                        ohash_insert(&targets, slot, gn);
                    511:
                    512:
                    513:                look_harder_for_target(gn);
1.58      espie     514:                kludge_look_harder_for_target(gn);
1.52      espie     515:                /*
                    516:                 * Apply any .USE rules before looking for implicit
                    517:                 * dependencies to make sure everything that should have
                    518:                 * commands has commands ...
                    519:                 */
                    520:                Lst_ForEach(&gn->children, MakeHandleUse, gn);
1.68    ! espie     521:                Suff_FindDeps(gn);
1.52      espie     522:                expand_all_children(gn);
1.46      espie     523:
1.52      espie     524:                if (gn->unmade != 0) {
                    525:                        if (DEBUG(MAKE))
                    526:                                printf("%s: not queuing (%d unmade children)\n",
                    527:                                    gn->name, gn->unmade);
                    528:                        Lst_ForEach(&gn->children, MakeAddChild,
                    529:                            &examine);
                    530:                } else {
                    531:                        if (DEBUG(MAKE))
                    532:                                printf("%s: queuing\n", gn->name);
1.56      espie     533:                        Array_Push(&toBeMade, gn);
1.46      espie     534:                }
                    535:        }
1.56      espie     536:        if (randomize_queue)
                    537:                randomize_garray(&toBeMade);
1.46      espie     538: }
                    539:
1.1       deraadt   540: /*-
                    541:  *-----------------------------------------------------------------------
1.6       millert   542:  * Make_Run --
                    543:  *     Initialize the nodes to remake and the list of nodes which are
                    544:  *     ready to be made by doing a breadth-first traversal of the graph
                    545:  *     starting from the nodes in the given list. Once this traversal
                    546:  *     is finished, all the 'leaves' of the graph are in the toBeMade
                    547:  *     queue.
                    548:  *     Using this queue and the Job module, work back up the graph,
                    549:  *     calling on MakeStartJobs to keep the job table as full as
                    550:  *     possible.
                    551:  *
1.1       deraadt   552:  * Results:
1.26      espie     553:  *     true if work was done. false otherwise.
1.1       deraadt   554:  *
                    555:  * Side Effects:
1.48      espie     556:  *     The must_make field of all nodes involved in the creation of the given
1.6       millert   557:  *     targets is set to 1. The toBeMade list is set to contain all the
                    558:  *     'leaves' of these subgraphs.
1.1       deraadt   559:  *-----------------------------------------------------------------------
                    560:  */
1.26      espie     561: bool
1.35      espie     562: Make_Run(Lst targs)            /* the initial list of targets */
1.1       deraadt   563: {
1.65      espie     564:        bool problem;   /* errors occurred */
1.52      espie     565:        GNode *gn;
                    566:        unsigned int i;
                    567:        bool cycle;
1.40      espie     568:
1.54      espie     569:        /* wild guess at initial sizes */
1.56      espie     570:        Array_Init(&toBeMade, 500);
                    571:        Array_Init(&examine, 150);
1.64      espie     572:        Array_Init(&heldBack, 100);
1.52      espie     573:        ohash_init(&targets, 10, &gnode_info);
1.54      espie     574:        if (DEBUG(PARALLEL))
                    575:                random_setup();
1.40      espie     576:
1.46      espie     577:        add_targets_to_make(targs);
1.40      espie     578:        if (queryFlag) {
                    579:                /*
1.41      espie     580:                 * We wouldn't do any work unless we could start some jobs in
                    581:                 * the next loop... (we won't actually start any, of course,
1.40      espie     582:                 * this is just to see if any of the targets was out of date)
                    583:                 */
                    584:                return MakeStartJobs();
                    585:        } else {
                    586:                /*
                    587:                 * Initialization. At the moment, no jobs are running and until
                    588:                 * some get started, nothing will happen since the remaining
1.41      espie     589:                 * upward traversal of the graph is performed by the routines
                    590:                 * in job.c upon the finishing of a job. So we fill the Job
1.40      espie     591:                 * table as much as we can before going into our loop.
                    592:                 */
                    593:                (void)MakeStartJobs();
1.1       deraadt   594:        }
1.4       millert   595:
1.1       deraadt   596:        /*
1.40      espie     597:         * Main Loop: The idea here is that the ending of jobs will take
                    598:         * care of the maintenance of data structures and the waiting for output
                    599:         * will cause us to be idle most of the time while our children run as
                    600:         * much as possible. Because the job table is kept as full as possible,
                    601:         * the only time when it will be empty is when all the jobs which need
                    602:         * running have been run, so that is the end condition of this loop.
1.41      espie     603:         * Note that the Job module will exit if there were any errors unless
1.40      espie     604:         * the keepgoing flag was given.
1.1       deraadt   605:         */
1.40      espie     606:        while (!Job_Empty()) {
1.57      espie     607:                handle_running_jobs();
1.40      espie     608:                (void)MakeStartJobs();
                    609:        }
                    610:
1.65      espie     611:        problem = Job_Finish();
1.52      espie     612:        cycle = false;
1.40      espie     613:
1.52      espie     614:        for (gn = ohash_first(&targets, &i); gn != NULL;
                    615:            gn = ohash_next(&targets, &i)) {
                    616:                if (has_been_built(gn))
                    617:                        continue;
                    618:                cycle = true;
1.65      espie     619:                problem = true;
1.52      espie     620:                printf("Error: target %s unaccounted for (%s)\n",
                    621:                    gn->name, status_to_string(gn));
                    622:        }
1.1       deraadt   623:        /*
1.40      espie     624:         * Print the final status of each target. E.g. if it wasn't made
                    625:         * because some inferior reported an error.
1.1       deraadt   626:         */
1.52      espie     627:        Lst_ForEach(targs, MakePrintStatus, &cycle);
1.65      espie     628:        if (problem)
1.52      espie     629:                Fatal("Errors while building");
1.4       millert   630:
1.40      espie     631:        return true;
1.1       deraadt   632: }