Use a better algorithm for calculating the grpsym library order.

The existing code did a full recursive walk for O(horrible).  Instead,
keep a single list of nodes plus the index of the first node whose
children haven't been scanned; lookup until that index catches the
end, appending the unscanned children of the node at the index.  This
also makes the grpsym list order match that calculated by FreeBSD and
glibc in dependency trees with inconsistent ordering of dependent libs.

To make this easier and more cache friendly, convert grpsym_list
to a vector: the size is bounded by the number of objects currently
loaded.

Other, related fixes:
 * increment the grpsym generation number _after_ pushing the loading
   object onto its grpsym list, to avoid double counting it
 * increment the grpsym generation number when building the grpsym list
   for an already loaded object that's being dlopen()ed, to avoid
   incomplete grpsym lists
 * use a more accurate test of whether an object already has a grpsym list

Prompted by a diff from Nathanael Rensen (nathanael (at) list.polymorpheus.com)
that pointed to _dl_cache_grpsym_list() as a performance bottleneck.

Much proding from robert@, sthen@, aja@, jca@
no problem reports after being in snaps
ok mpi@

5 files changed, 83 insertions, 59 deletions

diff --git a/libexec/ld.so/dlfcn.c b/libexec/ld.so/dlfcn.c
index b74a4e9d81c..138530ba81e 100644
--- a/libexec/ld.so/dlfcn.c
+++ b/libexec/ld.so/dlfcn.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: dlfcn.c,v 1.104 2019/08/04 23:51:45 guenther Exp $ */
+/*	$OpenBSD: dlfcn.c,v 1.105 2019/10/03 06:10:53 guenther Exp $ */
 
 /*
  * Copyright (c) 1998 Per Fogelstrom, Opsycon AB
@@ -90,12 +90,9 @@ dlopen(const char *libname, int flags)
 	_dl_link_dlopen(object);
 
 	if (OBJECT_REF_CNT(object) > 1) {
-		/* if opened but grpsym_list has not been created */
-		if (OBJECT_DLREF_CNT(object) == 1) {
-			/* add first object manually */
-			_dl_link_grpsym(object, 1);
-			_dl_cache_grpsym_list(object);
-		}
+		/* if opened but grpsym_vec has not been filled in */
+		if (object->grpsym_vec.len == 0)
+			_dl_cache_grpsym_list_setup(object);
 		goto loaded;
 	}
 
diff --git a/libexec/ld.so/library_subr.c b/libexec/ld.so/library_subr.c
index d5771e094c4..32b96ca10ce 100644
--- a/libexec/ld.so/library_subr.c
+++ b/libexec/ld.so/library_subr.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: library_subr.c,v 1.48 2017/08/28 14:06:22 deraadt Exp $ */
+/*	$OpenBSD: library_subr.c,v 1.49 2019/10/03 06:10:54 guenther Exp $ */
 
 /*
  * Copyright (c) 2002 Dale Rahn
@@ -523,35 +523,42 @@ _dl_link_child(elf_object_t *dep, elf_object_t *p)
 	    p->load_name));
 }
 
+void
+object_vec_grow(struct object_vector *vec, int more)
+{
+	vec->alloc += more;
+	vec->vec = _dl_reallocarray(vec->vec, vec->alloc, sizeof(*vec->vec));
+	if (vec->vec == NULL)
+		_dl_oom();
+}
+
 /* Generation number of the current grpsym insertion/caching */
 static unsigned int _dl_grpsym_gen = 0;
 
 void
-_dl_link_grpsym(elf_object_t *object, int checklist)
+_dl_link_grpsym(elf_object_t *object)
 {
-	struct dep_node *n;
+	struct object_vector *vec;
+	int len;
 
-	if (checklist) {
-		TAILQ_FOREACH(n, &_dl_loading_object->grpsym_list, next_sib)
-			if (n->data == object)
-				return; /* found, dont bother adding */
-	} else {
-		if (object->grpsym_gen == _dl_grpsym_gen) {
-			return; /* found, dont bother adding */
-		}
-	}
+	if (object->grpsym_gen == _dl_grpsym_gen)
+		return;
 	object->grpsym_gen = _dl_grpsym_gen;
 
-	n = _dl_malloc(sizeof *n);
-	if (n == NULL)
-		_dl_oom();
-	n->data = object;
-	TAILQ_INSERT_TAIL(&_dl_loading_object->grpsym_list, n, next_sib);
+	vec = &_dl_loading_object->grpsym_vec;
+	len = vec->len++;
+	if (len >= vec->alloc)
+		_dl_die("more grpsym than objects?!  %d > %d", vec->len,
+		    vec->alloc);
+	vec->vec[len] = object;
 }
 
 void
 _dl_cache_grpsym_list_setup(elf_object_t *object)
 {
+	struct object_vector *vec;
+	int next;
+
 	_dl_grpsym_gen += 1;
 
 	if (_dl_grpsym_gen == 0) {
@@ -567,22 +574,25 @@ _dl_cache_grpsym_list_setup(elf_object_t *object)
 		}
 		_dl_grpsym_gen = 1;
 	}
-	_dl_cache_grpsym_list(object);
-}
-void
-_dl_cache_grpsym_list(elf_object_t *object)
-{
-	struct dep_node *n;
 
 	/*
-	 * grpsym_list is an ordered list of all child libs of the
+	 * grpsym_vec is a vector of all child libs of the
 	 * _dl_loading_object with no dups. The order is equivalent
 	 * to a breadth-first traversal of the child list without dups.
 	 */
 
-	TAILQ_FOREACH(n, &object->child_list, next_sib)
-		_dl_link_grpsym(n->data, 0);
+	vec = &object->grpsym_vec;
+	object_vec_grow(vec, object_count);
+	next = 0;
+
+	/* add first object manually */
+	_dl_link_grpsym(object);
+
+	while (next < vec->len) {
+		struct dep_node *n;
 
-	TAILQ_FOREACH(n, &object->child_list, next_sib)
-		_dl_cache_grpsym_list(n->data);
+		object = vec->vec[next++];
+		TAILQ_FOREACH(n, &object->child_list, next_sib)
+			_dl_link_grpsym(n->data);
+	}
 }
diff --git a/libexec/ld.so/loader.c b/libexec/ld.so/loader.c
index 66480ac92de..fdb01469d86 100644
--- a/libexec/ld.so/loader.c
+++ b/libexec/ld.so/loader.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: loader.c,v 1.185 2019/08/06 04:01:41 guenther Exp $ */
+/*	$OpenBSD: loader.c,v 1.186 2019/10/03 06:10:54 guenther Exp $ */
 
 /*
  * Copyright (c) 1998 Per Fogelstrom, Opsycon AB
@@ -397,8 +397,6 @@ _dl_load_dep_libs(elf_object_t *object, int flags, int booting)
 		dynobj = dynobj->next;
 	}
 
-	/* add first object manually */
-	_dl_link_grpsym(object, 1);
 	_dl_cache_grpsym_list_setup(object);
 
 	return(0);
@@ -585,7 +583,7 @@ _dl_boot(const char **argv, char **envp, const long dyn_loff, long *dl_data)
 	_dl_add_object(dyn_obj);
 
 	dyn_obj->refcount++;
-	_dl_link_grpsym(dyn_obj, 1);
+	_dl_link_grpsym(dyn_obj);
 
 	dyn_obj->status |= STAT_RELOC_DONE;
 	_dl_set_sod(dyn_obj->load_name, &dyn_obj->sod);
diff --git a/libexec/ld.so/resolve.c b/libexec/ld.so/resolve.c
index c4bd6097f5d..c5bf588ade7 100644
--- a/libexec/ld.so/resolve.c
+++ b/libexec/ld.so/resolve.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: resolve.c,v 1.92 2019/08/04 23:51:45 guenther Exp $ */
+/*	$OpenBSD: resolve.c,v 1.93 2019/10/03 06:10:54 guenther Exp $ */
 
 /*
  * Copyright (c) 1998 Per Fogelstrom, Opsycon AB
@@ -53,7 +53,8 @@ struct symlookup {
 };
 
 elf_object_t *_dl_objects;
-elf_object_t *_dl_last_object;
+int object_count;
+static elf_object_t *_dl_last_object;
 elf_object_t *_dl_loading_object;
 
 /*
@@ -87,10 +88,13 @@ _dl_add_object(elf_object_t *object)
 
 	if (_dl_objects == NULL) {			/* First object ? */
 		_dl_last_object = _dl_objects = object;
+		object_count = 2;			/* count ld.so early */
 	} else {
 		_dl_last_object->next = object;
 		object->prev = _dl_last_object;
 		_dl_last_object = object;
+		if (object->obj_type != OBJTYPE_LDR)	/* see above */
+			object_count++;
 	}
 }
 
@@ -434,7 +438,6 @@ _dl_finalize_object(const char *objname, Elf_Dyn *dynp, Elf_Phdr *phdrp,
 	object->dev = 0;
 	object->inode = 0;
 	object->grpsym_gen = 0;
-	TAILQ_INIT(&object->grpsym_list);
 	TAILQ_INIT(&object->grpref_list);
 
 	if (object->dyn.runpath)
@@ -492,7 +495,7 @@ _dl_cleanup_objects()
 		_dl_free((char *)head->sod.sod_name);
 		_dl_free_path(head->runpath);
 		_dl_free_path(head->rpath);
-		_dl_tailq_free(TAILQ_FIRST(&head->grpsym_list));
+		_dl_free(head->grpsym_vec.vec);
 		_dl_tailq_free(TAILQ_FIRST(&head->child_list));
 		_dl_tailq_free(TAILQ_FIRST(&head->grpref_list));
 		nobj = head->next;
@@ -510,6 +513,7 @@ _dl_remove_object(elf_object_t *object)
 
 	if (_dl_last_object == object)
 		_dl_last_object = object->prev;
+	object_count--;
 
 	object->next = free_objects;
 	free_objects = object;
@@ -626,7 +630,6 @@ _dl_find_symbol(const char *name, int flags, const Elf_Sym *ref_sym,
 {
 	const unsigned char *p;
 	unsigned char c;
-	struct dep_node *n, *m;
 	struct symlookup sl = {
 		.sl_name = name,
 		.sl_out = { .sym = NULL },
@@ -651,6 +654,9 @@ _dl_find_symbol(const char *name, int flags, const Elf_Sym *ref_sym,
 			goto found;
 
 	if (flags & SYM_DLSYM) {
+		struct object_vector vec;
+		int i;
+
 		if (_dl_find_symbol_obj(req_obj, &sl))
 			goto found;
 
@@ -659,28 +665,34 @@ _dl_find_symbol(const char *name, int flags, const Elf_Sym *ref_sym,
 			goto found;
 
 		/* search dlopened obj and all children */
-		TAILQ_FOREACH(n, &req_obj->load_object->grpsym_list, next_sib) {
-			if (_dl_find_symbol_obj(n->data, &sl))
+		vec = req_obj->load_object->grpsym_vec;
+		for (i = 0; i < vec.len; i++) {
+			if (vec.vec[i] == req_obj)
+				continue;		/* already searched */
+			if (_dl_find_symbol_obj(vec.vec[i], &sl))
 				goto found;
 		}
 	} else {
-		int skip = 0;
+		struct dep_node *n;
+		struct object_vector vec;
+		int i, skip = 0;
 
 		if ((flags & SYM_SEARCH_SELF) || (flags & SYM_SEARCH_NEXT))
 			skip = 1;
 
 		/*
 		 * search dlopened objects: global or req_obj == dlopened_obj
-		 * and and it's children
+		 * and its children
 		 */
 		TAILQ_FOREACH(n, &_dlopened_child_list, next_sib) {
 			if (((n->data->obj_flags & DF_1_GLOBAL) == 0) &&
 			    (n->data != req_obj->load_object))
 				continue;
 
-			TAILQ_FOREACH(m, &n->data->grpsym_list, next_sib) {
+			vec = n->data->grpsym_vec;
+			for (i = 0; i < vec.len; i++) {
 				if (skip == 1) {
-					if (m->data == req_obj) {
+					if (vec.vec[i] == req_obj) {
 						skip = 0;
 						if (flags & SYM_SEARCH_NEXT)
 							continue;
@@ -688,9 +700,9 @@ _dl_find_symbol(const char *name, int flags, const Elf_Sym *ref_sym,
 						continue;
 				}
 				if ((flags & SYM_SEARCH_OTHER) &&
-				    (m->data == req_obj))
+				    (vec.vec[i] == req_obj))
 					continue;
-				if (_dl_find_symbol_obj(m->data, &sl))
+				if (_dl_find_symbol_obj(vec.vec[i], &sl))
 					goto found;
 			}
 		}
diff --git a/libexec/ld.so/resolve.h b/libexec/ld.so/resolve.h
index 7d9b2ab27c9..3be6f34c402 100644
--- a/libexec/ld.so/resolve.h
+++ b/libexec/ld.so/resolve.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: resolve.h,v 1.94 2019/08/04 23:51:45 guenther Exp $ */
+/*	$OpenBSD: resolve.h,v 1.95 2019/10/03 06:10:54 guenther Exp $ */
 
 /*
  * Copyright (c) 1998 Per Fogelstrom, Opsycon AB
@@ -68,12 +68,20 @@ typedef uint64_t Elf_Hash_Word;
 typedef uint32_t Elf_Hash_Word;
 #endif
 
+typedef struct elf_object elf_object_t;
+
+struct object_vector {
+	int		len;
+	int		alloc;
+	elf_object_t 	**vec;
+};
+void	object_vec_grow(struct object_vector *_vec, int _more);
+
 /*
  *  Structure describing a loaded object.
  *  The head of this struct must be compatible
  *  with struct link_map in sys/link.h
  */
-typedef struct elf_object elf_object_t;
 struct elf_object {
 	Elf_Addr obj_base;		/* object's address '0' base */
 	char	*load_name;		/* Pointer to object name */
@@ -182,7 +190,7 @@ struct elf_object {
 #define symndx_gnu	hash_u.u_gnu.symndx
 
 	TAILQ_HEAD(,dep_node)	child_list;	/* direct dep libs of object */
-	TAILQ_HEAD(,dep_node)	grpsym_list;	/* ordered complete dep list */
+	struct object_vector	grpsym_vec;	/* ordered complete dep list */
 	TAILQ_HEAD(,dep_node)	grpref_list;	/* refs to other load groups */
 
 	int		refcount;	/* dep libs only */
@@ -288,9 +296,8 @@ int _dl_load_dep_libs(elf_object_t *object, int flags, int booting);
 int _dl_rtld(elf_object_t *object);
 void _dl_call_init(elf_object_t *object);
 void _dl_link_child(elf_object_t *dep, elf_object_t *p);
-void _dl_link_grpsym(elf_object_t *object, int checklist);
-void _dl_cache_grpsym_list(elf_object_t *object);
-void _dl_cache_grpsym_list_setup(elf_object_t *object);
+void _dl_link_grpsym(elf_object_t *object);
+void _dl_cache_grpsym_list_setup(elf_object_t *_object);
 void _dl_link_grpref(elf_object_t *load_group, elf_object_t *load_object);
 void _dl_link_dlopen(elf_object_t *dep);
 void _dl_unlink_dlopen(elf_object_t *dep);
@@ -323,7 +330,7 @@ void	_dl_set_tls(elf_object_t *_object, Elf_Phdr *_ptls, Elf_Addr _libaddr,
 extern int _dl_tib_static_done;
 
 extern elf_object_t *_dl_objects;
-extern elf_object_t *_dl_last_object;
+extern int object_count;	/* how many objects are currently loaded */
 
 extern elf_object_t *_dl_loading_object;