Google Git
Sign in
chromium / external / dynamorio / 943803169438bfb21cc82c52f9b141574bb4b249 / . / core / hashtablex.h
blob: f807057d8dcbc7cc1a459f7fbe0236a7611c6029 [file] [log] [blame]
/* **********************************************************
* Copyright (c) 2011-2013 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
* 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--;
table->table[hindex] = e;
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
FIXME: 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 now this is too much to 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 address */
/* [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;
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, { 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 colliding_frags = 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++;
colliding_frags += len;
}
}
}
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,
"htable %s 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);
}
});
ASSERT_CURIOSITY((total_len <= ave_len_threshold * num
|| (TEST(HASHTABLE_RELAX_CLUSTER_CHECKS, table->table_flags) &&
table->capacity <= 513))
&& "hash table high average collision length");
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 cache_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 % cache_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 % cache_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 * cache_line_size),
cache_lines_used, cache_lines_used*cache_line_size/1024,
htable->entries*entry_size/cache_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, { 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_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