public inbox for gnu-gabi@sourceware.org
 help / color / mirror / Atom feed
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


  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).