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..bf6d621f73
--- /dev/null
+++ b/elf/dl-libname.c
@@ -0,0 +1,275 @@
+/* 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 (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
+        && (ln->map->l_public.l_prev != NULL
+            || ln->map->l_public.l_next != NULL))
+      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
