Module Name: src Committed By: rillig Date: Thu Oct 22 21:27:24 UTC 2020
Modified Files: src/usr.bin/make: lst.c lst.h make.c suff.c Log Message: make(1): add Lst_ForEachUntilConcurrent Previously, Lst_ForEachUntil allowed the list to be modified while iterating. Almost none of the code needs this, and it's also confusing for human readers. None of the current unit tests makes use of this concurrent modification right now, but that's not evidence enough. Only 72% of the code are covered by unit tests right now, and there are lots of edge cases (whether intended or not) that are not covered by unit tests. Therefore, all calls to Lst_ForEachUntil were changed to Lst_ForEachUntilConcurrent and those that were obvious were changed back. The remaining calls probably don't need the concurrent modification code, but that's not obvious from looking at the code. To generate a diff of this commit: cvs rdiff -u -r1.81 -r1.82 src/usr.bin/make/lst.c cvs rdiff -u -r1.76 -r1.77 src/usr.bin/make/lst.h cvs rdiff -u -r1.171 -r1.172 src/usr.bin/make/make.c cvs rdiff -u -r1.216 -r1.217 src/usr.bin/make/suff.c Please note that diffs are not public domain; they are subject to the copyright notices on the relevant files.
Modified files: Index: src/usr.bin/make/lst.c diff -u src/usr.bin/make/lst.c:1.81 src/usr.bin/make/lst.c:1.82 --- src/usr.bin/make/lst.c:1.81 Thu Oct 22 20:18:20 2020 +++ src/usr.bin/make/lst.c Thu Oct 22 21:27:24 2020 @@ -1,4 +1,4 @@ -/* $NetBSD: lst.c,v 1.81 2020/10/22 20:18:20 rillig Exp $ */ +/* $NetBSD: lst.c,v 1.82 2020/10/22 21:27:24 rillig Exp $ */ /* * Copyright (c) 1988, 1989, 1990, 1993 @@ -34,7 +34,7 @@ #include "make.h" -MAKE_RCSID("$NetBSD: lst.c,v 1.81 2020/10/22 20:18:20 rillig Exp $"); +MAKE_RCSID("$NetBSD: lst.c,v 1.82 2020/10/22 21:27:24 rillig Exp $"); /* Allocate and initialize a list node. * @@ -293,11 +293,28 @@ Lst_FindDatum(List *list, const void *da return NULL; } +/* Apply the given function to each element of the given list, until the + * function returns non-zero. During this iteration, the list must not be + * modified structurally. */ +int +Lst_ForEachUntil(List *list, LstActionUntilProc proc, void *procData) +{ + ListNode *node; + int result = 0; + + for (node = list->first; node != NULL; node = node->next) { + result = proc(node->datum, procData); + if (result != 0) + break; + } + return result; +} + /* Apply the given function to each element of the given list. The function * should return 0 if traversal should continue and non-zero if it should * abort. */ int -Lst_ForEachUntil(List *list, LstActionUntilProc proc, void *procData) +Lst_ForEachUntilConcurrent(List *list, LstActionUntilProc proc, void *procData) { ListNode *tln = list->first; int result = 0; Index: src/usr.bin/make/lst.h diff -u src/usr.bin/make/lst.h:1.76 src/usr.bin/make/lst.h:1.77 --- src/usr.bin/make/lst.h:1.76 Thu Oct 22 20:18:20 2020 +++ src/usr.bin/make/lst.h Thu Oct 22 21:27:24 2020 @@ -1,4 +1,4 @@ -/* $NetBSD: lst.h,v 1.76 2020/10/22 20:18:20 rillig Exp $ */ +/* $NetBSD: lst.h,v 1.77 2020/10/22 21:27:24 rillig Exp $ */ /* * Copyright (c) 1988, 1989, 1990 The Regents of the University of California. @@ -114,7 +114,7 @@ typedef void *LstCopyProc(void *); typedef void LstFreeProc(void *); /* Return TRUE if the datum matches the args, for Lst_Find. */ typedef Boolean LstFindProc(const void *datum, const void *args); -/* An action for Lst_ForEachUntil. */ +/* An action for Lst_ForEachUntil and Lst_ForEachUntilConcurrent. */ typedef int LstActionUntilProc(void *datum, void *args); /* Create or destroy a list */ @@ -167,6 +167,7 @@ void LstNode_SetNull(ListNode *); /* Apply a function to each datum of the list, until the callback function * returns non-zero. */ int Lst_ForEachUntil(List *, LstActionUntilProc, void *); +int Lst_ForEachUntilConcurrent(List *, LstActionUntilProc, void *); /* Iterating over a list while keeping track of the current node and possible * concurrent modifications */ Index: src/usr.bin/make/make.c diff -u src/usr.bin/make/make.c:1.171 src/usr.bin/make/make.c:1.172 --- src/usr.bin/make/make.c:1.171 Thu Oct 22 20:09:07 2020 +++ src/usr.bin/make/make.c Thu Oct 22 21:27:24 2020 @@ -1,4 +1,4 @@ -/* $NetBSD: make.c,v 1.171 2020/10/22 20:09:07 rillig Exp $ */ +/* $NetBSD: make.c,v 1.172 2020/10/22 21:27:24 rillig Exp $ */ /* * Copyright (c) 1988, 1989, 1990, 1993 @@ -107,7 +107,7 @@ #include "job.h" /* "@(#)make.c 8.1 (Berkeley) 6/6/93" */ -MAKE_RCSID("$NetBSD: make.c,v 1.171 2020/10/22 20:09:07 rillig Exp $"); +MAKE_RCSID("$NetBSD: make.c,v 1.172 2020/10/22 21:27:24 rillig Exp $"); /* Sequence # to detect recursion. */ static unsigned int checked = 1; @@ -645,7 +645,8 @@ Make_Update(GNode *cgn) parents = centurion->parents; /* If this was a .ORDER node, schedule the RHS */ - Lst_ForEachUntil(centurion->order_succ, MakeBuildParent, toBeMade->first); + Lst_ForEachUntilConcurrent(centurion->order_succ, + MakeBuildParent, toBeMade->first); /* Now mark all the parents as having one less unmade child */ for (ln = parents->first; ln != NULL; ln = ln->next) { @@ -751,9 +752,10 @@ UnmarkChildren(GNode *gn) } /* Add a child's name to the ALLSRC and OODATE variables of the given - * node. Called from Make_DoAllVar via Lst_ForEachUntil. A child is added only - * if it has not been given the .EXEC, .USE or .INVISIBLE attributes. - * .EXEC and .USE children are very rarely going to be files, so... + * node, but only if it has not been given the .EXEC, .USE or .INVISIBLE + * attributes. .EXEC and .USE children are very rarely going to be files, + * so... + * * If the child is a .JOIN node, its ALLSRC is propagated to the parent. * * A child is added to the OODATE variable if its modification time is @@ -899,7 +901,7 @@ MakeBuildChild(void *v_cn, void *toBeMad Lst_InsertBefore(toBeMade, toBeMade_next, cn); if (cn->unmade_cohorts != 0) - Lst_ForEachUntil(cn->cohorts, MakeBuildChild, toBeMade_next); + Lst_ForEachUntilConcurrent(cn->cohorts, MakeBuildChild, toBeMade_next); /* * If this node is a .WAIT node with unmade children @@ -966,7 +968,8 @@ MakeStartJobs(void) * just before the current first element. */ gn->made = DEFERRED; - Lst_ForEachUntil(gn->children, MakeBuildChild, toBeMade->first); + Lst_ForEachUntilConcurrent(gn->children, + MakeBuildChild, toBeMade->first); /* and drop this node on the floor */ DEBUG2(MAKE, "dropped %s%s\n", gn->name, gn->cohort_num); continue; @@ -1163,7 +1166,7 @@ Make_ExpandUse(GNodeList *targs) Suff_FindDeps(gn); else { /* Pretend we made all this node's children */ - Lst_ForEachUntil(gn->children, MakeFindChild, gn); + Lst_ForEachUntilConcurrent(gn->children, MakeFindChild, gn); if (gn->unmade != 0) printf("Warning: %s%s still has %d unmade children\n", gn->name, gn->cohort_num, gn->unmade); Index: src/usr.bin/make/suff.c diff -u src/usr.bin/make/suff.c:1.216 src/usr.bin/make/suff.c:1.217 --- src/usr.bin/make/suff.c:1.216 Thu Oct 22 19:30:37 2020 +++ src/usr.bin/make/suff.c Thu Oct 22 21:27:24 2020 @@ -1,4 +1,4 @@ -/* $NetBSD: suff.c,v 1.216 2020/10/22 19:30:37 rillig Exp $ */ +/* $NetBSD: suff.c,v 1.217 2020/10/22 21:27:24 rillig Exp $ */ /* * Copyright (c) 1988, 1989, 1990, 1993 @@ -129,7 +129,7 @@ #include "dir.h" /* "@(#)suff.c 8.4 (Berkeley) 3/21/94" */ -MAKE_RCSID("$NetBSD: suff.c,v 1.216 2020/10/22 19:30:37 rillig Exp $"); +MAKE_RCSID("$NetBSD: suff.c,v 1.217 2020/10/22 21:27:24 rillig Exp $"); #define SUFF_DEBUG0(text) DEBUG0(SUFF, text) #define SUFF_DEBUG1(fmt, arg1) DEBUG1(SUFF, fmt, arg1) @@ -592,7 +592,7 @@ Suff_EndTransform(GNode *gn) } } -/* Called from Suff_AddSuffix via Lst_ForEachUntil to search through the list of +/* Called from Suff_AddSuffix to search through the list of * existing transformation rules and rebuild the transformation graph when * it has been destroyed by Suff_ClearSuffixes. If the given rule is a * transformation involving this suffix and another, existing suffix, the