There are several optimizations here:

1) Objects on _rtld_list_main do not participate in the DAG structures
   at all.  This is okay because all symbols must be resolvable at
   link/load time, and _rtld_list_main is always searched first, so
   any references from those objects must necessarily be resolved to
   other objects on _rtld_list_main.

   (Making this work completely required setting obj->main a bit
   earlier; hence the RTLD_MAIN hack.)

2) Objects on _rtld_list_main are not put on _rtld_list_global,
   preventing an extra search.

3) A counter is used to keep track of whether an object is on
   _rtld_list_global, so we don't have to do a silly linear search.

4) A small attempt is made to prevent objects being put on the DAG
   lists multiple times (using a silly linear search).

The sum of this appears to be a ~10% (.3s) reduction in Mozilla's
startup time on my 800MHz box.

I've tested a few things that use modules, like xmms, and they appear
to still work correctly.


Index: load.c
===================================================================
RCS file: /cvsroot/basesrc/libexec/ld.elf_so/load.c,v retrieving
revision 1.19 diff -u -r1.19 load.c --- load.c 2002/09/23 23:56:46
1.19 +++ load.c 2002/10/03 18:07:07 @@ -153,8 +153,9 @@
free(filepath);
 
 	++obj->refcount;
-	if ((mode & RTLD_GLOBAL) &&
-	    _rtld_objlist_find(&_rtld_list_global, obj) == NULL)
+	if (mode & RTLD_MAIN)
+		obj->main = 1;
+	if (mode & RTLD_GLOBAL && !obj->globalref++)
 		_rtld_objlist_add(&_rtld_list_global, obj);
 	return obj;
 }
Index: rtld.c
===================================================================
RCS file: /cvsroot/basesrc/libexec/ld.elf_so/rtld.c,v
retrieving revision 1.83
diff -u -r1.83 rtld.c
--- rtld.c	2002/10/03 01:09:21	1.83
+++ rtld.c	2002/10/03 18:07:07
@@ -402,13 +402,11 @@
 		_rtld_die();
 
 	dbg(("loading needed objects"));
-	if (_rtld_load_needed_objects(_rtld_objmain, RTLD_GLOBAL) == -1)
+	if (_rtld_load_needed_objects(_rtld_objmain, RTLD_MAIN) == -1)
 		_rtld_die();
 
-	for (obj = _rtld_objlist; obj != NULL; obj = obj->next) {
-		obj->main = 1;
+	for (obj = _rtld_objlist; obj != NULL; obj = obj->next)
 		_rtld_objlist_add(&_rtld_list_main, obj);
-	}
 
 	dbg(("relocating objects"));
 	if (_rtld_relocate_objects(_rtld_objmain, bind_now) == -1)
@@ -499,9 +497,14 @@
 {
 	const Needed_Entry *needed;
 
-	_rtld_objlist_add(&obj->dldags, root);
-	if (!obj->main)
+	if (!obj->main) {
+		if (_rtld_objlist_find(&obj->dldags, root))
+			return;
+		rdbg(("add %p (%s) to %p (%s) DAG", obj, obj->path, root,
+		    root->path));
+		_rtld_objlist_add(&obj->dldags, root);
 		_rtld_objlist_add(&root->dagmembers, obj);
+	}
 	for (needed = obj->needed; needed != NULL; needed = needed->next)
 		if (needed->obj != NULL)
 			_rtld_init_dag1(root, needed->obj);
@@ -532,7 +535,10 @@
 			_rtld_objlist_remove(&elm->obj->dldags, root);
 
 		/* Remove the DAG from the RTLD_GLOBAL list. */
-		_rtld_objlist_remove(&_rtld_list_global, root);
+		if (root->globalref) {
+			root->globalref = 0;
+			_rtld_objlist_remove(&_rtld_list_global, root);
+		}
 
 		/* Unmap all objects that are no longer referenced. */
 		linkp = &_rtld_objlist->next;
Index: rtld.h
===================================================================
RCS file: /cvsroot/basesrc/libexec/ld.elf_so/rtld.h,v
retrieving revision 1.61
diff -u -r1.61 rtld.h
--- rtld.h	2002/10/03 01:09:21	1.61
+++ rtld.h	2002/10/03 18:07:07
@@ -115,6 +115,7 @@
 
 #define RTLD_MAGIC	0xd550b87a
 #define RTLD_VERSION	1
+#define	RTLD_MAIN	0x800
 
 typedef struct Struct_Obj_Entry {
 	Elf32_Word      magic;		/* Magic number (sanity check) */
@@ -191,6 +192,7 @@
 	const char     *interp;	/* Pathname of the interpreter, if any */
 	Objlist         dldags;	/* Object belongs to these dlopened DAGs (%) */
 	Objlist         dagmembers;	/* DAG has these members (%) */
+	int		globalref;
 	dev_t           dev;		/* Object's filesystem's device */
 	ino_t           ino;		/* Object's inode number */
 } Obj_Entry;
@@ -258,7 +260,7 @@
 const Elf_Sym *_rtld_find_symdef __P((unsigned long, const Obj_Entry *,
     const Obj_Entry **, bool));
 const Elf_Sym *_rtld_symlook_list(const char *, unsigned long,
-  Objlist *, const Obj_Entry **, bool);
+    const Objlist *, const Obj_Entry **, bool);
 
 /* map_object.c */
 Obj_Entry *_rtld_map_object __P((char *, int, const struct stat *));
Index: symbol.c
===================================================================
RCS file: /cvsroot/basesrc/libexec/ld.elf_so/symbol.c,v
retrieving revision 1.22
diff -u -r1.22 symbol.c
--- symbol.c	2002/09/24 20:27:07	1.22
+++ symbol.c	2002/10/03 18:07:07
@@ -74,7 +74,7 @@
 }
 
 const Elf_Sym *
-_rtld_symlook_list(const char *name, unsigned long hash, Objlist *objlist,
+_rtld_symlook_list(const char *name, unsigned long hash, const Objlist *objlist,
   const Obj_Entry **defobj_out, bool in_plt)
 {
 	const Elf_Sym *symp;
@@ -85,6 +85,7 @@
 	def = NULL;
 	defobj = NULL;
 	SIMPLEQ_FOREACH(elm, objlist, link) {
+		rdbg(("search object %p (%s)", elm->obj, elm->obj->path));
 		if ((symp = _rtld_symlook_obj(name, hash, elm->obj, in_plt))
 		    != NULL) {
 			if ((def == NULL) ||
@@ -127,6 +128,7 @@
 		assert(symnum < obj->nchains);
 		symp = obj->symtab + symnum;
 		strp = obj->strtab + symp->st_name;
+		rdbg(("check %s vs %s in %p", name, strp, obj));
 		if (name[1] == strp[1] && !strcmp(name, strp)) {
 			if (symp->st_shndx != SHN_UNDEF)
 				return symp;
@@ -192,6 +194,7 @@
 	
 	/* Search all objects loaded at program start up. */
 	if (def == NULL || ELF_ST_BIND(def->st_info) == STB_WEAK) {
+		rdbg(("search _rtld_list_main"));
 		symp = _rtld_symlook_list(name, hash, &_rtld_list_main, &obj, in_plt);
 		if (symp != NULL &&
 		    (def == NULL || ELF_ST_BIND(symp->st_info) != STB_WEAK)) {
@@ -204,6 +207,7 @@
 	SIMPLEQ_FOREACH(elm, &refobj->dldags, link) {
 		if (def != NULL && ELF_ST_BIND(def->st_info) != STB_WEAK)
 			break;
+		rdbg(("search DAG with root %p (%s)", elm->obj, elm->obj->path));
 		symp = _rtld_symlook_list(name, hash, &elm->obj->dagmembers, &obj, in_plt);
 		if (symp != NULL &&
 		    (def == NULL || ELF_ST_BIND(symp->st_info) != STB_WEAK)) {
@@ -214,6 +218,7 @@
 	
 	/* Search all RTLD_GLOBAL objects. */
 	if (def == NULL || ELF_ST_BIND(def->st_info) == STB_WEAK) {
+		rdbg(("search _rtld_list_global"));
 		symp = _rtld_symlook_list(name, hash, &_rtld_list_global, &obj, in_plt);
 		if (symp != NULL &&
 		    (def == NULL || ELF_ST_BIND(symp->st_info) != STB_WEAK)) {
@@ -234,8 +239,10 @@
 	
 	if (def != NULL)
 		*defobj_out = defobj;
-	else
+	else {
+		rdbg(("lookup failed"));
 		_rtld_error("%s: Undefined %ssymbol \"%s\" (symnum = %ld)",
 		    refobj->path, in_plt ? "PLT " : "", name, symnum);
+	}
 	return def;
 }