Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (c) 2015 Cisco and/or its affiliates. |
| 3 | * Licensed under the Apache License, Version 2.0 (the "License"); |
| 4 | * you may not use this file except in compliance with the License. |
| 5 | * You may obtain a copy of the License at: |
| 6 | * |
| 7 | * http://www.apache.org/licenses/LICENSE-2.0 |
| 8 | * |
| 9 | * Unless required by applicable law or agreed to in writing, software |
| 10 | * distributed under the License is distributed on an "AS IS" BASIS, |
| 11 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 12 | * See the License for the specific language governing permissions and |
| 13 | * limitations under the License. |
| 14 | */ |
| 15 | |
Chris Luke | 16bcf7d | 2016-09-01 14:31:46 -0400 | [diff] [blame] | 16 | /** @cond DOCUMENTATION_IS_IN_BIHASH_DOC_H */ |
Dave Barach | dd3a57f | 2016-07-27 16:58:51 -0400 | [diff] [blame] | 17 | |
Dave Barach | 16e4a4a | 2020-04-16 12:00:14 -0400 | [diff] [blame] | 18 | #ifndef MAP_HUGE_SHIFT |
| 19 | #define MAP_HUGE_SHIFT 26 |
| 20 | #endif |
| 21 | |
Dave Barach | 97f5af0 | 2018-02-22 09:48:45 -0500 | [diff] [blame] | 22 | static inline void *BV (alloc_aligned) (BVT (clib_bihash) * h, uword nbytes) |
| 23 | { |
| 24 | uword rv; |
| 25 | |
| 26 | /* Round to an even number of cache lines */ |
| 27 | nbytes += CLIB_CACHE_LINE_BYTES - 1; |
| 28 | nbytes &= ~(CLIB_CACHE_LINE_BYTES - 1); |
| 29 | |
Dave Barach | 9466c45 | 2018-08-24 17:21:14 -0400 | [diff] [blame] | 30 | rv = alloc_arena_next (h); |
| 31 | alloc_arena_next (h) += nbytes; |
Dave Barach | 97f5af0 | 2018-02-22 09:48:45 -0500 | [diff] [blame] | 32 | |
Andreas Schultz | b4b525e | 2019-07-19 11:14:50 +0200 | [diff] [blame] | 33 | if (alloc_arena_next (h) > alloc_arena_size (h)) |
Dave Barach | 97f5af0 | 2018-02-22 09:48:45 -0500 | [diff] [blame] | 34 | os_out_of_memory (); |
| 35 | |
Dave Barach | 16e4a4a | 2020-04-16 12:00:14 -0400 | [diff] [blame] | 36 | if (alloc_arena_next (h) > alloc_arena_mapped (h)) |
| 37 | { |
| 38 | void *base, *rv; |
| 39 | uword alloc = alloc_arena_next (h) - alloc_arena_mapped (h); |
| 40 | int mmap_flags = MAP_FIXED | MAP_PRIVATE | MAP_ANONYMOUS; |
Damjan Marion | e6db775 | 2020-05-24 20:43:10 +0200 | [diff] [blame^] | 41 | int mmap_flags_huge = (mmap_flags | MAP_HUGETLB | MAP_LOCKED | |
Dave Barach | 16e4a4a | 2020-04-16 12:00:14 -0400 | [diff] [blame] | 42 | BIHASH_LOG2_HUGEPAGE_SIZE << MAP_HUGE_SHIFT); |
| 43 | |
| 44 | /* new allocation is 25% of existing one */ |
| 45 | if (alloc_arena_mapped (h) >> 2 > alloc) |
| 46 | alloc = alloc_arena_mapped (h) >> 2; |
| 47 | |
| 48 | /* round allocation to page size */ |
| 49 | alloc = round_pow2 (alloc, 1 << BIHASH_LOG2_HUGEPAGE_SIZE); |
| 50 | |
| 51 | base = (void *) (uword) (alloc_arena (h) + alloc_arena_mapped (h)); |
| 52 | |
| 53 | rv = mmap (base, alloc, PROT_READ | PROT_WRITE, mmap_flags_huge, -1, 0); |
| 54 | |
| 55 | /* fallback - maybe we are still able to allocate normal pages */ |
| 56 | if (rv == MAP_FAILED) |
| 57 | rv = mmap (base, alloc, PROT_READ | PROT_WRITE, mmap_flags, -1, 0); |
| 58 | |
| 59 | if (rv == MAP_FAILED) |
| 60 | os_out_of_memory (); |
| 61 | |
| 62 | alloc_arena_mapped (h) += alloc; |
| 63 | } |
| 64 | |
Dave Barach | ffb14b9 | 2018-09-11 17:20:23 -0400 | [diff] [blame] | 65 | return (void *) (uword) (rv + alloc_arena (h)); |
Dave Barach | 97f5af0 | 2018-02-22 09:48:45 -0500 | [diff] [blame] | 66 | } |
| 67 | |
Vijayabhaskar Katamreddy | f0bae64 | 2020-01-15 13:45:19 -0800 | [diff] [blame] | 68 | static void BV (clib_bihash_instantiate) (BVT (clib_bihash) * h) |
Dave Barach | 32dcd3b | 2019-07-08 12:25:38 -0400 | [diff] [blame] | 69 | { |
| 70 | uword bucket_size; |
| 71 | |
Dave Barach | 16e4a4a | 2020-04-16 12:00:14 -0400 | [diff] [blame] | 72 | alloc_arena (h) = clib_mem_vm_reserve (0, h->memory_size, |
| 73 | BIHASH_LOG2_HUGEPAGE_SIZE); |
| 74 | if (alloc_arena (h) == ~0) |
| 75 | os_out_of_memory (); |
Dave Barach | 32dcd3b | 2019-07-08 12:25:38 -0400 | [diff] [blame] | 76 | alloc_arena_next (h) = 0; |
| 77 | alloc_arena_size (h) = h->memory_size; |
Dave Barach | 16e4a4a | 2020-04-16 12:00:14 -0400 | [diff] [blame] | 78 | alloc_arena_mapped (h) = 0; |
Dave Barach | 32dcd3b | 2019-07-08 12:25:38 -0400 | [diff] [blame] | 79 | |
| 80 | bucket_size = h->nbuckets * sizeof (h->buckets[0]); |
Dave Barach | 16e4a4a | 2020-04-16 12:00:14 -0400 | [diff] [blame] | 81 | |
| 82 | if (BIHASH_KVP_AT_BUCKET_LEVEL) |
| 83 | bucket_size += |
| 84 | h->nbuckets * BIHASH_KVP_PER_PAGE * sizeof (BVT (clib_bihash_kv)); |
| 85 | |
Dave Barach | 32dcd3b | 2019-07-08 12:25:38 -0400 | [diff] [blame] | 86 | h->buckets = BV (alloc_aligned) (h, bucket_size); |
Dave Barach | 16e4a4a | 2020-04-16 12:00:14 -0400 | [diff] [blame] | 87 | |
| 88 | if (BIHASH_KVP_AT_BUCKET_LEVEL) |
| 89 | { |
| 90 | int i; |
| 91 | BVT (clib_bihash_bucket) * b; |
| 92 | |
| 93 | b = h->buckets; |
| 94 | |
| 95 | for (i = 0; i < h->nbuckets; i++) |
| 96 | { |
| 97 | b->offset = BV (clib_bihash_get_offset) (h, (void *) (b + 1)); |
| 98 | b->refcnt = 1; |
| 99 | /* Mark all elements free */ |
| 100 | clib_memset ((b + 1), 0xff, |
| 101 | BIHASH_KVP_PER_PAGE * sizeof (BVT (clib_bihash_kv))); |
| 102 | |
| 103 | /* Compute next bucket start address */ |
| 104 | b = (void *) (((uword) b) + sizeof (*b) + |
| 105 | (BIHASH_KVP_PER_PAGE * |
| 106 | sizeof (BVT (clib_bihash_kv)))); |
| 107 | } |
| 108 | } |
Damjan Marion | 801ec2a | 2020-04-21 19:42:30 +0200 | [diff] [blame] | 109 | CLIB_MEMORY_STORE_BARRIER (); |
Dave Barach | 67d09e0 | 2019-08-01 08:15:01 -0400 | [diff] [blame] | 110 | h->instantiated = 1; |
Dave Barach | 32dcd3b | 2019-07-08 12:25:38 -0400 | [diff] [blame] | 111 | } |
Dave Barach | 97f5af0 | 2018-02-22 09:48:45 -0500 | [diff] [blame] | 112 | |
Dave Barach | bdf9b97 | 2019-09-03 10:57:19 -0400 | [diff] [blame] | 113 | void BV (clib_bihash_init2) (BVT (clib_bihash_init2_args) * a) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 114 | { |
Dave Barach | 32dcd3b | 2019-07-08 12:25:38 -0400 | [diff] [blame] | 115 | int i; |
| 116 | void *oldheap; |
Dave Barach | bdf9b97 | 2019-09-03 10:57:19 -0400 | [diff] [blame] | 117 | BVT (clib_bihash) * h = a->h; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 118 | |
Dave Barach | bdf9b97 | 2019-09-03 10:57:19 -0400 | [diff] [blame] | 119 | a->nbuckets = 1 << (max_log2 (a->nbuckets)); |
| 120 | |
| 121 | h->name = (u8 *) a->name; |
| 122 | h->nbuckets = a->nbuckets; |
| 123 | h->log2_nbuckets = max_log2 (a->nbuckets); |
| 124 | h->memory_size = a->memory_size; |
Dave Barach | 67d09e0 | 2019-08-01 08:15:01 -0400 | [diff] [blame] | 125 | h->instantiated = 0; |
Dave Barach | bdf9b97 | 2019-09-03 10:57:19 -0400 | [diff] [blame] | 126 | h->fmt_fn = a->fmt_fn; |
| 127 | |
Dave Barach | 32dcd3b | 2019-07-08 12:25:38 -0400 | [diff] [blame] | 128 | alloc_arena (h) = 0; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 129 | |
Dave Barach | 508498f | 2018-07-19 12:11:16 -0400 | [diff] [blame] | 130 | /* |
| 131 | * Make sure the requested size is rational. The max table |
| 132 | * size without playing the alignment card is 64 Gbytes. |
| 133 | * If someone starts complaining that's not enough, we can shift |
| 134 | * the offset by CLIB_LOG2_CACHE_LINE_BYTES... |
| 135 | */ |
Dave Barach | bdf9b97 | 2019-09-03 10:57:19 -0400 | [diff] [blame] | 136 | ASSERT (h->memory_size < (1ULL << BIHASH_BUCKET_OFFSET_BITS)); |
Dave Barach | 32dcd3b | 2019-07-08 12:25:38 -0400 | [diff] [blame] | 137 | |
| 138 | /* Add this hash table to the list */ |
Dave Barach | bdf9b97 | 2019-09-03 10:57:19 -0400 | [diff] [blame] | 139 | if (a->dont_add_to_all_bihash_list == 0) |
| 140 | { |
| 141 | for (i = 0; i < vec_len (clib_all_bihashes); i++) |
| 142 | if (clib_all_bihashes[i] == h) |
| 143 | goto do_lock; |
| 144 | oldheap = clib_all_bihash_set_heap (); |
| 145 | vec_add1 (clib_all_bihashes, (void *) h); |
| 146 | clib_mem_set_heap (oldheap); |
| 147 | } |
Dave Barach | 32dcd3b | 2019-07-08 12:25:38 -0400 | [diff] [blame] | 148 | |
Dave Barach | bdf9b97 | 2019-09-03 10:57:19 -0400 | [diff] [blame] | 149 | do_lock: |
| 150 | if (h->alloc_lock) |
| 151 | clib_mem_free ((void *) h->alloc_lock); |
Dave Barach | 67d09e0 | 2019-08-01 08:15:01 -0400 | [diff] [blame] | 152 | |
| 153 | /* |
| 154 | * Set up the lock now, so we can use it to make the first add |
| 155 | * thread-safe |
| 156 | */ |
| 157 | h->alloc_lock = clib_mem_alloc_aligned (CLIB_CACHE_LINE_BYTES, |
| 158 | CLIB_CACHE_LINE_BYTES); |
| 159 | h->alloc_lock[0] = 0; |
| 160 | |
Dave Barach | 16e4a4a | 2020-04-16 12:00:14 -0400 | [diff] [blame] | 161 | #if BIHASH_LAZY_INSTANTIATE |
Dave Barach | bdf9b97 | 2019-09-03 10:57:19 -0400 | [diff] [blame] | 162 | if (a->instantiate_immediately) |
Dave Barach | 16e4a4a | 2020-04-16 12:00:14 -0400 | [diff] [blame] | 163 | #endif |
Dave Barach | bdf9b97 | 2019-09-03 10:57:19 -0400 | [diff] [blame] | 164 | BV (clib_bihash_instantiate) (h); |
| 165 | } |
| 166 | |
| 167 | void BV (clib_bihash_init) |
| 168 | (BVT (clib_bihash) * h, char *name, u32 nbuckets, uword memory_size) |
| 169 | { |
| 170 | BVT (clib_bihash_init2_args) _a, *a = &_a; |
| 171 | |
| 172 | memset (a, 0, sizeof (*a)); |
| 173 | |
| 174 | a->h = h; |
| 175 | a->name = name; |
| 176 | a->nbuckets = nbuckets; |
| 177 | a->memory_size = memory_size; |
| 178 | |
| 179 | BV (clib_bihash_init2) (a); |
Vijayabhaskar Katamreddy | fb8e61c | 2017-12-14 13:20:50 -0800 | [diff] [blame] | 180 | } |
| 181 | |
Dave Barach | 9466c45 | 2018-08-24 17:21:14 -0400 | [diff] [blame] | 182 | #if BIHASH_32_64_SVM |
| 183 | #if !defined (MFD_ALLOW_SEALING) |
| 184 | #define MFD_ALLOW_SEALING 0x0002U |
| 185 | #endif |
| 186 | |
| 187 | void BV (clib_bihash_master_init_svm) |
Dave Barach | ffb14b9 | 2018-09-11 17:20:23 -0400 | [diff] [blame] | 188 | (BVT (clib_bihash) * h, char *name, u32 nbuckets, u64 memory_size) |
Dave Barach | 9466c45 | 2018-08-24 17:21:14 -0400 | [diff] [blame] | 189 | { |
| 190 | uword bucket_size; |
| 191 | u8 *mmap_addr; |
| 192 | vec_header_t *freelist_vh; |
| 193 | int fd; |
| 194 | |
Dave Barach | ffb14b9 | 2018-09-11 17:20:23 -0400 | [diff] [blame] | 195 | ASSERT (memory_size < (1ULL << 32)); |
Dave Barach | 9466c45 | 2018-08-24 17:21:14 -0400 | [diff] [blame] | 196 | /* Set up for memfd sharing */ |
| 197 | if ((fd = memfd_create (name, MFD_ALLOW_SEALING)) == -1) |
| 198 | { |
| 199 | clib_unix_warning ("memfd_create"); |
| 200 | return; |
| 201 | } |
| 202 | |
| 203 | if (ftruncate (fd, memory_size) < 0) |
| 204 | { |
| 205 | clib_unix_warning ("ftruncate"); |
| 206 | return; |
| 207 | } |
| 208 | |
| 209 | /* Not mission-critical, complain and continue */ |
| 210 | if ((fcntl (fd, F_ADD_SEALS, F_SEAL_SHRINK)) == -1) |
| 211 | clib_unix_warning ("fcntl (F_ADD_SEALS)"); |
| 212 | |
Dave Barach | ffb14b9 | 2018-09-11 17:20:23 -0400 | [diff] [blame] | 213 | mmap_addr = mmap (0, memory_size, |
| 214 | PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0 /* offset */ ); |
Dave Barach | 9466c45 | 2018-08-24 17:21:14 -0400 | [diff] [blame] | 215 | |
| 216 | if (mmap_addr == MAP_FAILED) |
| 217 | { |
| 218 | clib_unix_warning ("mmap failed"); |
| 219 | ASSERT (0); |
| 220 | } |
| 221 | |
| 222 | h->sh = (void *) mmap_addr; |
| 223 | h->memfd = fd; |
| 224 | nbuckets = 1 << (max_log2 (nbuckets)); |
| 225 | |
| 226 | h->name = (u8 *) name; |
| 227 | h->sh->nbuckets = h->nbuckets = nbuckets; |
| 228 | h->log2_nbuckets = max_log2 (nbuckets); |
| 229 | |
| 230 | alloc_arena (h) = (u64) (uword) mmap_addr; |
Dave Barach | ffb14b9 | 2018-09-11 17:20:23 -0400 | [diff] [blame] | 231 | alloc_arena_next (h) = CLIB_CACHE_LINE_BYTES; |
Dave Barach | 9466c45 | 2018-08-24 17:21:14 -0400 | [diff] [blame] | 232 | alloc_arena_size (h) = memory_size; |
| 233 | |
| 234 | bucket_size = nbuckets * sizeof (h->buckets[0]); |
| 235 | h->buckets = BV (alloc_aligned) (h, bucket_size); |
Dave Barach | ffb14b9 | 2018-09-11 17:20:23 -0400 | [diff] [blame] | 236 | h->sh->buckets_as_u64 = (u64) BV (clib_bihash_get_offset) (h, h->buckets); |
Dave Barach | 9466c45 | 2018-08-24 17:21:14 -0400 | [diff] [blame] | 237 | |
| 238 | h->alloc_lock = BV (alloc_aligned) (h, CLIB_CACHE_LINE_BYTES); |
| 239 | h->alloc_lock[0] = 0; |
| 240 | |
Dave Barach | ffb14b9 | 2018-09-11 17:20:23 -0400 | [diff] [blame] | 241 | h->sh->alloc_lock_as_u64 = |
| 242 | (u64) BV (clib_bihash_get_offset) (h, (void *) h->alloc_lock); |
| 243 | freelist_vh = |
| 244 | BV (alloc_aligned) (h, |
| 245 | sizeof (vec_header_t) + |
| 246 | BIHASH_FREELIST_LENGTH * sizeof (u64)); |
Dave Barach | 9466c45 | 2018-08-24 17:21:14 -0400 | [diff] [blame] | 247 | freelist_vh->len = BIHASH_FREELIST_LENGTH; |
Dave Barach | ffb14b9 | 2018-09-11 17:20:23 -0400 | [diff] [blame] | 248 | h->sh->freelists_as_u64 = |
| 249 | (u64) BV (clib_bihash_get_offset) (h, freelist_vh->vector_data); |
| 250 | h->freelists = (void *) (freelist_vh->vector_data); |
Dave Barach | 9466c45 | 2018-08-24 17:21:14 -0400 | [diff] [blame] | 251 | |
| 252 | h->fmt_fn = NULL; |
Vijayabhaskar Katamreddy | f0bae64 | 2020-01-15 13:45:19 -0800 | [diff] [blame] | 253 | h->instantiated = 1; |
Dave Barach | 9466c45 | 2018-08-24 17:21:14 -0400 | [diff] [blame] | 254 | } |
| 255 | |
| 256 | void BV (clib_bihash_slave_init_svm) |
| 257 | (BVT (clib_bihash) * h, char *name, int fd) |
| 258 | { |
| 259 | u8 *mmap_addr; |
Dave Barach | ffb14b9 | 2018-09-11 17:20:23 -0400 | [diff] [blame] | 260 | u64 memory_size; |
Dave Barach | 9466c45 | 2018-08-24 17:21:14 -0400 | [diff] [blame] | 261 | BVT (clib_bihash_shared_header) * sh; |
| 262 | |
Dave Barach | ffb14b9 | 2018-09-11 17:20:23 -0400 | [diff] [blame] | 263 | /* Trial mapping, to learn the segment size */ |
Dave Barach | 9466c45 | 2018-08-24 17:21:14 -0400 | [diff] [blame] | 264 | mmap_addr = mmap (0, 4096, PROT_READ, MAP_SHARED, fd, 0 /* offset */ ); |
| 265 | if (mmap_addr == MAP_FAILED) |
| 266 | { |
| 267 | clib_unix_warning ("trial mmap failed"); |
| 268 | ASSERT (0); |
| 269 | } |
| 270 | |
| 271 | sh = (BVT (clib_bihash_shared_header) *) mmap_addr; |
| 272 | |
Dave Barach | 9466c45 | 2018-08-24 17:21:14 -0400 | [diff] [blame] | 273 | memory_size = sh->alloc_arena_size; |
| 274 | |
| 275 | munmap (mmap_addr, 4096); |
| 276 | |
Dave Barach | ffb14b9 | 2018-09-11 17:20:23 -0400 | [diff] [blame] | 277 | /* Actual mapping, at the required size */ |
| 278 | mmap_addr = mmap (0, memory_size, |
| 279 | PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0 /* offset */ ); |
Dave Barach | 9466c45 | 2018-08-24 17:21:14 -0400 | [diff] [blame] | 280 | |
| 281 | if (mmap_addr == MAP_FAILED) |
| 282 | { |
| 283 | clib_unix_warning ("mmap failed"); |
| 284 | ASSERT (0); |
| 285 | } |
| 286 | |
| 287 | (void) close (fd); |
| 288 | |
| 289 | h->sh = (void *) mmap_addr; |
Dave Barach | ffb14b9 | 2018-09-11 17:20:23 -0400 | [diff] [blame] | 290 | alloc_arena (h) = (u64) (uword) mmap_addr; |
Dave Barach | 9466c45 | 2018-08-24 17:21:14 -0400 | [diff] [blame] | 291 | h->memfd = -1; |
| 292 | |
| 293 | h->name = (u8 *) name; |
Dave Barach | ffb14b9 | 2018-09-11 17:20:23 -0400 | [diff] [blame] | 294 | h->buckets = BV (clib_bihash_get_value) (h, h->sh->buckets_as_u64); |
Dave Barach | 9466c45 | 2018-08-24 17:21:14 -0400 | [diff] [blame] | 295 | h->nbuckets = h->sh->nbuckets; |
| 296 | h->log2_nbuckets = max_log2 (h->nbuckets); |
| 297 | |
Dave Barach | ffb14b9 | 2018-09-11 17:20:23 -0400 | [diff] [blame] | 298 | h->alloc_lock = BV (clib_bihash_get_value) (h, h->sh->alloc_lock_as_u64); |
| 299 | h->freelists = BV (clib_bihash_get_value) (h, h->sh->freelists_as_u64); |
Dave Barach | 9466c45 | 2018-08-24 17:21:14 -0400 | [diff] [blame] | 300 | h->fmt_fn = NULL; |
| 301 | } |
| 302 | #endif /* BIHASH_32_64_SVM */ |
| 303 | |
Vijayabhaskar Katamreddy | fb8e61c | 2017-12-14 13:20:50 -0800 | [diff] [blame] | 304 | void BV (clib_bihash_set_kvp_format_fn) (BVT (clib_bihash) * h, |
| 305 | format_function_t * fmt_fn) |
| 306 | { |
| 307 | h->fmt_fn = fmt_fn; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 308 | } |
| 309 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 310 | void BV (clib_bihash_free) (BVT (clib_bihash) * h) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 311 | { |
Dave Barach | 32dcd3b | 2019-07-08 12:25:38 -0400 | [diff] [blame] | 312 | int i; |
| 313 | |
Dave Barach | 67d09e0 | 2019-08-01 08:15:01 -0400 | [diff] [blame] | 314 | if (PREDICT_FALSE (h->instantiated == 0)) |
Dave Barach | 32dcd3b | 2019-07-08 12:25:38 -0400 | [diff] [blame] | 315 | goto never_initialized; |
| 316 | |
Dave Barach | 67d09e0 | 2019-08-01 08:15:01 -0400 | [diff] [blame] | 317 | h->instantiated = 0; |
Dave Barach | 97f5af0 | 2018-02-22 09:48:45 -0500 | [diff] [blame] | 318 | vec_free (h->working_copies); |
Vijayabhaskar Katamreddy | 72739a6 | 2019-05-07 13:27:32 -0700 | [diff] [blame] | 319 | vec_free (h->working_copy_lengths); |
Dave Barach | 9466c45 | 2018-08-24 17:21:14 -0400 | [diff] [blame] | 320 | #if BIHASH_32_64_SVM == 0 |
Dave Barach | 97f5af0 | 2018-02-22 09:48:45 -0500 | [diff] [blame] | 321 | vec_free (h->freelists); |
Dave Barach | 9466c45 | 2018-08-24 17:21:14 -0400 | [diff] [blame] | 322 | #else |
| 323 | if (h->memfd > 0) |
| 324 | (void) close (h->memfd); |
| 325 | #endif |
| 326 | clib_mem_vm_free ((void *) (uword) (alloc_arena (h)), alloc_arena_size (h)); |
Dave Barach | 32dcd3b | 2019-07-08 12:25:38 -0400 | [diff] [blame] | 327 | never_initialized: |
Dave Barach | b7b9299 | 2018-10-17 10:38:51 -0400 | [diff] [blame] | 328 | clib_memset (h, 0, sizeof (*h)); |
Dave Barach | 32dcd3b | 2019-07-08 12:25:38 -0400 | [diff] [blame] | 329 | for (i = 0; i < vec_len (clib_all_bihashes); i++) |
| 330 | { |
| 331 | if ((void *) h == clib_all_bihashes[i]) |
| 332 | { |
| 333 | vec_delete (clib_all_bihashes, 1, i); |
| 334 | return; |
| 335 | } |
| 336 | } |
| 337 | clib_warning ("Couldn't find hash table %llx on clib_all_bihashes...", |
Vijayabhaskar Katamreddy | f0bae64 | 2020-01-15 13:45:19 -0800 | [diff] [blame] | 338 | (u64) (uword) h); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 339 | } |
| 340 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 341 | static |
| 342 | BVT (clib_bihash_value) * |
| 343 | BV (value_alloc) (BVT (clib_bihash) * h, u32 log2_pages) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 344 | { |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 345 | BVT (clib_bihash_value) * rv = 0; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 346 | |
Dave Barach | 508498f | 2018-07-19 12:11:16 -0400 | [diff] [blame] | 347 | ASSERT (h->alloc_lock[0]); |
Dave Barach | 9466c45 | 2018-08-24 17:21:14 -0400 | [diff] [blame] | 348 | |
| 349 | #if BIHASH_32_64_SVM |
| 350 | ASSERT (log2_pages < vec_len (h->freelists)); |
| 351 | #endif |
| 352 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 353 | if (log2_pages >= vec_len (h->freelists) || h->freelists[log2_pages] == 0) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 354 | { |
Dave Barach | 97f5af0 | 2018-02-22 09:48:45 -0500 | [diff] [blame] | 355 | vec_validate_init_empty (h->freelists, log2_pages, 0); |
| 356 | rv = BV (alloc_aligned) (h, (sizeof (*rv) * (1 << log2_pages))); |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 357 | goto initialize; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 358 | } |
Dave Barach | ffb14b9 | 2018-09-11 17:20:23 -0400 | [diff] [blame] | 359 | rv = BV (clib_bihash_get_value) (h, (uword) h->freelists[log2_pages]); |
Dave Barach | 9466c45 | 2018-08-24 17:21:14 -0400 | [diff] [blame] | 360 | h->freelists[log2_pages] = rv->next_free_as_u64; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 361 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 362 | initialize: |
| 363 | ASSERT (rv); |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 364 | /* |
| 365 | * Latest gcc complains that the length arg is zero |
| 366 | * if we replace (1<<log2_pages) with vec_len(rv). |
| 367 | * No clue. |
| 368 | */ |
Dave Barach | b7b9299 | 2018-10-17 10:38:51 -0400 | [diff] [blame] | 369 | clib_memset (rv, 0xff, sizeof (*rv) * (1 << log2_pages)); |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 370 | return rv; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 371 | } |
| 372 | |
| 373 | static void |
Dave Barach | ba7ddfe | 2017-05-17 20:20:50 -0400 | [diff] [blame] | 374 | BV (value_free) (BVT (clib_bihash) * h, BVT (clib_bihash_value) * v, |
| 375 | u32 log2_pages) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 376 | { |
Dave Barach | 508498f | 2018-07-19 12:11:16 -0400 | [diff] [blame] | 377 | ASSERT (h->alloc_lock[0]); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 378 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 379 | ASSERT (vec_len (h->freelists) > log2_pages); |
| 380 | |
Dave Barach | 508498f | 2018-07-19 12:11:16 -0400 | [diff] [blame] | 381 | if (CLIB_DEBUG > 0) |
Dave Barach | b7b9299 | 2018-10-17 10:38:51 -0400 | [diff] [blame] | 382 | clib_memset (v, 0xFE, sizeof (*v) * (1 << log2_pages)); |
Dave Barach | 508498f | 2018-07-19 12:11:16 -0400 | [diff] [blame] | 383 | |
Dave Barach | 9466c45 | 2018-08-24 17:21:14 -0400 | [diff] [blame] | 384 | v->next_free_as_u64 = (u64) h->freelists[log2_pages]; |
Dave Barach | ffb14b9 | 2018-09-11 17:20:23 -0400 | [diff] [blame] | 385 | h->freelists[log2_pages] = (u64) BV (clib_bihash_get_offset) (h, v); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 386 | } |
| 387 | |
| 388 | static inline void |
Dave Barach | 908a5ea | 2017-07-14 12:42:21 -0400 | [diff] [blame] | 389 | BV (make_working_copy) (BVT (clib_bihash) * h, BVT (clib_bihash_bucket) * b) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 390 | { |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 391 | BVT (clib_bihash_value) * v; |
Dave Barach | 908a5ea | 2017-07-14 12:42:21 -0400 | [diff] [blame] | 392 | BVT (clib_bihash_bucket) working_bucket __attribute__ ((aligned (8))); |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 393 | BVT (clib_bihash_value) * working_copy; |
Damjan Marion | f55f9b8 | 2017-05-10 21:06:28 +0200 | [diff] [blame] | 394 | u32 thread_index = os_get_thread_index (); |
Dave Barach | ba7ddfe | 2017-05-17 20:20:50 -0400 | [diff] [blame] | 395 | int log2_working_copy_length; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 396 | |
Dave Barach | 508498f | 2018-07-19 12:11:16 -0400 | [diff] [blame] | 397 | ASSERT (h->alloc_lock[0]); |
| 398 | |
Damjan Marion | f55f9b8 | 2017-05-10 21:06:28 +0200 | [diff] [blame] | 399 | if (thread_index >= vec_len (h->working_copies)) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 400 | { |
Damjan Marion | f55f9b8 | 2017-05-10 21:06:28 +0200 | [diff] [blame] | 401 | vec_validate (h->working_copies, thread_index); |
Steve Shin | 871cdec | 2017-06-02 10:09:02 -0700 | [diff] [blame] | 402 | vec_validate_init_empty (h->working_copy_lengths, thread_index, ~0); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 403 | } |
| 404 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 405 | /* |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 406 | * working_copies are per-cpu so that near-simultaneous |
| 407 | * updates from multiple threads will not result in sporadic, spurious |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 408 | * lookup failures. |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 409 | */ |
Damjan Marion | f55f9b8 | 2017-05-10 21:06:28 +0200 | [diff] [blame] | 410 | working_copy = h->working_copies[thread_index]; |
Dave Barach | ba7ddfe | 2017-05-17 20:20:50 -0400 | [diff] [blame] | 411 | log2_working_copy_length = h->working_copy_lengths[thread_index]; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 412 | |
| 413 | h->saved_bucket.as_u64 = b->as_u64; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 414 | |
Dave Barach | ba7ddfe | 2017-05-17 20:20:50 -0400 | [diff] [blame] | 415 | if (b->log2_pages > log2_working_copy_length) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 416 | { |
Dave Barach | 97f5af0 | 2018-02-22 09:48:45 -0500 | [diff] [blame] | 417 | /* |
| 418 | * It's not worth the bookkeeping to free working copies |
| 419 | * if (working_copy) |
| 420 | * clib_mem_free (working_copy); |
| 421 | */ |
| 422 | working_copy = BV (alloc_aligned) |
| 423 | (h, sizeof (working_copy[0]) * (1 << b->log2_pages)); |
Dave Barach | ba7ddfe | 2017-05-17 20:20:50 -0400 | [diff] [blame] | 424 | h->working_copy_lengths[thread_index] = b->log2_pages; |
Damjan Marion | f55f9b8 | 2017-05-10 21:06:28 +0200 | [diff] [blame] | 425 | h->working_copies[thread_index] = working_copy; |
Dave Barach | 2ce28d6 | 2019-05-03 12:58:01 -0400 | [diff] [blame] | 426 | |
| 427 | BV (clib_bihash_increment_stat) (h, BIHASH_STAT_working_copy_lost, |
| 428 | 1ULL << b->log2_pages); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 429 | } |
| 430 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 431 | v = BV (clib_bihash_get_value) (h, b->offset); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 432 | |
Dave Barach | 178cf49 | 2018-11-13 16:34:13 -0500 | [diff] [blame] | 433 | clib_memcpy_fast (working_copy, v, sizeof (*v) * (1 << b->log2_pages)); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 434 | working_bucket.as_u64 = b->as_u64; |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 435 | working_bucket.offset = BV (clib_bihash_get_offset) (h, working_copy); |
Damjan Marion | 801ec2a | 2020-04-21 19:42:30 +0200 | [diff] [blame] | 436 | CLIB_MEMORY_STORE_BARRIER (); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 437 | b->as_u64 = working_bucket.as_u64; |
Damjan Marion | f55f9b8 | 2017-05-10 21:06:28 +0200 | [diff] [blame] | 438 | h->working_copies[thread_index] = working_copy; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 439 | } |
| 440 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 441 | static |
| 442 | BVT (clib_bihash_value) * |
| 443 | BV (split_and_rehash) |
| 444 | (BVT (clib_bihash) * h, |
Dave Barach | ba7ddfe | 2017-05-17 20:20:50 -0400 | [diff] [blame] | 445 | BVT (clib_bihash_value) * old_values, u32 old_log2_pages, |
| 446 | u32 new_log2_pages) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 447 | { |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 448 | BVT (clib_bihash_value) * new_values, *new_v; |
Dave Barach | ba7ddfe | 2017-05-17 20:20:50 -0400 | [diff] [blame] | 449 | int i, j, length_in_kvs; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 450 | |
Dave Barach | 508498f | 2018-07-19 12:11:16 -0400 | [diff] [blame] | 451 | ASSERT (h->alloc_lock[0]); |
| 452 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 453 | new_values = BV (value_alloc) (h, new_log2_pages); |
Dave Barach | ba7ddfe | 2017-05-17 20:20:50 -0400 | [diff] [blame] | 454 | length_in_kvs = (1 << old_log2_pages) * BIHASH_KVP_PER_PAGE; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 455 | |
Dave Barach | ba7ddfe | 2017-05-17 20:20:50 -0400 | [diff] [blame] | 456 | for (i = 0; i < length_in_kvs; i++) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 457 | { |
| 458 | u64 new_hash; |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 459 | |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 460 | /* Entry not in use? Forget it */ |
| 461 | if (BV (clib_bihash_is_free) (&(old_values->kvp[i]))) |
| 462 | continue; |
| 463 | |
| 464 | /* rehash the item onto its new home-page */ |
| 465 | new_hash = BV (clib_bihash_hash) (&(old_values->kvp[i])); |
Damjan Marion | 68e5fd5 | 2020-04-23 13:41:47 +0200 | [diff] [blame] | 466 | new_hash = extract_bits (new_hash, h->log2_nbuckets, new_log2_pages); |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 467 | new_v = &new_values[new_hash]; |
| 468 | |
| 469 | /* Across the new home-page */ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 470 | for (j = 0; j < BIHASH_KVP_PER_PAGE; j++) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 471 | { |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 472 | /* Empty slot */ |
| 473 | if (BV (clib_bihash_is_free) (&(new_v->kvp[j]))) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 474 | { |
Dave Barach | 178cf49 | 2018-11-13 16:34:13 -0500 | [diff] [blame] | 475 | clib_memcpy_fast (&(new_v->kvp[j]), &(old_values->kvp[i]), |
| 476 | sizeof (new_v->kvp[j])); |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 477 | goto doublebreak; |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 478 | } |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 479 | } |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 480 | /* Crap. Tell caller to try again */ |
Dave Barach | ba7ddfe | 2017-05-17 20:20:50 -0400 | [diff] [blame] | 481 | BV (value_free) (h, new_values, new_log2_pages); |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 482 | return 0; |
| 483 | doublebreak:; |
| 484 | } |
Dave Barach | ba7ddfe | 2017-05-17 20:20:50 -0400 | [diff] [blame] | 485 | |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 486 | return new_values; |
| 487 | } |
| 488 | |
| 489 | static |
| 490 | BVT (clib_bihash_value) * |
| 491 | BV (split_and_rehash_linear) |
| 492 | (BVT (clib_bihash) * h, |
Dave Barach | ba7ddfe | 2017-05-17 20:20:50 -0400 | [diff] [blame] | 493 | BVT (clib_bihash_value) * old_values, u32 old_log2_pages, |
| 494 | u32 new_log2_pages) |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 495 | { |
| 496 | BVT (clib_bihash_value) * new_values; |
Dave Barach | ba7ddfe | 2017-05-17 20:20:50 -0400 | [diff] [blame] | 497 | int i, j, new_length, old_length; |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 498 | |
Dave Barach | 508498f | 2018-07-19 12:11:16 -0400 | [diff] [blame] | 499 | ASSERT (h->alloc_lock[0]); |
| 500 | |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 501 | new_values = BV (value_alloc) (h, new_log2_pages); |
| 502 | new_length = (1 << new_log2_pages) * BIHASH_KVP_PER_PAGE; |
Dave Barach | ba7ddfe | 2017-05-17 20:20:50 -0400 | [diff] [blame] | 503 | old_length = (1 << old_log2_pages) * BIHASH_KVP_PER_PAGE; |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 504 | |
| 505 | j = 0; |
| 506 | /* Across the old value array */ |
Dave Barach | ba7ddfe | 2017-05-17 20:20:50 -0400 | [diff] [blame] | 507 | for (i = 0; i < old_length; i++) |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 508 | { |
| 509 | /* Find a free slot in the new linear scan bucket */ |
| 510 | for (; j < new_length; j++) |
| 511 | { |
Dave Barach | 8f54496 | 2017-01-18 10:23:22 -0500 | [diff] [blame] | 512 | /* Old value not in use? Forget it. */ |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 513 | if (BV (clib_bihash_is_free) (&(old_values->kvp[i]))) |
| 514 | goto doublebreak; |
| 515 | |
| 516 | /* New value should never be in use */ |
| 517 | if (BV (clib_bihash_is_free) (&(new_values->kvp[j]))) |
| 518 | { |
| 519 | /* Copy the old value and move along */ |
Dave Barach | 178cf49 | 2018-11-13 16:34:13 -0500 | [diff] [blame] | 520 | clib_memcpy_fast (&(new_values->kvp[j]), &(old_values->kvp[i]), |
| 521 | sizeof (new_values->kvp[j])); |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 522 | j++; |
| 523 | goto doublebreak; |
| 524 | } |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 525 | } |
Dave Barach | 8f54496 | 2017-01-18 10:23:22 -0500 | [diff] [blame] | 526 | /* This should never happen... */ |
| 527 | clib_warning ("BUG: linear rehash failed!"); |
Dave Barach | ba7ddfe | 2017-05-17 20:20:50 -0400 | [diff] [blame] | 528 | BV (value_free) (h, new_values, new_log2_pages); |
Dave Barach | 8f54496 | 2017-01-18 10:23:22 -0500 | [diff] [blame] | 529 | return 0; |
| 530 | |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 531 | doublebreak:; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 532 | } |
| 533 | return new_values; |
| 534 | } |
| 535 | |
Damjan Marion | 801ec2a | 2020-04-21 19:42:30 +0200 | [diff] [blame] | 536 | static_always_inline int BV (clib_bihash_add_del_inline_with_hash) |
| 537 | (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, u64 hash, int is_add, |
Matus Fabian | 828d27e | 2018-08-21 03:15:50 -0700 | [diff] [blame] | 538 | int (*is_stale_cb) (BVT (clib_bihash_kv) *, void *), void *arg) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 539 | { |
Dave Barach | 908a5ea | 2017-07-14 12:42:21 -0400 | [diff] [blame] | 540 | BVT (clib_bihash_bucket) * b, tmp_b; |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 541 | BVT (clib_bihash_value) * v, *new_v, *save_new_v, *working_copy; |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 542 | int i, limit; |
Damjan Marion | 801ec2a | 2020-04-21 19:42:30 +0200 | [diff] [blame] | 543 | u64 new_hash; |
Dave Barach | ba7ddfe | 2017-05-17 20:20:50 -0400 | [diff] [blame] | 544 | u32 new_log2_pages, old_log2_pages; |
Damjan Marion | f55f9b8 | 2017-05-10 21:06:28 +0200 | [diff] [blame] | 545 | u32 thread_index = os_get_thread_index (); |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 546 | int mark_bucket_linear; |
| 547 | int resplit_once; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 548 | |
Damjan Marion | 68e5fd5 | 2020-04-23 13:41:47 +0200 | [diff] [blame] | 549 | /* *INDENT-OFF* */ |
| 550 | static const BVT (clib_bihash_bucket) mask = { |
| 551 | .linear_search = 1, |
| 552 | .log2_pages = -1 |
| 553 | }; |
| 554 | /* *INDENT-ON* */ |
| 555 | |
| 556 | #if BIHASH_LAZY_INSTANTIATE |
Dave Barach | 67d09e0 | 2019-08-01 08:15:01 -0400 | [diff] [blame] | 557 | /* |
| 558 | * Create the table (is_add=1,2), or flunk the request now (is_add=0) |
| 559 | * Use the alloc_lock to protect the instantiate operation. |
| 560 | */ |
| 561 | if (PREDICT_FALSE (h->instantiated == 0)) |
Dave Barach | 32dcd3b | 2019-07-08 12:25:38 -0400 | [diff] [blame] | 562 | { |
| 563 | if (is_add == 0) |
| 564 | return (-1); |
Dave Barach | 67d09e0 | 2019-08-01 08:15:01 -0400 | [diff] [blame] | 565 | |
| 566 | BV (clib_bihash_alloc_lock) (h); |
| 567 | if (h->instantiated == 0) |
| 568 | BV (clib_bihash_instantiate) (h); |
| 569 | BV (clib_bihash_alloc_unlock) (h); |
Dave Barach | 32dcd3b | 2019-07-08 12:25:38 -0400 | [diff] [blame] | 570 | } |
Dave Barach | a90ba64 | 2020-04-23 16:56:15 -0400 | [diff] [blame] | 571 | #else |
| 572 | /* Debug image: make sure the table has been instantiated */ |
| 573 | ASSERT (h->instantiated != 0); |
Damjan Marion | 68e5fd5 | 2020-04-23 13:41:47 +0200 | [diff] [blame] | 574 | #endif |
Dave Barach | 32dcd3b | 2019-07-08 12:25:38 -0400 | [diff] [blame] | 575 | |
Damjan Marion | 4e14977 | 2020-03-27 16:57:28 +0100 | [diff] [blame] | 576 | b = BV (clib_bihash_get_bucket) (h, hash); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 577 | |
Dave Barach | 508498f | 2018-07-19 12:11:16 -0400 | [diff] [blame] | 578 | BV (clib_bihash_lock_bucket) (b); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 579 | |
| 580 | /* First elt in the bucket? */ |
Dave Barach | 16e4a4a | 2020-04-16 12:00:14 -0400 | [diff] [blame] | 581 | if (BIHASH_KVP_AT_BUCKET_LEVEL == 0 && BV (clib_bihash_bucket_is_empty) (b)) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 582 | { |
| 583 | if (is_add == 0) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 584 | { |
Dave Barach | 508498f | 2018-07-19 12:11:16 -0400 | [diff] [blame] | 585 | BV (clib_bihash_unlock_bucket) (b); |
| 586 | return (-1); |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 587 | } |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 588 | |
Dave Barach | 508498f | 2018-07-19 12:11:16 -0400 | [diff] [blame] | 589 | BV (clib_bihash_alloc_lock) (h); |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 590 | v = BV (value_alloc) (h, 0); |
Dave Barach | 508498f | 2018-07-19 12:11:16 -0400 | [diff] [blame] | 591 | BV (clib_bihash_alloc_unlock) (h); |
Dave Barach | ba7ddfe | 2017-05-17 20:20:50 -0400 | [diff] [blame] | 592 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 593 | *v->kvp = *add_v; |
Dave Barach | 508498f | 2018-07-19 12:11:16 -0400 | [diff] [blame] | 594 | tmp_b.as_u64 = 0; /* clears bucket lock */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 595 | tmp_b.offset = BV (clib_bihash_get_offset) (h, v); |
Dave Barach | e7d212f | 2018-02-07 13:14:06 -0500 | [diff] [blame] | 596 | tmp_b.refcnt = 1; |
Damjan Marion | 801ec2a | 2020-04-21 19:42:30 +0200 | [diff] [blame] | 597 | CLIB_MEMORY_STORE_BARRIER (); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 598 | |
Tom Seidenberg | 97f8ae9 | 2019-03-15 10:15:26 -0400 | [diff] [blame] | 599 | b->as_u64 = tmp_b.as_u64; /* unlocks the bucket */ |
Dave Barach | 2ce28d6 | 2019-05-03 12:58:01 -0400 | [diff] [blame] | 600 | BV (clib_bihash_increment_stat) (h, BIHASH_STAT_alloc_add, 1); |
| 601 | |
Dave Barach | 508498f | 2018-07-19 12:11:16 -0400 | [diff] [blame] | 602 | return (0); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 603 | } |
| 604 | |
Dave Barach | 508498f | 2018-07-19 12:11:16 -0400 | [diff] [blame] | 605 | /* WARNING: we're still looking at the live copy... */ |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 606 | limit = BIHASH_KVP_PER_PAGE; |
Dave Barach | 508498f | 2018-07-19 12:11:16 -0400 | [diff] [blame] | 607 | v = BV (clib_bihash_get_value) (h, b->offset); |
| 608 | |
Damjan Marion | 68e5fd5 | 2020-04-23 13:41:47 +0200 | [diff] [blame] | 609 | if (PREDICT_FALSE (b->as_u64 & mask.as_u64)) |
| 610 | { |
| 611 | if (PREDICT_FALSE (b->linear_search)) |
| 612 | limit <<= b->log2_pages; |
| 613 | else |
| 614 | v += extract_bits (hash, h->log2_nbuckets, b->log2_pages); |
| 615 | } |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 616 | |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 617 | if (is_add) |
| 618 | { |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 619 | /* |
Dave Barach | 508498f | 2018-07-19 12:11:16 -0400 | [diff] [blame] | 620 | * Because reader threads are looking at live data, |
| 621 | * we have to be extra careful. Readers do NOT hold the |
| 622 | * bucket lock. We need to be SLOWER than a search, past the |
| 623 | * point where readers CHECK the bucket lock. |
| 624 | */ |
| 625 | |
| 626 | /* |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 627 | * For obvious (in hindsight) reasons, see if we're supposed to |
| 628 | * replace an existing key, then look for an empty slot. |
| 629 | */ |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 630 | for (i = 0; i < limit; i++) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 631 | { |
Dave Barach | a11bf45 | 2019-04-17 17:27:31 -0400 | [diff] [blame] | 632 | if (BV (clib_bihash_key_compare) (v->kvp[i].key, add_v->key)) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 633 | { |
Dave Barach | 9e4946b | 2019-07-08 14:47:44 -0400 | [diff] [blame] | 634 | /* Add but do not overwrite? */ |
| 635 | if (is_add == 2) |
| 636 | { |
| 637 | BV (clib_bihash_unlock_bucket) (b); |
| 638 | return (-2); |
| 639 | } |
| 640 | |
Damjan Marion | 801ec2a | 2020-04-21 19:42:30 +0200 | [diff] [blame] | 641 | clib_memcpy_fast (&(v->kvp[i].value), |
| 642 | &add_v->value, sizeof (add_v->value)); |
Dave Barach | 508498f | 2018-07-19 12:11:16 -0400 | [diff] [blame] | 643 | BV (clib_bihash_unlock_bucket) (b); |
Dave Barach | 2ce28d6 | 2019-05-03 12:58:01 -0400 | [diff] [blame] | 644 | BV (clib_bihash_increment_stat) (h, BIHASH_STAT_replace, 1); |
Dave Barach | 508498f | 2018-07-19 12:11:16 -0400 | [diff] [blame] | 645 | return (0); |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 646 | } |
| 647 | } |
Dave Barach | 508498f | 2018-07-19 12:11:16 -0400 | [diff] [blame] | 648 | /* |
| 649 | * Look for an empty slot. If found, use it |
| 650 | */ |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 651 | for (i = 0; i < limit; i++) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 652 | { |
| 653 | if (BV (clib_bihash_is_free) (&(v->kvp[i]))) |
| 654 | { |
Dave Barach | 508498f | 2018-07-19 12:11:16 -0400 | [diff] [blame] | 655 | /* |
| 656 | * Copy the value first, so that if a reader manages |
| 657 | * to match the new key, the value will be right... |
| 658 | */ |
Dave Barach | 178cf49 | 2018-11-13 16:34:13 -0500 | [diff] [blame] | 659 | clib_memcpy_fast (&(v->kvp[i].value), |
| 660 | &add_v->value, sizeof (add_v->value)); |
Damjan Marion | 801ec2a | 2020-04-21 19:42:30 +0200 | [diff] [blame] | 661 | CLIB_MEMORY_STORE_BARRIER (); /* Make sure the value has settled */ |
Dave Barach | 178cf49 | 2018-11-13 16:34:13 -0500 | [diff] [blame] | 662 | clib_memcpy_fast (&(v->kvp[i]), &add_v->key, |
| 663 | sizeof (add_v->key)); |
Dave Barach | e7d212f | 2018-02-07 13:14:06 -0500 | [diff] [blame] | 664 | b->refcnt++; |
Dave Barach | 9466c45 | 2018-08-24 17:21:14 -0400 | [diff] [blame] | 665 | ASSERT (b->refcnt > 0); |
Dave Barach | 508498f | 2018-07-19 12:11:16 -0400 | [diff] [blame] | 666 | BV (clib_bihash_unlock_bucket) (b); |
Dave Barach | 2ce28d6 | 2019-05-03 12:58:01 -0400 | [diff] [blame] | 667 | BV (clib_bihash_increment_stat) (h, BIHASH_STAT_add, 1); |
Dave Barach | 508498f | 2018-07-19 12:11:16 -0400 | [diff] [blame] | 668 | return (0); |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 669 | } |
| 670 | } |
Matus Fabian | 828d27e | 2018-08-21 03:15:50 -0700 | [diff] [blame] | 671 | /* look for stale data to overwrite */ |
| 672 | if (is_stale_cb) |
| 673 | { |
| 674 | for (i = 0; i < limit; i++) |
| 675 | { |
| 676 | if (is_stale_cb (&(v->kvp[i]), arg)) |
| 677 | { |
Dave Barach | 178cf49 | 2018-11-13 16:34:13 -0500 | [diff] [blame] | 678 | clib_memcpy_fast (&(v->kvp[i]), add_v, sizeof (*add_v)); |
Damjan Marion | 801ec2a | 2020-04-21 19:42:30 +0200 | [diff] [blame] | 679 | CLIB_MEMORY_STORE_BARRIER (); |
Matus Fabian | 828d27e | 2018-08-21 03:15:50 -0700 | [diff] [blame] | 680 | BV (clib_bihash_unlock_bucket) (b); |
Dave Barach | 2ce28d6 | 2019-05-03 12:58:01 -0400 | [diff] [blame] | 681 | BV (clib_bihash_increment_stat) (h, BIHASH_STAT_replace, 1); |
Matus Fabian | 828d27e | 2018-08-21 03:15:50 -0700 | [diff] [blame] | 682 | return (0); |
| 683 | } |
| 684 | } |
| 685 | } |
Dave Barach | 508498f | 2018-07-19 12:11:16 -0400 | [diff] [blame] | 686 | /* Out of space in this bucket, split the bucket... */ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 687 | } |
Dave Barach | 508498f | 2018-07-19 12:11:16 -0400 | [diff] [blame] | 688 | else /* delete case */ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 689 | { |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 690 | for (i = 0; i < limit; i++) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 691 | { |
Dave Barach | 508498f | 2018-07-19 12:11:16 -0400 | [diff] [blame] | 692 | /* Found the key? Kill it... */ |
Dave Barach | a11bf45 | 2019-04-17 17:27:31 -0400 | [diff] [blame] | 693 | if (BV (clib_bihash_key_compare) (v->kvp[i].key, add_v->key)) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 694 | { |
Damjan Marion | 801ec2a | 2020-04-21 19:42:30 +0200 | [diff] [blame] | 695 | clib_memset_u8 (&(v->kvp[i]), 0xff, sizeof (*(add_v))); |
Dave Barach | 508498f | 2018-07-19 12:11:16 -0400 | [diff] [blame] | 696 | /* Is the bucket empty? */ |
| 697 | if (PREDICT_TRUE (b->refcnt > 1)) |
Dave Barach | e7d212f | 2018-02-07 13:14:06 -0500 | [diff] [blame] | 698 | { |
Dave Barach | 508498f | 2018-07-19 12:11:16 -0400 | [diff] [blame] | 699 | b->refcnt--; |
Dave Barach | 16e4a4a | 2020-04-16 12:00:14 -0400 | [diff] [blame] | 700 | /* Switch back to the bucket-level kvp array? */ |
| 701 | if (BIHASH_KVP_AT_BUCKET_LEVEL && b->refcnt == 1 |
| 702 | && b->log2_pages > 0) |
| 703 | { |
| 704 | tmp_b.as_u64 = b->as_u64; |
| 705 | b->offset = BV (clib_bihash_get_offset) |
| 706 | (h, (void *) (b + 1)); |
| 707 | b->linear_search = 0; |
| 708 | b->log2_pages = 0; |
| 709 | /* Clean up the bucket-level kvp array */ |
Damjan Marion | 801ec2a | 2020-04-21 19:42:30 +0200 | [diff] [blame] | 710 | clib_memset_u8 ((b + 1), 0xff, BIHASH_KVP_PER_PAGE * |
| 711 | sizeof (BVT (clib_bihash_kv))); |
| 712 | CLIB_MEMORY_STORE_BARRIER (); |
Dave Barach | 16e4a4a | 2020-04-16 12:00:14 -0400 | [diff] [blame] | 713 | BV (clib_bihash_unlock_bucket) (b); |
| 714 | BV (clib_bihash_increment_stat) (h, BIHASH_STAT_del, 1); |
| 715 | goto free_backing_store; |
| 716 | } |
| 717 | |
Damjan Marion | 801ec2a | 2020-04-21 19:42:30 +0200 | [diff] [blame] | 718 | CLIB_MEMORY_STORE_BARRIER (); |
Dave Barach | 508498f | 2018-07-19 12:11:16 -0400 | [diff] [blame] | 719 | BV (clib_bihash_unlock_bucket) (b); |
Dave Barach | 2ce28d6 | 2019-05-03 12:58:01 -0400 | [diff] [blame] | 720 | BV (clib_bihash_increment_stat) (h, BIHASH_STAT_del, 1); |
Dave Barach | 508498f | 2018-07-19 12:11:16 -0400 | [diff] [blame] | 721 | return (0); |
Dave Barach | e7d212f | 2018-02-07 13:14:06 -0500 | [diff] [blame] | 722 | } |
Dave Barach | 508498f | 2018-07-19 12:11:16 -0400 | [diff] [blame] | 723 | else /* yes, free it */ |
Dave Barach | e7d212f | 2018-02-07 13:14:06 -0500 | [diff] [blame] | 724 | { |
Dave Barach | 508498f | 2018-07-19 12:11:16 -0400 | [diff] [blame] | 725 | /* Save old bucket value, need log2_pages to free it */ |
| 726 | tmp_b.as_u64 = b->as_u64; |
Dave Barach | 508498f | 2018-07-19 12:11:16 -0400 | [diff] [blame] | 727 | |
| 728 | /* Kill and unlock the bucket */ |
| 729 | b->as_u64 = 0; |
| 730 | |
Dave Barach | 16e4a4a | 2020-04-16 12:00:14 -0400 | [diff] [blame] | 731 | free_backing_store: |
Dave Barach | 508498f | 2018-07-19 12:11:16 -0400 | [diff] [blame] | 732 | /* And free the backing storage */ |
| 733 | BV (clib_bihash_alloc_lock) (h); |
| 734 | /* Note: v currently points into the middle of the bucket */ |
| 735 | v = BV (clib_bihash_get_value) (h, tmp_b.offset); |
| 736 | BV (value_free) (h, v, tmp_b.log2_pages); |
| 737 | BV (clib_bihash_alloc_unlock) (h); |
Dave Barach | 2ce28d6 | 2019-05-03 12:58:01 -0400 | [diff] [blame] | 738 | BV (clib_bihash_increment_stat) (h, BIHASH_STAT_del_free, |
| 739 | 1); |
Dave Barach | 508498f | 2018-07-19 12:11:16 -0400 | [diff] [blame] | 740 | return (0); |
Dave Barach | e7d212f | 2018-02-07 13:14:06 -0500 | [diff] [blame] | 741 | } |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 742 | } |
| 743 | } |
Dave Barach | 508498f | 2018-07-19 12:11:16 -0400 | [diff] [blame] | 744 | /* Not found... */ |
| 745 | BV (clib_bihash_unlock_bucket) (b); |
| 746 | return (-3); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 747 | } |
| 748 | |
Dave Barach | 508498f | 2018-07-19 12:11:16 -0400 | [diff] [blame] | 749 | /* Move readers to a (locked) temp copy of the bucket */ |
| 750 | BV (clib_bihash_alloc_lock) (h); |
| 751 | BV (make_working_copy) (h, b); |
| 752 | |
| 753 | v = BV (clib_bihash_get_value) (h, h->saved_bucket.offset); |
| 754 | |
Dave Barach | ba7ddfe | 2017-05-17 20:20:50 -0400 | [diff] [blame] | 755 | old_log2_pages = h->saved_bucket.log2_pages; |
| 756 | new_log2_pages = old_log2_pages + 1; |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 757 | mark_bucket_linear = 0; |
Dave Barach | 2ce28d6 | 2019-05-03 12:58:01 -0400 | [diff] [blame] | 758 | BV (clib_bihash_increment_stat) (h, BIHASH_STAT_split_add, 1); |
| 759 | BV (clib_bihash_increment_stat) (h, BIHASH_STAT_splits, old_log2_pages); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 760 | |
Damjan Marion | f55f9b8 | 2017-05-10 21:06:28 +0200 | [diff] [blame] | 761 | working_copy = h->working_copies[thread_index]; |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 762 | resplit_once = 0; |
Dave Barach | 2ce28d6 | 2019-05-03 12:58:01 -0400 | [diff] [blame] | 763 | BV (clib_bihash_increment_stat) (h, BIHASH_STAT_splits, 1); |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 764 | |
Dave Barach | ba7ddfe | 2017-05-17 20:20:50 -0400 | [diff] [blame] | 765 | new_v = BV (split_and_rehash) (h, working_copy, old_log2_pages, |
| 766 | new_log2_pages); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 767 | if (new_v == 0) |
| 768 | { |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 769 | try_resplit: |
| 770 | resplit_once = 1; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 771 | new_log2_pages++; |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 772 | /* Try re-splitting. If that fails, fall back to linear search */ |
Dave Barach | ba7ddfe | 2017-05-17 20:20:50 -0400 | [diff] [blame] | 773 | new_v = BV (split_and_rehash) (h, working_copy, old_log2_pages, |
| 774 | new_log2_pages); |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 775 | if (new_v == 0) |
| 776 | { |
| 777 | mark_linear: |
| 778 | new_log2_pages--; |
| 779 | /* pinned collisions, use linear search */ |
| 780 | new_v = |
Dave Barach | ba7ddfe | 2017-05-17 20:20:50 -0400 | [diff] [blame] | 781 | BV (split_and_rehash_linear) (h, working_copy, old_log2_pages, |
| 782 | new_log2_pages); |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 783 | mark_bucket_linear = 1; |
Dave Barach | 2ce28d6 | 2019-05-03 12:58:01 -0400 | [diff] [blame] | 784 | BV (clib_bihash_increment_stat) (h, BIHASH_STAT_linear, 1); |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 785 | } |
Dave Barach | 2ce28d6 | 2019-05-03 12:58:01 -0400 | [diff] [blame] | 786 | BV (clib_bihash_increment_stat) (h, BIHASH_STAT_resplit, 1); |
| 787 | BV (clib_bihash_increment_stat) (h, BIHASH_STAT_splits, |
| 788 | old_log2_pages + 1); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 789 | } |
| 790 | |
| 791 | /* Try to add the new entry */ |
| 792 | save_new_v = new_v; |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 793 | new_hash = BV (clib_bihash_hash) (add_v); |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 794 | limit = BIHASH_KVP_PER_PAGE; |
| 795 | if (mark_bucket_linear) |
| 796 | limit <<= new_log2_pages; |
Damjan Marion | 68e5fd5 | 2020-04-23 13:41:47 +0200 | [diff] [blame] | 797 | else |
| 798 | new_v += extract_bits (new_hash, h->log2_nbuckets, new_log2_pages); |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 799 | |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 800 | for (i = 0; i < limit; i++) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 801 | { |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 802 | if (BV (clib_bihash_is_free) (&(new_v->kvp[i]))) |
| 803 | { |
Dave Barach | 178cf49 | 2018-11-13 16:34:13 -0500 | [diff] [blame] | 804 | clib_memcpy_fast (&(new_v->kvp[i]), add_v, sizeof (*add_v)); |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 805 | goto expand_ok; |
| 806 | } |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 807 | } |
Dave Barach | ba7ddfe | 2017-05-17 20:20:50 -0400 | [diff] [blame] | 808 | |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 809 | /* Crap. Try again */ |
Dave Barach | ba7ddfe | 2017-05-17 20:20:50 -0400 | [diff] [blame] | 810 | BV (value_free) (h, save_new_v, new_log2_pages); |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 811 | /* |
| 812 | * If we've already doubled the size of the bucket once, |
| 813 | * fall back to linear search now. |
| 814 | */ |
| 815 | if (resplit_once) |
| 816 | goto mark_linear; |
| 817 | else |
| 818 | goto try_resplit; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 819 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 820 | expand_ok: |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 821 | tmp_b.log2_pages = new_log2_pages; |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 822 | tmp_b.offset = BV (clib_bihash_get_offset) (h, save_new_v); |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 823 | tmp_b.linear_search = mark_bucket_linear; |
Dave Barach | 16e4a4a | 2020-04-16 12:00:14 -0400 | [diff] [blame] | 824 | #if BIHASH_KVP_AT_BUCKET_LEVEL |
| 825 | /* Compensate for permanent refcount bump at the bucket level */ |
| 826 | if (new_log2_pages > 0) |
| 827 | #endif |
| 828 | tmp_b.refcnt = h->saved_bucket.refcnt + 1; |
Dave Barach | 9466c45 | 2018-08-24 17:21:14 -0400 | [diff] [blame] | 829 | ASSERT (tmp_b.refcnt > 0); |
Dave Barach | 508498f | 2018-07-19 12:11:16 -0400 | [diff] [blame] | 830 | tmp_b.lock = 0; |
Damjan Marion | 801ec2a | 2020-04-21 19:42:30 +0200 | [diff] [blame] | 831 | CLIB_MEMORY_STORE_BARRIER (); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 832 | b->as_u64 = tmp_b.as_u64; |
Dave Barach | 16e4a4a | 2020-04-16 12:00:14 -0400 | [diff] [blame] | 833 | |
| 834 | #if BIHASH_KVP_AT_BUCKET_LEVEL |
| 835 | if (h->saved_bucket.log2_pages > 0) |
| 836 | { |
| 837 | #endif |
| 838 | |
| 839 | /* free the old bucket, except at the bucket level if so configured */ |
| 840 | v = BV (clib_bihash_get_value) (h, h->saved_bucket.offset); |
| 841 | BV (value_free) (h, v, h->saved_bucket.log2_pages); |
| 842 | |
| 843 | #if BIHASH_KVP_AT_BUCKET_LEVEL |
| 844 | } |
| 845 | #endif |
| 846 | |
| 847 | |
Dave Barach | 508498f | 2018-07-19 12:11:16 -0400 | [diff] [blame] | 848 | BV (clib_bihash_alloc_unlock) (h); |
| 849 | return (0); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 850 | } |
| 851 | |
Damjan Marion | 801ec2a | 2020-04-21 19:42:30 +0200 | [diff] [blame] | 852 | static_always_inline int BV (clib_bihash_add_del_inline) |
| 853 | (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, int is_add, |
| 854 | int (*is_stale_cb) (BVT (clib_bihash_kv) *, void *), void *arg) |
| 855 | { |
| 856 | u64 hash = BV (clib_bihash_hash) (add_v); |
| 857 | return BV (clib_bihash_add_del_inline_with_hash) (h, add_v, hash, is_add, |
| 858 | is_stale_cb, arg); |
| 859 | } |
| 860 | |
Matus Fabian | 828d27e | 2018-08-21 03:15:50 -0700 | [diff] [blame] | 861 | int BV (clib_bihash_add_del) |
| 862 | (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, int is_add) |
| 863 | { |
| 864 | return BV (clib_bihash_add_del_inline) (h, add_v, is_add, 0, 0); |
| 865 | } |
| 866 | |
| 867 | int BV (clib_bihash_add_or_overwrite_stale) |
| 868 | (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, |
| 869 | int (*stale_callback) (BVT (clib_bihash_kv) *, void *), void *arg) |
| 870 | { |
| 871 | return BV (clib_bihash_add_del_inline) (h, add_v, 1, stale_callback, arg); |
| 872 | } |
| 873 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 874 | int BV (clib_bihash_search) |
Dave Barach | 908a5ea | 2017-07-14 12:42:21 -0400 | [diff] [blame] | 875 | (BVT (clib_bihash) * h, |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 876 | BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 877 | { |
Damjan Marion | 68e5fd5 | 2020-04-23 13:41:47 +0200 | [diff] [blame] | 878 | return BV (clib_bihash_search_inline_2) (h, search_key, valuep); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 879 | } |
| 880 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 881 | u8 *BV (format_bihash) (u8 * s, va_list * args) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 882 | { |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 883 | BVT (clib_bihash) * h = va_arg (*args, BVT (clib_bihash) *); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 884 | int verbose = va_arg (*args, int); |
Dave Barach | 908a5ea | 2017-07-14 12:42:21 -0400 | [diff] [blame] | 885 | BVT (clib_bihash_bucket) * b; |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 886 | BVT (clib_bihash_value) * v; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 887 | int i, j, k; |
| 888 | u64 active_elements = 0; |
Dave Barach | e7d212f | 2018-02-07 13:14:06 -0500 | [diff] [blame] | 889 | u64 active_buckets = 0; |
| 890 | u64 linear_buckets = 0; |
Dave Barach | 97f5af0 | 2018-02-22 09:48:45 -0500 | [diff] [blame] | 891 | u64 used_bytes; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 892 | |
| 893 | s = format (s, "Hash table %s\n", h->name ? h->name : (u8 *) "(unnamed)"); |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 894 | |
Dave Barach | 16e4a4a | 2020-04-16 12:00:14 -0400 | [diff] [blame] | 895 | #if BIHASH_LAZY_INSTANTIATE |
Dave Barach | 32dcd3b | 2019-07-08 12:25:38 -0400 | [diff] [blame] | 896 | if (PREDICT_FALSE (alloc_arena (h) == 0)) |
| 897 | return format (s, "[empty, uninitialized]"); |
Dave Barach | 16e4a4a | 2020-04-16 12:00:14 -0400 | [diff] [blame] | 898 | #endif |
Dave Barach | 32dcd3b | 2019-07-08 12:25:38 -0400 | [diff] [blame] | 899 | |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 900 | for (i = 0; i < h->nbuckets; i++) |
| 901 | { |
Dave Barach | 16e4a4a | 2020-04-16 12:00:14 -0400 | [diff] [blame] | 902 | b = BV (clib_bihash_get_bucket) (h, i); |
Damjan Marion | 882fcfe | 2018-07-17 23:01:49 +0200 | [diff] [blame] | 903 | if (BV (clib_bihash_bucket_is_empty) (b)) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 904 | { |
| 905 | if (verbose > 1) |
| 906 | s = format (s, "[%d]: empty\n", i); |
| 907 | continue; |
| 908 | } |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 909 | |
Dave Barach | e7d212f | 2018-02-07 13:14:06 -0500 | [diff] [blame] | 910 | active_buckets++; |
| 911 | |
| 912 | if (b->linear_search) |
| 913 | linear_buckets++; |
| 914 | |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 915 | if (verbose) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 916 | { |
Dave Barach | 16e4a4a | 2020-04-16 12:00:14 -0400 | [diff] [blame] | 917 | s = format |
| 918 | (s, "[%d]: heap offset %lld, len %d, refcnt %d, linear %d\n", i, |
| 919 | b->offset, (1 << b->log2_pages), b->refcnt, b->linear_search); |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 920 | } |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 921 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 922 | v = BV (clib_bihash_get_value) (h, b->offset); |
| 923 | for (j = 0; j < (1 << b->log2_pages); j++) |
| 924 | { |
| 925 | for (k = 0; k < BIHASH_KVP_PER_PAGE; k++) |
| 926 | { |
| 927 | if (BV (clib_bihash_is_free) (&v->kvp[k])) |
| 928 | { |
| 929 | if (verbose > 1) |
| 930 | s = format (s, " %d: empty\n", |
| 931 | j * BIHASH_KVP_PER_PAGE + k); |
| 932 | continue; |
| 933 | } |
| 934 | if (verbose) |
| 935 | { |
Vijayabhaskar Katamreddy | fb8e61c | 2017-12-14 13:20:50 -0800 | [diff] [blame] | 936 | if (h->fmt_fn) |
| 937 | { |
| 938 | s = format (s, " %d: %U\n", |
| 939 | j * BIHASH_KVP_PER_PAGE + k, |
Vijayabhaskar Katamreddy | 72739a6 | 2019-05-07 13:27:32 -0700 | [diff] [blame] | 940 | h->fmt_fn, &(v->kvp[k]), verbose); |
Vijayabhaskar Katamreddy | fb8e61c | 2017-12-14 13:20:50 -0800 | [diff] [blame] | 941 | } |
| 942 | else |
| 943 | { |
| 944 | s = format (s, " %d: %U\n", |
| 945 | j * BIHASH_KVP_PER_PAGE + k, |
| 946 | BV (format_bihash_kvp), &(v->kvp[k])); |
| 947 | } |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 948 | } |
| 949 | active_elements++; |
| 950 | } |
| 951 | v++; |
| 952 | } |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 953 | } |
| 954 | |
Dave Barach | e7d212f | 2018-02-07 13:14:06 -0500 | [diff] [blame] | 955 | s = format (s, " %lld active elements %lld active buckets\n", |
| 956 | active_elements, active_buckets); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 957 | s = format (s, " %d free lists\n", vec_len (h->freelists)); |
Dave Barach | e7d212f | 2018-02-07 13:14:06 -0500 | [diff] [blame] | 958 | |
| 959 | for (i = 0; i < vec_len (h->freelists); i++) |
| 960 | { |
| 961 | u32 nfree = 0; |
| 962 | BVT (clib_bihash_value) * free_elt; |
Dave Barach | ffb14b9 | 2018-09-11 17:20:23 -0400 | [diff] [blame] | 963 | u64 free_elt_as_u64 = h->freelists[i]; |
Dave Barach | e7d212f | 2018-02-07 13:14:06 -0500 | [diff] [blame] | 964 | |
Dave Barach | ffb14b9 | 2018-09-11 17:20:23 -0400 | [diff] [blame] | 965 | while (free_elt_as_u64) |
Dave Barach | e7d212f | 2018-02-07 13:14:06 -0500 | [diff] [blame] | 966 | { |
Dave Barach | ffb14b9 | 2018-09-11 17:20:23 -0400 | [diff] [blame] | 967 | free_elt = BV (clib_bihash_get_value) (h, free_elt_as_u64); |
Dave Barach | e7d212f | 2018-02-07 13:14:06 -0500 | [diff] [blame] | 968 | nfree++; |
Dave Barach | ffb14b9 | 2018-09-11 17:20:23 -0400 | [diff] [blame] | 969 | free_elt_as_u64 = free_elt->next_free_as_u64; |
Dave Barach | e7d212f | 2018-02-07 13:14:06 -0500 | [diff] [blame] | 970 | } |
| 971 | |
Dave Barach | 9466c45 | 2018-08-24 17:21:14 -0400 | [diff] [blame] | 972 | if (nfree || verbose) |
| 973 | s = format (s, " [len %d] %u free elts\n", 1 << i, nfree); |
Dave Barach | e7d212f | 2018-02-07 13:14:06 -0500 | [diff] [blame] | 974 | } |
| 975 | |
| 976 | s = format (s, " %lld linear search buckets\n", linear_buckets); |
Dave Barach | ffb14b9 | 2018-09-11 17:20:23 -0400 | [diff] [blame] | 977 | used_bytes = alloc_arena_next (h); |
Dave Barach | 97f5af0 | 2018-02-22 09:48:45 -0500 | [diff] [blame] | 978 | s = format (s, |
| 979 | " arena: base %llx, next %llx\n" |
| 980 | " used %lld b (%lld Mbytes) of %lld b (%lld Mbytes)\n", |
Dave Barach | 9466c45 | 2018-08-24 17:21:14 -0400 | [diff] [blame] | 981 | alloc_arena (h), alloc_arena_next (h), |
Dave Barach | 97f5af0 | 2018-02-22 09:48:45 -0500 | [diff] [blame] | 982 | used_bytes, used_bytes >> 20, |
Dave Barach | 9466c45 | 2018-08-24 17:21:14 -0400 | [diff] [blame] | 983 | alloc_arena_size (h), alloc_arena_size (h) >> 20); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 984 | return s; |
| 985 | } |
| 986 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 987 | void BV (clib_bihash_foreach_key_value_pair) |
Neale Ranns | f50bac1 | 2019-12-06 05:53:17 +0000 | [diff] [blame] | 988 | (BVT (clib_bihash) * h, |
| 989 | BV (clib_bihash_foreach_key_value_pair_cb) cb, void *arg) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 990 | { |
| 991 | int i, j, k; |
Dave Barach | 908a5ea | 2017-07-14 12:42:21 -0400 | [diff] [blame] | 992 | BVT (clib_bihash_bucket) * b; |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 993 | BVT (clib_bihash_value) * v; |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 994 | |
Dave Barach | 16e4a4a | 2020-04-16 12:00:14 -0400 | [diff] [blame] | 995 | |
| 996 | #if BIHASH_LAZY_INSTANTIATE |
Dave Barach | 32dcd3b | 2019-07-08 12:25:38 -0400 | [diff] [blame] | 997 | if (PREDICT_FALSE (alloc_arena (h) == 0)) |
| 998 | return; |
Dave Barach | 16e4a4a | 2020-04-16 12:00:14 -0400 | [diff] [blame] | 999 | #endif |
Dave Barach | 32dcd3b | 2019-07-08 12:25:38 -0400 | [diff] [blame] | 1000 | |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 1001 | for (i = 0; i < h->nbuckets; i++) |
| 1002 | { |
Dave Barach | 16e4a4a | 2020-04-16 12:00:14 -0400 | [diff] [blame] | 1003 | b = BV (clib_bihash_get_bucket) (h, i); |
Damjan Marion | 882fcfe | 2018-07-17 23:01:49 +0200 | [diff] [blame] | 1004 | if (BV (clib_bihash_bucket_is_empty) (b)) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 1005 | continue; |
| 1006 | |
| 1007 | v = BV (clib_bihash_get_value) (h, b->offset); |
| 1008 | for (j = 0; j < (1 << b->log2_pages); j++) |
| 1009 | { |
| 1010 | for (k = 0; k < BIHASH_KVP_PER_PAGE; k++) |
| 1011 | { |
| 1012 | if (BV (clib_bihash_is_free) (&v->kvp[k])) |
| 1013 | continue; |
| 1014 | |
Neale Ranns | f50bac1 | 2019-12-06 05:53:17 +0000 | [diff] [blame] | 1015 | if (BIHASH_WALK_STOP == cb (&v->kvp[k], arg)) |
| 1016 | return; |
Dave Barach | ca45ee7 | 2018-08-06 08:43:47 -0400 | [diff] [blame] | 1017 | /* |
| 1018 | * In case the callback deletes the last entry in the bucket... |
| 1019 | */ |
| 1020 | if (BV (clib_bihash_bucket_is_empty) (b)) |
| 1021 | goto doublebreak; |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 1022 | } |
| 1023 | v++; |
| 1024 | } |
Dave Barach | ca45ee7 | 2018-08-06 08:43:47 -0400 | [diff] [blame] | 1025 | doublebreak: |
| 1026 | ; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 1027 | } |
| 1028 | } |
Dave Barach | dd3a57f | 2016-07-27 16:58:51 -0400 | [diff] [blame] | 1029 | |
Chris Luke | 16bcf7d | 2016-09-01 14:31:46 -0400 | [diff] [blame] | 1030 | /** @endcond */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 1031 | |
| 1032 | /* |
| 1033 | * fd.io coding-style-patch-verification: ON |
| 1034 | * |
| 1035 | * Local Variables: |
| 1036 | * eval: (c-set-style "gnu") |
| 1037 | * End: |
| 1038 | */ |