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

login
register
mail settings
Submitter Chris Zankel
Date Jan. 13, 2014, 4:18 p.m.
Message ID <52D411D5.4000108@zankel.net>
Download mbox | patch
Permalink /patch/310231/
State New
Headers show

Comments

Chris Zankel - Jan. 13, 2014, 4:18 p.m.
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
>
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(-)
aldot - Jan. 22, 2014, 10:15 p.m.
On 13 January 2014 17:18, Chris Zankel <chris@zankel.net> wrote:
> 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).

I did not have a chance to look at it yet, no.
I've been side-tracked attempting to understand gold's POV on TLS (or
static tls or however it is called, think dreaded tsd. Holler if that
rings a bell,
i could use somebody filling in my gaps of interest in that area ;).. Going
through the backlog now but it's getting too late for me today to continue.
Chris Zankel - Jan. 23, 2014, 1:11 a.m.
Hi Bernhard,

On 1/22/14, 2:15 PM, Bernhard Reutner-Fischer wrote:
> On 13 January 2014 17:18, Chris Zankel <chris@zankel.net> wrote:
>> 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).
> I did not have a chance to look at it yet, no.
> I've been side-tracked attempting to understand gold's POV on TLS (or
> static tls or however it is called, think dreaded tsd. Holler if that
> rings a bell,
Do you have any pointers to it? I'm not sure I know who or what 'gold' 
is or means?
I'd be curious, though...
> i could use somebody filling in my gaps of interest in that area ;).. Going
> through the backlog now but it's getting too late for me today to continue.
No worries. I'm just glad you haven't forgotten :-)

Regarding those patches, they should  be transparent for all other 
architectures, ie. not change anything, but are a requisite for to add 
TLS/NPTL support for Xtensa. For Xtensa, we have to use what's called 
TLS descriptors, and which will come in additional patches.

The two changes in that patch are:
- change struct funcdesc_value** to void**, which I think is save,
- pass the two functions, hash_pointer and eq_pointer as additional 
arguments to htab_find_slot(), but any advanced compiler should just 
inline them again.

(Note that the entire patch series for Xtensa is under 
https://github.com/foss-xtensa/uClibc.git in the xtensa_nptl branch)

Thanks,
-Chris
Baruch Siach - Jan. 23, 2014, 10:11 a.m.
Hi Chris,

On Wed, Jan 22, 2014 at 05:11:26PM -0800, Chris Zankel wrote:
> On 1/22/14, 2:15 PM, Bernhard Reutner-Fischer wrote:
> >On 13 January 2014 17:18, Chris Zankel <chris@zankel.net> wrote:
> >>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).
> >I did not have a chance to look at it yet, no.
> >I've been side-tracked attempting to understand gold's POV on TLS (or
> >static tls or however it is called, think dreaded tsd. Holler if that
> >rings a bell,
> Do you have any pointers to it? I'm not sure I know who or what
> 'gold' is or means?
> I'd be curious, though...

gold is the next generation binutils linker. Debian used to have a dedicated 
package for it, binutils-gold, but now it is part of the binutils package. Try 
'gold --version'.

baruch

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;