Create a hash table data structure to represent hash table sections

[mjhouse]

Overview

NOT ACCURATE. SEE THIS COMMENT FOR MORE.

A hash table section is used to very quickly find a symbol by it's name. Given the name, the hash table can be used in an iterative way to find potential matching symbols until the symbol with the correct name is found.

The hash table is made up of:

1. A number representing the number of "buckets" (nbucket)
2. A number representing the number of "chains" (nchain)
3. A "bucket" array of type Elf32_Word or Elf64_Word elements
4. A "chain" array of indices into the symbol table (what size? same as buckets?)

To find a symbol:

• A hashing function (see reference code) takes a string and converts it to a long value x
• A symbol index can be calculated with bucket [ x % nbucket]
• The symbol should be checked to see if the name is correct
• If it's not, the same index can be used to access a "chain" item: chain[x] = y
• The y can be used as an index into the symbol table for the next match
• The symbol should be checked to see if the name is correct
• If it's not, the y can be used to access the next "chain" item: chain[y] = z
• And so on, until the actual symbol is found

Reference

See: https://docs.oracle.com/cd/E23824_01/html/819-0690/chapter6-48031.html

Reference hash function (generated by GPT-4, so verify it):

fn elf_hash(name: &[u8]) -> u32 {
    let mut h: u32 = 0;
    let mut g: u32;

    for &c in name {
        h = (h << 4) + c as u32;
        g = h & 0xf000_0000;

        if g != 0 {
            h ^= g >> 24;
            h &= !g;
        }
    }

    h
}

Notes

• This data structure should have add/remove/append methods etc.
• When a symbol is removed from a symbol table, it should also be removed from the appropriate hash table
• The symbol table that the hash section is associated with is referenced through the sh_link attribute in the section header

[mjhouse]

The more common hash section used in modern ELF is DT_GNU_HASH, not DT_HASH as described above. DT_GNU_HASH includes a bloom filter and is significantly more complicated. Refer to the following pages for more information:

https://blogs.oracle.com/solaris/post/gnu-hash-elf-sections
https://flapenguin.me/elf-dt-gnu-hash