Re: Reviving planned ldso changes

[Rich Felker <dalias@libc.org>]

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

On Sun, Feb 26, 2017 at 04:39:25PM -0500, Rich Felker wrote:
> > > > > Are you sure? My understanding of what it does is:
> > > > > 
> > > > > 1. Descend a->b->c, construct c, and back up to b.
> > > > 
> > > > you did not explain how you get back to b after c
> > > > without a stack of visited dsos or modified c->needed_by.
> > > 
> > > Sorry, that should have been back up to a (c->needed_by). Then:
> > > 
> > > 2. Descend a->b->d, construct d, and back up to b.
> > > 
> > > The key point is that x->needed_by is always the first dso that pulled
> > > in x, so if we back all the way back up to x->needed_by, we'll revisit
> > > all later dsos which depend on x.
> > 
> > for that a->b transition has to happen twice,
> > but a.next_dep is already past b the second
> > time a is visited, so i still don't see why
> > this works.
> 
> Indeed, that looks like a bug. Removing the ++ from p =
> p->deps[p->next_dep++]; fixes it, but breaks the logic for avoiding
> circular descent (the condition !p->deps[p->next_dep]->next_dep). I
> think we need to add a separate field to control that, and a visited
> flag does not suffice; instead it should probably be something like
> the descent depth (or just sequence number) at which the DSO was first
> encountered, so that we can avoid descending into a DSO that we
> already started descending into and that will be descended into again
> as part of the backing-up process.

Here's a v4 of the patch that saves the "init parent" we descended
from so that it can return where it left off. There are a couple
gratuitous hunks left over adding setting of "needed_by" where it made
sense to be set, but it's not actually used anymore. They could be
dropped if desired but are probably nice to keep for the sake of
consistency of data, even thoough it's data we don't use.

I believe this can be extended to allow concurrent dlopen by amending
the case in the tree-walk where a dependency isn't constructed yet but
already has an "init parent" to check whether it's
pending-construction in the calling thread (recursive dlopen from a
ctor) or another thread; in the former case (as now) treat it as
already-constructed; in the latter, wait on a condvar that gets
signaled at the end of each construction, then continue the loop
without advancing p. There are probably some subtleties I'm missing,
though.

Rich

[-- Attachment #2: ctor_dep_order_v4.diff --]
[-- Type: text/plain, Size: 3553 bytes --]

diff --git a/ldso/dynlink.c b/ldso/dynlink.c
index a03f75e..b4754a5 100644
--- a/ldso/dynlink.c
+++ b/ldso/dynlink.c
@@ -66,7 +66,8 @@ struct dso {
 	char relocated;
 	char constructed;
 	char kernel_mapped;
-	struct dso **deps, *needed_by;
+	struct dso **deps, *needed_by, *init_parent;
+	size_t next_dep;
 	char *rpath_orig, *rpath;
 	struct tls_module tls;
 	size_t tls_id;
@@ -934,6 +935,7 @@ static struct dso *load_library(const char *name, struct dso *needed_by)
 		if (!ldso.prev) {
 			tail->next = &ldso;
 			ldso.prev = tail;
+			ldso.needed_by = needed_by;
 			tail = ldso.next ? ldso.next : &ldso;
 		}
 		return &ldso;
@@ -1090,9 +1092,12 @@ static void load_deps(struct dso *p)
 				if (runtime) longjmp(*rtld_fail, 1);
 				continue;
 			}
-			if (runtime) {
-				tmp = realloc(*deps, sizeof(*tmp)*(ndeps+2));
-				if (!tmp) longjmp(*rtld_fail, 1);
+			tmp = realloc(*deps, sizeof(*tmp)*(ndeps+2));
+			if (!tmp) {
+				error("Error allocating dependency data for %s: %m",
+					p->name);
+				if (runtime) longjmp(*rtld_fail, 1);
+			} else {
 				tmp[ndeps++] = dep;
 				tmp[ndeps] = 0;
 				*deps = tmp;
@@ -1110,7 +1115,7 @@ static void load_preload(char *s)
 		for (z=s; *z && !isspace(*z) && *z!=':'; z++);
 		tmp = *z;
 		*z = 0;
-		load_library(s, 0);
+		load_library(s, head);
 		*z = tmp;
 	}
 }
@@ -1211,13 +1216,23 @@ void __libc_exit_fini()
 static void do_init_fini(struct dso *p)
 {
 	size_t dyn[DYN_CNT];
-	int need_locking = libc.threads_minus_1;
-	/* Allow recursive calls that arise when a library calls
-	 * dlopen from one of its constructors, but block any
-	 * other threads until all ctors have finished. */
-	if (need_locking) pthread_mutex_lock(&init_fini_lock);
-	for (; p; p=p->prev) {
-		if (p->constructed) continue;
+	pthread_mutex_lock(&init_fini_lock);
+	/* Construct in dependency order without any recursive state. */
+	while (p && !p->constructed) {
+		/* The following loop descends into the first dependency
+		 * that is neither alredy constructed nor pending
+		 * construction due to circular deps, stopping only
+		 * when it reaches a dso with no remaining dependencies
+		 * to descend into. */
+		while (p->deps && p->deps[p->next_dep]) {
+			if (!p->deps[p->next_dep]->constructed &&
+			    !p->deps[p->next_dep]->init_parent) {
+				p->deps[p->next_dep]->init_parent = p;
+				p = p->deps[p->next_dep++];
+			} else {
+				p->next_dep++;
+			}
+		}
 		p->constructed = 1;
 		decode_vec(p->dynv, dyn, DYN_CNT);
 		if (dyn[0] & ((1<<DT_FINI) | (1<<DT_FINI_ARRAY))) {
@@ -1233,17 +1248,19 @@ static void do_init_fini(struct dso *p)
 			size_t *fn = laddr(p, dyn[DT_INIT_ARRAY]);
 			while (n--) ((void (*)(void))*fn++)();
 		}
-		if (!need_locking && libc.threads_minus_1) {
-			need_locking = 1;
-			pthread_mutex_lock(&init_fini_lock);
-		}
-	}
-	if (need_locking) pthread_mutex_unlock(&init_fini_lock);
+		/* Revisit "parent" dso which caused the just-constructed
+		 * dso to be pulled in as a dependency. On the next loop
+		 * iteration we will either descend to construct a sibling
+		 * of the just-constructed dso, or finish constructing the
+		 * parent if no unfinished deps remain. */
+		p = p->init_parent;
+	}
+	pthread_mutex_unlock(&init_fini_lock);
 }
 
 void __libc_start_init(void)
 {
-	do_init_fini(tail);
+	do_init_fini(head);
 }
 
 static void dl_debug_state(void)
@@ -1731,7 +1748,7 @@ end:
 	__release_ptc();
 	if (p) gencnt++;
 	pthread_rwlock_unlock(&lock);
-	if (p) do_init_fini(orig_tail);
+	if (p) do_init_fini(p);
 	pthread_setcancelstate(cs, 0);
 	return p;
 }