Hi,
I was wondering if anyone had a chance to look at these changes again? I
have attached the two patches we propose so we can add support for TLS
descriptors.
It would be great to get an ACK for it (or NACK with maybe some other
suggestions).
Thanks,
-Chris
On 11/7/13, 1:52 PM, Chris Zankel wrote:
Hi Rich,
Thanks for your feedback.
On 11/6/13, 9:27 PM, Rich Felker wrote:
On Wed, Nov 06, 2013 at 11:23:06AM +0200, Baruch Siach wrote:
The hashcode handling code never accesses the underlying structure
'struct funcdesc_value', but only operates on pointer to pointers,
so we can use void** instead.
No you can't. This is an aliasing violation, and a compiler performing
LTO would be free to reorder accesses in such a way as to horribly
break things. However it appears the code may already contain some
I think the original comment was a bit misleading, and I'm not sure
how to really word it. However, I fail to see where the aliasing
violation would be, but admit that I might be missing something.
The hashcode routine handles pointers, and they are never
dereferenced. My understanding is that void* is guaranteed to hold any
pointer (in size and alignment) and allows assignment to any other
pointer (T* <-> void*). In that case, it would be save to have a table
of pointers (void* table[]) and cast between T* and table[i]. This
seems to be the essence of that code.
similar aliasing violations. This should be investigated before any
further changes are made.
Would be great if you could point me to those violations. Note that
I'm not trying to defend the actual implementation of that code, but
it is also used that way in glibc, so we should only rewrite or fix if
and what is necessary.
Thanks,
-Chris
--- Begin Message ---
The hashcode handling code never accesses the underlying structure
'struct funcdesc_value', but only operates on pointer to pointers,
so we can use void** instead.
Also, pass in the functions to generate and compare a hash entry.
This is a minor functional change to inject function pointers
instead of using it inline functions.
This change is in preparation to support tls descriptors, which
require a different hash and compare function.
Signed-off-by: Chris Zankel <[email protected]>
Signed-off-by: Baruch Siach <[email protected]>
---
ldso/include/inline-hashtab.h | 41 ++++++++++++++++++-----------------------
ldso/ldso/fdpic/dl-inlines.h | 19 +++++++++++++++++--
2 files changed, 35 insertions(+), 25 deletions(-)
diff --git a/ldso/include/inline-hashtab.h b/ldso/include/inline-hashtab.h
index 5e82cc9..4a48120 100644
--- a/ldso/include/inline-hashtab.h
+++ b/ldso/include/inline-hashtab.h
@@ -71,7 +71,7 @@ higher_prime_number(unsigned long n)
struct funcdesc_ht
{
/* Table itself */
- struct funcdesc_value **entries;
+ void **entries;
/* Current size (in entries) of the hash table */
size_t size;
@@ -80,12 +80,6 @@ struct funcdesc_ht
size_t n_elements;
};
-static __always_inline int
-hash_pointer(const void *p)
-{
- return (int) ((long)p >> 3);
-}
-
static __always_inline struct funcdesc_ht *
htab_create(void)
{
@@ -95,7 +89,7 @@ htab_create(void)
if (!ht)
return NULL;
ht->size = 3;
- ent_size = sizeof(struct funcdesc_ht_value *) * ht->size;
+ ent_size = sizeof(void *) * ht->size;
ht->entries = _dl_malloc(ent_size);
if (!ht->entries)
return NULL;
@@ -131,12 +125,12 @@ htab_delete(struct funcdesc_ht *htab)
* This function also assumes there are no deleted entries in the table.
* HASH is the hash value for the element to be inserted.
*/
-static __always_inline struct funcdesc_value **
+static __always_inline void **
find_empty_slot_for_expand(struct funcdesc_ht *htab, int hash)
{
size_t size = htab->size;
unsigned int index = hash % size;
- struct funcdesc_value **slot = htab->entries + index;
+ void **slot = htab->entries + index;
int hash2;
if (!*slot)
@@ -164,12 +158,12 @@ find_empty_slot_for_expand(struct funcdesc_ht *htab, int
hash)
* expanded. If all goes well, it will return a non-zero value.
*/
static __always_inline int
-htab_expand(struct funcdesc_ht *htab)
+htab_expand(struct funcdesc_ht *htab, int (*hash_fn) (void *))
{
- struct funcdesc_value **oentries;
- struct funcdesc_value **olimit;
- struct funcdesc_value **p;
- struct funcdesc_value **nentries;
+ void **oentries;
+ void **olimit;
+ void **p;
+ void **nentries;
size_t nsize;
oentries = htab->entries;
@@ -194,7 +188,7 @@ htab_expand(struct funcdesc_ht *htab)
p = oentries;
do {
if (*p)
- *find_empty_slot_for_expand(htab,
hash_pointer((*p)->entry_point)) = *p;
+ *find_empty_slot_for_expand(htab, hash_fn(*p)) = *p;
p++;
} while (p < olimit);
@@ -223,19 +217,20 @@ htab_expand(struct funcdesc_ht *htab)
* When inserting an entry, NULL may be returned if memory allocation
* fails.
*/
-static __always_inline struct funcdesc_value **
-htab_find_slot(struct funcdesc_ht *htab, void *ptr, int insert)
+static __always_inline void **
+htab_find_slot(struct funcdesc_ht *htab, void *ptr, int insert,
+ int (*hash_fn)(void *), int (*eq_fn)(void *, void *))
{
unsigned int index;
int hash, hash2;
size_t size;
- struct funcdesc_value **entry;
+ void **entry;
if (htab->size * 3 <= htab->n_elements * 4 &&
- htab_expand(htab) == 0)
+ htab_expand(htab, hash_fn) == 0)
return NULL;
- hash = hash_pointer(ptr);
+ hash = hash_fn(ptr);
size = htab->size;
index = hash % size;
@@ -243,7 +238,7 @@ htab_find_slot(struct funcdesc_ht *htab, void *ptr, int
insert)
entry = &htab->entries[index];
if (!*entry)
goto empty_entry;
- else if ((*entry)->entry_point == ptr)
+ else if (eq_fn(*entry, ptr))
return entry;
hash2 = 1 + hash % (size - 2);
@@ -255,7 +250,7 @@ htab_find_slot(struct funcdesc_ht *htab, void *ptr, int
insert)
entry = &htab->entries[index];
if (!*entry)
goto empty_entry;
- else if ((*entry)->entry_point == ptr)
+ else if (eq_fn(*entry, ptr))
return entry;
}
diff --git a/ldso/ldso/fdpic/dl-inlines.h b/ldso/ldso/fdpic/dl-inlines.h
index 46e4ba3..ebbd033 100644
--- a/ldso/ldso/fdpic/dl-inlines.h
+++ b/ldso/ldso/fdpic/dl-inlines.h
@@ -145,6 +145,20 @@ __dl_addr_in_loadaddr(void *p, struct elf32_fdpic_loadaddr
loadaddr)
return 0;
}
+static int
+hash_pointer(void *p)
+{
+ return (int) ((long)p >> 3);
+}
+
+static int
+eq_pointer(void *p, void *q)
+{
+ struct funcdesc_value *entry = p;
+
+ return entry->entry_point == q;
+}
+
void *
_dl_funcdesc_for (void *entry_point, void *got_value)
{
@@ -161,7 +175,7 @@ _dl_funcdesc_for (void *entry_point, void *got_value)
tpnt->funcdesc_ht = ht;
}
- entry = htab_find_slot(ht, entry_point, 1);
+ entry = htab_find_slot(ht, entry_point, 1, hash_pointer, eq_pointer);
if (*entry) {
_dl_assert((*entry)->entry_point == entry_point);
return _dl_stabilize_funcdesc(*entry);
@@ -196,7 +210,8 @@ _dl_lookup_address(void const *address)
if (fd->got_value != rpnt->loadaddr.got_value)
continue;
- address = htab_find_slot(rpnt->funcdesc_ht, (void
*)fd->entry_point, 0);
+ address = htab_find_slot(rpnt->funcdesc_ht, (void
*)fd->entry_point, 0,
+ hash_pointer, eq_pointer);
if (address && *(struct funcdesc_value *const*)address == fd) {
address = (*(struct funcdesc_value
*const*)address)->entry_point;
--
1.8.4.rc3
--- End Message ---
--- Begin Message ---
Move the hashcode handling code inside the ldso/fdpic/dl-inlines.h
to a header file (include/inline-hashtab.h), without any functional
changes.
This is in preparation for supporting TLS descriptors, which also
uses that code.
Signed-off-by: Chris Zankel <[email protected]>
Signed-off-by: Baruch Siach <[email protected]>
---
ldso/include/inline-hashtab.h | 270 ++++++++++++++++++++++++++++++++++++++++++
ldso/ldso/fdpic/dl-inlines.h | 267 +----------------------------------------
2 files changed, 272 insertions(+), 265 deletions(-)
create mode 100644 ldso/include/inline-hashtab.h
diff --git a/ldso/include/inline-hashtab.h b/ldso/include/inline-hashtab.h
new file mode 100644
index 0000000..5e82cc9
--- /dev/null
+++ b/ldso/include/inline-hashtab.h
@@ -0,0 +1,270 @@
+/*
+ * The hashcode handling code below is heavily inspired in libiberty's
+ * hashtab code, but with most adaptation points and support for
+ * deleting elements removed.
+ *
+ * Copyright (C) 1999, 2000, 2001, 2002, 2003 Free Software Foundation, Inc.
+ * Contributed by Vladimir Makarov ([email protected]).
+ */
+
+#ifndef INLINE_HASHTAB_H
+# define INLINE_HASHTAB_H 1
+
+static __always_inline unsigned long
+higher_prime_number(unsigned long n)
+{
+ /* These are primes that are near, but slightly smaller than, a power
of two. */
+ static const unsigned long primes[] = {
+ 7,
+ 13,
+ 31,
+ 61,
+ 127,
+ 251,
+ 509,
+ 1021,
+ 2039,
+ 4093,
+ 8191,
+ 16381,
+ 32749,
+ 65521,
+ 131071,
+ 262139,
+ 524287,
+ 1048573,
+ 2097143,
+ 4194301,
+ 8388593,
+ 16777213,
+ 33554393,
+ 67108859,
+ 134217689,
+ 268435399,
+ 536870909,
+ 1073741789,
+ /* 4294967291 */
+ ((unsigned long) 2147483647) + ((unsigned long) 2147483644),
+ };
+ const unsigned long *low = &primes[0];
+ const unsigned long *high = &primes[ARRAY_SIZE(primes)];
+
+ while (low != high) {
+ const unsigned long *mid = low + (high - low) / 2;
+ if (n > *mid)
+ low = mid + 1;
+ else
+ high = mid;
+ }
+
+#if 0
+ /* If we've run out of primes, abort. */
+ if (n > *low) {
+ fprintf(stderr, "Cannot find prime bigger than %lu\n", n);
+ abort();
+ }
+#endif
+
+ return *low;
+}
+
+struct funcdesc_ht
+{
+ /* Table itself */
+ struct funcdesc_value **entries;
+
+ /* Current size (in entries) of the hash table */
+ size_t size;
+
+ /* Current number of elements */
+ size_t n_elements;
+};
+
+static __always_inline int
+hash_pointer(const void *p)
+{
+ return (int) ((long)p >> 3);
+}
+
+static __always_inline struct funcdesc_ht *
+htab_create(void)
+{
+ struct funcdesc_ht *ht = _dl_malloc(sizeof(*ht));
+ size_t ent_size;
+
+ if (!ht)
+ return NULL;
+ ht->size = 3;
+ ent_size = sizeof(struct funcdesc_ht_value *) * ht->size;
+ ht->entries = _dl_malloc(ent_size);
+ if (!ht->entries)
+ return NULL;
+
+ ht->n_elements = 0;
+ _dl_memset(ht->entries, 0, ent_size);
+
+ return ht;
+}
+
+/*
+ * This is only called from _dl_loadaddr_unmap, so it's safe to call
+ * _dl_free(). See the discussion below.
+ */
+static __always_inline void
+htab_delete(struct funcdesc_ht *htab)
+{
+ size_t i;
+
+ for (i = htab->size - 1; i >= 0; i--)
+ if (htab->entries[i])
+ _dl_free(htab->entries[i]);
+
+ _dl_free(htab->entries);
+ _dl_free(htab);
+}
+
+/*
+ * Similar to htab_find_slot, but without several unwanted side effects:
+ * - Does not call htab->eq_f when it finds an existing entry.
+ * - Does not change the count of elements/searches/collisions in the
+ * hash table.
+ * This function also assumes there are no deleted entries in the table.
+ * HASH is the hash value for the element to be inserted.
+ */
+static __always_inline struct funcdesc_value **
+find_empty_slot_for_expand(struct funcdesc_ht *htab, int hash)
+{
+ size_t size = htab->size;
+ unsigned int index = hash % size;
+ struct funcdesc_value **slot = htab->entries + index;
+ int hash2;
+
+ if (!*slot)
+ return slot;
+
+ hash2 = 1 + hash % (size - 2);
+ for (;;) {
+ index += hash2;
+ if (index >= size)
+ index -= size;
+
+ slot = htab->entries + index;
+ if (!*slot)
+ return slot;
+ }
+}
+
+/*
+ * The following function changes size of memory allocated for the
+ * entries and repeatedly inserts the table elements. The occupancy
+ * of the table after the call will be about 50%. Naturally the hash
+ * table must already exist. Remember also that the place of the
+ * table entries is changed. If memory allocation failures are allowed,
+ * this function will return zero, indicating that the table could not be
+ * expanded. If all goes well, it will return a non-zero value.
+ */
+static __always_inline int
+htab_expand(struct funcdesc_ht *htab)
+{
+ struct funcdesc_value **oentries;
+ struct funcdesc_value **olimit;
+ struct funcdesc_value **p;
+ struct funcdesc_value **nentries;
+ size_t nsize;
+
+ oentries = htab->entries;
+ olimit = oentries + htab->size;
+
+ /*
+ * Resize only when table after removal of unused elements is either
+ * too full or too empty.
+ */
+ if (htab->n_elements * 2 > htab->size)
+ nsize = higher_prime_number(htab->n_elements * 2);
+ else
+ nsize = htab->size;
+
+ nentries = _dl_malloc(sizeof(*nentries) * nsize);
+ _dl_memset(nentries, 0, sizeof(*nentries) * nsize);
+ if (nentries == NULL)
+ return 0;
+ htab->entries = nentries;
+ htab->size = nsize;
+
+ p = oentries;
+ do {
+ if (*p)
+ *find_empty_slot_for_expand(htab,
hash_pointer((*p)->entry_point)) = *p;
+ p++;
+ } while (p < olimit);
+
+#if 0
+ /*
+ * We can't tell whether this was allocated by the _dl_malloc()
+ * built into ld.so or malloc() in the main executable or libc,
+ * and calling free() for something that wasn't malloc()ed could
+ * do Very Bad Things (TM). Take the conservative approach
+ * here, potentially wasting as much memory as actually used by
+ * the hash table, even if multiple growths occur. That's not
+ * so bad as to require some overengineered solution that would
+ * enable us to keep track of how it was allocated.
+ */
+ _dl_free(oentries);
+#endif
+ return 1;
+}
+
+/*
+ * This function searches for a hash table slot containing an entry
+ * equal to the given element. To delete an entry, call this with
+ * INSERT = 0, then call htab_clear_slot on the slot returned (possibly
+ * after doing some checks). To insert an entry, call this with
+ * INSERT = 1, then write the value you want into the returned slot.
+ * When inserting an entry, NULL may be returned if memory allocation
+ * fails.
+ */
+static __always_inline struct funcdesc_value **
+htab_find_slot(struct funcdesc_ht *htab, void *ptr, int insert)
+{
+ unsigned int index;
+ int hash, hash2;
+ size_t size;
+ struct funcdesc_value **entry;
+
+ if (htab->size * 3 <= htab->n_elements * 4 &&
+ htab_expand(htab) == 0)
+ return NULL;
+
+ hash = hash_pointer(ptr);
+
+ size = htab->size;
+ index = hash % size;
+
+ entry = &htab->entries[index];
+ if (!*entry)
+ goto empty_entry;
+ else if ((*entry)->entry_point == ptr)
+ return entry;
+
+ hash2 = 1 + hash % (size - 2);
+ for (;;) {
+ index += hash2;
+ if (index >= size)
+ index -= size;
+
+ entry = &htab->entries[index];
+ if (!*entry)
+ goto empty_entry;
+ else if ((*entry)->entry_point == ptr)
+ return entry;
+ }
+
+ empty_entry:
+ if (!insert)
+ return NULL;
+
+ htab->n_elements++;
+ return entry;
+}
+
+#endif
diff --git a/ldso/ldso/fdpic/dl-inlines.h b/ldso/ldso/fdpic/dl-inlines.h
index 14a4916..46e4ba3 100644
--- a/ldso/ldso/fdpic/dl-inlines.h
+++ b/ldso/ldso/fdpic/dl-inlines.h
@@ -5,6 +5,8 @@
* Licensed under the LGPL v2.1, see the file COPYING.LIB in this tarball.
*/
+#include <inline-hashtab.h>
+
/* Initialize a DL_LOADADDR_TYPE given a got pointer and a complete load map.
*/
static __always_inline void
__dl_init_loadaddr_map(struct elf32_fdpic_loadaddr *loadaddr, Elf32_Addr
dl_boot_got_pointer,
@@ -143,271 +145,6 @@ __dl_addr_in_loadaddr(void *p, struct
elf32_fdpic_loadaddr loadaddr)
return 0;
}
-/*
- * The hashcode handling code below is heavily inspired in libiberty's
- * hashtab code, but with most adaptation points and support for
- * deleting elements removed.
- *
- * Copyright (C) 1999, 2000, 2001, 2002, 2003 Free Software Foundation, Inc.
- * Contributed by Vladimir Makarov ([email protected]).
- */
-static __always_inline unsigned long
-higher_prime_number(unsigned long n)
-{
- /* These are primes that are near, but slightly smaller than, a power
of two. */
- static const unsigned long primes[] = {
- 7,
- 13,
- 31,
- 61,
- 127,
- 251,
- 509,
- 1021,
- 2039,
- 4093,
- 8191,
- 16381,
- 32749,
- 65521,
- 131071,
- 262139,
- 524287,
- 1048573,
- 2097143,
- 4194301,
- 8388593,
- 16777213,
- 33554393,
- 67108859,
- 134217689,
- 268435399,
- 536870909,
- 1073741789,
- /* 4294967291 */
- ((unsigned long) 2147483647) + ((unsigned long) 2147483644),
- };
- const unsigned long *low = &primes[0];
- const unsigned long *high = &primes[ARRAY_SIZE(primes)];
-
- while (low != high) {
- const unsigned long *mid = low + (high - low) / 2;
- if (n > *mid)
- low = mid + 1;
- else
- high = mid;
- }
-
-#if 0
- /* If we've run out of primes, abort. */
- if (n > *low) {
- fprintf(stderr, "Cannot find prime bigger than %lu\n", n);
- abort();
- }
-#endif
-
- return *low;
-}
-
-struct funcdesc_ht
-{
- /* Table itself */
- struct funcdesc_value **entries;
-
- /* Current size (in entries) of the hash table */
- size_t size;
-
- /* Current number of elements */
- size_t n_elements;
-};
-
-static __always_inline int
-hash_pointer(const void *p)
-{
- return (int) ((long)p >> 3);
-}
-
-static __always_inline struct funcdesc_ht *
-htab_create(void)
-{
- struct funcdesc_ht *ht = _dl_malloc(sizeof(*ht));
- size_t ent_size;
-
- if (!ht)
- return NULL;
- ht->size = 3;
- ent_size = sizeof(struct funcdesc_ht_value *) * ht->size;
- ht->entries = _dl_malloc(ent_size);
- if (!ht->entries)
- return NULL;
-
- ht->n_elements = 0;
- _dl_memset(ht->entries, 0, ent_size);
-
- return ht;
-}
-
-/*
- * This is only called from _dl_loadaddr_unmap, so it's safe to call
- * _dl_free(). See the discussion below.
- */
-static __always_inline void
-htab_delete(struct funcdesc_ht *htab)
-{
- size_t i;
-
- for (i = htab->size - 1; i >= 0; i--)
- if (htab->entries[i])
- _dl_free(htab->entries[i]);
-
- _dl_free(htab->entries);
- _dl_free(htab);
-}
-
-/*
- * Similar to htab_find_slot, but without several unwanted side effects:
- * - Does not call htab->eq_f when it finds an existing entry.
- * - Does not change the count of elements/searches/collisions in the
- * hash table.
- * This function also assumes there are no deleted entries in the table.
- * HASH is the hash value for the element to be inserted.
- */
-static __always_inline struct funcdesc_value **
-find_empty_slot_for_expand(struct funcdesc_ht *htab, int hash)
-{
- size_t size = htab->size;
- unsigned int index = hash % size;
- struct funcdesc_value **slot = htab->entries + index;
- int hash2;
-
- if (!*slot)
- return slot;
-
- hash2 = 1 + hash % (size - 2);
- for (;;) {
- index += hash2;
- if (index >= size)
- index -= size;
-
- slot = htab->entries + index;
- if (!*slot)
- return slot;
- }
-}
-
-/*
- * The following function changes size of memory allocated for the
- * entries and repeatedly inserts the table elements. The occupancy
- * of the table after the call will be about 50%. Naturally the hash
- * table must already exist. Remember also that the place of the
- * table entries is changed. If memory allocation failures are allowed,
- * this function will return zero, indicating that the table could not be
- * expanded. If all goes well, it will return a non-zero value.
- */
-static __always_inline int
-htab_expand(struct funcdesc_ht *htab)
-{
- struct funcdesc_value **oentries;
- struct funcdesc_value **olimit;
- struct funcdesc_value **p;
- struct funcdesc_value **nentries;
- size_t nsize;
-
- oentries = htab->entries;
- olimit = oentries + htab->size;
-
- /*
- * Resize only when table after removal of unused elements is either
- * too full or too empty.
- */
- if (htab->n_elements * 2 > htab->size)
- nsize = higher_prime_number(htab->n_elements * 2);
- else
- nsize = htab->size;
-
- nentries = _dl_malloc(sizeof(*nentries) * nsize);
- _dl_memset(nentries, 0, sizeof(*nentries) * nsize);
- if (nentries == NULL)
- return 0;
- htab->entries = nentries;
- htab->size = nsize;
-
- p = oentries;
- do {
- if (*p)
- *find_empty_slot_for_expand(htab,
hash_pointer((*p)->entry_point)) = *p;
- p++;
- } while (p < olimit);
-
-#if 0
- /*
- * We can't tell whether this was allocated by the _dl_malloc()
- * built into ld.so or malloc() in the main executable or libc,
- * and calling free() for something that wasn't malloc()ed could
- * do Very Bad Things (TM). Take the conservative approach
- * here, potentially wasting as much memory as actually used by
- * the hash table, even if multiple growths occur. That's not
- * so bad as to require some overengineered solution that would
- * enable us to keep track of how it was allocated.
- */
- _dl_free(oentries);
-#endif
- return 1;
-}
-
-/*
- * This function searches for a hash table slot containing an entry
- * equal to the given element. To delete an entry, call this with
- * INSERT = 0, then call htab_clear_slot on the slot returned (possibly
- * after doing some checks). To insert an entry, call this with
- * INSERT = 1, then write the value you want into the returned slot.
- * When inserting an entry, NULL may be returned if memory allocation
- * fails.
- */
-static __always_inline struct funcdesc_value **
-htab_find_slot(struct funcdesc_ht *htab, void *ptr, int insert)
-{
- unsigned int index;
- int hash, hash2;
- size_t size;
- struct funcdesc_value **entry;
-
- if (htab->size * 3 <= htab->n_elements * 4 &&
- htab_expand(htab) == 0)
- return NULL;
-
- hash = hash_pointer(ptr);
-
- size = htab->size;
- index = hash % size;
-
- entry = &htab->entries[index];
- if (!*entry)
- goto empty_entry;
- else if ((*entry)->entry_point == ptr)
- return entry;
-
- hash2 = 1 + hash % (size - 2);
- for (;;) {
- index += hash2;
- if (index >= size)
- index -= size;
-
- entry = &htab->entries[index];
- if (!*entry)
- goto empty_entry;
- else if ((*entry)->entry_point == ptr)
- return entry;
- }
-
- empty_entry:
- if (!insert)
- return NULL;
-
- htab->n_elements++;
- return entry;
-}
-
void *
_dl_funcdesc_for (void *entry_point, void *got_value)
{
--
1.8.4.rc3
--- End Message ---
_______________________________________________
uClibc mailing list
[email protected]
http://lists.busybox.net/mailman/listinfo/uclibc
