Re: ABI document

[Florian Weimer <fweimer@redhat.com>]

* Vivek Das Mohapatra:

> +  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

Since the version is stored separately anyway, just say that the hash
covers the name only?  Maybe write this?

  h ← 31 * h + C

And just use uint32_t to express the truncation?

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

Maybe say that the link editor does this?

The description looks correct.

> +  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

I don't understand the “within its bucket” comment.

I think CINDEX increases sequentially among the symbols where CHASH %
nbuckets collides.  Is that it?

> +  - 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

Kind of an odd way of writing this, but I think it's correct.

Thanks,
Florian
-- 
Red Hat GmbH, https://de.redhat.com/ , Registered seat: Grasbrunn,
Commercial register: Amtsgericht Muenchen, HRB 153243,
Managing Directors: Charles Cachera, Brian Klemm, Laurie Krebs, Michael O'Neill