diff --git a/elf/Makefile b/elf/Makefile index 7f039b5563..cfe4b3f9a5 100644 --- a/elf/Makefile +++ b/elf/Makefile @@ -219,11 +219,11 @@ install-rootsbin += ldconfig ldconfig-modules := \ cache \ + cachestrings \ chroot_canon \ ldconfig-parse \ readlib \ static-stubs \ - stringtable \ xmalloc \ xstrdup \ # ldconfig-modules @@ -309,11 +309,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 a6dc85dc0f..d8bc2f7135 100644 --- a/elf/cache.c +++ b/elf/cache.c @@ -35,10 +35,10 @@ #include #include #include -#include +#include /* 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..c17c48bce6 --- /dev/null +++ b/elf/cachestrings.c @@ -0,0 +1,149 @@ +/* String tables for ld.so.cache construction. Implementation. + Copyright (C) 2020-2026 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 . */ + +#include + +#include +#include +#include +#include +#include +#include +#include + +#define STRINGTABLE_ENTRY cachestrings_entry +#define STRINGTABLE_STRUCT cachestrings +#define STRINGTABLE_PREFIX cache_s_table_ +#include + +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 3f78ec43aa..c57c5100d1 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 . */ -#ifndef _STRINGTABLE_H -#define _STRINGTABLE_H +#ifndef CACHESTRINGS_H +#define CACHESTRINGS_H #include #include +#include -/* 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 c59b417c2d..0000000000 --- a/elf/stringtable.c +++ /dev/null @@ -1,209 +0,0 @@ -/* String tables for ld.so.cache construction. Implementation. - Copyright (C) 2020-2026 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 . */ - -#include -#include -#include -#include -#include -#include -#include - -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 1f0727f38f..88196618ce 100644 --- a/elf/tst-stringtable.c +++ b/elf/tst-cachestrings.c @@ -19,7 +19,8 @@ #include #if __GNUC_PREREQ (5, 0) #include -#include +#define attribute_hidden +#include #include #include @@ -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 diff --git a/include/stringtable-skeleton.h b/include/stringtable-skeleton.h new file mode 100644 index 0000000000..041cf8e3aa --- /dev/null +++ b/include/stringtable-skeleton.h @@ -0,0 +1,129 @@ +/* Template for defining string tables. + Copyright (C) 2020-2026 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 + . */ + +/* To use the stringtable facility, you need to include + 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 + + 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 + + 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 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 +#include +#include + +#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..e0933289e6 --- /dev/null +++ b/include/stringtable.h @@ -0,0 +1,55 @@ +/* Support facilities for string tables. + Copyright (C) 2020-2026 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 + . */ + +/* See for a way to use this file. */ + +#ifndef STRINGTABLE_H +#define STRINGTABLE_H + +#include +#include + +/* 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 fc44de9934..856cf38ae7 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/misc/fnv1a.c b/misc/fnv1a.c new file mode 100644 index 0000000000..bc091f6515 --- /dev/null +++ b/misc/fnv1a.c @@ -0,0 +1,32 @@ +/* Simple hash function, used in string tables. + Copyright (C) 2020-2026 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 + . */ + +#include + +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; +} diff --git a/misc/stringtable_add.c b/misc/stringtable_add.c new file mode 100644 index 0000000000..c39a699270 --- /dev/null +++ b/misc/stringtable_add.c @@ -0,0 +1,128 @@ +/* Generic implementation for adding strings to string tables. + Copyright (C) 2020-2026 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 + . */ + +#include + +#include +#include +#include +#include + +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..00e477f340 --- /dev/null +++ b/misc/stringtable_free.c @@ -0,0 +1,44 @@ +/* Generic implementation for freeing string tables. + Copyright (C) 2020-2026 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 + . */ + +#include + +#include +#include + +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 1dae2802cf..2d10be3166 100644 --- a/support/Makefile +++ b/support/Makefile @@ -114,6 +114,7 @@ libsupport-routines = \ support_spawn_wrap \ support_stack_alloc \ support_stat_nanoseconds \ + support_stringtable \ support_subprocess \ support_test_compare_blob \ support_test_compare_failure \ diff --git a/elf/stringtable_free.c b/support/support_stringtable.c similarity index 56% rename from elf/stringtable_free.c rename to support/support_stringtable.c index 6ac73f6a8a..b809516fa9 100644 --- a/elf/stringtable_free.c +++ b/support/support_stringtable.c @@ -1,5 +1,5 @@ -/* String tables for ld.so.cache construction. Deallocation (for tests only). - Copyright (C) 2020-2026 Free Software Foundation, Inc. +/* Separate build of stringtables for use in tests. + Copyright (C) 2026 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 @@ -15,19 +15,6 @@ You should have received a copy of the GNU General Public License along with this program; if not, see . */ -#include -#include - -void -stringtable_free (struct stringtable *table) -{ - 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, }; -} +#include +#include +#include