[PATCH 4/7] Extract <stringtable.h> from ldconfig
Florian Weimer
fweimer@redhat.com
Mon Nov 24 19:48:03 GMT 2025
And make it usable in other parts of the library. The type safety
mechanism follows the dynarray approach.
The previous implementation now lives in elf/cachestrings.h and
elf/cachestrings.c and is layered on top of <stringtable.h>
and <stringtable-skeleton.h>.
The internal support routines are built for libsupport, so that
they can be used in tests.
---
elf/Makefile | 4 +-
elf/cache.c | 28 +--
elf/cachestrings.c | 149 +++++++++++++
elf/{stringtable.h => cachestrings.h} | 40 ++--
elf/stringtable.c | 209 ------------------
elf/{tst-stringtable.c => tst-cachestrings.c} | 128 ++++++-----
include/stringtable-skeleton.h | 128 +++++++++++
include/stringtable.h | 54 +++++
misc/Makefile | 3 +
elf/stringtable_free.c => misc/fnv1a.c | 24 +-
misc/stringtable_add.c | 127 +++++++++++
misc/stringtable_free.c | 43 ++++
support/Makefile | 1 +
support/support_stringtable.c | 20 ++
14 files changed, 638 insertions(+), 320 deletions(-)
create mode 100644 elf/cachestrings.c
rename elf/{stringtable.h => cachestrings.h} (53%)
delete mode 100644 elf/stringtable.c
rename elf/{tst-stringtable.c => tst-cachestrings.c} (54%)
create mode 100644 include/stringtable-skeleton.h
create mode 100644 include/stringtable.h
rename elf/stringtable_free.c => misc/fnv1a.c (63%)
create mode 100644 misc/stringtable_add.c
create mode 100644 misc/stringtable_free.c
create mode 100644 support/support_stringtable.c
diff --git a/elf/Makefile b/elf/Makefile
index 07b456f4f5..a99f22d717 100644
--- a/elf/Makefile
+++ b/elf/Makefile
@@ -225,10 +225,10 @@ install-rootsbin += ldconfig
ldconfig-modules := \
cache \
+ cachestrings \
chroot_canon \
readlib \
static-stubs \
- stringtable \
xmalloc \
xstrdup \
# ldconfig-modules
@@ -314,11 +314,11 @@ tests := \
tst-array4 \
tst-array5 \
tst-auxv \
+ tst-cachestrings \
tst-decorate-maps \
tst-dl-hash \
tst-env-setuid \
tst-leaks1 \
- tst-stringtable \
tst-tls9 \
tst-tunables-enable_secure-env \
# tests
diff --git a/elf/cache.c b/elf/cache.c
index 89a6a1e49a..e7959dd07e 100644
--- a/elf/cache.c
+++ b/elf/cache.c
@@ -35,10 +35,10 @@
#include <ldconfig.h>
#include <dl-cache.h>
#include <version.h>
-#include <stringtable.h>
+#include <cachestrings.h>
/* Used to store library names, paths, and other strings. */
-static struct stringtable strings;
+static struct cachestrings strings;
/* Keeping track of "glibc-hwcaps" subdirectories. During cache
construction, a linear search by name is performed to deduplicate
@@ -48,7 +48,7 @@ struct glibc_hwcaps_subdirectory
struct glibc_hwcaps_subdirectory *next;
/* Interned string with the subdirectory name. */
- struct stringtable_entry *name;
+ struct cachestrings_entry *name;
/* Array index in the cache_extension_tag_glibc_hwcaps section in
the stored cached file. This is computed after all the
@@ -63,7 +63,7 @@ struct glibc_hwcaps_subdirectory
const char *
glibc_hwcaps_subdirectory_name (const struct glibc_hwcaps_subdirectory *dir)
{
- return dir->name->string;
+ return dir->name->E.string;
}
/* Linked list of known hwcaps subdirectory names. */
@@ -72,7 +72,7 @@ static struct glibc_hwcaps_subdirectory *hwcaps;
struct glibc_hwcaps_subdirectory *
new_glibc_hwcaps_subdirectory (const char *name)
{
- struct stringtable_entry *name_interned = stringtable_add (&strings, name);
+ struct cachestrings_entry *name_interned = cachestrings_add (&strings, name);
for (struct glibc_hwcaps_subdirectory *p = hwcaps; p != NULL; p = p->next)
if (p->name == name_interned)
return p;
@@ -141,8 +141,8 @@ assign_glibc_hwcaps_indices (void)
struct cache_entry
{
- struct stringtable_entry *lib; /* Library name. */
- struct stringtable_entry *path; /* Path to find library. */
+ struct cachestrings_entry *lib; /* Library name. */
+ struct cachestrings_entry *path; /* Path to find library. */
int flags; /* Flags to indicate kind of library. */
unsigned int isa_level; /* Required ISA level. */
@@ -412,7 +412,7 @@ static int
compare (const struct cache_entry *e1, const struct cache_entry *e2)
{
/* We need to swap entries here to get the correct sort order. */
- int res = _dl_cache_libcmp (e2->lib->string, e1->lib->string);
+ int res = _dl_cache_libcmp (e2->lib->E.string, e1->lib->E.string);
if (res == 0)
{
if (e1->flags < e2->flags)
@@ -519,7 +519,7 @@ compute_hwcap_value (struct cache_entry *entry)
{
if (entry->isa_level > DL_CACHE_HWCAP_ISA_LEVEL_MASK)
error (EXIT_FAILURE, 0, _("%s: ISA level is too high (%d > %d)"),
- entry->path->string, entry->isa_level,
+ entry->path->E.string, entry->isa_level,
DL_CACHE_HWCAP_ISA_LEVEL_MASK);
return (DL_CACHE_HWCAP_EXTENSION
| (((uint64_t) entry->isa_level) << 32)
@@ -548,8 +548,8 @@ save_cache (const char *cache_name)
++cache_entry_old_count;
}
- struct stringtable_finalized strings_finalized;
- stringtable_finalize (&strings, &strings_finalized);
+ struct cachestrings_finalized strings_finalized;
+ cachestrings_finalize (&strings, &strings_finalized);
/* Create the on disk cache structure. */
struct cache_file *file_entries = NULL;
@@ -758,16 +758,16 @@ add_to_cache (const char *path, const char *filename, const char *soname,
{
struct cache_entry *new_entry = xmalloc (sizeof (*new_entry));
- struct stringtable_entry *path_interned;
+ struct cachestrings_entry *path_interned;
{
char *p;
if (asprintf (&p, "%s/%s", path, filename) < 0)
error (EXIT_FAILURE, errno, _("Could not create library path"));
- path_interned = stringtable_add (&strings, p);
+ path_interned = cachestrings_add (&strings, p);
free (p);
}
- new_entry->lib = stringtable_add (&strings, soname);
+ new_entry->lib = cachestrings_add (&strings, soname);
new_entry->path = path_interned;
new_entry->flags = flags;
new_entry->isa_level = isa_level;
diff --git a/elf/cachestrings.c b/elf/cachestrings.c
new file mode 100644
index 0000000000..68f990d974
--- /dev/null
+++ b/elf/cachestrings.c
@@ -0,0 +1,149 @@
+/* String tables for ld.so.cache construction. Implementation.
+ Copyright (C) 2020-2025 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+
+ 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; version 2 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/>. */
+
+#include <cachestrings.h>
+
+#include <assert.h>
+#include <errno.h>
+#include <error.h>
+#include <ldconfig.h>
+#include <libintl.h>
+#include <stdlib.h>
+#include <string.h>
+
+#define STRINGTABLE_ENTRY cachestrings_entry
+#define STRINGTABLE_STRUCT cachestrings
+#define STRINGTABLE_PREFIX cache_s_table_
+#include <stringtable-skeleton.h>
+
+struct cachestrings_entry *
+cachestrings_add (struct cachestrings *table, const char *string)
+{
+ struct cachestrings_entry *e = cache_s_table_add (table, string);
+ if (e == NULL)
+ error (EXIT_FAILURE, errno, _("String table is too large"));
+ return e;
+}
+
+void
+cachestrings_free (struct cachestrings *table)
+{
+ cache_s_table_free (table);
+}
+
+/* Sort reversed strings in reverse lexicographic order. This is used
+ for tail merging. */
+static int
+finalize_compare (const void *l, const void *r)
+{
+ struct cachestrings_entry *left = *(struct cachestrings_entry **) l;
+ struct cachestrings_entry *right = *(struct cachestrings_entry **) r;
+ size_t to_compare;
+ if (left->E.length < right->E.length)
+ to_compare = left->E.length;
+ else
+ to_compare = right->E.length;
+ for (size_t i = 1; i <= to_compare; ++i)
+ {
+ unsigned char lch = left->E.string[left->E.length - i];
+ unsigned char rch = right->E.string[right->E.length - i];
+ if (lch != rch)
+ return rch - lch;
+ }
+ if (left->E.length == right->E.length)
+ return 0;
+ else if (left->E.length < right->E.length)
+ /* Longer strings should come first. */
+ return 1;
+ else
+ return -1;
+}
+
+/* Add E to the array (identified via CLOSURE). */
+static void
+cache_s_table_cb_list (struct cachestrings_entry *e, void *closure)
+{
+ struct cachestrings_entry ***pptr = closure;
+ **pptr = e;
+ ++*pptr;
+}
+
+/* Copy the string of E into the result buffer (a struct
+ cachestrings_finalized *). */
+static void
+cache_s_table_cb_store (struct cachestrings_entry *e, void *closure)
+{
+ struct cachestrings_finalized *result = closure;
+ if (result->strings[e->offset] == '\0')
+ memcpy (&result->strings[e->offset], e->E.string, e->E.length + 1);
+}
+
+void
+cachestrings_finalize (struct cachestrings *table,
+ struct cachestrings_finalized *result)
+{
+ size_t table_count = table->T.count;
+ if (table_count == 0)
+ {
+ result->strings = xstrdup ("");
+ result->size = 0;
+ return;
+ }
+
+ /* Optimize the order of the strings. */
+ struct cachestrings_entry **array
+ = xcalloc (table_count, sizeof (*array));
+ {
+ struct cachestrings_entry **tmp = array;
+ cache_s_table_foreach (table, cache_s_table_cb_list, &tmp);
+ assert (tmp == array + table_count);
+ }
+ qsort (array, table_count, sizeof (*array), finalize_compare);
+
+ /* Assign offsets, using tail merging (sharing suffixes) if possible. */
+ array[0]->offset = 0;
+ for (uint32_t j = 1; j < table_count; ++j)
+ {
+ struct cachestrings_entry *previous = array[j - 1];
+ struct cachestrings_entry *current = array[j];
+ if (previous->E.length >= current->E.length
+ && memcmp (&previous->E.string[previous->E.length
+ - current->E.length],
+ current->E.string, current->E.length) == 0)
+ current->offset = (previous->offset + previous->E.length
+ - current->E.length);
+ else if (__builtin_add_overflow (previous->offset,
+ previous->E.length + 1,
+ ¤t->offset))
+ error (EXIT_FAILURE, 0, _("String table is too large"));
+ }
+
+ /* Allocate the result string. */
+ {
+ struct cachestrings_entry *last = array[table_count - 1];
+ if (__builtin_add_overflow (last->offset, last->E.length + 1,
+ &result->size))
+ error (EXIT_FAILURE, 0, _("String table is too large"));
+ }
+ /* The strings are copied from the hash table, so the array is no
+ longer needed. */
+ free (array);
+ result->strings = xcalloc (result->size, 1);
+
+ /* Copy the strings. */
+ cache_s_table_foreach (table, cache_s_table_cb_store, result);
+}
diff --git a/elf/stringtable.h b/elf/cachestrings.h
similarity index 53%
rename from elf/stringtable.h
rename to elf/cachestrings.h
index 62711bbee3..bcacd92bb2 100644
--- a/elf/stringtable.h
+++ b/elf/cachestrings.h
@@ -15,37 +15,35 @@
You should have received a copy of the GNU General Public License
along with this program; if not, see <https://www.gnu.org/licenses/>. */
-#ifndef _STRINGTABLE_H
-#define _STRINGTABLE_H
+#ifndef CACHESTRINGS_H
+#define CACHESTRINGS_H
#include <stddef.h>
#include <stdint.h>
+#include <stringtable.h>
-/* An entry in the string table. Only the length and string fields are
- expected to be used outside the string table code. */
-struct stringtable_entry
+/* An entry in the string table. Only the entry.length and
+ entry.string fields are expected to be used outside the string
+ table code. */
+struct cachestrings_entry
{
- struct stringtable_entry *next; /* For collision resolution. */
- uint32_t length; /* Length of then string. */
- uint32_t offset; /* From start of finalized table. */
- char string[]; /* Null-terminated string. */
+ size_t offset; /* From start of finalized table. */
+ struct stringtable_entry E;
};
-/* A string table. Zero-initialization produces a valid atable. */
-struct stringtable
+/* String table for use with ldconfig cache strings. */
+struct cachestrings
{
- struct stringtable_entry **entries; /* Array of hash table buckets. */
- uint32_t count; /* Number of elements in the table. */
- uint32_t allocated; /* Length of the entries array. */
+ struct stringtable T;
};
/* Adds STRING to TABLE. May return the address of an existing entry. */
-struct stringtable_entry *stringtable_add (struct stringtable *table,
- const char *string);
+struct cachestrings_entry *cachestrings_add (struct cachestrings *table,
+ const char *string);
/* Result of stringtable_finalize. SIZE bytes at STRINGS should be
written to the file. */
-struct stringtable_finalized
+struct cachestrings_finalized
{
char *strings;
size_t size;
@@ -53,12 +51,12 @@ struct stringtable_finalized
/* Assigns offsets to string table entries and computes the serialized
form of the string table. */
-void stringtable_finalize (struct stringtable *table,
- struct stringtable_finalized *result);
+void cachestrings_finalize (struct cachestrings *,
+ struct cachestrings_finalized *);
/* Deallocate the string table (but not the TABLE pointer itself).
(The table can be re-used for adding more strings without
initialization.) */
-void stringtable_free (struct stringtable *table);
+void cachestrings_free (struct cachestrings *table);
-#endif /* _STRINGTABLE_H */
+#endif /* CACHESTRINGS_H */
diff --git a/elf/stringtable.c b/elf/stringtable.c
deleted file mode 100644
index 89d1952425..0000000000
--- a/elf/stringtable.c
+++ /dev/null
@@ -1,209 +0,0 @@
-/* String tables for ld.so.cache construction. Implementation.
- Copyright (C) 2020-2025 Free Software Foundation, Inc.
- This file is part of the GNU C Library.
-
- 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; version 2 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/>. */
-
-#include <assert.h>
-#include <error.h>
-#include <ldconfig.h>
-#include <libintl.h>
-#include <stdlib.h>
-#include <string.h>
-#include <stringtable.h>
-
-static void
-stringtable_init (struct stringtable *table)
-{
- table->count = 0;
-
- /* This needs to be a power of two. 128 is sufficient to keep track
- of 42 DSOs without resizing (assuming two strings per DSOs).
- glibc itself comes with more than 20 DSOs, so 64 would likely to
- be too small. */
- table->allocated = 128;
-
- table->entries = xcalloc (table->allocated, sizeof (table->entries[0]));
-}
-
-/* 32-bit FNV-1a hash function. */
-static uint32_t
-fnv1a (const char *string, size_t length)
-{
- const unsigned char *p = (const unsigned char *) string;
- uint32_t hash = 2166136261U;
- for (size_t i = 0; i < length; ++i)
- {
- hash ^= p[i];
- hash *= 16777619U;
- }
- return hash;
-}
-
-/* Double the capacity of the hash table. */
-static void
-stringtable_rehash (struct stringtable *table)
-{
- /* This computation cannot overflow because the old total in-memory
- size of the hash table is larger than the computed value. */
- uint32_t new_allocated = table->allocated * 2;
- struct stringtable_entry **new_entries
- = xcalloc (new_allocated, sizeof (table->entries[0]));
-
- uint32_t mask = new_allocated - 1;
- for (uint32_t i = 0; i < table->allocated; ++i)
- for (struct stringtable_entry *e = table->entries[i]; e != NULL; )
- {
- struct stringtable_entry *next = e->next;
- uint32_t hash = fnv1a (e->string, e->length);
- uint32_t new_index = hash & mask;
- e->next = new_entries[new_index];
- new_entries[new_index] = e;
- e = next;
- }
-
- free (table->entries);
- table->entries = new_entries;
- table->allocated = new_allocated;
-}
-
-struct stringtable_entry *
-stringtable_add (struct stringtable *table, const char *string)
-{
- /* Check for a zero-initialized table. */
- if (table->allocated == 0)
- stringtable_init (table);
-
- size_t length = strlen (string);
- if (length > (1U << 30))
- error (EXIT_FAILURE, 0, _("String table string is too long"));
- uint32_t hash = fnv1a (string, length);
-
- /* Return a previously-existing entry. */
- for (struct stringtable_entry *e
- = table->entries[hash & (table->allocated - 1)];
- e != NULL; e = e->next)
- if (e->length == length && memcmp (e->string, string, length) == 0)
- return e;
-
- /* Increase the size of the table if necessary. Keep utilization
- below two thirds. */
- if (table->count >= (1U << 30))
- error (EXIT_FAILURE, 0, _("String table has too many entries"));
- if (table->count * 3 > table->allocated * 2)
- stringtable_rehash (table);
-
- /* Add the new table entry. */
- ++table->count;
- struct stringtable_entry *e
- = xmalloc (offsetof (struct stringtable_entry, string) + length + 1);
- uint32_t index = hash & (table->allocated - 1);
- e->next = table->entries[index];
- table->entries[index] = e;
- e->length = length;
- e->offset = 0;
- memcpy (e->string, string, length + 1);
- return e;
-}
-
-/* Sort reversed strings in reverse lexicographic order. This is used
- for tail merging. */
-static int
-finalize_compare (const void *l, const void *r)
-{
- struct stringtable_entry *left = *(struct stringtable_entry **) l;
- struct stringtable_entry *right = *(struct stringtable_entry **) r;
- size_t to_compare;
- if (left->length < right->length)
- to_compare = left->length;
- else
- to_compare = right->length;
- for (size_t i = 1; i <= to_compare; ++i)
- {
- unsigned char lch = left->string[left->length - i];
- unsigned char rch = right->string[right->length - i];
- if (lch != rch)
- return rch - lch;
- }
- if (left->length == right->length)
- return 0;
- else if (left->length < right->length)
- /* Longer strings should come first. */
- return 1;
- else
- return -1;
-}
-
-void
-stringtable_finalize (struct stringtable *table,
- struct stringtable_finalized *result)
-{
- if (table->count == 0)
- {
- result->strings = xstrdup ("");
- result->size = 0;
- return;
- }
-
- /* Optimize the order of the strings. */
- struct stringtable_entry **array = xcalloc (table->count, sizeof (*array));
- {
- size_t j = 0;
- for (uint32_t i = 0; i < table->allocated; ++i)
- for (struct stringtable_entry *e = table->entries[i]; e != NULL;
- e = e->next)
- {
- array[j] = e;
- ++j;
- }
- assert (j == table->count);
- }
- qsort (array, table->count, sizeof (*array), finalize_compare);
-
- /* Assign offsets, using tail merging (sharing suffixes) if possible. */
- array[0]->offset = 0;
- for (uint32_t j = 1; j < table->count; ++j)
- {
- struct stringtable_entry *previous = array[j - 1];
- struct stringtable_entry *current = array[j];
- if (previous->length >= current->length
- && memcmp (&previous->string[previous->length - current->length],
- current->string, current->length) == 0)
- current->offset = (previous->offset + previous->length
- - current->length);
- else if (__builtin_add_overflow (previous->offset,
- previous->length + 1,
- ¤t->offset))
- error (EXIT_FAILURE, 0, _("String table is too large"));
- }
-
- /* Allocate the result string. */
- {
- struct stringtable_entry *last = array[table->count - 1];
- if (__builtin_add_overflow (last->offset, last->length + 1,
- &result->size))
- error (EXIT_FAILURE, 0, _("String table is too large"));
- }
- /* The strings are copied from the hash table, so the array is no
- longer needed. */
- free (array);
- result->strings = xcalloc (result->size, 1);
-
- /* Copy the strings. */
- for (uint32_t i = 0; i < table->allocated; ++i)
- for (struct stringtable_entry *e = table->entries[i]; e != NULL;
- e = e->next)
- if (result->strings[e->offset] == '\0')
- memcpy (&result->strings[e->offset], e->string, e->length + 1);
-}
diff --git a/elf/tst-stringtable.c b/elf/tst-cachestrings.c
similarity index 54%
rename from elf/tst-stringtable.c
rename to elf/tst-cachestrings.c
index 5fffb0de1b..7daa8838d0 100644
--- a/elf/tst-stringtable.c
+++ b/elf/tst-cachestrings.c
@@ -19,7 +19,8 @@
#include <stdlib.h>
#if __GNUC_PREREQ (5, 0)
#include <string.h>
-#include <stringtable.h>
+#define attribute_hidden
+#include <cachestrings.h>
#include <support/check.h>
#include <support/support.h>
@@ -28,72 +29,75 @@ do_test (void)
{
/* Empty string table. */
{
- struct stringtable s = { 0, };
- struct stringtable_finalized f;
- stringtable_finalize (&s, &f);
+ struct cachestrings s = { 0, };
+ struct cachestrings_finalized f;
+ cachestrings_finalize (&s, &f);
TEST_COMPARE_STRING (f.strings, "");
TEST_COMPARE (f.size, 0);
free (f.strings);
- stringtable_free (&s);
+ cachestrings_free (&s);
}
/* String table with one empty string. */
{
- struct stringtable s = { 0, };
- struct stringtable_entry *e = stringtable_add (&s, "");
- TEST_COMPARE_STRING (e->string, "");
- TEST_COMPARE (e->length, 0);
- TEST_COMPARE (s.count, 1);
-
- struct stringtable_finalized f;
- stringtable_finalize (&s, &f);
+ struct cachestrings s = { 0, };
+ struct cachestrings_entry *e = cachestrings_add (&s, "");
+ TEST_COMPARE_STRING (e->E.string, "");
+ TEST_COMPARE (e->E.length, 0);
+ TEST_COMPARE (e->offset, 0);
+ TEST_COMPARE (s.T.count, 1);
+
+ struct cachestrings_finalized f;
+ cachestrings_finalize (&s, &f);
TEST_COMPARE (e->offset, 0);
TEST_COMPARE_STRING (f.strings, "");
TEST_COMPARE (f.size, 1);
free (f.strings);
- stringtable_free (&s);
+ cachestrings_free (&s);
}
/* String table with one non-empty string. */
{
- struct stringtable s = { 0, };
- struct stringtable_entry *e = stringtable_add (&s, "name");
- TEST_COMPARE_STRING (e->string, "name");
- TEST_COMPARE (e->length, 4);
- TEST_COMPARE (s.count, 1);
-
- struct stringtable_finalized f;
- stringtable_finalize (&s, &f);
+ struct cachestrings s = { 0, };
+ struct cachestrings_entry *e = cachestrings_add (&s, "name");
+ TEST_COMPARE_STRING (e->E.string, "name");
+ TEST_COMPARE (e->E.length, 4);
+ TEST_COMPARE (e->offset, 0);
+ TEST_COMPARE (s.T.count, 1);
+
+ struct cachestrings_finalized f;
+ cachestrings_finalize (&s, &f);
TEST_COMPARE (e->offset, 0);
TEST_COMPARE_STRING (f.strings, "name");
TEST_COMPARE (f.size, 5);
free (f.strings);
- stringtable_free (&s);
+ cachestrings_free (&s);
}
/* Two strings, one is a prefix of the other. Tail-merging can only
happen in one way in this case. */
{
- struct stringtable s = { 0, };
- struct stringtable_entry *suffix = stringtable_add (&s, "suffix");
- TEST_COMPARE_STRING (suffix->string, "suffix");
- TEST_COMPARE (suffix->length, 6);
- TEST_COMPARE (s.count, 1);
-
- struct stringtable_entry *prefix
- = stringtable_add (&s, "prefix-suffix");
- TEST_COMPARE_STRING (prefix->string, "prefix-suffix");
- TEST_COMPARE (prefix->length, strlen ("prefix-suffix"));
- TEST_COMPARE (s.count, 2);
-
- struct stringtable_finalized f;
- stringtable_finalize (&s, &f);
+ struct cachestrings s = { 0, };
+ struct cachestrings_entry *suffix
+ = cachestrings_add (&s, "suffix");
+ TEST_COMPARE_STRING (suffix->E.string, "suffix");
+ TEST_COMPARE (suffix->E.length, 6);
+ TEST_COMPARE (s.T.count, 1);
+
+ struct cachestrings_entry *prefix
+ = cachestrings_add (&s, "prefix-suffix");
+ TEST_COMPARE_STRING (prefix->E.string, "prefix-suffix");
+ TEST_COMPARE (prefix->E.length, strlen ("prefix-suffix"));
+ TEST_COMPARE (s.T.count, 2);
+
+ struct cachestrings_finalized f;
+ cachestrings_finalize (&s, &f);
TEST_COMPARE (prefix->offset, 0);
TEST_COMPARE (suffix->offset, strlen ("prefix-"));
TEST_COMPARE_STRING (f.strings, "prefix-suffix");
TEST_COMPARE (f.size, sizeof ("prefix-suffix"));
free (f.strings);
- stringtable_free (&s);
+ cachestrings_free (&s);
}
/* String table with various shared prefixes. Triggers hash
@@ -101,38 +105,40 @@ do_test (void)
{
enum { count = 1500 };
char *strings[2 * count];
- struct stringtable_entry *entries[2 * count];
- struct stringtable s = { 0, };
+ struct cachestrings_entry *entries[2 * count];
+ struct cachestrings s = { 0, };
for (int i = 0; i < count; ++i)
{
strings[i] = xasprintf ("%d", i);
- entries[i] = stringtable_add (&s, strings[i]);
- TEST_COMPARE (entries[i]->length, strlen (strings[i]));
- TEST_COMPARE_STRING (entries[i]->string, strings[i]);
+ entries[i] = cachestrings_add (&s, strings[i]);
+ TEST_COMPARE (entries[i]->E.length, strlen (strings[i]));
+ TEST_COMPARE_STRING (entries[i]->E.string, strings[i]);
strings[i + count] = xasprintf ("prefix/%d", i);
- entries[i + count] = stringtable_add (&s, strings[i + count]);
- TEST_COMPARE (entries[i + count]->length, strlen (strings[i + count]));
- TEST_COMPARE_STRING (entries[i + count]->string, strings[i + count]);
+ entries[i + count] = cachestrings_add (&s, strings[i + count]);
+ TEST_COMPARE (entries[i + count]->E.length,
+ strlen (strings[i + count]));
+ TEST_COMPARE_STRING (entries[i + count]->E.string,
+ strings[i + count]);
}
- struct stringtable_finalized f;
- stringtable_finalize (&s, &f);
+ struct cachestrings_finalized f;
+ cachestrings_finalize (&s, &f);
for (int i = 0; i < 2 * count; ++i)
{
- TEST_COMPARE (entries[i]->length, strlen (strings[i]));
- TEST_COMPARE_STRING (entries[i]->string, strings[i]);
+ TEST_COMPARE (entries[i]->E.length, strlen (strings[i]));
+ TEST_COMPARE_STRING (entries[i]->E.string, strings[i]);
TEST_COMPARE_STRING (f.strings + entries[i]->offset, strings[i]);
free (strings[i]);
}
free (f.strings);
- stringtable_free (&s);
+ cachestrings_free (&s);
}
/* Verify that maximum tail merging happens. */
{
- struct stringtable s = { 0, };
+ struct cachestrings s = { 0, };
const char *strings[] = {
"",
"a",
@@ -146,14 +152,14 @@ do_test (void)
"ba",
"baa",
};
- struct stringtable_entry *entries[array_length (strings)];
+ struct cachestrings_entry *entries[array_length (strings)];
for (int i = 0; i < array_length (strings); ++i)
- entries[i] = stringtable_add (&s, strings[i]);
+ entries[i] = cachestrings_add (&s, strings[i]);
for (int i = 0; i < array_length (strings); ++i)
- TEST_COMPARE_STRING (entries[i]->string, strings[i]);
+ TEST_COMPARE_STRING (entries[i]->E.string, strings[i]);
- struct stringtable_finalized f;
- stringtable_finalize (&s, &f);
+ struct cachestrings_finalized f;
+ cachestrings_finalize (&s, &f);
/* There are only four different strings, "aaa", "ba", "baa",
"bb". The rest is shared in an unspecified fashion. */
@@ -161,12 +167,12 @@ do_test (void)
for (int i = 0; i < array_length (strings); ++i)
{
- TEST_COMPARE_STRING (entries[i]->string, strings[i]);
+ TEST_COMPARE_STRING (entries[i]->E.string, strings[i]);
TEST_COMPARE_STRING (f.strings + entries[i]->offset, strings[i]);
}
free (f.strings);
- stringtable_free (&s);
+ cachestrings_free (&s);
}
return 0;
@@ -178,8 +184,8 @@ do_test (void)
possible to link against the actual build because it was built for
use in ldconfig. */
#define _(arg) arg
-#include "stringtable.c"
-#include "stringtable_free.c"
+#define __set_errno(code) (void) (errno = (code))
+#include "cachestrings.c"
#else
#include <support/test-driver.h>
diff --git a/include/stringtable-skeleton.h b/include/stringtable-skeleton.h
new file mode 100644
index 0000000000..d48a800efc
--- /dev/null
+++ b/include/stringtable-skeleton.h
@@ -0,0 +1,128 @@
+/* Template for defining string tables.
+ Copyright (C) 2020-2025 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+
+ 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; version 2 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/>. */
+
+/* To use the stringtable facility, you need to include
+ <stringtable-skeleton.h> and define the parameter macros.
+
+ The tables are intrusive: you need to define your own types,
+ embedding struct stringtable_entry and struct stringtable.
+
+ A minimal example looks like this:
+
+ #include <stringtable.h>
+
+ struct table_entry
+ {
+ struct stringtable_entry E;
+ };
+
+ struct table
+ {
+ struct stringtable T;
+ };
+
+ #define STRINGTABLE_ENTRY table_entry
+ #define STRINGTABLE_STRUCT table
+ #define STRINGTABLE_PREFIX table_
+ #include <stringtable-skeleton.h>
+
+ The struct STRINGTABLE_ENTRY type must have a
+
+ struct stringtable_entry E;
+
+ member at the end.
+
+ The struct STRINGTABLE_STRUCT type must have a
+
+ struct stringtable T;
+
+ member (not necessarily at the end). The T member must be
+ zero-initialized before the functions described below are called.
+
+ Including <stringtable-skeleton.h> defines the following functions:
+
+ STRINGTABLE_ENTRY *
+ STRINGTABLE_PREFIX_add (struct STRINGTABLE_STRUCT *table,
+ const char *string);
+
+ Add STRING to TABLE. Returns NULL on memory allocation failure.
+
+ void STRINGTABLE_PREFIX_free (struct STRINGTABLE_STRUCT *table);
+
+ Deallocate TABLE and all its entries.
+
+ void STRINGTABLE_PREFIX_foreach (struct STRINGTABLE_STRUCT *table,
+ void (*cb) (struct STRINGTABLE_ENTRY *,
+ void *),
+ void *closure);
+
+ Iterate over all entries in TABLE, calling CB for each entry
+ with CLOSURE as the second argument.
+*/
+
+#include <stddef.h>
+#include <stdint.h>
+#include <string.h>
+
+#define STRINGTABLE_ENTRY_OFFSET (offsetof (struct STRINGTABLE_ENTRY, E))
+
+_Static_assert (STRINGTABLE_ENTRY_OFFSET + sizeof (struct stringtable_entry)
+ == sizeof (struct STRINGTABLE_ENTRY),
+ "entry member must come last");
+
+#define STRINGTABLE_CONCAT0(prefix, name) prefix##name
+#define STRINGTABLE_CONCAT1(prefix, name) STRINGTABLE_CONCAT0(prefix, name)
+#define STRINGTABLE_NAME(name) STRINGTABLE_CONCAT1(STRINGTABLE_PREFIX, name)
+
+
+__attribute__ ((unused)) static struct STRINGTABLE_ENTRY *
+STRINGTABLE_NAME(add) (struct STRINGTABLE_STRUCT *table,
+ const char *string)
+{
+ return __stringtable_add (&table->T, string, STRINGTABLE_ENTRY_OFFSET);
+}
+
+__attribute__ ((unused)) static void
+STRINGTABLE_NAME(free) (struct STRINGTABLE_STRUCT *table)
+{
+ __stringtable_free (&table->T, STRINGTABLE_ENTRY_OFFSET);
+}
+
+static inline void
+STRINGTABLE_NAME(foreach) (struct STRINGTABLE_STRUCT *table,
+ void (*callback) (struct STRINGTABLE_ENTRY *,
+ void *),
+ void *closure)
+{
+ struct stringtable_entry **p = table->T.entries;
+ if (p == NULL)
+ return;
+ struct stringtable_entry **end = p + table->T.allocated;
+ for (; p != end; ++p)
+ for (struct stringtable_entry *e = *p; e != NULL; e = e->next)
+ callback ((struct STRINGTABLE_ENTRY *) ((char *) e -
+ STRINGTABLE_ENTRY_OFFSET),
+ closure);
+}
+
+#undef STRINGTABLE_CONCAT0
+#undef STRINGTABLE_CONCAT1
+#undef STRINGTABLE_NAME
+#undef STRINGTABLE_ENTRY_OFFSET
+#undef STRINGTABLE_ENTRY
+#undef STRINGTABLE_STRUCT
+#undef STRINGTABLE_PREFIX
diff --git a/include/stringtable.h b/include/stringtable.h
new file mode 100644
index 0000000000..7176dbd7c1
--- /dev/null
+++ b/include/stringtable.h
@@ -0,0 +1,54 @@
+/* Support facilities for string tables.
+ Copyright (C) 2020-2025 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+
+ 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; version 2 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/>. */
+
+/* See <stringtable-skeleton.h> for a way to use this file. */
+
+#ifndef STRINGTABLE_H
+#define STRINGTABLE_H
+
+#include <stddef.h>
+#include <stdint.h>
+
+/* Common part of hash table entries. Used for the E member. */
+struct stringtable_entry
+{
+ struct stringtable_entry *next; /* For collision resolution. */
+ uint32_t length; /* Length of the string. */
+ char string[]; /* Null-terminated string. */
+};
+
+/* Common fields of a string table. Used for the T member.
+ Zero-initialization produces a valid table. */
+struct stringtable
+{
+ struct stringtable_entry **entries; /* Array of hash table buckets. */
+ uint32_t count; /* Number of elements in the table. */
+ uint32_t allocated; /* Length of the entries array. */
+};
+
+/* 32-bit FNV-1a hash function. */
+uint32_t __fnv1a (const char *string, size_t length) attribute_hidden;
+
+/* Internal functions. ENTRY_OFFSET is the offset of the
+ stringtable_entry structs from the start of the malloc
+ allocation. */
+void *__stringtable_add (struct stringtable *, const char *,
+ size_t entry_offset) attribute_hidden;
+void __stringtable_free (struct stringtable *, size_t entry_offset)
+ attribute_hidden;
+
+#endif /* STRINGTABLE_H */
diff --git a/misc/Makefile b/misc/Makefile
index e792d94ebd..a5df61574a 100644
--- a/misc/Makefile
+++ b/misc/Makefile
@@ -99,6 +99,7 @@ routines := \
fdatasync \
fgetxattr \
flistxattr \
+ fnv1a \
fremovexattr \
fsetxattr \
fstab \
@@ -187,6 +188,8 @@ routines := \
setxattr \
single_threaded \
sstk \
+ stringtable_add \
+ stringtable_free \
stty \
swapoff \
swapon \
diff --git a/elf/stringtable_free.c b/misc/fnv1a.c
similarity index 63%
rename from elf/stringtable_free.c
rename to misc/fnv1a.c
index 0141b4132b..6dc35e2b3e 100644
--- a/elf/stringtable_free.c
+++ b/misc/fnv1a.c
@@ -1,4 +1,4 @@
-/* String tables for ld.so.cache construction. Deallocation (for tests only).
+/* Simple hash function, used in string tables.
Copyright (C) 2020-2025 Free Software Foundation, Inc.
This file is part of the GNU C Library.
@@ -15,19 +15,17 @@
You should have received a copy of the GNU General Public License
along with this program; if not, see <https://www.gnu.org/licenses/>. */
-#include <stdlib.h>
#include <stringtable.h>
-void
-stringtable_free (struct stringtable *table)
+uint32_t
+__fnv1a (const char *string, size_t length)
{
- for (uint32_t i = 0; i < table->allocated; ++i)
- for (struct stringtable_entry *e = table->entries[i]; e != NULL; )
- {
- struct stringtable_entry *next = e->next;
- free (e);
- e = next;
- }
- free (table->entries);
- *table = (struct stringtable) { 0, };
+ const unsigned char *p = (const unsigned char *) string;
+ uint32_t hash = 2166136261U;
+ for (size_t i = 0; i < length; ++i)
+ {
+ hash ^= p[i];
+ hash *= 16777619U;
+ }
+ return hash;
}
diff --git a/misc/stringtable_add.c b/misc/stringtable_add.c
new file mode 100644
index 0000000000..6c71a19d2e
--- /dev/null
+++ b/misc/stringtable_add.c
@@ -0,0 +1,127 @@
+/* Generic implementation for adding strings to string tables.
+ Copyright (C) 2020-2025 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+
+ 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; version 2 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/>. */
+
+#include <stringtable.h>
+
+#include <errno.h>
+#include <stdbool.h>
+#include <stdlib.h>
+#include <string.h>
+
+static bool
+__stringtable_init (struct stringtable *table)
+{
+ table->count = 0;
+
+ /* This needs to be a power of two. */
+ table->allocated = 16;
+
+ table->entries = calloc (table->allocated, sizeof (table->entries[0]));
+ return table->entries != NULL;
+}
+
+/* Double the capacity of the hash table. */
+static bool
+__stringtable_rehash (struct stringtable *table)
+{
+ uint32_t new_allocated = table->allocated * 2;
+ if (new_allocated < table->allocated)
+ {
+ __set_errno (ENOMEM);
+ return false;
+ }
+
+ struct stringtable_entry **new_entries
+ = calloc (new_allocated, sizeof (table->entries[0]));
+ if (new_entries == NULL)
+ return false;
+
+ uint32_t mask = new_allocated - 1;
+ for (uint32_t i = 0; i < table->allocated; ++i)
+ for (struct stringtable_entry *e = table->entries[i]; e != NULL; )
+ {
+ struct stringtable_entry *next = e->next;
+ uint32_t hash = __fnv1a (e->string, e->length);
+ uint32_t new_index = hash & mask;
+ e->next = new_entries[new_index];
+ new_entries[new_index] = e;
+ e = next;
+ }
+
+ free (table->entries);
+ table->entries = new_entries;
+ table->allocated = new_allocated;
+ return true;
+}
+
+void *
+__stringtable_add (struct stringtable *table, const char *string,
+ size_t entry_offset)
+{
+ /* Check for a zero-initialized table. */
+ if (table->allocated == 0 && !__stringtable_init (table))
+ return NULL;
+
+ size_t length = strlen (string);
+ if (length != (uint32_t) length)
+ {
+ /* String is too long to store. */
+ __set_errno (ENOMEM);
+ return NULL;
+ }
+
+ uint32_t hash = __fnv1a (string, length);
+
+ /* Return a previously-existing entry. */
+ for (struct stringtable_entry *e
+ = table->entries[hash & (table->allocated - 1)];
+ e != NULL; e = e->next)
+ if (e->length == length && memcmp (e->string, string, length) == 0)
+ return (char *) e - entry_offset;
+
+ /* Increase the size of the table if necessary. Keep utilization
+ below two thirds. */
+ if (table->count >= UINT32_MAX / 3)
+ {
+ __set_errno (ENOMEM);
+ return NULL;
+ }
+ if (table->count * 3 > table->allocated * 2)
+ if (!__stringtable_rehash (table))
+ return NULL;
+
+ /* Add the new table entry. No overflow is possible because length
+ must be less than half of the address space size. */
+ char *base = malloc (entry_offset
+ + offsetof (struct stringtable_entry, string)
+ + length + 1);
+ if (base == NULL)
+ return NULL;
+ /* Extra data is zero-initialized. */
+ memset (base, 0, entry_offset);
+
+ struct stringtable_entry *e
+ = (struct stringtable_entry *) (base + entry_offset);
+ e->length = length;
+ memcpy (e->string, string, length + 1);
+
+ ++table->count;
+ uint32_t index = hash & (table->allocated - 1);
+ e->next = table->entries[index];
+ table->entries[index] = e;
+ return (char *) e - entry_offset;
+}
diff --git a/misc/stringtable_free.c b/misc/stringtable_free.c
new file mode 100644
index 0000000000..e7204010f2
--- /dev/null
+++ b/misc/stringtable_free.c
@@ -0,0 +1,43 @@
+/* Generic implementation for freeing string tables.
+ Copyright (C) 2020-2025 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+
+ 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; version 2 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/>. */
+
+#include <stringtable.h>
+
+#include <stddef.h>
+#include <stdlib.h>
+
+void
+__stringtable_free (struct stringtable *table,
+ size_t entry_offset)
+{
+ size_t allocated = table->allocated;
+ for (size_t i = 0; i < allocated; ++i)
+ {
+ struct stringtable_entry *e = table->entries[i];
+ while (e != NULL)
+ {
+ struct stringtable_entry *next = e->next;
+ /* The allocated pointer is at an offset before the entry. */
+ free ((char *) e - entry_offset);
+ e = next;
+ }
+ }
+ free (table->entries);
+ table->entries = NULL;
+ table->allocated = 0;
+ table->count = 0;
+}
diff --git a/support/Makefile b/support/Makefile
index 2043e4e590..dbea4b3726 100644
--- a/support/Makefile
+++ b/support/Makefile
@@ -93,6 +93,7 @@ libsupport-routines = \
support_socket_so_timestamp_time64 \
support_stack_alloc \
support_stat_nanoseconds \
+ support_stringtable \
support_subprocess \
support_test_compare_blob \
support_test_compare_failure \
diff --git a/support/support_stringtable.c b/support/support_stringtable.c
new file mode 100644
index 0000000000..aef6d6f6db
--- /dev/null
+++ b/support/support_stringtable.c
@@ -0,0 +1,20 @@
+/* Separate build of stringtables for use in tests.
+ Copyright (C) 2025 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+
+ 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; version 2 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/>. */
+
+#include <misc/fnv1a.c>
+#include <misc/stringtable_add.c>
+#include <misc/stringtable_free.c>
--
2.52.0
More information about the Libc-alpha
mailing list