Re: Reviving planned ldso changes

[Rich Felker <dalias@libc.org>]

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

On Wed, Jan 04, 2017 at 01:22:03AM -0500, Rich Felker wrote:
> On Wed, Jan 04, 2017 at 01:06:40AM -0500, Rich Felker wrote:
> > diff --git a/ldso/dynlink.c b/ldso/dynlink.c
> > index c689084..cb82b2c 100644
> > --- a/ldso/dynlink.c
> > +++ b/ldso/dynlink.c
> > @@ -67,6 +67,7 @@ struct dso {
> >  	char constructed;
> >  	char kernel_mapped;
> >  	struct dso **deps, *needed_by;
> > +	size_t next_dep;
> >  	char *rpath_orig, *rpath;
> >  	struct tls_module tls;
> >  	size_t tls_id;
> > @@ -1211,13 +1212,14 @@ 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);
> > +	while (!p->constructed) {
> > +		while (p->deps[p->next_dep] && p->deps[p->next_dep]->constructed)
> > +			p->next_dep++;
> > +		if (p->deps[p->next_dep]) {
> > +			p = p->deps[p->next_dep++];
> > +			continue;
> > +		}
> 
> I think this logic is probably broken in the case of circular
> dependencies, and will end up skipping ctors for some deps due to the
> increment in this line:
> 
> +			p = p->deps[p->next_dep++];
> 
> which happens before the new p's ctors have actually run. Omitting the
> increment here, however, would turn it into an infinite loop. We need
> some way to detect this case and let the dso with an indirect
> dependency on itself run its ctors once all non-circular deps have
> been satisfied. I don't now the right algorithm for this right off,
> though; suggestions would be welcome.

Here's a v2 of the patch with the above issues fixed, and some
comments that hopefully make it make sense. I still think there's more
logic needed to allow concurrent ctors from unrelated dlopen in
multiple threads, though.

Rich

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

diff --git a/ldso/dynlink.c b/ldso/dynlink.c
index c689084..fd59389 100644
--- a/ldso/dynlink.c
+++ b/ldso/dynlink.c
@@ -67,6 +67,7 @@ struct dso {
 	char constructed;
 	char kernel_mapped;
 	struct dso **deps, *needed_by;
+	size_t next_dep;
 	char *rpath_orig, *rpath;
 	struct tls_module tls;
 	size_t tls_id;
@@ -1090,9 +1091,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;
@@ -1211,13 +1215,21 @@ 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]->next_dep)
+				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,12 +1245,14 @@ 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->needed_by;
+	}
+	pthread_mutex_unlock(&init_fini_lock);
 }
 
 void __libc_start_init(void)