Bug 13546 - improve map hashing
Summary: improve map hashing
Status: RESOLVED FIXED
Alias: None
Product: systemtap
Classification: Unclassified
Component: runtime (show other bugs)
Version: unspecified
: P2 normal
Target Milestone: ---
Assignee: Chris Meek
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2011-12-31 01:32 UTC by Frank Ch. Eigler
Modified: 2012-01-26 19:39 UTC (History)
1 user (show)

See Also:
Host:
Target:
Build:
Last reconfirmed:


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Frank Ch. Eigler 2011-12-31 01:32:22 UTC
The runtime/map* functions have several weaknesses w.r.t. hashing
that we should improve.

1) HASH_TABLE_BITS/SIZE should probably be a function of MAXMAPENTRIES.
2) str_hash() should be more hashy.  It looks rather wimpy.
3) With deliberate hash-collision-inducing data conceivably fed to stap,
   we should investigate salting the map FOO_hash functions with some
   runtime-random value, such as a few bytes collected at startup time with
   get_random_bytes(), as in

static unsigned long stap_hash_seed; /* init during module startup */
static unsigned int int64_hash (const int64_t v)
{
        return (unsigned int)hash_long (((unsigned long)v) ^ stap_hash_seed,
                                        HASH_TABLE_BITS);
}
/* and similarly for str_hash */
Comment 1 Chris Meek 2012-01-26 19:39:10 UTC
Fixed in commit: f99a86ea97ab942378d72d696bd5a07b51ba8a51

- Made str_hash() in map.c more hashy.
- Introduced a runtime random seed to the hash calculations
  to reduce the chance of deliberate hash collision inducing
  attacks.
- Made the HASH_TABLE_SIZE depend on MAXMAPENTRIES, rather than
  just a static 256. This effectivly increases the size of the
  hash table.