From: "Vivek Das Mohapatra" <vivek@collabora.com>
To: Florian Weimer <fweimer@redhat.com>
Cc: Mark Wielaard <mark@klomp.org>,
GNU gABI gnu-gabi <gnu-gabi@sourceware.org>
Subject: Re: ABI document
Date: Tue, 8 Sep 2020 13:09:47 +0100 (BST) [thread overview]
Message-ID: <alpine.DEB.2.21.2009081308560.31454@noise.cbg.collabora.co.uk> (raw)
In-Reply-To: <alpine.DEB.2.21.2009021818280.31454@noise.cbg.collabora.co.uk>
[-- Attachment #1: Type: text/plain, Size: 163 bytes --]
On Wed, 2 Sep 2020, Vivek Das Mohapatra via Gnu-gabi wrote:
This patch is cumulative with the last one (again)
It adds a description of the GNU ELF hash section
[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: Type: text/x-diff; name=0003-Document-DT_GNU_HASH-SHT_GNU_HASH-contents.patch, Size: 5935 bytes --]
From 33ecd5f2c552e23ae946fb967a312f3af73c8773 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Vivek=20Das=C2=A0Mohapatra?= <vivek@collabora.com>
Date: Tue, 8 Sep 2020 13:03:43 +0100
Subject: [PATCH] Document DT_GNU_HASH / SHT_GNU_HASH contents
The GNU ELF hash table has not been documented other than
a in mailing list posts and the actual implementation.
---
program-loading-and-dynamic-linking.txt | 117 +++++++++++++++++++++++-
1 file changed, 116 insertions(+), 1 deletion(-)
diff --git a/program-loading-and-dynamic-linking.txt b/program-loading-and-dynamic-linking.txt
index f7f4284..a37ac34 100644
--- a/program-loading-and-dynamic-linking.txt
+++ b/program-loading-and-dynamic-linking.txt
@@ -232,7 +232,122 @@ DT_GNU_HASH 0x6ffffef5
The d_ptr value gives the location of the GNU style symbol hash table.
- DOCUMENTME: find the canonical spec for this (or reverse e from glibc source)
+ The GNU hash of a symbol is computed as follows:
+ - extract the NAME of the symbol
+ - examples: 'foo@version-info' becomes 'foo'; 'bar' remains 'bar'
+ - unsigned long h ← 5381
+ - for each unsigned character C in NAME, starting at position 0:
+ - h ← (h << 5) + h + C;
+ - HASH ← h & 0xffffffff // 32 bit value
+
+ Hash Table contents:
+
+ bitmask-bits is a power of 2.
+ It is at least 32 (on 32 bit); at least 64 on 64 bit architectures.
+ There are other restrictions, see elflink.c in the binutils-gdb/bfd source.
+
+ The bucket in which a symbol's hash entry is found is:
+
+ gnu-hash( symbol-name ) % nbuckets
+
+ The table is divided into 4 parts:
+ ----------------------------------------------------------------------------
+ Part 1 (metadata):
+
+ - nbuckets : 4 byte native integer. Number of buckets
+ A bucket occupies 32 bits.
+
+ - symoffset : 4 byte native integer.
+ Starting index of first "real" symbol in the ".dynsym"
+ section, See below.
+
+ - bitmask-words: 4 byte native integer.
+ The number of ELFCLASS<SIZE> words in part 2 of the table.
+ On 64-bit architctures: bitmask-bits / 64
+ And on 32-bit ones : bitmask-bits / 32
+
+ - bloom-shift : 4 byte native integer.
+ The shift-count used in the bloom filter.
+
+ symoffset:
+ There are synthetic symbols - one for each section in the linker output.
+ symoffset gives the number of such synthetic symbols ( which cannot be
+ looked up via the GNU hash section described here ).
+
+ NB: symbols that _can_ be looked up via the GNU hash must be stored in
+ the ".dynsym" section in ascending order of bucket.
+ That is the ordering is determined by:
+
+ gnu-hash( symbol-name ) % nbuckets
+
+ ----------------------------------------------------------------------------
+ Part 2 (the bloom filter bitmask):
+
+ - bloom : ElfW(Addr)[ bitmask-words ]
+
+ For each symbol [name] S the following is carried out:
+ - C ← __ELF_NATIVE_CLASS /* ie 32 on ELF32, 64 on ELF64 */
+ - H ← gnu-hash( S )
+ - BWORD ← (H / C) & (bitmask-words - 1)
+ - in bloom[ BWORD ] set:
+ - bit H & (C - 1)
+ - bit (H >> bloom-shift) & (C - 1)
+
+ NOTE: The discussions and examples of this that are around may
+ use modulo operations instead of the logical-ands you see above:
+ This is not an error or divergence since:
+
+ x % 2ⁿ ≡ x & (2ⁿ - 1) /* NB: where x is unsigned */
+
+ NOTE: For those unfamiliar with bloom filters: If either bit
+ described above is NOT SET then the hash is DEFINITELY NOT
+ present in the table and lookup need proceed no further.
+
+ ----------------------------------------------------------------------------
+ Part 3 (the bucket metadata):
+
+ - bucket[nbuckets] : Array of 4 byte native integers, giving:
+
+ For each bucket:
+ - The INDEX of the first symbol in that bucket,
+ OR 0 if no symbols in that bucket.
+
+ NOTE: these indices give the offset into the ".dynsym" section.
+ For the offset into the bucket data in part 4 of the table, see below:
+ ----------------------------------------------------------------------------
+ Part 4 (the chains, or actual bucket data):
+
+ - chain : Contiguous arrays of pseudo hash values combining the
+ hash values and the index of the related symbol
+ Each pseudo hash value is a 4 byte native integer.
+
+ ElfW(Word)[number-of-symbols].
+
+ For each symbol [name] S:
+
+ - CHASH ← gnu-hash( S )
+ - BUCKET ← CHASH % nbuckets
+ - CINDEX ← position of the symbol _within_ its bucket
+ 0 for the first symbol, 1 for the second and so forth
+ - if this is the last symbol in the bucket:
+ - CHASH ← CHASH | 1 /* set the least bit */
+ - else
+ - CHASH ← CHASH & ~1 /* unset the least bit */
+ - BYTE-OFFSET ← (bucket[BUCKET] + CINDEX - symoffset) * 4
+ - CHAIN-ADDR ← ((char *)&bucket[nbuckets]) + BYTE-OFFSET
+ - *(ElfW(Word) *)(CHAIN-ADDR) ← CHASH
+
+ The least bit of a pseudo-hash value being set indicates that
+ this entry is the last in the chain - this is used during lookupg
+ since unlike the stock ELF hash the GNU hash does not use linked
+ lists to store its chains.
+
+ Reference: https://sourceware.org/legacy-ml/binutils/2006-10/msg00377.html
+ Reference: https://flapenguin.me/elf-dt-gnu-hash
+ Reference: https://sourceware.org/git/?p=binutils-gdb.git;a=blob;f=bfd/elflink.c;h=1384c1a46b83b55876b6a73dbcba0386a458063b;hb=HEAD#l7263
+ bfd_elf_size_dynsym_hash_dynstr
+ Reference: https://sourceware.org/git/?p=glibc.git;a=blob;f=elf/dl-lookup.c;h=807f3ea9b67489b3116535b7c433c774a72e4c29;hb=HEAD#l357
+ do_lookup_x
Section Headers
===============
--
2.20.1
next prev parent reply other threads:[~2020-09-08 12:09 UTC|newest]
Thread overview: 24+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-07-29 11:47 Florian Weimer
2020-07-29 11:53 ` Mark Wielaard
2020-07-29 12:15 ` H.J. Lu
2020-07-29 12:22 ` Florian Weimer
2020-08-14 9:51 ` Vivek Das Mohapatra
2020-08-14 10:58 ` Mark Wielaard
2020-08-14 11:33 ` Vivek Das Mohapatra
2020-08-14 15:17 ` Mark Wielaard
2020-08-27 16:52 ` Vivek Das Mohapatra
2020-08-31 12:54 ` Florian Weimer
2020-09-02 17:29 ` Vivek Das Mohapatra
2020-09-08 12:09 ` Vivek Das Mohapatra [this message]
2020-09-16 13:57 ` Vivek Das Mohapatra
2020-09-21 13:03 ` Florian Weimer
2020-09-21 12:36 ` Florian Weimer
2020-11-27 15:40 ` Vivek Das Mohapatra
2020-11-30 17:36 ` Florian Weimer
2020-12-09 16:59 ` Vivek Das Mohapatra
2022-08-25 8:11 ` Florian Weimer
2022-08-25 15:38 ` Carlos O'Donell
2022-08-30 11:55 ` Vivek Dasmohapatra
2022-08-30 12:12 ` Florian Weimer
2022-08-30 15:17 ` Vivek Dasmohapatra
2020-07-29 12:56 ` Jose E. Marchesi
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=alpine.DEB.2.21.2009081308560.31454@noise.cbg.collabora.co.uk \
--to=vivek@collabora.com \
--cc=fweimer@redhat.com \
--cc=gnu-gabi@sourceware.org \
--cc=mark@klomp.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).