diff mbox

[2/2] ldso: make hashcode handling more generic

Message ID 1f3a9aacda749bd59246003a9d9590a9889f9dbe.1383729687.git.baruch@tkos.co.il
State New
Headers show

Commit Message

Baruch Siach Nov. 6, 2013, 9:23 a.m. UTC 
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 <chris@zankel.net>
Signed-off-by: Baruch Siach <baruch@tkos.co.il>
---
 ldso/include/inline-hashtab.h | 41 ++++++++++++++++++-----------------------
 ldso/ldso/fdpic/dl-inlines.h  | 19 +++++++++++++++++--
 2 files changed, 35 insertions(+), 25 deletions(-)

Comments

Rich Felker Nov. 7, 2013, 5:27 a.m. UTC | #1 
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
similar aliasing violations. This should be investigated before any
further changes are made.

Rich
Chris Zankel Nov. 7, 2013, 9:52 p.m. UTC | #2 
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
diff mbox

Patch

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;