DynamoRIO API
Container Data Structures

Data Structures

struct  _drvector_t
 
struct  _hashtable_config_t
 

Macros

#define DRTABLE_INVALID_INDEX   ((ptr_uint_t)-1)
 

Typedefs

typedef struct _drvector_t drvector_t
 
typedef struct _hashtable_config_t hashtable_config_t
 

Enumerations

enum  drtable_flags_t {
  DRTABLE_MEM_REACHABLE = 0x1,
  DRTABLE_MEM_32BIT = 0x2,
  DRTABLE_ALLOC_COMPACT = 0x4
}
 
enum  hash_type_t {
  HASH_INTPTR,
  HASH_STRING,
  HASH_STRING_NOCASE,
  HASH_CUSTOM
}
 
enum  hasthable_persist_flags_t {
  DR_HASHPERS_PAYLOAD_IS_POINTER = 0x0001,
  DR_HASHPERS_CLONE_PAYLOAD = 0x0002,
  DR_HASHPERS_REBASE_KEY = 0x0004,
  DR_HASHPERS_ONLY_IN_RANGE = 0x0008,
  DR_HASHPERS_ONLY_PERSISTED = 0x0010
}
 

Functions

void * drtable_create (ptr_uint_t capacity, size_t entry_size, uint flags, bool synch, void(*free_entry_func)(ptr_uint_t idx, void *entry, void *user_data))
 
void * drtable_alloc (void *tab, ptr_uint_t num_entries, ptr_uint_t *idx_ptr)
 
void drtable_destroy (void *tab, void *user_data)
 
void drtable_iterate (void *tab, void *iter_data, bool(*iter_func)(ptr_uint_t id, void *, void *))
 
void * drtable_get_entry (void *tab, ptr_uint_t idx)
 
ptr_uint_t drtable_get_index (void *tab, void *ptr)
 
void drtable_lock (void *tab)
 
void drtable_unlock (void *tab)
 
ptr_uint_t drtable_num_entries (void *tab)
 
ptr_uint_t drtable_dump_entries (void *tab, file_t log)
 
bool drvector_init (drvector_t *vec, uint initial_capacity, bool synch, void(*free_data_func)(void *))
 
void * drvector_get_entry (drvector_t *vec, uint idx)
 
bool drvector_set_entry (drvector_t *vec, uint idx, void *data)
 
bool drvector_append (drvector_t *vec, void *data)
 
bool drvector_delete (drvector_t *vec)
 
void drvector_lock (drvector_t *vec)
 
void drvector_unlock (drvector_t *vec)
 
bool stri_eq (const char *s1, const char *s2)
 
void hashtable_global_config (void *(*alloc_func)(size_t), void(*free_func)(void *, size_t), void(*assert_fail_func)(const char *))
 
void hashtable_init (hashtable_t *table, uint num_bits, hash_type_t hashtype, bool str_dup)
 
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 *))
 
void hashtable_configure (hashtable_t *table, hashtable_config_t *config)
 
void * hashtable_lookup (hashtable_t *table, void *key)
 
bool hashtable_add (hashtable_t *table, void *key, void *payload)
 
void * hashtable_add_replace (hashtable_t *table, void *key, void *payload)
 
bool hashtable_remove (hashtable_t *table, void *key)
 
bool hashtable_remove_range (hashtable_t *table, void *start, void *end)
 
void hashtable_clear (hashtable_t *table)
 
void hashtable_delete (hashtable_t *table)
 
void hashtable_lock (hashtable_t *table)
 
void hashtable_unlock (hashtable_t *table)
 
bool hashtable_lock_self_owns (hashtable_t *table)
 
size_t hashtable_persist_size (void *drcontext, hashtable_t *table, size_t entry_size, void *perscxt, hasthable_persist_flags_t flags)
 
bool hashtable_persist (void *drcontext, hashtable_t *table, size_t entry_size, file_t fd, void *perscxt, hasthable_persist_flags_t flags)
 
bool hashtable_resurrect (void *drcontext, byte **map, 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))
 

Detailed Description

Macro Definition Documentation

#define DRTABLE_INVALID_INDEX   ((ptr_uint_t)-1)

Invalid index of drtable

Typedef Documentation

typedef struct _drvector_t drvector_t

The storage for a vector.

Configuration parameters for a hashtable.

Enumeration Type Documentation

Flags used for drtable_create

Enumerator
DRTABLE_MEM_REACHABLE 

allocated table entries must be reachable from code cache

DRTABLE_MEM_32BIT 

Allocates table entries from the addresss space that can be converted to a 32-bit int.

DRTABLE_ALLOC_COMPACT 

Allocates table entries as compactly as possible, which may return indics in a random order.

The type of hash key

Enumerator
HASH_INTPTR 

A pointer-sized integer or pointer

HASH_STRING 

A case-sensitive string

HASH_STRING_NOCASE 

A case-insensitive string

HASH_CUSTOM 

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.

Flags to control hashtable persistence

Enumerator
DR_HASHPERS_PAYLOAD_IS_POINTER 

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_CLONE_PAYLOAD 

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_REBASE_KEY 

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_ONLY_IN_RANGE 

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_PERSISTED 

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.

Function Documentation

void* drtable_alloc ( void *  tab,
ptr_uint_t  num_entries,
ptr_uint_t *  idx_ptr 
)

Allocates memory for an array of num_entries table entries, and returns a pointer to the allocated memory. Returns NULL if fails. If idx_ptr is not NULL, the index for the first entry is returned in idx_ptr, and all the entries from the same allocation can be referred to as index + n.

void* drtable_create ( ptr_uint_t  capacity,
size_t  entry_size,
uint  flags,
bool  synch,
void(*)(ptr_uint_t idx, void *entry, void *user_data)  free_entry_func 
)

Creates a drtable with the given parameters.

Parameters
[in]capacityThe approximate number of entries for the table. The capacity is only a suggestion for better memory usage.
[in]entry_sizeThe size of each table entry, which should be greater than 0 and smaller than USHRT_MAX (65535).
[in]flagsThe flags to specify the features of the table.
[in]synchWhether to synchronize each operation. Even when synch is false, the table's lock is initialized and can be used via drtable_lock() and drtable_unlock(), allowing the caller to extend synchronization beyond just the operation in question.
[in]free_entry_funcThe callback for freeing each table entry. Leave it NULL if no callback is needed.
void drtable_destroy ( void *  tab,
void *  user_data 
)

Destroys all storage for the table. The user_data is passed to each free_entry_func if specified.

ptr_uint_t drtable_dump_entries ( void *  tab,
file_t  log 
)

Dumps all the table entries as an array into a file in binary format. There is no header add, so the user should add one if so desired. Returns the number of entries dumped.

void* drtable_get_entry ( void *  tab,
ptr_uint_t  idx 
)

Returns a pointer to the entry at index idx. Returns NULL if the entry for idx is not allocated.

ptr_uint_t drtable_get_index ( void *  tab,
void *  ptr 
)

Returns an index to the entry pointed at by ptr. Returns DRTABLE_INVALID_INDEX if ptr does not point to any allocated entries.

void drtable_iterate ( void *  tab,
void *  iter_data,
bool(*)(ptr_uint_t id, void *, void *)  iter_func 
)

Iterates over entries in the table and call the callback function.

Parameters
[in]tabThe drtable to be operated on.
[in]iter_dataIteration data passed to iter_func.
[in]iter_funcThe callback for iterating each table entry. Returns false to stop iterating.
void drtable_lock ( void *  tab)

Acquires the table lock.

ptr_uint_t drtable_num_entries ( void *  tab)

Returns the number of entries in the table.

void drtable_unlock ( void *  tab)

Releases the table lock.

bool drvector_append ( drvector_t vec,
void *  data 
)

Adds a new entry to the end of the vector, resizing it if necessary. If drvector_set_entry() has been called, this will add to the index beyond the last index passed to drvector_set_entry().

bool drvector_delete ( drvector_t vec)

Destroys all storage for the vector. If free_payload_func was specified calls it for each payload.

void* drvector_get_entry ( drvector_t vec,
uint  idx 
)

Returns the entry at index idx. For an unsychronized table, the caller is free to directly access the array field of vec.

bool drvector_init ( drvector_t vec,
uint  initial_capacity,
bool  synch,
void(*)(void *)  free_data_func 
)

Initializes a drvector with the given parameters

Parameters
[out]vecThe vector to be initialized.
[in]initial_capacityThe initial number of entries allocated for the vector.
[in]synchWhether to synchronize each operation. Even when synch is false, the vector's lock is initialized and can be used via vector_lock() and vector_unlock(), allowing the caller to extend synchronization beyond just the operation in question, to include accessing a looked-up payload, e.g.
[in]free_data_funcA callback for freeing each data item. Leave it NULL if no callback is needed.
void drvector_lock ( drvector_t vec)

Acquires the vector lock.

bool drvector_set_entry ( drvector_t vec,
uint  idx,
void *  data 
)

Sets the entry at index idx to data. For an unsychronized table, the caller is free to directly set the array field of vec. Entries in between the last set index and idx are left uninitialized. Returns whether successful.

void drvector_unlock ( drvector_t vec)

Releases the vector lock.

bool hashtable_add ( hashtable_t *  table,
void *  key,
void *  payload 
)

Adds a new entry. Returns false if an entry for key already exists.

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 
)

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_clear ( hashtable_t *  table)

Removes all entries from the table. If free_payload_func was specified calls it for each payload.

void hashtable_configure ( hashtable_t *  table,
hashtable_config_t config 
)

Configures optional parameters of hashtable operation.

void hashtable_delete ( 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_global_config ( void *(*)(size_t)  alloc_func,
void(*)(void *, size_t)  free_func,
void(*)(const char *)  assert_fail_func 
)

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_init ( hashtable_t *  table,
uint  num_bits,
hash_type_t  hashtype,
bool  str_dup 
)

Initializes a hashtable with the given size, hash type, and whether to duplicate string keys. All operations are synchronized by default.

void hashtable_init_ex ( hashtable_t *  table,
uint  num_bits,
hash_type_t  hashtype,
bool  str_dup,
bool  synch,
void(*)(void *)  free_payload_func,
uint(*)(void *)  hash_key_func,
bool(*)(void *, void *)  cmp_key_func 
)

Initializes a hashtable with the given parameters.

Parameters
[out]tableThe hashtable to be initialized.
[in]num_bitsThe 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).
[in]hashtypeThe type of hash to perform.
[in]str_dupWhether to duplicate string keys.
[in]synchWhether to synchronize each operation. Even when 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.
[in]free_payload_funcA callback for freeing each payload. Leave it NULL if no callback is needed.
[in]hash_key_funcA 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.
[in]cmp_key_funcA 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.
void hashtable_lock ( hashtable_t *  table)

Acquires the hashtable lock.

bool hashtable_lock_self_owns ( 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.

void* hashtable_lookup ( hashtable_t *  table,
void *  key 
)

Returns the payload for the given key, or NULL if the key is not found

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.

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().

Parameters
[in]drcontextThe opaque DR context
[in]tableThe table to persist
[in]entry_sizeThe size of each table entry payload
[in]fdThe target persisted file handle
[in]perscxtThe opaque persistence context from DR's persist events
[in]flagsControls 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.

Parameters
[in]drcontextThe opaque DR context
[in]tableThe table to persist
[in]entry_sizeThe size of each table entry payload
[in]perscxtThe opaque persistence context from DR's persist events
[in]flagsControls various aspects of the persistence
bool hashtable_remove ( hashtable_t *  table,
void *  key 
)

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_range ( hashtable_t *  table,
void *  start,
void *  end 
)

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_resurrect ( void *  drcontext,
byte **  map,
hashtable_t *  table,
size_t  entry_size,
void *  perscxt,
hasthable_persist_flags_t  flags,
bool(*)(void *key, void *payload, ptr_int_t shift)  process_payload 
)

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.

Parameters
[in]drcontextThe opaque DR context
[in]mapThe mapped-in persisted file, pointing at the data written by hashtable_persist()
[in]tableThe live table to add to
[in]entry_sizeThe size of each table entry payload
[in]perscxtThe opaque persistence context from DR's persist events
[in]flagsControls various aspects of the persistence
[in]process_payloadIf non-NULL, calls process_payload instead of hashtable_add. process_payload can then adjust the paylod and if it wishes invoke hashtable_add.
void hashtable_unlock ( hashtable_t *  table)

Releases the hashtable lock.

bool stri_eq ( const char *  s1,
const char *  s2 
)

Caseless string compare