Requirements depth in setup.exe

Requirements depth in setup.exe

[Thrall, Bryan]

[-- Attachment #1: Type: text/plain, Size: 1429 bytes --]


We have a custom cygwin mirror for distributing our software and
occasionally run into problems where a package that is listed in the
setup.ini as being required isn't installed like it should be. For
example, xterm is required (eventually) but isn't installed by default.
The problem seems to be a limitation in setup.exe:
packageversion::set_requirements() has a hardcoded recursion depth of 5,
and as best I can tell, xterm for our purposes has a depth of 6.
Increasing the limit to 20 allowed xterm to be set to install like it
should be.

It occurred to me, without any evidence whatsoever, this limit might
also explain the messages on cygwin-users about people who don't get
certain required packages installed (such as
http://cygwin.com/ml/cygwin/2008-01/msg00439.html) even though they are
listed as required.

This seems like a harsh recursion limit, especially as the number of
Cygwin packages grows; please consider the attached patch (based on CVS
HEAD) for a (IMHO) better solution which does not recurse once a
particular package has been visited.

ChangeLog entry:

2008-06-26  Bryan Thrall <bryan.thrall@flightsafety.com>

	* package_meta.cc, package_meta.h, package_version.cc, 
	package_version.h: Keep track of visited packages instead
	  of hardcoding maximum depth to avoid unlimited recursion.

--
Bryan Thrall
FlightSafety International
bryan.thrall@flightsafety.com
 

[-- Attachment #2: deplimit.patch --]
[-- Type: application/octet-stream, Size: 6505 bytes --]

Index: package_meta.cc
===================================================================
RCS file: /cvs/cygwin-apps/setup/package_meta.cc,v
retrieving revision 2.52
diff -u -w -p -r2.52 package_meta.cc
--- package_meta.cc	17 Apr 2006 16:13:17 -0000	2.52
+++ package_meta.cc	26 Jun 2008 22:31:44 -0000
@@ -411,22 +411,22 @@ packagemeta::set_action (packageversion 
 }
 
 int
-packagemeta::set_requirements (trusts deftrust, size_t depth)
+packagemeta::set_requirements (trusts deftrust, set<packagemeta *>& visitedpkgs)
 {
   if (visited())
     return 0;
   /* Only prevent further checks once we have been required by something else */
-  if (depth)
+  if (!visitedpkgs.empty())
     visited(true);
   int changed = 0;
   /* handle build-depends */
-  if (depth == 0 && desired.sourcePackage ().picked())
-    changed += desired.sourcePackage ().set_requirements (deftrust, depth + 1);
+  if (visitedpkgs.empty() && desired.sourcePackage ().picked())
+    changed += desired.sourcePackage ().set_requirements (deftrust, visitedpkgs);
   if (!desired || (desired != installed && !desired.picked ()))
     /* uninstall || source only */
     return changed;
 
-  return changed + desired.set_requirements (deftrust, depth);
+  return changed + desired.set_requirements (deftrust, visitedpkgs);
 }
 
 
Index: package_meta.h
===================================================================
RCS file: /cvs/cygwin-apps/setup/package_meta.h,v
retrieving revision 2.36
diff -u -w -p -r2.36 package_meta.h
--- package_meta.h	17 Apr 2006 16:13:17 -0000	2.36
+++ package_meta.h	26 Jun 2008 22:31:44 -0000
@@ -80,10 +80,13 @@ public:
   void set_action (packageversion const &default_version);
   void set_action (_actions, packageversion const & default_version);
   void uninstall ();
-  int set_requirements (trusts deftrust, size_t depth);
+  int set_requirements (trusts deftrust, std::set<packagemeta *>& visitedpkgs);
   // explicit separation for generic programming.
   int set_requirements (trusts deftrust) 
-    { return set_requirements (deftrust, 0); }
+  { 
+      std::set<packagemeta *> visitedpkgs;
+      return set_requirements (deftrust, visitedpkgs);
+  }
 
   std::string action_caption () const;
   packageversion trustp (trusts const t) const
Index: package_version.cc
===================================================================
RCS file: /cvs/cygwin-apps/setup/package_version.cc,v
retrieving revision 2.27
diff -u -w -p -r2.27 package_version.cc
--- package_version.cc	6 Aug 2006 22:22:39 -0000	2.27
+++ package_version.cc	26 Jun 2008 22:31:45 -0000
@@ -385,7 +385,7 @@ checkForSatisfiable (PackageSpecificatio
 }
 
 static int
-select (trusts deftrust, size_t depth, packagemeta *required,
+select (trusts deftrust, set<packagemeta *>& visitedpkgs, packagemeta *required,
         const packageversion &aVersion)
 {
   /* preserve source */
@@ -395,11 +395,11 @@ select (trusts deftrust, size_t depth, p
   required->desired.pick (required->installed != required->desired);
   required->desired.sourcePackage ().pick (sourceticked);
   /* does this requirement have requirements? */
-  return required->set_requirements (deftrust, depth + 1);
+  return required->set_requirements (deftrust, visitedpkgs);
 }
 
 static int
-processOneDependency (trusts deftrust, size_t depth,
+processOneDependency (trusts deftrust, set<packagemeta *>& visitedpkgs,
                       PackageSpecification *spec)
 {
   /* TODO: add this to a set of packages to be offered to meet the
@@ -411,7 +411,7 @@ processOneDependency (trusts deftrust, s
 
   packageversion trusted = required->trustp(deftrust);
   if (spec->satisfies (trusted)) {
-      return select (deftrust, depth, required, trusted);
+      return select (deftrust, visitedpkgs, required, trusted);
   }
 
   log (LOG_TIMESTAMP) << "Warning, the default trust level for package "
@@ -426,17 +426,19 @@ processOneDependency (trusts deftrust, s
       /* assert ?! */
       return 0;
   
-  return select (deftrust, depth, required, *v);
+  return select (deftrust, visitedpkgs, required, *v);
 }
 
 int
-packageversion::set_requirements (trusts deftrust, size_t depth)
+packageversion::set_requirements (trusts deftrust, set<packagemeta *>& visitedpkgs)
 {
   int changed = 0;
   vector <vector <PackageSpecification *> *>::iterator dp = depends ()->begin();
-  /* cheap test for too much recursion */
-  if (depth > 5)
-    return changed;
+  packagedb db;
+  packagemeta * mypkg = db.findBinary(PackageSpecification(Name()));
+  if (visitedpkgs.find(mypkg) != visitedpkgs.end())
+    return changed; /* already visited, so don't recurse into dependencies */
+  visitedpkgs.insert(mypkg); /* mark as visited */
   /* walk through each and clause */
   while (dp != depends ()->end())
     {
@@ -464,7 +466,7 @@ packageversion::set_requirements (trusts
 	     requirement. (*i is the packagespec that can be satisfied.)
 	     */
 	  ++dp;
-	  changed += processOneDependency (deftrust, depth, *i) + 1;
+          changed += processOneDependency (deftrust, visitedpkgs, *i) + 1;
 	  continue;
 	}
       /* check each or clause for an installable version */
@@ -473,7 +475,7 @@ packageversion::set_requirements (trusts
 	{
 	  /* we found a package that can be installed to meet the requirement */
 	  ++dp;
-	  changed += processOneDependency (deftrust, depth, *i) + 1;
+          changed += processOneDependency (deftrust, visitedpkgs, *i) + 1;
 	  continue;
 	}
       ++dp;
Index: package_version.h
===================================================================
RCS file: /cvs/cygwin-apps/setup/package_version.h,v
retrieving revision 2.23
diff -u -w -p -r2.23 package_version.h
--- package_version.h	17 Apr 2006 16:41:33 -0000	2.23
+++ package_version.h	26 Jun 2008 22:31:45 -0000
@@ -45,6 +45,7 @@ class CategoryList;
 #include "PackageTrust.h"
 #include "script.h"
 #include <vector>
+#include <set>
 
 typedef enum
 {
@@ -69,6 +70,9 @@ typedef enum
 }
 package_type_t;
 
+/* forward declarations */
+class packagemeta;
+
 /* A wrapper class to be copied by value that
    references the same package.
    Nothing is virtual, because the wrapper cannot be inherited.
@@ -139,7 +143,7 @@ public:
   void scan();
 
   /* ensure that the depends clause is satisfied */
-  int set_requirements (trusts deftrust, size_t depth = 0);
+  int set_requirements (trusts deftrust, std::set<packagemeta *>& visitedpkgs = std::set<packageversion *>());
 
   void addScript(Script const &);
   std::vector <Script> &scripts();

Re: Requirements depth in setup.exe

[Christopher Faylor]

On Thu, Jun 26, 2008 at 05:46:22PM -0500, Thrall, Bryan wrote:
>We have a custom cygwin mirror for distributing our software and
>occasionally run into problems where a package that is listed in the
>setup.ini as being required isn't installed like it should be.  For
>example, xterm is required (eventually) but isn't installed by default.
>The problem seems to be a limitation in setup.exe:
>packageversion::set_requirements() has a hardcoded recursion depth of
>5, and as best I can tell, xterm for our purposes has a depth of 6.
>Increasing the limit to 20 allowed xterm to be set to install like it
>should be.
>
>It occurred to me, without any evidence whatsoever, this limit might
>also explain the messages on cygwin-users about people who don't get
>certain required packages installed (such as
>http://cygwin.com/ml/cygwin/2008-01/msg00439.html) even though they are
>listed as required.
>
>This seems like a harsh recursion limit, especially as the number of
>Cygwin packages grows; please consider the attached patch (based on CVS
>HEAD) for a (IMHO) better solution which does not recurse once a
>particular package has been visited.

Wow, I'll say it sounds harsh.  Five?  I had no idea it was that low.

>ChangeLog entry:
>
>2008-06-26  Bryan Thrall <bryan.thrall@flightsafety.com>
>
>	* package_meta.cc, package_meta.h, package_version.cc, 
>	package_version.h: Keep track of visited packages instead
>	  of hardcoding maximum depth to avoid unlimited recursion.

I just eyeballed the change.  I like the way you implemented it but
I'll defer to the people who are more familiar with the code.

But, even if the change isn't accepted I'd say that we probably owe
you a debt of gratitude for tracking this down.  I wouldn't be surprised
if you are right and this is responsible for many strange dependency
problems.

Can someone look at this and consider it for the trunk and the branch?

Thanks for the patch.

cgf

Re: Requirements depth in setup.exe

[Reini Urban]

Christopher Faylor schrieb:
> On Thu, Jun 26, 2008 at 05:46:22PM -0500, Thrall, Bryan wrote:
>> We have a custom cygwin mirror for distributing our software and
>> occasionally run into problems where a package that is listed in the
>> setup.ini as being required isn't installed like it should be.  For
>> example, xterm is required (eventually) but isn't installed by default.
>> The problem seems to be a limitation in setup.exe:
>> packageversion::set_requirements() has a hardcoded recursion depth of
>> 5, and as best I can tell, xterm for our purposes has a depth of 6.
>> Increasing the limit to 20 allowed xterm to be set to install like it
>> should be.
>>
>> It occurred to me, without any evidence whatsoever, this limit might
>> also explain the messages on cygwin-users about people who don't get
>> certain required packages installed (such as
>> http://cygwin.com/ml/cygwin/2008-01/msg00439.html) even though they are
>> listed as required.
>>
>> This seems like a harsh recursion limit, especially as the number of
>> Cygwin packages grows; please consider the attached patch (based on CVS
>> HEAD) for a (IMHO) better solution which does not recurse once a
>> particular package has been visited.
> 
> Wow, I'll say it sounds harsh.  Five?  I had no idea it was that low.
> 
>> ChangeLog entry:
>>
>> 2008-06-26  Bryan Thrall <bryan.thrall@flightsafety.com>
>>
>> 	* package_meta.cc, package_meta.h, package_version.cc, 
>> 	package_version.h: Keep track of visited packages instead
>> 	  of hardcoding maximum depth to avoid unlimited recursion.
> 
> I just eyeballed the change.  I like the way you implemented it but
> I'll defer to the people who are more familiar with the code.
> 
> But, even if the change isn't accepted I'd say that we probably owe
> you a debt of gratitude for tracking this down.  I wouldn't be surprised
> if you are right and this is responsible for many strange dependency
> problems.
> 
> Can someone look at this and consider it for the trunk and the branch?
> 
> Thanks for the patch.

Tracked at http://sourceware.org/bugzilla/show_bug.cgi?id=6699

I left the default assignee to cygwin-apps@ to test the recent change 
but apparently the notification email didn't arrive here.
-- 
Reini Urban
http://phpwiki.org/  http://murbreak.at/

Re: Requirements depth in setup.exe

[Christopher Faylor]

On Fri, Jun 27, 2008 at 03:01:45PM +0200, Reini Urban wrote:
>I left the default assignee to cygwin-apps@ to test the recent change
>but apparently the notification email didn't arrive here.

Sigh.  Of course it didn't.  I forgot to subscribe the bugzilla account
(whatever that might be) to cygwin-apps.  I'm checking now.

Doh.

cgf

Re: Requirements depth in setup.exe

[Brian Dessent]

"Thrall, Bryan" wrote:

> We have a custom cygwin mirror for distributing our software and
> occasionally run into problems where a package that is listed in the
> setup.ini as being required isn't installed like it should be. For
> example, xterm is required (eventually) but isn't installed by default.
> The problem seems to be a limitation in setup.exe:
> packageversion::set_requirements() has a hardcoded recursion depth of 5,
> and as best I can tell, xterm for our purposes has a depth of 6.
> Increasing the limit to 20 allowed xterm to be set to install like it
> should be.

For the record, as of right now the longest dep chains[1] in setup.ini
top out at 12:

octave-htmldoc -> octave-doc -> octave -> gnuplot -> xorg-x11-bin-dlls
-> xorg-x11-base -> xorg-x11-libs-data -> tar -> bzip2 -> coreutils ->
tzcode -> gawk

octave-headers -> octave-devel -> octave -> gnuplot -> xorg-x11-bin-dlls
-> xorg-x11-base -> xorg-x11-libs-data -> tar -> bzip2 -> coreutils ->
tzcode -> gawk

There are many more at lesser lengths that are still greater than 5, so
it's clear that 5 is too small.

However, I'm concerned that this patch touches a lot more than just a
recursion/looping safety valve.  It seems like you're duplicating the
existing functionality of the 'visited' flag in a very inefficient way
by maintaining that set.  I'm going to have to play with this some more
before I can come to a conclusion.

Brian

[1] I wrote a rather brute force perl script to compute this:
<http://dessent.net/tmp/cygpackage-longest-path.pl>.  The output takes a
while to compute and looks like
<http://dessent.net/tmp/cygpackage-dep-chains.txt>.

RE: Requirements depth in setup.exe

[Thrall, Bryan]

Brian Dessent wrote on Friday, June 27, 2008 4:46 PM:

> "Thrall, Bryan" wrote:
> 
>> We have a custom cygwin mirror for distributing our software and
>> occasionally run into problems where a package that is listed in the
>> setup.ini as being required isn't installed like it should be. For
>> example, xterm is required (eventually) but isn't installed by
default.
>> The problem seems to be a limitation in setup.exe:
>> packageversion::set_requirements() has a hardcoded recursion depth of
5,
>> and as best I can tell, xterm for our purposes has a depth of 6.
>> Increasing the limit to 20 allowed xterm to be set to install like it
>> should be.
> 
> For the record, as of right now the longest dep chains[1] in setup.ini
> top out at 12:
> 
> octave-htmldoc -> octave-doc -> octave -> gnuplot -> xorg-x11-bin-dlls
> -> xorg-x11-base -> xorg-x11-libs-data -> tar -> bzip2 -> coreutils ->
> tzcode -> gawk
> 
> octave-headers -> octave-devel -> octave -> gnuplot ->
xorg-x11-bin-dlls
> -> xorg-x11-base -> xorg-x11-libs-data -> tar -> bzip2 -> coreutils ->
> tzcode -> gawk
> 
> There are many more at lesser lengths that are still greater than 5,
so
> it's clear that 5 is too small.

Hmmm... my own brute force perl script found a maximum depth of 14, but
we mostly agree :) Probably mine has a bug somewhere; I'm very new with
Perl.

> However, I'm concerned that this patch touches a lot more than just a
> recursion/looping safety valve.  It seems like you're duplicating the
> existing functionality of the 'visited' flag in a very inefficient way
> by maintaining that set.  I'm going to have to play with this some
more
> before I can come to a conclusion.

It seemed like purpose of the visited flag overlapped, but I wasn't
familiar enough with the code to say it was equivalent.

Perhaps the (depth > 5) check in packageversion::set_requirements()
isn't needed at all?

-- 
Bryan Thrall
FlightSafety International
bryan.thrall@flightsafety.com

Re: Requirements depth in setup.exe

[Christopher Faylor]

Sorry for the top posting but could we get closure on the issues discussed
below?  It seems like this problem could be impacting a lot of people and
this is a bug that really needs to be fixed.

I'm going to raise the recursion check from 5 to 30 but I am not sure that
this will actually have a beneficial effect.

cgf

On Fri, Jun 27, 2008 at 05:26:27PM -0500, Thrall, Bryan wrote:
>Brian Dessent wrote on Friday, June 27, 2008 4:46 PM:
>
>> "Thrall, Bryan" wrote:
>> 
>>> We have a custom cygwin mirror for distributing our software and
>>> occasionally run into problems where a package that is listed in the
>>> setup.ini as being required isn't installed like it should be. For
>>> example, xterm is required (eventually) but isn't installed by
>default.
>>> The problem seems to be a limitation in setup.exe:
>>> packageversion::set_requirements() has a hardcoded recursion depth of
>5,
>>> and as best I can tell, xterm for our purposes has a depth of 6.
>>> Increasing the limit to 20 allowed xterm to be set to install like it
>>> should be.
>> 
>> For the record, as of right now the longest dep chains[1] in setup.ini
>> top out at 12:
>> 
>> octave-htmldoc -> octave-doc -> octave -> gnuplot -> xorg-x11-bin-dlls
>> -> xorg-x11-base -> xorg-x11-libs-data -> tar -> bzip2 -> coreutils ->
>> tzcode -> gawk
>> 
>> octave-headers -> octave-devel -> octave -> gnuplot ->
>xorg-x11-bin-dlls
>> -> xorg-x11-base -> xorg-x11-libs-data -> tar -> bzip2 -> coreutils ->
>> tzcode -> gawk
>> 
>> There are many more at lesser lengths that are still greater than 5,
>so
>> it's clear that 5 is too small.
>
>Hmmm... my own brute force perl script found a maximum depth of 14, but
>we mostly agree :) Probably mine has a bug somewhere; I'm very new with
>Perl.
>
>> However, I'm concerned that this patch touches a lot more than just a
>> recursion/looping safety valve.  It seems like you're duplicating the
>> existing functionality of the 'visited' flag in a very inefficient way
>> by maintaining that set.  I'm going to have to play with this some
>more
>> before I can come to a conclusion.
>
>It seemed like purpose of the visited flag overlapped, but I wasn't
>familiar enough with the code to say it was equivalent.
>
>Perhaps the (depth > 5) check in packageversion::set_requirements()
>isn't needed at all?
>
>-- 
>Bryan Thrall
>FlightSafety International
>bryan.thrall@flightsafety.com
>
>