bugmake - Bugs: bug #13976, Regression in :: deps handling...

 
 

bug #13976: Regression in :: deps handling between V3.76 and V3.80

Submitter:  Reid Madsen <srmadsen>
Submitted:  Fri 29 Jul 2005 08:31:21 PM UTC
   
 
Severity:  3 - Normal Item Group:  Bug
Status:  Duplicate Privacy:  Public
Assigned to:  None Open/Closed:  Closed
Component Version:  3.80 Operating System:  Any
Fixed Release:  None Triage Status:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Sat 13 Jun 2009 11:18:56 PM UTC, comment #9: 

I'm going to close this as a duplicate of bug #13862.  Let me know if you don't agree.

Paul D. Smith <psmith>
Group administrator
Tue 30 Aug 2005 08:29:19 AM UTC, comment #8: 

OK, I have submitted a separate bug report #14334 on this topic.

Patrick

Patrick W Daly <pwdaly>
Mon 29 Aug 2005 05:53:45 PM UTC, comment #7: 

Actually Patrick's problem is not in any way related to Reids original problem, other than they both are related to double-colon rules.  Patrick's issue has nothing to do with parallel builds; it happens for make without -j as well.  In fact, GNU make does guarantee that every double-colon rule will be invoked serially (so that, in Patrick's situation, the first command to build test.tmp is run before the second command and they will never be run in parallel).  What make doesn't (any more) guarantee, and what this bug is originally about, is that all the prerequisites of the double-colon targets are also built such that all the prerequisites of one double-colon rule are built before any prerequisites of the next.

Patrick's issue is that when make gets to considering the second rule it sees that its target been updated already and doesn't bother to run the second rule at all.  This is quit different.  Put another way, changing make to behave as Patrick expects will in no way help Reid with his problem, and vice versa.

Patrick, it would be helpful to me if you could file a separate bug report on this issue so they can be considered separately.  Thanks!

Paul D. Smith <psmith>
Group administrator
Mon 29 Aug 2005 03:58:08 PM UTC, comment #6: 

I don't think Patrick's problem can be solved using the .WAIT approach or the order-only approach.

I can't think of a better example of why the dependencies of :: targets cannot be evaulated in parallel when the command for the first :: target is launched.

Please revert to 3.79.1 functionality for handling :: targets. 

Reid Madsen

Reid Madsen <srmadsen>
Mon 29 Aug 2005 01:48:41 PM UTC, comment #5: 

Hi everyone involved,

I came here to file a bug report and then found this one, which looks like mine. I am providing a software project with over 250 modules in Fortran and C to colleagues using different platforms, from Suns, Linux, WIN32, and portability is important to me. The software is portable, but recently I discovered that the makefile no longer works as expected under Linux with gnu make 3.80. It works with make 3.79.1. The problem is exactly this :: one. I created a simple makefile to demonstrate the problem.
test.tmp :: one.tmp
        echo Dependence One>>test.tmp

test.tmp :: two.tmp
        echo Dependence Two>>test.tmp

If test.tmp does not exist, both commands are to be executed. With 3.80, test.tmp is created with the first command, then tested against two.tmp, which is obviously older, and so the second is skipped. All other make's, including gnu make 3.79.1, test both conditions at the start and execute both commands, as I want.

So I tried replacing the :: with a single : with the result that 3.80 ignores the first block, telling me that the second has overwritten the first. The other make's behave as though I put everything into a single block. This is what I finally did to get portability, but then everything is reprocessed when only one block is necessary. Rather too much than too little, but it does take longer.

It seems one can debate the meaning of the :: as described in the gnu make manual, but consistency with other make programs should be paramount for something that is so fundamental. Also consistency with earlier versions. I do not want a special makefile just for gnu make 3.80 and later.

Regards, Patrick

Patrick W Daly <pwdaly>
Wed 03 Aug 2005 09:30:13 PM UTC, comment #4: 

Paul,

If you will implement .WAIT, I'll concede this one as well.  I read the bug report about .WAIT, but it did not click -- until now.

I'll admit that the processing of :: targets is a gray area, and the .WAIT approach is the clearest solution.

Like I said, if you will implement .WAIT, I'll concede on this bug as well.

In fact if you'll dump a few ideas my direction I'll take a stab at it.  I really need this solved.

My first thought is that a files deps list has to have two dimensions

struct dep {
  struct dep* wait_list;
  struct dep* next;
  ...
};

The dependencies are broken into individual lists on the .WAIT target, and the individual lists are then hooked up in order through the 'wait_list' member.  Transition between the dependency list occurs if all the current dependencies are up to date, and the 'wait_list' member is non-nil.

My only question about the '.WAIT' target is whether the following is valid:

all:: foo .WAIT bar
...
all:: foo
...
all:: bar
...
all:: bar foo
...
all:: bar .WAIT foo

Reid


Reid Madsen <srmadsen>
Wed 03 Aug 2005 08:42:54 PM UTC, comment #3: 

Hi Reid; I will definitely look to see if I can recover the previous behavior, because it seems useful.  However, I don't agree with your assessment that the docs guarantee the old behavior and the new behavior is not consistent with the documentation.  The docs say that the targets are treated individually, and so they are.  But just because they're treated individually does NOT mean that all the prerequisites of one are guaranteed to be completed before the prerequisites of another.  What it means is that the targets, although they share the same name, are treated by make as if they were different targets. Consider the situation if we were to change these so they were REALLY different targets, something like this:

  all: all1 all2 all3
  all1: all.prologue
  all2: all.serial all.parallel
  all3: all.epilogue

Now if you run this with -j12, ALL of those "leaf" targets will be invoked at the same time, and that's exactly how it should be done.  If there's no prerequisite relationship then parallel make will build as much as it possibly can at the same time.  I don't see any way that the documentation makes a statement about double-colon rules which is stronger than it makes for the normal rules in my example above.

In newer versions of GNU make there's a feature called an order-only prerequisite, which tries to help with the situation you describe here.  The downside to order-only prerequisites is that you have to define them on every single target, which can be annoying.

Other enhancement requests (see bug #13862) discuss a BSD make fetaure of a .WAIT special target which, when it appears in a prerequisite list, creates a stop-point in the parallelism.  With this model you'd write something like this:

  all: all.prologue .WAIT all.serial all.parallel .WAIT all.epilogue

This seems more generic than special-casing double-colon rules, but off the top of my head both of these features seem tricky to implement.

Paul D. Smith <psmith>
Group administrator
Fri 29 Jul 2005 11:47:58 PM UTC, comment #2: 

Solution is still flawed...
Pointers requested

And, seeing that the previous was sooo illegible, I've attached a version of remake.c that contains the net of my fix so far.

srmadsen

Reid Madsen <srmadsen>
Fri 29 Jul 2005 11:29:57 PM UTC, comment #1: 

** CORRECTION **

My initial fix was flawed.  I've included a replacement for update_file() below that corrects the problem.

srmadsen

--------------------------

static int
update_file (file, depth)
     struct file *file;
     unsigned int depth;
{
  register int status = 0;
  register struct file *f;

  f = file->double_colon ? file->double_colon : file;

  /* Prune the dependency graph: if we've already been here on this
     pass through the dependency graph, we don't have to go any further.
     We won't reap_children until we start the next pass, so no state
     change is possible below here until then.  */
  if (f->considered == considered)
    {
      DBF (DB_VERBOSE, _("Pruning file `%s'.\n"));
      return f->command_state == cs_finished ? f->update_status : 0;
    }

  /* This loop runs until we start commands for a double colon rule, or until
     the chain is exhausted. */
  for (; f != 0; f = f->prev)
    {
      f->considered = considered;

      status |= update_file_1 (f, depth);
      check_renamed (f);

      if (status != 0 && !keep_going_flag)
return status;

      if (f->command_state == cs_running
          || f->command_state == cs_deps_running)
        {
  /* Don't run the other :: rules for this
     file until this rule is finished.  */
          status = 0;
          break;
        }

    /* Okay no :: commands are running, we can continue
       processing :: deps. */
      {
struct dep *d;

f->considered = considered;

for (d = f->deps; d != 0; d = d->next)
  status |= update_file (d->file, depth + 1);
      }
    }
  return status;
}

Reid Madsen <srmadsen>
Fri 29 Jul 2005 08:31:21 PM UTC, original submission:  

Consider the following GNUmakefile:

  .PHONY: all all.prologue all.epilogue all.serial all.parallel
  SECS = 3

  all:: all.prologue
      @echo ---- cmd1 ----
  all:: all.serial all.parallel
      @echo ---- cmd2 ----
  all:: all.epilogue
      @echo ---- cmd3 ----

  all.prologue all.epilogue::
      @echo start - $@; sleep $(SECS); echo end   - $@

  all.parallel:
      @echo start - $@; sleep $(SECS); echo end   - $@

This makefile will be executed using the following command:

    make -j12

The intent of the makefile is to define certain actions which will occur first, then actions which will occur in serial/parallel, and then actions which will occur last.  This allows us to maximize parallelism, while still supporting serial processing -- all within the same Makefile.  This is defined by the following construct:

    all:: all.prologue               # first
        @true
    all:: all.serial all.parallel    # serial & parallel
        @true
    all:: all.epilogue               # last
        @true

This allows us to do the following (greatly simplified):

    all.prologue::
        @mkdir output

    all.parallel: $(TASKS)   # generate output/* (parallel)

    $(TASKS): ; generate $@ > output/$@

    all.epilogue::
        combine output/*

This works perfectly in version 3.76 of make using -j12, but no longer works in version 3.80 (and 3.78).

In version 3.76, the output from the makefile is:

    >> make-3.76 -j12
    start - all.prologue
    end - all.prologue
    ---- cmd1 ----
    start - all.serial
    start - all.parallel
    end - all.serial
    end - all.parallel
    ---- cmd2 ----
    start - all.epilogue
    end - all.epilogue
    ---- cmd3 ----

In version 3.80, the dependencies of ALL the 'all' targets are evaluated prior to the first command:

    >> make-3.80 -j12
    start - all.prologue
    start - all.epilogue
    start - all.serial
    start - all.parallel
    end - all.prologue
    end - all.epilogue
    end - all.parallel
    end - all.serial
    ---- cmd1 ----
    ---- cmd2 ----
    ---- cmd3 ----

In the GNUmake documentation I find the following regarding the order in which '::' targets are evaulated (emphasis added):

"When a target appears in multiple rules, all the rules must be the same type: all ordinary, or all double-colon.  If they are double-colon, each of them is INDEPENDENT OF ALL THE OTHERS."

"Double-colon rules with the same target are in fact COMPLETELY SEPARATE from one another.  EACH DOUBLE-COLON RULE IS PROCESSED INDIVIDUALLY, just as rules with different targets are evaluated."

Given that description, V3.76 is processing the Makefile correctly.  Version 3.80 (and 3.78) is broken in that it processes the dependencies of ALL the 'all::' targets before launching the command for the first one.  This violates the documented "INDEPENDENT OF ALL THE OTHERS" statement.

This bug is found at the end of the remake.c file in the update_file() function.  If the following code is removed from the 3.80 version of remake.c, then the documented functionality is restored:

#if 0
  THE FOLLOWING BREAKS DOCUMENTED '::' FUNCTIONALITY!

  /* Process the remaining rules in the double colon chain so they're marked
     considered.  Start their prerequisites, too.  */

  for (; f != 0 ; f = f->prev)
    {
      struct dep *d;

      f->considered = considered;

      for (d = f->deps; d != 0; d = d->next)
        status |= update_file (d->file, depth + 1);
    }
#endif

I've attached the Makefile shown above if you require it to debug the problem.

srmadsen

Reid Madsen <srmadsen>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

Attached Files
file #3299:  remake.c.fix added by srmadsen (40KiB - application/octet-stream - My work so far...)
file #3297:  GNUmakefile added by srmadsen (751B - application/octet-stream)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by psmith (Posted a comment)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only logged-in users can vote.

     

    Follow 4 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2009-06-13 psmith StatusNone Duplicate
        Open/ClosedOpen Closed
    2005-07-29 srmadsen Attached File- Added remake.c.fix, #2765
    2005-07-29 srmadsen Attached File- Added GNUmakefile, #2763

    Back to the top

    Powered by Savane 3.13-f8d8.
    Corresponding source code