Re: pkg/45077: pkgtools/pkg_install catch circular dependencies in add/perform.c

[Thomas Cort <tcort%minix3.org@localhost>]

The following reply was made to PR pkg/45077; it has been noted by GNATS.

From: Thomas Cort <tcort%minix3.org@localhost>
To: gnats-bugs%netbsd.org@localhost
Cc: 
Subject: Re: pkg/45077: pkgtools/pkg_install catch circular dependencies in
 add/perform.c
Date: Mon, 1 Aug 2011 21:02:33 -0400

 Update: the patch originally attached to this PR has been in use in Minix
 for a little while now. One of our power users, Jan Wieck, was able to
 exercise the infinite recursion check. If Jan wipes binutils and
 gcc, then adds binutils and gcc, he gets an infinite recursion which
 results in an EMFILE error.
 
 # pkgin -y rm binutils
 # pkg_add /usr/pkgsrc/packages/3.2.0/i386/All/gcc44-4.4.5*
 
 Jan tracked down the issue to a circular dependency between devel/gmp and
 devel/gcc44. The patch originally attached to this PR doesn't handle
 this well. Jan's analysis: "What happens is that pkg_do() and
 check_dependencies() call each other, but one of them opens some file or
 dir before calling the other. The error happens at depth=250, which
 makes total sense given that Minix has a 255 open file limit.
 Thomas defined the max depth as 1024, which is never reached in my case."
 
 Jan re-wrote the circular dependency checking patch to use a stack.
 The patch is attached. It allows the packages in the above example to be
 installed.
 
 diff --git a/pkgtools/pkg_install/files/add/perform.c 
b/pkgtools/pkg_install/files/add/perform.c
 index aa3dff3..ae71fe2 100644
 --- a/pkgtools/pkg_install/files/add/perform.c
 +++ b/pkgtools/pkg_install/files/add/perform.c
 @@ -102,6 +102,12 @@ struct pkg_task {
        char **dependencies;
  };
  
 +struct dependency_chain {
 +      const char *pkgpath;
 +      struct dependency_chain *next;
 +};
 +static struct dependency_chain *dependency_chain = NULL;
 +
  static const struct pkg_meta_desc {
        size_t entry_offset;
        const char *entry_filename;
 @@ -128,6 +134,9 @@ static const struct pkg_meta_desc {
  
  static int pkg_do(const char *, int, int);
  
 +static int dependency_push(const char *);
 +static void dependency_pop(void);
 +
  static int
  end_of_version(const char *opsys, const char *version_end)
  {
 @@ -1378,6 +1387,10 @@ pkg_do(const char *pkgpath, int mark_automatic, int 
top_level)
        char *archive_name;
        int status, invalid_sig;
        struct pkg_task *pkg;
 +      int rc;
 +
 +      if ((rc = dependency_push(pkgpath)) != 1)
 +              return rc;
  
        pkg = xcalloc(1, sizeof(*pkg));
  
 @@ -1572,6 +1585,7 @@ clean_memory:
        free(pkg->pkgname);
  clean_find_archive:
        free(pkg);
 +      dependency_pop();
        return status;
  }
  
 @@ -1588,5 +1602,77 @@ pkg_perform(lpkg_head_t *pkgs)
                free_lpkg(lpp);
        }
  
 +      if (dependency_chain != NULL) { /* ensure stack is empty */
 +              warnx("leaving pkg_perform with a non-empty stack.");
 +              ++errors;
 +      }
 +
        return errors;
  }
 +
 +
 +/*
 + * Add an element to the dependency chain and check for circular dependency
 + * while at it.
 + *
 + * returns 1 on success, 0 on circular dep detected, -1 on error.
 + */
 +static int
 +dependency_push(const char *pkgpath)
 +{
 +      struct dependency_chain *dep;
 +      struct dependency_chain **last_pdep;
 +
 +      /* Check if that package is already in the chain. */
 +      last_pdep = &dependency_chain;
 +      for (dep = *last_pdep; dep; last_pdep = &(dep->next), dep = dep->next) {
 +              if (strcmp(dep->pkgpath, pkgpath) == 0) {
 +                      /* Found it - that means we have a circular dependency 
*/
 +                      warnx("ignoring circular dependency:");
 +                      while (dep != NULL) {
 +                              fprintf(stderr, "- %s requires\n", 
dep->pkgpath);
 +                              dep = dep->next;
 +                      }
 +                      fprintf(stderr, "- %s\n", pkgpath);
 +                      return 0;
 +              }
 +      }
 +
 +      /* Not found. Add an entry to the end of the chain */
 +      dep = (struct dependency_chain *)malloc(sizeof(struct 
dependency_chain));
 +      if (dep == NULL) {
 +              fprintf(stderr, "Out of memory in dependency_push for %s\n",
 +                      pkgpath);
 +              return -1;
 +      }
 +
 +      dep->pkgpath = pkgpath;
 +      dep->next = NULL;
 +      *last_pdep = dep;
 +      return 1;
 +}
 +
 +
 +/*
 + * Remove the last entry from the dependency chain.
 + */
 +static void
 +dependency_pop(void)
 +{
 +      struct dependency_chain *dep = dependency_chain;
 +      struct dependency_chain **pdep = &dependency_chain;
 +
 +      /* This should never happen */
 +      if (dep == NULL) {
 +              warnx("empty dependency chain on pop");
 +              return;
 +      }
 +
 +      while (dep->next != NULL) {
 +              pdep = &(dep->next);
 +              dep = dep->next;
 +      }
 +
 +      free(dep);
 +      *pdep = NULL;
 +}