1/*
2 * vmapx.c
3 *
4 * Copyright (C) 2012-2016 Aerospike, Inc.
5 *
6 * Portions may be licensed to Aerospike, Inc. under one or more contributor
7 * license agreements.
8 *
9 * This program is free software: you can redistribute it and/or modify it under
10 * the terms of the GNU Affero General Public License as published by the Free
11 * Software Foundation, either version 3 of the License, or (at your option) any
12 * later version.
13 *
14 * This program is distributed in the hope that it will be useful, but WITHOUT
15 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
16 * FOR A PARTICULAR PURPOSE. See the GNU Affero General Public License for more
17 * details.
18 *
19 * You should have received a copy of the GNU Affero General Public License
20 * along with this program. If not, see http://www.gnu.org/licenses/
21 */
22
23//==========================================================
24// Includes.
25//
26
27#include "vmapx.h"
28
29#include <stdbool.h>
30#include <stddef.h>
31#include <stdint.h>
32#include <string.h>
33
34#include "cf_mutex.h"
35#include "fault.h"
36
37#include "citrusleaf/alloc.h"
38#include "citrusleaf/cf_hash_math.h"
39
40
41//==========================================================
42// Forward declarations.
43//
44
45bool vhash_get(const vhash* h, const char* key, size_t key_len, uint32_t* p_value);
46
47
48//==========================================================
49// Public API.
50//
51
52// Return memory size needed - includes cf_vmapx struct plus values vector.
53size_t
54cf_vmapx_sizeof(uint32_t value_size, uint32_t max_count)
55{
56 return sizeof(cf_vmapx) + ((size_t)value_size * (size_t)max_count);
57}
58
59// Initialize an already allocated cf_vmapx object.
60void
61cf_vmapx_init(cf_vmapx* vmap, uint32_t value_size, uint32_t max_count,
62 uint32_t hash_size, uint32_t max_name_size)
63{
64 cf_assert(vmap, CF_VMAPX, "null vmap pointer");
65 cf_assert((value_size & 3) == 0, CF_VMAPX, "bad value_size");
66 cf_assert(max_count != 0, CF_VMAPX, "bad max_count");
67 cf_assert(hash_size != 0, CF_VMAPX, "bad hash_size");
68 cf_assert(max_name_size != 0 && max_name_size <= value_size, CF_VMAPX,
69 "bad max_name_size");
70
71 vmap->value_size = value_size;
72 vmap->max_count = max_count;
73 vmap->count = 0;
74
75 vmap->key_size = max_name_size;
76 vmap->hash = vhash_create(max_name_size, hash_size);
77
78 cf_mutex_init(&vmap->write_lock);
79}
80
81// Don't call after failed cf_vmapx_create() or cf_vmapx_resume() call - those
82// functions clean up on failure.
83void
84cf_vmapx_release(cf_vmapx* vmap)
85{
86 // Helps in handling bins vmap, which doesn't exist in single-bin mode.
87 if (! vmap) {
88 return;
89 }
90
91 cf_mutex_destroy(&vmap->write_lock);
92
93 vhash_destroy(vmap->hash);
94}
95
96// Return count.
97uint32_t
98cf_vmapx_count(const cf_vmapx* vmap)
99{
100 return vmap->count;
101}
102
103// Get value by index.
104cf_vmapx_err
105cf_vmapx_get_by_index(const cf_vmapx* vmap, uint32_t index, void** pp_value)
106{
107 // This check is commented out for now to avoid the volatile access.
108 // TODO - ultimately, caller code can be simplified. (Especially if this
109 // just returned the value pointer.) And if necessary, we could make a
110 // "safe" version of this that does the check.
111
112// if (index >= vmap->count) {
113// return CF_VMAPX_ERR_BAD_PARAM;
114// }
115
116 *pp_value = vmapx_value_ptr(vmap, index);
117
118 return CF_VMAPX_OK;
119}
120
121// Get value by null-terminated name.
122cf_vmapx_err
123cf_vmapx_get_by_name(const cf_vmapx* vmap, const char* name, void** pp_value)
124{
125 size_t name_len = strlen(name);
126
127 if (name_len >= vmap->key_size) {
128 return CF_VMAPX_ERR_NAME_NOT_FOUND;
129 }
130
131 uint32_t index;
132
133 if (! vhash_get(vmap->hash, name, name_len, &index)) {
134 return CF_VMAPX_ERR_NAME_NOT_FOUND;
135 }
136
137 *pp_value = vmapx_value_ptr(vmap, index);
138
139 return CF_VMAPX_OK;
140}
141
142// Same as above, but non-null-terminated name.
143cf_vmapx_err
144cf_vmapx_get_by_name_w_len(const cf_vmapx* vmap, const char* name,
145 size_t name_len, void** pp_value)
146{
147 if (name_len >= vmap->key_size) {
148 return CF_VMAPX_ERR_NAME_NOT_FOUND;
149 }
150
151 uint32_t index;
152
153 if (! vhash_get(vmap->hash, name, name_len, &index)) {
154 return CF_VMAPX_ERR_NAME_NOT_FOUND;
155 }
156
157 *pp_value = vmapx_value_ptr(vmap, index);
158
159 return CF_VMAPX_OK;
160}
161
162// Get index by null-terminated name. May pass null p_index to check existence.
163cf_vmapx_err
164cf_vmapx_get_index(const cf_vmapx* vmap, const char* name, uint32_t* p_index)
165{
166 size_t name_len = strlen(name);
167
168 if (name_len >= vmap->key_size) {
169 return CF_VMAPX_ERR_NAME_NOT_FOUND;
170 }
171
172 return vhash_get(vmap->hash, name, name_len, p_index) ?
173 CF_VMAPX_OK : CF_VMAPX_ERR_NAME_NOT_FOUND;
174}
175
176// Same as above, but non-null-terminated name.
177cf_vmapx_err
178cf_vmapx_get_index_w_len(const cf_vmapx* vmap, const char* name,
179 size_t name_len, uint32_t* p_index)
180{
181 if (name_len >= vmap->key_size) {
182 return CF_VMAPX_ERR_NAME_NOT_FOUND;
183 }
184
185 return vhash_get(vmap->hash, name, name_len, p_index) ?
186 CF_VMAPX_OK : CF_VMAPX_ERR_NAME_NOT_FOUND;
187}
188
189// The value must begin with a string which is its name. (The hash map is not
190// stored in persistent memory, so names must be in the vector to enable us to
191// rebuild the hash map on warm or cool restart.)
192//
193// If name is not found, add new name, clear rest of value in vector, and return
194// newly assigned index (and CF_VMAPX_OK). If name is found, return index for
195// existing value (with CF_VMAPX_ERR_NAME_EXISTS). May pass null p_index.
196cf_vmapx_err
197cf_vmapx_put_unique(cf_vmapx* vmap, const char* name, uint32_t* p_index)
198{
199 return cf_vmapx_put_unique_w_len(vmap, name, strlen(name), p_index);
200}
201
202// Same as above, but with known name length.
203cf_vmapx_err
204cf_vmapx_put_unique_w_len(cf_vmapx* vmap, const char* name, size_t name_len,
205 uint32_t* p_index)
206{
207 // Make sure name fits in key's allocated size.
208 if (name_len >= vmap->key_size) {
209 return CF_VMAPX_ERR_BAD_PARAM;
210 }
211
212 cf_mutex_lock(&vmap->write_lock);
213
214 // If name is found, return existing name's index, ignore p_value.
215 if (vhash_get(vmap->hash, name, name_len, p_index)) {
216 cf_mutex_unlock(&vmap->write_lock);
217 return CF_VMAPX_ERR_NAME_EXISTS;
218 }
219
220 // Make sure name has no illegal premature null-terminator.
221 for (uint32_t i = 0; i < name_len; i++) {
222 if (name[i] == 0) {
223 cf_mutex_unlock(&vmap->write_lock);
224 return CF_VMAPX_ERR_BAD_PARAM;
225 }
226 }
227
228 uint32_t count = vmap->count;
229
230 // If vmap is full, can't add more.
231 if (count >= vmap->max_count) {
232 cf_mutex_unlock(&vmap->write_lock);
233 return CF_VMAPX_ERR_FULL;
234 }
235
236 // Add name to vector (and clear rest of value).
237 char* value_ptr = (char*)vmapx_value_ptr(vmap, count);
238
239 memset((void*)value_ptr, 0, vmap->value_size);
240 memcpy((void*)value_ptr, name, name_len);
241
242 // Increment count here so indexes returned by other public API calls (just
243 // after adding to hash below) are guaranteed to be valid.
244 vmap->count++;
245
246 // Add to hash.
247 vhash_put(vmap->hash, value_ptr, name_len, count);
248
249 cf_mutex_unlock(&vmap->write_lock);
250
251 if (p_index) {
252 *p_index = count;
253 }
254
255 return CF_VMAPX_OK;
256}
257
258
259//==========================================================
260// Private API - for enterprise separation only.
261//
262
263// Return value pointer at trusted index.
264void*
265vmapx_value_ptr(const cf_vmapx* vmap, uint32_t index)
266{
267 return (void*)(vmap->values + (vmap->value_size * index));
268}
269
270
271//==========================================================
272// vhash "scoped class".
273//
274
275// Custom hashmap for cf_vmapx usage.
276// - Elements are added but never removed.
277// - It's thread safe yet lockless. (Relies on cf_vmapx's write_lock.)
278// - Element keys are null-terminated strings.
279// - Element values are uint32_t's.
280
281struct vhash_s {
282 uint32_t key_size;
283 uint32_t ele_size;
284 uint32_t n_rows;
285 uint8_t* table;
286 bool row_usage[];
287};
288
289typedef struct vhash_ele_s {
290 struct vhash_ele_s* next;
291 uint8_t data[]; // key_size bytes of key, 4 bytes of value
292} vhash_ele;
293
294#define VHASH_ELE_KEY_PTR(_e) ((char*)_e->data)
295#define VHASH_ELE_VALUE_PTR(_h, _e) ((uint32_t*)(_e->data + _h->key_size))
296
297// Copy null-terminated key into hash, then pad with non-null characters.
298// Padding ensures quicker compare in vhash_get() when key in hash is shorter,
299// and prevents accidental match if key param has illegal null character(s).
300static inline void
301vhash_set_ele_key(char* ele_key, size_t key_size, const char* zkey,
302 size_t zkey_size)
303{
304 memcpy((void*)ele_key, (const void*)zkey, zkey_size);
305 memset((void*)(ele_key + zkey_size), 'x', key_size - zkey_size);
306}
307
308// Create vhash with specified key size (max) and number or rows.
309vhash*
310vhash_create(uint32_t key_size, uint32_t n_rows)
311{
312 size_t row_usage_size = n_rows * sizeof(bool);
313 vhash* h = (vhash*)cf_malloc(sizeof(vhash) + row_usage_size);
314
315 h->key_size = key_size;
316 h->ele_size = sizeof(vhash_ele) + key_size + sizeof(uint32_t);
317 h->n_rows = n_rows;
318
319 size_t table_size = n_rows * h->ele_size;
320
321 h->table = (uint8_t*)cf_malloc(table_size);
322
323 memset((void*)h->row_usage, 0, row_usage_size);
324 memset((void*)h->table, 0, table_size);
325
326 return h;
327}
328
329// Destroy vhash. (Assumes it was fully created.)
330void
331vhash_destroy(vhash* h)
332{
333 vhash_ele* e_table = (vhash_ele*)h->table;
334
335 for (uint32_t i = 0; i < h->n_rows; i++) {
336 if (e_table->next) {
337 vhash_ele* e = e_table->next;
338
339 while (e) {
340 vhash_ele* t = e->next;
341
342 cf_free(e);
343 e = t;
344 }
345 }
346
347 e_table = (vhash_ele*)((uint8_t*)e_table + h->ele_size);
348 }
349
350 cf_free(h->table);
351 cf_free(h);
352}
353
354// Add element. Key must be null-terminated, although its length is known.
355void
356vhash_put(vhash* h, const char* zkey, size_t key_len, uint32_t value)
357{
358 uint64_t hashed_key = cf_hash_fnv32((const uint8_t*)zkey, key_len);
359 uint32_t row_i = (uint32_t)(hashed_key % h->n_rows);
360
361 vhash_ele* e = (vhash_ele*)(h->table + (h->ele_size * row_i));
362
363 if (! h->row_usage[row_i]) {
364 vhash_set_ele_key(VHASH_ELE_KEY_PTR(e), h->key_size, zkey, key_len + 1);
365 *VHASH_ELE_VALUE_PTR(h, e) = value;
366 // TODO - need barrier?
367 h->row_usage[row_i] = true;
368
369 return;
370 }
371
372 vhash_ele* e_head = e;
373
374 // This function is always called under write lock, after get, so we'll
375 // never encounter the key - don't bother checking it.
376 while (e) {
377 e = e->next;
378 }
379
380 e = (vhash_ele*)cf_malloc(h->ele_size);
381
382 vhash_set_ele_key(VHASH_ELE_KEY_PTR(e), h->key_size, zkey, key_len + 1);
383 *VHASH_ELE_VALUE_PTR(h, e) = value;
384
385 e->next = e_head->next;
386 // TODO - need barrier?
387 e_head->next = e;
388}
389
390// Get element value. Key may or may not be null-terminated.
391bool
392vhash_get(const vhash* h, const char* key, size_t key_len, uint32_t* p_value)
393{
394 uint64_t hashed_key = cf_hash_fnv32((const uint8_t*)key, key_len);
395 uint32_t row_i = (uint32_t)(hashed_key % h->n_rows);
396
397 if (! h->row_usage[row_i]) {
398 return false;
399 }
400
401 // TODO - need barrier?
402 vhash_ele* e = (vhash_ele*)(h->table + (h->ele_size * row_i));
403
404 while (e) {
405 if (VHASH_ELE_KEY_PTR(e)[key_len] == 0 &&
406 memcmp(VHASH_ELE_KEY_PTR(e), key, key_len) == 0) {
407 if (p_value) {
408 *p_value = *VHASH_ELE_VALUE_PTR(h, e);
409 }
410
411 return true;
412 }
413
414 e = e->next;
415 }
416
417 return false;
418}
419