Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 1 | /* |
| 2 | Copyright (c) 2014 Cisco and/or its affiliates. |
| 3 | |
| 4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
| 5 | * you may not use this file except in compliance with the License. |
| 6 | * You may obtain a copy of the License at: |
| 7 | * |
| 8 | * http://www.apache.org/licenses/LICENSE-2.0 |
| 9 | * |
| 10 | * Unless required by applicable law or agreed to in writing, software |
| 11 | * distributed under the License is distributed on an "AS IS" BASIS, |
| 12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 13 | * See the License for the specific language governing permissions and |
| 14 | * limitations under the License. |
| 15 | */ |
| 16 | |
Chris Luke | 16bcf7d | 2016-09-01 14:31:46 -0400 | [diff] [blame] | 17 | /** @cond DOCUMENTATION_IS_IN_BIHASH_DOC_H */ |
Dave Barach | dd3a57f | 2016-07-27 16:58:51 -0400 | [diff] [blame] | 18 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 19 | /* |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 20 | * Note: to instantiate the template multiple times in a single file, |
| 21 | * #undef __included_bihash_template_h__... |
| 22 | */ |
| 23 | #ifndef __included_bihash_template_h__ |
| 24 | #define __included_bihash_template_h__ |
| 25 | |
| 26 | #include <vppinfra/heap.h> |
| 27 | #include <vppinfra/format.h> |
| 28 | #include <vppinfra/pool.h> |
| 29 | |
| 30 | #ifndef BIHASH_TYPE |
| 31 | #error BIHASH_TYPE not defined |
| 32 | #endif |
| 33 | |
| 34 | #define _bv(a,b) a##b |
| 35 | #define __bv(a,b) _bv(a,b) |
| 36 | #define BV(a) __bv(a,BIHASH_TYPE) |
| 37 | |
| 38 | #define _bvt(a,b) a##b##_t |
| 39 | #define __bvt(a,b) _bvt(a,b) |
| 40 | #define BVT(a) __bvt(a,BIHASH_TYPE) |
| 41 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 42 | typedef struct BV (clib_bihash_value) |
| 43 | { |
| 44 | union |
| 45 | { |
| 46 | BVT (clib_bihash_kv) kvp[BIHASH_KVP_PER_PAGE]; |
| 47 | struct BV (clib_bihash_value) * next_free; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 48 | }; |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 49 | } BVT (clib_bihash_value); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 50 | |
Dave Barach | 908a5ea | 2017-07-14 12:42:21 -0400 | [diff] [blame] | 51 | #if BIHASH_KVP_CACHE_SIZE > 5 |
| 52 | #error Requested KVP cache LRU data exceeds 16 bits |
| 53 | #endif |
| 54 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 55 | typedef struct |
| 56 | { |
| 57 | union |
| 58 | { |
| 59 | struct |
| 60 | { |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 61 | u32 offset; |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 62 | u8 linear_search; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 63 | u8 log2_pages; |
Dave Barach | 908a5ea | 2017-07-14 12:42:21 -0400 | [diff] [blame] | 64 | u16 cache_lru; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 65 | }; |
| 66 | u64 as_u64; |
| 67 | }; |
Dave Barach | c8ef08a | 2017-08-31 05:58:22 -0400 | [diff] [blame] | 68 | #if BIHASH_KVP_CACHE_SIZE > 0 |
Dave Barach | 908a5ea | 2017-07-14 12:42:21 -0400 | [diff] [blame] | 69 | BVT (clib_bihash_kv) cache[BIHASH_KVP_CACHE_SIZE]; |
Dave Barach | c8ef08a | 2017-08-31 05:58:22 -0400 | [diff] [blame] | 70 | #endif |
Dave Barach | 908a5ea | 2017-07-14 12:42:21 -0400 | [diff] [blame] | 71 | } BVT (clib_bihash_bucket); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 72 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 73 | typedef struct |
| 74 | { |
| 75 | BVT (clib_bihash_value) * values; |
Dave Barach | 908a5ea | 2017-07-14 12:42:21 -0400 | [diff] [blame] | 76 | BVT (clib_bihash_bucket) * buckets; |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 77 | volatile u32 *writer_lock; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 78 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 79 | BVT (clib_bihash_value) ** working_copies; |
Dave Barach | ba7ddfe | 2017-05-17 20:20:50 -0400 | [diff] [blame] | 80 | int *working_copy_lengths; |
Dave Barach | 908a5ea | 2017-07-14 12:42:21 -0400 | [diff] [blame] | 81 | BVT (clib_bihash_bucket) saved_bucket; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 82 | |
| 83 | u32 nbuckets; |
| 84 | u32 log2_nbuckets; |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 85 | u32 linear_buckets; |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 86 | u8 *name; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 87 | |
Dave Barach | 908a5ea | 2017-07-14 12:42:21 -0400 | [diff] [blame] | 88 | u64 cache_hits; |
| 89 | u64 cache_misses; |
| 90 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 91 | BVT (clib_bihash_value) ** freelists; |
| 92 | void *mheap; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 93 | |
Vijayabhaskar Katamreddy | fb8e61c | 2017-12-14 13:20:50 -0800 | [diff] [blame] | 94 | /** |
| 95 | * A custom format function to print the Key and Value of bihash_key instead of default hexdump |
| 96 | */ |
| 97 | format_function_t *fmt_fn; |
| 98 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 99 | } BVT (clib_bihash); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 100 | |
| 101 | |
Dave Barach | 908a5ea | 2017-07-14 12:42:21 -0400 | [diff] [blame] | 102 | static inline void |
| 103 | BV (clib_bihash_update_lru) (BVT (clib_bihash_bucket) * b, u8 slot) |
| 104 | { |
| 105 | u16 value, tmp, mask; |
| 106 | u8 found_lru_pos; |
| 107 | u16 save_hi; |
| 108 | |
| 109 | if (BIHASH_KVP_CACHE_SIZE < 2) |
| 110 | return; |
| 111 | |
| 112 | ASSERT (slot < BIHASH_KVP_CACHE_SIZE); |
| 113 | |
| 114 | /* First, find the slot in cache_lru */ |
| 115 | mask = slot; |
| 116 | if (BIHASH_KVP_CACHE_SIZE > 1) |
| 117 | mask |= slot << 3; |
| 118 | if (BIHASH_KVP_CACHE_SIZE > 2) |
| 119 | mask |= slot << 6; |
| 120 | if (BIHASH_KVP_CACHE_SIZE > 3) |
| 121 | mask |= slot << 9; |
| 122 | if (BIHASH_KVP_CACHE_SIZE > 4) |
| 123 | mask |= slot << 12; |
| 124 | |
| 125 | value = b->cache_lru; |
| 126 | tmp = value ^ mask; |
| 127 | |
| 128 | /* Already the most-recently used? */ |
| 129 | if ((tmp & 7) == 0) |
| 130 | return; |
| 131 | |
| 132 | found_lru_pos = ((tmp & (7 << 3)) == 0) ? 1 : 0; |
| 133 | if (BIHASH_KVP_CACHE_SIZE > 2) |
| 134 | found_lru_pos = ((tmp & (7 << 6)) == 0) ? 2 : found_lru_pos; |
| 135 | if (BIHASH_KVP_CACHE_SIZE > 3) |
| 136 | found_lru_pos = ((tmp & (7 << 9)) == 0) ? 3 : found_lru_pos; |
| 137 | if (BIHASH_KVP_CACHE_SIZE > 4) |
| 138 | found_lru_pos = ((tmp & (7 << 12)) == 0) ? 4 : found_lru_pos; |
| 139 | |
| 140 | ASSERT (found_lru_pos); |
| 141 | |
| 142 | /* create a mask to kill bits in or above slot */ |
| 143 | mask = 0xFFFF << found_lru_pos; |
| 144 | mask <<= found_lru_pos; |
| 145 | mask <<= found_lru_pos; |
| 146 | mask ^= 0xFFFF; |
| 147 | tmp = value & mask; |
| 148 | |
| 149 | /* Save bits above slot */ |
| 150 | mask ^= 0xFFFF; |
| 151 | mask <<= 3; |
| 152 | save_hi = value & mask; |
| 153 | |
| 154 | value = save_hi | (tmp << 3) | slot; |
| 155 | |
| 156 | b->cache_lru = value; |
| 157 | } |
| 158 | |
| 159 | void |
| 160 | BV (clib_bihash_update_lru_not_inline) (BVT (clib_bihash_bucket) * b, |
| 161 | u8 slot); |
| 162 | |
| 163 | static inline u8 BV (clib_bihash_get_lru) (BVT (clib_bihash_bucket) * b) |
| 164 | { |
Dave Barach | c8ef08a | 2017-08-31 05:58:22 -0400 | [diff] [blame] | 165 | #if BIHASH_KVP_CACHE_SIZE > 0 |
Dave Barach | 908a5ea | 2017-07-14 12:42:21 -0400 | [diff] [blame] | 166 | return (b->cache_lru >> (3 * (BIHASH_KVP_CACHE_SIZE - 1))) & 7; |
Dave Barach | c8ef08a | 2017-08-31 05:58:22 -0400 | [diff] [blame] | 167 | #else |
| 168 | return 0; |
| 169 | #endif |
Dave Barach | 908a5ea | 2017-07-14 12:42:21 -0400 | [diff] [blame] | 170 | } |
| 171 | |
| 172 | static inline void BV (clib_bihash_reset_cache) (BVT (clib_bihash_bucket) * b) |
| 173 | { |
Dave Barach | c8ef08a | 2017-08-31 05:58:22 -0400 | [diff] [blame] | 174 | #if BIHASH_KVP_CACHE_SIZE > 0 |
Dave Barach | 908a5ea | 2017-07-14 12:42:21 -0400 | [diff] [blame] | 175 | u16 initial_lru_value; |
| 176 | |
| 177 | memset (b->cache, 0xff, sizeof (b->cache)); |
| 178 | |
| 179 | /* |
| 180 | * We'll want the cache to be loaded from slot 0 -> slot N, so |
| 181 | * the initial LRU order is reverse index order. |
| 182 | */ |
| 183 | if (BIHASH_KVP_CACHE_SIZE == 1) |
| 184 | initial_lru_value = 0; |
| 185 | else if (BIHASH_KVP_CACHE_SIZE == 2) |
| 186 | initial_lru_value = (0 << 3) | (1 << 0); |
| 187 | else if (BIHASH_KVP_CACHE_SIZE == 3) |
| 188 | initial_lru_value = (0 << 6) | (1 << 3) | (2 << 0); |
| 189 | else if (BIHASH_KVP_CACHE_SIZE == 4) |
| 190 | initial_lru_value = (0 << 9) | (1 << 6) | (2 << 3) | (3 << 0); |
| 191 | else if (BIHASH_KVP_CACHE_SIZE == 5) |
| 192 | initial_lru_value = (0 << 12) | (1 << 9) | (2 << 6) | (3 << 3) | (4 << 0); |
| 193 | |
| 194 | b->cache_lru = initial_lru_value; |
Dave Barach | c8ef08a | 2017-08-31 05:58:22 -0400 | [diff] [blame] | 195 | #endif |
Dave Barach | 908a5ea | 2017-07-14 12:42:21 -0400 | [diff] [blame] | 196 | } |
| 197 | |
Dave Barach | 858c06f | 2017-07-21 10:44:27 -0400 | [diff] [blame] | 198 | static inline int BV (clib_bihash_lock_bucket) (BVT (clib_bihash_bucket) * b) |
Dave Barach | 908a5ea | 2017-07-14 12:42:21 -0400 | [diff] [blame] | 199 | { |
| 200 | BVT (clib_bihash_bucket) tmp_b; |
Dave Barach | 858c06f | 2017-07-21 10:44:27 -0400 | [diff] [blame] | 201 | u64 rv; |
| 202 | |
| 203 | tmp_b.as_u64 = 0; |
| 204 | tmp_b.cache_lru = 1 << 15; |
| 205 | |
| 206 | rv = __sync_fetch_and_or (&b->as_u64, tmp_b.as_u64); |
| 207 | tmp_b.as_u64 = rv; |
| 208 | /* Was already locked? */ |
| 209 | if (tmp_b.cache_lru & (1 << 15)) |
| 210 | return 0; |
| 211 | return 1; |
| 212 | } |
| 213 | |
| 214 | static inline void BV (clib_bihash_unlock_bucket) |
| 215 | (BVT (clib_bihash_bucket) * b) |
| 216 | { |
| 217 | BVT (clib_bihash_bucket) tmp_b; |
| 218 | |
Dave Barach | 908a5ea | 2017-07-14 12:42:21 -0400 | [diff] [blame] | 219 | tmp_b.as_u64 = b->as_u64; |
Dave Barach | 858c06f | 2017-07-21 10:44:27 -0400 | [diff] [blame] | 220 | tmp_b.cache_lru &= ~(1 << 15); |
Dave Barach | 908a5ea | 2017-07-14 12:42:21 -0400 | [diff] [blame] | 221 | b->as_u64 = tmp_b.as_u64; |
| 222 | } |
| 223 | |
| 224 | static inline void *BV (clib_bihash_get_value) (BVT (clib_bihash) * h, |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 225 | uword offset) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 226 | { |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 227 | u8 *hp = h->mheap; |
| 228 | u8 *vp = hp + offset; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 229 | |
| 230 | return (void *) vp; |
| 231 | } |
| 232 | |
Dave Barach | 908a5ea | 2017-07-14 12:42:21 -0400 | [diff] [blame] | 233 | static inline uword BV (clib_bihash_get_offset) (BVT (clib_bihash) * h, |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 234 | void *v) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 235 | { |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 236 | u8 *hp, *vp; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 237 | |
| 238 | hp = (u8 *) h->mheap; |
| 239 | vp = (u8 *) v; |
| 240 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 241 | ASSERT ((vp - hp) < 0x100000000ULL); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 242 | return vp - hp; |
| 243 | } |
| 244 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 245 | void BV (clib_bihash_init) |
| 246 | (BVT (clib_bihash) * h, char *name, u32 nbuckets, uword memory_size); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 247 | |
Vijayabhaskar Katamreddy | fb8e61c | 2017-12-14 13:20:50 -0800 | [diff] [blame] | 248 | void BV (clib_bihash_set_kvp_format_fn) (BVT (clib_bihash) * h, |
| 249 | format_function_t * fmt_fn); |
| 250 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 251 | void BV (clib_bihash_free) (BVT (clib_bihash) * h); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 252 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 253 | int BV (clib_bihash_add_del) (BVT (clib_bihash) * h, |
| 254 | BVT (clib_bihash_kv) * add_v, int is_add); |
Dave Barach | 908a5ea | 2017-07-14 12:42:21 -0400 | [diff] [blame] | 255 | int BV (clib_bihash_search) (BVT (clib_bihash) * h, |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 256 | BVT (clib_bihash_kv) * search_v, |
| 257 | BVT (clib_bihash_kv) * return_v); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 258 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 259 | void BV (clib_bihash_foreach_key_value_pair) (BVT (clib_bihash) * h, |
| 260 | void *callback, void *arg); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 261 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 262 | format_function_t BV (format_bihash); |
| 263 | format_function_t BV (format_bihash_kvp); |
Dave Barach | 908a5ea | 2017-07-14 12:42:21 -0400 | [diff] [blame] | 264 | format_function_t BV (format_bihash_lru); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 265 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 266 | static inline int BV (clib_bihash_search_inline) |
Dave Barach | 908a5ea | 2017-07-14 12:42:21 -0400 | [diff] [blame] | 267 | (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * key_result) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 268 | { |
| 269 | u64 hash; |
| 270 | u32 bucket_index; |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 271 | BVT (clib_bihash_value) * v; |
Dave Barach | 908a5ea | 2017-07-14 12:42:21 -0400 | [diff] [blame] | 272 | BVT (clib_bihash_bucket) * b; |
Dave Barach | c8ef08a | 2017-08-31 05:58:22 -0400 | [diff] [blame] | 273 | #if BIHASH_KVP_CACHE_SIZE > 0 |
Dave Barach | 908a5ea | 2017-07-14 12:42:21 -0400 | [diff] [blame] | 274 | BVT (clib_bihash_kv) * kvp; |
Dave Barach | c8ef08a | 2017-08-31 05:58:22 -0400 | [diff] [blame] | 275 | #endif |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 276 | int i, limit; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 277 | |
Dave Barach | 908a5ea | 2017-07-14 12:42:21 -0400 | [diff] [blame] | 278 | hash = BV (clib_bihash_hash) (key_result); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 279 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 280 | bucket_index = hash & (h->nbuckets - 1); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 281 | b = &h->buckets[bucket_index]; |
| 282 | |
| 283 | if (b->offset == 0) |
| 284 | return -1; |
| 285 | |
Dave Barach | c8ef08a | 2017-08-31 05:58:22 -0400 | [diff] [blame] | 286 | #if BIHASH_KVP_CACHE_SIZE > 0 |
Dave Barach | 858c06f | 2017-07-21 10:44:27 -0400 | [diff] [blame] | 287 | /* Check the cache, if not currently locked */ |
| 288 | if (PREDICT_TRUE ((b->cache_lru & (1 << 15)) == 0)) |
Dave Barach | 908a5ea | 2017-07-14 12:42:21 -0400 | [diff] [blame] | 289 | { |
| 290 | limit = BIHASH_KVP_CACHE_SIZE; |
| 291 | kvp = b->cache; |
| 292 | for (i = 0; i < limit; i++) |
| 293 | { |
| 294 | if (BV (clib_bihash_key_compare) (kvp[i].key, key_result->key)) |
| 295 | { |
| 296 | *key_result = kvp[i]; |
| 297 | h->cache_hits++; |
| 298 | return 0; |
| 299 | } |
| 300 | } |
| 301 | } |
Dave Barach | c8ef08a | 2017-08-31 05:58:22 -0400 | [diff] [blame] | 302 | #endif |
Dave Barach | 908a5ea | 2017-07-14 12:42:21 -0400 | [diff] [blame] | 303 | |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 304 | hash >>= h->log2_nbuckets; |
| 305 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 306 | v = BV (clib_bihash_get_value) (h, b->offset); |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 307 | |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 308 | /* If the bucket has unresolvable collisions, use linear search */ |
| 309 | limit = BIHASH_KVP_PER_PAGE; |
| 310 | v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0; |
| 311 | if (PREDICT_FALSE (b->linear_search)) |
| 312 | limit <<= b->log2_pages; |
| 313 | |
| 314 | for (i = 0; i < limit; i++) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 315 | { |
Dave Barach | 908a5ea | 2017-07-14 12:42:21 -0400 | [diff] [blame] | 316 | if (BV (clib_bihash_key_compare) (v->kvp[i].key, key_result->key)) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 317 | { |
Dave Barach | 908a5ea | 2017-07-14 12:42:21 -0400 | [diff] [blame] | 318 | *key_result = v->kvp[i]; |
| 319 | |
Dave Barach | c8ef08a | 2017-08-31 05:58:22 -0400 | [diff] [blame] | 320 | #if BIHASH_KVP_CACHE_SIZE > 0 |
| 321 | u8 cache_slot; |
Dave Barach | 858c06f | 2017-07-21 10:44:27 -0400 | [diff] [blame] | 322 | /* Try to lock the bucket */ |
| 323 | if (BV (clib_bihash_lock_bucket) (b)) |
| 324 | { |
| 325 | cache_slot = BV (clib_bihash_get_lru) (b); |
| 326 | b->cache[cache_slot] = v->kvp[i]; |
| 327 | BV (clib_bihash_update_lru) (b, cache_slot); |
Dave Barach | 908a5ea | 2017-07-14 12:42:21 -0400 | [diff] [blame] | 328 | |
Dave Barach | 858c06f | 2017-07-21 10:44:27 -0400 | [diff] [blame] | 329 | /* Unlock the bucket */ |
| 330 | BV (clib_bihash_unlock_bucket) (b); |
| 331 | h->cache_misses++; |
| 332 | } |
Dave Barach | c8ef08a | 2017-08-31 05:58:22 -0400 | [diff] [blame] | 333 | #endif |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 334 | return 0; |
| 335 | } |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 336 | } |
| 337 | return -1; |
| 338 | } |
| 339 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 340 | static inline int BV (clib_bihash_search_inline_2) |
Dave Barach | 908a5ea | 2017-07-14 12:42:21 -0400 | [diff] [blame] | 341 | (BVT (clib_bihash) * h, |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 342 | BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 343 | { |
| 344 | u64 hash; |
| 345 | u32 bucket_index; |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 346 | BVT (clib_bihash_value) * v; |
Dave Barach | 908a5ea | 2017-07-14 12:42:21 -0400 | [diff] [blame] | 347 | BVT (clib_bihash_bucket) * b; |
Dave Barach | c8ef08a | 2017-08-31 05:58:22 -0400 | [diff] [blame] | 348 | #if BIHASH_KVP_CACHE_SIZE > 0 |
Dave Barach | 908a5ea | 2017-07-14 12:42:21 -0400 | [diff] [blame] | 349 | BVT (clib_bihash_kv) * kvp; |
Dave Barach | c8ef08a | 2017-08-31 05:58:22 -0400 | [diff] [blame] | 350 | #endif |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 351 | int i, limit; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 352 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 353 | ASSERT (valuep); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 354 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 355 | hash = BV (clib_bihash_hash) (search_key); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 356 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 357 | bucket_index = hash & (h->nbuckets - 1); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 358 | b = &h->buckets[bucket_index]; |
| 359 | |
| 360 | if (b->offset == 0) |
| 361 | return -1; |
| 362 | |
Dave Barach | 858c06f | 2017-07-21 10:44:27 -0400 | [diff] [blame] | 363 | /* Check the cache, if currently unlocked */ |
Dave Barach | c8ef08a | 2017-08-31 05:58:22 -0400 | [diff] [blame] | 364 | #if BIHASH_KVP_CACHE_SIZE > 0 |
Dave Barach | 858c06f | 2017-07-21 10:44:27 -0400 | [diff] [blame] | 365 | if (PREDICT_TRUE ((b->cache_lru & (1 << 15)) == 0)) |
Dave Barach | 908a5ea | 2017-07-14 12:42:21 -0400 | [diff] [blame] | 366 | { |
| 367 | limit = BIHASH_KVP_CACHE_SIZE; |
| 368 | kvp = b->cache; |
| 369 | for (i = 0; i < limit; i++) |
| 370 | { |
| 371 | if (BV (clib_bihash_key_compare) (kvp[i].key, search_key->key)) |
| 372 | { |
| 373 | *valuep = kvp[i]; |
| 374 | h->cache_hits++; |
| 375 | return 0; |
| 376 | } |
| 377 | } |
| 378 | } |
Dave Barach | c8ef08a | 2017-08-31 05:58:22 -0400 | [diff] [blame] | 379 | #endif |
Dave Barach | 908a5ea | 2017-07-14 12:42:21 -0400 | [diff] [blame] | 380 | |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 381 | hash >>= h->log2_nbuckets; |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 382 | v = BV (clib_bihash_get_value) (h, b->offset); |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 383 | |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 384 | /* If the bucket has unresolvable collisions, use linear search */ |
| 385 | limit = BIHASH_KVP_PER_PAGE; |
| 386 | v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0; |
| 387 | if (PREDICT_FALSE (b->linear_search)) |
| 388 | limit <<= b->log2_pages; |
| 389 | |
| 390 | for (i = 0; i < limit; i++) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 391 | { |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 392 | if (BV (clib_bihash_key_compare) (v->kvp[i].key, search_key->key)) |
| 393 | { |
| 394 | *valuep = v->kvp[i]; |
Dave Barach | 908a5ea | 2017-07-14 12:42:21 -0400 | [diff] [blame] | 395 | |
Dave Barach | c8ef08a | 2017-08-31 05:58:22 -0400 | [diff] [blame] | 396 | #if BIHASH_KVP_CACHE_SIZE > 0 |
| 397 | u8 cache_slot; |
| 398 | |
Dave Barach | 858c06f | 2017-07-21 10:44:27 -0400 | [diff] [blame] | 399 | /* Try to lock the bucket */ |
| 400 | if (BV (clib_bihash_lock_bucket) (b)) |
| 401 | { |
| 402 | cache_slot = BV (clib_bihash_get_lru) (b); |
| 403 | b->cache[cache_slot] = v->kvp[i]; |
| 404 | BV (clib_bihash_update_lru) (b, cache_slot); |
Dave Barach | 908a5ea | 2017-07-14 12:42:21 -0400 | [diff] [blame] | 405 | |
Dave Barach | 858c06f | 2017-07-21 10:44:27 -0400 | [diff] [blame] | 406 | /* Reenable the cache */ |
| 407 | BV (clib_bihash_unlock_bucket) (b); |
| 408 | h->cache_misses++; |
| 409 | } |
Dave Barach | c8ef08a | 2017-08-31 05:58:22 -0400 | [diff] [blame] | 410 | #endif |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 411 | return 0; |
| 412 | } |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 413 | } |
| 414 | return -1; |
| 415 | } |
| 416 | |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 417 | #endif /* __included_bihash_template_h__ */ |
Dave Barach | dd3a57f | 2016-07-27 16:58:51 -0400 | [diff] [blame] | 418 | |
Chris Luke | 16bcf7d | 2016-09-01 14:31:46 -0400 | [diff] [blame] | 419 | /** @endcond */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 420 | |
| 421 | /* |
| 422 | * fd.io coding-style-patch-verification: ON |
| 423 | * |
| 424 | * Local Variables: |
| 425 | * eval: (c-set-style "gnu") |
| 426 | * End: |
| 427 | */ |