diff mbox series

[v2,31/32] elf: Add hash tables to speed up DT_NEEDED, dlopen lookups

Message ID af287eecfa1031f5d2315bb5241fc0a03a2c154e.1688741159.git.fweimer@redhat.com
State New
Headers show
Series RELRO link maps | expand

Commit Message

Florian Weimer July 7, 2023, 7:08 p.m. UTC
Each hash table is specific to one dlopen namespace.  For convenience,
it uses the GNU symbol hash function, but that choice is arbitrary.
The hash tables use the protected memory allocator.

The associated aliases are linked from the link map using the dual-use
l_name field.  See the new l_libname accessor function.  This could
be changed back to a dedicated field in the private link map if
it is necessary to enable applications which write to l_name in a
limited fashion.

The alloca copy in _dl_load_cache_lookup is no longer needed
because _dl_libname_allocate does not use the interposable malloc,
and so cannot call back into the dynamic linker.

In _dl_map_new_object, check for memory allocation failure and
empty tokens during DST expansion. This was handled implicitly
before, by falling through to the fd == -1 path (memory allocation
failure), or by trying to open "" (empty DST expansion).

The rewritten logic in _dl_new_object avoids adding an alias to
an object that is identical to the object's file name in l_name.
It also special-cases the vDSO cases, which is initially created
without a name (the soname becomes known only afterwards).

The l_soname_added field in the link map is no longer needed because
duplicated additions are avoided in _dl_libname_add_alias.
---
 elf/Makefile               |   1 +
 elf/dl-cache.c             |  13 +-
 elf/dl-close.c             |  14 --
 elf/dl-libc_freeres.c      |  13 --
 elf/dl-libname.c           | 281 +++++++++++++++++++++++++++++++++++++
 elf/dl-libname.h           | 121 ++++++++++++++++
 elf/dl-load.c              | 165 ++++++++--------------
 elf/dl-misc.c              |  18 ---
 elf/dl-object.c            | 131 ++++++++++-------
 elf/dl-open.c              |  11 +-
 elf/dl-support.c           |  15 +-
 elf/dl-version.c           |   9 +-
 elf/pldd-xx.c              |  19 +--
 elf/pldd.c                 |   1 +
 elf/rtld.c                 |  91 ++++--------
 elf/setup-vdso.h           |  18 +--
 elf/sotruss-lib.c          |   6 +-
 include/link.h             |   5 +-
 sysdeps/generic/ldsodefs.h |  23 ++-
 19 files changed, 630 insertions(+), 325 deletions(-)
 create mode 100644 elf/dl-libname.c
 create mode 100644 elf/dl-libname.h
diff mbox series

Patch

diff --git a/elf/Makefile b/elf/Makefile
index 2219263e8c..c6a3c4678b 100644
--- a/elf/Makefile
+++ b/elf/Makefile
@@ -63,6 +63,7 @@  dl-routines = \
   dl-find_object \
   dl-fini \
   dl-init \
+  dl-libname \
   dl-load \
   dl-lookup \
   dl-lookup-direct \
diff --git a/elf/dl-cache.c b/elf/dl-cache.c
index a3eb960dac..2818f9a8f4 100644
--- a/elf/dl-cache.c
+++ b/elf/dl-cache.c
@@ -26,6 +26,7 @@ 
 #include <_itoa.h>
 #include <dl-hwcaps.h>
 #include <dl-isa-level.h>
+#include <dl-libname.h>
 
 #ifndef _DL_PLATFORMS_COUNT
 # define _DL_PLATFORMS_COUNT 0
@@ -399,7 +400,7 @@  _dl_cache_libcmp (const char *p1, const char *p2)
    this function must take care that it does not return references to
    any data in the mapping.  */
 bool
-_dl_load_cache_lookup (const char *name, char **realname)
+_dl_load_cache_lookup (const char *name, struct libname **realname)
 {
   /* Print a message if the loading of libs is traced.  */
   if (__glibc_unlikely (GLRO(dl_debug_mask) & DL_DEBUG_LIBS))
@@ -510,15 +511,7 @@  _dl_load_cache_lookup (const char *name, char **realname)
       return true;
     }
 
-  /* The double copy is *required* since malloc may be interposed
-     and call dlopen itself whose completion would unmap the data
-     we are accessing. Therefore we must make the copy of the
-     mapping data without using malloc.  */
-  char *temp;
-  size_t best_len = strlen (best) + 1;
-  temp = alloca (best_len);
-  memcpy (temp, best, best_len);
-  char *copy = __strdup (temp);
+  struct libname *copy = _dl_libname_allocate (best);
   if (copy == NULL)
     return false;
   *realname = copy;
diff --git a/elf/dl-close.c b/elf/dl-close.c
index 7fbd9a4814..39a00e5f35 100644
--- a/elf/dl-close.c
+++ b/elf/dl-close.c
@@ -675,20 +675,6 @@  _dl_close_worker (struct link_map_private *map, bool force)
 	    _dl_debug_printf ("\nfile=%s [%lu];  destroying link map\n",
 			      imap->l_public.l_name, imap->l_ns);
 
-	  /* This name always is allocated.  */
-	  free (imap->l_public.l_name);
-	  /* Remove the list with all the names of the shared object.  */
-
-	  struct libname_list *lnp = imap->l_libname;
-	  do
-	    {
-	      struct libname_list *this = lnp;
-	      lnp = lnp->next;
-	      if (!this->dont_free)
-		free (this);
-	    }
-	  while (lnp != NULL);
-
 	  /* Remove the searchlists.  */
 	  free (imap->l_initfini);
 
diff --git a/elf/dl-libc_freeres.c b/elf/dl-libc_freeres.c
index 066629639c..f72d9df8d6 100644
--- a/elf/dl-libc_freeres.c
+++ b/elf/dl-libc_freeres.c
@@ -70,19 +70,6 @@  __rtld_libc_freeres (void)
     {
       for (l = GL(dl_ns)[ns]._ns_loaded; l != NULL; l = l_next (l))
 	{
-	  struct libname_list *lnp = l->l_libname->next;
-
-	  l->l_libname->next = NULL;
-
-	  /* Remove all additional names added to the objects.  */
-	  while (lnp != NULL)
-	    {
-	      struct libname_list *old = lnp;
-	      lnp = lnp->next;
-	      if (! old->dont_free)
-		free (old);
-	    }
-
 	  /* Free the initfini dependency list.  */
 	  if (l->l_free_initfini)
 	    free (l->l_initfini);
diff --git a/elf/dl-libname.c b/elf/dl-libname.c
new file mode 100644
index 0000000000..28fc262343
--- /dev/null
+++ b/elf/dl-libname.c
@@ -0,0 +1,281 @@ 
+/* Managing alias names for link names, and link map lookup by name.
+   Copyright (C) 2023 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
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   The GNU C Library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with the GNU C Library; if not, see
+   <https://www.gnu.org/licenses/>.  */
+
+#include <dl-libname.h>
+
+#include <assert.h>
+#include <dl-new-hash.h>
+#include <dl-protmem.h>
+#include <ldsodefs.h>
+#include <libintl.h>
+
+/* Per-namespace hash table of library names.  Uses linked lists via
+   next_hash for collision resolution.  Resized once half-full.  */
+struct libname_table { uint32_t count; /* Number of
+entries in the hash table.  */
+  uint32_t mask;                /* Bucket count minus 1.  */
+  struct libname **buckets;     /* Hash buckets.  */
+};
+
+#ifndef SHARED
+struct libname_table *_dl_libnames[DL_NNS];
+#endif
+
+struct libname *
+_dl_libname_allocate_hash (const char *name, uint32_t hash)
+{
+  size_t name_len = strlen (name) + 1;
+  struct libname *result
+    = _dl_protmem_allocate (offsetof (struct libname, name) + name_len);
+  result->map = NULL;
+  result->next_link_map = NULL;
+  result->next_hash = NULL;
+  result->hash = _dl_libname_hash (name);
+  memcpy (result->name, name, name_len);
+  return result;
+}
+
+struct libname *
+_dl_libname_allocate (const char *name)
+{
+  return _dl_libname_allocate_hash (name, _dl_libname_hash (name));
+}
+
+void
+_dl_libname_free (struct libname *ln)
+{
+  _dl_protmem_free (ln,
+                    offsetof (struct libname, name) + strlen (ln->name) + 1);
+}
+
+uint32_t
+_dl_libname_hash (const char *name)
+{
+  return _dl_new_hash (name);
+}
+
+/* Returns the appropriate hash chain for the name's HASH in
+   namespace NSID.  */
+static struct libname *
+_dl_libname_chain (Lmid_t nsid, uint32_t hash)
+{
+  struct libname_table *lt = GLPM (dl_libnames)[nsid];
+  if (lt == NULL)
+    return NULL;
+  return lt->buckets[hash & lt->mask];
+}
+
+struct link_map_private *
+_dl_libname_lookup_hash (Lmid_t nsid, const char *name, uint32_t hash)
+{
+
+  /* Checking l_prev and l_next verifies that the discovered alias has
+     been added to a namespace list.  It is necessary to add aliases
+     to the hash table early, before updating the namespace list, so
+     that _dl_libname_add_alias can avoid adding duplicates.  However,
+     during early startup, the ld.so link map is not added to the list
+     when the main program is loaded as part of an explicit loader
+     invocation.  If the main program is again ld.so (a user error),
+     it is not loaded again, violating some core assumptions in
+     rtld_chain_load and setup_vdso.  For static builds, the l_prev
+     and l_next checks need to be disabled because the main program is
+     the only map if there is no vDSO (and the hash table is
+     initialized after the namespace list anyway).  */
+  for (struct libname *ln = _dl_libname_chain (nsid, hash);
+       ln != NULL; ln = ln->next_hash)
+    if (ln->hash == hash && strcmp (name, ln->name) == 0
+        && (ln->map->l_faked | ln->map->l_removed) == 0
+#ifdef SHARED
+        && (ln->map->l_public.l_prev != NULL
+            || ln->map->l_public.l_next != NULL)
+#endif
+        )
+      return ln->map;
+  return NULL;
+}
+
+struct link_map_private *
+_dl_lookup_map (Lmid_t nsid, const char *name)
+{
+  return _dl_libname_lookup_hash (nsid, name, _dl_libname_hash (name));
+}
+
+struct link_map_private *
+_dl_lookup_map_unfiltered (Lmid_t nsid, const char *name)
+{
+  /* This is only used in dl-version.c, which may rely l_faked
+     objects.  The l_prev/l_next filter is not needed there because
+     the namespace list update has completed.  */
+  uint32_t hash = _dl_libname_hash (name);
+  for (struct libname *ln = _dl_libname_chain (nsid, hash);
+       ln != NULL; ln = ln->next_hash)
+    if (ln->hash == hash && strcmp (name, ln->name) == 0
+        && (ln->map->l_removed == 0))
+      return ln->map;
+  return NULL;
+}
+
+int
+_dl_name_match_p (const char *name, const struct link_map_private *map)
+{
+  /* An alternative implementation could use the list of names
+     starting at l_libname (map), but this implementation is fast even
+     with many aliases.  */
+  uint32_t hash = _dl_libname_hash (name);
+  for (struct libname *ln = _dl_libname_chain (map->l_ns, hash);
+       ln != NULL; ln = ln->next_hash)
+    if (ln->hash == hash && ln->map == map && strcmp (name, ln->name) == 0)
+      return true;
+  return false;
+}
+
+bool
+_dl_libname_table_init (Lmid_t nsid)
+{
+  struct libname_table *lt = GLPM (dl_libnames)[nsid];
+  if (lt != NULL)
+    return true;
+  lt = _dl_protmem_allocate (sizeof (*lt));
+  if (lt == NULL)
+    return false;
+  lt->count = 0;
+  lt->mask = 15;
+  size_t buckets_size = (lt->mask + 1) * sizeof (*lt->buckets);
+  lt->buckets = _dl_protmem_allocate (buckets_size);
+  if (lt->buckets == NULL)
+    {
+      _dl_protmem_free (lt, sizeof (*lt));
+      return NULL;
+    }
+  memset (lt->buckets, 0, buckets_size);
+  GLPM (dl_libnames)[nsid] = lt;
+#ifndef SHARED
+  /* _dl_libname_table_init is called from dlopen in the !SHARED case
+     to set up the hash map.  The code in _dl_non_dynamic_init avoids
+     these allocation in case dlopen is never called.  */
+  _dl_libname_link_hash (l_libname (GL (dl_ns)[0]._ns_loaded));
+#endif
+  return true;
+}
+
+void
+_dl_libname_add_link_map (struct link_map_private *l, struct libname *ln)
+{
+  assert (ln->map == NULL);
+  ln->map = l;
+  if (l->l_public.l_name == NULL)
+    l->l_public.l_name = ln->name;
+  else
+    {
+      /* Do not override l_name.  */
+      struct libname *first = l_libname (l);
+      ln->next_link_map = first->next_link_map;
+      first->next_link_map = ln;
+    }
+}
+
+/* Grow LT->buckets.  */
+static void
+_dl_libname_table_grow (struct libname_table *lt)
+{
+  uint32_t new_mask = lt->mask * 2 + 1;
+  struct libname **new_buckets;
+  size_t new_buckets_size = (new_mask + 1) * sizeof (*new_buckets);
+
+  new_buckets = _dl_protmem_allocate (new_buckets_size);
+  if (new_buckets == NULL)
+    /* If the allocation fails, we can just add more bucket collisions.  */
+    return;
+
+  /* Rehash.  */
+  memset (new_buckets, 0, new_buckets_size);
+  for (unsigned int i = 0; i <= lt->mask; ++i)
+    for (struct libname *ln = lt->buckets[i]; ln != NULL; )
+      {
+        struct libname *next = ln->next_hash;
+        ln->next_hash = new_buckets[ln->hash & new_mask];
+        new_buckets[ln->hash & new_mask] = ln;
+        ln = next;
+      }
+  /* Discard old bucket array.  */
+  _dl_protmem_free (lt->buckets,
+                    (lt->mask + 1) * sizeof (*lt->buckets));
+  /* Switch to new bucket array.  */
+  lt->buckets = new_buckets;
+  lt->mask = new_mask;
+}
+
+void
+_dl_libname_link_hash (struct libname *lname)
+{
+  assert (lname->next_hash == NULL);
+  struct libname_table *lt = GLPM (dl_libnames)[lname->map->l_ns];
+  ++lt->count;
+  if (lt->count * 2 > lt->mask)
+    _dl_libname_table_grow (lt);
+
+  /* Add the new entry to the end.  This prevents overriding the alias
+     of a different, already-loaded object.  */
+  struct libname **pln = &lt->buckets[lname->hash & lt->mask];
+  while (*pln != NULL)
+    pln = &(*pln)->next_hash;
+  *pln = lname;
+}
+
+void
+_dl_libname_unlink_hash (struct libname *lname)
+{
+  struct libname_table *lt = GLPM (dl_libnames)[lname->map->l_ns];
+  struct libname **pln = &lt->buckets[lname->hash & lt->mask];
+  while (*pln != NULL)
+    {
+      if (*pln == lname)
+        {
+          *pln = lname->next_hash;
+          lname->next_hash = NULL;
+          --lt->count;
+          return;
+        }
+      pln = &(*pln)->next_hash;
+    }
+
+  _dl_fatal_printf ("\
+Fatal glibc error: library name not found on hash chain\n");
+}
+
+void
+_dl_libname_add_alias (struct link_map_private *l, const char *name)
+{
+  uint32_t hash = _dl_libname_hash (name);
+
+  /* Check if the name is already present.  */
+  for (struct libname *ln = _dl_libname_chain (l->l_ns, hash); ln != NULL;
+       ln = ln->next_hash)
+    if (ln->hash == hash && ln->map == l && strcmp (name, ln->name) == 0)
+      return;
+
+  struct libname *ln = _dl_libname_allocate_hash (name, hash);
+  if (ln == NULL || ! _dl_libname_table_init (l->l_ns))
+    {
+      if (ln != NULL)
+        _dl_libname_free (ln);
+      _dl_signal_error (ENOMEM, name, NULL, N_("cannot allocate name record"));
+    }
+  _dl_libname_add_link_map (l, ln);
+  _dl_libname_link_hash (ln);
+}
diff --git a/elf/dl-libname.h b/elf/dl-libname.h
new file mode 100644
index 0000000000..3b4f426d05
--- /dev/null
+++ b/elf/dl-libname.h
@@ -0,0 +1,121 @@ 
+/* Managing alias names for link names, and link map lookup by name.
+   Copyright (C) 2023 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
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   The GNU C Library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with the GNU C Library; if not, see
+   <https://www.gnu.org/licenses/>.  */
+
+#ifndef DL_LIBNAME_H
+#define DL_LIBNAME_H
+
+#include <link.h>
+
+/* A name or alias of a link map.  */
+struct libname
+  {
+    /* The link map to which this name belongs.   */
+    struct link_map_private *map;
+
+    /* Next alias of the same link map.  */
+    struct libname *next_link_map;
+
+    /* Next library name on the same hash chain.  */
+    struct libname *next_hash;
+
+    /* GNU hash of the name.  See _dl_libname_hash below.  */
+    uint32_t hash;
+
+    /* Null-terminated name.  Must not be modified after allocation.  */
+    char name[];
+  };
+
+/* Derive the start of the alias list from the l_name field of the
+   link map.  */
+static inline struct libname *
+l_libname (struct link_map_private *l)
+{
+  return (struct libname *) (l->l_public.l_name
+                             - offsetof (struct libname, name));
+}
+
+/* Return the user-supplied name if available, otherwise the internal
+   name.  */
+static inline const char *
+l_libname_last_alias (struct link_map_private *l)
+{
+  /* This is the internal name (typically an absolute  path).  */
+  struct libname *ln = l_libname (l);
+  if (ln->next_link_map != NULL)
+    /* This is a user-supplied alias.  The successor to ln is the
+       alias that was added last.  */
+    return ln->next_link_map->name;
+  else
+    return ln->name;
+}
+
+/* Deallocate a library name allocated using _dl_libname_allocate
+   below.  */
+void _dl_libname_free (struct libname *name)
+  attribute_hidden __nonnull ((1));
+
+/* Allocate a link map alias name for NAME.  The map field,
+   next_link_map and next_hash are set to NULL, and the hash is
+   computed based on NAME.  */
+struct libname *_dl_libname_allocate (const char *name)
+  attribute_hidden __attribute_malloc__ __nonnull ((2))
+  __attr_dealloc (_dl_libname_free, 1);
+
+/* Like _dl_libname_allocate, but uses a pre-computed HASH.  */
+struct libname *_dl_libname_allocate_hash (const char *name, uint32_t hash)
+  attribute_hidden __attribute_malloc__ __nonnull ((2))
+  __attr_dealloc (_dl_libname_free, 1);
+
+/* Computes the GNU hash of NAME.  */
+uint32_t _dl_libname_hash (const char *name) attribute_hidden __nonnull ((1));
+
+/* Looks up the NAME string in hash table for namespace NSID, using
+   the pre-computed HASH (see _dl_libname_hash).  Returns NULL if
+   NAME has not been loaded into NSID.  */
+struct link_map_private *_dl_libname_lookup_hash (Lmid_t nsid,
+                                                  const char *name,
+                                                  uint32_t hash)
+  attribute_hidden __nonnull ((2)) __attribute__ ((warn_unused_result));
+
+/* Links NAME into the alias list for L.  Sets NAME->map to L, which
+   must be NULL originally.  */
+void _dl_libname_add_link_map (struct link_map_private *l,
+                               struct libname *name)
+  attribute_hidden __nonnull ((1, 2));
+
+/* Initalize the hash table for NSID.  Must be called at least once
+   before _dl_libname_link_hash.  Returns false if initialization
+   failed (due to memory allocation failure).  */
+bool _dl_libname_table_init (Lmid_t nsid) attribute_hidden;
+
+/* Links NAME into the hash table for NAME->map->l_ns.  */
+void _dl_libname_link_hash (struct libname *name)
+  attribute_hidden __nonnull ((2));
+
+/* Removes NAME from the hash table from NAME->map->l_ns.  */
+void _dl_libname_unlink_hash (struct libname *name)
+  attribute_hidden __nonnull ((2));
+
+/* Add an alias name to L (which must contain at least one name in
+   L-l_name).  Raises an exception on memory allocation failure.  Does
+   nothing if NAME is already associated with any object in L's
+   namespace.  */
+void _dl_libname_add_alias (struct link_map_private *l, const char *name)
+  attribute_hidden __nonnull ((1, 2));
+
+#endif /* DL_LIBNAME_H */
diff --git a/elf/dl-load.c b/elf/dl-load.c
index 3d446614cb..035760a90e 100644
--- a/elf/dl-load.c
+++ b/elf/dl-load.c
@@ -34,6 +34,7 @@ 
 #include <gnu/lib-names.h>
 #include <alloc_buffer.h>
 #include <dl-protmem.h>
+#include <dl-libname.h>
 
 /* Type for the buffer we put the ELF header and hopefully the program
    header.  This buffer does not really have to be too large.  In most
@@ -387,40 +388,6 @@  expand_dynamic_string_token (struct link_map_private *l, const char *input)
   return result;
 }
 
-
-/* Add `name' to the list of names for a particular shared object.
-   `name' is expected to have been allocated with malloc and will
-   be freed if the shared object already has this name.
-   Returns false if the object already had this name.  */
-static void
-add_name_to_object (struct link_map_private *l, const char *name)
-{
-  struct libname_list *lnp, *lastp;
-  struct libname_list *newname;
-  size_t name_len;
-
-  lastp = NULL;
-  for (lnp = l->l_libname; lnp != NULL; lastp = lnp, lnp = lnp->next)
-    if (strcmp (name, lnp->name) == 0)
-      return;
-
-  name_len = strlen (name) + 1;
-  newname = (struct libname_list *) malloc (sizeof *newname + name_len);
-  if (newname == NULL)
-    {
-      /* No more memory.  */
-      _dl_signal_error (ENOMEM, name, NULL, N_("cannot allocate name record"));
-      return;
-    }
-  /* The object should have a libname set from _dl_new_object.  */
-  assert (lastp != NULL);
-
-  newname->name = memcpy (newname + 1, name, name_len);
-  newname->next = NULL;
-  newname->dont_free = 0;
-  lastp->next = newname;
-}
-
 /* Standard search directories.  */
 struct r_search_path_struct __rtld_search_dirs attribute_relro;
 
@@ -902,7 +869,7 @@  static
 #endif
 struct link_map_private *
 _dl_map_object_from_fd (const char *name, const char *origname, int fd,
-			struct filebuf *fbp, char *realname,
+			struct filebuf *fbp, struct libname *realname,
 			struct link_map_private *loader, int l_type, int mode,
 			void **stack_endp, Lmid_t nsid)
 {
@@ -940,13 +907,10 @@  _dl_map_object_from_fd (const char *name, const char *origname, int fd,
 	    _dl_unmap_segments (l);
 	  if (l != NULL && l->l_origin != (char *) -1l)
 	    free ((char *) l->l_origin);
-	  if (l != NULL && !l->l_libname->dont_free)
-	    free (l->l_libname);
 	  if (l != NULL && l->l_phdr_allocated)
 	    free ((void *) l->l_phdr);
 	  if (l != NULL)
 	    _dl_free_object (l);
-	  free (realname);
 	  _dl_signal_error (errval, name, NULL, errstring);
 	}
 
@@ -960,8 +924,8 @@  _dl_map_object_from_fd (const char *name, const char *origname, int fd,
 
 	    /* If the name is not in the list of names for this object add
 	       it.  */
-	    free (realname);
-	    add_name_to_object (l, name);
+	    _dl_libname_free (realname);
+	    _dl_libname_add_alias (l, name);
 
 	    return l;
 	  }
@@ -1002,7 +966,7 @@  _dl_map_object_from_fd (const char *name, const char *origname, int fd,
     {
       /* We are not supposed to load the object unless it is already
 	 loaded.  So return now.  */
-      free (realname);
+      _dl_libname_free (realname);
       __close_nocancel (fd);
       return NULL;
     }
@@ -1410,17 +1374,15 @@  cannot enable executable stack as shared object requires");
   /* When auditing is used the recorded names might not include the
      name by which the DSO is actually known.  Add that as well.  */
   if (__glibc_unlikely (origname != NULL))
-    add_name_to_object (l, origname);
+    _dl_libname_add_alias (l, origname);
 #else
   /* Audit modules only exist when linking is dynamic so ORIGNAME
      cannot be non-NULL.  */
   assert (origname == NULL);
 #endif
 
-  /* When we profile the SONAME might be needed for something else but
-     loading.  Add it right away.  */
-  if (__glibc_unlikely (GLRO(dl_profile) != NULL) && l_soname (l) != NULL)
-    add_name_to_object (l, l_soname (l));
+  if (l_soname (l) != NULL)
+    _dl_libname_add_alias (l, l_soname (l));
 
   /* If we have newly loaded libc.so, update the namespace
      description.  */
@@ -1535,7 +1497,8 @@  print_search_path (struct r_search_path_elem **list,
 static int
 open_verify (const char *name, int fd,
              struct filebuf *fbp, struct link_map_private *loader,
-	     int whatcode, int mode, bool *found_other_class, bool free_name)
+	     int whatcode, int mode, bool *found_other_class,
+	     struct libname *free_name_on_error)
 {
   /* This is the expected ELF header.  */
 #define ELF32_CLASS ELFCLASS32
@@ -1620,8 +1583,8 @@  open_verify (const char *name, int fd,
 	lose:;
 	  struct dl_exception exception;
 	  _dl_exception_create (&exception, name, errstring);
-	  if (free_name)
-	    free ((char *) name);
+	  if (free_name_on_error != NULL)
+	    _dl_libname_free (free_name_on_error);
 	  __close_nocancel (fd);
 	  _dl_signal_exception (errval, &exception, NULL);
 	}
@@ -1749,7 +1712,7 @@  open_verify (const char *name, int fd,
 
 static int
 open_path (const char *name, size_t namelen, int mode,
-	   struct r_search_path_struct *sps, char **realname,
+	   struct r_search_path_struct *sps, struct libname **realname,
 	   struct filebuf *fbp, struct link_map_private *loader, int whatcode,
 	   bool *found_other_class)
 {
@@ -1805,7 +1768,7 @@  open_path (const char *name, size_t namelen, int mode,
 	    _dl_debug_printf ("  trying file=%s\n", buf);
 
 	  fd = open_verify (buf, -1, fbp, loader, whatcode, mode,
-			    found_other_class, false);
+			    found_other_class, NULL);
 	  if (this_dir->status[cnt] == unknown)
 	    {
 	      if (fd != -1)
@@ -1859,12 +1822,9 @@  open_path (const char *name, size_t namelen, int mode,
 
       if (fd != -1)
 	{
-	  *realname = (char *) malloc (buflen);
+	  *realname = _dl_libname_allocate (buf);
 	  if (*realname != NULL)
-	    {
-	      memcpy (*realname, buf, buflen);
-	      return fd;
-	    }
+	    return fd;
 	  else
 	    {
 	      /* No memory for the name, we certainly won't be able
@@ -1899,38 +1859,6 @@  open_path (const char *name, size_t namelen, int mode,
   return -1;
 }
 
-struct link_map_private *
-_dl_lookup_map (Lmid_t nsid, const char *name)
-{
-  assert (nsid >= 0);
-  assert (nsid < GL(dl_nns));
-
-  for (struct link_map_private *l = GL(dl_ns)[nsid]._ns_loaded;
-       l != NULL; l = l_next (l))
-    {
-      /* If the requested name matches the soname of a loaded object,
-	 use that object.  Elide this check for names that have not
-	 yet been opened.  */
-      if (__glibc_unlikely ((l->l_faked | l->l_removed) != 0))
-	continue;
-      if (!_dl_name_match_p (name, l))
-	{
-	  if (__glibc_likely (l->l_soname_added) || l_soname (l) == NULL
-	      || strcmp (name, l_soname (l)) != 0)
-	    continue;
-
-	  /* We have a match on a new name -- cache it.  */
-	  add_name_to_object (l, l_soname (l));
-	  l->l_soname_added = 1;
-	}
-
-      /* We have a match.  */
-      return l;
-    }
-
-  return NULL;
-}
-
 /* Map in the shared object file NAME.  */
 
 struct link_map_private *
@@ -1939,8 +1867,7 @@  _dl_map_new_object (struct link_map_private *loader, const char *name,
 {
   int fd;
   const char *origname = NULL;
-  char *realname;
-  char *name_copy;
+  struct libname *realname;
   struct link_map_private *l;
   struct filebuf fb;
 
@@ -2058,7 +1985,7 @@  _dl_map_new_object (struct link_map_private *loader, const char *name,
 	{
 	  /* Check the list of libraries in the file /etc/ld.so.cache,
 	     for compatibility with Linux's ldconfig program.  */
-	  char *cached;
+	  struct libname *cached;
 	  if (!_dl_load_cache_lookup (name, &cached))
 	    _dl_signal_error (ENOMEM, NULL, NULL,
 			      N_("cannot allocate library name"));
@@ -2082,10 +2009,11 @@  _dl_map_new_object (struct link_map_private *loader, const char *name,
 
 		  do
 		    {
-		      if (memcmp (cached, dirp, system_dirs_len[cnt]) == 0)
+		      if (memcmp (cached->name, dirp, system_dirs_len[cnt])
+			  == 0)
 			{
 			  /* The prefix matches.  Don't use the entry.  */
-			  free (cached);
+			  _dl_libname_free (cached);
 			  cached = NULL;
 			  break;
 			}
@@ -2098,14 +2026,14 @@  _dl_map_new_object (struct link_map_private *loader, const char *name,
 
 	      if (cached != NULL)
 		{
-		  fd = open_verify (cached, -1,
+		  fd = open_verify (cached->name, -1,
 				    &fb, loader ?: GL(dl_ns)[nsid]._ns_loaded,
 				    LA_SER_CONFIG, mode, &found_other_class,
-				    false);
+				    NULL);
 		  if (__glibc_likely (fd != -1))
 		    realname = cached;
 		  else
-		    free (cached);
+		    _dl_libname_free (cached);
 		}
 	    }
 	}
@@ -2126,21 +2054,36 @@  _dl_map_new_object (struct link_map_private *loader, const char *name,
   else
     {
       /* The path may contain dynamic string tokens.  */
-      realname = (loader
-		  ? expand_dynamic_string_token (loader, name)
-		  : __strdup (name));
-      if (realname == NULL)
-	fd = -1;
-      else
+      if (loader != NULL && strchr (name, '$') != NULL)
 	{
-	  fd = open_verify (realname, -1, &fb,
-			    loader ?: GL(dl_ns)[nsid]._ns_loaded, 0, mode,
-			    &found_other_class, true);
-	  if (__glibc_unlikely (fd == -1))
-	    free (realname);
+	  char *expanded = expand_dynamic_string_token (loader, name);
+	  if (expanded == NULL)
+	    realname = NULL;
+	  else if (*expanded == '\0')
+	    {
+	      free (expanded);
+	      _dl_signal_error (0, name, NULL, N_("\
+empty dynamic string token substitution"));
+	    }
+	  else
+	    {
+	      realname = _dl_libname_allocate (expanded);
+	      free (expanded);
+	    }
 	}
-    }
+      else
+	realname = _dl_libname_allocate (name);
 
+      if (realname == NULL)
+	_dl_signal_error (ENOMEM, name, NULL,
+			  N_("cannot allocate library name"));
+
+      fd = open_verify (realname->name, -1, &fb,
+			loader ?: GL(dl_ns)[nsid]._ns_loaded, 0, mode,
+			&found_other_class, realname);
+      if (__glibc_unlikely (fd == -1))
+	_dl_libname_free (realname);
+    }
 #ifdef SHARED
  no_file:
 #endif
@@ -2161,11 +2104,13 @@  _dl_map_new_object (struct link_map_private *loader, const char *name,
 	  static const Elf_Symndx dummy_bucket = STN_UNDEF;
 
 	  /* Allocate a new object map.  */
-	  if ((name_copy = __strdup (name)) == NULL
+	  struct libname *name_copy = _dl_libname_allocate (name);
+	  if (name_copy == NULL
 	      || (l = _dl_new_object (name_copy, name, type, loader,
 				      mode, nsid)) == NULL)
 	    {
-	      free (name_copy);
+	      if (name_copy != NULL)
+		_dl_libname_free (name_copy);
 	      _dl_signal_error (ENOMEM, name, NULL,
 				N_("cannot create shared object descriptor"));
 	    }
diff --git a/elf/dl-misc.c b/elf/dl-misc.c
index 37c8a4dee9..579194b0a0 100644
--- a/elf/dl-misc.c
+++ b/elf/dl-misc.c
@@ -62,24 +62,6 @@  _dl_sysdep_read_whole_file (const char *file, size_t *sizep, int prot)
   return result;
 }
 
-/* Test whether given NAME matches any of the names of the given object.  */
-int
-_dl_name_match_p (const char *name, const struct link_map_private *map)
-{
-  if (strcmp (name, map->l_public.l_name) == 0)
-    return 1;
-
-  struct libname_list *runp = map->l_libname;
-
-  while (runp != NULL)
-    if (strcmp (name, runp->name) == 0)
-      return 1;
-    else
-      runp = runp->next;
-
-  return 0;
-}
-
 unsigned long int
 _dl_higher_prime_number (unsigned long int n)
 {
diff --git a/elf/dl-object.c b/elf/dl-object.c
index 0ea3f6e2da..15714f59e1 100644
--- a/elf/dl-object.c
+++ b/elf/dl-object.c
@@ -22,6 +22,7 @@ 
 #include <unistd.h>
 #include <ldsodefs.h>
 #include <dl-protmem.h>
+#include <dl-libname.h>
 
 #include <assert.h>
 
@@ -55,44 +56,32 @@  _dl_add_to_namespace_list (struct link_map_private *new, Lmid_t nsid)
 /* Allocate a `struct link_map_private' for a new object being loaded,
    and enter it into the _dl_loaded list.  */
 struct link_map_private *
-_dl_new_object (char *realname, const char *libname, int type,
+_dl_new_object (struct libname *realname, const char *libname, int type,
 		struct link_map_private *loader, int mode, Lmid_t nsid)
 {
 #ifdef SHARED
   unsigned int naudit;
   if (__glibc_unlikely ((mode & (__RTLD_OPENEXEC | __RTLD_VDSO)) != 0))
-    {
-      if (mode & __RTLD_OPENEXEC)
-	{
-	  assert (type == lt_executable);
-	  assert (nsid == LM_ID_BASE);
-
-	  /* Ignore the specified libname for the main executable.  It is
-	     only known with an explicit loader invocation.  */
-	  libname = "";
-	}
-
-      /* We create the map for the executable and vDSO before we know whether
-	 we have auditing libraries and if yes, how many.  Assume the
-	 worst.  */
+    /* We create the map for the executable and vDSO before we know whether
+       we have auditing libraries and if yes, how many.  Assume the
+       worst.  */
       naudit = DL_NNS;
-    }
   else
     naudit = GLRO (dl_naudit);
 #endif
 
-  size_t libname_len = strlen (libname) + 1;
   struct link_map_private *new;
-  struct libname_list *newname;
 #ifdef SHARED
   size_t audit_space = naudit * sizeof (struct auditstate);
 #else
 # define audit_space 0
 #endif
 
+  if (!_dl_libname_table_init (nsid))
+    return NULL;
+
   size_t l_size = (sizeof (*new)
-		   + sizeof (struct link_map_private *)
-		   + sizeof (*newname) + libname_len);
+		   + sizeof (struct link_map_private *));
 
   new = _dl_protmem_allocate (l_size);
   if (new == NULL)
@@ -106,34 +95,68 @@  _dl_new_object (char *realname, const char *libname, int type,
       return NULL;
     }
 
+  new->l_ns = nsid;
   new->l_real = new;
   new->l_symbolic_searchlist.r_list
     = (struct link_map_private **) ((char *) (new + 1));
 
-  new->l_libname = newname
-    = (struct libname_list *) (new->l_symbolic_searchlist.r_list + 1);
-  newname->name = (char *) memcpy (newname + 1, libname, libname_len);
-  newname->next = NULL;
-  newname->dont_free = 1;
-
-  /* When we create the executable link map, or a VDSO link map, we start
-     with "" for the l_name. In these cases "" points to ld.so rodata
-     and won't get dumped during core file generation. Therefore to assist
-     gdb and to create more self-contained core files we adjust l_name to
-     point at the newly allocated copy (which will get dumped) instead of
-     the ld.so rodata copy.
-
-     Furthermore, in case of explicit loader invocation, discard the
-     name of the main executable, to match the regular behavior, where
-     name of the executable is not known.  */
-#ifdef SHARED
-  if (*realname != '\0' && (mode & __RTLD_OPENEXEC) == 0)
-#else
-  if (*realname != '\0')
-#endif
-    new->l_public.l_name = realname;
-  else
-    new->l_public.l_name = (char *) newname->name + libname_len - 1;
+ /* When creating the link map for the vDSO, there is no naming
+    information yet, so do not link in the names.  */
+  if (!(mode & __RTLD_VDSO))
+    {
+      if ((mode & __RTLD_OPENEXEC))
+	{
+	  /* Link map for the main executable.  */
+	  if (realname->name[0] == '\0')
+	    {
+	      /* Not an explicit loader invocation (standard PT_INTERP
+		 usage).  Use realname directly.  */
+	      new->l_public.l_name = realname->name;
+	      realname->map = new;
+	      _dl_libname_link_hash (realname);
+	    }
+	  else
+	    {
+	      /* Explict loader invocation.  Discard the file name for
+		 compatibility with the PT_INTERP invocation.  */
+	      struct libname *newname = _dl_libname_allocate ("");
+	      if (newname == NULL)
+		{
+		newname_error:
+		  free (new->l_rw);
+		  _dl_protmem_free (new, l_size);
+		  return NULL;
+		}
+	      new->l_public.l_name = newname->name;
+	      newname->map = new;
+	      _dl_libname_link_hash (newname);
+	      /* NB: realname is freed below.  */
+	    }
+	}
+      else
+	{
+	  /* Regular link map.  The file name is in realname.  Put it
+	     into l_name, to helper debuggers.  */
+	  new->l_public.l_name = realname->name;
+
+	  /* There may be a different alias in libname.  Store it if
+	     it is different.  */
+	  if (strcmp (libname, realname->name) != 0)
+	    {
+	      struct libname *newname = _dl_libname_allocate (libname);
+	      if (newname == NULL)
+		goto newname_error;
+	      _dl_libname_add_link_map (new, newname);
+	      _dl_libname_link_hash (newname);
+	    }
+
+	  /* This has to come after the potential memory allocation
+	     failure, so that we do not have to revert these changes
+	     on error.  */
+	  realname->map = new;
+	  _dl_libname_link_hash (realname);
+	}
+    }
 
   new->l_type = type;
   /* If we set the bit now since we know it is never used we avoid
@@ -144,7 +167,6 @@  _dl_new_object (char *realname, const char *libname, int type,
 #if NO_TLS_OFFSET != 0
   new->l_rw->l_tls_offset = NO_TLS_OFFSET;
 #endif
-  new->l_ns = nsid;
 
 #ifdef SHARED
   for (unsigned int cnt = 0; cnt < naudit; ++cnt)
@@ -194,13 +216,13 @@  _dl_new_object (char *realname, const char *libname, int type,
      point of view of the kernel, the main executable is the
      dynamic loader, and this would lead to a computation of the wrong
      origin.  */
-  if (realname[0] != '\0')
+  if (!(mode & __RTLD_VDSO) && realname->name[0] != '\0')
     {
-      size_t realname_len = strlen (realname) + 1;
+      size_t realname_len = strlen (realname->name) + 1;
       char *origin;
       char *cp;
 
-      if (realname[0] == '/')
+      if (realname->name[0] == '/')
 	{
 	  /* It is an absolute path.  Use it.  But we have to make a
 	     copy since we strip out the trailing slash.  */
@@ -250,7 +272,7 @@  _dl_new_object (char *realname, const char *libname, int type,
 	}
 
       /* Add the real file name.  */
-      cp = __mempcpy (cp, realname, realname_len);
+      cp = __mempcpy (cp, realname->name, realname_len);
 
       /* Now remove the filename and the slash.  Leave the slash if
 	 the name is something like "/foo".  */
@@ -267,11 +289,22 @@  _dl_new_object (char *realname, const char *libname, int type,
       new->l_origin = origin;
     }
 
+  if ((mode & __RTLD_OPENEXEC) && realname->name[0] == '\0')
+    _dl_libname_free (realname);
+
   return new;
 }
 
 void
 _dl_free_object (struct link_map_private *l)
 {
+  /* Deallocate the aliases of this link name.  */
+  for (struct libname *libname = l_libname (l); libname != NULL; )
+    {
+      _dl_libname_unlink_hash (libname);
+      struct libname *next = libname->next_link_map;
+      _dl_libname_free (libname);
+      libname = next;
+    }
   _dl_protmem_free (l, l->l_size);
 }
diff --git a/elf/dl-open.c b/elf/dl-open.c
index 9bd48826f9..d48fc5a095 100644
--- a/elf/dl-open.c
+++ b/elf/dl-open.c
@@ -38,6 +38,7 @@ 
 #include <gnu/lib-names.h>
 #include <dl-find_object.h>
 #include <dl-protmem.h>
+#include <dl-libname.h>
 
 #include <dl-prop.h>
 
@@ -79,7 +80,7 @@  struct dl_open_args
 static void __attribute__ ((noreturn))
 add_to_global_resize_failure (struct link_map_private *new)
 {
-  _dl_signal_error (ENOMEM, new->l_libname->name, NULL,
+  _dl_signal_error (ENOMEM, l_libname_last_alias (new), NULL,
 		    N_ ("cannot extend global scope"));
 }
 
@@ -737,7 +738,7 @@  dl_open_worker_begin (void *a)
   update_scopes (new);
 
   if (!_dl_find_object_update (new))
-    _dl_signal_error (ENOMEM, new->l_libname->name, NULL,
+    _dl_signal_error (ENOMEM, l_libname_last_alias (new), NULL,
 		      N_ ("cannot allocate address lookup data"));
 
   /* FIXME: It is unclear whether the order here is correct.
@@ -877,6 +878,12 @@  no more namespaces available for dlmopen()"));
     _dl_signal_error (EINVAL, file, NULL,
 		      N_("invalid target namespace in dlmopen()"));
 
+#ifndef SHARED
+  /* This completes initialization of the hash table.  */
+  if  (!_dl_libname_table_init (LM_ID_BASE))
+    _dl_signal_error (ENOMEM, NULL, NULL, N_("failed to initialize dlopen"));
+#endif
+
   struct dl_open_args args;
   args.file = file;
   args.mode = mode;
diff --git a/elf/dl-support.c b/elf/dl-support.c
index 459fb5c988..1b6ef0ba58 100644
--- a/elf/dl-support.c
+++ b/elf/dl-support.c
@@ -45,6 +45,7 @@ 
 #include <dl-find_object.h>
 #include <array_length.h>
 #include <dl-symbol-redir-ifunc.h>
+#include <dl-libname.h>
 
 extern char *__progname;
 char **_dl_argv = &__progname;	/* This is checked for some error messages.  */
@@ -80,6 +81,13 @@  const char *_dl_origin_path;
 /* Nonzero if runtime lookup should not update the .got/.plt.  */
 int _dl_bind_not;
 
+/* Used to populate _dl_main_map.l_name.  */
+static struct libname _dl_main_map_name =
+  {
+    .hash = 0x1505,		/* GNU hash of the empty string.  */
+    .name = { 0 },
+  };
+
 /* A dummy link map for the executable, used by dlopen to access the global
    scope.  We don't export any symbols ourselves, so this can be minimal.  */
 static struct link_map_private _dl_main_map =
@@ -91,7 +99,6 @@  static struct link_map_private _dl_main_map =
     },
     .l_real = &_dl_main_map,
     .l_ns = LM_ID_BASE,
-    .l_libname = &(struct libname_list) { .name = "", .dont_free = 1 },
     .l_searchlist =
       {
 	.r_list = &(struct link_map_private *) { &_dl_main_map },
@@ -279,6 +286,12 @@  _dl_aux_init (ElfW(auxv_t) *av)
 void
 _dl_non_dynamic_init (void)
 {
+  /* Set up of the namespace hash table is delayed until
+     _dl_libname_table_init is called from dlopen.  But l_name should
+     be initialized properly even if dlopen is never called.  */
+  _dl_main_map_name.map = &_dl_main_map;
+  _dl_main_map.l_public.l_name = _dl_main_map_name.name;
+
   _dl_main_map.l_origin = _dl_get_origin ();
   _dl_main_map.l_phdr = GL(dl_phdr);
   _dl_main_map.l_phnum = GL(dl_phnum);
diff --git a/elf/dl-version.c b/elf/dl-version.c
index faad3fea16..fc4bcff9d1 100644
--- a/elf/dl-version.c
+++ b/elf/dl-version.c
@@ -30,12 +30,9 @@  static inline struct link_map_private *
 __attribute ((always_inline))
 find_needed (const char *name, struct link_map_private *map)
 {
-  struct link_map_private *tmap;
-
-  for (tmap = GL(dl_ns)[map->l_ns]._ns_loaded; tmap != NULL;
-       tmap = l_next (tmap))
-    if (_dl_name_match_p (name, tmap))
-      return tmap;
+  struct link_map_private *tmap = _dl_lookup_map_unfiltered (map->l_ns, name);
+  if (tmap != NULL)
+    return tmap;
 
   struct dl_exception exception;
   _dl_exception_create_format
diff --git a/elf/pldd-xx.c b/elf/pldd-xx.c
index 36fcaff2fb..e6e30ef9e6 100644
--- a/elf/pldd-xx.c
+++ b/elf/pldd-xx.c
@@ -33,7 +33,6 @@  struct E(link_map)
   EW(Addr) l_prev;
   EW(Addr) l_real;
   Lmid_t l_ns;
-  EW(Addr) l_libname;
 };
 #if CLASS == __ELF_NATIVE_CLASS
 _Static_assert (offsetof (struct link_map, l_addr)
@@ -45,16 +44,20 @@  _Static_assert (offsetof (struct link_map, l_next)
 #endif
 
 
-struct E(libname_list)
+struct E(libname)
 {
-  EW(Addr) name;
-  EW(Addr) next;
+  EW(Addr) map;
+  EW(Addr) next_link_map;
+  EW(Addr) next_hash;
+  uint32_t gnu_hash;
+  char name[];
 };
 #if CLASS == __ELF_NATIVE_CLASS
-_Static_assert (offsetof (struct libname_list, name)
-		== offsetof (struct E(libname_list), name), "name");
-_Static_assert (offsetof (struct libname_list, next)
-		== offsetof (struct E(libname_list), next), "next");
+_Static_assert (offsetof (struct libname, name)
+		== offsetof (struct E(libname), name), "name");
+_Static_assert (offsetof (struct libname, next_link_map)
+		== offsetof (struct E(libname), next_link_map),
+		"next_link_map");
 #endif
 
 struct E(r_debug)
diff --git a/elf/pldd.c b/elf/pldd.c
index 454805dc17..0646b35272 100644
--- a/elf/pldd.c
+++ b/elf/pldd.c
@@ -31,6 +31,7 @@ 
 #include <scratch_buffer.h>
 
 #include <ldsodefs.h>
+#include <dl-libname.h>
 #include <version.h>
 
 /* Global variables.  */
diff --git a/elf/rtld.c b/elf/rtld.c
index 9ce6406c04..2b589994f2 100644
--- a/elf/rtld.c
+++ b/elf/rtld.c
@@ -38,6 +38,7 @@ 
 #include <dl-procinfo.h>
 #include <dl-prop.h>
 #include <dl-vdso.h>
+#include <dl-libname.h>
 #include <dl-vdso-setup.h>
 #include <tls.h>
 #include <stap-probe.h>
@@ -385,9 +386,6 @@  extern struct rtld_global_ro _rtld_local_ro
 static void dl_main (const ElfW(Phdr) *phdr, ElfW(Word) phnum,
 		     ElfW(Addr) *user_entry, ElfW(auxv_t) *auxv);
 
-/* These two variables cannot be moved into .data.rel.ro.  */
-static struct libname_list _dl_rtld_libname;
-
 /* Variable for statistics.  */
 RLTD_TIMING_DECLARE (relocate_time, static);
 RLTD_TIMING_DECLARE (load_time,     static, attribute_relro);
@@ -1180,10 +1178,9 @@  rtld_setup_main_map (struct link_map_private *main_map)
 	   dlopen call or DT_NEEDED entry, for something that wants to link
 	   against the dynamic linker as a shared library, will know that
 	   the shared object is already loaded.  */
-	_dl_rtld_libname.name = ((const char *) main_map->l_public.l_addr
-				 + ph->p_vaddr);
-	/* _dl_rtld_libname.next = NULL;	Already zero.  */
-	GLPM(dl_rtld_map).l_libname = &_dl_rtld_libname;
+	_dl_libname_add_alias (&GLPM (dl_rtld_map),
+			       (const char *) main_map->l_public.l_addr
+			       + ph->p_vaddr);
 
 	has_interp = true;
 	break;
@@ -1269,16 +1266,6 @@  rtld_setup_main_map (struct link_map_private *main_map)
     main_map->l_map_end = ~0;
   if (! main_map->l_text_end)
     main_map->l_text_end = ~0;
-  if (! GLPM(dl_rtld_map).l_libname && GLPM(dl_rtld_map).l_public.l_name)
-    {
-      /* We were invoked directly, so the program might not have a
-	 PT_INTERP.  */
-      _dl_rtld_libname.name = GLPM(dl_rtld_map).l_public.l_name;
-      /* _dl_rtld_libname.next = NULL;	Already zero.  */
-      GLPM(dl_rtld_map).l_libname =  &_dl_rtld_libname;
-    }
-  else
-    assert (GLPM(dl_rtld_map).l_libname); /* How else did we get here?  */
 
   return has_interp;
 }
@@ -1394,8 +1381,12 @@  dl_main (const ElfW(Phdr) *phdr,
       char *argv0 = NULL;
       char **orig_argv = _dl_argv;
 
-      /* Note the place where the dynamic linker actually came from.  */
-      GLPM(dl_rtld_map).l_public.l_name = rtld_progname;
+      /* Note the place where the dynamic linker actually came from.
+	 This sets l_name for the dynamic linker and must lead
+	 debuggers to the ld.so binary (so it cannot be the ABI path,
+	 in case this copy of ld.so is not installed in the correct
+	 place).  */
+      _dl_libname_add_alias (&GLPM (dl_rtld_map), rtld_progname);
 
       while (_dl_argc > 1)
 	if (! strcmp (_dl_argv[1], "--list"))
@@ -1580,8 +1571,8 @@  dl_main (const ElfW(Phdr) *phdr,
 	{
 	  RTLD_TIMING_VAR (start);
 	  rtld_timer_start (&start);
-	  _dl_map_object (NULL, rtld_progname, lt_executable, 0,
-			  __RTLD_OPENEXEC, LM_ID_BASE);
+	  _dl_map_new_object (NULL, rtld_progname, lt_executable, 0,
+			      __RTLD_OPENEXEC, LM_ID_BASE);
 	  rtld_timer_stop (&load_time, start);
 	}
 
@@ -1593,11 +1584,6 @@  dl_main (const ElfW(Phdr) *phdr,
 
       phdr = main_map->l_phdr;
       phnum = main_map->l_phnum;
-      /* We overwrite here a pointer to a malloc()ed string.  But since
-	 the malloc() implementation used at this point is the dummy
-	 implementations which has no real free() function it does not
-	 makes sense to free the old string first.  */
-      main_map->l_public.l_name = (char *) "";
       *user_entry = main_map->l_entry;
 
       /* Set bit indicating this is the main program map.  */
@@ -1635,9 +1621,14 @@  dl_main (const ElfW(Phdr) *phdr,
     {
       /* Create a link_map for the executable itself.
 	 This will be what dlopen on "" returns.  */
-      main_map = _dl_new_object ((char *) "", "", lt_executable, NULL,
-				 __RTLD_OPENEXEC, LM_ID_BASE);
-      assert (main_map != NULL);
+      {
+	struct libname *ln = _dl_libname_allocate ("");
+	if (ln == NULL ||
+	    (main_map = _dl_new_object (ln, "", lt_executable, NULL,
+					__RTLD_OPENEXEC, LM_ID_BASE))
+	    == NULL)
+	  _dl_fatal_printf ("Fatal glibc error: Cannot allocate link map\n");
+      }
       main_map->l_phdr = phdr;
       main_map->l_phnum = phnum;
       main_map->l_entry = *user_entry;
@@ -1670,20 +1661,8 @@  dl_main (const ElfW(Phdr) *phdr,
 
   /* If the current libname is different from the SONAME, add the
      latter as well.  */
-  {
-    const char *soname = l_soname (&GLPM(dl_rtld_map));
-    if (soname != NULL
-	&& strcmp (GLPM(dl_rtld_map).l_libname->name, soname) != 0)
-      {
-	static struct libname_list newname;
-	newname.name = soname;
-	newname.next = NULL;
-	newname.dont_free = 1;
+  _dl_libname_add_alias (&GLPM (dl_rtld_map), l_soname (&GLPM (dl_rtld_map)));
 
-	assert (GLPM(dl_rtld_map).l_libname->next == NULL);
-	GLPM(dl_rtld_map).l_libname->next = &newname;
-      }
-  }
   /* The ld.so must be relocated since otherwise loading audit modules
      will fail since they reuse the very same ld.so.  */
   assert (GLPM(dl_rtld_map).l_relocated);
@@ -1733,13 +1712,6 @@  dl_main (const ElfW(Phdr) *phdr,
 					    LM_ID_BASE);
   r->r_state = RT_CONSISTENT;
 
-  /* Put the link_map for ourselves on the chain so it can be found by
-     name.  Note that at this point the global chain of link maps contains
-     exactly one element, which is pointed to by dl_loaded.  */
-  if (! GLPM(dl_rtld_map).l_public.l_name)
-    /* If not invoked directly, the dynamic linker shared object file was
-       found by the PT_INTERP name.  */
-    GLPM(dl_rtld_map).l_public.l_name = (char *) GLPM(dl_rtld_map).l_libname->name;
   GLPM(dl_rtld_map).l_type = lt_library;
   main_map->l_public.l_next = &GLPM(dl_rtld_map).l_public;
   GLPM(dl_rtld_map).l_public.l_prev = &main_map->l_public;
@@ -2112,16 +2084,17 @@  dl_main (const ElfW(Phdr) *phdr,
 	       l; l = l_next (l)) {
 	    if (l->l_faked)
 	      /* The library was not found.  */
-	      _dl_printf ("\t%s => not found\n",  l->l_libname->name);
-	    else if (strcmp (l->l_libname->name, l->l_public.l_name) == 0)
+	      _dl_printf ("\t%s => not found\n",  l_libname_last_alias (l));
+	    else if (strcmp (l_libname_last_alias (l), l->l_public.l_name)
+		     == 0)
 	      /* Print vDSO like libraries without duplicate name.  Some
 		 consumers depend of this format.  */
-	      _dl_printf ("\t%s (0x%0*zx)\n", l->l_libname->name,
+	      _dl_printf ("\t%s (0x%0*zx)\n", l_libname_last_alias (l),
 			  (int) sizeof l->l_map_start * 2,
 			  (size_t) l->l_map_start);
 	    else
 	      _dl_printf ("\t%s => %s (0x%0*zx)\n",
-			  DSO_FILENAME (l->l_libname->name),
+			  DSO_FILENAME (l_libname_last_alias (l)),
 			  DSO_FILENAME (l->l_public.l_name),
 			  (int) sizeof l->l_map_start * 2,
 			  (size_t) l->l_map_start);
@@ -2295,17 +2268,7 @@  dl_main (const ElfW(Phdr) *phdr,
       {
 	struct link_map_private *l = main_map->l_initfini[i];
 
-	/* While we are at it, help the memory handling a bit.  We have to
-	   mark some data structures as allocated with the fake malloc()
-	   implementation in ld.so.  */
-	struct libname_list *lnp = l->l_libname->next;
-
-	while (__builtin_expect (lnp != NULL, 0))
-	  {
-	    lnp->dont_free = 1;
-	    lnp = lnp->next;
-	  }
-	/* Also allocated with the fake malloc().  */
+	/* Allocated with the fake malloc.  */
 	l->l_free_initfini = 0;
 
 	if (l != &GLPM(dl_rtld_map))
diff --git a/elf/setup-vdso.h b/elf/setup-vdso.h
index 387cef8cb3..efafda4732 100644
--- a/elf/setup-vdso.h
+++ b/elf/setup-vdso.h
@@ -29,9 +29,11 @@  setup_vdso (struct link_map_private *main_map __attribute__ ((unused)),
      better be, since it's read-only and so we couldn't relocate it).
      We just want our data structures to describe it as if we had just
      mapped and relocated it normally.  */
-  struct link_map_private *l = _dl_new_object ((char *) "", "", lt_library,
+  struct link_map_private *l = _dl_new_object (NULL, NULL, lt_library,
 					       NULL, __RTLD_VDSO, LM_ID_BASE);
-  if (__glibc_likely (l != NULL))
+  if (l == NULL)
+    _dl_fatal_printf ("Fatal glibc error: cannot allocate vDSO link map");
+  else
     {
       l->l_phdr = ((const void *) GLRO(dl_sysinfo_dso)
 		   + GLRO(dl_sysinfo_dso)->e_phoff);
@@ -80,15 +82,9 @@  setup_vdso (struct link_map_private *main_map __attribute__ ((unused)),
       l->l_local_scope[0]->r_list = &l->l_real;
 
       /* Now that we have the info handy, use the DSO image's soname
-	 so this object can be looked up by name.  */
-      {
-	const char *dsoname = l_soname (l);
-	if (dsoname != NULL)
-	  {
-	    l->l_libname->name = dsoname;
-	    l->l_public.l_name = (char *) dsoname;
-	  }
-      }
+	 so this object can be looked up by name.  Use "" as the dummy
+	 name.  */
+      _dl_libname_add_alias (l, l_soname (l) ?: "");
 
       /* Add the vDSO to the object list.  */
       _dl_add_to_namespace_list (l, LM_ID_BASE);
diff --git a/elf/sotruss-lib.c b/elf/sotruss-lib.c
index 09232b1a4a..2c47ffd290 100644
--- a/elf/sotruss-lib.c
+++ b/elf/sotruss-lib.c
@@ -27,7 +27,7 @@ 
 #include <sys/uio.h>
 
 #include <ldsodefs.h>
-
+#include <dl-libname.h>
 
 extern const char *__progname;
 extern const char *__progname_full;
@@ -173,8 +173,8 @@  la_objopen (struct link_map *map, Lmid_t lmid, uintptr_t *cookie)
 
   int result = 0;
   const char *print_name = NULL;
-  for (struct libname_list *l = l_private (map)->l_libname; l != NULL;
-       l = l->next)
+  for (struct libname *l = l_libname (l_private (map));
+       l != NULL; l = l->next_link_map)
     {
       if (print_name == NULL || (print_name[0] == '/' && l->name[0] != '/'))
 	print_name = l->name;
diff --git a/include/link.h b/include/link.h
index e57cf93efd..ac3d170954 100644
--- a/include/link.h
+++ b/include/link.h
@@ -46,7 +46,7 @@  extern unsigned int la_objopen (struct link_map *__map, Lmid_t __lmid,
 
 /* Some internal data structures of the dynamic linker used in the
    linker map.  We only provide forward declarations.  */
-struct libname_list;
+struct libname;
 struct r_found_version;
 struct r_search_path_elem;
 
@@ -173,7 +173,6 @@  struct link_map_private
     /* Number of the namespace this link map belongs to.  */
     Lmid_t l_ns;
 
-    struct libname_list *l_libname;
     /* Indexed pointers to dynamic section.
        [0,DT_NUM) are indexed by the processor-independent tags.
        [DT_NUM,DT_NUM+DT_THISPROCNUM) are indexed by the tag minus DT_LOPROC.
@@ -245,8 +244,6 @@  struct link_map_private
     unsigned int l_map_done:1;  /* of maps in _dl_close_worker. */
     unsigned int l_phdr_allocated:1; /* Nonzero if the data structure pointed
 					to by `l_phdr' is allocated.  */
-    unsigned int l_soname_added:1; /* Nonzero if the SONAME is for sure in
-				      the l_libname list.  */
     unsigned int l_faked:1;	/* Nonzero if this is a faked descriptor
 				   without associated file.  */
     unsigned int l_need_tls_init:1; /* Nonzero if GL(dl_init_static_tls)
diff --git a/sysdeps/generic/ldsodefs.h b/sysdeps/generic/ldsodefs.h
index c13a686267..f47cdcf47b 100644
--- a/sysdeps/generic/ldsodefs.h
+++ b/sysdeps/generic/ldsodefs.h
@@ -229,16 +229,7 @@  struct r_strlenpair
     size_t len;
   };
 
-
-/* A data structure for a simple single linked list of strings.  */
-struct libname_list
-  {
-    const char *name;		/* Name requested (before search).  */
-    struct libname_list *next;	/* Link to next name for this object.  */
-    int dont_free;		/* Flag whether this element should be freed
-				   if the object is not entirely unloaded.  */
-  };
-
+struct libname_table;		/* See dl-libname.c.  */
 
 /* DSO sort algorithm to use (check dl-sort-maps.c).  */
 enum dso_sort_algorithm
@@ -540,6 +531,9 @@  struct rtld_protmem
      _dlfo_loaded_mappings_version in dl-find_object.c.  */
   EXTERN struct dlfo_mappings_segment *_dlfo_loaded_mappings[2];
 
+  /* Per-namespace hash tables for library name lookup.  */
+  EXTERN struct libname_table *_dl_libnames[DL_NNS];
+
 #ifdef SHARED
 };
 #endif /* SHARED */
@@ -953,6 +947,11 @@  rtld_hidden_proto (_dl_catch_exception)
 struct link_map_private *_dl_lookup_map (Lmid_t nsid, const char *name)
      attribute_hidden;
 
+/* Like _dl_lookup_map, but returns l_removed and l_fake objects as well.  */
+struct link_map_private *_dl_lookup_map_unfiltered (Lmid_t nsid,
+						    const char *name)
+     attribute_hidden;
+
 /* Open the shared object NAME and map in its segments.
    LOADER's DT_RPATH is used in searching for NAME.
    If the object is already opened, returns its existing map.  */
@@ -1049,7 +1048,7 @@  extern void _dl_add_to_namespace_list (struct link_map_private *new,
 				       Lmid_t nsid) attribute_hidden;
 
 /* Allocate a `struct link_map_private' for a new object being loaded.  */
-struct link_map_private *_dl_new_object (char *realname,
+struct link_map_private *_dl_new_object (struct libname *realname,
 					 const char *libname, int type,
 					 struct link_map_private *loader,
 					 int mode, Lmid_t nsid)
@@ -1170,7 +1169,7 @@  const struct r_strlenpair *_dl_important_hwcaps (const char *prepend,
    and write a null pointer to *REALNAME.  If lookup suceeds, write a
    copy of the full name to *REALNAME (which has to be freed by the
    caller).  */
-bool _dl_load_cache_lookup (const char *name, char **realname)
+bool _dl_load_cache_lookup (const char *name, struct libname **realname)
   attribute_hidden __nonnull ((1, 2)) __attribute__ ((warn_unused_result));
 
 /* If the system does not support MAP_COPY we cannot leave the file open