Paul Eggert wrote:
> > 1) change the default back from posix_memalign to mmap,
> > except on OpenBSD.
> > 2) since the "list" is not going away, use a different implementation
> > for it: either prev/next fields (doubly-linked list) or a hash-set
> > container.
>
> Although I wouldn't bother doing either (1) or (2) I don't object to
> doing (1) if (2) is also done, given that CVS is the only user.
Done through the attached patches.
0001 fixes an embarrassing mistake, and includes a correction of the
invocation of VirtualFree. With these fixes, the results table looks
very reasonable:
b c d e f
glibc 176% 101% 175% --- ---
musl libc 198% 101% 197% --- ---
macOS 190% 100% 195% --- ---
FreeBSD 190% 100% 380% --- ---
NetBSD 185% 101% 379% --- ---
OpenBSD 177% 101% 101% --- ---
AIX 177% 101% 176% --- ---
Solaris 11.4 176% 101% 175% --- ---
Cygwin 181% 100% 181% --- ---
native Windows 184% --- --- 180% 100%
Android 182% 101% 181% --- ---
0002 replaces the hand-written ad-hoc linked list with a use of the hash-map
container, which 'void *' as key type and 'void *' as value type. This is
a real simplification: The size of the file shrinks by more than 30 lines.
0003 adds the scalability unit test.
0004 changes the default implementation by considering the table above:
mmap or VirtualAlloc, except on OpenBSD. Thus eliminating the big waste
of memory that the use of posix_memalign introduced a couple of days ago.
Bruno
>From 8bca9f3cc8706785632b093e3e6f00b7df7b35f8 Mon Sep 17 00:00:00 2001
From: Bruno Haible <[email protected]>
Date: Sat, 13 Sep 2025 22:36:06 +0200
Subject: [PATCH 1/4] pagealign_alloc: Fix crashes (regression 2025-09-11).
* lib/pagealign_alloc.c (pagealign_alloc, pagealign_free): Add missing
'break' statements. For PA_IMPL_VIRTUAL_ALLOC, don't use new_memnode and
get_memnode.
---
ChangeLog | 7 +++++++
lib/pagealign_alloc.c | 12 +++++++-----
2 files changed, 14 insertions(+), 5 deletions(-)
diff --git a/ChangeLog b/ChangeLog
index f53d4204fe..d585d51c49 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,10 @@
+2025-09-13 Bruno Haible <[email protected]>
+
+ pagealign_alloc: Fix crashes (regression 2025-09-11).
+ * lib/pagealign_alloc.c (pagealign_alloc, pagealign_free): Add missing
+ 'break' statements. For PA_IMPL_VIRTUAL_ALLOC, don't use new_memnode and
+ get_memnode.
+
2025-09-13 Paul Eggert <[email protected]>
endian: port to Solaris 11.4 and macOS 15
diff --git a/lib/pagealign_alloc.c b/lib/pagealign_alloc.c
index 28aca9baf5..0e2ccdf7e0 100644
--- a/lib/pagealign_alloc.c
+++ b/lib/pagealign_alloc.c
@@ -61,7 +61,7 @@ typedef union
For each memory region, we store the original pointer returned by
malloc(). */
void *pointer;
- /* For PA_IMPL_MMAP, PA_IMPL_VIRTUAL_ALLOC:
+ /* For PA_IMPL_MMAP:
For each memory region, we store its size. */
size_t size;
} info_t;
@@ -215,9 +215,7 @@ pagealign_alloc (size_t size)
errno = ENOMEM;
return NULL;
}
- info_t info;
- info.size = size;
- new_memnode (ret, info);
+ break;
#else
errno = ENOSYS;
return NULL;
@@ -261,6 +259,7 @@ pagealign_free (void *aligned_ptr)
#if HAVE_SYS_MMAN_H
if (munmap (aligned_ptr, get_memnode (aligned_ptr).size) < 0)
error (EXIT_FAILURE, errno, "Failed to unmap memory");
+ break;
#else
abort ();
#endif
@@ -268,6 +267,7 @@ pagealign_free (void *aligned_ptr)
case PA_IMPL_POSIX_MEMALIGN:
#if HAVE_POSIX_MEMALIGN
free (aligned_ptr);
+ break;
#else
abort ();
#endif
@@ -277,6 +277,7 @@ pagealign_free (void *aligned_ptr)
/* Documentation:
<https://learn.microsoft.com/en-us/cpp/c-runtime-library/reference/aligned-free> */
_aligned_free (aligned_ptr);
+ break;
#else
abort ();
#endif
@@ -285,8 +286,9 @@ pagealign_free (void *aligned_ptr)
#if defined _WIN32 && !defined __CYGWIN__
/* Documentation:
<https://learn.microsoft.com/en-us/windows/win32/api/memoryapi/nf-memoryapi-virtualfree> */
- if (!VirtualFree (aligned_ptr, get_memnode (aligned_ptr).size, MEM_RELEASE))
+ if (!VirtualFree (aligned_ptr, 0, MEM_RELEASE))
error (EXIT_FAILURE, 0, "Failed to free memory");
+ break;
#else
abort ();
#endif
--
2.50.1
>From 9437102692cb2fc6f0f9a48753c5ab3f81511ef7 Mon Sep 17 00:00:00 2001
From: Bruno Haible <[email protected]>
Date: Sun, 14 Sep 2025 00:24:21 +0200
Subject: [PATCH 2/4] pagealign_alloc: Fix scalability problem.
Reported by Harry Sintonen <[email protected]> in
<https://lists.gnu.org/archive/html/bug-gnulib/2025-09/msg00108.html>.
* lib/pagealign_alloc.c: Include gl_xmap.h, gl_hash_map.h. Don't include
xalloc.h.
(info_t, memnode_t, struct memnode_s): Remove types.
(memnode_table): Remove variable.
(new_memnode, get_memnode): Remove functions.
(page_info_map): New variable.
(pagealign_alloc): Use gl_map_put instead of new_memnode.
(pagealign_free): Use gl_map_getremove instead of get_memnode.
* modules/pagealign_alloc (Depends-on): Add xmap, hash-map. Remove
xalloc.
---
ChangeLog | 16 +++++++
lib/pagealign_alloc.c | 104 +++++++++++++---------------------------
modules/pagealign_alloc | 3 +-
3 files changed, 51 insertions(+), 72 deletions(-)
diff --git a/ChangeLog b/ChangeLog
index d585d51c49..e0ab0ed821 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,19 @@
+2025-09-13 Bruno Haible <[email protected]>
+
+ pagealign_alloc: Fix scalability problem.
+ Reported by Harry Sintonen <[email protected]> in
+ <https://lists.gnu.org/archive/html/bug-gnulib/2025-09/msg00108.html>.
+ * lib/pagealign_alloc.c: Include gl_xmap.h, gl_hash_map.h. Don't include
+ xalloc.h.
+ (info_t, memnode_t, struct memnode_s): Remove types.
+ (memnode_table): Remove variable.
+ (new_memnode, get_memnode): Remove functions.
+ (page_info_map): New variable.
+ (pagealign_alloc): Use gl_map_put instead of new_memnode.
+ (pagealign_free): Use gl_map_getremove instead of get_memnode.
+ * modules/pagealign_alloc (Depends-on): Add xmap, hash-map. Remove
+ xalloc.
+
2025-09-13 Bruno Haible <[email protected]>
pagealign_alloc: Fix crashes (regression 2025-09-11).
diff --git a/lib/pagealign_alloc.c b/lib/pagealign_alloc.c
index 0e2ccdf7e0..332306bd41 100644
--- a/lib/pagealign_alloc.c
+++ b/lib/pagealign_alloc.c
@@ -39,7 +39,8 @@
#endif
#include <error.h>
-#include "xalloc.h"
+#include "gl_xmap.h"
+#include "gl_hash_map.h"
#include "gettext.h"
#define _(msgid) dgettext (GNULIB_TEXT_DOMAIN, msgid)
@@ -55,68 +56,14 @@
/* Implementation of pagealign_alloc. */
pagealign_impl_t pagealign_impl;
-typedef union
-{
- /* For PA_IMPL_MALLOC:
- For each memory region, we store the original pointer returned by
- malloc(). */
- void *pointer;
- /* For PA_IMPL_MMAP:
+/* Map:
+ For PA_IMPL_MALLOC:
+ aligned_ptr -> void *.
+ For each memory region, we store the original pointer returned by malloc().
+ For PA_IMPL_MMAP:
+ aligned_ptr -> size_t.
For each memory region, we store its size. */
- size_t size;
-} info_t;
-
-
-/* For PA_IMPL_MALLOC, PA_IMPL_MMAP. */
-
-/* A simple linked list of allocated memory regions. It is probably not the
- most efficient way to store these, but anyway... */
-typedef struct memnode_s memnode_t;
-struct memnode_s
-{
- void *aligned_ptr;
- info_t info;
- memnode_t *next;
-};
-
-/* The list of currently allocated memory regions. */
-static memnode_t *memnode_table = NULL;
-
-static void
-new_memnode (void *aligned_ptr, info_t info)
-{
- memnode_t *new_node = XMALLOC (memnode_t);
- new_node->aligned_ptr = aligned_ptr;
- new_node->info = info;
- new_node->next = memnode_table;
- memnode_table = new_node;
-}
-
-/* Dispose of the memnode containing a map for the ALIGNED_PTR in question
- and return the content of the node's INFO field. */
-static info_t
-get_memnode (void *aligned_ptr)
-{
- info_t ret;
- memnode_t *c;
- memnode_t **p_next = &memnode_table;
-
- for (c = *p_next; c != NULL; p_next = &c->next, c = c->next)
- if (c->aligned_ptr == aligned_ptr)
- break;
-
- if (c == NULL)
- /* An attempt to free untracked memory. A wrong pointer was passed
- to pagealign_free(). */
- abort ();
-
- /* Remove this entry from the list, save the return value, and free it. */
- *p_next = c->next;
- ret = c->info;
- free (c);
-
- return ret;
-}
+static gl_map_t page_info_map;
/* Returns the default implementation. */
@@ -158,9 +105,10 @@ pagealign_alloc (size_t size)
}
ret = (char *) unaligned_ptr
+ ((- (uintptr_t) unaligned_ptr) & (pagesize - 1));
- info_t info;
- info.pointer = unaligned_ptr;
- new_memnode (ret, info);
+ if (page_info_map == NULL)
+ page_info_map =
+ gl_map_create_empty (GL_HASH_MAP, NULL, NULL, NULL, NULL);
+ gl_map_put (page_info_map, ret, unaligned_ptr);
}
break;
@@ -170,9 +118,10 @@ pagealign_alloc (size_t size)
MAP_ANONYMOUS | MAP_PRIVATE, -1, 0);
if (ret == MAP_FAILED)
return NULL;
- info_t info;
- info.size = size;
- new_memnode (ret, info);
+ if (page_info_map == NULL)
+ page_info_map =
+ gl_map_create_empty (GL_HASH_MAP, NULL, NULL, NULL, NULL);
+ gl_map_put (page_info_map, ret, (void *) (uintptr_t) size);
break;
#else
errno = ENOSYS;
@@ -252,13 +201,26 @@ pagealign_free (void *aligned_ptr)
switch (impl)
{
case PA_IMPL_MALLOC:
- free (get_memnode (aligned_ptr).pointer);
+ {
+ const void *value;
+ if (page_info_map == NULL
+ || !gl_map_getremove (page_info_map, aligned_ptr, &value))
+ abort ();
+ void *unaligned_ptr = (void *) value;
+ free (unaligned_ptr);
+ }
break;
case PA_IMPL_MMAP:
#if HAVE_SYS_MMAN_H
- if (munmap (aligned_ptr, get_memnode (aligned_ptr).size) < 0)
- error (EXIT_FAILURE, errno, "Failed to unmap memory");
+ {
+ const void *value;
+ if (page_info_map == NULL
+ || !gl_map_getremove (page_info_map, aligned_ptr, &value))
+ abort ();
+ if (munmap (aligned_ptr, (size_t) (uintptr_t) value) < 0)
+ error (EXIT_FAILURE, errno, "Failed to unmap memory");
+ }
break;
#else
abort ();
diff --git a/modules/pagealign_alloc b/modules/pagealign_alloc
index 6570226665..22f8373c70 100644
--- a/modules/pagealign_alloc
+++ b/modules/pagealign_alloc
@@ -14,9 +14,10 @@ getpagesize
gettext-h
gnulib-i18n
stdlib-h
-xalloc
unistd-h
stdint-h
+xmap
+hash-map
configure.ac:
gl_PAGEALIGN_ALLOC
--
2.50.1
From 7f4d4edc36cd358836211021f6b4b6e3e9ce4d95 Mon Sep 17 00:00:00 2001
From: Bruno Haible <[email protected]>
Date: Sun, 14 Sep 2025 00:25:12 +0200
Subject: [PATCH 3/4] pagealign_alloc: Add unit test for scalability.
* tests/test-pagealign_alloc.c: New file.
* modules/pagealign_alloc-tests (Files): Add it.
(Depends-on): Add xalloc.
(configure.ac): Check for alarm().
(Makefile.am): Arrange to compile and run test-pagealign_alloc.
---
ChangeLog | 7 +++
modules/pagealign_alloc-tests | 6 +++
tests/test-pagealign_alloc.c | 83 +++++++++++++++++++++++++++++++++++
3 files changed, 96 insertions(+)
create mode 100644 tests/test-pagealign_alloc.c
diff --git a/ChangeLog b/ChangeLog
index e0ab0ed821..78a8111497 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,12 @@
2025-09-13 Bruno Haible <[email protected]>
+ pagealign_alloc: Add unit test for scalability.
+ * tests/test-pagealign_alloc.c: New file.
+ * modules/pagealign_alloc-tests (Files): Add it.
+ (Depends-on): Add xalloc.
+ (configure.ac): Check for alarm().
+ (Makefile.am): Arrange to compile and run test-pagealign_alloc.
+
pagealign_alloc: Fix scalability problem.
Reported by Harry Sintonen <[email protected]> in
<https://lists.gnu.org/archive/html/bug-gnulib/2025-09/msg00108.html>.
diff --git a/modules/pagealign_alloc-tests b/modules/pagealign_alloc-tests
index bc9f16fc16..9e3bc64acc 100644
--- a/modules/pagealign_alloc-tests
+++ b/modules/pagealign_alloc-tests
@@ -1,13 +1,19 @@
Files:
+tests/test-pagealign_alloc.c
tests/bench-pagealign_alloc.c
Depends-on:
getpagesize
get-rusage-as
get-rusage-data
+xalloc
configure.ac:
+AC_CHECK_DECLS_ONCE([alarm])
Makefile.am:
+TESTS += test-pagealign_alloc
+check_PROGRAMS += test-pagealign_alloc
+
noinst_PROGRAMS += bench-pagealign_alloc
bench_pagealign_alloc_CPPFLAGS = $(AM_CPPFLAGS) -DNDEBUG
diff --git a/tests/test-pagealign_alloc.c b/tests/test-pagealign_alloc.c
new file mode 100644
index 0000000000..0b1374a589
--- /dev/null
+++ b/tests/test-pagealign_alloc.c
@@ -0,0 +1,83 @@
+/* Test pagealign_alloc module.
+ Copyright (C) 2025 Free Software Foundation, Inc.
+
+ This program is free software: you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation, either version 3 of the License, or
+ (at your option) any later version.
+
+ This program 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 General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see <https://www.gnu.org/licenses/>. */
+
+/* Written by Bruno Haible <[email protected]>, 2025. */
+
+#include <config.h>
+
+/* Specification. */
+#include "pagealign_alloc.h"
+
+/* This test verifies that allocating and then freeing N pages is O(N),
+ not O(N??). */
+
+#include <signal.h>
+#include <stdlib.h>
+#include <unistd.h>
+
+#include "xalloc.h"
+
+int
+main (int argc, char *argv[])
+{
+#if HAVE_DECL_ALARM
+ /* Declare failure if test takes too long, by using default abort
+ caused by SIGALRM.
+ On a fast x86_64 machine in 2025, with the PA_IMPL_MALLOC implementation,
+ the execution times are:
+ n | time | time |
+ | linear list | hash set |
+ -------+-------------+----------+
+ 10000 | 0.15 sec | 0.03 sec |
+ 25000 | 0.8 sec | 0.07 sec |
+ 50000 | 3.1 sec | 0.13 sec |
+ 100000 | 14 sec | 0.26 sec |
+ */
+ int alarm_value = 10;
+ signal (SIGALRM, SIG_DFL);
+ alarm (alarm_value);
+#endif
+
+ int n;
+ if (argc > 1)
+ n = atoi (argv[1]);
+ else
+ {
+#if defined __CYGWIN__
+ n = 25000;
+#else
+ n = (sizeof (void *) <= 4 ? 25000 : 50000);
+#endif
+ }
+
+ void **pages = XNMALLOC (n, void *);
+
+ size_t pagesize = getpagesize ();
+
+ int i;
+ for (i = 0; i < n; i++)
+ pages[i] = pagealign_xalloc (pagesize);
+
+ /* Free half of the pages in allocation order and the other half of the pages
+ in reverse allocation order. */
+ int half = n / 2;
+ for (i = 0; i < half; i++)
+ pagealign_free (pages[i]);
+ for (i = n - 1; i >= half; i--)
+ pagealign_free (pages[i]);
+
+ return 0;
+}
--
2.50.1
>From bcc735c1ebb0ae26bff284a4b48500f241db8ee4 Mon Sep 17 00:00:00 2001
From: Bruno Haible <[email protected]>
Date: Sun, 14 Sep 2025 00:25:21 +0200
Subject: [PATCH 4/4] pagealign_alloc: Don't waste large amounts of memory
(regr. 2025-09-10).
* lib/pagealign_alloc.c (get_default_impl): Choose a default that does
not waste large amounts of memory.
---
ChangeLog | 6 ++++++
lib/pagealign_alloc.c | 38 +++++++++++++++++++++++++++++++++++++-
2 files changed, 43 insertions(+), 1 deletion(-)
diff --git a/ChangeLog b/ChangeLog
index 78a8111497..41303f9ce2 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,9 @@
+2025-09-13 Bruno Haible <[email protected]>
+
+ pagealign_alloc: Don't waste large amounts of memory (regr. 2025-09-10).
+ * lib/pagealign_alloc.c (get_default_impl): Choose a default that does
+ not waste large amounts of memory.
+
2025-09-13 Bruno Haible <[email protected]>
pagealign_alloc: Add unit test for scalability.
diff --git a/lib/pagealign_alloc.c b/lib/pagealign_alloc.c
index 332306bd41..b730cceabd 100644
--- a/lib/pagealign_alloc.c
+++ b/lib/pagealign_alloc.c
@@ -70,11 +70,47 @@ static gl_map_t page_info_map;
static pagealign_impl_t
get_default_impl (void)
{
-#if HAVE_POSIX_MEMALIGN
+ /* The default is chosen so as to
+ 1. (most important) not waste memory, when possible.
+ 2. when there is no waste of memory, avoid using the page_info_map,
+ when possible.
+ Regarding the amount of used memory, it was determined through the
+ 'bench-pagealign_alloc' program. The results were:
+
+ b c d e f
+
+ glibc 176% 101% 175% --- ---
+ musl libc 198% 101% 197% --- ---
+ macOS 190% 100% 195% --- ---
+ FreeBSD 190% 100% 380% --- ---
+ NetBSD 185% 101% 379% --- ---
+ OpenBSD 177% 101% 101% --- ---
+ AIX 177% 101% 176% --- ---
+ Solaris 11.4 176% 101% 175% --- ---
+ Cygwin 181% 100% 181% --- ---
+ native Windows 184% --- --- 180% 100%
+ Android 182% 101% 181% --- ---
+
+ where
+ b = PA_IMPL_MALLOC
+ c = PA_IMPL_MMAP
+ d = PA_IMPL_POSIX_MEMALIGN
+ e = PA_IMPL_ALIGNED_MALLOC
+ f = PA_IMPL_VIRTUAL_ALLOC
+ */
+#if defined _WIN32 && !defined __CYGWIN__
+ /* Native Windows. */
+ return PA_IMPL_VIRTUAL_ALLOC;
+#elif defined __OpenBSD__ && HAVE_POSIX_MEMALIGN
+ /* On OpenBSD, we may choose among PA_IMPL_MMAP and PA_IMPL_POSIX_MEMALIGN.
+ The latter does not need the page_info_map. */
return PA_IMPL_POSIX_MEMALIGN;
#elif HAVE_SYS_MMAN_H
+ /* On all other platforms, PA_IMPL_MMAP is the only implementation that does
+ not waste memory. */
return PA_IMPL_MMAP;
#else
+ /* Old platforms without mmap: use PA_IMPL_MALLOC. */
return PA_IMPL_MALLOC;
#endif
}
--
2.50.1
