debuggers.hg

view tools/memshr/bidir-hash.c @ 21067:b4a1832a916f

Update Xen version to 4.0.0-rc6
author Keir Fraser <keir.fraser@citrix.com>
date Tue Mar 09 18:18:05 2010 +0000 (2010-03-09)
parents 58dbf27875c5
children
line source
1 /******************************************************************************
2 *
3 * Copyright (c) 2009 Citrix Systems, Inc. (Grzegorz Milos)
4 *
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 2 of the License, or
8 * (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18 */
19 #include <assert.h>
20 #include <errno.h>
21 #include <math.h>
22 #include <pthread.h>
23 #include <stddef.h>
24 #include <stdint.h>
25 #include <stdlib.h>
26 #include <string.h>
27 #include <time.h>
28 #include <unistd.h>
30 #include "bidir-hash.h"
32 static const uint32_t hash_sizes[] = {53, 97, 193, 389, 769, 1543, 3079, 6151,
33 12289, 24593, 49157, 98317, 196613, 393241, 786433, 1572869, 3145739,
34 6291469, 12582917, 25165843, 50331653, 100663319, 201326611, 402653189,
35 805306457, 1610612741};
36 static const uint16_t hash_sizes_len =
37 sizeof(hash_sizes)/sizeof(hash_sizes[0]);
38 static const float hash_max_load_fact = 0.65;
39 static const float hash_min_load_fact = 0.10;
41 /* How many buckets will be covered by a single rw lock */
42 #define BUCKETS_PER_LOCK 64
43 #define nr_locks(_nr_buckets) (1 + (_nr_buckets) / BUCKETS_PER_LOCK)
46 #define HASH_LOCK \
47 pthread_rwlock_t hash_lock
49 #define BUCKET_LOCK \
50 pthread_rwlock_t bucket_lock
52 struct hash_entry
53 {
54 __k_t key;
55 __v_t value;
56 /* This structure will belong to two buckets, one in each hash table */
57 struct hash_entry *key_next;
58 struct hash_entry *value_next;
59 };
61 struct bucket
62 {
63 struct hash_entry *hash_entry;
64 };
66 struct bucket_lock
67 {
68 BUCKET_LOCK;
69 };
71 struct __hash
72 {
73 int lock_alive;
74 HASH_LOCK; /* protects:
75 * *_tab, tab_size, size_idx, *_load
76 * (all writes with wrlock)
77 */
78 uint32_t nr_ent; /* # entries held in hashtables */
79 struct bucket *key_tab; /* forward mapping hashtable */
80 struct bucket *value_tab; /* backward mapping hashtable */
81 struct bucket_lock *key_lock_tab; /* key table bucket locks */
82 struct bucket_lock *value_lock_tab; /* value table bucket locks */
83 uint32_t tab_size; /* # buckets is hashtables */
84 uint16_t size_idx; /* table size index */
85 uint32_t max_load; /* # entries before rehash */
86 uint32_t min_load; /* # entries before rehash */
87 };
89 struct __hash *__hash_init (struct __hash *h, uint32_t min_size);
90 int __key_lookup (struct __hash *h, __k_t k, __v_t *vp);
91 int __value_lookup(struct __hash *h, __v_t v, __k_t *kp);
92 int __insert (struct __hash *h, __k_t k, __v_t v);
93 int __key_remove (struct __hash *h, __k_t k, __v_t *vp);
94 int __value_remove(struct __hash *h, __v_t v, __k_t *kp);
95 int __hash_destroy(struct __hash *h,
96 void (*entry_consumer)(__k_t k, __v_t v, void *p),
97 void *d);
98 int __hash_iterator(struct __hash *h,
99 int (*entry_consumer)(__k_t k, __v_t v, void *p),
100 void *d);
101 static void hash_resize(struct __hash *h);
103 #if defined(__ia64__)
104 #define ia64_fetchadd4_rel(p, inc) do { \
105 uint64_t ia64_intri_res; \
106 asm volatile ("fetchadd4.rel %0=[%1],%2" \
107 : "=r"(ia64_intri_res) : "r"(p), "i" (inc) \
108 : "memory"); \
109 } while (0)
110 static inline void atomic_inc(uint32_t *v) { ia64_fetchadd4_rel(v, 1); }
111 static inline void atomic_dec(uint32_t *v) { ia64_fetchadd4_rel(v, -1); }
112 #else /* __x86__ */
113 static inline void atomic_inc(uint32_t *v)
114 {
115 asm volatile (
116 "lock ; incl %0"
117 : "=m" (*(volatile uint32_t *)v)
118 : "m" (*(volatile uint32_t *)v) );
119 }
120 static inline void atomic_dec(uint32_t *v)
121 {
122 asm volatile (
123 "lock ; decl %0"
124 : "=m" (*(volatile uint32_t *)v)
125 : "m" (*(volatile uint32_t *)v) );
126 }
127 #endif
129 #ifdef BIDIR_USE_STDMALLOC
131 static void* alloc_entry(struct __hash *h, int size)
132 {
133 return malloc(size);
134 }
136 static void alloc_buckets(struct __hash *h,
137 int nr_buckets,
138 struct bucket **bucket_tab,
139 struct bucket_lock **bucket_locks_tab)
140 {
141 *bucket_tab = (struct bucket*)
142 malloc(nr_buckets * sizeof(struct bucket));
143 *bucket_locks_tab = (struct bucket_lock*)
144 malloc(nr_locks(nr_buckets) * sizeof(struct bucket_lock));
145 }
147 static void free_entry(struct __hash *h, void *p)
148 {
149 free(p);
150 }
152 static void free_buckets(struct __hash *h,
153 struct bucket *buckets,
154 struct bucket_lock *bucket_locks)
155 {
156 if(buckets) free(buckets);
157 if(bucket_locks) free(bucket_locks);
158 }
160 static int max_entries(struct __hash *h)
161 {
162 /* There are no explicit restrictions to how many entries we can store */
163 return -1;
164 }
166 #else
168 /*****************************************************************************/
169 /** Memory allocator for shared memory region **/
170 /*****************************************************************************/
171 #define SHM_TABLE_SLOTS 4
173 struct shm_hdr
174 {
175 int hash_allocated;
176 pthread_mutex_t mutex;
177 int free_tab_slots[SHM_TABLE_SLOTS];
179 unsigned long freelist_offset;
181 unsigned long entries_offset;
182 unsigned long nr_entries;
184 unsigned long tabs_offset;
185 unsigned long max_tab_size;
186 unsigned long max_lock_tab_size;
188 struct __hash hash;
189 };
191 static unsigned long get_shm_baddr(void *hdr)
192 {
193 return ((unsigned long)hdr - offsetof(struct shm_hdr, hash));
194 }
197 /** Locations of various structures/memory areas **/
198 static struct shm_hdr* get_shm_hdr(struct __hash *h)
199 {
200 return (struct shm_hdr *)
201 ((unsigned long)h - offsetof(struct shm_hdr, hash));
202 }
204 static uint32_t* get_shm_freelist(struct shm_hdr *hdr)
205 {
206 unsigned long shm_baddr = (unsigned long)hdr;
207 return ((uint32_t *)(shm_baddr + hdr->freelist_offset));
208 }
210 static struct hash_entry* get_shm_entries(struct shm_hdr *hdr)
211 {
212 unsigned long shm_baddr = (unsigned long)hdr;
213 return ((struct hash_entry *)(shm_baddr + hdr->entries_offset));
214 }
216 static struct bucket* get_shm_tab(struct shm_hdr *hdr, int i)
217 {
218 unsigned long shm_baddr = (unsigned long)hdr;
219 return ((struct bucket *)
220 ((shm_baddr + hdr->tabs_offset) +
221 i * (hdr->max_tab_size + hdr->max_lock_tab_size)));
222 }
224 static struct bucket_lock* get_shm_lock_tab(struct shm_hdr *hdr, int i)
225 {
226 unsigned long shm_baddr = (unsigned long)hdr;
227 return ((struct bucket_lock *)
228 ((shm_baddr + hdr->tabs_offset) +
229 i * (hdr->max_tab_size + hdr->max_lock_tab_size) +
230 hdr->max_tab_size));
231 }
233 static int get_shm_slot(struct shm_hdr *hdr, void *p)
234 {
235 unsigned long shm_baddr = (unsigned long)hdr;
236 return ((unsigned long)p - (shm_baddr + hdr->tabs_offset)) /
237 (hdr->max_tab_size + hdr->max_lock_tab_size);
238 }
240 /* Shared memory allocator locks */
241 static int shm_mutex_init(struct shm_hdr *h)
242 {
243 int ret;
244 pthread_mutexattr_t _attr;
246 ret = pthread_mutexattr_init(&_attr);
247 if(ret == 0)
248 ret = pthread_mutexattr_setpshared(&_attr, PTHREAD_PROCESS_SHARED);
249 if(ret == 0)
250 ret = pthread_mutex_init(&h->mutex, &_attr);
251 if(ret == 0)
252 ret = pthread_mutexattr_destroy(&_attr);
254 return ret;
255 };
257 static int shm_mutex_lock(struct shm_hdr *h)
258 {
259 return pthread_mutex_lock(&h->mutex);
260 }
262 static int shm_mutex_unlock(struct shm_hdr *h)
263 {
264 return pthread_mutex_unlock(&h->mutex);
265 }
268 /* Shared memory allocator freelist */
269 static void shm_add_to_freelist(struct shm_hdr *hdr, uint32_t sl)
270 {
271 uint32_t *freelist = get_shm_freelist(hdr);
273 shm_mutex_lock(hdr);
274 freelist[sl+1] = freelist[0];
275 freelist[0] = sl;
276 shm_mutex_unlock(hdr);
277 }
279 static uint32_t shm_get_from_freelist(struct shm_hdr *hdr)
280 {
281 uint32_t *freelist = get_shm_freelist(hdr);
282 uint32_t slot;
284 shm_mutex_lock(hdr);
285 slot = freelist[0];
286 freelist[0] = freelist[slot+1];
287 shm_mutex_unlock(hdr);
289 return (slot == 0 ? -1 : slot);
290 }
293 #define SHM_ALLOC_MAIN(_n)
295 static unsigned long shm_init_offsets(
296 struct shm_hdr *hdr, int nr_entries)
297 {
298 hdr->freelist_offset = sizeof(struct shm_hdr);
300 /* Freelist needs one extra slot in the array for the freelist head */
301 hdr->entries_offset =
302 hdr->freelist_offset + (nr_entries + 1) * sizeof(uint32_t);
303 hdr->nr_entries = nr_entries;
305 hdr->tabs_offset = hdr->entries_offset +
306 nr_entries * sizeof(struct hash_entry);
307 /* We want to allocate table 1.5 larger than the number of entries
308 we want to hold in it */
309 hdr->max_tab_size =
310 (nr_entries * 3 / 2) * sizeof(struct bucket);
311 hdr->max_lock_tab_size =
312 nr_locks(hdr->max_tab_size) * sizeof(struct bucket_lock);
314 return hdr->tabs_offset + (hdr->max_tab_size + hdr->max_lock_tab_size) * 4;
315 }
317 struct __hash* __shm_hash_init(unsigned long shm_baddr, unsigned long shm_size)
318 {
319 uint32_t i;
320 struct shm_hdr *hdr;
322 /* Some sanity checks */
323 hdr = (struct shm_hdr *)shm_baddr;
324 memset(hdr, 0, sizeof(struct shm_hdr));
326 /* Find the maximum number of entries we can store in the given shm_size */
327 for(i=1; shm_init_offsets(hdr, i) < shm_size; i++){};
328 shm_init_offsets(hdr, (i-1));
330 memset(get_shm_freelist(hdr), 0,
331 (hdr->nr_entries + 1) * sizeof(uint32_t));
332 if(shm_mutex_init(hdr) != 0)
333 return NULL;
334 for(i=0; i<hdr->nr_entries; i++)
335 shm_add_to_freelist(hdr, i);
336 for(i=0; i<SHM_TABLE_SLOTS; i++)
337 hdr->free_tab_slots[i] = 1;
339 shm_mutex_lock(hdr);
340 assert(!hdr->hash_allocated);
341 hdr->hash_allocated = 1;
342 shm_mutex_unlock(hdr);
344 return __hash_init(&hdr->hash, 1000);
345 }
347 struct __hash* __shm_hash_get(unsigned long shm_baddr)
348 {
349 struct shm_hdr *hdr = (struct shm_hdr *)shm_baddr;
351 return (hdr->hash_allocated ? &hdr->hash : NULL);
352 }
354 static void* alloc_entry(struct __hash *h, int size)
355 {
356 struct shm_hdr *hdr = get_shm_hdr(h);
357 uint32_t slot = shm_get_from_freelist(hdr);
359 assert(size == sizeof(struct hash_entry));
360 if(slot == -1)
361 return NULL;
363 return (get_shm_entries(hdr) + slot);
364 }
366 static void alloc_buckets(struct __hash *h,
367 int nr_buckets,
368 struct bucket **buckets_tab,
369 struct bucket_lock **bucket_locks_tab)
370 {
371 struct shm_hdr *hdr = get_shm_hdr(h);
372 int free_slot;
374 *buckets_tab = NULL;
375 *bucket_locks_tab = NULL;
377 if(((nr_buckets * sizeof(struct bucket)) > hdr->max_tab_size) ||
378 ((nr_locks(nr_buckets) * sizeof(struct bucket_lock)) >
379 hdr->max_lock_tab_size))
380 return;
382 shm_mutex_lock(hdr);
383 for(free_slot=0; free_slot<SHM_TABLE_SLOTS; free_slot++)
384 if(hdr->free_tab_slots[free_slot])
385 break;
386 if(free_slot == SHM_TABLE_SLOTS)
387 {
388 shm_mutex_unlock(hdr);
389 return;
390 }
391 hdr->free_tab_slots[free_slot] = 0;
392 shm_mutex_unlock(hdr);
393 *buckets_tab = get_shm_tab(hdr, free_slot);
394 *bucket_locks_tab = get_shm_lock_tab(hdr, free_slot);
395 }
397 static void free_entry(struct __hash *h, void *p)
398 {
399 struct shm_hdr *hdr = get_shm_hdr(h);
400 uint32_t slot;
402 slot = ((uint32_t)((struct hash_entry *)p -
403 get_shm_entries(hdr)));
404 shm_add_to_freelist(hdr, slot);
405 }
407 static void free_buckets(struct __hash *h,
408 struct bucket *buckets,
409 struct bucket_lock *bucket_locks)
410 {
411 struct shm_hdr *hdr = get_shm_hdr(h);
412 int slot;
414 if(!buckets || !bucket_locks)
415 {
416 assert(!buckets && !bucket_locks);
417 return;
418 }
419 slot = get_shm_slot(hdr, buckets);
420 assert(slot < SHM_TABLE_SLOTS);
421 assert((char *)bucket_locks == (char *)buckets + hdr->max_tab_size);
422 shm_mutex_lock(hdr);
423 assert(hdr->free_tab_slots[slot] == 0);
424 hdr->free_tab_slots[slot] = 1;
425 shm_mutex_unlock(hdr);
426 }
428 static int max_entries(struct __hash *h)
429 {
430 struct shm_hdr *hdr = get_shm_hdr(h);
432 return hdr->nr_entries;
433 }
435 #endif /* !BIDIR_USE_STDMALLOC */
438 /* The structures may be stored in shared memory region, with base address */
439 /* stored in shm_base_addr. All the pointers in the above structures need */
440 /* to be relative to this base address (otherwise they would not make */
441 /* sense to other processes). Bellow accessor functions are used to */
442 /* convert between canonical (base address relative) and local addresses. */
443 /* C2L stands for CANONICAL_TO_LOCAL, and vice versa */
444 #define C2L(_h, _p) ((typeof(_p))((unsigned long)(_p) + \
445 get_shm_baddr(_h)))
446 #define L2C(_h, _p) ((typeof(_p))((unsigned long)(_p) - \
447 get_shm_baddr(_h)))
450 #define HASH_LOCK_INIT(_h) ({ \
451 int _ret; \
452 pthread_rwlockattr_t _attr; \
453 \
454 h->lock_alive = 1; \
455 _ret = pthread_rwlockattr_init(&_attr); \
456 if(_ret == 0) \
457 _ret = pthread_rwlockattr_setpshared(&_attr, \
458 PTHREAD_PROCESS_SHARED); \
459 if(_ret == 0) \
460 _ret = pthread_rwlock_init(&(_h)->hash_lock, &_attr); \
461 if(_ret == 0) \
462 _ret = pthread_rwlockattr_destroy(&_attr); \
463 \
464 _ret; \
465 })
467 #define HASH_LOCK_RDLOCK(_h) ({ \
468 int _ret; \
469 \
470 if(!_h->lock_alive) _ret = ENOLCK; \
471 else \
472 { \
473 struct timespec _ts; \
474 /* 10s timeout, long but ~matches disk spin-up times */ \
475 _ts.tv_sec = time(NULL) + 10; \
476 _ts.tv_nsec = 0; \
477 _ret = pthread_rwlock_timedrdlock(&(_h)->hash_lock, &_ts); \
478 if(_ret == ETIMEDOUT) _h->lock_alive = 0; \
479 } \
480 _ret; \
481 })
483 #define HASH_LOCK_RDUNLOCK(_h) \
484 pthread_rwlock_unlock(&(_h)->hash_lock)
486 #define HASH_LOCK_WRLOCK(_h) ({ \
487 int _ret; \
488 \
489 if(!_h->lock_alive) _ret = ENOLCK; \
490 else \
491 { \
492 struct timespec _ts; \
493 _ts.tv_sec = time(NULL) + 10; \
494 _ts.tv_nsec = 0UL; \
495 _ret = pthread_rwlock_timedwrlock(&(_h)->hash_lock, &_ts); \
496 if(_ret == ETIMEDOUT) _h->lock_alive = 0; \
497 } \
498 _ret; \
499 })
501 #define HASH_LOCK_TRYWRLOCK(_h) ({ \
502 int _ret = (_h->lock_alive ? \
503 pthread_rwlock_trywrlock(&(_h)->hash_lock) : \
504 ENOLCK); \
505 _ret; \
506 })
508 #define HASH_LOCK_WRUNLOCK(_h) \
509 pthread_rwlock_unlock(&(_h)->hash_lock)
512 #define BUCKET_LOCK_INIT(_h, _b) ({ \
513 int _ret; \
514 pthread_rwlockattr_t _attr; \
515 \
516 _ret = pthread_rwlockattr_init(&_attr); \
517 if(_ret == 0) \
518 _ret = pthread_rwlockattr_setpshared(&_attr, \
519 PTHREAD_PROCESS_SHARED); \
520 if(_ret == 0) \
521 _ret = pthread_rwlock_init(&(_b)->bucket_lock, &_attr); \
522 if(_ret == 0) \
523 _ret = pthread_rwlockattr_destroy(&_attr); \
524 \
525 _ret; \
526 })
529 #define BUCKET_LOCK_RDLOCK(_h, _lock_tab, _idx) ({ \
530 int _ret; \
531 struct timespec _ts; \
532 struct bucket_lock *_lock = &(_lock_tab)[(_idx) / BUCKETS_PER_LOCK]; \
533 \
534 _ts.tv_sec = time(NULL) + 10; \
535 _ts.tv_nsec = 0; \
536 _ret = pthread_rwlock_timedrdlock(&(_lock)->bucket_lock, &_ts); \
537 if(_ret == ETIMEDOUT) (_h)->lock_alive = 0; \
538 _ret; \
539 })
542 #define BUCKET_LOCK_RDUNLOCK(_h, _lock_tab, _idx) ({ \
543 struct bucket_lock *_lock = &(_lock_tab)[(_idx) / BUCKETS_PER_LOCK]; \
544 pthread_rwlock_unlock(&(_lock)->bucket_lock); \
545 })
547 #define BUCKET_LOCK_WRLOCK(_h, _lock_tab, _idx) ({ \
548 int _ret; \
549 struct timespec _ts; \
550 struct bucket_lock *_lock = &(_lock_tab)[(_idx) / BUCKETS_PER_LOCK]; \
551 \
552 _ts.tv_sec = time(NULL) + 10; \
553 _ts.tv_nsec = 0; \
554 _ret = pthread_rwlock_timedwrlock(&(_lock)->bucket_lock, &_ts); \
555 if(_ret == ETIMEDOUT) (_h)->lock_alive = 0; \
556 _ret; \
557 })
559 #define BUCKET_LOCK_WRUNLOCK(_h, _lock_tab, _idx) ({ \
560 struct bucket_lock *_lock = &(_lock_tab)[(_idx) / BUCKETS_PER_LOCK]; \
561 pthread_rwlock_unlock(&(_lock)->bucket_lock); \
562 })
564 #define TWO_BUCKETS_LOCK_WRLOCK(_h, _blt1, _idx1, _blt2, _idx2) ({ \
565 int _ret; \
566 pthread_rwlock_t *_l1, *_l2; \
567 struct timespec _ts; \
568 struct bucket_lock *_bl1 = &(_blt1)[(_idx1) / BUCKETS_PER_LOCK]; \
569 struct bucket_lock *_bl2 = &(_blt2)[(_idx2) / BUCKETS_PER_LOCK]; \
570 \
571 assert((_bl1) != (_bl2)); \
572 if((_bl1) < (_bl2)) \
573 { \
574 _l1 = &(_bl1)->bucket_lock; \
575 _l2 = &(_bl2)->bucket_lock; \
576 } \
577 else \
578 { \
579 _l1 = &(_bl2)->bucket_lock; \
580 _l2 = &(_bl1)->bucket_lock; \
581 } \
582 _ts.tv_sec = time(NULL) + 10; \
583 _ts.tv_nsec = 0; \
584 _ret = pthread_rwlock_timedwrlock(_l1, &_ts); \
585 _ts.tv_sec = time(NULL) + 10; \
586 _ts.tv_nsec = 0; \
587 if(_ret == 0) \
588 _ret = pthread_rwlock_timedwrlock(_l2, &_ts); \
589 if(_ret == ETIMEDOUT) (_h)->lock_alive = 0; \
590 \
591 _ret; \
592 })
594 #define TWO_BUCKETS_LOCK_WRUNLOCK(_h, _blt1, _idx1, _blt2, _idx2) ({ \
595 int _ret; \
596 struct bucket_lock *_bl1 = &(_blt1)[(_idx1) / BUCKETS_PER_LOCK]; \
597 struct bucket_lock *_bl2 = &(_blt2)[(_idx2) / BUCKETS_PER_LOCK]; \
598 \
599 _ret = pthread_rwlock_unlock(&(_bl1)->bucket_lock); \
600 if(_ret == 0) \
601 _ret = pthread_rwlock_unlock(&(_bl2)->bucket_lock); \
602 \
603 _ret; \
604 })
609 static uint32_t hash_to_idx(struct __hash *h, uint32_t hash)
610 {
611 return (hash % h->tab_size);
612 }
614 static void alloc_tab(struct __hash *h,
615 int size,
616 struct bucket **buckets_tab,
617 struct bucket_lock **bucket_locks_tab)
618 {
619 int i;
621 alloc_buckets(h, size, buckets_tab, bucket_locks_tab);
622 if(!(*buckets_tab) || !(*bucket_locks_tab))
623 goto error_out;
624 memset(*buckets_tab, 0, size * sizeof(struct bucket));
625 memset(*bucket_locks_tab, 0, nr_locks(size) * sizeof(struct bucket_lock));
626 for(i=0; i<nr_locks(size); i++)
627 if(BUCKET_LOCK_INIT(h, *bucket_locks_tab + i) != 0)
628 goto error_out;
630 return;
631 error_out:
632 free_buckets(h, *buckets_tab, *bucket_locks_tab);
633 *buckets_tab = NULL;
634 *bucket_locks_tab = NULL;
635 return;
636 }
639 struct __hash *__hash_init(struct __hash *h, uint32_t min_size)
640 {
641 uint32_t size;
642 uint16_t size_idx;
643 struct bucket *buckets;
644 struct bucket_lock *bucket_locks;
646 /* Sanity check on args */
647 if (min_size > hash_sizes[hash_sizes_len-1]) return NULL;
648 /* Find least size greater than init_size */
649 for(size_idx = 0; size_idx < hash_sizes_len; size_idx++)
650 if(hash_sizes[size_idx] >= min_size)
651 break;
652 size = hash_sizes[size_idx];
654 if(!h) return NULL;
655 alloc_tab(h, size, &buckets, &bucket_locks);
656 if(!buckets || !bucket_locks) goto alloc_fail;
657 h->key_tab = L2C(h, buckets);
658 h->key_lock_tab = L2C(h, bucket_locks);
659 alloc_tab(h, size, &buckets, &bucket_locks);
660 if(!buckets || !bucket_locks) goto alloc_fail;
661 h->value_tab = L2C(h, buckets);
662 h->value_lock_tab = L2C(h, bucket_locks);
663 /* Init all h variables */
664 if(HASH_LOCK_INIT(h) != 0) goto alloc_fail;
665 h->nr_ent = 0;
666 h->tab_size = size;
667 h->size_idx = size_idx;
668 h->max_load = (uint32_t)ceilf(hash_max_load_fact * size);
669 h->min_load = (uint32_t)ceilf(hash_min_load_fact * size);
671 return h;
673 alloc_fail:
674 if(h->key_tab || h->key_lock_tab)
675 free_buckets(h, C2L(h, h->key_tab), C2L(h, h->key_lock_tab));
676 return NULL;
677 }
679 #undef __prim
680 #undef __prim_t
681 #undef __prim_tab
682 #undef __prim_lock_tab
683 #undef __prim_hash
684 #undef __prim_cmp
685 #undef __prim_next
686 #undef __sec
687 #undef __sec_t
689 #define __prim key
690 #define __prim_t __k_t
691 #define __prim_tab key_tab
692 #define __prim_lock_tab key_lock_tab
693 #define __prim_hash __key_hash
694 #define __prim_cmp __key_cmp
695 #define __prim_next key_next
696 #define __sec value
697 #define __sec_t __v_t
698 int __key_lookup(struct __hash *h, __prim_t k, __sec_t *vp)
699 {
700 struct hash_entry *entry;
701 struct bucket *b;
702 struct bucket_lock *blt;
703 uint32_t idx;
705 if(HASH_LOCK_RDLOCK(h) != 0) return -ENOLCK;
706 idx = hash_to_idx(h, __prim_hash(k));
707 b = C2L(h, &h->__prim_tab[idx]);
708 blt = C2L(h, h->__prim_lock_tab);
709 if(BUCKET_LOCK_RDLOCK(h, blt, idx) != 0) return -ENOLCK;
710 entry = b->hash_entry;
711 while(entry != NULL)
712 {
713 entry = C2L(h, entry);
714 if(__prim_cmp(k, entry->__prim))
715 {
716 /* Unlock here */
717 *vp = entry->__sec;
718 BUCKET_LOCK_RDUNLOCK(h, blt, idx);
719 HASH_LOCK_RDUNLOCK(h);
720 return 1;
721 }
722 entry = entry->__prim_next;
723 }
724 BUCKET_LOCK_RDUNLOCK(h, blt, idx);
725 HASH_LOCK_RDUNLOCK(h);
726 return 0;
727 }
729 /* value lookup is an almost exact copy of key lookup */
730 #undef __prim
731 #undef __prim_t
732 #undef __prim_tab
733 #undef __prim_lock_tab
734 #undef __prim_hash
735 #undef __prim_cmp
736 #undef __prim_next
737 #undef __sec
738 #undef __sec_t
740 #define __prim value
741 #define __prim_t __v_t
742 #define __prim_tab value_tab
743 #define __prim_lock_tab value_lock_tab
744 #define __prim_hash __value_hash
745 #define __prim_cmp __value_cmp
746 #define __prim_next value_next
747 #define __sec key
748 #define __sec_t __k_t
749 int __value_lookup(struct __hash *h, __prim_t k, __sec_t *vp)
750 {
751 struct hash_entry *entry;
752 struct bucket *b;
753 struct bucket_lock *blt;
754 uint32_t idx;
756 if(HASH_LOCK_RDLOCK(h) != 0) return -ENOLCK;
757 idx = hash_to_idx(h, __prim_hash(k));
758 b = C2L(h, &h->__prim_tab[idx]);
759 blt = C2L(h, h->__prim_lock_tab);
760 if(BUCKET_LOCK_RDLOCK(h, blt, idx) != 0) return -ENOLCK;
761 entry = b->hash_entry;
762 while(entry != NULL)
763 {
764 entry = C2L(h, entry);
765 if(__prim_cmp(k, entry->__prim))
766 {
767 /* Unlock here */
768 *vp = entry->__sec;
769 BUCKET_LOCK_RDUNLOCK(h, blt, idx);
770 HASH_LOCK_RDUNLOCK(h);
771 return 1;
772 }
773 entry = entry->__prim_next;
774 }
775 BUCKET_LOCK_RDUNLOCK(h, blt, idx);
776 HASH_LOCK_RDUNLOCK(h);
777 return 0;
778 }
780 int __insert(struct __hash *h, __k_t k, __v_t v)
781 {
782 uint32_t k_idx, v_idx;
783 struct hash_entry *entry;
784 struct bucket *bk, *bv;
785 struct bucket_lock *bltk, *bltv;
787 /* Allocate new entry before any locks (in case it fails) */
788 entry = (struct hash_entry*)
789 alloc_entry(h, sizeof(struct hash_entry));
790 if(!entry) return 0;
792 if(HASH_LOCK_RDLOCK(h) != 0) return -ENOLCK;
793 /* Read from nr_ent is atomic(TODO check), no need for fancy accessors */
794 if(h->nr_ent+1 > h->max_load)
795 {
796 /* Resize needs the write lock, drop read lock temporarily */
797 HASH_LOCK_RDUNLOCK(h);
798 hash_resize(h);
799 if(HASH_LOCK_RDLOCK(h) != 0) return -ENOLCK;
800 }
802 /* Init the entry */
803 entry->key = k;
804 entry->value = v;
806 /* Work out the indicies */
807 k_idx = hash_to_idx(h, __key_hash(k));
808 v_idx = hash_to_idx(h, __value_hash(v));
810 /* Insert */
811 bk = C2L(h, &h->key_tab[k_idx]);
812 bv = C2L(h, &h->value_tab[v_idx]);
813 bltk = C2L(h, h->key_lock_tab);
814 bltv = C2L(h, h->value_lock_tab);
815 if(TWO_BUCKETS_LOCK_WRLOCK(h, bltk, k_idx, bltv, v_idx) != 0)
816 return -ENOLCK;
817 entry->key_next = bk->hash_entry;
818 bk->hash_entry = L2C(h, entry);
819 entry->value_next = bv->hash_entry;
820 bv->hash_entry = L2C(h, entry);
821 TWO_BUCKETS_LOCK_WRUNLOCK(h, bltk, k_idx, bltv, v_idx);
823 /* Book keeping */
824 atomic_inc(&h->nr_ent);
826 HASH_LOCK_RDUNLOCK(h);
828 return 1;
829 }
832 #undef __prim
833 #undef __prim_t
834 #undef __prim_tab
835 #undef __prim_lock_tab
836 #undef __prim_hash
837 #undef __prim_cmp
838 #undef __prim_next
839 #undef __sec
840 #undef __sec_t
841 #undef __sec_tab
842 #undef __sec_lock_tab
843 #undef __sec_hash
844 #undef __sec_next
846 #define __prim key
847 #define __prim_t __k_t
848 #define __prim_tab key_tab
849 #define __prim_lock_tab key_lock_tab
850 #define __prim_hash __key_hash
851 #define __prim_cmp __key_cmp
852 #define __prim_next key_next
853 #define __sec value
854 #define __sec_t __v_t
855 #define __sec_tab value_tab
856 #define __sec_lock_tab value_lock_tab
857 #define __sec_hash __value_hash
858 #define __sec_next value_next
860 int __key_remove(struct __hash *h, __prim_t k, __sec_t *vp)
861 {
862 struct hash_entry *e, *es, **pek, **pev;
863 struct bucket *bk, *bv;
864 struct bucket_lock *bltk, *bltv;
865 uint32_t old_kidx, kidx, vidx, min_load, nr_ent;
866 __prim_t ks;
867 __sec_t vs;
869 if(HASH_LOCK_RDLOCK(h) != 0) return -ENOLCK;
871 again:
872 old_kidx = kidx = hash_to_idx(h, __prim_hash(k));
873 bk = C2L(h, &h->__prim_tab[kidx]);
874 bltk = C2L(h, h->__prim_lock_tab);
875 if(BUCKET_LOCK_RDLOCK(h, bltk, kidx) != 0) return -ENOLCK;
876 pek = &(bk->hash_entry);
877 e = *pek;
878 while(e != NULL)
879 {
880 e = C2L(h, e);
881 if(__prim_cmp(k, e->__prim))
882 {
883 goto found;
884 }
885 pek = &(e->__prim_next);
886 e = *pek;
887 }
889 BUCKET_LOCK_RDUNLOCK(h, bltk, kidx);
890 HASH_LOCK_RDUNLOCK(h);
892 return 0;
894 found:
895 /*
896 * Make local copy of key and value.
897 */
898 es = e;
899 ks = e->__prim;
900 vs = e->__sec;
901 kidx = hash_to_idx(h, __prim_hash(ks));
902 /* Being paranoid: check if kidx has not changed, so that we unlock the
903 * right bucket */
904 assert(old_kidx == kidx);
905 vidx = hash_to_idx(h, __sec_hash(vs));
906 bk = C2L(h, &h->__prim_tab[kidx]);
907 bv = C2L(h, &h->__sec_tab[vidx]);
908 bltk = C2L(h, h->__prim_lock_tab);
909 bltv = C2L(h, h->__sec_lock_tab);
910 BUCKET_LOCK_RDUNLOCK(h, bltk, kidx);
911 if(TWO_BUCKETS_LOCK_WRLOCK(h, bltk, kidx, bltv, vidx) != 0) return -ENOLCK;
912 pek = &(bk->hash_entry);
913 pev = &(bv->hash_entry);
915 /* Find the entry in both tables */
916 e = *pek;
917 while(e != NULL)
918 {
919 e = C2L(h, e);
920 if(e == es)
921 {
922 /* Being paranoid: make sure that the key and value are
923 * still the same. This is still not 100%, because, in
924 * principle, the entry could have got deleted, when we
925 * didn't hold the locks for a little while, and exactly
926 * the same entry reinserted. If the __k_t & __v_t are
927 * simple types than it probably doesn't matter, but if
928 * either is a pointer type, the actual structure might
929 * now be different. The chances that happens are very
930 * slim, but still, if that's a problem, the user needs to
931 * pay attention to the structure re-allocation */
932 if((memcmp(&(e->__prim), &ks, sizeof(__prim_t))) ||
933 (memcmp(&(e->__sec), &vs, sizeof(__sec_t))))
934 break;
935 goto found_again;
936 }
937 pek = &(e->__prim_next);
938 e = *pek;
939 }
941 TWO_BUCKETS_LOCK_WRUNLOCK(h, bltk, kidx, bltv, vidx);
943 /* Entry got removed in the meantime, try again */
944 goto again;
946 found_again:
947 /* We are now comitted to the removal */
948 e = *pev;
949 while(e != NULL)
950 {
951 e = C2L(h, e);
952 if(e == es)
953 {
954 /* Both pek and pev are pointing to the right place, remove */
955 *pek = e->__prim_next;
956 *pev = e->__sec_next;
958 atomic_dec(&h->nr_ent);
959 nr_ent = h->nr_ent;
960 /* read min_load still under the hash lock! */
961 min_load = h->min_load;
963 TWO_BUCKETS_LOCK_WRUNLOCK(h, bltk, kidx, bltv, vidx);
964 HASH_LOCK_RDUNLOCK(h);
966 if(nr_ent < min_load)
967 hash_resize(h);
968 if(vp != NULL)
969 *vp = e->__sec;
970 free_entry(h, e);
971 return 1;
972 }
973 pev = &(e->__sec_next);
974 e = *pev;
975 }
977 /* We should never get here!, no need to unlock anything */
978 return -ENOLCK;
979 }
981 #undef __prim
982 #undef __prim_t
983 #undef __prim_tab
984 #undef __prim_lock_tab
985 #undef __prim_hash
986 #undef __prim_cmp
987 #undef __prim_next
988 #undef __sec
989 #undef __sec_t
990 #undef __sec_tab
991 #undef __sec_lock_tab
992 #undef __sec_hash
993 #undef __sec_next
995 #define __prim value
996 #define __prim_t __v_t
997 #define __prim_tab value_tab
998 #define __prim_lock_tab value_lock_tab
999 #define __prim_hash __value_hash
1000 #define __prim_cmp __value_cmp
1001 #define __prim_next value_next
1002 #define __sec key
1003 #define __sec_t __k_t
1004 #define __sec_tab key_tab
1005 #define __sec_lock_tab key_lock_tab
1006 #define __sec_hash __key_hash
1007 #define __sec_next key_next
1009 int __value_remove(struct __hash *h, __prim_t k, __sec_t *vp)
1011 struct hash_entry *e, *es, **pek, **pev;
1012 struct bucket *bk, *bv;
1013 struct bucket_lock *bltk, *bltv;
1014 uint32_t old_kidx, kidx, vidx, min_load, nr_ent;
1015 __prim_t ks;
1016 __sec_t vs;
1018 if(HASH_LOCK_RDLOCK(h) != 0) return -ENOLCK;
1020 again:
1021 old_kidx = kidx = hash_to_idx(h, __prim_hash(k));
1022 bk = C2L(h, &h->__prim_tab[kidx]);
1023 bltk = C2L(h, h->__prim_lock_tab);
1024 if(BUCKET_LOCK_RDLOCK(h, bltk, kidx) != 0) return -ENOLCK;
1025 pek = &(bk->hash_entry);
1026 e = *pek;
1027 while(e != NULL)
1029 e = C2L(h, e);
1030 if(__prim_cmp(k, e->__prim))
1032 goto found;
1034 pek = &(e->__prim_next);
1035 e = *pek;
1038 BUCKET_LOCK_RDUNLOCK(h, bltk, kidx);
1039 HASH_LOCK_RDUNLOCK(h);
1041 return 0;
1043 found:
1044 /*
1045 * Make local copy of key and value.
1046 */
1047 es = e;
1048 ks = e->__prim;
1049 vs = e->__sec;
1050 kidx = hash_to_idx(h, __prim_hash(ks));
1051 /* Being paranoid: check if kidx has not changed, so that we unlock the
1052 * right bucket */
1053 assert(old_kidx == kidx);
1054 vidx = hash_to_idx(h, __sec_hash(vs));
1055 bk = C2L(h, &h->__prim_tab[kidx]);
1056 bv = C2L(h, &h->__sec_tab[vidx]);
1057 bltk = C2L(h, h->__prim_lock_tab);
1058 bltv = C2L(h, h->__sec_lock_tab);
1059 BUCKET_LOCK_RDUNLOCK(h, bltk, kidx);
1060 if(TWO_BUCKETS_LOCK_WRLOCK(h, bltk, kidx, bltv, vidx) != 0) return -ENOLCK;
1061 pek = &(bk->hash_entry);
1062 pev = &(bv->hash_entry);
1064 /* Find the entry in both tables */
1065 e = *pek;
1066 while(e != NULL)
1068 e = C2L(h, e);
1069 if(e == es)
1071 /* Being paranoid: make sure that the key and value are
1072 * still the same. This is still not 100%, because, in
1073 * principle, the entry could have got deleted, when we
1074 * didn't hold the locks for a little while, and exactly
1075 * the same entry reinserted. If the __k_t & __v_t are
1076 * simple types than it probably doesn't matter, but if
1077 * either is a pointer type, the actual structure might
1078 * now be different. The chances that happens are very
1079 * slim, but still, if that's a problem, the user needs to
1080 * pay attention to the structure re-allocation */
1081 if((memcmp(&(e->__prim), &ks, sizeof(__prim_t))) ||
1082 (memcmp(&(e->__sec), &vs, sizeof(__sec_t))))
1083 break;
1084 goto found_again;
1086 pek = &(e->__prim_next);
1087 e = *pek;
1090 TWO_BUCKETS_LOCK_WRUNLOCK(h, bltk, kidx, bltv, vidx);
1092 /* Entry got removed in the meantime, try again */
1093 goto again;
1095 found_again:
1096 /* We are now comitted to the removal */
1097 e = *pev;
1098 while(e != NULL)
1100 e = C2L(h, e);
1101 if(e == es)
1103 /* Both pek and pev are pointing to the right place, remove */
1104 *pek = e->__prim_next;
1105 *pev = e->__sec_next;
1107 atomic_dec(&h->nr_ent);
1108 nr_ent = h->nr_ent;
1109 /* read min_load still under the hash lock! */
1110 min_load = h->min_load;
1112 TWO_BUCKETS_LOCK_WRUNLOCK(h, bltk, kidx, bltv, vidx);
1113 HASH_LOCK_RDUNLOCK(h);
1115 if(nr_ent < min_load)
1116 hash_resize(h);
1117 if(vp != NULL)
1118 *vp = e->__sec;
1119 free_entry(h, e);
1120 return 1;
1122 pev = &(e->__sec_next);
1123 e = *pev;
1126 /* We should never get here!, no need to unlock anything */
1127 return -ENOLCK;
1131 int __hash_destroy(struct __hash *h,
1132 void (*entry_consumer)(__k_t k, __v_t v, void *p),
1133 void *d)
1135 struct hash_entry *e, *n;
1136 struct bucket *b;
1137 int i;
1139 if(HASH_LOCK_WRLOCK(h) != 0) return -ENOLCK;
1141 /* No need to lock individual buckets, with hash write lock */
1142 for(i=0; i < h->tab_size; i++)
1144 b = C2L(h, &h->key_tab[i]);
1145 e = b->hash_entry;
1146 while(e != NULL)
1148 e = C2L(h, e);
1149 n = e->key_next;
1150 if(entry_consumer)
1151 entry_consumer(e->key, e->value, d);
1152 free_entry(h, e);
1153 e = n;
1156 free_buckets(h, C2L(h, h->key_tab), C2L(h, h->key_lock_tab));
1157 free_buckets(h, C2L(h, h->value_tab), C2L(h, h->value_lock_tab));
1159 HASH_LOCK_WRUNLOCK(h);
1160 h->lock_alive = 0;
1162 return 0;
1165 static void hash_resize(struct __hash *h)
1167 int new_size_idx, i, lock_ret;
1168 uint32_t size, old_size, kidx, vidx;
1169 struct bucket *t1, *t2, *b;
1170 struct bucket_lock *l1, *l2;
1171 struct hash_entry *e, *n;
1173 /* We may fail to allocate the lock, if the resize is triggered while
1174 we are iterating (under read lock) */
1175 lock_ret = HASH_LOCK_TRYWRLOCK(h);
1176 if(lock_ret != 0) return;
1178 new_size_idx = h->size_idx;
1179 /* Work out the new size */
1180 if(h->nr_ent >= h->max_load)
1181 new_size_idx = h->size_idx+1;
1182 if(h->nr_ent < h->min_load)
1183 new_size_idx = h->size_idx-1;
1184 if((new_size_idx == h->size_idx) ||
1185 (new_size_idx >= hash_sizes_len) ||
1186 (new_size_idx < 0))
1188 HASH_LOCK_WRUNLOCK(h);
1189 return;
1192 size = hash_sizes[new_size_idx];
1194 /* Allocate the new sizes */
1195 t1 = t2 = NULL;
1196 l1 = l2 = NULL;
1197 alloc_tab(h, size, &t1, &l1);
1198 if(!t1 || !l1) goto alloc_fail;
1199 alloc_tab(h, size, &t2, &l2);
1200 if(!t2 || !l2) goto alloc_fail;
1202 old_size = h->tab_size;
1203 h->tab_size = size;
1204 h->size_idx = new_size_idx;
1205 h->max_load = (uint32_t)ceilf(hash_max_load_fact * size);
1206 h->min_load = (uint32_t)ceilf(hash_min_load_fact * size);
1208 /* Move the entries */
1209 for(i=0; i < old_size; i++)
1211 b = C2L(h, &h->key_tab[i]);
1212 e = b->hash_entry;
1213 while(e != NULL)
1215 e = C2L(h, e);
1216 n = e->key_next;
1217 kidx =hash_to_idx(h, __key_hash(e->key));
1218 vidx =hash_to_idx(h, __value_hash(e->value));
1219 /* Move to the correct bucket */
1220 e->key_next = t1[kidx].hash_entry;
1221 t1[kidx].hash_entry = L2C(h, e);
1222 e->value_next = t2[vidx].hash_entry;
1223 t2[vidx].hash_entry = L2C(h, e);
1224 e = n;
1227 free_buckets(h, C2L(h, h->key_tab), C2L(h, h->key_lock_tab));
1228 free_buckets(h, C2L(h, h->value_tab), C2L(h, h->value_lock_tab));
1229 h->key_tab = L2C(h, t1);
1230 h->key_lock_tab = L2C(h, l1);
1231 h->value_tab = L2C(h, t2);
1232 h->value_lock_tab = L2C(h, l2);
1234 HASH_LOCK_WRUNLOCK(h);
1236 return;
1238 alloc_fail:
1239 /* If we failed to resize, adjust max/min load. This will stop us from
1240 * retrying resize too frequently */
1241 if(new_size_idx > h->size_idx)
1242 h->max_load = (h->max_load + 2 * h->tab_size) / 2 + 1;
1243 else
1244 if (new_size_idx < h->size_idx)
1245 h->min_load = h->min_load / 2;
1246 HASH_LOCK_WRUNLOCK(h);
1247 if(t1 || l1) free_buckets(h, t1, l1);
1248 if(t2 || l2) free_buckets(h, t2, l2);
1249 return;
1252 int __hash_iterator(struct __hash *h,
1253 int (*entry_consumer)(__k_t k, __v_t v, void *p),
1254 void *d)
1256 struct hash_entry *e, *n;
1257 struct bucket *b;
1258 struct bucket_lock *blt;
1259 int i, brk_early;
1261 if(HASH_LOCK_RDLOCK(h) != 0) return -ENOLCK;
1263 for(i=0; i < h->tab_size; i++)
1265 b = C2L(h, &h->key_tab[i]);
1266 blt = C2L(h, h->key_lock_tab);
1267 if(BUCKET_LOCK_RDLOCK(h, blt, i) != 0) return -ENOLCK;
1268 e = b->hash_entry;
1269 while(e != NULL)
1271 e = C2L(h, e);
1272 n = e->key_next;
1273 brk_early = entry_consumer(e->key, e->value, d);
1274 if(brk_early)
1276 BUCKET_LOCK_RDUNLOCK(h, blt, i);
1277 goto out;
1279 e = n;
1281 BUCKET_LOCK_RDUNLOCK(h, blt, i);
1283 out:
1284 HASH_LOCK_RDUNLOCK(h);
1285 return 0;
1288 void __hash_sizes(struct __hash *h,
1289 uint32_t *nr_ent,
1290 uint32_t *max_nr_ent,
1291 uint32_t *tab_size,
1292 uint32_t *max_load,
1293 uint32_t *min_load)
1295 if(nr_ent != NULL) *nr_ent = h->nr_ent;
1296 if(max_nr_ent != NULL) *max_nr_ent = max_entries(h);
1297 if(tab_size != NULL) *tab_size = h->tab_size;
1298 if(max_load != NULL) *max_load = h->max_load;
1299 if(min_load != NULL) *min_load = h->min_load;