Dynamic linker speed improvement diff. tested by several sinc k2k11.

get it in tree now deraadt@, ok by several ports folks. Thanks for the testing.

4 files changed, 141 insertions, 12 deletions

diff --git a/libexec/ld.so/dlfcn.c b/libexec/ld.so/dlfcn.c
index f975f61603e..74b2a587e4d 100644
--- a/libexec/ld.so/dlfcn.c
+++ b/libexec/ld.so/dlfcn.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: dlfcn.c,v 1.82 2010/07/01 19:25:44 drahn Exp $ */
+/*	$OpenBSD: dlfcn.c,v 1.83 2011/05/22 22:43:47 drahn Exp $ */
 
 /*
  * Copyright (c) 1998 Per Fogelstrom, Opsycon AB
@@ -108,6 +108,7 @@ dlopen(const char *libname, int flags)
 			_dl_unload_shlib(object);
 			_dl_exit(0);
 		}
+		_dl_search_list_valid = 0;
 		err = _dl_rtld(object);
 		if (err != 0) {
 			_dl_real_close(object);
@@ -263,6 +264,7 @@ dlclose(void *handle)
 
 	retval = _dl_real_close(handle);
 
+	_dl_search_list_valid = 0;
 
 	if (_dl_debug_map->r_brk) {
 		_dl_debug_map->r_state = RT_CONSISTENT;
diff --git a/libexec/ld.so/loader.c b/libexec/ld.so/loader.c
index bf778f433e6..bc71ee57531 100644
--- a/libexec/ld.so/loader.c
+++ b/libexec/ld.so/loader.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: loader.c,v 1.123 2011/05/09 18:13:34 otto Exp $ */
+/*	$OpenBSD: loader.c,v 1.124 2011/05/22 22:43:47 drahn Exp $ */
 
 /*
  * Copyright (c) 1998 Per Fogelstrom, Opsycon AB
@@ -423,6 +423,7 @@ _dl_boot(const char **argv, char **envp, const long dyn_loff, long *dl_data)
 
 	/* init this in runtime, not statically */
 	TAILQ_INIT(&_dlopened_child_list);
+	TAILQ_INIT(&_dlsym_search_list);
 
 	exe_obj = NULL;
 	_dl_loading_object = NULL;
@@ -510,6 +511,7 @@ _dl_boot(const char **argv, char **envp, const long dyn_loff, long *dl_data)
 	dyn_obj->status |= STAT_RELOC_DONE;
 	_dl_set_sod(dyn_obj->load_name, &dyn_obj->sod);
 
+	_dl_search_list_valid = 0;
 	/*
 	 * Everything should be in place now for doing the relocation
 	 * and binding. Call _dl_rtld to do the job. Fingers crossed.
diff --git a/libexec/ld.so/resolve.c b/libexec/ld.so/resolve.c
index 25eed5cf09b..d823a562765 100644
--- a/libexec/ld.so/resolve.c
+++ b/libexec/ld.so/resolve.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: resolve.c,v 1.53 2011/05/10 04:50:35 otto Exp $ */
+/*	$OpenBSD: resolve.c,v 1.54 2011/05/22 22:43:47 drahn Exp $ */
 
 /*
  * Copyright (c) 1998 Per Fogelstrom, Opsycon AB
@@ -213,6 +213,90 @@ _dl_cleanup_objects()
 	}
 }
 
+struct dep_node_head _dlsym_search_list;
+int _dl_search_list_valid = 0;
+
+void
+_dl_rebuild_allobj_grouplist()
+{
+	struct dep_node *n, *m;
+	int global;
+	static int maxgrouplist = 0;
+	static int maxchildlist = 0;
+	int childlistlen = 0, grouplistlen = 0;
+
+	DL_DEB(("rebuil\n"));
+
+	/* get rid of old list */
+	while( (n = TAILQ_FIRST(&_dlsym_search_list)) != NULL) {
+		TAILQ_REMOVE(&_dlsym_search_list, n, next_sib);
+		n->data->obj_global = 0; /* clear the cached global flag */
+		_dl_free(n);
+	}
+
+	/* rebuild list */
+	_dl_newsymsearch();
+	/*
+	 * search dlopened objects: global or req_obj == dlopened_obj
+	 * and and it's children
+	 */
+	
+	 _dl_newsymsearch();
+
+	TAILQ_FOREACH(n, &_dlopened_child_list, next_sib) {
+		childlistlen++;
+#if 0
+		DL_DEB(("opened list: %s\n", n->data->load_name)); 
+#endif
+		global = n->data->obj_flags & RTLD_GLOBAL;
+
+		if (n->data->lastlookup == _dl_searchnum)
+			continue;
+
+		grouplistlen = 0;
+		TAILQ_FOREACH(m, &n->data->grpsym_list, next_sib) {
+			grouplistlen++;
+			if (m->data->lastlookup == _dl_searchnum)
+				continue;
+			if (!global && m->data != n->data) {
+				continue;
+			}
+			m->data->obj_global |= global & RTLD_GLOBAL;
+
+			_dl_append_search(m->data);
+		}
+	}
+	if (grouplistlen > maxgrouplist) {
+		maxgrouplist = grouplistlen ;
+		DL_DEB(("maxgrouplist = %d\n", maxgrouplist));
+	}
+	if (childlistlen > maxchildlist) {
+		maxchildlist = childlistlen;
+		DL_DEB(("maxchildlist = %d\n", maxchildlist));
+	}
+
+#if 0
+	TAILQ_FOREACH(n, &_dlsym_search_list, next_sib) {
+		DL_DEB(("objects: %s global %d\n",
+		    n->data->load_name,
+		    n->data->obj_global));
+	}
+#endif
+
+	_dl_search_list_valid = 1;
+}
+
+void
+_dl_append_search(elf_object_t *object)
+{
+	struct dep_node *n;
+	n = _dl_malloc(sizeof *n);
+	n->data = object;
+
+	object->lastlookup = _dl_searchnum;
+	TAILQ_INSERT_TAIL(&_dlsym_search_list, n, next_sib);
+}
+
 void
 _dl_remove_object(elf_object_t *object)
 {
@@ -322,6 +406,8 @@ _dl_find_symbol(const char *name, const Elf_Sym **this,
 	const char *p = name;
 	elf_object_t *object = NULL, *weak_object = NULL;
 	int found = 0;
+	int visit = 0;
+	static int maxvisit = 0;
 	struct dep_node *n, *m;
 
 
@@ -372,14 +458,12 @@ _dl_find_symbol(const char *name, const Elf_Sym **this,
 				}
 			}
 		}
-	} else {
+	} else if ((flags & (SYM_SEARCH_NEXT|SYM_SEARCH_SELF|SYM_SEARCH_OTHER))) {
 		int skip = 0;
 
 		if ((flags & SYM_SEARCH_SELF) || (flags & SYM_SEARCH_NEXT))
 			skip = 1;
 
-		_dl_newsymsearch();
-
 		/*
 		 * search dlopened objects: global or req_obj == dlopened_obj
 		 * and and it's children
@@ -389,7 +473,6 @@ _dl_find_symbol(const char *name, const Elf_Sym **this,
 			    (n->data != req_obj->load_object))
 				continue;
 
-			n->data->lastlookup_head = _dl_searchnum;
 			TAILQ_FOREACH(m, &n->data->grpsym_list, next_sib) {
 				if (skip == 1) {
 					if (m->data == req_obj) {
@@ -402,7 +485,6 @@ _dl_find_symbol(const char *name, const Elf_Sym **this,
 				if ((flags & SYM_SEARCH_OTHER) &&
 				    (m->data == req_obj))
 					continue;
-				m->data->lastlookup = _dl_searchnum;
 				if (_dl_find_symbol_obj(m->data, name, h, flags,
 				    this, &weak_sym, &weak_object)) {
 					object = m->data;
@@ -411,9 +493,46 @@ _dl_find_symbol(const char *name, const Elf_Sym **this,
 				}
 			}
 		}
+	} else {
+		if (_dl_search_list_valid == 0) {
+			_dl_rebuild_allobj_grouplist();
+		}
+
+		TAILQ_FOREACH(n, &_dlsym_search_list, next_sib) {
+			if (n->data == req_obj->load_object) {
+				TAILQ_FOREACH(m, &n->data->grpsym_list,
+				    next_sib) {
+					visit++;
+					if (_dl_find_symbol_obj(m->data, name,
+					    h, flags, this, &weak_sym,
+					    &weak_object)) {
+						object = m->data;
+						found = 1;
+						goto found;
+					}
+				}
+			}
+			if (((n->data->obj_global & RTLD_GLOBAL) == 0) &&
+			    (n->data != req_obj->load_object))
+				continue;
+
+			//DL_DEB(("searching for %s in %s\n", name, n->data->load_name));
+			visit++;
+			if (_dl_find_symbol_obj(n->data, name, h, flags,
+			    this, &weak_sym, &weak_object)) {
+				object = n->data;
+				found = 1;
+				DL_DEB(("sym %s is in %s\n", name, object->load_name));
+				goto found;
+			}
+		}
 	}
 
 found:
+	if (visit > maxvisit) {
+		maxvisit = visit;
+		DL_DEB(("maxvisit is %d\n", maxvisit));
+	}
 	if (weak_object != NULL && found == 0) {
 		object=weak_object;
 		*this = weak_sym;
diff --git a/libexec/ld.so/resolve.h b/libexec/ld.so/resolve.h
index 977fa444619..6eecc649e62 100644
--- a/libexec/ld.so/resolve.h
+++ b/libexec/ld.so/resolve.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: resolve.h,v 1.62 2010/10/25 20:34:44 kurt Exp $ */
+/*	$OpenBSD: resolve.h,v 1.63 2011/05/22 22:43:47 drahn Exp $ */
 
 /*
  * Copyright (c) 1998 Per Fogelstrom, Opsycon AB
@@ -43,6 +43,9 @@ struct load_list {
 	long		foff;
 };
 
+TAILQ_HEAD(dep_node_head, dep_node);
+extern struct dep_node_head _dlsym_search_list;
+
 /*
  *  Structure describing a loaded object.
  *  The head of this struct must be compatible
@@ -115,6 +118,7 @@ struct elf_object {
 #define	OBJTYPE_LIB	3
 #define	OBJTYPE_DLO	4
 	int		obj_flags;
+	int		obj_global;
 
 	Elf_Word	*buckets;
 	u_int32_t	nbuckets;
@@ -122,9 +126,9 @@ struct elf_object {
 	u_int32_t	nchains;
 	Elf_Dyn		*dynamic;
 
-	TAILQ_HEAD(,dep_node)	child_list;	/* direct dep libs of object */
-	TAILQ_HEAD(,dep_node)	grpsym_list;	/* ordered complete dep list */
-	TAILQ_HEAD(,dep_node)	grpref_list;	/* refs to other load groups */
+	struct dep_node_head	child_list;	/* direct dep libs of object */
+	struct dep_node_head	grpsym_list;	/* ordered complete dep list */
+	struct dep_node_head	grpref_list;	/* refs to other load groups */
 
 	int		refcount;	/* dep libs only */
 	int		opencount;	/* # dlopen() & exe */
@@ -233,6 +237,7 @@ extern elf_object_t *_dl_objects;
 extern elf_object_t *_dl_last_object;
 
 extern elf_object_t *_dl_loading_object;
+void _dl_append_search(elf_object_t *object);
 
 extern const char *_dl_progname;
 extern struct r_debug *_dl_debug_map;
@@ -278,6 +283,7 @@ extern int _dl_symcachestat_hits;
 extern int _dl_symcachestat_lookups;
 TAILQ_HEAD(dlochld, dep_node);
 extern struct dlochld _dlopened_child_list;
+extern int _dl_search_list_valid;
 
 /* variables used to avoid duplicate node checking */
 int _dl_searchnum;