1 // SPDX-FileCopyrightText: 2011 Mathieu Desnoyers <mathieu.desnoyers (at) efficios.com> 2 // SPDX-FileCopyrightText: 2011 Lai Jiangshan <laijs (at) cn.fujitsu.com> 3 // 4 // SPDX-License-Identifier: LGPL-2.1-or-later 5 6 #ifndef _URCU_RCULFHASH_INTERNAL_H 7 #define _URCU_RCULFHASH_INTERNAL_H 8 9 /* 10 * Internal header for Lock-Free RCU Hash Table 11 */ 12 13 #include <urcu/assert.h> 14 #include <urcu/rculfhash.h> 15 #include <stdio.h> 16 #include <stdlib.h> 17 18 #include "workqueue.h" 19 20 #ifdef DEBUG 21 #define dbg_printf(fmt, args...) printf("[debug rculfhash] " fmt, ## args) 22 #else 23 #define dbg_printf(fmt, args...) \ 24 do { \ 25 /* do nothing but check printf format */ \ 26 if (0) \ 27 printf("[debug rculfhash] " fmt, ## args); \ 28 } while (0) 29 #endif 30 31 #if (CAA_BITS_PER_LONG == 32) 32 #define MAX_TABLE_ORDER 32 33 #else 34 #define MAX_TABLE_ORDER 64 35 #endif 36 37 #define MAX_CHUNK_TABLE (1UL << 10) 38 39 #ifndef min 40 #define min(a, b) ((a) < (b) ? (a) : (b)) 41 #endif 42 43 #ifndef max 44 #define max(a, b) ((a) > (b) ? (a) : (b)) 45 #endif 46 47 struct ht_items_count; 48 49 /* 50 * cds_lfht: Top-level data structure representing a lock-free hash 51 * table. Defined in the implementation file to make it be an opaque 52 * cookie to users. 53 * 54 * The fields used in fast-paths are placed near the end of the 55 * structure, because we need to have a variable-sized union to contain 56 * the mm plugin fields, which are used in the fast path. 57 */ 58 struct cds_lfht { 59 /* Initial configuration items */ 60 unsigned long max_nr_buckets; 61 const struct cds_lfht_mm_type *mm; /* memory management plugin */ 62 const struct cds_lfht_alloc *alloc; /* memory allocator for mm */ 63 const struct rcu_flavor_struct *flavor; /* RCU flavor */ 64 65 long count; /* global approximate item count */ 66 67 /* 68 * We need to put the work threads offline (QSBR) when taking this 69 * mutex, because we use synchronize_rcu within this mutex critical 70 * section, which waits on read-side critical sections, and could 71 * therefore cause grace-period deadlock if we hold off RCU G.P. 72 * completion. 73 */ 74 pthread_mutex_t resize_mutex; /* resize mutex: add/del mutex */ 75 pthread_attr_t *caller_resize_attr; /* resize threads attributes from lfht_new caller */ 76 pthread_attr_t resize_attr; 77 unsigned int in_progress_destroy; 78 unsigned long resize_target; 79 int resize_initiated; 80 struct urcu_work destroy_work; 81 82 /* 83 * Variables needed for add and remove fast-paths. 84 */ 85 int flags; 86 unsigned long min_alloc_buckets_order; 87 unsigned long min_nr_alloc_buckets; 88 struct ht_items_count *split_count; /* split item count */ 89 90 /* 91 * Variables needed for the lookup, add and remove fast-paths. 92 */ 93 unsigned long size; /* always a power of 2, shared (RCU) */ 94 /* 95 * bucket_at pointer is kept here to skip the extra level of 96 * dereference needed to get to "mm" (this is a fast-path). 97 */ 98 struct cds_lfht_node *(*bucket_at)(struct cds_lfht *ht, 99 unsigned long index); 100 /* 101 * Dynamic length "tbl_chunk" needs to be at the end of 102 * cds_lfht. 103 */ 104 union { 105 /* 106 * Contains the per order-index-level bucket node table. 107 * The size of each bucket node table is half the number 108 * of hashes contained in this order (except for order 0). 109 * The minimum allocation buckets size parameter allows 110 * combining the bucket node arrays of the lowermost 111 * levels to improve cache locality for small index orders. 112 */ 113 struct cds_lfht_node *tbl_order[MAX_TABLE_ORDER]; 114 115 /* 116 * Contains the bucket node chunks. The size of each 117 * bucket node chunk is ->min_alloc_size (we avoid to 118 * allocate chunks with different size). Chunks improve 119 * cache locality for small index orders, and are more 120 * friendly with environments where allocation of large 121 * contiguous memory areas is challenging due to memory 122 * fragmentation concerns or inability to use virtual 123 * memory addressing. 124 */ 125 struct cds_lfht_node *tbl_chunk[0]; 126 127 /* 128 * Memory mapping with room for all possible buckets. 129 * Their memory is allocated when needed. 130 */ 131 struct cds_lfht_node *tbl_mmap; 132 }; 133 /* 134 * End of variables needed for the lookup, add and remove 135 * fast-paths. 136 */ 137 }; 138 139 extern unsigned int cds_lfht_fls_ulong(unsigned long x); 140 extern int cds_lfht_get_count_order_ulong(unsigned long x); 141 142 #ifdef POISON_FREE 143 #define poison_free(alloc, ptr) \ 144 do { \ 145 if (ptr) { \ 146 memset(ptr, 0x42, sizeof(*(ptr))); \ 147 alloc->free(alloc->state, ptr); \ 148 } \ 149 } while (0) 150 #else 151 #define poison_free(alloc, ptr) alloc->free(alloc->state, ptr) 152 #endif 153 154 static inline 155 struct cds_lfht *__default_alloc_cds_lfht( 156 const struct cds_lfht_mm_type *mm, 157 const struct cds_lfht_alloc *alloc, 158 unsigned long cds_lfht_size, 159 unsigned long min_nr_alloc_buckets, 160 unsigned long max_nr_buckets) 161 { 162 struct cds_lfht *ht; 163 164 ht = alloc->calloc(alloc->state, 1, cds_lfht_size); 165 urcu_posix_assert(ht); 166 167 ht->mm = mm; 168 ht->alloc = alloc; 169 ht->bucket_at = mm->bucket_at; 170 ht->min_nr_alloc_buckets = min_nr_alloc_buckets; 171 ht->min_alloc_buckets_order = 172 cds_lfht_get_count_order_ulong(min_nr_alloc_buckets); 173 ht->max_nr_buckets = max_nr_buckets; 174 175 return ht; 176 } 177 178 #endif /* _URCU_RCULFHASH_INTERNAL_H */ 179
Indexes created Fri Jun 12 00:25:51 UTC 2026