Google Git
Sign in
chromium / external / github.com / DynamoRIO / dynamorio / refs/tags/cronbuild-10.0.19798 / . / core / hashtablex.h
blob: 3b7d697aa53f74791ad8ec028ed5845ec67ec84b [file] [log] [blame]
/* **********************************************************
* Copyright (c) 2011-2022 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. */
/*
* hashtablex.h
*
* Generic hashtable support.
*
* Implementation is an open-address hashtable with sentinel.
* Supports invalid slots for concurrent-access usage, in particular
* lockless read concurrent access (such as for indirect branch lookup tables).
* Also supports a synchronized lookup table.
*
* Usage: define the following macros, and then include this file.
* It is meant to be included multiple times.
* Define HASHTABLEX_HEADER to get the data struct and no implementation;
* else, you'll get implementation but NOT the data struct.
*
* set HASHTABLE_USE_LOOKUPTABLE if using lookuptable
* set HASHTABLE_ENTRY_STATS if want entry stats
*
* for struct:
* token NAME_KEY
* type ENTRY_TYPE
* if HASHTABLE_USE_LOOKUPTABLE is defined:
* type AUX_ENTRY_TYPE
* endif
* fields CUSTOM_FIELDS
*
* for main table:
* ptr_uint_t ENTRY_TAG(entry)
* bool ENTRY_IS_EMPTY(entry)
* bool ENTRY_IS_SENTINEL(entry)
* bool ENTRY_IS_INVALID(entry)
* assumption: invalid entries are only used with
* HASHTABLE_LOCKLESS_ACCESS tables
* bool ENTRIES_ARE_EQUAL(table, entry1, entry2)
* if using pointers, pointer equality is fine
* void ENTRY_SET_TO_ENTRY(table_entry, new_entry)
* This is optional; if omitted, "table_entry = new_entry" is used.
* ENTRY_TYPE ENTRY_EMPTY
* ENTRY_TYPE ENTRY_SENTINEL
* FIXME: to support structs we'll need lhs like AUX_ENTRY_SET_TO_SENTINEL
* (up to caller to ever set an entry to invalid)
* HTLOCK_RANK
* table_rwlock will work for most users.
* Needs higher rank than memory alloc locks.
* optional for main table:
* bool TAGS_ARE_EQUAL(table, tag1, tag2)
*
* for lookuptable:
* if HASHTABLE_USE_LOOKUPTABLE is defined:
* ptr_uint_t AUX_ENTRY_TAG(aux_entry)
* bool AUX_ENTRY_IS_EMPTY(aux_entry)
* empty entry is assumed to be all zeros!
* bool AUX_ENTRY_IS_SENTINEL(aux_entry)
* bool AUX_ENTRY_IS_INVALID(aux_entry)
* bool AUX_PAYLOAD_IS_INVALID(dcontext, table, aux_entry)
* AUX_ENTRY_SET_TO_SENTINEL(aux_entry)
* takes lhs since may be struct and C only allows setting to {} in decl
* AUX_ENTRY_IS_SET_TO_ENTRY(aux_entry, entry)
* AUX_ENTRY_SET_TO_ENTRY(aux_entry, entry)
* takes lhs since may be struct and C only allows setting to {} in decl
* string AUX_ENTRY_FORMAT_STR
* printf-args AUX_ENTRY_FORMAT_ARGS(aux_entry)
* endif
* we assume value semantics, i.e., we can copy entries via the = operator
*
* for HEAP_ACCOUNTING:
* heapacct-enum HASHTABLE_WHICH_HEAP(table_flags)
*
* to obtain persistence routines, define
* HASHTABLE_SUPPORT_PERSISTENCE
*
* for custom behavior we assume that these routines exist:
*
* static void
* HTNAME(hashtable_,NAME_KEY,_init_internal_custom)
* (dcontext_t *dcontext,
* HTNAME(,NAME_KEY,_table_t) *htable
* _IFLOOKUP(bool use_lookup));
*
* static void
* HTNAME(hashtable_,NAME_KEY,_resized_custom)
* (dcontext_t *dcontext,
* HTNAME(,NAME_KEY,_table_t) *htable,
* uint old_capacity, ENTRY_TYPE *old_table,
* ENTRY_TYPE *old_table_unaligned
* _IFLOOKUP(AUX_ENTRY_TYPE* lookuptable)
* _IFLOOKUP(byte *old_lookup_table_unaligned),
* uint old_ref_count,
* uint old_table_flags);
*
* #ifdef DEBUG
* static void
* HTNAME(hashtable_,NAME_KEY,_study_custom)
* (dcontext_t *dcontext,
* HTNAME(,NAME_KEY,_table_t) *htable,
* uint entries_inc);
* #endif
*
* static void
* HTNAME(hashtable_,NAME_KEY,_free_entry)
* (dcontext_t *dcontext, HTNAME(,NAME_KEY,_table_t) *table,
* ENTRY_TYPE entry);
*
* FIXME:
* - use defines to weed out unused static routines
* - rename unlinked_entries to invalid_entries
* - remove references to "ibl"/"ibt" and make them general comments
* - same with references to "fragment_t" or "f"
* - caller uses expanded names "hashtable_fragment_init" -- should we
* provide a macro HASHTABLE_INIT(NAME_KEY, args...) or ok to mix
* the generated names here w/ hardcoded names in instantiations?
* - provide wrapper routines for lookup, etc. that lock and unlock?
* see app_pc table usage for after call and rct target tables.
* - eliminate the HASHTABLE_ENTRY_SHARED flag?
*/
#define EXPANDKEY(pre, key, post) pre##key##post
#define HTNAME(pre, key, post) EXPANDKEY(pre, key, post)
#define KEY_STRING STRINGIFY(NAME_KEY)
#define ENTRY_IS_REAL(e) \
(!ENTRY_IS_EMPTY(e) && !ENTRY_IS_SENTINEL(e) && !ENTRY_IS_INVALID(e))
#ifdef HASHTABLE_USE_LOOKUPTABLE
# define _IFLOOKUP(x) , x
# define IFLOOKUP_ELSE(x, y) (x)
#else
# define _IFLOOKUP(x) /* nothing */
# define IFLOOKUP_ELSE(x, y) (y)
#endif
#ifndef TAGS_ARE_EQUAL
# define TAGS_ARE_EQUAL(table, t1, t2) ((t1) == (t2))
#endif
/****************************************************************************/
#ifdef HASHTABLEX_HEADER
/* N.B.: if you change any fields here you must increase
* PERSISTENT_CACHE_VERSION!
*/
typedef struct HTNAME(_, NAME_KEY, _table_t) {
/* entries used from shared private IBL routines copy come first:
* used to be lookuptable, now table for case 7691 */
/* preferred location of a given tag is then at
* lookuptable[(hash_func(tag) & hash_mask) >> hash_offset]
*/
ptr_uint_t hash_mask; /* mask selects the index bits of hash value */
# ifdef HASHTABLE_USE_LOOKUPTABLE
AUX_ENTRY_TYPE *lookuptable; /* allocation aligned within lookuptable_unaligned */
# endif
ENTRY_TYPE *table; /* hash_bits-bit addressed hash table */
uint ref_count; /* when table is shared -- HASHTABLE_SHARED --
* # threads with active ptrs to the table */
uint hash_bits;
hash_function_t hash_func; /* selects hash function */
uint hash_mask_offset; /* ignores given number of LSB bits */
uint capacity; /* = 2^hash_bits + 1 sentinel */
uint entries;
/* FIXME: rename to invalid_entries to be more general */
uint unlinked_entries;
uint load_factor_percent; /* \alpha = load_factor_percent/100 */
uint resize_threshold; /* = capacity * load_factor */
uint groom_factor_percent; /* \gamma = groom_factor_percent/100 */
uint groom_threshold; /* = capacity * groom_factor_percent */
uint max_capacity_bits; /* log_2 of maximum size to grow table */
# ifdef HASHTABLE_STATISTICS
/* These refer only to accesses from DR lookups */
hashtable_statistics_t drlookup_stats;
# ifdef HASHTABLE_ENTRY_STATS
/* Accesses from ibl */
fragment_stat_entry_t *entry_stats;
/* precomputed (entry_stats - lookup_table) for easy parallel
* table access from IBL routines
*/
uint entry_stats_to_lookup_table;
uint added_since_dumped; /* clock handle - usually the same as
* delta in entries, unless we have removed
*/
# endif
# endif /* HASHTABLE_STATISTICS */
uint table_flags; /* the HASHTABLE_* values are used here */
read_write_lock_t rwlock; /* shared tables should use a read/write lock */
ENTRY_TYPE *table_unaligned; /* real alloc for table if HASHTABLE_ALIGN_TABLE */
# ifdef HASHTABLE_USE_LOOKUPTABLE
byte *lookup_table_unaligned; /* real allocation unit for lookuptable */
# endif
# ifdef DEBUG
const char *name;
bool is_local; /* no lock needed since only known to this thread */
# endif
CUSTOM_FIELDS
} HTNAME(, NAME_KEY, _table_t);
/****************************************************************************/
#else /* implementation */
/* forward decls */
static bool HTNAME(hashtable_, NAME_KEY,
_check_size)(dcontext_t *dcontext,
HTNAME(, NAME_KEY, _table_t) * htable, uint add_now,
uint add_later);
static void HTNAME(hashtable_, NAME_KEY,
_init_internal_custom)(dcontext_t *dcontext,
HTNAME(, NAME_KEY, _table_t) *
htable _IFLOOKUP(bool use_lookup));
static void HTNAME(hashtable_, NAME_KEY, _resized_custom)(
dcontext_t *dcontext, HTNAME(, NAME_KEY, _table_t) * htable, uint old_capacity,
ENTRY_TYPE *old_table,
ENTRY_TYPE *old_table_unaligned _IFLOOKUP(AUX_ENTRY_TYPE *lookuptable)
_IFLOOKUP(byte *old_lookup_table_unaligned),
uint old_ref_count, uint old_table_flags);
static uint HTNAME(hashtable_, NAME_KEY,
_unlinked_remove)(dcontext_t *dcontext,
HTNAME(, NAME_KEY, _table_t) * table);
static void HTNAME(hashtable_, NAME_KEY,
_groom_table)(dcontext_t *dcontext,
HTNAME(, NAME_KEY, _table_t) * table);
static inline void HTNAME(hashtable_, NAME_KEY,
_groom_helper)(dcontext_t *dcontext,
HTNAME(, NAME_KEY, _table_t) * table);
static void HTNAME(hashtable_, NAME_KEY,
_free_entry)(dcontext_t *dcontext,
HTNAME(, NAME_KEY, _table_t) * table, ENTRY_TYPE entry);
# ifdef DEBUG
static void HTNAME(hashtable_, NAME_KEY, _study)(dcontext_t *dcontext,
HTNAME(, NAME_KEY, _table_t) * htable,
uint entries_inc);
static void HTNAME(hashtable_, NAME_KEY,
_study_custom)(dcontext_t *dcontext,
HTNAME(, NAME_KEY, _table_t) * htable,
uint entries_inc);
# ifdef HASHTABLE_ENTRY_STATS
void HTNAME(hashtable_, NAME_KEY,
_dump_entry_stats)(dcontext_t *dcontext,
HTNAME(, NAME_KEY, _table_t) * htable);
# endif
void HTNAME(hashtable_, NAME_KEY, _dump_table)(dcontext_t *dcontext,
HTNAME(, NAME_KEY, _table_t) * htable);
# endif /* DEBUG */
# if defined(DEBUG) && defined(INTERNAL)
static void HTNAME(hashtable_, NAME_KEY,
_load_statistics)(dcontext_t *dcontext,
HTNAME(, NAME_KEY, _table_t) * htable);
# endif
/* get size in bytes padded for later cache alignment */
static inline size_t
HTNAME(hashtable_, NAME_KEY, _table_aligned_size)(uint table_capacity, uint flags)
{
size_t size;
/* we assume table size allows 32-bit indices */
IF_X64(ASSERT(CHECK_TRUNCATE_TYPE_uint(table_capacity * sizeof(ENTRY_TYPE))));
size = table_capacity * sizeof(ENTRY_TYPE);
if (TEST(HASHTABLE_ALIGN_TABLE, flags)) {
/* aligned at least at 4, and may be aligned */
size += proc_get_cache_line_size() - 4;
}
return size;
}
# ifdef HASHTABLE_USE_LOOKUPTABLE
/* get size in bytes padded for later cache alignment */
static inline size_t
HTNAME(hashtable_, NAME_KEY, _lookuptable_aligned_size)(uint table_capacity)
{
return table_capacity * sizeof(AUX_ENTRY_TYPE) + proc_get_cache_line_size() -
4; /* aligned at least at 4, and may be aligned */
}
# endif
/* callers should use either hashtable_init or hashtable_resize instead */
static void
HTNAME(hashtable_, NAME_KEY,
_init_internal)(dcontext_t *dcontext, HTNAME(, NAME_KEY, _table_t) * table,
uint bits, uint load_factor_percent, hash_function_t func,
uint hash_mask_offset _IFLOOKUP(bool use_lookup))
{
uint i;
uint sentinel_index;
size_t alloc_size;
table->hash_bits = bits;
table->hash_func = func;
table->hash_mask_offset = hash_mask_offset;
table->hash_mask = HASH_MASK(table->hash_bits) << hash_mask_offset;
table->capacity = HASHTABLE_SIZE(table->hash_bits);
/*
* add an extra null_fragment at end to allow critical collision path
* not to worry about table overwrap
* FIXME: case 2147 to stay at power of 2 should use last element instead
*/
table->capacity++;
sentinel_index = table->capacity - 1;
table->entries = 0;
table->unlinked_entries = 0;
/* STUDY: try different ratios for the load factor \alpha
* It may save memory and it will not necessarily hurt performance:
* better cache utilization may help us even if touch more entries
* on a cache line.
*/
table->load_factor_percent = load_factor_percent;
/* be careful with integer overflows if ever let this in non-debug versions
* ASSERT is not enough if this is a user controlled release option - needs
* sanity check always
*/
ASSERT(table->load_factor_percent > 0 && table->load_factor_percent < 100);
table->resize_threshold = table->capacity * table->load_factor_percent / 100;
table->groom_factor_percent = 0; /* grooming disabled */
table->max_capacity_bits = 0; /* unlimited */
ASSERT(table->groom_factor_percent >= 0 /* 0 == disabled */);
ASSERT(table->groom_factor_percent < 100);
ASSERT(table->groom_factor_percent <= table->load_factor_percent);
/* when groom factor < load/2 then we'd have to groom during table rehashing */
ASSERT(table->groom_factor_percent == 0 ||
table->groom_factor_percent * 2 > table->load_factor_percent);
table->groom_threshold = table->capacity * table->groom_factor_percent / 100;
alloc_size = HTNAME(hashtable_, NAME_KEY, _table_aligned_size)(table->capacity,
table->table_flags);
table->table_unaligned = (ENTRY_TYPE *)TABLE_MEMOP(table->table_flags, alloc)(
dcontext, alloc_size HEAPACCT(HASHTABLE_WHICH_HEAP(table->table_flags)));
if (TEST(HASHTABLE_ALIGN_TABLE, table->table_flags)) {
ASSERT(ALIGNED(table->table_unaligned, 4)); /* guaranteed by heap_alloc */
table->table = (ENTRY_TYPE *)ALIGN_FORWARD(table->table_unaligned,
proc_get_cache_line_size());
ASSERT(ALIGNED(table->table, proc_get_cache_line_size()));
ASSERT(ALIGNED(table->table, sizeof(ENTRY_TYPE)));
} else
table->table = table->table_unaligned;
for (i = 0; i < table->capacity; i++)
table->table[i] = ENTRY_EMPTY;
/* overwrite last element to be a sentinel, reached only by assembly routines */
table->table[sentinel_index] = ENTRY_SENTINEL;
table->ref_count = 0;
# ifdef HASHTABLE_USE_LOOKUPTABLE
if (use_lookup) {
/* We need to allocate aligned size, yet there is no point in
* calling heap_mmap for small sizes. Instead we use normal
* heap and guarantee alignment manually by padding. For
* larger sizes, we're already wasting a page beyond the table
* size, so this will not waste more memory.
*/
size_t lookup_table_allocation =
HTNAME(hashtable_, NAME_KEY, _lookuptable_aligned_size)(table->capacity);
table->lookup_table_unaligned = TABLE_MEMOP(table->table_flags, alloc)(
dcontext,
lookup_table_allocation HEAPACCT(HASHTABLE_WHICH_HEAP(table->table_flags)));
ASSERT(ALIGNED(table->lookup_table_unaligned, 4)); /* guaranteed by heap_alloc */
table->lookuptable = (AUX_ENTRY_TYPE *)ALIGN_FORWARD(
table->lookup_table_unaligned, proc_get_cache_line_size());
/* When the table is used for IBL, for correctness we need to
* make sure it's allocated at a 4 byte aligned address. This
* is required so that writes to the start_pc field during a
* flush are atomic. If the start address is 4-byte aligned
* then each 8 byte entry -- and the entry's two 4 byte fields
* -- will also be aligned. This should be guaranteed by
* heap_alloc and we even align the table start address at
* cache line.
*/
ASSERT(ALIGNED(table->lookuptable, 4));
/* make sure an entry doesn't cross a cache line boundary for performance */
ASSERT(ALIGNED(table->lookuptable, sizeof(AUX_ENTRY_TYPE)));
/* A minor point: save one extra cache line on the whole table
* by making sure first entry is aligned to a cache line
* boundary, otherwise if straddling we would need
* 1 + table_size/cache_line_size to fit the whole table in d-cache
*/
ASSERT(ALIGNED(table->lookuptable, proc_get_cache_line_size()));
LOG(THREAD, LOG_HTABLE, 2,
"hashtable_" KEY_STRING "_init %s lookup unaligned=" PFX " "
"aligned=" PFX " allocated=%d\n",
table->name, table->lookup_table_unaligned, table->lookuptable,
lookup_table_allocation);
/* set all to null_fragment {tag : 0, start_pc : 0} */
memset(table->lookuptable, 0, table->capacity * sizeof(AUX_ENTRY_TYPE));
ASSERT(AUX_ENTRY_IS_EMPTY(table->lookuptable[0]));
/* set last to sentinel_fragment {tag : 0, start_pc : 1} */
AUX_ENTRY_SET_TO_SENTINEL(table->lookuptable[sentinel_index]);
} else {
/* TODO: emit_utils assumes lookuptable will exist, but we can't match
* the initializations.
*/
table->lookup_table_unaligned = NULL;
table->lookuptable = NULL;
}
# endif
ASSERT(ENTRY_IS_EMPTY(ENTRY_EMPTY));
ASSERT(ENTRY_IS_SENTINEL(ENTRY_SENTINEL));
LOG(THREAD, LOG_HTABLE, 1,
"hashtable_" KEY_STRING "_init %s htable=" PFX " bits=%d size=%d "
"mask=" PFX " offset=%d load=%d%% resize=%d\n"
" %s %s " PFX " %s " PFX " groom=%d%% groom_at=%d\n",
table->name, table, bits, table->capacity, table->hash_mask,
table->hash_mask_offset, table->load_factor_percent, table->resize_threshold,
table->name, "table", table->table, IFLOOKUP_ELSE(use_lookup ? "lookup" : "", ""),
IFLOOKUP_ELSE(table->lookuptable, NULL), table->groom_factor_percent,
table->groom_threshold);
# ifdef HASHTABLE_STATISTICS
# ifdef HASHTABLE_ENTRY_STATS
if (INTERNAL_OPTION(hashtable_ibl_entry_stats)) {
if (TEST(HASHTABLE_USE_ENTRY_STATS, table->table_flags)) {
# ifdef HASHTABLE_USE_LOOKUPTABLE
ASSERT(sizeof(fragment_stat_entry_t) == sizeof(AUX_ENTRY_TYPE));
# else
ASSERT(sizeof(fragment_stat_entry_t) == sizeof(ENTRY_TYPE));
# endif
if (table->entry_stats != NULL) { /* resize */
/* assuming resize is always doubling the table */
/* FIXME: too error prone we should pass old capacity
* somewhere if case 2147 changes the table size
*/
uint old_capacity =
HASHTABLE_SIZE(table->hash_bits - 1) + 1 /* sentinel */;
/* make sure we've printed the old stats, now losing them */
HEAP_ARRAY_FREE(dcontext, table->entry_stats, fragment_stat_entry_t,
old_capacity, HASHTABLE_WHICH_HEAP(table->table_flags),
UNPROTECTED);
}
/* FIXME: either put in nonpersistent heap as appropriate, or
* preserve across resets
*/
table->entry_stats =
HEAP_ARRAY_ALLOC(dcontext, fragment_stat_entry_t, table->capacity,
HASHTABLE_WHICH_HEAP(table->table_flags), UNPROTECTED);
ASSERT_TRUNCATE(table->entry_stats_to_lookup_table, uint,
((byte *)table->entry_stats - (byte *)table->table));
table->entry_stats_to_lookup_table = (uint)
# ifdef HASHTABLE_USE_LOOKUPTABLE
((byte *)table->entry_stats - (byte *)table->lookuptable);
# else
((byte *)table->entry_stats - (byte *)table->table);
# endif
memset(table->entry_stats, 0,
table->capacity * sizeof(fragment_stat_entry_t));
}
}
# endif
# endif
HTNAME(hashtable_, NAME_KEY, _init_internal_custom)
(dcontext, table _IFLOOKUP(use_lookup));
}
static void
HTNAME(hashtable_, NAME_KEY, _init)(dcontext_t *dcontext,
HTNAME(, NAME_KEY, _table_t) * table, uint bits,
uint load_factor_percent, hash_function_t func,
uint hash_offset
/* FIXME: turn this bool into a HASHTABLE_ flag */
_IFLOOKUP(bool use_lookup),
uint table_flags _IF_DEBUG(const char *table_name))
{
# ifdef DEBUG
table->name = table_name;
table->is_local = false;
# endif
table->table_flags = table_flags;
# ifdef HASHTABLE_STATISTICS
/* indicate this is first time, not a resize */
# ifdef HASHTABLE_ENTRY_STATS
table->entry_stats = NULL;
table->added_since_dumped = 0;
# endif
# endif
ASSERT(dcontext != GLOBAL_DCONTEXT || TEST(HASHTABLE_SHARED, table_flags));
HTNAME(hashtable_, NAME_KEY, _init_internal)
(dcontext, table, bits, load_factor_percent, func, hash_offset _IFLOOKUP(use_lookup));
ASSIGN_INIT_READWRITE_LOCK_FREE(table->rwlock, HTLOCK_RANK);
# ifdef HASHTABLE_STATISTICS
INIT_HASHTABLE_STATS(table->drlookup_stats);
# endif
}
/* caller is responsible for any needed synchronization */
static void
HTNAME(hashtable_, NAME_KEY, _resize)(dcontext_t *dcontext,
HTNAME(, NAME_KEY, _table_t) * table)
{
HTNAME(hashtable_, NAME_KEY, _init_internal)
(dcontext, table, table->hash_bits, table->load_factor_percent, table->hash_func,
table->hash_mask_offset
/* keep using lookup if used so far */
_IFLOOKUP(table->lookuptable != 0));
}
static inline void
HTNAME(hashtable_, NAME_KEY,
_free_table)(dcontext_t *alloc_dc,
ENTRY_TYPE *table_unaligned _IFLOOKUP(byte *lookup_table_unaligned),
uint flags, uint capacity)
{
if (table_unaligned != NULL) {
TABLE_MEMOP(flags, free)
(alloc_dc, table_unaligned,
HTNAME(hashtable_, NAME_KEY, _table_aligned_size)(capacity, flags)
HEAPACCT(HASHTABLE_WHICH_HEAP(flags)));
}
# ifdef HASHTABLE_USE_LOOKUPTABLE
if (lookup_table_unaligned != NULL) {
TABLE_MEMOP(flags, free)
(alloc_dc, lookup_table_unaligned,
HTNAME(hashtable_, NAME_KEY, _lookuptable_aligned_size)(capacity)
HEAPACCT(HASHTABLE_WHICH_HEAP(flags)));
}
# endif
}
static void
HTNAME(hashtable_, NAME_KEY, _free)(dcontext_t *dcontext,
HTNAME(, NAME_KEY, _table_t) * table)
{
LOG(THREAD, LOG_HTABLE, 1,
"hashtable_" KEY_STRING "_free %s table=" PFX " bits=%d size=%d "
"load=%d%% resize=%d %s groom=%d%% groom_at=%d\n",
table->name, table->table, table->hash_bits, table->capacity,
table->load_factor_percent, table->resize_threshold,
IFLOOKUP_ELSE((table->lookuptable != NULL) ? "use lookup" : "", ""),
table->groom_factor_percent, table->groom_threshold);
# ifdef HASHTABLE_STATISTICS
# ifdef HASHTABLE_ENTRY_STATS
if (INTERNAL_OPTION(hashtable_ibl_entry_stats)) {
if (TEST(HASHTABLE_USE_ENTRY_STATS, table->table_flags)) {
HEAP_ARRAY_FREE(dcontext, table->entry_stats, fragment_stat_entry_t,
table->capacity, HASHTABLE_WHICH_HEAP(table->table_flags),
UNPROTECTED);
} else
ASSERT(table->entry_stats == NULL);
}
# endif
# endif /* HASHTABLE_STATISTICS */
HTNAME(hashtable_, NAME_KEY, _free_table)
(dcontext, table->table_unaligned _IFLOOKUP(table->lookup_table_unaligned),
table->table_flags, table->capacity);
table->table = NULL;
table->table_unaligned = NULL;
# ifdef HASHTABLE_USE_LOOKUPTABLE
table->lookuptable = NULL;
table->lookup_table_unaligned = NULL;
# endif
DELETE_READWRITE_LOCK(table->rwlock);
}
/* Need to keep the cached start_pc_fragment consistent between lookuptable and
* the htable.
* Shared fragment IBTs: Unlinked lookup table entries are marked with
* unlinked_fragment and
* are expected to target a target_delete_entry.
*/
# ifdef DEBUG
static inline void
HTNAME(hashtable_, NAME_KEY, _check_consistency)(dcontext_t *dcontext,
HTNAME(, NAME_KEY, _table_t) * htable,
uint hindex)
{
# ifdef HASHTABLE_USE_LOOKUPTABLE
if (htable->lookuptable == NULL) {
LOG(THREAD, LOG_HTABLE, 6, "[%u] tag=" PFX ")\n", hindex,
ENTRY_TAG(htable->table[hindex]));
} else {
LOG(THREAD, LOG_HTABLE, 6, "[%u] " AUX_ENTRY_FORMAT_STR " tag=" PFX ")\n", hindex,
AUX_ENTRY_FORMAT_ARGS(htable->lookuptable[hindex]),
ENTRY_IS_REAL(htable->table[hindex]) ? ENTRY_TAG(htable->table[hindex]) : 0);
# else
LOG(THREAD, LOG_HTABLE, 6, "[%u] tag=" PFX ")\n", hindex,
ENTRY_IS_REAL(htable->table[hindex]) ? ENTRY_TAG(htable->table[hindex]) : 0);
# endif
/* We can't assert that an IBL target isn't a trace head due to a race
* between trace head marking and adding to a table. See the comments
* in fragment_add_to_hashtable().
*/
if (ENTRY_IS_INVALID(htable->table[hindex])) {
ASSERT(TEST(HASHTABLE_NOT_PRIMARY_STORAGE, htable->table_flags));
ASSERT(TEST(HASHTABLE_LOCKLESS_ACCESS, htable->table_flags));
# ifdef HASHTABLE_USE_LOOKUPTABLE
ASSERT(AUX_ENTRY_IS_INVALID(htable->lookuptable[hindex]));
# endif
}
# ifdef HASHTABLE_USE_LOOKUPTABLE
/* "Inclusive hierarachy" lookup tables -- per-type tables not attached
* to a table such as the BB table -- are simpler to reason about
* since we have more latitude setting fragment_t ptrs and so can ensure
* that the entry is always sync-ed with the corresponding fragment_t*.
* For a non-"inclusive hierarachy" table, only when the entry has not
* been unlinked (and so doesn't point to target_delete) can we expect
* the lookup table and fragment_t* to be in-sync.
*/
else if (TEST(HASHTABLE_NOT_PRIMARY_STORAGE, htable->table_flags) ||
AUX_PAYLOAD_IS_INVALID(dcontext, htable, htable->lookuptable[hindex])) {
ASSERT(AUX_ENTRY_IS_SET_TO_ENTRY(htable->lookuptable[hindex],
htable->table[hindex]));
}
/* Shouldn't be needed but could catch errors so leaving in. */
else {
ASSERT(AUX_PAYLOAD_IS_INVALID(dcontext, htable, htable->lookuptable[hindex]));
}
}
# endif
}
# endif
/* Returns entry if tag found;
* Otherwise returns an "empty" entry -- does NOT return NULL!
* Shared tables: It can be the case that an "invalid" entry is returned,
* which also has a tag of 0. This can occur when htable has a lookup table
* and 'tag' is for a fragment that was unlinked due to shared deletion.
*/
/* CHECK this routine is partially specialized, otherwise turn it into a macro */
static /* want to inline but > limit in fragment_lookup */ ENTRY_TYPE
HTNAME(hashtable_, NAME_KEY, _lookup)(dcontext_t *dcontext, ptr_uint_t tag,
HTNAME(, NAME_KEY, _table_t) * htable)
{
ENTRY_TYPE e;
ptr_uint_t ftag;
uint hindex = HASH_FUNC(tag, htable);
# ifdef HASHTABLE_STATISTICS
uint collision_len = 0;
# endif
ASSERT_TABLE_SYNCHRONIZED(htable, READWRITE); /* requires read (or write) lock */
e = htable->table[hindex];
DODEBUG({
HTNAME(hashtable_, NAME_KEY, _check_consistency)(dcontext, htable, hindex);
});
while (!ENTRY_IS_EMPTY(e)) {
DODEBUG({
HTNAME(hashtable_, NAME_KEY, _check_consistency)(dcontext, htable, hindex);
});
/* If a FAKE_TAG is present in lookuptable as an unlinked marker, use the
* table entry. */
# ifdef HASHTABLE_USE_LOOKUPTABLE
ftag = (htable->lookuptable != NULL &&
!AUX_ENTRY_IS_INVALID(htable->lookuptable[hindex]))
? AUX_ENTRY_TAG(htable->lookuptable[hindex])
: ENTRY_TAG(e);
# else
ftag = ENTRY_TAG(e);
# endif
/* FIXME future frags have a 0 tag and that's why we have
* to compare with null_fragment for end of chain in table[]
* whenever future frags go to their own table, this code should
* be reworked to touch lookuptable only -- i.e. become while
* (ftag != NULL_TAG).
*/
if (TAGS_ARE_EQUAL(htable, ftag, tag)) {
# ifdef HASHTABLE_STATISTICS
if (collision_len > 0)
HTABLE_STAT_INC(htable, collision_hit);
HTABLE_STAT_INC(htable, hit);
# endif
return e;
}
/* collision */
# ifdef HASHTABLE_STATISTICS
LOG(THREAD_GET, LOG_HTABLE, 6,
"(hashtable_" KEY_STRING "_lookup: collision sequence " PFX " "
"%u [len=%u])\n",
tag, hindex, collision_len);
collision_len++;
HTABLE_STAT_INC(htable, collision);
# endif
hindex = HASH_INDEX_WRAPAROUND(hindex + 1, htable);
e = htable->table[hindex];
DODEBUG({
HTNAME(hashtable_, NAME_KEY, _check_consistency)(dcontext, htable, hindex);
});
}
HTABLE_STAT_INC(htable, miss);
return e;
}
/* Convenience routine that grabs the read lock and does a lookup */
static inline ENTRY_TYPE
HTNAME(hashtable_, NAME_KEY, _rlookup)(dcontext_t *dcontext, ptr_uint_t tag,
HTNAME(, NAME_KEY, _table_t) * htable)
{
ENTRY_TYPE e;
TABLE_RWLOCK(htable, read, lock);
e = HTNAME(hashtable_, NAME_KEY, _lookup)(dcontext, tag, htable);
TABLE_RWLOCK(htable, read, unlock);
return e;
}
/* add f to a fragment table
* returns whether resized the table or not
* N.B.: this routine will recursively call itself via check_table_size if the
* table is resized
*/
static inline bool
HTNAME(hashtable_, NAME_KEY, _add)(dcontext_t *dcontext, ENTRY_TYPE e,
HTNAME(, NAME_KEY, _table_t) * table)
{
uint hindex;
bool resized;
DEBUG_DECLARE(uint cluster_len = 0;)
ASSERT_TABLE_SYNCHRONIZED(table, WRITE); /* add requires write lock */
ASSERT(!TEST(HASHTABLE_READ_ONLY, table->table_flags));
if (TEST(HASHTABLE_READ_ONLY, table->table_flags))
return false;
/* ensure higher-level synch not allowing any races between lookup and add */
/* Shared fragment IBTs: Tolerate unlinked markers. */
ASSERT(!ENTRY_IS_REAL(
HTNAME(hashtable_, NAME_KEY, _lookup)(dcontext, ENTRY_TAG(e), table)));
/* check_table_size increments table->entries for us and ensures
* we have enough space. don't grab any properties of table prior to this
* call, like hindex, as it will change if resized.
*/
resized = !HTNAME(hashtable_, NAME_KEY, _check_size)(dcontext, table, 1, 0);
hindex = HASH_FUNC(ENTRY_TAG(e), table);
/* find an empty null slot */
do {
LOG(THREAD_GET, LOG_HTABLE, 4,
"hashtable_" KEY_STRING "_add(" PFX ") mask=" PFX " offset=%d trying " PFX
":\n",
ENTRY_TAG(e), table->hash_mask, table->hash_mask_offset, hindex);
/* We could use !ENTRY_IS_REAL() here but it could make what we're doing
* more confusing since the &unlinked_fragment is handled a little
* differently. So we enumerate the cases to make things more
* apparent.
*/
if (ENTRY_IS_EMPTY(table->table[hindex]))
break;
/* Replace pending deletion entries in a private table but not
* in a shared table. */
if (ENTRY_IS_INVALID(table->table[hindex])) {
/* FIXME We cannot blindly overwrite an unlinked entry for a shared
* table. We overwrite an entry only when we know that since the
* unlink, every thread has exited the cache at least once (just as
* with shared deletion). Refcounting on a per-entry basis is
* very likely not worth the potential gain.
*
* A broader approach that may be effective enough piggybacks
* on shared deletion. When a flusher unlinks entries in a
* shared table, the table is marked FRAG_NO_CLOBBER_UNLINK --
* this prevents unlinked entries from being replaced. After a
* thread decrements a shared deletion refcount via
* check_flush_queue(), it checks if the shared deletion queuee
* is empty. If the queue is empty, then we know that since the
* last flush (and table unlinks) all threads have
* exited the cache at least once, so any shared tables marked
* as FRAG_NO_CLOBBER_UNLINK can have that flag cleared.
*/
if (!TEST(HASHTABLE_SHARED, table->table_flags)) {
ASSERT(table->unlinked_entries > 0);
ASSERT(TEST(HASHTABLE_LOCKLESS_ACCESS, table->table_flags));
# ifdef HASHTABLE_USE_LOOKUPTABLE
ASSERT(
AUX_PAYLOAD_IS_INVALID(dcontext, table, table->lookuptable[hindex]));
ASSERT(AUX_ENTRY_IS_INVALID(table->lookuptable[hindex]));
LOG(THREAD_GET, LOG_HTABLE, 4,
" replace target_delete "
"entry " AUX_ENTRY_FORMAT_STR "\n",
AUX_ENTRY_FORMAT_ARGS(table->lookuptable[hindex]));
# endif
STATS_INC(num_ibt_replace_unlinked_fragments);
break;
}
}
DODEBUG({ ++cluster_len; });
hindex = HASH_INDEX_WRAPAROUND(hindex + 1, table);
} while (1);
/* FIXME: case 4814 we may want to flush the table if we are running into a too long
* collision cluster
*/
DOLOG(1, LOG_HTABLE, {
if (cluster_len > HASHTABLE_SIZE((1 + table->hash_bits) / 2)) {
LOG(THREAD_GET, LOG_HTABLE,
cluster_len > HASHTABLE_SIZE((1 + table->hash_bits) / 2 + 1) ? 1U : 2U,
"hashtable_" KEY_STRING "_add: long collision sequence len=%u"
"for " PFX " %s table[%u] capacity=%d entries=%d)\n",
cluster_len, ENTRY_TAG(e), table->name, hindex, table->capacity,
table->entries);
}
});
/* If we had uniformly distributed hash functions, expected max length is
* sqrt(capacity.\pi/8) see Knuth vol.3, FIXME we double below because this
* sometimes ASSERTS for the shared_future_table at the 10 to 11 bits
* transition (seems to be fine at larger sizes)
* bug2241 we add an additional 64 to handle problems in private future
* tables at small sizes, for bug2271 we disable for tables using the
* _NONE hash function (currently private bb and trace) when we have no
* shared fragments
*/
# ifdef DEBUG
if (!TEST(HASHTABLE_RELAX_CLUSTER_CHECKS, table->table_flags) &&
(table->hash_func != HASH_FUNCTION_NONE || SHARED_FRAGMENTS_ENABLED())) {
uint max_cluster_len =
HASHTABLE_SIZE((1 + table->hash_bits) / 2 + 1 /* double */) + 64;
if (!(cluster_len <= max_cluster_len)) {
DO_ONCE({ /* once reach this may fire many times in a row */
/* always want to know which table this is */
SYSLOG_INTERNAL_WARNING(
"cluster length assert: %s cluster=%d vs %d,"
" cap=%d, entries=%d",
table->name, cluster_len, max_cluster_len, table->capacity,
table->entries);
DOLOG(3, LOG_HTABLE, {
HTNAME(hashtable_, NAME_KEY, _dump_table)(dcontext, table);
});
ASSERT_CURIOSITY(false && "table collision cluster is too large");
});
}
}
# endif
/* actually add the entry
* add to lookuptable first to avoid race spoiling ASSERT_CONSISTENCY -- better
* for other thread to miss in lookup
*/
# ifdef HASHTABLE_USE_LOOKUPTABLE
if (table->lookuptable != NULL) {
AUX_ENTRY_SET_TO_ENTRY(table->lookuptable[hindex], e);
ASSERT(!AUX_ENTRY_IS_INVALID(table->lookuptable[hindex]));
}
# endif
if (ENTRY_IS_INVALID(table->table[hindex]))
table->unlinked_entries--;
# ifdef ENTRY_SET_TO_ENTRY
ENTRY_SET_TO_ENTRY(table->table[hindex], e);
# else
table->table[hindex] = e;
# endif
ASSERT(!ENTRY_IS_INVALID(table->table[hindex]));
LOG(THREAD_GET, LOG_HTABLE, 4,
"hashtable_" KEY_STRING "_add: added " PFX " to %s at table[%u]\n", ENTRY_TAG(e),
table->name, hindex);
return resized;
}
/* Ensures that the table has enough room for add_now+add_later new entries.
* If not, the table is resized and rehashed into its new space.
* The table's entry count is incremented by add_now but nothing changes
* with respect to add_later other than making space.
* Returns false if it had to re-size the table.
* Caller must hold the write lock, if this is a shared table!
* N.B.: this routine will recursively be called when resizing, b/c it
* calls fragment_add_to_hashtable, which calls back, but should never
* trigger another resize.
*/
static bool
HTNAME(hashtable_, NAME_KEY, _check_size)(dcontext_t *dcontext,
HTNAME(, NAME_KEY, _table_t) * table,
uint add_now, uint add_later)
{
dcontext_t *alloc_dc = FRAGMENT_TABLE_ALLOC_DC(dcontext, table->table_flags);
uint entries;
bool shared_lockless =
TESTALL(HASHTABLE_ENTRY_SHARED | HASHTABLE_SHARED | HASHTABLE_LOCKLESS_ACCESS,
table->table_flags);
/* FIXME: too many assumptions here that if lockless, then a lookuptable
* is always used, etc.
*/
bool lockless =
TESTALL(HASHTABLE_LOCKLESS_ACCESS | HASHTABLE_ENTRY_SHARED, table->table_flags);
/* write lock must be held */
ASSERT_TABLE_SYNCHRONIZED(table, WRITE);
ASSERT(!TEST(HASHTABLE_READ_ONLY, table->table_flags));
if (TEST(HASHTABLE_READ_ONLY, table->table_flags))
return false;
/* check flush threshold to see if we'd want to flush hashtable */
if (table->entries > table->groom_threshold && table->groom_threshold > 0) {
HTNAME(hashtable_, NAME_KEY, _groom_table)(dcontext, table);
/* FIXME Grooming a table in-place doesn't work for a shared IBT table.
* To make it work, we should a) realloc a same-sized table
* b) re-add all entries in the old table, c) add the old
* to the dead list, and d) then call groom_table(). (b) is
* needed because we can't assume that groom_table() will
* always flush the entire table.
*
* Or we could groom the old table -- making sure that it's done
* thread-safely -- and then copy into the new table, requiring
* fewer re-adds.
*
* This is covered by case 5838.
*/
}
/* FIXME: case 4814 we should move clock handles here
*/
# ifdef HASHTABLE_STATISTICS
# ifdef HASHTABLE_ENTRY_STATS
/* dump per entry hit statistics regularly to see working set */
if (table->entry_stats != NULL) {
table->added_since_dumped += add_now;
if (table->added_since_dumped >= INTERNAL_OPTION(hashtable_ibl_study_interval)) {
LOG(THREAD, LOG_HTABLE, 2, "dump_and_clean_entry_statistics %s added %d\n",
table->name, table->added_since_dumped);
HTNAME(hashtable_, NAME_KEY, _dump_entry_stats)(dcontext, table);
table->added_since_dumped = 0;
}
}
# endif
# endif /* HASHTABLE_STATISTICS */
/* Pretend we had full # entries; we'll lower later */
table->entries += add_now + add_later;
/* check resize threshold to see if a larger hashtable is needed
* or that we may want to reset the table.
*
* For an IBT table, the # unlinked entries needs to be checked also.
* For a shared table, they cannot be replaced so they are effectively
* real entries. For a private table, they can be replaced but those
* that remain present can lengthen collision chain lengths.
*
* NOTE: unlinked_entries is used only when shared targets are
* stored in IBT tables, since unlinking in those tables is NOT
* followed up by a full removal of the unlinked entries.
*/
entries = lockless ? table->entries + table->unlinked_entries : table->entries;
if (entries > table->resize_threshold) {
ENTRY_TYPE *old_table = table->table;
ENTRY_TYPE *old_table_unaligned = table->table_unaligned;
uint old_capacity = table->capacity;
# ifdef HASHTABLE_USE_LOOKUPTABLE
AUX_ENTRY_TYPE *old_lookuptable_to_nullify = table->lookuptable;
byte *old_lookup_table_unaligned = table->lookup_table_unaligned;
# endif
uint old_ref_count = table->ref_count - 1; /* remove this thread's
* reference to the table */
uint i;
DEBUG_DECLARE(uint old_entries = table->entries - add_later;)
DODEBUG({
/* study before resizing */
HTNAME(hashtable_, NAME_KEY, _study)(dcontext, table, add_now + add_later);
});
# ifdef HASHTABLE_STATISTICS
# ifdef HASHTABLE_ENTRY_STATS
if (table->entry_stats != NULL) {
LOG(THREAD, LOG_HTABLE, 2, "dump_and_clean_entry_statistics %s resized\n",
table->name);
HTNAME(hashtable_, NAME_KEY, _dump_entry_stats)(dcontext, table);
}
# endif
# endif /* HASHTABLE_STATISTICS */
/* For a shared IBT table, the flushing/grooming is done after
* a resize -- we can't groom in-place. */
if (table->hash_bits == table->max_capacity_bits && !shared_lockless) {
STATS_INC(num_ibt_max_capacity);
HTNAME(hashtable_, NAME_KEY, _groom_helper)(dcontext, table);
return true; /* == did not resize the table */
}
/* For an IBT table, if the # unlinked entries is what kicked
* in the resize then check the # actual entries and do
* a same-size realloc to eliminate the unlinked entries. Also,
* if we've reached the max size, do a same-size realloc.
*
* Otherwise, double the table size.
*/
if (lockless &&
(table->entries <= table->resize_threshold ||
table->hash_bits == table->max_capacity_bits)) {
STATS_INC(num_same_size_ibt_table_resizes);
} else {
DEBUG_DECLARE(uint old_bits = table->hash_bits;)
ASSERT(table->resize_threshold ==
(HASHTABLE_SIZE(table->hash_bits) + 1 /*sentinel*/) *
table->load_factor_percent / 100);
while (entries > (HASHTABLE_SIZE(table->hash_bits) + 1 /*sentinel*/) *
table->load_factor_percent / 100 &&
table->hash_bits != table->max_capacity_bits) {
table->hash_bits++; /* double the size */
}
ASSERT(table->hash_bits > old_bits);
}
HTNAME(hashtable_, NAME_KEY, _resize)(alloc_dc, table);
/* will be incremented by rehashing below -- in fact, by
* recursive calls to this routine from
* fragment_add_to_hashtable -- see warning below
*/
table->entries = 0;
table->unlinked_entries = 0;
ASSERT(table->ref_count == 0);
/* can't just memcpy, must rehash */
/* For open address table rehash should first find an empty
* slot and start from there so that we make sure that entries
* that used to find a hit on the first lookup continue to do
* so instead of creating even longer collision parking lots.
* XXX: can we do better?
*/
for (i = 0; i < old_capacity; i++) {
ENTRY_TYPE e = old_table[i];
if (!ENTRY_IS_REAL(e))
continue;
/* Don't carry over frags that point to target_delete. This can
* happen in any IBT table, shared or private, that targets
* shared fragments.
*/
if (lockless && ENTRY_IS_INVALID(old_table[i])) {
LOG(GLOBAL, LOG_HTABLE, 1,
"Don't copy tag " PFX " in %s[%u] across a resize\n", ENTRY_TAG(e),
table->name, i);
DODEBUG({ old_entries--; });
STATS_INC(num_ibt_unlinked_entries_not_moved);
continue;
}
# ifdef HASHTABLE_USE_LOOKUPTABLE
if (lockless && old_lookuptable_to_nullify != NULL &&
AUX_ENTRY_IS_INVALID(old_lookuptable_to_nullify[i])) {
LOG(GLOBAL, LOG_HTABLE, 1,
"Don't copy tag " PFX " in %s[%u] across a resize\n", ENTRY_TAG(e),
table->name, i);
ASSERT(AUX_PAYLOAD_IS_INVALID(dcontext, table,
old_lookuptable_to_nullify[i]));
DODEBUG({ old_entries--; });
STATS_INC(num_ibt_unlinked_entries_not_moved);
continue;
}
# endif
/* N.B.: this routine will call us again, but we assume the
* resize will NEVER be triggered, since we hold the write lock
* and set table->entries to 0.
* We could have a special add routine that doesn't call us,
* I suppose.
*/
HTNAME(hashtable_, NAME_KEY, _add)(dcontext, e, table);
}
table->entries += add_now; /* for about-to-be-added fragment(s) */
/* (add_later will be added later though calls to this same routine) */
/* For a shared IBT table, the flushing/grooming is done after a
* same-size realloc -- we can't groom the original table in-place.
* Groom when we know that the table was just bumped up in size
* earlier in the routine -- compare the old and new sizes to
* determine.
*/
if (table->hash_bits == table->max_capacity_bits &&
old_capacity == table->capacity) {
STATS_INC(num_ibt_max_capacity);
ASSERT(shared_lockless);
HTNAME(hashtable_, NAME_KEY, _groom_helper)(dcontext, table);
} else {
/* should have rehashed all old entries into new table */
ASSERT(table->entries == old_entries);
}
LOG(THREAD, LOG_HTABLE, 2,
"%s hashtable resized at %d entries from capacity %d to %d\n", table->name,
table->entries, old_capacity, table->capacity);
/* Since readers now synchronize with writers of shared htables,
* we can now delete old htable even when sharing.
*/
DODEBUG({
LOG(THREAD, LOG_HTABLE, 1, "Rehashed %s table\n", table->name);
/* study after rehashing
* ok to become reader for study while a writer
*/
HTNAME(hashtable_, NAME_KEY, _study)(dcontext, table, add_now);
DOLOG(3, LOG_HTABLE, {
HTNAME(hashtable_, NAME_KEY, _dump_table)(dcontext, table);
});
});
/* Shared IBT tables are resized at safe points, not here, since
* they are accessed while in-cache, unlike other shared tables
* such as the shared BB or shared trace table.
*/
if (!shared_lockless) {
HTNAME(hashtable_, NAME_KEY, _free_table)
(alloc_dc, old_table_unaligned _IFLOOKUP(old_lookup_table_unaligned),
table->table_flags, old_capacity);
} else {
if (old_ref_count == 0) {
/* Note that a write lock is held on the table, so no danger of
* a double free. */
HTNAME(hashtable_, NAME_KEY, _free_table)
(GLOBAL_DCONTEXT,
old_table_unaligned _IFLOOKUP(old_lookup_table_unaligned),
table->table_flags, old_capacity);
STATS_INC(num_shared_ibt_tables_freed_immediately);
}
}
HTNAME(hashtable_, NAME_KEY, _resized_custom)
(dcontext, table, old_capacity, old_table,
old_table_unaligned _IFLOOKUP(old_lookuptable_to_nullify)
_IFLOOKUP(old_lookup_table_unaligned),
old_ref_count, table->table_flags);
return false; /* == resized the table */
}
/* If there are too many unlinked markers cluttering the table, remove them. */
else if (table->unlinked_entries > 0 &&
((INTERNAL_OPTION(rehash_unlinked_threshold) < 100 &&
INTERNAL_OPTION(rehash_unlinked_threshold) <
(100 * table->unlinked_entries /
(table->entries + table->unlinked_entries))) ||
INTERNAL_OPTION(rehash_unlinked_always))) {
/* Currently, such markers should be present only when shared BBs are IB
* targets or traces are shared. */
ASSERT(SHARED_IB_TARGETS());
ASSERT(TESTALL(HASHTABLE_ENTRY_SHARED | HASHTABLE_LOCKLESS_ACCESS,
table->table_flags));
STATS_INC(num_ibt_table_rehashes);
LOG(THREAD, LOG_HTABLE, 1, "Rehash table %s: linked %u, unlinked %u\n",
table->name, table->entries, table->unlinked_entries);
/* we will inc for these at a "later" time */
table->entries -= add_later;
/* entries was incremented earlier but the new entry hasn't been
* added yet. We decrement before and re-inc after so that any calls
* to study_hashtable in the remove routine succeed.
*/
DODEBUG({ table->entries -= add_now; });
HTNAME(hashtable_, NAME_KEY, _unlinked_remove)(dcontext, table);
DODEBUG({ table->entries += add_now; });
} else {
/* we will inc for these at a "later" time */
table->entries -= add_later;
}
return true; /* == did not resize the table */
}
/* Return pointer to the record for fragment in its collision chain (table or next field)
or NULL if not found */
static inline ENTRY_TYPE *
HTNAME(hashtable_, NAME_KEY, _lookup_for_removal)(ENTRY_TYPE fr,
HTNAME(, NAME_KEY, _table_t) * htable,
uint *rhindex)
{
uint hindex = HASH_FUNC(ENTRY_TAG(fr), htable);
ENTRY_TYPE *pg = &htable->table[hindex];
while (!ENTRY_IS_EMPTY(*pg)) {
if (ENTRIES_ARE_EQUAL(htable, fr, *pg)) {
*rhindex = hindex;
return pg;
}
/* collision */
LOG(THREAD_GET, LOG_HTABLE, 6,
"(hashtable_" KEY_STRING "_lookup_for_"
"removal: collision sequence " PFX " %u)\n",
ENTRY_TAG(fr), hindex);
hindex = HASH_INDEX_WRAPAROUND(hindex + 1, htable);
pg = &htable->table[hindex];
}
*rhindex = 0; /* to make sure always initialized */
return NULL;
}
# ifdef HASHTABLE_USE_LOOKUPTABLE
/* FIXME: figure out what weight function I tipped off so this is too much too inline */
static INLINE_FORCED void
HTNAME(hashtable_, NAME_KEY, _update_lookup)(HTNAME(, NAME_KEY, _table_t) * htable,
uint hindex)
{
if (htable->lookuptable != NULL) {
AUX_ENTRY_SET_TO_ENTRY(htable->lookuptable[hindex], htable->table[hindex]);
LOG(THREAD_GET, LOG_HTABLE, 4,
"hashtable_" KEY_STRING "_update_lookup:"
"updated " PFX " at table[%u]\n",
AUX_ENTRY_TAG(htable->lookuptable[hindex]), hindex);
}
}
# endif
/* This is based on Algorithm R from Knuth's Vol.3, section 6.4 */
/* Deletion markers tend to form clusters ("parking lot effect"), */
/* and in steady state the hashtable will always be full. */
/* This slightly more complicated deletion scheme solves these undesired effects, */
/* with the final arrangement being as if the elements were never inserted. */
/* Returns whether it copied from the start of the table to the end (wraparound).
* FIXME: if callers need more info, could return the final hindex, or the final
* hole.
*/
static uint
HTNAME(hashtable_, NAME_KEY,
_remove_helper_open_address)(HTNAME(, NAME_KEY, _table_t) * htable, uint hindex,
ENTRY_TYPE *prevg)
{
bool wrapped = false;
/* Assumptions:
* We have to move the htable->table and lookuptable elements. It
* is OK to do so since the address of these structures is never
* passed back to clients, instead, all clients can only hold onto
* a fragment_t* itself, not to the indirection here.
*/
LOG(THREAD_GET, LOG_HTABLE, 4,
"hashtable_" KEY_STRING "_remove_helper_open_address(table=" PFX ", "
"hindex=%u)\n",
htable, hindex);
for (;;) {
uint preferred;
uint hole = hindex;
/* first go ahead and set entry to null */
htable->table[hole] = ENTRY_EMPTY;
# ifdef HASHTABLE_USE_LOOKUPTABLE
HTNAME(hashtable_, NAME_KEY, _update_lookup)(htable, hole);
# endif
do {
/* positive probing to get the rest in the same cache line
also gains from +1 unit stride HW prefetching
*/
hindex = HASH_INDEX_WRAPAROUND(hindex + 1, htable);
/* no orphaned elements, we're done */
/* Note that an &unlinked_fragment will get moved since it
* and its lookup table entry are designed to preserve linear
* probing. See the comment after fragment_update_lookup()
* for the implications.
*/
if (ENTRY_IS_EMPTY(htable->table[hindex]))
return wrapped;
preferred = HASH_FUNC(ENTRY_TAG(htable->table[hindex]), htable);
/* Verify if it will be lost if we leave a hole behind its preferred addr */
/* [preferred] <= [hole] < [hindex] : BAD */
/* [hindex] < [preferred] <= [hole] : BAD [after wraparound] */
/* [hole] < [hindex] < [preferred] : BAD [after wraparound] */
/* Note the <='s: hole != hindex, but it is possible that preferred == hole */
} while (!(((preferred <= hole) && (hole < hindex)) ||
((hindex < preferred) && (preferred <= hole)) ||
((hole < hindex) && (hindex < preferred))));
LOG(THREAD_GET, LOG_HTABLE, 3,
"hashtable_" KEY_STRING "_remove_helper_open_address: moving " PFX " "
"from table[%u] into table[%u], preferred=%u\n",
ENTRY_TAG(htable->table[hindex]), hindex, hole, preferred);
/* need to move current entry into the hole */
htable->table[hole] = htable->table[hindex];
if (hindex < hole)
wrapped = true;
# ifdef HASHTABLE_USE_LOOKUPTABLE
HTNAME(hashtable_, NAME_KEY, _update_lookup)(htable, hole);
/* Since an &unlinked entry can be moved into a hole, we take
* special care to sync the lookup table to preserve the assert-able
* conditions that an unlinked entry has a lookup table entry
* w/a FAKE_TAG tag and a target_delete start_pc. FAKE_TAG is
* copied via the preceding update_lookup() but that also sets
* start_pc to 0. We manually set start_pc to the start_pc value of
* the old entry, to carry over the target_delete value.
*
* We also block the call to fragment_update_lookup() in the
* caller.
*/
/* FIXME We can remove this specialized code and simplify the
* ASSERT_CONSISTENCY by using a dedicated unlinked fragment per
* table. Each unlinked fragment can have its start_pc set to
* the corresponding target_delete value for the table.
*/
if (ENTRY_IS_INVALID(htable->table[hole])) {
htable->lookuptable[hole] = htable->lookuptable[hindex];
ASSERT(!AUX_ENTRY_IS_EMPTY(htable->lookuptable[hole]));
LOG(THREAD_GET, LOG_HTABLE, 4, " re-set " PFX " at table[%u]\n",
AUX_ENTRY_TAG(htable->lookuptable[hindex]), hole);
}
# endif
}
return wrapped;
}
/* Returns whether it copied from the start of the table to the end (wraparound). */
static inline bool
HTNAME(hashtable_, NAME_KEY, _remove_helper)(HTNAME(, NAME_KEY, _table_t) * htable,
uint hindex, ENTRY_TYPE *prevg)
{
/* Non-trivial for open addressed scheme */
/* just setting elements to null will make unreachable any following elements */
/* better solution is to move entries that would become unreachable */
int iwrapped =
HTNAME(hashtable_, NAME_KEY, _remove_helper_open_address)(htable, hindex, prevg);
bool wrapped = CAST_TO_bool(iwrapped);
# ifdef HASHTABLE_USE_LOOKUPTABLE
/* Don't sync the lookup table for unlinked fragments -- see the comments
* above in fragment_remove_helper_open_address(). */
if (!ENTRY_IS_INVALID(htable->table[hindex]))
HTNAME(hashtable_, NAME_KEY, _update_lookup)(htable, hindex);
# endif
htable->entries--;
return wrapped;
}
/* Removes f from htable (does not delete f)
* returns true if fragment found and removed
*/
static inline bool
HTNAME(hashtable_, NAME_KEY, _remove)(ENTRY_TYPE fr,
HTNAME(, NAME_KEY, _table_t) * htable)
{
uint hindex;
ENTRY_TYPE *pg;
ASSERT_TABLE_SYNCHRONIZED(htable, WRITE); /* remove requires write lock */
ASSERT(!TEST(HASHTABLE_READ_ONLY, htable->table_flags));
if (TEST(HASHTABLE_READ_ONLY, htable->table_flags))
return false;
pg = HTNAME(hashtable_, NAME_KEY, _lookup_for_removal)(fr, htable, &hindex);
if (pg != NULL) {
HTNAME(hashtable_, NAME_KEY, _remove_helper)(htable, hindex, pg);
return true;
}
return false;
}
/* Replaces a fragment in hashtable assuming tag is preserved
* returns true if fragment found and removed
*/
static inline bool
HTNAME(hashtable_, NAME_KEY, _replace)(ENTRY_TYPE old_e, ENTRY_TYPE new_e,
HTNAME(, NAME_KEY, _table_t) * htable)
{
uint hindex;
ENTRY_TYPE *pg =
HTNAME(hashtable_, NAME_KEY, _lookup_for_removal)(old_e, htable, &hindex);
/* replace requires write lock only because we have readers who
* need global consistency and replace requires two local writes!
*/
ASSERT_TABLE_SYNCHRONIZED(htable, WRITE);
ASSERT(!TEST(HASHTABLE_READ_ONLY, htable->table_flags));
if (TEST(HASHTABLE_READ_ONLY, htable->table_flags))
return false;
if (pg != NULL) {
ASSERT(ENTRY_TAG(old_e) == ENTRY_TAG(new_e));
ASSERT(ENTRIES_ARE_EQUAL(htable, *pg, old_e));
*pg = new_e;
# ifdef HASHTABLE_USE_LOOKUPTABLE
if (htable->lookuptable != NULL) {
/* TODO: update
* tag doesn't change, only start_pc may change */
ASSERT(AUX_ENTRY_TAG(htable->lookuptable[hindex]) ==
ENTRY_TAG(htable->table[hindex]));
AUX_ENTRY_SET_TO_ENTRY(htable->lookuptable[hindex], htable->table[hindex]);
}
# endif
return true;
}
return false;
}
/* removes all entries and resets the table but keeps the same capacity */
/* not static b/c not used by all tables */
void
HTNAME(hashtable_, NAME_KEY, _clear)(dcontext_t *dcontext,
HTNAME(, NAME_KEY, _table_t) * table)
{
uint i;
ENTRY_TYPE e;
ASSERT(!TEST(HASHTABLE_READ_ONLY, table->table_flags));
if (TEST(HASHTABLE_READ_ONLY, table->table_flags))
return;
LOG(THREAD, LOG_HTABLE, 2, "hashtable_" KEY_STRING "_clear\n");
DOLOG(2, LOG_HTABLE | LOG_STATS, {
HTNAME(hashtable_, NAME_KEY, _load_statistics)(dcontext, table);
});
for (i = 0; i < table->capacity; i++) {
e = table->table[i];
/* must check for sentinel */
if (ENTRY_IS_REAL(e)) {
HTNAME(hashtable_, NAME_KEY, _free_entry)(dcontext, table, e);
}
table->table[i] = ENTRY_EMPTY;
}
# ifdef HASHTABLE_USE_LOOKUPTABLE
memset(table->lookuptable, 0, table->capacity * sizeof(AUX_ENTRY_TYPE));
# endif
# ifdef HASHTABLE_STATISTICS
# ifdef HASHTABLE_ENTRY_STATS
table->added_since_dumped = 0;
if (INTERNAL_OPTION(hashtable_ibl_entry_stats) && table->entry_stats != NULL) {
if (TEST(HASHTABLE_USE_ENTRY_STATS, table->table_flags)) {
memset(table->entry_stats, 0,
table->capacity * sizeof(fragment_stat_entry_t));
}
}
# endif
# endif
table->entries = 0;
table->unlinked_entries = 0;
}
/* removes all entries within a specified range of tags
*
* should generalize hashtable_reset to do this in all cases,
* yet we haven't had an instance where this is necessary
*
* FIXME: note that we don't do a full type dispatch here, while
* hashtable_reset is not properly moving elements hence can't be used
* for removing subsets, and is inefficient!
*/
static uint
HTNAME(hashtable_, NAME_KEY, _range_remove)(dcontext_t *dcontext,
HTNAME(, NAME_KEY, _table_t) * table,
ptr_uint_t tag_start, ptr_uint_t tag_end,
bool (*filter)(ENTRY_TYPE e))
{
int i;
ENTRY_TYPE e;
uint entries_removed = 0;
DEBUG_DECLARE(uint entries_initial = 0;)
ASSERT(!TEST(HASHTABLE_READ_ONLY, table->table_flags));
if (TEST(HASHTABLE_READ_ONLY, table->table_flags))
return 0;
LOG(THREAD, LOG_HTABLE, 2, "hashtable_" KEY_STRING "_range_remove\n");
DOLOG(2, LOG_HTABLE | LOG_STATS, {
HTNAME(hashtable_, NAME_KEY, _load_statistics)(dcontext, table);
});
DODEBUG({
HTNAME(hashtable_, NAME_KEY, _study)(dcontext, table, 0 /*table consistent*/);
/* ensure write lock is held if the table is shared, unless exiting */
if (!dynamo_exited)
ASSERT_TABLE_SYNCHRONIZED(table, WRITE); /* remove requires write lock */
entries_initial = table->entries;
});
/* Deletion in hashtable_NAME_KEY_remove_helper has to move entries
* in order to keep all reachable. We go in reverse order to
* efficiently delete all entries */
i = table->capacity - 1 - 1 /* sentinel */;
while (i >= 0) {
e = table->table[i];
if (!ENTRY_IS_EMPTY(e) && ENTRY_TAG(e) >= tag_start && ENTRY_TAG(e) < tag_end &&
(filter == NULL || filter(e))) {
if (HTNAME(hashtable_, NAME_KEY, _remove_helper)(table, i,
&table->table[i])) {
/* Pulled a chain across the wraparound, so we must start over
* at the end as otherwise we will never look at that last
* element (case 10384).
*/
i = table->capacity - 1 - 1 /* sentinel */;
} else {
/* we can assume deletion doesn't move any entries ahead of i
* to smaller values, so i stays here
*/
}
entries_removed++;
/* de-allocate payload */
HTNAME(hashtable_, NAME_KEY, _free_entry)(dcontext, table, e);
} else {
i--;
}
}
ASSERT(table->entries + entries_removed == entries_initial);
return entries_removed;
}
/* removes all unlinked entries from table's lookup table */
static uint
HTNAME(hashtable_, NAME_KEY, _unlinked_remove)(dcontext_t *dcontext,
HTNAME(, NAME_KEY, _table_t) * table)
{
int i;
ENTRY_TYPE e UNUSED;
uint entries_removed = 0;
ASSERT(!TEST(HASHTABLE_READ_ONLY, table->table_flags));
if (TEST(HASHTABLE_READ_ONLY, table->table_flags))
return 0;
LOG(THREAD, LOG_HTABLE, 2, "hashtable_" KEY_STRING "_unlinked_remove\n");
/* body based on hashtable_range_remove() */
ASSERT(TEST(HASHTABLE_LOCKLESS_ACCESS, table->table_flags));
DOLOG(2, LOG_HTABLE | LOG_STATS, {
HTNAME(hashtable_, NAME_KEY, _load_statistics)(dcontext, table);
});
DODEBUG({
/* ensure write lock is held if the table is shared, unless exiting */
if (!dynamo_exited)
ASSERT_TABLE_SYNCHRONIZED(table, WRITE); /* remove requires write lock */
});
/* Deletion in fragment_remove_fragment_helper has to move entries
* in order to keep all reachable. We go in reverse order to
* efficiently delete all entries
*/
i = (int)table->capacity - 1 - 1 /* sentinel */;
while (i >= 0) {
e = table->table[i];
if (ENTRY_IS_INVALID(e)) {
LOG(THREAD, LOG_HTABLE | LOG_STATS, 2, "unlinked_remove(%s) -- %u\n",
table->name, i);
if (HTNAME(hashtable_, NAME_KEY, _remove_helper)(table, i,
&table->table[i])) {
/* Pulled a chain across the wraparound, so we must start over
* at the end as otherwise we will never look at that last
* element (case 10384).
*/
i = table->capacity - 1 - 1 /* sentinel */;
} else {
/* we can assume deletion doesn't move any entries ahead of i
* to smaller values, so i stays here
*/
}
entries_removed++;
} else {
i--;
}
}
/* fragment_remove_fragment_helper decrements table->entries but we
* want only unlinked_entries decremented, so adjust entries. */
table->entries += entries_removed;
LOG(THREAD, LOG_HTABLE | LOG_STATS, 1, "unlinked_remove(%s) -- %d deletions\n",
table->name, entries_removed);
ASSERT(entries_removed == table->unlinked_entries);
# ifdef HASHTABLE_USE_LOOKUPTABLE
DODEBUG({
/* Check that there are no remnants of unlinked fragments in the table. */
for (i = 0; i < (int)table->capacity; i++) {
ASSERT(!ENTRY_IS_INVALID(table->table[i]));
ASSERT(!AUX_ENTRY_IS_INVALID(table->lookuptable[i]));
ASSERT(!AUX_PAYLOAD_IS_INVALID(dcontext, table, table->lookuptable[i]));
}
});
# else
DODEBUG({
/* Check that there are no remnants of unlinked fragments in the table. */
for (i = 0; i < (int)table->capacity; i++) {
ASSERT(!ENTRY_IS_INVALID(table->table[i]));
}
});
# endif
table->unlinked_entries = 0;
DOLOG(3, LOG_HTABLE, { HTNAME(hashtable_, NAME_KEY, _dump_table)(dcontext, table); });
DODEBUG({
HTNAME(hashtable_, NAME_KEY, _study)(dcontext, table, 0 /*table consistent*/);
});
return entries_removed;
}
/* we should clean the table from entries that are not frequently used
*/
static void
HTNAME(hashtable_, NAME_KEY, _groom_table)(dcontext_t *dcontext,
HTNAME(, NAME_KEY, _table_t) * table)
{
DOLOG(1, LOG_STATS, { d_r_print_timestamp(THREAD); });
LOG(THREAD, LOG_HTABLE, 1, "hashtable_" KEY_STRING "_groom_table %s\n", table->name);
/* flush only tables caching data persistent in another table */
ASSERT(TEST(HASHTABLE_NOT_PRIMARY_STORAGE, table->table_flags));
DOLOG(3, LOG_HTABLE, { HTNAME(hashtable_, NAME_KEY, _dump_table)(dcontext, table); });
LOG(THREAD, LOG_HTABLE, 2, "%s hashtable flushing at %d entries capacity %d\n",
table->name, table->entries, table->capacity);
/* most simple grooming technique - just flush everyone */
HTNAME(hashtable_, NAME_KEY, _range_remove)(dcontext, table, 0, UINT_MAX, NULL);
ASSERT(table->entries == 0);
/* FIXME: we should do better - we can tag fragments that have
* been readded after getting flushed, so that they are not
* flushed next time we do this Some kind of aging that can be
* used also if we do a real clock working set.
*/
/* will not flush again until table gets resized */
table->groom_threshold = 0;
/* FIXME: we may want to do this more often - so that we can catch
* phases and that we don't even have to resize if working set
* does in fact fit here. In that case we may want to
* do have a step function,
* e.g. (groom 50, resize 80, groom step 10) translating into
* 50 - groom, 60 - groom, 70 - groom, 80 - resize
*/
STATS_INC(num_ibt_groomed);
LOG(THREAD, LOG_HTABLE, 1,
"hashtable_" KEY_STRING "_groom_table %s totally groomed - "
"should be empty\n",
table->name);
DOLOG(3, LOG_HTABLE, { HTNAME(hashtable_, NAME_KEY, _dump_table)(dcontext, table); });
}
static inline void
HTNAME(hashtable_, NAME_KEY, _groom_helper)(dcontext_t *dcontext,
HTNAME(, NAME_KEY, _table_t) * table)
{
/* flush only tables caching data persistent in another table */
ASSERT(TEST(HASHTABLE_NOT_PRIMARY_STORAGE, table->table_flags));
ASSERT(table->hash_bits != 0);
/* can't double size, and there is no point in resizing
* we have to flush it.
*/
LOG(THREAD, LOG_HTABLE, 1,
"hashtable_" KEY_STRING "_check_size reached maximum size %s\n", table->name);
/* Currently groom_table() resets the whole table, but if
* it gets smarter, we may want to invoke the reset all
* logic here.
*/
table->entries--; /* entry not added yet */
HTNAME(hashtable_, NAME_KEY, _groom_table)(dcontext, table);
table->entries++;
/* can't make forward progress if groom_table() doesn't
* remove at least one entry
*/
ASSERT(table->entries <= table->resize_threshold);
}
# ifdef DEBUG
/* The above dyn.avg.coll is a little off: we can't show average
* succesfull search time, since some collisions are for misses but
* indcalls_miss_stat includes misses both with and without
* collisions.
*/
static void
HTNAME(hashtable_, NAME_KEY,
_study)(dcontext_t *dcontext, HTNAME(, NAME_KEY, _table_t) * table,
uint entries_inc /*amnt table->entries was pre-inced*/)
{
/* hashtable sparseness study */
uint i;
uint max = 0;
uint num = 0, len = 0, num_collisions = 0;
uint total_len = 0;
uint hindex;
const char *name = table->name;
uint ave_len_threshold;
uint overwraps = 0;
ENTRY_TYPE e;
bool lockless_access = TEST(HASHTABLE_LOCKLESS_ACCESS, table->table_flags);
if (!INTERNAL_OPTION(hashtable_study))
return;
/* studying needs the entire table to be in a consistent state.
* we considered having read mean local read/write and write mean global
* read/write, thus making study() a writer and add() a reader,
* but we do want add() and remove() to be exclusive w/o relying on the
* bb building lock, so we have them as writers and study() as a reader.
*/
TABLE_RWLOCK(table, read, lock);
for (i = 0; i < table->capacity; i++) {
e = table->table[i];
DODEBUG({
HTNAME(hashtable_, NAME_KEY, _check_consistency)(dcontext, table, i);
});
if (ENTRY_IS_EMPTY(e))
continue;
if (ENTRY_IS_SENTINEL(e)) {
ASSERT(i == table->capacity - 1);
/* don't count in collision length - not a real fragment */
continue;
}
hindex = HASH_FUNC(ENTRY_TAG(e), table);
if (i < hindex) {
len = i + (table->capacity - hindex - 1) + 1; /* counting the sentinel */
overwraps++;
LOG(THREAD, LOG_HTABLE | LOG_STATS, 2,
"WARNING: hashtable_" KEY_STRING "_study: overwrap[%d] of "
"len=%d, F tag=" PFX ",i=%d,hindex=%d\n",
overwraps, len, ENTRY_TAG(e), i, hindex);
} else {
len = i - hindex + 1;
}
if (ENTRY_IS_INVALID(e)) {
ASSERT(lockless_access);
LOG(THREAD, LOG_HTABLE | LOG_STATS, 2,
"hashtable_" KEY_STRING "_study: entry not found in %s[%u]\n",
table->name, i);
len = 0;
continue;
}
/* check for unique entries - the entry found by
* fragment_lookup_in_hashtable should be us! */
else {
uint found_at_hindex;
ENTRY_TYPE *pg = HTNAME(hashtable_, NAME_KEY,
_lookup_for_removal)(e, table, &found_at_hindex);
ASSERT(pg != NULL);
ASSERT(ENTRIES_ARE_EQUAL(table, *pg, e));
ASSERT(found_at_hindex == i && "duplicate entry found");
}
if (len > 0) {
if (len > max)
max = len;
total_len += len;
num++;
if (len > 1) {
num_collisions++;
}
}
}
DOLOG(1, LOG_HTABLE | LOG_STATS, {
uint st_top = 0;
uint st_bottom = 0;
if (num != 0)
divide_uint64_print(total_len, num, false, 2, &st_top, &st_bottom);
LOG(THREAD, LOG_HTABLE | LOG_STATS, 1,
"%s %s hashtable statistics: num=%d, max=%d, #>1=%d, st.avg=%u.%.2u\n",
entries_inc == 0 ? "Total" : "Current", name, num, max, num_collisions,
st_top, st_bottom);
});
/* static average length is supposed to be under 5 even up
* to load factors of 90% see Knuth vol.3 or in CLR (p.238-9 in
* first edition) but of course only if we had uniformly
* distributed hash functions
*/
/* for bug 2271 we make more lenient for non trace tables using the
* _NONE hash function (i.e. private bb) when we are !SHARED_FRAGMENTS_ENABLED().
*/
if (!TEST(HASHTABLE_RELAX_CLUSTER_CHECKS, table->table_flags) &&
(lockless_access || table->hash_func != HASH_FUNCTION_NONE ||
SHARED_FRAGMENTS_ENABLED()))
ave_len_threshold = 5;
else
ave_len_threshold = 10;
DOLOG(1, LOG_HTABLE | LOG_STATS, {
/* This happens enough that it's good to get some info on it */
if (!(total_len <= ave_len_threshold * num ||
(TEST(HASHTABLE_RELAX_CLUSTER_CHECKS, table->table_flags) &&
table->capacity <= 513))) {
/* Hash table high average collision length */
LOG(THREAD, LOG_HTABLE | LOG_STATS, 1,
"WARNING: high average collision length for htable %s\n"
" ave len: tot=%d <= %d, cap=%d entr=%d fac=%d\n",
name, total_len, ave_len_threshold * num, table->capacity, table->entries,
table->load_factor_percent);
HTNAME(hashtable_, NAME_KEY, _dump_table)(dcontext, table);
}
});
DOLOG(3, LOG_HTABLE, { HTNAME(hashtable_, NAME_KEY, _dump_table)(dcontext, table); });
{
uint doublecheck = num + entries_inc;
LOG(THREAD, LOG_HTABLE | LOG_STATS, 2,
"\t%s doublecheck %u (unlinked %u) == %u %d\n", name, table->entries,
table->unlinked_entries, doublecheck, entries_inc);
ASSERT(table->entries == doublecheck);
}
# ifdef HASHTABLE_STATISTICS
print_hashtable_stats(dcontext, entries_inc == 0 ? "Total" : "Current", name,
"fragment_lookup", "", &table->drlookup_stats);
# endif
HTNAME(hashtable_, NAME_KEY, _study_custom)(dcontext, table, entries_inc);
TABLE_RWLOCK(table, read, unlock);
}
void
HTNAME(hashtable_, NAME_KEY, _dump_table)(dcontext_t *dcontext,
HTNAME(, NAME_KEY, _table_t) * htable)
{
uint i;
bool track_cache_lines;
bool entry_size;
size_t line_size = proc_get_cache_line_size();
uint cache_lines_used = 0;
bool cache_line_in_use = false;
# ifdef HASHTABLE_USE_LOOKUPTABLE
track_cache_lines = true;
entry_size = sizeof(AUX_ENTRY_TYPE);
# else
track_cache_lines = TEST(HASHTABLE_ALIGN_TABLE, htable->table_flags);
entry_size = sizeof(ENTRY_TYPE);
# endif
DOLOG(1, LOG_HTABLE | LOG_STATS, {
HTNAME(hashtable_, NAME_KEY, _load_statistics)(dcontext, htable);
});
LOG(THREAD, LOG_HTABLE, 1, " i tag coll hits age %s dump\n",
htable->name);
/* need read lock to traverse the table */
TABLE_RWLOCK(htable, read, lock);
for (i = 0; i < htable->capacity; i++) {
if (track_cache_lines && (i * entry_size % line_size == 0)) {
if (cache_line_in_use)
cache_lines_used++;
cache_line_in_use = false;
}
if (ENTRY_IS_INVALID(htable->table[i])) {
LOG(THREAD, LOG_HTABLE, 1, "%6x *** unlinked marker ***\n", i);
} else if (ENTRY_IS_REAL(htable->table[i])) {
uint preferred = HASH_FUNC(ENTRY_TAG(htable->table[i]), htable);
uint collision_len = (preferred <= i)
? i - preferred /* collision */
: (htable->capacity + i - preferred) /* with overwrap */;
/* overwrap count should include the sentinel to total length */
# if defined(HASHTABLE_STATISTICS) && defined(HASHTABLE_ENTRY_STATS)
LOG(THREAD, LOG_HTABLE, 1, "%6x " PFX " %3d %c %8d %3d\n", i,
ENTRY_TAG(htable->table[i]), collision_len + 1,
(preferred <= i) ? ' ' : 'O' /* overwrap */,
htable->entry_stats ? htable->entry_stats[i].hits : 0,
htable->entry_stats ? htable->entry_stats[i].age : 0);
# else /* !(HASHTABLE_STATISTICS && HASHTABLE_ENTRY_STATS) */
LOG(THREAD, LOG_HTABLE, 1, "%6x " PFX " %3d %c \n", i,
ENTRY_TAG(htable->table[i]), collision_len + 1,
(preferred <= i) ? ' ' : 'O' /* overwrap */
);
# endif /* (HASHTABLE_STATISTICS && HASHTABLE_ENTRY_STATS) */
if (track_cache_lines)
cache_line_in_use = true;
} else {
/* skip null_fragment entries */
}
DOLOG(2, LOG_HTABLE, {
/* print full table */
if (ENTRY_IS_EMPTY(htable->table[i])) {
LOG(THREAD, LOG_HTABLE, 2, "%6x " PFX "\n", i, 0);
}
});
DOLOG(2, LOG_HTABLE, {
if (track_cache_lines && (i + 1) * entry_size % line_size == 0 &&
cache_line_in_use) {
LOG(THREAD, LOG_HTABLE, 1, "----cache line----\n");
}
});
DODEBUG({
HTNAME(hashtable_, NAME_KEY, _check_consistency)(dcontext, htable, i);
});
}
if (track_cache_lines) {
if (cache_line_in_use)
cache_lines_used++;
if (cache_lines_used) {
LOG(THREAD, LOG_HTABLE, 1,
"%s %d%% cache density, cache_lines_used=%d "
"(%dKB), minimum needed %d (%dKB)\n",
htable->name,
100 * htable->entries * entry_size / (cache_lines_used * line_size),
cache_lines_used, cache_lines_used * line_size / 1024,
htable->entries * entry_size / line_size,
htable->entries * entry_size / 1024);
}
}
TABLE_RWLOCK(htable, read, unlock);
}
# endif /* DEBUG */
# if defined(DEBUG) && defined(INTERNAL)
static void
HTNAME(hashtable_, NAME_KEY, _load_statistics)(dcontext_t *dcontext,
HTNAME(, NAME_KEY, _table_t) * table)
{
LOG(THREAD, LOG_HTABLE | LOG_STATS, 1,
"%s hashtable: %d entries, %d unlinked entries, %d capacity,"
" %d%% load\n",
table->name, table->entries, table->unlinked_entries, table->capacity,
(100 * table->entries) / table->capacity);
}
# endif
# ifdef HASHTABLE_STATISTICS
# ifdef HASHTABLE_ENTRY_STATS
void
HTNAME(hashtable_, NAME_KEY, _dump_entry_stats)(dcontext_t *dcontext,
HTNAME(, NAME_KEY, _table_t) * htable)
{
/* mostly a copy of dump_table but printing only entries with non 0 stats */
uint i;
uint max_age = 0;
DOLOG(1, LOG_STATS, { d_r_print_timestamp(THREAD); });
LOG(THREAD, LOG_HTABLE, 1, "dump_and_clean_entry_statistics: %s\n", htable->name);
DOLOG(1, LOG_HTABLE | LOG_STATS, {
HTNAME(hashtable_, NAME_KEY, _load_statistics)(dcontext, htable);
/* TODO: should preserve a copy of the old hashtable_statistics_t
* so that the difference between the two can be matched with
* the per-entry hits and collisions. though a Perl script will do.
*/
});
LOG(THREAD, LOG_HTABLE, 1, " i tag coll hits age %s\n",
htable->name);
/* need read lock to traverse the table */
TABLE_RWLOCK(htable, read, lock);
for (i = 0; i < htable->capacity; i++) {
if (!ENTRY_IS_EMPTY(htable->table[i]) && !ENTRY_IS_INVALID(htable->table[i])) {
uint preferred = HASH_FUNC(ENTRY_TAG(htable->table[i]), htable);
uint collision_len = (preferred <= i)
? i - preferred /* collision */
: (htable->capacity + i - preferred) /* with overwrap */;
if (htable->entry_stats[i].hits == 0) {
/* no hits in a row */
htable->entry_stats[i].age++;
if (max_age < htable->entry_stats[i].age)
max_age = htable->entry_stats[i].age;
}
LOG(THREAD, LOG_HTABLE, htable->entry_stats[i].hits ? 1U : 2U, /* only hits */
"%6x " PFX " %3d %c %8d %3d\n", i, ENTRY_TAG(htable->table[i]),
collision_len + 1, (preferred <= i) ? ' ' : 'O' /* overwrap */,
htable->entry_stats[i].hits, htable->entry_stats[i].age);
} else {
/* skip null_fragment entries */
}
DODEBUG({
HTNAME(hashtable_, NAME_KEY, _check_consistency)(dcontext, htable, i);
});
}
if (max_age > 0) {
LOG(THREAD, LOG_HTABLE, 1,
"hashtable_" KEY_STRING "dump_entry_stats: %s max_age:%d\n", htable->name,
max_age);
}
TABLE_RWLOCK(htable, read, unlock);
}
# endif
# endif /* HASHTABLE_STATISTICS */
# ifdef HASHTABLE_SUPPORT_PERSISTENCE
uint
HTNAME(hashtable_, NAME_KEY, _persist_size)(dcontext_t *dcontext,
HTNAME(, NAME_KEY, _table_t) * htable)
{
if (htable == NULL)
return 0;
return (sizeof(*htable) + (htable->capacity * sizeof(ENTRY_TYPE)));
}
/* We need enough of the htable struct fields that we simply persist
* the entire struct to avoid defining a separate subset struct.
* The version field of the entire file suffices to version the htable struct.
* The table pointer (and stats in debug) need to be writable,
* so at load time we do not directly use the mmapped copy, but we could
* with a little work (case 10349: see comments below as well) (not worth
* making COW and having the whole page private: case 9582).
* Returns true iff all writes succeeded.
*/
bool
HTNAME(hashtable_, NAME_KEY, _persist)(dcontext_t *dcontext,
HTNAME(, NAME_KEY, _table_t) * htable, file_t fd)
{
uint size;
ASSERT(htable != NULL);
if (htable == NULL)
return false;
ASSERT(fd != INVALID_FILE);
size = sizeof(*htable);
if (os_write(fd, htable, size) != (int)size)
return false;
/* We don't bother to align */
size = htable->capacity * sizeof(ENTRY_TYPE);
if (os_write(fd, htable->table, size) != (int)size)
return false;
return true;
}
static uint
HTNAME(hashtable_, NAME_KEY, _num_unique_entries)(dcontext_t *dcontext,
HTNAME(, NAME_KEY, _table_t) * src1,
HTNAME(, NAME_KEY, _table_t) * src2)
{
HTNAME(, NAME_KEY, _table_t) * big, *small;
uint unique, i;
ENTRY_TYPE e;
ASSERT(src1 != NULL && src2 != NULL);
if (src1->entries >= src2->entries) {
big = src1;
small = src2;
} else {
big = src2;
small = src1;
}
unique = big->entries;
/* Deadlock-avoidance won't let us grab both locks; for now we only
* use this when all-synched so we let that solve the problem.
* N.B.: we assume that on suspend failure for flush synchall
* (which ignores such failures) we do not come here as we abort
* coarse freezing/merging/persist. FIXME: should we export
* another variable, or not set dynamo_all_threads_synched?
*/
ASSERT(dynamo_all_threads_synched);
DODEBUG({ big->is_local = true; });
TABLE_RWLOCK(small, read, lock);
for (i = 0; i < small->capacity; i++) {
e = small->table[i];
if (ENTRY_IS_REAL(e)) {
if (ENTRY_IS_EMPTY(
HTNAME(hashtable_, NAME_KEY, _lookup(dcontext, ENTRY_TAG(e), big))))
unique++;
}
}
TABLE_RWLOCK(small, read, unlock);
DODEBUG({ big->is_local = false; });
return unique;
}
/* Adds all entries from src to dst */
static void
HTNAME(hashtable_, NAME_KEY,
_add_all)(dcontext_t *dcontext, HTNAME(, NAME_KEY, _table_t) * dst,
HTNAME(, NAME_KEY, _table_t) * src, bool check_dups)
{
ENTRY_TYPE e;
uint i;
ASSERT(dst != NULL && src != NULL);
/* assumption: dst is private to this thread and so does not need synch */
DODEBUG({ dst->is_local = true; });
TABLE_RWLOCK(src, read, lock);
for (i = 0; i < src->capacity; i++) {
e = src->table[i];
if (ENTRY_IS_REAL(e)) {
if (!check_dups ||
ENTRY_IS_EMPTY(
HTNAME(hashtable_, NAME_KEY, _lookup(dcontext, ENTRY_TAG(e), dst)))) {
/* add will also add lookuptable entry, if any */
HTNAME(hashtable_, NAME_KEY, _add)(dcontext, e, dst);
}
}
}
TABLE_RWLOCK(src, read, unlock);
DODEBUG({ dst->is_local = false; });
}
/* Creates a new hashtable that contains the union of src1 and src2 (removing
* the duplicates)
*/
HTNAME(, NAME_KEY, _table_t) *
HTNAME(hashtable_, NAME_KEY, _merge)(dcontext_t *dcontext,
HTNAME(, NAME_KEY, _table_t) * src1,
HTNAME(, NAME_KEY, _table_t) * src2)
{
HTNAME(, NAME_KEY, _table_t) * dst;
uint merged_entries, init_bits;
ASSERT(src1 != NULL && src2 != NULL);
/* We only support merging the same type of table */
ASSERT((src1->table_flags & ~(HASHTABLE_COPY_IGNORE_FLAGS)) ==
(src2->table_flags & ~(HASHTABLE_COPY_IGNORE_FLAGS)));
ASSERT(src1->load_factor_percent == src2->load_factor_percent);
ASSERT(src1->hash_func == src2->hash_func);
dst = (HTNAME(, NAME_KEY, _table_t) *)TABLE_TYPE_MEMOP(
src1->table_flags, ALLOC, dcontext, HTNAME(, NAME_KEY, _table_t),
HASHTABLE_WHICH_HEAP(src1->table_flags), PROTECTED);
merged_entries =
HTNAME(hashtable_, NAME_KEY, _num_unique_entries)(dcontext, src1, src2);
LOG(THREAD, LOG_HTABLE, 2,
"hashtable_" KEY_STRING "_merge: %d + %d => %d unique entries\n", src1->entries,
src2->entries, merged_entries);
init_bits = hashtable_bits_given_entries(merged_entries, src1->load_factor_percent);
HTNAME(hashtable_, NAME_KEY, _init)
(dcontext, dst, init_bits, src1->load_factor_percent, src1->hash_func,
src1->hash_mask_offset _IFLOOKUP(use_lookup),
src1->table_flags & ~(HASHTABLE_COPY_IGNORE_FLAGS)_IF_DEBUG(src1->name));
HTNAME(hashtable_, NAME_KEY, _add_all)
(dcontext, dst, src1, false /*don't check dups*/);
HTNAME(hashtable_, NAME_KEY, _add_all)(dcontext, dst, src2, true /*check dups*/);
return dst;
}
/* Performs a deep copy (struct plus table) of src */
HTNAME(, NAME_KEY, _table_t) *
HTNAME(hashtable_, NAME_KEY, _copy)(dcontext_t *dcontext,
HTNAME(, NAME_KEY, _table_t) * src)
{
HTNAME(, NAME_KEY, _table_t) * dst;
ASSERT(src != NULL);
dst = (HTNAME(, NAME_KEY, _table_t) *)TABLE_TYPE_MEMOP(
src->table_flags, ALLOC, dcontext, HTNAME(, NAME_KEY, _table_t),
HASHTABLE_WHICH_HEAP(src->table_flags), PROTECTED);
/* use init() rather than memcpy of header, so we get table and/or lookuptable
* allocated to proper alignment
*/
HTNAME(hashtable_, NAME_KEY, _init)
(dcontext, dst, src->hash_bits, src->load_factor_percent, src->hash_func,
src->hash_mask_offset _IFLOOKUP(use_lookup),
src->table_flags & ~(HASHTABLE_COPY_IGNORE_FLAGS)_IF_DEBUG(src->name));
dst->entries = src->entries;
dst->unlinked_entries = src->unlinked_entries;
if (dst->table != NULL)
memcpy(dst->table, src->table, dst->capacity * sizeof(ENTRY_TYPE));
# ifdef HASHTABLE_USE_LOOKUPTABLE
if (dst->lookuptable != NULL) {
memcpy(dst->lookuptable, src->lookuptable,
dst->capacity * sizeof(AUX_ENTRY_TYPE));
}
# endif
return dst;
}
/* See comments in HTNAME(hashtable_,NAME_KEY,_persist)
* Returns a newly allocated struct on the heap.
*/
HTNAME(, NAME_KEY, _table_t) *
HTNAME(hashtable_, NAME_KEY,
_resurrect)(dcontext_t *dcontext,
byte *mapped_table _IF_DEBUG(const char *table_name))
{
HTNAME(, NAME_KEY, _table_t) * htable;
uint flags;
ASSERT(mapped_table != NULL);
flags = ((HTNAME(, NAME_KEY, _table_t) *)mapped_table)->table_flags;
/* FIXME: the free, and the init alloc, are in client code: would be better
* to have all in same file using more-easily-kept-consistent alloc routines
*/
htable = (HTNAME(, NAME_KEY, _table_t) *)TABLE_TYPE_MEMOP(
flags, ALLOC, dcontext, HTNAME(, NAME_KEY, _table_t),
HASHTABLE_WHICH_HEAP(table->table_flags), PROTECTED);
/* FIXME case 10349: we could directly use the mmapped struct when
* !HASHTABLE_STATISTICS if we supported calculating where the table lies
* in all the htable routines, and set HASHTABLE_READ_ONLY when persisting
*/
memcpy(htable, mapped_table, sizeof(*htable));
htable->table_flags |= HASHTABLE_READ_ONLY;
htable->table = (ENTRY_TYPE *)(mapped_table + sizeof(*htable));
htable->table_unaligned = NULL;
ASSIGN_INIT_READWRITE_LOCK_FREE(htable->rwlock, HTLOCK_RANK);
DODEBUG({ htable->name = table_name; });
# ifdef HASHTABLE_STATISTICS
INIT_HASHTABLE_STATS(htable->drlookup_stats);
# endif
return htable;
}
# endif /* HASHTABLE_SUPPORT_PERSISTENCE */
#endif
/****************************************************************************/
/* make it easier to have multiple instantiations in a file
* user must re-specify name and types for struct and impl, though
*/
#undef NAME_KEY
#undef ENTRY_TYPE
#undef AUX_ENTRY_TYPE
#undef CUSTOM_FIELDS
#undef ENTRY_TAG
#undef ENTRY_IS_EMPTY
#undef ENTRY_IS_SENTINEL
#undef ENTRY_IS_INVALID
#undef ENTRIES_ARE_EQUAL
#undef ENTRY_SET_TO_ENTRY
#undef ENTRY_EMPTY
#undef ENTRY_SENTINEL
#undef TAGS_ARE_EQUAL
#undef AUX_ENTRY_TAG
#undef AUX_ENTRY_IS_EMPTY
#undef AUX_ENTRY_IS_SENTINEL
#undef AUX_ENTRY_IS_INVALID
#undef AUX_PAYLOAD_IS_INVALID
#undef AUX_ENTRY_SET_TO_SENTINEL
#undef AUX_ENTRY_IS_SET_TO_ENTRY
#undef AUX_ENTRY_SET_TO_ENTRY
#undef AUX_ENTRY_FORMAT_STR
#undef AUX_ENTRY_FORMAT_ARGS
#undef HASHTABLE_WHICH_HEAP
#undef HASHTABLE_USE_LOOKUPTABLE
#undef HASHTABLE_ENTRY_STATS
#undef HASHTABLE_SUPPORT_PERSISTENCE
#undef HTLOCK_RANK
#undef _IFLOOKUP
#undef IFLOOKUP_ELSE