diff --git a/elf/Makefile b/elf/Makefile
index afec7be084..feeaffe533 100644
--- a/elf/Makefile
+++ b/elf/Makefile
@@ -443,6 +443,7 @@ tests += \
   tst-p_align3 \
   tst-relsort1 \
   tst-ro-dynamic \
+  tst-rtld-nomem \
   tst-rtld-run-static \
   tst-single_threaded \
   tst-single_threaded-pthread \
diff --git a/elf/dl-protmem_bootstrap.h b/elf/dl-protmem_bootstrap.h
new file mode 100644
index 0000000000..2ba0973d07
--- /dev/null
+++ b/elf/dl-protmem_bootstrap.h
@@ -0,0 +1,29 @@
+/* Bootstrap allocation for the protected memory area.
+   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-early_mmap.h>
+
+/* Return a pointer to the protected memory area, or NULL if
+   allocation fails.  This function is called before self-relocation,
+   and the system call needs to be inlined for (most)
+   HIDDEN_VAR_NEEDS_DYNAMIC_RELOC targets.  */
+static inline __attribute__ ((always_inline)) struct rtld_protmem *
+_dl_protmem_bootstrap (void)
+{
+  return _dl_early_mmap (sizeof (struct rtld_protmem));
+}
diff --git a/elf/rtld.c b/elf/rtld.c
index 733dbf46a3..4abede1bab 100644
--- a/elf/rtld.c
+++ b/elf/rtld.c
@@ -53,6 +53,7 @@
 #include <dl-find_object.h>
 #include <dl-audit-check.h>
 #include <dl-call_tls_init_tp.h>
+#include <dl-protmem_bootstrap.h>
 
 #include <assert.h>
 
@@ -345,8 +346,6 @@ struct rtld_global _rtld_global =
 extern struct rtld_global _rtld_local
     __attribute__ ((alias ("_rtld_global"), visibility ("hidden")));
 
-struct rtld_protmem _rtld_protmem;
-
 /* This variable is similar to _rtld_local, but all values are
    read-only after relocation.  */
 struct rtld_global_ro _rtld_global_ro attribute_relro =
@@ -418,7 +417,7 @@ static ElfW(Addr) _dl_start_final (void *arg);
 #else
 struct dl_start_final_info
 {
-  struct link_map_private l;
+  struct rtld_protmem *protmem;
   RTLD_TIMING_VAR (start_time);
 };
 static ElfW(Addr) _dl_start_final (void *arg,
@@ -453,6 +452,14 @@ _dl_start_final (void *arg, struct dl_start_final_info *info)
 {
   ElfW(Addr) start_addr;
 
+#ifndef DONT_USE_BOOTSTRAP_MAP
+  GLRO (dl_protmem) = info->protmem;
+#endif
+
+  /* Delayed error reporting after relocation processing.  */
+  if (GLRO (dl_protmem) == NULL)
+    _dl_fatal_printf ("Fatal glibc error: Cannot allocate link map\n");
+
   __rtld_malloc_init_stubs ();
 
   /* Do not use an initializer for these members because it would
@@ -477,15 +484,6 @@ _dl_start_final (void *arg, struct dl_start_final_info *info)
 #endif
 
   /* Transfer data about ourselves to the permanent link_map structure.  */
-#ifndef DONT_USE_BOOTSTRAP_MAP
-  GLPM(dl_rtld_map).l_public.l_addr = info->l.l_public.l_addr;
-  GLPM(dl_rtld_map).l_public.l_ld = info->l.l_public.l_ld;
-  GLPM(dl_rtld_map).l_ld_readonly = info->l.l_ld_readonly;
-  memcpy (GLPM(dl_rtld_map).l_info, info->l.l_info,
-	  sizeof GLPM(dl_rtld_map).l_info);
-  GLPM(dl_rtld_map).l_mach = info->l.l_mach;
-  GLPM(dl_rtld_map).l_relocated = 1;
-#endif
   _dl_setup_hash (&GLPM(dl_rtld_map));
   GLPM(dl_rtld_map).l_real = &GLPM(dl_rtld_map);
   GLPM(dl_rtld_map).l_map_start = (ElfW(Addr)) &__ehdr_start;
@@ -529,44 +527,60 @@ _dl_start (void *arg)
   rtld_timer_start (&info.start_time);
 #endif
 
-  /* Partly clean the `bootstrap_map' structure up.  Don't use
-     `memset' since it might not be built in or inlined and we cannot
-     make function calls at this point.  Use '__builtin_memset' if we
-     know it is available.  We do not have to clear the memory if we
-     do not have to use the temporary bootstrap_map.  Global variables
-     are initialized to zero by default.  */
-#ifndef DONT_USE_BOOTSTRAP_MAP
-# ifdef HAVE_BUILTIN_MEMSET
-  __builtin_memset (bootstrap_map.l_info, '\0', sizeof (bootstrap_map.l_info));
-# else
-  for (size_t cnt = 0;
-       cnt < sizeof (bootstrap_map.l_info) / sizeof (bootstrap_map.l_info[0]);
-       ++cnt)
-    bootstrap_map.l_info[cnt] = 0;
-# endif
+  struct rtld_protmem *protmem = _dl_protmem_bootstrap ();
+  bool protmem_failed = protmem == NULL;
+  if (protmem_failed)
+    {
+      /* Allocate some space for a stub protected memory area on the
+	 stack, to get to the point when we can report the error.  */
+      protmem = alloca (sizeof (*protmem));
+
+      /* Partly clean the `bootstrap_map' structure up.  Don't use
+	 `memset' since it might not be built in or inlined and we
+	 cannot make function calls at this point.  Use
+	 '__builtin_memset' if we know it is available.  */
+#ifdef HAVE_BUILTIN_MEMSET
+      __builtin_memset (protmem->_dl_rtld_map.l_info,
+			'\0', sizeof (protmem->_dl_rtld_map.l_info));
+#else
+      for (size_t i = 0; i < array_length (protmem->_dl_rtld_map.l_info); ++i)
+	protmem->_dl_rtld_map.l_info[i] = NULL;
 #endif
+    }
 
   /* Figure out the run-time load address of the dynamic linker itself.  */
-  bootstrap_map.l_public.l_addr = elf_machine_load_address ();
+  protmem->_dl_rtld_map.l_public.l_addr = elf_machine_load_address ();
 
   /* Read our own dynamic section and fill in the info array.  */
-  bootstrap_map.l_public.l_ld
-    = (void *) bootstrap_map.l_public.l_addr + elf_machine_dynamic ();
-  bootstrap_map.l_ld_readonly = DL_RO_DYN_SECTION;
-  elf_get_dynamic_info (&bootstrap_map, true, false);
+  protmem->_dl_rtld_map.l_public.l_ld
+    = ((void *) protmem->_dl_rtld_map.l_public.l_addr
+       + elf_machine_dynamic ());
+  protmem->_dl_rtld_map.l_ld_readonly = DL_RO_DYN_SECTION;
+  elf_get_dynamic_info (&protmem->_dl_rtld_map, true, false);
 
 #ifdef ELF_MACHINE_BEFORE_RTLD_RELOC
-  ELF_MACHINE_BEFORE_RTLD_RELOC (&bootstrap_map, bootstrap_map.l_info);
+  ELF_MACHINE_BEFORE_RTLD_RELOC (&protmem->_dl_rtld_map,
+				 protmem->_dl_rtld_map.l_info);
 #endif
 
-  if (bootstrap_map.l_public.l_addr)
+  if (protmem->_dl_rtld_map.l_public.l_addr)
     {
       /* Relocate ourselves so we can do normal function calls and
 	 data access using the global offset table.  */
 
-      ELF_DYNAMIC_RELOCATE (&bootstrap_map, NULL, 0, 0, 0);
+      ELF_DYNAMIC_RELOCATE (&protmem->_dl_rtld_map, NULL, 0, 0, 0);
     }
-  bootstrap_map.l_relocated = 1;
+  protmem->_dl_rtld_map.l_relocated = 1;
+
+  /* Communicate the original mmap failure to _dl_start_final.  */
+  if (protmem_failed)
+    protmem = NULL;
+
+#ifdef DONT_USE_BOOTSTRAP_MAP
+  GLRO (dl_protmem) = protmem;
+#else
+  info.protmem = protmem;
+#endif
 
   /* Please note that we don't allow profiling of this object and
      therefore need not test whether we have to allocate the array
@@ -1035,7 +1049,7 @@ ERROR: audit interface '%s' requires version %d (maximum supported version %d);
   else
     *last_audit = (*last_audit)->next = &newp->ifaces;
 
-  /* The dynamic linker link map is statically allocated, so the
+  /* The dynamic linker link map is allocated separately, so the
      cookie in _dl_new_object has not happened.  */
   link_map_audit_state (&GLPM (dl_rtld_map), GLRO (dl_naudit))->cookie
     = (intptr_t) &GLPM (dl_rtld_map);
diff --git a/elf/tst-rtld-nomem.c b/elf/tst-rtld-nomem.c
new file mode 100644
index 0000000000..37dbfe2903
--- /dev/null
+++ b/elf/tst-rtld-nomem.c
@@ -0,0 +1,177 @@
+/* Test that out-of-memory during early ld.so startup reports an error.
+   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/>.  */
+
+/* This test invokes execve with increasing RLIMIT_AS limits, to
+   trigger the early _dl_protmem_bootstrap memory allocation failure
+   and check that a proper error is reported for it.  */
+
+#include <errno.h>
+#include <stdbool.h>
+#include <stddef.h>
+#include <stdio.h>
+#include <string.h>
+#include <support/check.h>
+#include <support/support.h>
+#include <support/xunistd.h>
+#include <sys/resource.h>
+#include <sys/wait.h>
+#include <unistd.h>
+
+static int
+do_test (void)
+{
+  long int page_size = sysconf (_SC_PAGE_SIZE);
+  TEST_VERIFY (page_size > 0);
+
+  struct rlimit rlim;
+  TEST_COMPARE (getrlimit (RLIMIT_AS, &rlim), 0);
+
+  /* Reduced once we encounter success.  */
+  int kb_limit = 2048;
+
+  /* Exit status in case of test error.  */
+  enum { unexpected_error = 17 };
+
+  /* Used to verify that at least one execve crash is encountered.
+     This is how exexcve reports late memory allocation failures due
+     to rlimit.  */
+  bool crash_seen = false;
+
+  /* Set to true if the early out-of-memory error message is
+     encountered.  */
+  bool oom_error_seen = false;
+
+  /* Set to true once success (the usage message) is encountered.
+     This is expected to happen only after oom_error_seen turns true,
+     otherwise the rlimit does not work.  */
+  bool success_seen = false;
+
+  /* Try increasing rlimits.  The kernel rounds down to page sizes, so
+     try only page size increments.  */
+  for (int kb = 128; kb <= kb_limit; kb += page_size / 1024)
+    {
+      printf ("info: trying %d KiB\n", kb);
+
+      int pipe_stdout[2];
+      xpipe (pipe_stdout);
+      int pipe_stderr[2];
+      xpipe (pipe_stderr);
+
+      pid_t pid = xfork ();
+      if (pid == 0)
+        {
+          /* Restrict address space for the ld.so invocation.  */
+          rlim.rlim_cur = kb * 1024;
+          int ret = setrlimit (RLIMIT_AS, &rlim);
+          TEST_COMPARE (ret, 0);
+          if (ret != 0)
+            _exit (unexpected_error);
+
+          /* Redirect output for capture.  */
+          TEST_COMPARE (dup2 (pipe_stdout[1], STDOUT_FILENO),
+                        STDOUT_FILENO);
+          TEST_COMPARE (dup2 (pipe_stderr[1], STDERR_FILENO),
+                        STDERR_FILENO);
+
+          /* Try to invoke ld.so with the resource limit in place.  */
+          char ldso[] = "ld.so";
+          char *const argv[] = { ldso, NULL };
+          execve (support_objdir_elf_ldso, argv, &argv[1]);
+          TEST_COMPARE (errno, ENOMEM);
+          _exit (unexpected_error);
+        }
+
+      int status;
+      xwaitpid (pid, &status, 0);
+
+      xclose (pipe_stdout[1]);
+      xclose (pipe_stderr[1]);
+
+      /* No output on stdout.  */
+      char actual[1024];
+      ssize_t count = read (pipe_stdout[0], actual, sizeof (actual));
+      if (count < 0)
+        FAIL_EXIT1 ("read stdout: %m");
+      TEST_COMPARE_BLOB ("", 0, actual, count);
+
+      /* Read the standard error output.  */
+      count = read (pipe_stderr[0], actual, sizeof (actual));
+      if (count < 0)
+        FAIL_EXIT1 ("read stderr: %m");
+
+      if (WIFEXITED (status) && WEXITSTATUS (status) == 1)
+        {
+          TEST_VERIFY (oom_error_seen);
+          static const char expected[] = "\
+ld.so: missing program name\n\
+Try 'ld.so --help' for more information.\n\
+";
+          TEST_COMPARE_BLOB (expected, strlen (expected), actual, count);
+          if (!success_seen)
+            {
+              puts ("info: first success");
+              /* Four more tries with increasing rlimit, to catch
+                 potential secondary crashes.  */
+              kb_limit = kb + page_size / 1024 * 4;
+            }
+          success_seen = true;
+          continue;
+        }
+      if (WIFEXITED (status) && WEXITSTATUS (status) == 127)
+        {
+          TEST_VERIFY (crash_seen);
+          TEST_VERIFY (!success_seen);
+          static const char expected[] =
+            "Fatal glibc error: Cannot allocate link map\n";
+          TEST_COMPARE_BLOB (expected, strlen (expected), actual, count);
+          if (!oom_error_seen)
+            puts ("info: first memory allocation error");
+          oom_error_seen = true;
+          continue;
+        }
+
+      TEST_VERIFY (!success_seen);
+      TEST_VERIFY (!oom_error_seen);
+
+      if (WIFEXITED (status))
+        {
+          /* Unexpected regular exit status.  */
+          TEST_COMPARE (WIFEXITED (status), 1);
+          TEST_COMPARE_BLOB ("", 0, actual, count);
+        }
+      else if (WIFSIGNALED (status) && WTERMSIG (status) == SIGSEGV)
+        {
+          /* Very early out of memory.  No output expected.  */
+          TEST_COMPARE_BLOB ("", 0, actual, count);
+          if (!crash_seen)
+            puts ("info: first expected crash observed");
+          crash_seen = true;
+        }
+      else
+        {
+          /* Unexpected status.  */
+          printf ("error: unexpected exit status %d\n", status);
+          support_record_failure ();
+          TEST_COMPARE_BLOB ("", 0, actual, count);
+        }
+    }
+
+  return 0;
+}
+
+#include <support/test-driver.c>
diff --git a/sysdeps/generic/dl-early_mmap.h b/sysdeps/generic/dl-early_mmap.h
new file mode 100644
index 0000000000..33dd8c2f68
--- /dev/null
+++ b/sysdeps/generic/dl-early_mmap.h
@@ -0,0 +1,35 @@
+/* Early anonymous mmap for ld.so, before self-relocation.  Generic version.
+   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_EARLY_MMAP_H
+#define DL_EARLY_MMAP_H
+
+/* The generic version assumes that regular mmap works.  It returns
+   NULL on failure.  */
+static inline void *
+_dl_early_mmap (size_t size)
+{
+  void *ret = __mmap (NULL, size, PROT_READ | PROT_WRITE,
+                      MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
+  if (ret == MAP_FAILED)
+    return NULL;
+  else
+    return ret;
+}
+
+#endif /* DL_EARLY_MMAP_H */
diff --git a/sysdeps/generic/ldsodefs.h b/sysdeps/generic/ldsodefs.h
index 0015fcf993..e8f7c8b70b 100644
--- a/sysdeps/generic/ldsodefs.h
+++ b/sysdeps/generic/ldsodefs.h
@@ -530,12 +530,11 @@ struct rtld_protmem
   /* Structure describing the dynamic linker itself.  */
   EXTERN struct link_map_private _dl_rtld_map;
 };
-extern struct rtld_protmem _rtld_protmem attribute_hidden;
 #endif /* SHARED */
 
 /* GLPM(FIELD) denotes the FIELD in the protected memory area.  */
 #ifdef SHARED
-# define GLPM(name) _rtld_protmem._##name
+# define GLPM(name) GLRO (dl_protmem)->_##name
 #else
 # define GLPM(name) _##name
 #endif
@@ -673,6 +672,9 @@ struct rtld_global_ro
   EXTERN enum dso_sort_algorithm _dl_dso_sort_algo;
 
 #ifdef SHARED
+  /* Pointer to the protected memory area.  */
+  EXTERN struct rtld_protmem *_dl_protmem;
+
   /* We add a function table to _rtld_global which is then used to
      call the function instead of going through the PLT.  The result
      is that we can avoid exporting the functions and we do not jump
diff --git a/sysdeps/mips/Makefile b/sysdeps/mips/Makefile
index d770e59fc9..551612cb1e 100644
--- a/sysdeps/mips/Makefile
+++ b/sysdeps/mips/Makefile
@@ -23,6 +23,12 @@ ASFLAGS-.o += $(pie-default)
 ASFLAGS-.op += $(pie-default)
 
 ifeq ($(subdir),elf)
+# _dl_start performs a system call before self-relocation, to allocate
+# the link map for ld.so itself.  This involves a direct function
+# call.  Build rtld.c in MIPS32 mode, so that this function call does
+# not require a run-time relocation.
+CFLAGS-rtld.c += -mno-mips16
+
 ifneq ($(o32-fpabi),)
 tests += tst-abi-interlink
 
diff --git a/sysdeps/unix/sysv/linux/dl-early_allocate.c b/sysdeps/unix/sysv/linux/dl-early_allocate.c
index 9d5976a3b7..c688097d6f 100644
--- a/sysdeps/unix/sysv/linux/dl-early_allocate.c
+++ b/sysdeps/unix/sysv/linux/dl-early_allocate.c
@@ -29,7 +29,7 @@
 #include <unistd.h>
 
 #include <brk_call.h>
-#include <mmap_call.h>
+#include <dl-early_mmap.h>
 
 /* Defined in brk.c.  */
 extern void *__curbrk;
@@ -63,20 +63,7 @@ _dl_early_allocate (size_t size)
      unfortunate ASLR layout decisions and kernel bugs, particularly
      for static PIE.  */
   if (result == NULL)
-    {
-      long int ret;
-      int prot = PROT_READ | PROT_WRITE;
-      int flags = MAP_PRIVATE | MAP_ANONYMOUS;
-#ifdef __NR_mmap2
-      ret = MMAP_CALL_INTERNAL (mmap2, 0, size, prot, flags, -1, 0);
-#else
-      ret = MMAP_CALL_INTERNAL (mmap, 0, size, prot, flags, -1, 0);
-#endif
-      if (INTERNAL_SYSCALL_ERROR_P (ret))
-        result = NULL;
-      else
-        result = (void *) ret;
-    }
+    result = _dl_early_mmap (size);
 
   return result;
 }
diff --git a/sysdeps/unix/sysv/linux/dl-early_mmap.h b/sysdeps/unix/sysv/linux/dl-early_mmap.h
new file mode 100644
index 0000000000..1d83daa6a6
--- /dev/null
+++ b/sysdeps/unix/sysv/linux/dl-early_mmap.h
@@ -0,0 +1,41 @@
+/* Early anonymous mmap for ld.so, before self-relocation.  Linux version.
+   Copyright (C) 2022-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_EARLY_MMAP_H
+#define DL_EARLY_MMAP_H
+
+#include <mmap_call.h>
+
+static inline __attribute__ ((always_inline)) void *
+_dl_early_mmap (size_t size)
+{
+  long int ret;
+  int prot = PROT_READ | PROT_WRITE;
+  int flags = MAP_PRIVATE | MAP_ANONYMOUS;
+#ifdef __NR_mmap2
+  ret = MMAP_CALL_INTERNAL (mmap2, 0, size, prot, flags, -1, 0);
+#else
+  ret = MMAP_CALL_INTERNAL (mmap, 0, size, prot, flags, -1, 0);
+#endif
+  if (INTERNAL_SYSCALL_ERROR_P (ret))
+    return NULL;
+  else
+    return (void *) ret;
+}
+
+#endif /* DL_EARLY_MMAP_H */
