DynamoRIO/dynamorio
1
0
Fork 0
mirror of https://github.com/DynamoRIO/dynamorio.git synced 2026-10-12 02:02:04 +00:00
Code Issues Packages Projects Releases Wiki Activity
Files
master
dynamorio/core/hashtable.c
T
Derek Bruening f88e38abc3 i#8001 shared defs: Use TESTANY instead of TEST (#8032) 
In preparation of moving the TEST* defines into
dr_project_wide_headers.h, we replace all uses of TEST with the
equivalent TESTANY. Although we avoid exposing
dr_project_wide_headers.h in DR_API headers, it is exposed in
drmemtrace's headers where TEST causes collisions with third-party code
such as googletest.

Issue: #8001
2026-07-30 11:39:13 -04:00

554 lines
22 KiB
C
Raw Permalink Blame History

/* **********************************************************
* Copyright (c) 2011-2026 Google, Inc. All rights reserved.
* Copyright (c) 2006-2010 VMware, Inc. All rights reserved.
* **********************************************************/
/*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* * Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
*
* * Redistributions in binary form must reproduce the above copyright notice,
* this list of conditions and the following disclaimer in the documentation
* and/or other materials provided with the distribution.
*
* * Neither the name of VMware, Inc. nor the names of its contributors may be
* used to endorse or promote products derived from this software without
* specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL VMWARE, INC. OR CONTRIBUTORS BE LIABLE
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
* SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
* CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
* DAMAGE.
*/
/* Copyright (c) 2006-2007 Determina Corp. */
#include "globals.h"
#include "hashtable.h"
/* Returns the proper number of hash bits to have a capacity with the
* given load for the given number of entries
*/
uint
hashtable_bits_given_entries(uint entries, uint load)
{
/* Add 1 for the sentinel */
return hashtable_num_bits(((entries + 1) * 100) / load);
}
/*******************************************************************************
* GENERIC HASHTABLE INSTANTIATION
*
* We save code space by having hashtables that don't need special inlining
* use the same code. We also provide a more "normal" hashtable interface,
* with key and payload separation and payload freeing.
*
* We only support caller synchronization currently (the caller should
* use TABLE_RWLOCK) but we could provide a flag specifying whether
* synch is intra-routine or not.
*/
/* 2 macros w/ name and types are duplicated in fragment.h -- keep in sync */
#define NAME_KEY generic
#define ENTRY_TYPE generic_entry_t *
/* not defining HASHTABLE_USE_LOOKUPTABLE */
#define ENTRY_TAG(f) ((f)->key)
#define ENTRY_EMPTY NULL
/* we assume that 1 is not a valid value: that keys are in fact pointers */
#define ENTRY_SENTINEL ((generic_entry_t *)(ptr_uint_t)1)
#define ENTRY_IS_EMPTY(f) ((f) == NULL)
#define ENTRY_IS_SENTINEL(f) ((f) == ENTRY_SENTINEL)
#define ENTRY_IS_INVALID(f) (false) /* no invalid entries */
#define ENTRIES_ARE_EQUAL(t, f, g) (ENTRY_TAG(f) == ENTRY_TAG(g))
/* if usage becomes widespread we may need to parameterize this */
#define HASHTABLE_WHICH_HEAP(flags) (ACCT_OTHER)
#define HTLOCK_RANK table_rwlock
#define HASHTABLE_SUPPORT_PERSISTENCE 0
#include "hashtablex.h"
/* all defines are undef-ed at end of hashtablex.h */
#define GENERIC_ENTRY_IS_REAL(e) ((e) != NULL && (e) != (generic_entry_t *)(ptr_uint_t)1)
/* required routines for hashtable interface */
static void
hashtable_generic_init_internal_custom(dcontext_t *dcontext, generic_table_t *htable)
{ /* nothing */
}
static void
hashtable_generic_resized_custom(dcontext_t *dcontext, generic_table_t *htable,
uint old_capacity, generic_entry_t **old_table,
generic_entry_t **old_table_unaligned,
uint old_ref_count, uint old_table_flags)
{ /* nothing */
}
#ifdef DEBUG
static void
hashtable_generic_study_custom(dcontext_t *dcontext, generic_table_t *htable,
uint entries_inc /*amnt table->entries was pre-inced*/)
{ /* nothing */
}
#endif
static void
hashtable_generic_free_entry(dcontext_t *dcontext, generic_table_t *htable,
generic_entry_t *entry)
{
if (htable->free_payload_func != NULL)
(*htable->free_payload_func)(dcontext, entry->payload);
HEAP_TYPE_FREE(dcontext, entry, generic_entry_t, ACCT_OTHER, PROTECTED);
}
/* Wrapper routines to implement our generic_entry_t and free-func layer */
generic_table_t *
generic_hash_create(dcontext_t *dcontext, uint bits, uint load_factor_percent,
uint table_flags,
void (*free_payload_func)(dcontext_t *, void *)
_IF_DEBUG(const char *table_name))
{
generic_table_t *table =
HEAP_TYPE_ALLOC(dcontext, generic_table_t, ACCT_OTHER, PROTECTED);
hashtable_generic_init(dcontext, table, bits, load_factor_percent,
(hash_function_t)INTERNAL_OPTION(alt_hash_func),
0 /* hash_mask_offset */, table_flags _IF_DEBUG(table_name));
table->free_payload_func = free_payload_func;
return table;
}
void
generic_hash_clear(dcontext_t *dcontext, generic_table_t *htable)
{
hashtable_generic_clear(dcontext, htable);
}
void
generic_hash_destroy(dcontext_t *dcontext, generic_table_t *htable)
{
/* XXX: why doesn't hashtablex.h walk the table and call the free routine
* in free() or in remove()? It only seems to do it for range_remove().
*/
uint i;
generic_entry_t *e;
for (i = 0; i < htable->capacity; i++) {
e = htable->table[i];
/* must check for sentinel */
if (GENERIC_ENTRY_IS_REAL(e)) {
hashtable_generic_free_entry(dcontext, htable, e);
}
}
hashtable_generic_free(dcontext, htable);
HEAP_TYPE_FREE(dcontext, htable, generic_table_t, ACCT_OTHER, PROTECTED);
}
void *
generic_hash_lookup(dcontext_t *dcontext, generic_table_t *htable, ptr_uint_t key)
{
generic_entry_t *e = hashtable_generic_lookup(dcontext, key, htable);
if (e != NULL)
return e->payload;
return NULL;
}
void
generic_hash_add(dcontext_t *dcontext, generic_table_t *htable, ptr_uint_t key,
void *payload)
{
generic_entry_t *e =
HEAP_TYPE_ALLOC(dcontext, generic_entry_t, ACCT_OTHER, PROTECTED);
e->key = key;
e->payload = payload;
hashtable_generic_add(dcontext, e, htable);
}
bool
generic_hash_remove(dcontext_t *dcontext, generic_table_t *htable, ptr_uint_t key)
{
/* There is no remove routine that takes in a tag, nor one that frees the
* payload, so we construct it.
*/
generic_entry_t *e = hashtable_generic_lookup(dcontext, key, htable);
if (e != NULL && hashtable_generic_remove(e, htable)) {
hashtable_generic_free_entry(dcontext, htable, e);
return true;
}
return false;
}
uint
generic_hash_range_remove(dcontext_t *dcontext, generic_table_t *htable, ptr_uint_t start,
ptr_uint_t end)
{
return hashtable_generic_range_remove(dcontext, htable, start, end, NULL);
}
/* pass 0 to start. returns -1 when there are no more entries. */
int
generic_hash_iterate_next(dcontext_t *dcontext, generic_table_t *htable, int iter,
DR_PARAM_OUT ptr_uint_t *key, DR_PARAM_OUT void **payload)
{
int i;
generic_entry_t *e = NULL;
for (i = iter; i < (int)htable->capacity; i++) {
e = htable->table[i];
if (!GENERIC_ENTRY_IS_REAL(e))
continue;
else
break;
}
if (i >= (int)htable->capacity)
return -1;
ASSERT(e != NULL);
if (key != NULL)
*key = e->key;
if (payload != NULL)
*payload = e->payload;
return i + 1;
}
/* removes from the hashtable in a safe way during iteration. returns an
* updated iteration index to pass to generic_hash_iterate_next().
*/
int
generic_hash_iterate_remove(dcontext_t *dcontext, generic_table_t *htable, int iter,
ptr_uint_t key)
{
generic_entry_t *e = hashtable_generic_lookup(dcontext, key, htable);
uint hindex;
generic_entry_t **rm = hashtable_generic_lookup_for_removal(e, htable, &hindex);
int res = iter;
if (rm != NULL) {
if (hashtable_generic_remove_helper(htable, hindex, rm)) {
/* pulled entry from start to here so skip it as we've already seen it */
} else {
/* pulled entry from below us, so step back */
res--;
}
hashtable_generic_free_entry(dcontext, htable, e);
}
return res;
}
/*******************************************************************************
* STRING KEY HASHTABLE INSTANTIATION
*
* We only support caller synchronization currently (the caller should
* use TABLE_RWLOCK).
*/
/* 2 macros w/ name and types are duplicated in fragment.h -- keep in sync */
#define NAME_KEY strhash
#define ENTRY_TYPE strhash_entry_t *
/* not defining HASHTABLE_USE_LOOKUPTABLE */
#define ENTRY_TAG(f) (ptr_uint_t)((f)->key)
#define ENTRY_EMPTY NULL
/* we assume that 1 is not a valid value: that keys are in fact pointers */
#define STRHASH_SENTINEL ((strhash_entry_t *)(ptr_uint_t)1)
#define ENTRY_SENTINEL STRHASH_SENTINEL
#define ENTRY_IS_EMPTY(f) ((f) == NULL)
#define ENTRY_IS_SENTINEL(f) ((f) == STRHASH_SENTINEL)
#define ENTRY_IS_INVALID(f) (false) /* no invalid entries */
#define TAGS_ARE_EQUAL(table, s1, s2) \
(strhash_key_cmp(table, (const char *)(s1), (const char *)(s2)))
#define ENTRIES_ARE_EQUAL(table, f, g) (TAGS_ARE_EQUAL(table, (f)->key, (g)->key))
/* if usage becomes widespread we may need to parameterize this */
#define HASHTABLE_WHICH_HEAP(flags) (ACCT_OTHER)
#define HTLOCK_RANK table_rwlock
#define HASHTABLE_SUPPORT_PERSISTENCE 0
/* case sensitive by default */
#define STRHASH_CASE_INSENSITIVE HASHTABLE_CUSTOM_FLAGS_START
static inline bool
strhash_key_cmp(strhash_table_t *htable, const char *s1, const char *s2)
{
if (TESTANY(STRHASH_CASE_INSENSITIVE, htable->table_flags))
return strcasecmp(s1, s2) == 0;
else
return strcmp(s1, s2) == 0;
}
#include "hashtablex.h"
/* all defines are undef-ed at end of hashtablex.h */
#define STRHASH_ENTRY_IS_REAL(e) ((e) != NULL && (e) != STRHASH_SENTINEL)
/* required routines for hashtable interface */
static void
hashtable_strhash_init_internal_custom(dcontext_t *dcontext, strhash_table_t *htable)
{ /* nothing */
}
static void
hashtable_strhash_resized_custom(dcontext_t *dcontext, strhash_table_t *htable,
uint old_capacity, strhash_entry_t **old_table,
strhash_entry_t **old_table_unaligned,
uint old_ref_count, uint old_table_flags)
{ /* nothing */
}
#ifdef DEBUG
static void
hashtable_strhash_study_custom(dcontext_t *dcontext, strhash_table_t *htable,
uint entries_inc /*amnt table->entries was pre-inced*/)
{ /* nothing */
}
#endif
static void
hashtable_strhash_free_entry(dcontext_t *dcontext, strhash_table_t *htable,
strhash_entry_t *entry)
{
if (htable->free_payload_func != NULL)
(*htable->free_payload_func)(entry->payload);
HEAP_TYPE_FREE(dcontext, entry, strhash_entry_t, ACCT_OTHER, PROTECTED);
}
/* Wrapper routines to implement our strhash_entry_t and free-func layer */
strhash_table_t *
strhash_hash_create(dcontext_t *dcontext, uint bits, uint load_factor_percent,
uint table_flags,
void (*free_payload_func)(void *) _IF_DEBUG(const char *table_name))
{
strhash_table_t *table =
HEAP_TYPE_ALLOC(GLOBAL_DCONTEXT, strhash_table_t, ACCT_OTHER, PROTECTED);
hashtable_strhash_init(GLOBAL_DCONTEXT, table, bits, load_factor_percent,
TESTANY(STRHASH_CASE_INSENSITIVE, table_flags)
? HASH_FUNCTION_STRING_NOCASE
: HASH_FUNCTION_STRING,
0 /* hash_mask_offset */, table_flags _IF_DEBUG(table_name));
table->free_payload_func = free_payload_func;
return table;
}
void
strhash_hash_clear(dcontext_t *dcontext, strhash_table_t *htable)
{
hashtable_strhash_clear(dcontext, htable);
}
void
strhash_hash_destroy(dcontext_t *dcontext, strhash_table_t *htable)
{
/* XXX: why doesn't hashtablex.h walk the table and call the free routine
* in free() or in remove()? It only seems to do it for range_remove().
*/
uint i;
strhash_entry_t *e;
for (i = 0; i < htable->capacity; i++) {
e = htable->table[i];
/* must check for sentinel */
if (STRHASH_ENTRY_IS_REAL(e)) {
hashtable_strhash_free_entry(dcontext, htable, e);
}
}
hashtable_strhash_free(dcontext, htable);
HEAP_TYPE_FREE(dcontext, htable, strhash_table_t, ACCT_OTHER, PROTECTED);
}
void *
strhash_hash_lookup(dcontext_t *dcontext, strhash_table_t *htable, const char *key)
{
strhash_entry_t *e = hashtable_strhash_lookup(dcontext, (ptr_uint_t)key, htable);
if (e != NULL)
return e->payload;
return NULL;
}
void
strhash_hash_add(dcontext_t *dcontext, strhash_table_t *htable, const char *key,
void *payload)
{
strhash_entry_t *e =
HEAP_TYPE_ALLOC(dcontext, strhash_entry_t, ACCT_OTHER, PROTECTED);
e->key = key;
e->payload = payload;
hashtable_strhash_add(dcontext, e, htable);
}
bool
strhash_hash_remove(dcontext_t *dcontext, strhash_table_t *htable, const char *key)
{
/* There is no remove routine that takes in a tag, nor one that frees the
* payload, so we construct it
*/
strhash_entry_t *e = hashtable_strhash_lookup(dcontext, (ptr_uint_t)key, htable);
if (e != NULL && hashtable_strhash_remove(e, htable)) {
hashtable_strhash_free_entry(dcontext, htable, e);
return true;
}
return false;
}
/*******************************************************************************/
#ifdef HASHTABLE_STATISTICS
/* caller is responsible for any needed synchronization */
void
print_hashtable_stats(dcontext_t *dcontext, const char *is_final_str,
const char *is_trace_str, const char *lookup_routine_str,
const char *brtype_str, hashtable_statistics_t *lookup_stats)
{
uint64 hits_stat = lookup_stats->hit_stat;
uint64 total_lookups;
if (lookup_stats->hit_stat < lookup_stats->collision_hit_stat) {
/* HACK OVERFLOW: we special case here the case of a single overflow */
/* assuming only one overflow, which is the only case on spec (GAP) */
hits_stat = (uint64)lookup_stats->hit_stat + UINT_MAX + 1;
}
total_lookups =
hits_stat + lookup_stats->miss_stat + lookup_stats->collision_hit_stat;
DOLOG(1, LOG_FRAGMENT | LOG_STATS, {
uint miss_top = 0;
uint miss_bottom = 0;
uint hit_top = 0;
uint hit_bottom = 0;
uint col_top = 0;
uint col_bottom = 0;
if (total_lookups > 0) {
divide_uint64_print(lookup_stats->miss_stat, total_lookups, false, 4,
&miss_top, &miss_bottom);
}
if (hits_stat > 0) {
divide_uint64_print(lookup_stats->collision_hit_stat, hits_stat, false, 4,
&hit_top, &hit_bottom);
divide_uint64_print(hits_stat + lookup_stats->collision_stat, hits_stat,
false, 4, &col_top, &col_bottom);
}
LOG(THREAD, LOG_FRAGMENT | LOG_STATS, 1,
"%s %s table %s%s lookup hits%s: " UINT64_FORMAT_STRING ", "
"misses: %u, total: " UINT64_FORMAT_STRING ", miss%%=%u.%.4u\n",
is_final_str, is_trace_str, lookup_routine_str, brtype_str,
(lookup_stats->hit_stat < lookup_stats->collision_hit_stat) ? "[OVFL]" : "",
hits_stat, lookup_stats->miss_stat, total_lookups, miss_top, miss_bottom);
LOG(THREAD, LOG_FRAGMENT | LOG_STATS, 1,
"%s %s table %s%s "
"collisions: %u, collision hits: %u, "
">2_or_miss: %u, overwrap: %u\n",
is_final_str, is_trace_str, lookup_routine_str, brtype_str,
lookup_stats->collision_stat,
/* XXX: collision hit stats are updated only when inlining IBL head */
lookup_stats->collision_hit_stat,
lookup_stats->collision_stat - lookup_stats->collision_hit_stat,
lookup_stats->overwrap_stat);
LOG(THREAD, LOG_FRAGMENT | LOG_STATS, 1,
"%s %s table %s%s lookup "
" coll%%=%u.%.4u, dyn.avgcoll=%u.%.4u\n",
is_final_str, is_trace_str, lookup_routine_str, brtype_str, hit_top,
hit_bottom, col_top, col_bottom);
if (lookup_stats->race_condition_stat || lookup_stats->unlinked_count_stat) {
LOG(THREAD, LOG_FRAGMENT | LOG_STATS, 1,
"%s %s table %s%s inlined ibl unlinking races: %d, unlinked: %d\n",
is_final_str, is_trace_str, lookup_routine_str, brtype_str,
lookup_stats->race_condition_stat, lookup_stats->unlinked_count_stat);
}
if (lookup_stats->ib_stay_on_trace_stat) {
uint ontrace_top = 0;
uint ontrace_bottom = 0;
uint lastexit_top = 0;
uint lastexit_bottom = 0;
uint speculate_lastexit_top = 0;
uint speculate_lastexit_bottom = 0;
/* indirect branch lookups */
uint64 total_dynamic_ibs = total_lookups +
lookup_stats->ib_stay_on_trace_stat +
(DYNAMO_OPTION(speculate_last_exit)
? lookup_stats->ib_trace_last_ibl_speculate_success
: 0);
/* XXX: add ib_stay_on_trace_stat_ovfl here */
if (total_dynamic_ibs > 0) {
divide_uint64_print(lookup_stats->ib_stay_on_trace_stat,
total_dynamic_ibs, false, 4, &ontrace_top,
&ontrace_bottom);
divide_uint64_print(lookup_stats->ib_trace_last_ibl_exit,
total_dynamic_ibs, false, 4, &lastexit_top,
&lastexit_bottom);
divide_uint64_print(lookup_stats->ib_trace_last_ibl_speculate_success,
total_dynamic_ibs, false, 4, &speculate_lastexit_top,
&speculate_lastexit_bottom);
}
/* all percentages here relative to IB lookups */
/* ontrace is how often we stay on trace wrt all indirect branches */
/* ontrace_fail is assuming IBL's that are not the last exit are due to
* ontrace failures
*/
/* lastexit is how many are on last IBL when it is not speculated */
/* lastexit_speculate is how many are speculatively hit (as of all IBs) */
LOG(THREAD, LOG_FRAGMENT | LOG_STATS, 1,
"%s %s table %s%s stay on trace hit:%s %u, last_ibl: %u, "
"ontrace%%=%u.%.4u, lastexit%%=%u.%.4u\n",
is_final_str, is_trace_str, lookup_routine_str, brtype_str,
lookup_stats->ib_stay_on_trace_stat_ovfl ? " OVFL" : "",
lookup_stats->ib_stay_on_trace_stat, lookup_stats->ib_trace_last_ibl_exit,
ontrace_top, ontrace_bottom, lastexit_top, lastexit_bottom);
LOG(THREAD, LOG_FRAGMENT | LOG_STATS, 1,
"%s %s table %s%s last trace exit speculation hit: %u, "
"lastexit_ontrace%%=%u.%.4u(%%IB)\n",
is_final_str, is_trace_str, lookup_routine_str, brtype_str,
lookup_stats->ib_trace_last_ibl_speculate_success, speculate_lastexit_top,
speculate_lastexit_bottom);
}
if (lookup_stats->ib_trace_last_ibl_exit > 0) {
/* ignoring indirect branches that stayed on trace */
/* XXX: add ib_stay_on_trace_stat_ovfl here */
uint speculate_only_lastexit_top = 0;
uint speculate_only_lastexit_bottom = 0;
uint lastexit_ibl_top = 0;
uint lastexit_ibl_bottom = 0;
uint speculate_lastexit_ibl_top = 0;
uint speculate_lastexit_ibl_bottom = 0;
uint64 total_dynamic_ibl_no_trace =
total_lookups + lookup_stats->ib_trace_last_ibl_exit;
if (total_dynamic_ibl_no_trace > 0) {
divide_uint64_print(lookup_stats->ib_trace_last_ibl_exit,
total_dynamic_ibl_no_trace, false, 4,
&lastexit_ibl_top, &lastexit_ibl_bottom);
divide_uint64_print(lookup_stats->ib_trace_last_ibl_speculate_success,
total_dynamic_ibl_no_trace, false, 4,
&speculate_lastexit_ibl_top,
&speculate_lastexit_ibl_bottom);
}
/* ib_trace_last_ibl_exit includes all ib_trace_last_ibl_speculate_success */
divide_uint64_print(lookup_stats->ib_trace_last_ibl_speculate_success,
lookup_stats->ib_trace_last_ibl_exit, false, 4,
&speculate_only_lastexit_top,
&speculate_only_lastexit_bottom);
LOG(THREAD, LOG_FRAGMENT | LOG_STATS, 1,
"%s %s table %s%s last trace exit speculation hit: %u, speculation miss: "
"%u, lastexit%%=%u.%.4u(%%IBL), lastexit_succ%%=%u.%.4u(%%IBL), "
"spec hit%%=%u.%.4u(%%last exit)\n",
is_final_str, is_trace_str, lookup_routine_str, brtype_str,
lookup_stats->ib_trace_last_ibl_speculate_success,
lookup_stats->ib_trace_last_ibl_exit -
lookup_stats->ib_trace_last_ibl_speculate_success,
lastexit_ibl_top, lastexit_ibl_bottom, speculate_lastexit_ibl_top,
speculate_lastexit_ibl_bottom, speculate_only_lastexit_top,
speculate_only_lastexit_bottom);
}
});
}
#endif /* HASHTABLE_STATISTICS */
Reference in New Issue View Git Blame Copy Permalink