wsutil/wmem/wmem_map.c

   1 /* wmem_map.c
   2  * Wireshark Memory Manager Hash Map
   3  * Copyright 2014, Evan Huus <eapache@gmail.com>
   4  *
   5  * Wireshark - Network traffic analyzer
   6  * By Gerald Combs <gerald@wireshark.org>
   7  * Copyright 1998 Gerald Combs
   8  *
   9  * SPDX-License-Identifier: GPL-2.0-or-later
  10  */
  11 #include "config.h"
  12
  13 #include <glib.h>
  14
  15 #include "wmem_core.h"
  16 #include "wmem_list.h"
  17 #include "wmem_map.h"
  18 #include "wmem_map_int.h"
  19 #include "wmem_user_cb.h"
  20
  21 static uint32_t x; /* Used for universal integer hashing (see the HASH macro) */
  22
  23 /* Used for the wmem_strong_hash() function */
  24 static uint32_t preseed;
  25 static uint32_t postseed;
  26
  27 void
  28 wmem_init_hashing(void)
  29 {
  30     x = g_random_int();
  31     if (G_UNLIKELY(x == 0))
  32         x = 1;
  33
  34     preseed  = g_random_int();
  35     postseed = g_random_int();
  36 }
  37
  38 typedef struct _wmem_map_item_t {
  39     const void *key;
  40     void *value;
  41     struct _wmem_map_item_t *next;
  42 } wmem_map_item_t;
  43
  44 struct _wmem_map_t {
  45     unsigned count; /* number of items stored */
  46
  47     /* The base-2 logarithm of the actual size of the table. We store this
  48      * value for efficiency in hashing, since finding the actual capacity
  49      * becomes just a left-shift (see the CAPACITY macro) whereas taking
  50      * logarithms is expensive. */
  51     size_t capacity;
  52
  53     wmem_map_item_t **table;
  54
  55     GHashFunc  hash_func;
  56     GEqualFunc eql_func;
  57
  58     unsigned   metadata_scope_cb_id;
  59     unsigned   data_scope_cb_id;
  60
  61     wmem_allocator_t *metadata_allocator;
  62     wmem_allocator_t *data_allocator;
  63 };
  64
  65 /* As per the comment on the 'capacity' member of the wmem_map_t struct, this is
  66  * the base-2 logarithm, meaning the actual default capacity is 2^5 = 32 */
  67 #define WMEM_MAP_DEFAULT_CAPACITY 5
  68
  69 /* Macro for calculating the real capacity of the map by using a left-shift to
  70  * do the 2^x operation. */
  71 #define CAPACITY(MAP) (((size_t)1) << (MAP)->capacity)
  72
  73 /* Efficient universal integer hashing:
  74  * https://en.wikipedia.org/wiki/Universal_hashing#Avoiding_modular_arithmetic
  75  */
  76 #define HASH(MAP, KEY) \
  77     ((uint32_t)(((MAP)->hash_func(KEY) * x) >> (32 - (MAP)->capacity)))
  78
  79 static void
  80 wmem_map_init_table(wmem_map_t *map)
  81 {
  82     map->count     = 0;
  83     map->capacity  = WMEM_MAP_DEFAULT_CAPACITY;
  84     map->table     = wmem_alloc0_array(map->data_allocator, wmem_map_item_t*, CAPACITY(map));
  85 }
  86
  87 wmem_map_t *
  88 wmem_map_new(wmem_allocator_t *allocator,
  89         GHashFunc hash_func, GEqualFunc eql_func)
  90 {
  91     wmem_map_t *map;
  92
  93     map = wmem_new(allocator, wmem_map_t);
  94
  95     map->hash_func = hash_func;
  96     map->eql_func  = eql_func;
  97     map->metadata_allocator    = allocator;
  98     map->data_allocator = allocator;
  99     map->count = 0;
 100     map->table = NULL;
 101
 102     return map;
 103 }
 104
 105 static bool
 106 wmem_map_reset_cb(wmem_allocator_t *allocator _U_, wmem_cb_event_t event,
 107         void *user_data)
 108 {
 109     wmem_map_t *map = (wmem_map_t*)user_data;
 110
 111     map->count = 0;
 112     map->table = NULL;
 113
 114     if (event == WMEM_CB_DESTROY_EVENT) {
 115         wmem_unregister_callback(map->metadata_allocator, map->metadata_scope_cb_id);
 116         wmem_free(map->metadata_allocator, map);
 117     }
 118
 119     return true;
 120 }
 121
 122 static bool
 123 wmem_map_destroy_cb(wmem_allocator_t *allocator _U_, wmem_cb_event_t event _U_,
 124         void *user_data)
 125 {
 126     wmem_map_t *map = (wmem_map_t*)user_data;
 127
 128     wmem_unregister_callback(map->data_allocator, map->data_scope_cb_id);
 129
 130     return false;
 131 }
 132
 133 wmem_map_t *
 134 wmem_map_new_autoreset(wmem_allocator_t *metadata_scope, wmem_allocator_t *data_scope,
 135         GHashFunc hash_func, GEqualFunc eql_func)
 136 {
 137     wmem_map_t *map;
 138
 139     map = wmem_new(metadata_scope, wmem_map_t);
 140
 141     map->hash_func = hash_func;
 142     map->eql_func  = eql_func;
 143     map->metadata_allocator = metadata_scope;
 144     map->data_allocator = data_scope;
 145     map->count = 0;
 146     map->table = NULL;
 147
 148     map->metadata_scope_cb_id = wmem_register_callback(metadata_scope, wmem_map_destroy_cb, map);
 149     map->data_scope_cb_id  = wmem_register_callback(data_scope, wmem_map_reset_cb, map);
 150
 151     return map;
 152 }
 153
 154 static inline void
 155 wmem_map_grow(wmem_map_t *map)
 156 {
 157     wmem_map_item_t **old_table, *cur, *nxt;
 158     size_t            old_cap, i;
 159     unsigned          slot;
 160
 161     /* store the old table and capacity */
 162     old_table = map->table;
 163     old_cap   = CAPACITY(map);
 164
 165     /* double the size (capacity is base-2 logarithm, so this just means
 166      * increment it) and allocate new table */
 167     map->capacity++;
 168     map->table = wmem_alloc0_array(map->data_allocator, wmem_map_item_t*, CAPACITY(map));
 169
 170     /* copy all the elements over from the old table */
 171     for (i=0; i<old_cap; i++) {
 172         cur = old_table[i];
 173         while (cur) {
 174             nxt              = cur->next;
 175             slot             = HASH(map, cur->key);
 176             cur->next        = map->table[slot];
 177             map->table[slot] = cur;
 178             cur              = nxt;
 179         }
 180     }
 181
 182     /* free the old table */
 183     wmem_free(map->data_allocator, old_table);
 184 }
 185
 186 void *
 187 wmem_map_insert(wmem_map_t *map, const void *key, void *value)
 188 {
 189     wmem_map_item_t **item;
 190     void *old_val;
 191
 192     /* Make sure we have a table */
 193     if (map->table == NULL) {
 194         wmem_map_init_table(map);
 195     }
 196
 197     /* get a pointer to the slot */
 198     item = &(map->table[HASH(map, key)]);
 199
 200     /* check existing items in that slot */
 201     while (*item) {
 202         if (map->eql_func(key, (*item)->key)) {
 203             /* replace and return old value for this key */
 204             old_val = (*item)->value;
 205             (*item)->value = value;
 206             return old_val;
 207         }
 208         item = &((*item)->next);
 209     }
 210
 211     /* insert new item */
 212     (*item) = wmem_new(map->data_allocator, wmem_map_item_t);
 213
 214     (*item)->key   = key;
 215     (*item)->value = value;
 216     (*item)->next  = NULL;
 217
 218     map->count++;
 219
 220     /* increase size if we are over-full */
 221     if (map->count >= CAPACITY(map)) {
 222         wmem_map_grow(map);
 223     }
 224
 225     /* no previous entry, return NULL */
 226     return NULL;
 227 }
 228
 229 bool
 230 wmem_map_contains(wmem_map_t *map, const void *key)
 231 {
 232     wmem_map_item_t *item;
 233
 234     /* Make sure we have map and a table */
 235     if (map == NULL || map->table == NULL) {
 236         return false;
 237     }
 238
 239     /* find correct slot */
 240     item = map->table[HASH(map, key)];
 241
 242     /* scan list of items in this slot for the correct value */
 243     while (item) {
 244         if (map->eql_func(key, item->key)) {
 245             return true;
 246         }
 247         item = item->next;
 248     }
 249
 250     return false;
 251 }
 252
 253 void *
 254 wmem_map_lookup(wmem_map_t *map, const void *key)
 255 {
 256     wmem_map_item_t *item;
 257
 258     /* Make sure we have map and a table */
 259     if (map == NULL || map->table == NULL) {
 260         return NULL;
 261     }
 262
 263     /* find correct slot */
 264     item = map->table[HASH(map, key)];
 265
 266     /* scan list of items in this slot for the correct value */
 267     while (item) {
 268         if (map->eql_func(key, item->key)) {
 269             return item->value;
 270         }
 271         item = item->next;
 272     }
 273
 274     return NULL;
 275 }
 276
 277 bool
 278 wmem_map_lookup_extended(wmem_map_t *map, const void *key, const void **orig_key, void **value)
 279 {
 280     wmem_map_item_t *item;
 281
 282     /* Make sure we have map and a table */
 283     if (map == NULL || map->table == NULL) {
 284         return false;
 285     }
 286
 287     /* find correct slot */
 288     item = map->table[HASH(map, key)];
 289
 290     /* scan list of items in this slot for the correct value */
 291     while (item) {
 292         if (map->eql_func(key, item->key)) {
 293             if (orig_key) {
 294                 *orig_key = item->key;
 295             }
 296             if (value) {
 297                 *value = item->value;
 298             }
 299             return true;
 300         }
 301         item = item->next;
 302     }
 303
 304     return false;
 305 }
 306
 307 void *
 308 wmem_map_remove(wmem_map_t *map, const void *key)
 309 {
 310     wmem_map_item_t **item, *tmp;
 311     void *value;
 312
 313     /* Make sure we have map and a table */
 314     if (map == NULL || map->table == NULL) {
 315         return NULL;
 316     }
 317
 318     /* get a pointer to the slot */
 319     item = &(map->table[HASH(map, key)]);
 320
 321     /* check the items in that slot */
 322     while (*item) {
 323         if (map->eql_func(key, (*item)->key)) {
 324             /* found it */
 325             tmp     = (*item);
 326             value   = tmp->value;
 327             (*item) = tmp->next;
 328             wmem_free(map->data_allocator, tmp);
 329             map->count--;
 330             return value;
 331         }
 332         item = &((*item)->next);
 333     }
 334
 335     /* didn't find it */
 336     return NULL;
 337 }
 338
 339 bool
 340 wmem_map_steal(wmem_map_t *map, const void *key)
 341 {
 342     wmem_map_item_t **item, *tmp;
 343
 344     /* Make sure we have map and a table */
 345     if (map == NULL || map->table == NULL) {
 346         return false;
 347     }
 348
 349     /* get a pointer to the slot */
 350     item = &(map->table[HASH(map, key)]);
 351
 352     /* check the items in that slot */
 353     while (*item) {
 354         if (map->eql_func(key, (*item)->key)) {
 355             /* found it */
 356             tmp     = (*item);
 357             (*item) = tmp->next;
 358             map->count--;
 359             return true;
 360         }
 361         item = &((*item)->next);
 362     }
 363
 364     /* didn't find it */
 365     return false;
 366 }
 367
 368 wmem_list_t*
 369 wmem_map_get_keys(wmem_allocator_t *list_allocator, wmem_map_t *map)
 370 {
 371     size_t capacity, i;
 372     wmem_map_item_t *cur;
 373     wmem_list_t* list = wmem_list_new(list_allocator);
 374
 375     if (map->table != NULL) {
 376         capacity = CAPACITY(map);
 377
 378         /* copy all the elements into the list over from table */
 379         for (i=0; i<capacity; i++) {
 380             cur = map->table[i];
 381             while (cur) {
 382                 wmem_list_prepend(list, (void*)cur->key);
 383                 cur = cur->next;
 384             }
 385         }
 386     }
 387
 388     return list;
 389 }
 390
 391 void
 392 wmem_map_foreach(wmem_map_t *map, GHFunc foreach_func, void * user_data)
 393 {
 394     wmem_map_item_t *cur;
 395     unsigned i;
 396
 397     /* Make sure we have a table */
 398     if (map == NULL || map->table == NULL) {
 399         return;
 400     }
 401
 402     for (i = 0; i < CAPACITY(map); i++) {
 403         cur = map->table[i];
 404         while (cur) {
 405             foreach_func((void *)cur->key, (void *)cur->value, user_data);
 406             cur = cur->next;
 407         }
 408     }
 409 }
 410
 411 void*
 412 wmem_map_find(wmem_map_t *map, GHRFunc foreach_func, void * user_data)
 413 {
 414     wmem_map_item_t **item;
 415     unsigned i;
 416
 417     /* Make sure we have a table */
 418     if (map == NULL || map->table == NULL) {
 419         return 0;
 420     }
 421
 422     for (i = 0; i < CAPACITY(map); i++) {
 423         item = &(map->table[i]);
 424         while (*item) {
 425             if (foreach_func((void *)(*item)->key, (void *)(*item)->value, user_data)) {
 426                 return (*item)->value;
 427             } else {
 428                 item = &((*item)->next);
 429             }
 430         }
 431     }
 432     return NULL;
 433 }
 434
 435 unsigned
 436 wmem_map_foreach_remove(wmem_map_t *map, GHRFunc foreach_func, void * user_data)
 437 {
 438     wmem_map_item_t **item, *tmp;
 439     unsigned i, deleted = 0;
 440
 441     /* Make sure we have a table */
 442     if (map == NULL || map->table == NULL) {
 443         return 0;
 444     }
 445
 446     for (i = 0; i < CAPACITY(map); i++) {
 447         item = &(map->table[i]);
 448         while (*item) {
 449             if (foreach_func((void *)(*item)->key, (void *)(*item)->value, user_data)) {
 450                 tmp   = *item;
 451                 *item = tmp->next;
 452                 wmem_free(map->data_allocator, tmp);
 453                 map->count--;
 454                 deleted++;
 455             } else {
 456                 item = &((*item)->next);
 457             }
 458         }
 459     }
 460     return deleted;
 461 }
 462
 463 unsigned
 464 wmem_map_size(wmem_map_t *map)
 465 {
 466     return map->count;
 467 }
 468
 469 /* Borrowed from Perl 5.18. This is based on Bob Jenkin's one-at-a-time
 470  * algorithm with some additional randomness seeded in. It is believed to be
 471  * generally secure against collision attacks. See
 472  * http://blog.booking.com/hardening-perls-hash-function.html
 473  */
 474 uint32_t
 475 wmem_strong_hash(const uint8_t *buf, const size_t len)
 476 {
 477     const uint8_t * const end = (const uint8_t *)buf + len;
 478     uint32_t hash = preseed + (uint32_t)len;
 479
 480     while (buf < end) {
 481         hash += (hash << 10);
 482         hash ^= (hash >> 6);
 483         hash += *buf++;
 484     }
 485
 486     hash += (hash << 10);
 487     hash ^= (hash >> 6);
 488     hash += ((uint8_t*)&postseed)[0];
 489
 490     hash += (hash << 10);
 491     hash ^= (hash >> 6);
 492     hash += ((uint8_t*)&postseed)[1];
 493
 494     hash += (hash << 10);
 495     hash ^= (hash >> 6);
 496     hash += ((uint8_t*)&postseed)[2];
 497
 498     hash += (hash << 10);
 499     hash ^= (hash >> 6);
 500     hash += ((uint8_t*)&postseed)[3];
 501
 502     hash += (hash << 10);
 503     hash ^= (hash >> 6);
 504
 505     hash += (hash << 3);
 506     hash ^= (hash >> 11);
 507     return (hash + (hash << 15));
 508 }
 509
 510 unsigned
 511 wmem_str_hash(const void *key)
 512 {
 513     return wmem_strong_hash((const uint8_t *)key, strlen((const char *)key));
 514 }
 515
 516 unsigned
 517 wmem_int64_hash(const void *key)
 518 {
 519     return wmem_strong_hash((const uint8_t *)key, sizeof(uint64_t));
 520 }
 521
 522 unsigned
 523 wmem_double_hash(const void *key)
 524 {
 525     return wmem_strong_hash((const uint8_t *)key, sizeof(double));
 526 }
 527
 528 /*
 529  * Editor modelines  -  https://www.wireshark.org/tools/modelines.html
 530  *
 531  * Local variables:
 532  * c-basic-offset: 4
 533  * tab-width: 8
 534  * indent-tabs-mode: nil
 535  * End:
 536  *
 537  * vi: set shiftwidth=4 tabstop=8 expandtab:
 538  * :indentSize=4:tabSize=8:noTabs=true:
 539  */