From patchwork Mon Jan 13 16:18:29 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Chris Zankel X-Patchwork-Id: 310231 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from fraxinus.osuosl.org (fraxinus.osuosl.org [140.211.166.137]) by ozlabs.org (Postfix) with ESMTP id 1F7AB2C0092 for ; Tue, 14 Jan 2014 03:18:33 +1100 (EST) Received: from localhost (localhost [127.0.0.1]) by fraxinus.osuosl.org (Postfix) with ESMTP id 1CB1E8B64C; Mon, 13 Jan 2014 16:18:32 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from fraxinus.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id y3eks9HLq4dD; Mon, 13 Jan 2014 16:18:28 +0000 (UTC) Received: from ash.osuosl.org (ash.osuosl.org [140.211.166.34]) by fraxinus.osuosl.org (Postfix) with ESMTP id 435D18B617; Mon, 13 Jan 2014 16:18:28 +0000 (UTC) X-Original-To: uclibc@lists.busybox.net Delivered-To: uclibc@osuosl.org Received: from silver.osuosl.org (silver.osuosl.org [140.211.166.136]) by ash.osuosl.org (Postfix) with ESMTP id EB6D11C21AF for ; Mon, 13 Jan 2014 16:18:26 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by silver.osuosl.org (Postfix) with ESMTP id E665732A4A for ; Mon, 13 Jan 2014 16:18:26 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from silver.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id at40-wxh9dVj for ; Mon, 13 Jan 2014 16:18:25 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from mail-pd0-f176.google.com (mail-pd0-f176.google.com [209.85.192.176]) by silver.osuosl.org (Postfix) with ESMTPS id EE8183101A for ; Mon, 13 Jan 2014 16:18:24 +0000 (UTC) Received: by mail-pd0-f176.google.com with SMTP id r10so3613775pdi.21 for ; Mon, 13 Jan 2014 08:18:24 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:message-id:date:from:user-agent:mime-version:to :cc:subject:references:in-reply-to:content-type; bh=mtrMBgVP16Fs/pWEfC/2fj1rESz1CH0AVtfxZrXNIFQ=; b=k3KpHvIb2CpDmYJFsFQFSx1Wg9ycK3diL1nphXBATkg1LR1qMbsouTjxzx5IRnwYCp A5WgLFIOgsXSqm2SjirS4neXrYbP8yMlkG8pJnuxY30MfKgYMiQZF/EXz2qf5XLprsCH euxWmltqHvhPFGyNlWN9jWDFSoKdetXcfCN82ciToCvHVumyRuAnPqL3p599FGXbMjZI tGl3rQZSgoQNnnrfw2AtlItGBvGbPp0t3D11Zj+negSzcygP7q2lDOXFoF+DaQaoNYYu xus63BHj3/DNh2AajWwkcBLjUEZoOun6+eYpUVranP2XdW75xhb3O1Rsft6Wn2LrmK2/ 5mVg== X-Gm-Message-State: ALoCoQkhj4JedZBKNZmhIadUr8nMtQ+6wkToNfYijjTa8gX+M8HKb59MldkTk8QqzAa5VYihZO9E X-Received: by 10.66.156.137 with SMTP id we9mr11717888pab.30.1389629904683; Mon, 13 Jan 2014 08:18:24 -0800 (PST) Received: from chriss-mbp.zankel.net (c-67-161-9-61.hsd1.ca.comcast.net. [67.161.9.61]) by mx.google.com with ESMTPSA id zc6sm23994088pab.18.2014.01.13.08.18.22 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Mon, 13 Jan 2014 08:18:23 -0800 (PST) Message-ID: <52D411D5.4000108@zankel.net> Date: Mon, 13 Jan 2014 08:18:29 -0800 From: Chris Zankel User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.9; rv:24.0) Gecko/20100101 Thunderbird/24.2.0 MIME-Version: 1.0 To: uclibc@uclibc.org Subject: Re: [PATCH 2/2] ldso: make hashcode handling more generic References: <1f3a9aacda749bd59246003a9d9590a9889f9dbe.1383729687.git.baruch@tkos.co.il> <20131107052747.GS24286@brightrain.aerifal.cx> <527C0BB3.5010901@zankel.net> In-Reply-To: <527C0BB3.5010901@zankel.net> Cc: Rich Felker X-BeenThere: uclibc@uclibc.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Discussion and development of uClibc \(the embedded C library\)" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: uclibc-bounces@uclibc.org Sender: uclibc-bounces@uclibc.org 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 Signed-off-by: Baruch Siach --- 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;