Convert the child_list member from a linked list to a vector.

ok mpi@

7 files changed, 66 insertions, 43 deletions

diff --git a/libexec/ld.so/dlfcn.c b/libexec/ld.so/dlfcn.c
index 138530ba81e..b8d5512e32b 100644
--- a/libexec/ld.so/dlfcn.c
+++ b/libexec/ld.so/dlfcn.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: dlfcn.c,v 1.105 2019/10/03 06:10:53 guenther Exp $ */
+/*	$OpenBSD: dlfcn.c,v 1.106 2019/10/04 17:42:16 guenther Exp $ */
 
 /*
  * Copyright (c) 1998 Per Fogelstrom, Opsycon AB
@@ -237,8 +237,11 @@ dlctl(void *handle, int command, void *data)
 		break;
 	case 0x21:
 	{
+		struct object_vector vec;
 		struct dep_node *n, *m;
 		elf_object_t *obj;
+		int i;
+
 		_dl_printf("Load Groups:\n");
 
 		TAILQ_FOREACH(n, &_dlopened_child_list, next_sib) {
@@ -246,8 +249,8 @@ dlctl(void *handle, int command, void *data)
 			_dl_printf("%s\n", obj->load_name);
 
 			_dl_printf("  children\n");
-			TAILQ_FOREACH(m, &obj->child_list, next_sib)
-				_dl_printf("\t[%s]\n", m->data->load_name);
+			for (vec = obj->child_vec, i = 0; i < vec.len; i++)
+				_dl_printf("\t[%s]\n", vec.vec[i]->load_name);
 
 			_dl_printf("  grpref\n");
 			TAILQ_FOREACH(m, &obj->grpref_list, next_sib)
diff --git a/libexec/ld.so/library.c b/libexec/ld.so/library.c
index c8f2b572c93..e9def013abc 100644
--- a/libexec/ld.so/library.c
+++ b/libexec/ld.so/library.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: library.c,v 1.82 2017/12/08 05:25:20 deraadt Exp $ */
+/*	$OpenBSD: library.c,v 1.83 2019/10/04 17:42:16 guenther Exp $ */
 
 /*
  * Copyright (c) 2002 Dale Rahn
@@ -64,7 +64,7 @@ _dl_unload_shlib(elf_object_t *object)
 	 * If our load object has become unreferenced then we lost the
 	 * last group reference to it, so the entire group should be taken
 	 * down.  The current object is somewhere below load_object in
-	 * the child_list tree, so it'll get cleaned up by the recursion.
+	 * the child_vec tree, so it'll get cleaned up by the recursion.
 	 * That means we can just switch here to the load object.
 	 */
 	if (load_object != object && OBJECT_REF_CNT(load_object) == 0 &&
@@ -78,10 +78,12 @@ _dl_unload_shlib(elf_object_t *object)
 	DL_DEB(("unload_shlib called on %s\n", object->load_name));
 	if (OBJECT_REF_CNT(object) == 0 &&
 	    (object->status & STAT_UNLOADED) == 0) {
+		struct object_vector vec;
+		int i;
 unload:
 		object->status |= STAT_UNLOADED;
-		TAILQ_FOREACH(n, &object->child_list, next_sib)
-			_dl_unload_shlib(n->data);
+		for (vec = object->child_vec, i = 0; i < vec.len; i++)
+			_dl_unload_shlib(vec.vec[i]);
 		TAILQ_FOREACH(n, &object->grpref_list, next_sib)
 			_dl_unload_shlib(n->data);
 		DL_DEB(("unload_shlib unloading on %s\n", object->load_name));
diff --git a/libexec/ld.so/library_mquery.c b/libexec/ld.so/library_mquery.c
index 2eca7e76246..6f061410f51 100644
--- a/libexec/ld.so/library_mquery.c
+++ b/libexec/ld.so/library_mquery.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: library_mquery.c,v 1.59 2019/01/25 18:13:13 kurt Exp $ */
+/*	$OpenBSD: library_mquery.c,v 1.60 2019/10/04 17:42:16 guenther Exp $ */
 
 /*
  * Copyright (c) 2002 Dale Rahn
@@ -69,7 +69,7 @@ _dl_unload_shlib(elf_object_t *object)
 	 * If our load object has become unreferenced then we lost the
 	 * last group reference to it, so the entire group should be taken
 	 * down.  The current object is somewhere below load_object in
-	 * the child_list tree, so it'll get cleaned up by the recursion.
+	 * the child_vec tree, so it'll get cleaned up by the recursion.
 	 * That means we can just switch here to the load object.
 	 */
 	if (load_object != object && OBJECT_REF_CNT(load_object) == 0 &&
@@ -83,10 +83,12 @@ _dl_unload_shlib(elf_object_t *object)
 	DL_DEB(("unload_shlib called on %s\n", object->load_name));
 	if (OBJECT_REF_CNT(object) == 0 &&
 	    (object->status & STAT_UNLOADED) == 0) {
+		struct object_vector vec;
+		int i;
 unload:
 		object->status |= STAT_UNLOADED;
-		TAILQ_FOREACH(n, &object->child_list, next_sib)
-			_dl_unload_shlib(n->data);
+		for (vec = object->child_vec, i = 0; i < vec.len; i++)
+			_dl_unload_shlib(vec.vec[i]);
 		TAILQ_FOREACH(n, &object->grpref_list, next_sib)
 			_dl_unload_shlib(n->data);
 		DL_DEB(("unload_shlib unloading on %s\n", object->load_name));
diff --git a/libexec/ld.so/library_subr.c b/libexec/ld.so/library_subr.c
index 32b96ca10ce..4ffcf44ec1c 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.49 2019/10/03 06:10:54 guenther Exp $ */
+/*	$OpenBSD: library_subr.c,v 1.50 2019/10/04 17:42:16 guenther Exp $ */
 
 /*
  * Copyright (c) 2002 Dale Rahn
@@ -448,22 +448,25 @@ _dl_link_dlopen(elf_object_t *dep)
 static void
 _dl_child_refcnt_decrement(elf_object_t *object)
 {
-	struct dep_node *n;
+	struct object_vector vec;
+	int i;
 
 	object->refcount--;
 	if (OBJECT_REF_CNT(object) == 0)
-		TAILQ_FOREACH(n, &object->child_list, next_sib)
-			_dl_child_refcnt_decrement(n->data);
+		for (vec = object->child_vec, i = 0; i < vec.len; i++)
+			_dl_child_refcnt_decrement(vec.vec[i]);
 }
 
 void
 _dl_notify_unload_shlib(elf_object_t *object)
 {
+	struct object_vector vec;
 	struct dep_node *n;
+	int i;
 
 	if (OBJECT_REF_CNT(object) == 0)
-		TAILQ_FOREACH(n, &object->child_list, next_sib)
-			_dl_child_refcnt_decrement(n->data);
+		for (vec = object->child_vec, i = 0; i < vec.len; i++)
+			_dl_child_refcnt_decrement(vec.vec[i]);
 
 	if (OBJECT_DLREF_CNT(object) == 0) {
 		while ((n = TAILQ_FIRST(&object->grpref_list)) != NULL) {
@@ -509,13 +512,13 @@ _dl_link_grpref(elf_object_t *load_group, elf_object_t *load_object)
 void
 _dl_link_child(elf_object_t *dep, elf_object_t *p)
 {
-	struct dep_node *n;
+	int i;
 
-	n = _dl_malloc(sizeof *n);
-	if (n == NULL)
-		_dl_oom();
-	n->data = dep;
-	TAILQ_INSERT_TAIL(&p->child_list, n, next_sib);
+	i = p->child_vec.len++;
+	if (i == p->child_vec.alloc)
+		_dl_die("child appeared  %d > %d", p->child_vec.len,
+		    p->child_vec.alloc);
+	p->child_vec.vec[i] = dep;
 
 	dep->refcount++;
 
@@ -589,10 +592,11 @@ _dl_cache_grpsym_list_setup(elf_object_t *object)
 	_dl_link_grpsym(object);
 
 	while (next < vec->len) {
-		struct dep_node *n;
+		struct object_vector child_vec;
+		int i;
 
-		object = vec->vec[next++];
-		TAILQ_FOREACH(n, &object->child_list, next_sib)
-			_dl_link_grpsym(n->data);
+		child_vec = vec->vec[next++]->child_vec;
+		for (i = 0; i < child_vec.len; i++)
+			_dl_link_grpsym(child_vec.vec[i]);
 	}
 }
diff --git a/libexec/ld.so/loader.c b/libexec/ld.so/loader.c
index fdb01469d86..3ffe9307c3f 100644
--- a/libexec/ld.so/loader.c
+++ b/libexec/ld.so/loader.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: loader.c,v 1.186 2019/10/03 06:10:54 guenther Exp $ */
+/*	$OpenBSD: loader.c,v 1.187 2019/10/04 17:42:16 guenther Exp $ */
 
 /*
  * Copyright (c) 1998 Per Fogelstrom, Opsycon AB
@@ -127,7 +127,6 @@ void
 _dl_run_all_dtors(void)
 {
 	elf_object_t *node;
-	struct dep_node *dnode;
 	int fini_complete;
 	int skip_initfirst;
 	int initfirst_skipped;
@@ -160,10 +159,13 @@ _dl_run_all_dtors(void)
 			    (node->status & STAT_INIT_DONE) &&
 			    ((node->status & STAT_FINI_DONE) == 0) &&
 			    (!skip_initfirst ||
-			    (node->obj_flags & DF_1_INITFIRST) == 0))
-				TAILQ_FOREACH(dnode, &node->child_list,
-				    next_sib)
-					dnode->data->status &= ~STAT_FINI_READY;
+			    (node->obj_flags & DF_1_INITFIRST) == 0)) {
+				struct object_vector vec = node->child_vec;
+				int i;
+
+				for (i = 0; i < vec.len; i++)
+					vec.vec[i]->status &= ~STAT_FINI_READY;
+			}
 		}
 
 
@@ -227,11 +229,20 @@ _dl_dopreload(char *paths)
 {
 	char		*cp, *dp;
 	elf_object_t	*shlib;
+	int		count;
 
 	dp = paths = _dl_strdup(paths);
 	if (dp == NULL)
 		_dl_oom();
 
+	/* preallocate child_vec for the LD_PRELOAD objects */
+	count = 1;
+	while (*dp++ != '\0')
+		if (*dp == ':')
+			count++;
+	object_vec_grow(&_dl_objects->child_vec, count);
+
+	dp = paths;
 	while ((cp = _dl_strsep(&dp, ":")) != NULL) {
 		shlib = _dl_load_shlib(cp, _dl_objects, OBJTYPE_LIB,
 		    _dl_objects->obj_flags);
@@ -387,6 +398,7 @@ _dl_load_dep_libs(elf_object_t *object, int flags, int booting)
 				liblist[randomlist[loop]].depobj = depobj;
 			}
 
+			object_vec_grow(&dynobj->child_vec, libcount);
 			for (loop = 0; loop < libcount; loop++) {
 				_dl_add_object(liblist[loop].depobj);
 				_dl_link_child(liblist[loop].depobj, dynobj);
@@ -573,7 +585,7 @@ _dl_boot(const char **argv, char **envp, const long dyn_loff, long *dl_data)
 	/*
 	 * Now add the dynamic loader itself last in the object list
 	 * so we can use the _dl_ code when serving dl.... calls.
-	 * Intentionally left off the exe child_list.
+	 * Intentionally left off the exe child_vec.
 	 */
 	dynp = (Elf_Dyn *)((void *)_DYNAMIC);
 	ehdr = (Elf_Ehdr *)dl_data[AUX_base];
@@ -765,15 +777,16 @@ _dl_relro(elf_object_t *object)
 void
 _dl_call_init_recurse(elf_object_t *object, int initfirst)
 {
-	struct dep_node *n;
+	struct object_vector vec;
 	int visited_flag = initfirst ? STAT_VISIT_INITFIRST : STAT_VISIT_INIT;
+	int i;
 
 	object->status |= visited_flag;
 
-	TAILQ_FOREACH(n, &object->child_list, next_sib) {
-		if (n->data->status & visited_flag)
+	for (vec = object->child_vec, i = 0; i < vec.len; i++) {
+		if (vec.vec[i]->status & visited_flag)
 			continue;
-		_dl_call_init_recurse(n->data, initfirst);
+		_dl_call_init_recurse(vec.vec[i], initfirst);
 	}
 
 	if (object->status & STAT_INIT_DONE)
diff --git a/libexec/ld.so/resolve.c b/libexec/ld.so/resolve.c
index c5bf588ade7..1d882d2109a 100644
--- a/libexec/ld.so/resolve.c
+++ b/libexec/ld.so/resolve.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: resolve.c,v 1.93 2019/10/03 06:10:54 guenther Exp $ */
+/*	$OpenBSD: resolve.c,v 1.94 2019/10/04 17:42:16 guenther Exp $ */
 
 /*
  * Copyright (c) 1998 Per Fogelstrom, Opsycon AB
@@ -431,7 +431,6 @@ _dl_finalize_object(const char *objname, Elf_Dyn *dynp, Elf_Phdr *phdrp,
 	DL_DEB(("obj %s has %s as head\n", object->load_name,
 	    _dl_loading_object->load_name ));
 	object->refcount = 0;
-	TAILQ_INIT(&object->child_list);
 	object->opencount = 0;	/* # dlopen() & exe */
 	object->grprefcount = 0;
 	/* default dev, inode for dlopen-able objects. */
@@ -496,7 +495,7 @@ _dl_cleanup_objects()
 		_dl_free_path(head->runpath);
 		_dl_free_path(head->rpath);
 		_dl_free(head->grpsym_vec.vec);
-		_dl_tailq_free(TAILQ_FIRST(&head->child_list));
+		_dl_free(head->child_vec.vec);
 		_dl_tailq_free(TAILQ_FIRST(&head->grpref_list));
 		nobj = head->next;
 		_dl_free(head);
diff --git a/libexec/ld.so/resolve.h b/libexec/ld.so/resolve.h
index 3be6f34c402..1bad5d6913a 100644
--- a/libexec/ld.so/resolve.h
+++ b/libexec/ld.so/resolve.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: resolve.h,v 1.95 2019/10/03 06:10:54 guenther Exp $ */
+/*	$OpenBSD: resolve.h,v 1.96 2019/10/04 17:42:16 guenther Exp $ */
 
 /*
  * Copyright (c) 1998 Per Fogelstrom, Opsycon AB
@@ -189,7 +189,7 @@ struct elf_object {
 #define shift2_gnu	hash_u.u_gnu.shift2
 #define symndx_gnu	hash_u.u_gnu.symndx
 
-	TAILQ_HEAD(,dep_node)	child_list;	/* direct dep libs of object */
+	struct object_vector	child_vec;	/* direct dep libs of object */
 	struct object_vector	grpsym_vec;	/* ordered complete dep list */
 	TAILQ_HEAD(,dep_node)	grpref_list;	/* refs to other load groups */