blob: c53fcd59e9f54096878e88e0a21d3bc9f910bf99 [file] [log] [blame]
/* **********************************************************
* Copyright (c) 2011-2022 Google, Inc. All rights reserved.
* Copyright (c) 2007-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.
*/
/* Containers DynamoRIO Extension: Hashtable */
#ifndef _HASHTABLE_H_
#define _HASHTABLE_H_ 1
/**
* @file hashtable.h
* @brief Header for DynamoRIO Hashtable Extension
*/
#ifdef __cplusplus
extern "C" {
#endif
/***************************************************************************
* HASHTABLE
*/
/**
* \addtogroup drcontainers Container Data Structures
*/
/**@{*/ /* begin doxygen group */
/** The type of hash key */
typedef enum {
HASH_INTPTR, /**< A pointer-sized integer or pointer */
HASH_STRING, /**< A case-sensitive string */
HASH_STRING_NOCASE, /**< A case-insensitive string */
/**
* A custom key. Hash and compare operations must be provided
* in hashtable_init_ex(). The hash operation can return a full
* uint, as its result will be truncated via a mod of the
* hash key bit size. This allows for resizing the table
* without changing the hash operation.
*/
HASH_CUSTOM,
} hash_type_t;
typedef struct _hash_entry_t {
void *key;
void *payload;
struct _hash_entry_t *next;
} hash_entry_t;
/** Configuration parameters for a hashtable. */
typedef struct _hashtable_config_t {
size_t size; /**< The size of the hashtable_config_t struct used */
bool resizable; /**< Whether the table should be resized */
uint resize_threshold; /**< Resize the table at this % full */
/**
* Called whenever an entry is removed, with the key passed in. If "str_dup" is set
* to true in hashtable_init() or hashtable_init_ex(), this field is ignored.
*/
void (*free_key_func)(void *);
} hashtable_config_t;
typedef struct _hashtable_t {
hash_entry_t **table;
hash_type_t hashtype;
bool str_dup;
void *lock;
uint table_bits;
bool synch;
void (*free_payload_func)(void *);
uint (*hash_key_func)(void *);
bool (*cmp_key_func)(void *, void *);
uint entries;
hashtable_config_t config;
uint persist_count;
} hashtable_t;
/* should move back to utils.c once have iterator and alloc_exit
* doesn't need this macro
*/
#define HASHTABLE_SIZE(num_bits) (1U << (num_bits))
/** Caseless string compare */
bool
stri_eq(const char *s1, const char *s2);
/**
* The hashtable has parametrized heap and assert routines for flexibility.
* This routine must be called BEFORE any other hashtable_ routine; else,
* the defaults will be used.
*/
void
hashtable_global_config(void *(*alloc_func)(size_t), void (*free_func)(void *, size_t),
void (*assert_fail_func)(const char *));
/**
* Initializes a hashtable with the given size, hash type, and whether to
* duplicate string keys. All operations are synchronized by default.
*/
void
hashtable_init(hashtable_t *table, uint num_bits, hash_type_t hashtype, bool str_dup);
/**
* Initializes a hashtable with the given parameters.
*
* @param[out] table The hashtable to be initialized.
* @param[in] num_bits The initial number of bits to use for the hash key
* which determines the initial size of the table itself. The result of the
* hash function will be truncated to this size. This size will be
* increased when the table is resized (resizing always doubles the size).
* @param[in] hashtype The type of hash to perform.
* @param[in] str_dup Whether to duplicate string keys.
* @param[in] synch Whether to synchronize each operation.
* Even when \p synch is false, the hashtable's lock is initialized and can
* be used via hashtable_lock() and hashtable_unlock(), allowing the caller
* to extend synchronization beyond just the operation in question, to
* include accessing a looked-up payload, e.g.
* @param[in] free_payload_func A callback for freeing each payload.
* Leave it NULL if no callback is needed.
* @param[in] hash_key_func A callback for hashing a key.
* Leave it NULL if no callback is needed and the default is to be used.
* For HASH_CUSTOM, a callback must be provided.
* The hash operation can return a full uint, as its result will be
* truncated via a mod of the hash key bit size. This allows for resizing
* the table without changing the hash operation.
* @param[in] cmp_key_func A callback for comparing two keys.
* Leave it NULL if no callback is needed and the default is to be used.
* For HASH_CUSTOM, a callback must be provided.
*
* This hashtable uses closed addressing.
* For an open-address hashtable, consider dr_hashtable_create().
*/
void
hashtable_init_ex(hashtable_t *table, uint num_bits, hash_type_t hashtype, bool str_dup,
bool synch, void (*free_payload_func)(void *),
uint (*hash_key_func)(void *), bool (*cmp_key_func)(void *, void *));
/** Configures optional parameters of hashtable operation. */
void
hashtable_configure(hashtable_t *table, hashtable_config_t *config);
/** Returns the payload for the given key, or NULL if the key is not found */
void *
hashtable_lookup(hashtable_t *table, void *key);
/**
* Adds a new entry. Returns false if an entry for \p key already exists.
* \note Never use NULL as a payload as that is used for a lookup failure.
*/
bool
hashtable_add(hashtable_t *table, void *key, void *payload);
/**
* Adds a new entry, replacing an existing entry if any.
* Returns the old payload, or NULL if there was no existing entry.
* \note Never use NULL as a payload as that is used for a lookup failure.
*/
void *
hashtable_add_replace(hashtable_t *table, void *key, void *payload);
/**
* Removes the entry for key. If free_payload_func was specified calls it
* for the payload being removed. Returns false if no such entry
* exists.
*/
bool
hashtable_remove(hashtable_t *table, void *key);
/**
* Removes all entries with key in [start..end). If free_payload_func
* was specified calls it for each payload being removed. Returns
* false if no such entry exists.
*/
bool
hashtable_remove_range(hashtable_t *table, void *start, void *end);
/**
* Calls the \p apply_func for each payload.
* @param table The hashtable to apply the function.
* @param apply_func A pointer to a function that is called for all payloads
* stored in the map.
*/
void
hashtable_apply_to_all_payloads(hashtable_t *table, void (*apply_func)(void *payload));
/**
* Calls the \p apply_func for each payload with user data. Similar to
* hashtable_apply_to_all_payloads().
* @param table The hashtable to apply the function.
* @param apply_func A pointer to a function that is called for all payloads
* stored in the map. It also takes user data as a parameter.
* @param user_data User data that is available when iterating through payloads.
*/
void
hashtable_apply_to_all_payloads_user_data(hashtable_t *table,
void (*apply_func)(void *payload,
void *user_data),
void *user_data);
/**
* Removes all entries from the table. If free_payload_func was specified
* calls it for each payload.
*/
void
hashtable_clear(hashtable_t *table);
/**
* Destroys all storage for the table, including all entries and the
* table itself. If free_payload_func was specified calls it for each
* payload.
*/
void
hashtable_delete(hashtable_t *table);
/** Acquires the hashtable lock. */
void
hashtable_lock(hashtable_t *table);
/** Releases the hashtable lock. */
void
hashtable_unlock(hashtable_t *table);
/**
* Returns true iff the hashtable lock is owned by the calling thread.
* This routine is only available in debug builds.
* In release builds it always returns true.
*/
bool
hashtable_lock_self_owns(hashtable_t *table);
/* DR_API EXPORT BEGIN */
/** Flags to control hashtable persistence */
typedef enum {
/**
* Valid for hashtable_persist() and hashtable_resurrect() and the
* same value must be passed to both. Treats payloads as pointers
* to allocated memory. By default payloads are treated as
* inlined values if this flag is not set.
*/
DR_HASHPERS_PAYLOAD_IS_POINTER = 0x0001,
/**
* Valid for hashtable_resurrect(). Only applies if
* DR_HASHPERS_KEY_IS_POINTER. Performs a shallow clone of the
* payload upon resurrection. If this flag is not set, the
* payloads will remain pointing into the mapped file.
*/
DR_HASHPERS_CLONE_PAYLOAD = 0x0002,
/**
* Valid for hashtable_persist_size(), hashtable_persist(), and
* hashtable_resurrect(), and the same value must be passed to all.
* Only applies if keys are of type HASH_INTPTR. Adjusts each key by
* the difference in the persist-time start address of the persisted
* code region and the resurrected start address. The value of this
* flag must match across all three calls hashtable_persist_size(),
* hashtable_persist(), and hashtable_resurrect().
*/
DR_HASHPERS_REBASE_KEY = 0x0004,
/**
* Valid for hashtable_persist_size() and hashtable_persist() and
* the same value must be passed to both. Only applies if keys
* are of type HASH_INTPTR. Only persists entries whose key is
* in the address range being persisted.
*/
DR_HASHPERS_ONLY_IN_RANGE = 0x0008,
/**
* Valid for hashtable_persist_size() and hashtable_persist() and
* the same value must be passed to both. Only applies if keys
* are of type HASH_INTPTR. Only persists entries for which
* dr_fragment_persistable() returns true.
*/
DR_HASHPERS_ONLY_PERSISTED = 0x0010,
} hasthable_persist_flags_t;
/* DR_API EXPORT END */
/**
* For use persisting a table of single-alloc entries (i.e., via a
* shallow copy) for loading into a live table later.
*
* These routines assume that the caller is synchronizing across the
* call to hashtable_persist_size() and hashtable_persist(). If these
* are called using DR's persistence interface, DR guarantees
* synchronization.
*
* @param[in] drcontext The opaque DR context
* @param[in] table The table to persist
* @param[in] entry_size The size of each table entry payload
* @param[in] perscxt The opaque persistence context from DR's persist events
* @param[in] flags Controls various aspects of the persistence
*/
size_t
hashtable_persist_size(void *drcontext, hashtable_t *table, size_t entry_size,
void *perscxt, hasthable_persist_flags_t flags);
/**
* For use persisting a table of single-alloc entries (i.e., via a
* shallow copy) for loading into a live table later.
*
* These routines assume that the caller is synchronizing across the
* call to hashtable_persist_size() and hashtable_persist(). If these
* are called using DR's persistence interface, DR guarantees
* synchronization.
*
* hashtable_persist_size() must be called immediately prior to
* calling hashtable_persist().
*
* @param[in] drcontext The opaque DR context
* @param[in] table The table to persist
* @param[in] entry_size The size of each table entry payload
* @param[in] fd The target persisted file handle
* @param[in] perscxt The opaque persistence context from DR's persist events
* @param[in] flags Controls various aspects of the persistence
*/
bool
hashtable_persist(void *drcontext, hashtable_t *table, size_t entry_size, file_t fd,
void *perscxt, hasthable_persist_flags_t flags);
/**
* For use persisting a table of single-alloc entries (i.e., via a
* shallow copy) for loading into a live table later.
*
* Reads in entries from disk and adds them to the live table.
*
* @param[in] drcontext The opaque DR context
* @param[in] map The mapped-in persisted file, pointing at the
* data written by hashtable_persist()
* @param[in] table The live table to add to
* @param[in] entry_size The size of each table entry payload
* @param[in] perscxt The opaque persistence context from DR's persist events
* @param[in] flags Controls various aspects of the persistence
* @param[in] process_payload If non-NULL, calls process_payload instead of
* hashtable_add. process_payload can then adjust the paylod and if
* it wishes invoke hashtable_add.
*/
bool
hashtable_resurrect(void *drcontext, byte **map /*INOUT*/, hashtable_t *table,
size_t entry_size, void *perscxt, hasthable_persist_flags_t flags,
bool (*process_payload)(void *key, void *payload, ptr_int_t shift));
/**@}*/ /* end doxygen group */
#ifdef __cplusplus
}
#endif
#endif /* _HASHTABLE_H_ */