NetBSD Problem Report #45077

From www@NetBSD.org  Fri Jun 17 14:26:40 2011
Return-Path: <www@NetBSD.org>
Received: from mail.netbsd.org (mail.netbsd.org [204.152.190.11])
	by www.NetBSD.org (Postfix) with ESMTP id 9C54263C847
	for <gnats-bugs@gnats.NetBSD.org>; Fri, 17 Jun 2011 14:26:40 +0000 (UTC)
Message-Id: <20110617142639.C9DC463C6C2@www.NetBSD.org>
Date: Fri, 17 Jun 2011 14:26:39 +0000 (UTC)
From: tcort@minix3.org
Reply-To: tcort@minix3.org
To: gnats-bugs@NetBSD.org
Subject: pkgtools/pkg_install catch circular dependencies in add/perform.c
X-Send-Pr-Version: www-1.0

>Number:         45077
>Category:       pkg
>Synopsis:       pkgtools/pkg_install catch circular dependencies in add/perform.c
>Confidential:   no
>Severity:       non-critical
>Priority:       medium
>Responsible:    agc
>State:          open
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Fri Jun 17 14:30:00 +0000 2011
>Last-Modified:  Thu Aug 04 21:29:29 +0000 2011
>Originator:     Thomas Cort
>Release:        N/A
>Organization:
Minix3
>Environment:
Minix 192.168.122.210 3.2.0 i686
>Description:
During the porting of pkgsrc to Minix, a developer ran into an issue 
where the pkg_do() function in add/perform.c would go into an infinite 
recursion due to a circular dependency. The dependency issue was caused 
by different versions of the pkgsrc tree being used to compile different 
packages.

The patch below adds a counter to pkg_do(). Every time pkg_do() gets
called recursively, the counter is incremented. If the counter exceeds
MAX_PKG_DO_RECURSION_DEPTH it is assumed that a circular dependency
has been detected, a warning is printed, and the recursion is stopped.

This patch was moved from pkg/45047 so that the PR would
only deal with one problem.
>How-To-Repeat:
I wasn't able to recreate the conditions that caused the
circular dependency.
>Fix:
--- a/pkg_install/files/add/perform.c	Thu Jun 16 19:34:17 2011
+++ b/pkg_install/files/add/perform.c	Thu Jun 16 19:38:27 2011
@@ -60,6 +60,8 @@
 #include "add.h"
 #include "version.h"

+#define MAX_PKG_DO_RECURSION_DEPTH (1024)
+
 struct pkg_meta {
 	char *meta_contents;
 	char *meta_comment;
@@ -126,7 +128,7 @@
 	{ 0, NULL, 0, 0 },
 };

-static int pkg_do(const char *, int, int);
+static int pkg_do(const char *, int, int, int);

 static int
 end_of_version(const char *opsys, const char *version_end)
@@ -738,7 +740,7 @@
 			continue;

 		case PLIST_CMD:
-			if (format_cmd(cmd, sizeof(cmd), p->name, pkg->prefix, last_file))
+			if (format_cmd(cmd, sizeof(cmd), p->name, pkg->install_prefix, last_file))
 				return -1;
 			printf("Executing '%s'\n", cmd);
 			if (!Fake && system(cmd))
@@ -1093,7 +1095,7 @@
 }

 static int
-check_dependencies(struct pkg_task *pkg)
+check_dependencies(struct pkg_task *pkg, int depth)
 {
 	plist_t *p;
 	char *best_installed;
@@ -1124,7 +1126,7 @@
 				    p->name);
 				continue;
 			}
-			if (pkg_do(p->name, 1, 0)) {
+			if (pkg_do(p->name, 1, 0, depth)) {
 				if (ForceDepends) {
 					warnx("Can't install dependency %s, "
 					    "continuing", p->name);
@@ -1373,12 +1375,17 @@
  * Install a single package.
  */
 static int
-pkg_do(const char *pkgpath, int mark_automatic, int top_level)
+pkg_do(const char *pkgpath, int mark_automatic, int top_level, int depth)
 {
 	char *archive_name;
 	int status, invalid_sig;
 	struct pkg_task *pkg;

+	if (++depth > MAX_PKG_DO_RECURSION_DEPTH) {
+		warnx("circular dependency detected");
+		return -1;
+	}
+
 	pkg = xcalloc(1, sizeof(*pkg));

 	status = -1;
@@ -1490,7 +1497,7 @@
 			pkg->install_logdir_real = NULL;
 		}

-		if (check_dependencies(pkg))
+		if (check_dependencies(pkg, depth))
 			goto nuke_pkgdb;
 	} else {
 		/*
@@ -1498,7 +1505,7 @@
 		 * Install/update dependencies first and
 		 * write the current package to disk afterwards.
 		 */ 
-		if (check_dependencies(pkg))
+		if (check_dependencies(pkg, depth))
 			goto clean_memory;

 		if (write_meta_data(pkg))
@@ -1582,7 +1589,7 @@
 	lpkg_t *lpp;

 	while ((lpp = TAILQ_FIRST(pkgs)) != NULL) {
-		if (pkg_do(lpp->lp_name, Automatic, 1))
+		if (pkg_do(lpp->lp_name, Automatic, 1, 0))
 			++errors;
 		TAILQ_REMOVE(pkgs, lpp, lp_link);
 		free_lpkg(lpp);

>Release-Note:

>Audit-Trail:
From: Thomas Cort <tcort@minix3.org>
To: gnats-bugs@netbsd.org
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;
 +}

Responsible-Changed-From-To: pkg-manager->agc
Responsible-Changed-By: wiz@NetBSD.org
Responsible-Changed-When: Thu, 04 Aug 2011 21:29:29 +0000
Responsible-Changed-Why:
Over to maintainer.


>Unformatted:

NetBSD Home
NetBSD PR Database Search

(Contact us) $NetBSD: query-full-pr,v 1.39 2013/11/01 18:47:49 spz Exp $
$NetBSD: gnats_config.sh,v 1.8 2006/05/07 09:23:38 tsutsui Exp $
Copyright © 1994-2007 The NetBSD Foundation, Inc. ALL RIGHTS RESERVED.