[bug #63098] make-4.3.90 regression of unexpected dependencies in pattern rules with multiple targets

[Sergei Trofimovich]

Follow-up Comment #3, bug #63098 (project make):

Aha, behavior change makes sense. Let's close it as intended then.

Looks like opensp's case is even more nuanced. `%.h %.cxx %.rc: %.msg`
produces `.cxx` files only for a subset of `.msg` files: `.cxx` generation
happens only where file contents has `!cxx` marking. Otherwise only `.h` and
`.rc` are produced. That explains why tarballs don't contain some of `.cxx`
files and cause the rules to attempt to regenerate them at each `make`
invocation.

I filed https://sourceforge.net/p/openjade/bugs/151/ against opensp upstream.
Looks like last activity was in 2007, might take a long while to get fixed.
I'll attach the path there if I manage to get something working.

Thank you!


___

Reply to this item at:

  

___
Message sent via Savannah
https://savannah.gnu.org/

[bug #63098] make-4.3.90 regression of unexpected dependencies in pattern rules with multiple targets

[Sergei Trofimovich]

URL:
  <https://savannah.gnu.org/bugs/?63098>

 Summary: make-4.3.90 regression of unexpected dependencies in
pattern rules with multiple targets
 Project: make
   Submitter: slyfox
   Submitted: Fri 23 Sep 2022 07:05:25 PM UTC
Severity: 3 - Normal
  Item Group: None
  Status: None
 Privacy: Public
 Assigned to: None
 Open/Closed: Open
 Discussion Lock: Any
   Component Version: None
Operating System: None
   Fixed Release: None
   Triage Status: None


___

Follow-up Comments:


---
Date: Fri 23 Sep 2022 07:05:25 PM UTC By: Sergei Trofimovich 
Initially noticed the problem in OpenSP-1.5.2 build failure. Here is a
minimised example:


# cat Makefile
all: foo.a foo.b

%.a %.b %.c: %.d
touch $*.a
touch $*.b
touch $*.c


To trigger it we need to have up-to-date foo.d, foo.a and foo.b:


$ touch foo.d; touch foo.a; touch foo.b

# good make-4.3:
$ make-4.3
make: Nothing to be done for 'all'.

# problematic make-4.3.90:
$ make-4.3.90
touch foo.a
touch foo.b
touch foo.c


Note how new make version decided it needs to do extra work.

Looks like a bug.

A bit of background on original bug context (in case I extracted it
incorrectly):

OpenSP-1.5.2 uses similar pattern in
https://sourceforge.net/p/openjade/code/HEAD/tree/trunk/sp/lib/Makefile.am


# ...
%.h %.cxx %.rc: %.msg
[ ! -f $(top_srcdir)/msggen.pl ] || $(PERL) -w $(top_srcdir)/msggen.pl
$(MSGGENFLAGS) $<


OpenSP's release tarball ships only .h and .rc files (but not .cxx):
lib/WinInetStorageMessages.h lib/WinInetStorageMessages.msg
lib/WinInetStorageMessages.rc. It looks like nothing requires .cxx files in
that directory.

I only noticed the failure because my sandbox environment did not have perl
and caused build failure of make upgrade to 4.3.90.







___

Reply to this item at:

  <https://savannah.gnu.org/bugs/?63098>

___
Message sent via Savannah
https://savannah.gnu.org/

[bug #63047] --shuffle mode does not work on .SECONDEXPANSION targets

[Sergei Trofimovich]

Follow-up Comment #1, bug #63047 (project make):

Posted the patch for review as
https://lists.gnu.org/archive/html/bug-make/2022-09/msg00069.html


___

Reply to this item at:

  

___
Message sent via Savannah
https://savannah.gnu.org/

[bug #63047] --shuffle mode does not work on .SECONDEXPANSION targets

[Sergei Trofimovich]

Additional Item Attachment, bug #63047 (project make):

File name: 0001-Fix-shuffle-for-SECONDEXPANSION-prerequisites.patch Size:3 KB
   




___

Reply to this item at:

  

___
Message sent via Savannah
https://savannah.gnu.org/

[PATCH] Fix --shuffle for SECONDEXPANSION prerequisites

[Sergei Trofimovich]

From: Sergei Trofimovich 

Since commit 07eea3aa4 ("[SV 62706] Only second-expand targets that
might be built") `make --shuffle` stopped shuffling prerequisites that
use .SECONDEXPANSION feature for Makefiles like:

.SECONDEXPANSION:
all: $$(var)
%_: ; @echo $@
var = a_ b_ c_

Shuffle does not happen anymore because second expansion now happens
after shuffle phase. This has two problems:
1. No shuffling happens for such prerequisites.
2. Already freed data is accessed when when oudated '->shuf' links
   are used.

The fix inserts reshuffle into expansion phase right after dependency
changes to fix both problems.

* src/file.c (expand_deps): Add reshuffling phase if dependency updates.
* src/shuffle.c (identity_shuffle_array): Fix comment typo.
* tests/scripts/options/shuffle: Add new SECONDEXPANSION test.
---
 src/file.c| 10 ++
 src/shuffle.c |  2 +-
 tests/scripts/options/shuffle |  9 +
 3 files changed, 20 insertions(+), 1 deletion(-)

diff --git a/src/file.c b/src/file.c
index 7596ff10..83aa593c 100644
--- a/src/file.c
+++ b/src/file.c
@@ -25,6 +25,7 @@ this program.  If not, see <http://www.gnu.org/licenses/>.  */
 #include "variable.h"
 #include "debug.h"
 #include "hash.h"
+#include "shuffle.h"
 
 
 /* Remember whether snap_deps has been invoked: we need this to be sure we
@@ -576,6 +577,7 @@ expand_deps (struct file *f)
   struct dep **dp;
   const char *fstem;
   int initialized = 0;
+  int changed_dep = 0;
 
   if (f->snapped)
 return;
@@ -664,6 +666,7 @@ expand_deps (struct file *f)
   if (new == 0)
 {
   *dp = d->next;
+  changed_dep = 1;
   free_dep (d);
   d = *dp;
   continue;
@@ -672,6 +675,7 @@ expand_deps (struct file *f)
   /* Add newly parsed prerequisites.  */
   fstem = d->stem;
   next = d->next;
+  changed_dep = 1;
   free_dep (d);
   *dp = new;
   for (dp = , d = new; d != 0; dp = >next, d = d->next)
@@ -688,6 +692,12 @@ expand_deps (struct file *f)
   *dp = next;
   d = *dp;
 }
+
+/* --shuffle mode assumes '->next' and '->shuf' links both traverse
+   the same dependencies (in different sequences).  Here we
+   regenerate '->shuf'.  Otherwise we risk referring stale data.  */
+if (changed_dep)
+  shuffle_deps_recursive (f->deps);
 }
 
 /* Add extra prereqs to the file in question.  */
diff --git a/src/shuffle.c b/src/shuffle.c
index ea6e836d..23c9c224 100644
--- a/src/shuffle.c
+++ b/src/shuffle.c
@@ -154,7 +154,7 @@ identity_shuffle_array (void **a UNUSED, size_t len UNUSED)
   /* No-op!  */
 }
 
-/* Shuffle list of dependencies by populating '->next'
+/* Shuffle list of dependencies by populating '->shuf'
field in each 'struct dep'.  */
 static void
 shuffle_deps (struct dep *deps)
diff --git a/tests/scripts/options/shuffle b/tests/scripts/options/shuffle
index e037ed1a..5661683c 100644
--- a/tests/scripts/options/shuffle
+++ b/tests/scripts/options/shuffle
@@ -116,4 +116,13 @@ run_make_test('
 ',
   '--shuffle=reverse a_ b_ c_', "a_\nb_\nc_");
 
+# Check if SECONDEXPANSION targets also get reshuffled.
+run_make_test('
+.SECONDEXPANSION:
+all: $$(var)
+%_: ; @echo $@
+var = a_ b_ c_
+',
+  '--shuffle=reverse', "c_\nb_\na_");
+
 1;
-- 
2.37.2

[bug #63047] --shuffle mode does not work on .SECONDEXPANSION targets

[Sergei Trofimovich]

URL:
  <https://savannah.gnu.org/bugs/?63047>

 Summary: --shuffle mode does not work on .SECONDEXPANSION
targets
 Project: make
   Submitter: slyfox
   Submitted: Sun 11 Sep 2022 08:13:12 PM UTC
Severity: 3 - Normal
  Item Group: None
  Status: None
 Privacy: Public
 Assigned to: None
 Open/Closed: Open
 Discussion Lock: Any
   Component Version: None
Operating System: None
   Fixed Release: None
   Triage Status: None


___

Follow-up Comments:


---
Date: Sun 11 Sep 2022 08:13:12 PM UTC By: Sergei Trofimovich 
Since commit 07eea3aa496184bb763b7306e9de6a40a94605c9 ("[SV 62706] Only
second-expand targets that might be built") `make --shuffle` stopped shuffling
.SECONDEXPANSION. Example `Makefile`:

.SECONDEXPANSION:
all: $$(var)
%_: ; @echo $@
var = a_ b_ c_

Before (good):

$ make --shuffle=reverse
c_
b_
a_

After (bad):

$ ./make --shuffle=reverse
a_
b_
c_


I'll send a possible fix today.







___

Reply to this item at:

  <https://savannah.gnu.org/bugs/?63047>

___
Message sent via Savannah
https://savannah.gnu.org/

[bug #63040] autoconf-2.69 and 2.71 fail to build after $(shell ...) environment handlign change

[Sergei Trofimovich]

Follow-up Comment #1, bug #63040 (project make):

Proposed possible fix for autoconf as
https://lists.gnu.org/archive/html/autoconf-patches/2022-09/msg7.html


___

Reply to this item at:

  

___
Message sent via Savannah
https://savannah.gnu.org/

[bug #63040] autoconf-2.69 and 2.71 fail to build after $(shell ...) environment handlign change

[Sergei Trofimovich]

URL:
  <https://savannah.gnu.org/bugs/?63040>

 Summary: autoconf-2.69 and 2.71 fail to build after $(shell
...) environment handlign change
 Project: make
   Submitter: slyfox
   Submitted: Fri 09 Sep 2022 10:35:02 AM UTC
Severity: 3 - Normal
  Item Group: None
  Status: None
 Privacy: Public
 Assigned to: None
 Open/Closed: Open
 Discussion Lock: Any
   Component Version: None
Operating System: None
   Fixed Release: None
   Triage Status: None


___

Follow-up Comments:


---
Date: Fri 09 Sep 2022 10:35:02 AM UTC By: Sergei Trofimovich 
Tried to use `make` from today's git (commit
7d484017077089ac2642b89da8984ca46a07323d [SV 63016] Don't fail exporting to
$(shell ...)) and observed build failure on autoconf:


build flags: -j16 -l16 SHELL=bash
bash: line 1: env: command not found
make  all-am
bash: line 1: make: command not found
make: *** [Makefile:928: all] Error 127


The build failure happens because (I think) autoconf uses the following
trick:


cfg.mk:export PATH = $(shell echo "`pwd`/tests:$$PATH")


Comparing behaviour from `make` a few months ago:


$ make --version
GNU Make 4.3.90.20220619

$ printf 'export PATH = $(shell echo $$PWD:$$PATH)'"\n"'all:; echo $$PATH' |
make -f -
echo $PATH
/tmp:/run/current-system/sw/bin


Path is prepended to existing one, ok.

And the today's one:


$ ./make --version
GNU Make 4.3.90.20220909
$ printf 'export PATH = $(shell echo $$PWD:$$PATH)'"\n"'all:; echo $$PATH' |
./make -f -
echo $PATH
make: sh: No such file or directory
make: sh: No such file or directory
make: *** [/tmp/GmYdo0my:2: all] Error 127


If we use `:=` then it works as expected:


$ printf 'export PATH := $(shell echo $$PWD:$$PATH)'"\n"'all:; echo $$PATH' |
./make -f -
echo $PATH
/tmp:/run/current-system/sw/bin


In theory it should be easy to adapt `autoconf`s build system. Filing a bug to
make sure it's an intended change and not an unexpected regression.







___

Reply to this item at:

  <https://savannah.gnu.org/bugs/?63040>

___
Message sent via Savannah
https://savannah.gnu.org/

[bug #62100] [PATCH] Add '--shuffle' argument support

[Sergei Trofimovich]

Additional Item Attachment, bug #62100 (project make):

File name: v7-0001-Add-shuffle-argument-support.patch Size:35 KB
   




___

Reply to this item at:

  

___
  Message sent via Savannah
  https://savannah.gnu.org/

[bug #62100] [PATCH] Add '--shuffle' argument support

[Sergei Trofimovich]

Follow-up Comment #6, bug #62100 (project make):

Adding a v7-0001-Add-shuffle-argument-support.patch which 2 extra changes:
1. fixed 'if' indentation in src/main.c noticed by Fangrui Song
2. tweaked --help output to '--shuffle[={SEED|random|identity|reverse|none}]'
noticed by Fangrui Song


___

Reply to this item at:

  

___
  Message sent via Savannah
  https://savannah.gnu.org/

[bug #62100] [PATCH] Add '--shuffle' argument support

[Sergei Trofimovich]

Follow-up Comment #4, bug #62100 (project make):

Caught bugs in a few upstream projects. Two nice simple examples:
- vim: https://github.com/vim/vim/pull/9978
- groff: https://savannah.gnu.org/bugs/?62084


___

Reply to this item at:

  

___
  Message sent via Savannah
  https://savannah.gnu.org/

[bug #62100] [PATCH] Add '--shuffle' argument support

[Sergei Trofimovich]

Follow-up Comment #3, bug #62100 (project make):

Uploaded v6-0001-Add-shuffle-argument-support.patch. It's the rebased v5
against today's make.git where a small merge conflict is fixed around added
option. Otherwise identical to v5.

___

Reply to this item at:

  

___
  Message sent via Savannah
  https://savannah.gnu.org/

[bug #62100] [PATCH] Add '--shuffle' argument support

[Sergei Trofimovich]

Additional Item Attachment, bug #62100 (project make):

File name: v6-0001-Add-shuffle-argument-support.patch Size:35 KB
   




___

Reply to this item at:

  

___
  Message sent via Savannah
  https://savannah.gnu.org/

[bug #62100] [PATCH] Add '--shuffle' argument support

[Sergei Trofimovich]

Follow-up Comment #1, bug #62100 (project make):

Changes from v4: presence of `.NOTPARALLEL:` target disables shuffling as
makefile is already known to be broken in target reorder caused by -j
parallelism.

Example of real package is `netpbm`. Upstream does not plan to fix it.

___

Reply to this item at:

  

___
  Message sent via Savannah
  https://savannah.gnu.org/

[bug #62100] [PATCH] Add '--shuffle' argument support

[Sergei Trofimovich]

Additional Item Attachment, bug #62100 (project make):

File name: v5-0001-Add-shuffle-argument-support.patch Size:35 KB
   




___

Reply to this item at:

  

___
  Message sent via Savannah
  https://savannah.gnu.org/

[bug #62100] [PATCH] Add '--shuffle' argument support

[Sergei Trofimovich]

URL:
  

 Summary: [PATCH] Add '--shuffle' argument support
 Project: make
Submitted by: slyfox
Submitted on: Wed 23 Feb 2022 07:51:47 AM UTC
Severity: 3 - Normal
  Item Group: None
  Status: None
 Privacy: Public
 Assigned to: None
 Open/Closed: Open
 Discussion Lock: Any
   Component Version: None
Operating System: None
   Fixed Release: None
   Triage Status: None

___

Details:

The idea of the change is to introduce non-deterministic ordering
into goal and prerequisite traversal to imitate non-deterministic
ordering of 'make -j g1 g2 g3' mode.

Filing the bug to make sure it does not get lost.

The patch is against current git tree:


$ git describe
4.3-138-gfcc23a4d






___

File Attachments:


---
Date: Wed 23 Feb 2022 07:51:47 AM UTC  Name:
v4-0001-Add-shuffle-argument-support.patch  Size: 35KiB   By: slyfox



___

Reply to this item at:

  

___
  Message sent via Savannah
  https://savannah.gnu.org/

Re: [PATCH] Fix src/function.c build failure on gcc-12.

[Sergei Trofimovich]

On Mon, 21 Feb 2022, 15:29 Paul Smith,  wrote:
>
> On Mon, 2022-02-21 at 08:59 +, Edward Welbourne wrote:
> > and that's assuming a 32-bit int; the signed range is from -
> > 2,147,483,647 to 2,147,483,648.  However, may I suggest the following
> > (which I know included in the GPL'd cfengine sources at some point):
>
> This computation is already included in GNU make (in Git) as the
> constant INTSTR_LENGTH (which uses sizeof(uintmax_t) as the basis),
> from a previous, similar suggestion you made a few months ago :).
>
> I modified this and a few other buffers that used static lengths, to
> use the INTSTR_LENGTH macro.

Sounds good. Which repository I should use to pull changes like that?
I looked at https://git.savannah.gnu.org/cgit/make.git and did not find it.

[PATCH v4] Add '--shuffle' argument support

[Sergei Trofimovich]

On Sun, Feb 20, 2022 at 10:30:10AM +, Sergei Trofimovich wrote:
> On Sat, Feb 19, 2022 at 09:57:13AM +0200, Eli Zaretskii wrote:

> > I think NEWS should also call out the new feature.

Forgot the actual NEWS entry. Attached v4.

-- 

  Sergei
>From 6eb8c759f6e917ff82326769e509505f8ff0e310 Mon Sep 17 00:00:00 2001
From: Sergei Trofimovich 
Date: Fri, 4 Feb 2022 22:43:28 +
Subject: [PATCH v4] Add '--shuffle' argument support

The idea of the change is to introduce non-deterministic ordering
into goal and prerequisite traversal to imitate non-deterministic
ordering of 'make -j g1 g2 g3' mode.

The implementation is to introduce second order into each dependency chain:
1. existing order is syntactic order reachable via 'dep->next'
2. new order is shuffled order stored as 'dep->shuf' in each 'dep'

When goals or prerequisites are updated we use shuffled order when
'--shuffle' is passed to make. When recipes are evaluated we use
syntactic order of parameters.

Sample execution looks like:

$ while echo === && rm -f a b && make --shuffle; do sleep 1; done
===
touch a
cp a b
===
cp a b
cp: cannot stat 'a': No such file or directory
make: *** [Makefile:5: b] Error 1 --shuffle=1644097687

Note: here first run succeeds while second run fails and exposes the bug in
Makefile. --shuffle=1644097687 allows us to rerun the same build sequence
again.

There are a few shuffle modes available:
- --shuffle (or --shuffle=random): use random seed and produce random order
- --shuffle=identity: use original order, but store and use it explicitly
  (most useful for GNU make testing)
- --shuffle=reverse: use inverse order for every goal list and prerequisite
  list. It is frequently enough to trigger simplest bugs.
- --shuffle=none: disable shuffle infrastructure completely. Useful to negate
  effect of previous --shuffle options.

* Makefile.am (make_SRCS): Add src/shuf.h and src/shuf.c file references.
* NEWS: Mention --shuffle option in news.
* builddos.bat: Add shuf.o into build script.
* build_w32.bat: Add shuf.c into build script.
* doc/make.1: Add '--shuffle' option description.
* doc/make.texi: Add '--shuffle' option description.
* makefile.com: Add shuf.c into build script.
* src/dep.h (DEP): Add 'shuf' field to store shuffled order.
* src/filedef.h (struct file): Add 'was_shuffled' bit flag to guard against
  circular dependencies.
* src/implicit.c (pattern_search): Reshuffle dependencies for targets
  dynamically extended with dependencies from implicit rules.
* src/job.c (child_error): Print shuffle parameter used for dependency
  shuffling.
* src/main.c: Add '--shuffle' option handling.
* src/remake.c (update_goal_chain): Change goal traversal order to shuffled.
* src/shuf.c: New file with shuffle infrastructure.
* src/shuf.h: New file with shuffle infrastructure declarations.
* tests/scripts/misc/rand-shuf: New file with randomness tests.
* tests/scripts/options/shuffle-reverse: New file with basic tests.
---
 Makefile.am   |   5 +-
 NEWS  |   6 +
 build_w32.bat |   1 +
 builddos.bat  |   3 +-
 doc/make.1|  34 
 doc/make.texi |  51 ++
 makefile.com  |   2 +-
 src/dep.h |   1 +
 src/filedef.h |   2 +
 src/implicit.c|   7 +
 src/job.c |  21 ++-
 src/main.c|  29 
 src/remake.c  | 138 ---
 src/shuf.c| 241 ++
 src/shuf.h|  23 +++
 tests/scripts/misc/rand-shuf  |  40 +
 tests/scripts/options/shuffle-reverse | 112 
 17 files changed, 644 insertions(+), 72 deletions(-)
 create mode 100644 src/shuf.c
 create mode 100644 src/shuf.h
 create mode 100644 tests/scripts/misc/rand-shuf
 create mode 100644 tests/scripts/options/shuffle-reverse

diff --git a/Makefile.am b/Makefile.am
index 9be60fec..3ad19e0c 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -35,8 +35,9 @@ make_SRCS =   src/ar.c src/arscan.c src/commands.c 
src/commands.h \
src/hash.c src/hash.h src/implicit.c src/job.c src/job.h \
src/load.c src/loadapi.c src/main.c src/makeint.h src/misc.c \
src/os.h src/output.c src/output.h src/read.c src/remake.c \
-   src/rule.c src/rule.h src/signame.c src/strcache.c \
-   src/variable.c src/variable.h src/version.c src/vpath.c
+   src/rule.c src/rule.h src/shuf.h src/shuf.c src/signame.c \
+   src/strcache.c src/variable.c src/variable.h src/version.c \
+   src/vpath.c
 
 w32_SRCS = src/w32/pathstuff.c src/w32/w32os.c src/w32/compat/dirent.c \
src/w32/compat/posixfcn

Re: [PATCH v2] Add '--shuffle' argument support

[Sergei Trofimovich]

On Sat, Feb 19, 2022 at 09:57:13AM +0200, Eli Zaretskii wrote:

> > * Makefile.am (make_SRCS): Add src/shuf.h and src/shuf.c file references.
> > * builddos.bat: Add shuf.o into build script.

> This should also update build_w32.bat, which is used to build Make on
> MS-Windows.  I think NEWS should also call out the new feature.

Sounds good! Added there and to makefile.com.

> > +Note that @code{make --shuffle clean all install} does reorder goals
> > +similar to how @code{make -j clean all install} runs all targets in
> 
> These should use @kbd, not @code, since you are describing commands
> the user will type.  I also recommend to wrap each one in @w{..}, so
> that these (long) command isn't broken between 2 lines.

Changed to @w{@kbd{..}}.

> > +@samp{--shuffle=} accepts an optional value:
> 
> I think nowadays it's customary to use @option as markup for
> command-line options (unless Make wants to keep its manual compatible
> to very old versions of Texinfo -- this is up to Paul to decide).

I left it as is as I see on @option{} being used in make.texi.
Can do as a separate patch if others agree.

> > +  /* TODO: could we make this shuffle more deterministic and less
> > + dependent on current filesystem state?  */
> > +  if (! file->was_shuffled)
> > +shuffle_file_deps_recursive (file);
> 
> Should this TODO be resolved before installing the feature?

Sounds good. Added re-seeding for each implicit dependency to get
more deterministic shuffling.

> > +  /* Handle shuffle mode argument.  */
> > +  if (shuffle_mode_arg)
> > +  {
> > +if (streq (shuffle_mode_arg, "none"))
> > +  sm = sm_none;
> > +else if (streq (shuffle_mode_arg, "identity"))
> > +  sm = sm_identity;
> > +else if (streq (shuffle_mode_arg, "reverse"))
> > +  sm = sm_reverse;
> > +else if (streq (shuffle_mode_arg, "random"))
> > +  sm = sm_random;
> > +/* Assume explicit seed if starts from a digit.  */
> > +else if (ISDIGIT (shuffle_mode_arg[0]))
> > +  {
> > +sm = sm_random;
> > +shuffle_seed = atoi (shuffle_mode_arg);
> > +  }
> > +else
> > +  {
> > +O (error, NILF, _("error: unsupported --shuffle= option."));
> > +die (MAKE_FAILURE);
> > +  }
> > +set_shuffle_mode (sm, shuffle_seed);
> > +
> > +/* Write fixed seed back to argument list to propagate fixed seed
> > +   to child $(MAKE) runs.  */
> > +free (shuffle_mode_arg);
> > +shuffle_mode_arg = xstrdup (shuffle_get_str_value ());
> > +  }
> 
> Should this be factored out and put on shuf.c?

Sounds goo.d Moved out to shuf.c. Only left small option rewrite bit in main.c.

> > +  switch (mode)
> > +{
> > +case sm_random:
> > +  if (seed == 0)
> > +seed = (int)time(NULL);
> > +  srand (seed);
> > +  shuffler = random_shuffle_array;
> > +  sprintf(shuffle_str_value, "%d", seed);
>^^
> Stylistic comment: I believe our style is to leave one space between
> the function name and the opening parenthesis (here and elsewhere in
> the patch).

Good catch! Added whitespace everywhere in the new code.

> > +random_shuffle_array (void ** a, size_t len)
> > +{
> > +  for (unsigned int i = 0; i < len; i++)
>  ^^^
> This requires some minimal level of ANSI C support that I'm not sure
> Make already requires.  Older compilers will error out here.

i think it does. Moved out to a separate declaration and switched to
size_t while at it to match function argument type.

> > +  /* TODO: below is almost identical to goaldeps shuffle.  The only 
> > difference
> > + is a type change.  Worth deduplicating?  */
> 
> Another TODO.

Deduplicated by coercing 'strct goaldep*' traversal into 'struct dep *'.
Similar to other dep.h primitives.

> > +  /* Shuffle dependencies. */
> > +  /* TODO: this is a naive recursion.  Is it good enough?  Or better 
> > change it
> > + to queue based implementation?  */
> 
> And another one.

Dropped a TODO as it's no worse than naive recursion in update_file_1.

> > --- /dev/null
> > +++ b/tests/scripts/options/shuffle-reverse
> 
> This test doesn't seem to test the random option.  I understand why
> this is not easy, but shouldn't it still be tested, if only to make
> sure the option works, and also that different seeds produce different
> outcomes?

Added tests/scripts/misc/rand-shuf test to test for random order and
for unchanged order for a fixed seed.

Attaching v3-0001-Add-shuffle

make re-exec regression in 'make -sf -' mode

[Sergei Trofimovich]

Noticed the regression on lowdown-0.10.0 upstream package.

Here is a complete trigger:

$ printf 'all:\n\techo $(CC)' | make -sf -

[good] GNU make 4.3 works as expected:

$ printf 'all:\n\techo $(CC)' | make -sf -
cc

[bad] GNU make from git loops indefinitely in re-execution:

$ printf 'all:\n\techo $(CC)' | ./make -sf -


Curiously space separation workaround is enough to
get the result:

$ printf 'all:\n\techo $(CC)' | ./make -s -f -
cc

Bitsect points at commit 7c4e6b0299 "[SV 60595] Restart
whenever any makefile is rebuilt".

-- 

  Sergei

Re: [PATCH] RFC: add --shuffle[=seed] argument support

[Sergei Trofimovich]

On Sun, 6 Feb 2022 09:34:22 +
Sergei Trofimovich  wrote:

> On Sat, 05 Feb 2022 18:39:41 -0500
> Paul Smith  wrote:
> 
> > Nice work!
> > 
> > On Sat, 2022-02-05 at 22:04 +, Sergei Trofimovich wrote:  
> > > Some high level TODOs:
> > 
> > For this amount of change it's likely that you'll need to provide
> > copyright assignment paperwork.  Let me know if you'd like more details
> > about this.

Somehow managed to completely miss this part last time. Google (my
employer) has the assignment agreement with FSF. Do I also need to sign
personal agreement? I am UK citizen if that afects the decision.

Sent v2 of the patch with @google.com address as an author and attempted
to address almost everything you mentioned. The only thing I left in place
is goal reordering.

> > I recommend you try your version of GNU make on a bunch of different
> > real codebases and make sure it still works (and of course, create the
> > above-mentioned regression tests).  
> 
> Will do. I tried on 100 simple packages, but most of them are resursive
> makefiles (which I missed): 'toenv = 0' effectively disabled the option
> very early. Will try a few crafted inputs and handpick projects with
> handwritten build systems.

Tested '--shuffle=random' on ~2000 packages as part of NixOS distribution
bootstrap. It builds all dependencies from binutils, gcc and kernel up to
xorg. Build found a few real bugs on: ion-3, cramfsswap, dev86, libf2c,
groff, source-highlight, aspell, bind, pth, slang, gpm and subversion.

Having inspected failures manually most of the failures are real bugs of
missing dependencies and they came up before when 'make -j' was tested on
them.

cramfsswap is the shortest example:
  https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=996964

-- 

  Sergei

[PATCH v2] Add '--shuffle' argument support

[Sergei Trofimovich]

From: Sergei Trofimovich 

The idea of the change is to introduce non-deterministic ordering
into goal and prerequisite traversal to imitate non-deterministic
ordering of 'make -j g1 g2 g3' mode.

The implementation is to introduce second order into each dependency chain:
1. existing order is syntactic order reachable via 'dep->next'
2. new order is shuffled order stored as 'dep->shuf' in each 'dep'

When goals or prerequisites are updated we use shuffled order when
'--shuffle' is passed to make. When recipes are evaluated we use
syntactic order of parameters.

Sample execution looks like:

$ while echo === && rm -f a b && make --shuffle; do sleep 1; done
===
touch a
cp a b
===
cp a b
cp: cannot stat 'a': No such file or directory
make: *** [Makefile:5: b] Error 1 --shuffle=1644097687

Note: here first run succeeds while second run fails and exposes the bug in
Makefile. --shuffle=1644097687 allows us to rerun the same build sequence
again.

* Makefile.am (make_SRCS): Add src/shuf.h and src/shuf.c file references.
* builddos.bat: Add shuf.o into build script.
* doc/make.1: Add '--shuffle' option description.
* doc/make.texi: Add '--shuffle' option description.
* src/dep.h (DEP): Add 'shuf' field to store shuffled order.
* src/filedef.h (struct file): Add 'was_shuffled' bit flag to guard against
  circular dependencies.
* src/implicit.c (pattern_search): Reshuffle dependencies for targets
  dynamically extended with dependencies from implicit rules.
* src/job.c (child_error): Print shuffle parameter used for dependency
  shuffling.
* src/main.c: Add '--shuffle' option handling.
* src/remake.c (update_goal_chain): Change goal traversal order to shuffled.
* src/shuf.c: New file with shuffle infrastructure.
* src/shuf.h: New file with shuffle infrastructure declarations.
* tests/scripts/options/shuffle-reverse: New file with basic tests.
---
 Makefile.am   |   5 +-
 builddos.bat  |   3 +-
 doc/make.1|  34 +
 doc/make.texi |  51 +++
 src/dep.h |   1 +
 src/filedef.h |   2 +
 src/implicit.c|   9 ++
 src/job.c |  19 ++-
 src/main.c|  45 ++
 src/remake.c  |  54 ---
 src/shuf.c| 202 ++
 src/shuf.h|  34 +
 tests/scripts/options/shuffle-reverse | 112 ++
 13 files changed, 542 insertions(+), 29 deletions(-)
 create mode 100644 src/shuf.c
 create mode 100644 src/shuf.h
 create mode 100644 tests/scripts/options/shuffle-reverse

diff --git a/Makefile.am b/Makefile.am
index 9be60fec..3ad19e0c 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -35,8 +35,9 @@ make_SRCS =   src/ar.c src/arscan.c src/commands.c 
src/commands.h \
src/hash.c src/hash.h src/implicit.c src/job.c src/job.h \
src/load.c src/loadapi.c src/main.c src/makeint.h src/misc.c \
src/os.h src/output.c src/output.h src/read.c src/remake.c \
-   src/rule.c src/rule.h src/signame.c src/strcache.c \
-   src/variable.c src/variable.h src/version.c src/vpath.c
+   src/rule.c src/rule.h src/shuf.h src/shuf.c src/signame.c \
+   src/strcache.c src/variable.c src/variable.h src/version.c \
+   src/vpath.c
 
 w32_SRCS = src/w32/pathstuff.c src/w32/w32os.c src/w32/compat/dirent.c \
src/w32/compat/posixfcn.c src/w32/include/dirent.h \
diff --git a/builddos.bat b/builddos.bat
index 9cecabec..cfb224c2 100644
--- a/builddos.bat
+++ b/builddos.bat
@@ -68,12 +68,13 @@ gcc -c -I./src -I%XSRC%/src -I./lib -I%XSRC%/lib 
-DHAVE_CONFIG_H -O2 -g %XSRC%/s
 gcc -c -I./src -I%XSRC%/src -I./lib -I%XSRC%/lib -DHAVE_CONFIG_H -O2 -g 
%XSRC%/src/remote-stub.c -o remote-stub.o
 gcc -c -I./src -I%XSRC%/src -I./lib -I%XSRC%/lib -DHAVE_CONFIG_H -O2 -g 
%XSRC%/src/getopt.c -o getopt.o
 gcc -c -I./src -I%XSRC%/src -I./lib -I%XSRC%/lib -DHAVE_CONFIG_H -O2 -g 
%XSRC%/src/getopt1.c -o getopt1.o
+gcc -c -I./src -I%XSRC%/src -I./lib -I%XSRC%/lib -DHAVE_CONFIG_H -O2 -g 
%XSRC%/src/shuf.c -o shuf.o
 gcc -c -I./src -I%XSRC%/src -I./lib -I%XSRC%/lib -DHAVE_CONFIG_H -O2 -g 
%XSRC%/lib/glob.c -o lib/glob.o
 gcc -c -I./src -I%XSRC%/src -I./lib -I%XSRC%/lib -DHAVE_CONFIG_H -O2 -g 
%XSRC%/lib/fnmatch.c -o lib/fnmatch.o
 @echo off
 echo commands.o > respf.$$$
 for %%f in (job output dir file misc main read remake rule implicit default 
variable) do echo %%f.o >> respf.$$$
-for %%f in (expand function vpath hash strcache version ar arscan signame 
remote-stub getopt getopt1) do echo %%f.o >> respf.$$$
+for %%f in (expand function vpath hash strcache version ar arscan signame 
remote-stub getopt getopt1 shuf) do echo %%f.o >> respf.$$$
 for 

[PATCH] Fix src/function.c build failure on gcc-12.

[Sergei Trofimovich]

From: Sergei Trofimovich 

Upcoming gcc-12 detects possible buffer overflow for 1 byte:

src/function.c: In function 'func_call':
src/function.c:2781:24: error: '__builtin___sprintf_chk' may write a 
terminating nul past the end of the destination [-Werror=format-overflow=8]
 2781 |   sprintf (num, "%d", i);
  |^
In file included from glibc-2.35-dev/include/stdio.h:894,
 from src/makeint.h:89,
 from src/function.c:17:
In function 'sprintf',
inlined from 'func_call' at src/function.c:2781:7:
glibc-2.35-dev/include/bits/stdio2.h:38:10: note: '__builtin___sprintf_chk' 
output between 2 and 12 bytes into a destination of size 11

Unlikely numbers like '-1234567890' including null terminator take 12
bytes of storage.

* src/function.c: Allocate enough storage for num
---
 src/function.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/src/function.c b/src/function.c
index 9add8f65..af2095da 100644
--- a/src/function.c
+++ b/src/function.c
@@ -2776,7 +2776,7 @@ func_call (char *o, char **argv, const char *funcname 
UNUSED)
 
   for (; i < max_args; ++i)
 {
-  char num[11];
+  char num[12];
 
   sprintf (num, "%d", i);
   define_variable (num, strlen (num), "", o_automatic, 0);
-- 
2.35.1

Re: [PATCH] RFC: add --shuffle[=seed] argument support

[Sergei Trofimovich]

On Sat, 05 Feb 2022 18:39:41 -0500
Paul Smith  wrote:

> Nice work!
> 
> On Sat, 2022-02-05 at 22:04 +0000, Sergei Trofimovich wrote:
> > Some high level TODOs:  
> 
> For this amount of change it's likely that you'll need to provide
> copyright assignment paperwork.  Let me know if you'd like more details
> about this.
> 
> > - No documentation for the optin yet.  
> 
> This feature would also need a set of regression tests.

Sounds good. Will start adding the tests.

> > - No(?) environment passing for recursive make.  I would prefer to
> > share the same see across all calls to get easier reproducers.  
> 
> You explicitly disabled this, though... was there a reason?

Just a bug. I misinterpreted the 'toenv' meaning.

> > - The dependency traversal is naive and uses potentially unbounded
> > stack.
> > - srand() / rand() is used from system libc.  This might make it
> > harder to reproduce a failure on another machine.  But maybe it's
> > fine.  
> 
> There are a few issues here:
> 
> I recommend you try your version of GNU make on a bunch of different
> real codebases and make sure it still works (and of course, create the
> above-mentioned regression tests).

Will do. I tried on 100 simple packages, but most of them are resursive
makefiles (which I missed): 'toenv = 0' effectively disabled the option
very early. Will try a few crafted inputs and handpick projects with
handwritten build systems.

> First, I think it's not correct to shuffle the goaldeps.  The goals
> that are specified on the command line should always be invoked in the
> order that the user requested.  It would be bad to convert:
> 
>   make clean all install
> 
> to:
> 
>   make install clean all

Just to clarify for myself: I agree changing the order of MAKECMDGOALS is
unexpected and harmful as it's observable in rules definitions (like
'echo $MAKECMDGOALS'). But I also think reordering rule execution should
be fine as it would be close to effect of -j in:

make -j clean all install

Does it sound about right? Or there is some subtler difference between goal
order and prerequisite order treatment?

> Second, you cannot rearrange the first prerequisite.  The first
> prerequisite always must be placed in $<.  Consider the simple pattern
> rule:
> 
>   %.o : %.c
>   $(CC) $(CFLAGS) -c -o $@ $<
> 
>   foo.o: foo.c foo.h bar.h baz.h
> 
> If you rearrange the prerequisites to "bar.h foo.h foo.c baz.h" it will
> not work well :).
> 
> Lastly, I'm not entirely sure that this is the best way to do the
> shuffle.  Similar to my concern above about the first prerequisite,
> this change will break makefiles that rely on the order of
> prerequisites in perfectly legitimate ways; for example:
> 
>   foo%: arg%1 arg%2 arg%3 arg%4
>   bld $< $(word 3,$^) $(word 2,$^) $(word 4,$^)
> 
> The concept you want to implement is not the shuffling of the actual
> prerequisites, it's the shuffling of the BUILDING of the prerequisites.
> The list of deps should not be modified but instead when make goes to
> build the deps it should build them in a different order than they
> appear in the prerequisites list.
> 
> Put another way, you don't want to change the structure of make's
> dependency graph; you just want to change the order in which it's
> walked.
> 
> If you do it this way you don't have to worry about any of the
> reordering issues I raise above, because the values of $<, $^, etc.
> won't change, and also you won't have to worry about deep recursions
> etc. because you'll just be rearranging the targets that are being
> built.
> 
> But, I think making it work this way will be trickier to code.

Oh, I did not realize prerequisite reordering completely breaks rule
definitions! That makes sense.

I'll spend some time to understand where I can plug in to reshuffle
schedulable queue instead.

Ideally I would like to preserve the order of execution across
incremental runs of:

make --shuffle=$seed foo
make --shuffle=$seed foo

but was afraid of the change of already satisfied prerequisites. Might
have to abandon the ideal for simplest first implementation.

Thank you for the detailed comment!

-- 

  Sergei

[PATCH] RFC: add --shuffle[=seed] argument support

[Sergei Trofimovich]

The idea of the change is to introduce non-deterministic ordering
into goal and prerequisite traversal to imitate non-deterministic
ordering of 'make -j' mode.

The implementation is to reorder lists of goals to build and list
of dependencies attached to files reachable via goals.

tested on the following problematic Makefile:

all: a b
a:
touch a
b:
cp a b

Sample execution looks like:

$ while echo === && rm -f a b && make --shuffle; do sleep 1; done
===
random seed: --shuffle=1644097687
touch a
cp a b
===
random seed: --shuffle=1644097688
cp a b
cp: cannot stat 'a': No such file or directory
make: *** [Makefile:5: b] Error 1

Note: here first run succeeds while second run fails exposing the failure.

Some high level TODOs:
- No documentation for the optin yet.
- No(?) environment passing for recursive make.  I would prefer to share
  the same see across all calls to get easier reproducers.
- The dependency traversal is naive and uses potentially unbounded stack.
- srand() / rand() is used from system libc.  This might make it harder
  to reproduce a failure on another machine.  But maybe it's fine.

If the general shape is reasonable I can try to get it up to standard.

What do you think?

* src/dep.h: Add 'shuffle_goaldeps_recursive' helper.
* src/filedef.h (struct file): Add 'was_shuffled' bit to track visited files.
* src/main.c: Add '--shuffle' argument and it's handling.
* src/misc.c: Implement 'shuffle_goaldeps_recursive()' helper.
---
 src/dep.h |   1 +
 src/filedef.h |   2 +
 src/main.c|  23 +++
 src/misc.c| 109 ++
 4 files changed, 135 insertions(+)

diff --git a/src/dep.h b/src/dep.h
index e492a0b3..2b098650 100644
--- a/src/dep.h
+++ b/src/dep.h
@@ -135,3 +135,4 @@ struct dep *copy_dep_chain (const struct dep *d);
 struct goaldep *read_all_makefiles (const char **makefiles);
 void eval_buffer (char *buffer, const floc *floc);
 enum update_status update_goal_chain (struct goaldep *goals);
+struct goaldep * shuffle_goaldeps_recursive(struct goaldep * g);
diff --git a/src/filedef.h b/src/filedef.h
index 0b9f6e17..d36a6011 100644
--- a/src/filedef.h
+++ b/src/filedef.h
@@ -108,6 +108,8 @@ struct file
pattern-specific variables.  */
 unsigned int no_diag:1; /* True if the file failed to update and no
diagnostics has been issued (dontcare). */
+unsigned int was_shuffled:1; /* Did we already shuffle 'deps'? used when
+--shuffle passes through the graph.  */
   };
 
 
diff --git a/src/main.c b/src/main.c
index 2d98a64b..9731f3d3 100644
--- a/src/main.c
+++ b/src/main.c
@@ -233,6 +233,12 @@ static const int inf_jobs = 0;
 
 static char *jobserver_auth = NULL;
 
+#define NO_SHUFFLE (-1)
+#define RANDOM_SHUFFLE (0)
+static int arg_shuffle_seed = NO_SHUFFLE;
+static const int no_shuffle = NO_SHUFFLE;
+static const int random_shuffle = RANDOM_SHUFFLE;
+
 /* Handle for the mutex used on Windows to synchronize output of our
children under -O.  */
 
@@ -358,6 +364,8 @@ static const char *const usage[] =
 N_("\
   -R, --no-builtin-variables  Disable the built-in variable settings.\n"),
 N_("\
+  --shuffle[=seed]Perform random shuffle on prerequisites.\n"),
+N_("\
   -s, --silent, --quiet   Don't echo recipes.\n"),
 N_("\
   --no-silent Echo recipes (disable --silent mode).\n"),
@@ -472,6 +480,8 @@ static const struct command_switch switches[] =
 { CHAR_MAX+8, flag_off, _flag, 1, 1, 0, 0, _silent_flag,
   "no-silent" },
 { CHAR_MAX+9, string, _auth, 1, 0, 0, 0, 0, "jobserver-fds" },
+{ CHAR_MAX+10, positive_int, _shuffle_seed, 1, 0, 0, _shuffle,
+  _shuffle, "shuffle" },
 { 0, 0, 0, 0, 0, 0, 0, 0, 0 }
   };
 
@@ -1498,6 +1508,11 @@ main (int argc, char **argv, char **envp)
   arg_job_slots = env_slots;
   }
 
+  if (arg_shuffle_seed == RANDOM_SHUFFLE)
+  arg_shuffle_seed = (int)time(NULL);
+  if (arg_shuffle_seed != NO_SHUFFLE)
+  printf("random seed: --shuffle=%i\n", arg_shuffle_seed);
+
   /* Set a variable specifying whether stdout/stdin is hooked to a TTY.  */
 #ifdef HAVE_ISATTY
   if (isatty (fileno (stdout)))
@@ -2645,6 +2660,14 @@ main (int argc, char **argv, char **envp)
   O (fatal, NILF, _("No targets specified and no makefile found"));
 }
 
+  /* Shuffle prerequisites to catch makefiles with incomplete depends. */
+  if (arg_shuffle_seed != NO_SHUFFLE)
+{
+  /* TODO: provide portable deterministic rand/srand.  */
+  srand(arg_shuffle_seed);
+  goals = shuffle_goaldeps_recursive (goals);
+}
+
   /* Update the goals.  */
 
   DB (DB_BASIC, (_("Updating goal targets\n")));
diff --git a/src/misc.c b/src/misc.c
index f400135b..b46c6d07 100644
--- a/src/misc.c
+++ b/src/misc.c
@@ -854,3 +854,112 @@ mempcpy (void *dest, 

Re: Idea of triggering bugs in users' Makefiles

[Sergei Trofimovich]

On Fri, 04 Feb 2022 10:27:01 -0500
Paul Smith  wrote:

> On Fri, 2022-02-04 at 09:13 +0000, Sergei Trofimovich wrote:
> > 1. Enable parallel builds by GNU make by default
> > 
> > 2. Do not run dependencies in deterministic order by default:  
> 
> GNU make (unlike Ninja) is bound by the POSIX standard in terms of its
> behaviors.  The POSIX standard makes very clear the way in which make
> operates on prerequisites and neither of these changes are conforming
> to the standard.
> 
> So, it's not possible to modify the default behavior of GNU make in
> these  ways.  Not to mention that GNU make is also a foundational
> component of hundreds of thousands of build systems and changes that
> would cause a large number of them to break isn't acceptable, even in
> pursuit of a good cause.

Sounds good.

> The idea of having a non-deterministic order of prerequisite builds is
> something others have suggested but no one has implemented.  Of course
> it would not be possible to move the first prerequisite as that one is
> special but randomly rearranging the rest of them could be done.  This
> would require an option to enable of course; it could not be the
> default behavior.

Thank you!

-- 

  Sergei

Idea of triggering bugs in users' Makefiles

[Sergei Trofimovich]

Individual developers more often than not build large projects
in parallel to speed the process up with 'make -j '.

OS distributions would also prefer to enable parallel builds
by default. But there is a problem of deciding if it's safe
to build a package in general.

In small projects developers frequently forget that their
Makefile might be used in a 'make -j' setting and don't test
the scenario.

Recently I attempted to enable 'make -j $(nproc)' instead of
'make' for the whole NixOS software collection.

I found quite a few build failures. Most of them have very easy
fixes. The good simple example is 'cramfsswap':

  https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=996964

There one of the targets uses effect of another target, but does
not declare it. Contrived example:

# Makefile:
all: a b
a:
touch a
b:
cp a b

Here 'make all' happens to work, but 'make b' alone does not.

This made me thinking: what could GNU make do to make these
types of errors more obvious?

I cane up with two ideas:

1. Enable parallel builds by GNU make by default, so 'make'
   would mean 'make -j $(nproc)' unless asked otherwise.

   Some build systems (like ninja or waf) already do it.
   While sounding drastic I think it's a reasonable change
   longer term.

2. Do not run dependencies in deterministic order by default:

   Even when make is ran sequentially GNU make could do some
   effort to reorder targets to have a higher chance of executing
   steps in unexpected order.

   A possible implementation would be to pick a random seed at
   GNU make startup and perform target order permutation when
   allowed. If build were to fail random seed would be printed
   along with failure message. That way it would be trivial for
   others to reproduce the failure. Sometimes build failures
   are very hard to replicate.

I think both are worth implementing.

What do you think? Would it be reasonable to implement any or
both of these changes for GNU make?

Thanks!

-- 

  Sergei