3
* This file contains various definitions and interface for management
4
* of in-memory, through mmaped file, growable hash table, that stores
7
* @remark Copyright 2002 OProfile authors
8
* @remark Read the file COPYING
10
* @author Philippe Elie
21
/** the type of key. 64-bit because CG needs 32-bit pair {from,to} */
22
typedef uint64_t odb_key_t;
23
/** the type of an information in the database */
24
typedef unsigned int odb_value_t;
25
/** the type of index (node number), list are implemented through index */
26
typedef unsigned int odb_index_t;
27
/** the type store node number */
28
typedef odb_index_t odb_node_nr_t;
29
/** store the hash mask, hash table size are always power of two */
30
typedef odb_index_t odb_hash_mask_t;
32
/* there is (bucket factor * nr node) entry in hash table, this can seem
33
* excessive but hash coding eip don't give a good distributions and our
34
* goal is to get a O(1) amortized insert time. bucket factor must be a
35
* power of two. FIXME: see big comment in odb_hash_add_node, you must
36
* re-enable zeroing hash table if BUCKET_FACTOR > 2 (roughly exact, you
37
* want to read the comment in odb_hash_add_node() if you tune this define)
39
#define BUCKET_FACTOR 1
43
odb_key_t key; /**< eip */
44
odb_value_t value; /**< samples count */
45
odb_index_t next; /**< next entry for this bucket */
48
/** the minimal information which must be stored in the file to reload
49
* properly the data base, following this header is the node array then
50
* the hash table (when growing we avoid to copy node array)
53
odb_node_nr_t size; /**< in node nr (power of two) */
54
odb_node_nr_t current_size; /**< nr used node + 1, node 0 unused */
55
int padding[6]; /**< for padding and future use */
58
/** a "database". this is an in memory only description.
60
* We allow to manage a database inside a mapped file with an "header" of
61
* unknown size so odb_open get a parameter to specify the size of this header.
64
* struct header { int etc; ... };
65
* odb_open(&hash, filename, ODB_RW, sizeof(header));
66
* so on this library have no dependency on the header type.
68
* the internal memory layout from base_memory is:
69
* the unknown header (sizeof_header)
71
* the node array: (descr->size * sizeof(odb_node_t) entries
72
* the hash table: array of odb_index_t indexing the node array
73
* (descr->size * BUCKET_FACTOR) entries
75
typedef struct odb_data {
76
odb_node_t * node_base; /**< base memory area of the page */
77
odb_index_t * hash_base; /**< base memory of hash table */
78
odb_descr_t * descr; /**< the current state of database */
79
odb_hash_mask_t hash_mask; /**< == descr->size - 1 */
80
unsigned int sizeof_header; /**< from base_memory to odb header */
81
unsigned int offset_node; /**< from base_memory to node array */
82
void * base_memory; /**< base memory of the maped memory */
83
int fd; /**< mmaped memory file descriptor */
84
char * filename; /**< full path name of sample file */
85
int ref_count; /**< reference count */
86
struct list_head list; /**< hash bucket list */
99
/** how to open the DB file */
101
ODB_RDONLY = 0, /**< open for read only */
102
ODB_RDWR = 1 /**< open for read and/or write */
106
* odb_init - initialize a DB file
107
* @param odb the DB file to init
109
void odb_init(odb_t * odb);
112
* odb_open - open a DB file
113
* @param odb the data base object to setup
114
* @param filename the filename where go the maped memory
115
* @param rw \enum ODB_RW if opening for writing, else \enum ODB_RDONLY
116
* @param sizeof_header size of the file header if any
118
* The sizeof_header parameter allows the data file to have a header
119
* at the start of the file which is skipped.
120
* odb_open() always preallocate a few number of pages.
121
* returns 0 on success, errno on failure
123
int odb_open(odb_t * odb, char const * filename,
124
enum odb_rw rw, size_t sizeof_header);
126
/** Close the given ODB file */
127
void odb_close(odb_t * odb);
129
/** return the number of times this sample file is open */
130
int odb_open_count(odb_t const * odb);
132
/** return the start of the mapped data */
133
void * odb_get_data(odb_t * odb);
135
/** issue a msync on the used size of the mmaped file */
136
void odb_sync(odb_t const * odb);
139
* grow the hashtable in such way current_size is the index of the first free
140
* node. Take care all node pointer can be invalidated by this call.
142
* Node allocation is done in a two step way 1st) ensure a free node exist
143
* eventually, caller can setup it, 2nd) commit the node allocation with
144
* odb_commit_reservation().
145
* This is done in this way to ensure node setup is visible from another
146
* process like pp tools in an atomic way.
148
* returns 0 on success, non zero on failure in this case this function do
149
* nothing and errno is set by the first libc call failure allowing to retry
150
* after cleanup some program resource.
152
int odb_grow_hashtable(odb_data_t * data);
154
* commit a previously successfull node reservation. This can't fail.
156
static __inline void odb_commit_reservation(odb_data_t * data)
158
++data->descr->current_size;
161
/** "immpossible" node number to indicate an error from odb_hash_add_node() */
162
#define ODB_NODE_NR_INVALID ((odb_node_nr_t)-1)
165
/** check that the hash is well built */
166
int odb_check_hash(odb_t const * odb);
169
typedef struct odb_hash_stat_t odb_hash_stat_t;
170
odb_hash_stat_t * odb_hash_stat(odb_t const * odb);
171
void odb_hash_display_stat(odb_hash_stat_t const * stats);
172
void odb_hash_free_stat(odb_hash_stat_t * stats);
175
/** update info at key by incrementing its associated value by one,
176
* if the key does not exist a new node is created and the value associated
179
* returns EXIT_SUCCESS on success, EXIT_FAILURE on failure
181
int odb_update_node(odb_t * odb, odb_key_t key);
184
* odb_update_node_with_offset
185
* @param odb the data base object to setup
186
* @param key the hash key
187
* @param offset the offset to be added
189
* update info at key by adding the specified offset to its associated value,
190
* if the key does not exist a new node is created and the value associated
193
* returns EXIT_SUCCESS on success, EXIT_FAILURE on failure
195
int odb_update_node_with_offset(odb_t * odb,
197
unsigned long int offset);
199
/** Add a new node w/o regarding if a node with the same key already exists
201
* returns EXIT_SUCCESS on success, EXIT_FAILURE on failure
203
int odb_add_node(odb_t * odb, odb_key_t key, odb_value_t value);
207
* return a base pointer to the node array and number of node in this array
208
* caller then will iterate through:
210
* odb_node_nr_t node_nr, pos;
211
* odb_node_t * node = odb_get_iterator(odb, &node_nr);
212
* for ( pos = 0 ; pos < node_nr ; ++pos)
215
* note than caller does not need to filter nil key as it's a valid key,
216
* The returned range is all valid (i.e. should never contain zero value).
218
odb_node_t * odb_get_iterator(odb_t const * odb, odb_node_nr_t * nr);
220
static __inline unsigned int
221
odb_do_hash(odb_data_t const * data, odb_key_t value)
223
/* FIXME: better hash for eip value, needs to instrument code
224
* and do a lot of tests ... */
225
/* trying to combine high order bits his a no-op: inside a binary image
226
* high order bits don't vary a lot, hash table start with 7 bits mask
227
* so this hash coding use bits 0-7, 8-15. Hash table is stored in
228
* files avoiding to rebuilding them at profiling re-start so
229
* on changing do_hash() change the file format!
231
uint32_t temp = (value >> 32) ^ value;
232
return ((temp << 0) ^ (temp >> 8)) & data->hash_mask;
added
removed
libdb/odb.h
