Tue Jun 4 18:57:57 1996 Roland McGrath <roland@delasyd.gnu.ai.mit.edu>

	* elf/dladdr.c: Remove #include <setjmp.h>, we don't use it.

	* shlib-versions: Set libdl=2.

	* elf/dl-deps.c (_dl_map_object_deps): Use a linked list of alloca'd
 	elements and then scan it to fill the single malloc'd array, instead
 	of using realloc to grow the array in the first pass.  _dl_map_object
	may do some mallocs that break our stream of reallocs, and the minimal
	realloc can't handle that.

	* elf/dl-init.c (_dl_init_next): Take argument, link_map whose
 	searchlist describes the piece of the DT_NEEDED graph to be
 	initialized.
	* elf/link.h: Update prototype.
	* sysdeps/i386/dl-machine.h (RTLD_START): Pass _dl_loaded as argument
	to _dl_init_next.
	* sysdeps/m68k/dl-machine.h: Likewise.
	* elf/dl-deps.c (_dl_open): Pass new object as arg to _dl_init_next.

	* elf/link.h (struct link_map): Add `l_reserved' member, soaking up
	extra bits in last byte.
	* elf/dl-deps.c (_dl_map_object_deps): Use that for mark bit to avoid
	putting dup elts in search list.

	* elf/dlclose.c: Use MAP->l_searchlist to find deps to close.

	* elf/dlsym.c: Don't tweak linked list.  Scope array given to
	_dl_lookup_symbol does the right thing.
Tue Jun  4 02:25:44 1996  Roland McGrath  <roland@delasyd.gnu.ai.mit.edu>

6 files changed, 126 insertions, 119 deletions

diff --git a/elf/dl-deps.c b/elf/dl-deps.c
index f87475a670..92403d4110 100644
--- a/elf/dl-deps.c
+++ b/elf/dl-deps.c
@@ -25,20 +25,33 @@ Cambridge, MA 02139, USA.  */
 void
 _dl_map_object_deps (struct link_map *map)
 {
-  unsigned int nlist = 1;
-  struct link_map **list = malloc (sizeof *list);
-  unsigned int done;
+  struct list
+    {
+      struct link_map *map;
+      struct list *next;
+    };
+  struct list head, *tailp, *scanp;
+  unsigned int nlist;
 
   /* Start the search list with one element: MAP itself.  */
-  list[0] = map;
+  head.map = map;
+  head.next = NULL;
+  nlist = 1;
+
 
   /* Process each element of the search list, loading each of its immediate
      dependencies and appending them to the list as we step through it.
      This produces a flat, ordered list that represents a breadth-first
      search of the dependency tree.  */
-  for (done = 0; done < nlist; ++done)
+  for (scanp = tailp = &head; scanp; scanp = scanp->next)
     {
-      struct link_map *l = list[done];
+      struct link_map *l = scanp->map;
+
+      /* We use `l_reserved' as a mark bit to detect objects we have
+         already put in the search list and avoid adding duplicate elements
+         later in the list.  */
+      l->l_reserved = 1;
+
       if (l->l_info[DT_NEEDED])
 	{
 	  const char *strtab
@@ -47,24 +60,42 @@ _dl_map_object_deps (struct link_map *map)
 	  for (d = l->l_ld; d->d_tag != DT_NULL; ++d)
 	    if (d->d_tag == DT_NEEDED)
 	      {
-		/* Extend the list and put this object on the end.  */
-		struct link_map **n
-		  = realloc (list, (nlist + 1) * sizeof *list);
-		if (n)
-		  list = n;
+		/* Map in the needed object.  */
+		struct link_map *dep
+		  = _dl_map_object (l, strtab + d->d_un.d_val);
+
+		if (dep->l_reserved)
+		  /* This object is already in the search list we are
+                     building.  Don't add a duplicate pointer.  Release the
+                     reference just added by _dl_map_object.  */
+		  --dep->l_opencount;
 		else
 		  {
-		    free (list);
-		    _dl_signal_error (ENOMEM, map->l_name,
-				      "finding dependencies");
+		    /* Append DEP to the search list.  */
+		    tailp->next = alloca (sizeof *tailp);
+		    tailp = tailp->next;
+		    tailp->map = dep;
+		    tailp->next = NULL;
+		    ++nlist;
 		  }
-		list[nlist++] = _dl_map_object (l, strtab + d->d_un.d_val);
 	      }
 	}
     }
 
-  map->l_searchlist = list;
+  /* Store the search list we built in the object.  It will be used for
+     searches in the scope of this object.  */
+  map->l_searchlist = malloc (nlist * sizeof (struct link_map *));
   map->l_nsearchlist = nlist;
+
+  nlist = 0;
+  for (scanp = &head; scanp; scanp = scanp->next)
+    {
+      map->l_searchlist[nlist++] = scanp->map;
+
+      /* Now clear all the mark bits we set in the objects on the search list
+	 to avoid duplicates, so the next call starts fresh.  */
+      scanp->map->l_reserved = 0;
+    }
 }
 
 
@@ -86,7 +117,7 @@ _dl_open (struct link_map *parent, const char *file, int mode)
       _dl_relocate_object (l, (mode & RTLD_BINDING_MASK) == RTLD_LAZY);
 
   /* Run the initializer functions of new objects.  */
-  while (init = _dl_init_next ())
+  while (init = _dl_init_next (new))
     (*(void (*) (void)) init) ();
 
   return new;
diff --git a/elf/dl-init.c b/elf/dl-init.c
index 7375c5f782..ee99ce3dec 100644
--- a/elf/dl-init.c
+++ b/elf/dl-init.c
@@ -1,5 +1,5 @@
 /* Return the next shared object initializer function not yet run.
-Copyright (C) 1995 Free Software Foundation, Inc.
+Copyright (C) 1995, 1996 Free Software Foundation, Inc.
 This file is part of the GNU C Library.
 
 The GNU C Library is free software; you can redistribute it and/or
@@ -21,45 +21,35 @@ Cambridge, MA 02139, USA.  */
 #include <link.h>
 
 
+/* Run initializers for MAP and its dependencies, in inverse dependency
+   order (that is, leaf nodes first).  */
+
 Elf32_Addr
-_dl_init_next (void)
+_dl_init_next (struct link_map *map)
 {
-  struct link_map *l;
-  Elf32_Addr init;
+  unsigned int i;
+
+  /* The search list for symbol lookup is a flat list in top-down
+     dependency order, so processing that list from back to front gets us
+     breadth-first leaf-to-root order.  */
 
-  Elf32_Addr next_init (struct link_map *l)
+  i = map->l_nsearchlist;
+  while (i-- > 0)
     {
+      struct link_map *l = map->l_searchlist[i];
+
       if (l->l_init_called)
 	/* This object is all done.  */
-	return 0;
+	continue;
+
       if (l->l_init_running)
 	{
 	  /* This object's initializer was just running.
 	     Now mark it as having run, so this object
 	     will be skipped in the future.  */
-	  l->l_init_called = 1;
 	  l->l_init_running = 0;
-	  return 0;
-	}
-
-      if (l->l_info[DT_NEEDED])
-	{
-	  /* Find each dependency in order, and see if it
-	     needs to run an initializer.  */
-	  const char *strtab
-	    = ((void *) l->l_addr + l->l_info[DT_STRTAB]->d_un.d_ptr);
-	  const Elf32_Dyn *d;
-	  for (d = l->l_ld; d->d_tag != DT_NULL; ++d)
-	    if (d->d_tag == DT_NEEDED)
-	      {
-		struct link_map *needed
-		  = _dl_map_object (l, strtab + d->d_un.d_val);
-		Elf32_Addr init;
-		--needed->l_opencount;
-		init = next_init (needed); /* Recurse on this dependency.  */
-		if (init != 0)
-		  return init;
-	      }
+	  l->l_init_called = 1;
+	  continue;
 	}
 
       if (l->l_info[DT_INIT] &&
@@ -73,17 +63,7 @@ _dl_init_next (void)
       /* No initializer for this object.
 	 Mark it so we will skip it in the future.  */
       l->l_init_called = 1;
-      return 0;
-    }
-
-  /* Look for the first initializer not yet called.  */
-  l = _dl_loaded;
-  do
-    {
-      init = next_init (l);
-      l = l->l_next;
     }
-  while (init == 0 && l);
 
-  return init;
+  return 0;
 }
diff --git a/elf/dladdr.c b/elf/dladdr.c
index 166952ac46..87283e2586 100644
--- a/elf/dladdr.c
+++ b/elf/dladdr.c
@@ -20,7 +20,6 @@ Cambridge, MA 02139, USA.  */
 #include <stddef.h>
 #include <link.h>
 #include <dlfcn.h>
-#include <setjmp.h>
 
 
 int
@@ -30,7 +29,6 @@ dladdr (void *address, Dl_info *info)
   struct link_map *l, *match;
   const Elf32_Sym *symtab, *matchsym;
   const char *strtab;
-  Elf32_Word symidx;
 
   /* Find the highest-addressed object that ADDRESS is not below.  */
   match = NULL;
diff --git a/elf/dlclose.c b/elf/dlclose.c
index 06b2d1bdcd..fbb3ca6fe2 100644
--- a/elf/dlclose.c
+++ b/elf/dlclose.c
@@ -1,5 +1,5 @@
 /* dlclose -- Close a handle opened by `dlopen'.
-Copyright (C) 1995 Free Software Foundation, Inc.
+Copyright (C) 1995, 1996 Free Software Foundation, Inc.
 This file is part of the GNU C Library.
 
 The GNU C Library is free software; you can redistribute it and/or
@@ -32,64 +32,68 @@ dlclose (void *handle)
   void doit (void)
     {
       struct link_map *map = handle;
+      struct link_map **list;
+      unsigned int i;
 
       if (map->l_opencount == 0)
 	LOSE ("shared object not open");
 
       /* Decrement the reference count.  */
-      --map->l_opencount;
-
-      if (map->l_opencount == 0 && map->l_type == lt_loaded)
+      if (--map->l_opencount > 0 || map->l_type != lt_loaded)
+	/* There are still references to this object.  Do nothing more.  */
+	return;
+
+      list = map->l_searchlist;
+
+      /* The search list contains a counted reference to each object it
+	 points to, the 0th elt being MAP itself.  Decrement the reference
+	 counts on all the objects MAP depends on.  */
+      for (i = 1; i < map->l_nsearchlist; ++i)
+	--list[i]->l_opencount;
+
+      /* Clear the search list so it doesn't get freed while we are still
+         using it.  We have cached it in LIST and will free it when
+         finished.  */
+      map->l_searchlist = NULL;
+
+      /* Check each element of the search list to see if all references to
+         it are gone.  */
+      for (i = 0; i < map->l_nsearchlist; ++i)
 	{
-	  /* That was the last reference, and this was a dlopen-loaded
-	     object.  We can unmap it.  */
-	  const Elf32_Phdr *ph;
-
-	  if (map->l_info[DT_FINI])
-	    /* Call its termination function.  */
-	    (*(void (*) (void)) ((void *) map->l_addr +
-				 map->l_info[DT_FINI]->d_un.d_ptr)) ();
-
-	  if (map->l_info[DT_NEEDED])
+	  struct link_map *map = list[i];
+	  if (map->l_opencount == 0 && map->l_type == lt_loaded)
 	    {
-	      /* Also close all the dependencies.  */
-	      const char *strtab
-		= (void *) map->l_addr + map->l_info[DT_STRTAB]->d_un.d_ptr;
-	      const Elf32_Dyn *d;
-	      for (d = map->l_ld; d->d_tag != DT_NULL; ++d)
-		if (d->d_tag == DT_NEEDED)
+	      /* That was the last reference, and this was a dlopen-loaded
+		 object.  We can unmap it.  */
+	      const Elf32_Phdr *ph;
+
+	      if (map->l_info[DT_FINI])
+		/* Call its termination function.  */
+		(*(void (*) (void)) ((void *) map->l_addr +
+				     map->l_info[DT_FINI]->d_un.d_ptr)) ();
+
+	      /* Unmap the segments.  */
+	      for (ph = map->l_phdr; ph < &map->l_phdr[map->l_phnum]; ++ph)
+		if (ph->p_type == PT_LOAD)
 		  {
-		    /* It must already be open, since this one needed it;
-		       so dlopen will just find us its `struct link_map'
-		       and bump its reference count.  */
-		    struct link_map *o, *dep
-		      = dlopen (strtab + d->d_un.d_val, RTLD_LAZY);
-		    --dep->l_opencount; /* Lose the ref from that dlopen.  */
-		    /* Now we have the handle; we can close it for real.  */
-		    o = map;
-		    map = dep;
-		    doit ();
-		    map = o;
+		    Elf32_Addr mapstart = ph->p_vaddr & ~(ph->p_align - 1);
+		    Elf32_Addr mapend = ((ph->p_vaddr + ph->p_memsz
+					  + ph->p_align - 1)
+					 & ~(ph->p_align - 1));
+		    munmap ((caddr_t) mapstart, mapend - mapstart);
 		  }
-	    }
 
-	  /* Unmap the segments.  */
-	  for (ph = map->l_phdr; ph < &map->l_phdr[map->l_phnum]; ++ph)
-	    if (ph->p_type == PT_LOAD)
-	      {
-		Elf32_Addr mapstart = ph->p_vaddr & ~(ph->p_align - 1);
-		Elf32_Addr mapend = ((ph->p_vaddr + ph->p_memsz
-				      + ph->p_align - 1)
-				     & ~(ph->p_align - 1));
-		munmap ((caddr_t) mapstart, mapend - mapstart);
-	      }
-
-	  /* Finally, unlink the data structure and free it.  */
-	  map->l_prev->l_next = map->l_next;
-	  if (map->l_next)
-	    map->l_next->l_prev = map->l_prev;
-	  free (map);
+	      /* Finally, unlink the data structure and free it.  */
+	      map->l_prev->l_next = map->l_next;
+	      if (map->l_next)
+		map->l_next->l_prev = map->l_prev;
+	      if (map->l_searchlist)
+		free (map->l_searchlist);
+	      free (map);
+	    }
 	}
+
+      free (list);
     }
 
   return _dlerror_run (doit) ? -1 : 0;
diff --git a/elf/dlsym.c b/elf/dlsym.c
index 804d404bb3..f874af780a 100644
--- a/elf/dlsym.c
+++ b/elf/dlsym.c
@@ -27,21 +27,13 @@ void *
 dlsym (void *handle, const char *name)
 {
   struct link_map *map = handle;
-  struct link_map *real_next;
   Elf32_Addr loadbase;
   const Elf32_Sym *ref = NULL;
-  int lose;
   void doit (void)
     {
       struct link_map *scope[2] = { map, NULL };
       loadbase = _dl_lookup_symbol (name, &ref, scope, map->l_name, 0, 0);
     }
 
-  /* Confine the symbol scope to just this map.  */
-  real_next = map->l_next;
-  map->l_next = NULL;
-  lose = _dlerror_run (doit);
-  map->l_next = real_next;
-
-  return lose ? NULL : (void *) (loadbase + ref->st_value);
+  return _dlerror_run (doit) ? NULL : (void *) (loadbase + ref->st_value);
 }
diff --git a/elf/link.h b/elf/link.h
index 73782d8ac3..51740eeeee 100644
--- a/elf/link.h
+++ b/elf/link.h
@@ -111,6 +111,7 @@ struct link_map
     unsigned int l_relocated:1;	/* Nonzero if object's relocations done.  */
     unsigned int l_init_called:1; /* Nonzero if DT_INIT function called.  */
     unsigned int l_init_running:1; /* Nonzero while DT_INIT function runs.  */
+    unsigned int l_reserved:3;	/* Reserved for internal use.  */
   };
 
 /* Internal functions of the run-time dynamic linker.
@@ -231,10 +232,11 @@ extern struct link_map *_dl_new_object (char *realname, const char *libname,
    If LAZY is nonzero, don't relocate its PLT.  */
 extern void _dl_relocate_object (struct link_map *map, int lazy);
 
-/* Return the address of the next initializer function not yet run.
-   When there are no more initializers to be run, this returns zero.
-   The functions are returned in the order they should be called.  */
-extern Elf32_Addr _dl_init_next (void);
+/* Return the address of the next initializer function for MAP or one of
+   its dependencies that has not yet been run.  When there are no more
+   initializers to be run, this returns zero.  The functions are returned
+   in the order they should be called.  */
+extern Elf32_Addr _dl_init_next (struct link_map *map);
 
 /* Call the finalizer functions of all shared objects whose
    initializer functions have completed.  */