2 Copyright (c) 2013 Cisco and/or its affiliates.
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:
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 #ifndef included_clib_pfhash_h
18 #define included_clib_pfhash_h
21 #include <vppinfra/clib.h>
22 #include <vppinfra/hash.h>
23 #include <vppinfra/pool.h>
25 #if defined(CLIB_HAVE_VEC128) && ! defined (__ALTIVEC__)
29 /* 3 x 16 = 48 key bytes */
35 /* 3 x 4 = 12 value bytes */
42 /* 5 x 8 = 40 key bytes */
48 /* 5 x 4 = 20 value bytes */
55 /* 4 x 8 = 32 key bytes */
61 /* 4 x 8 = 32 value bytes */
67 /* 8 x 4 = 32 key bytes */
74 /* 8 x 4 = 32 value bytes */
82 pfhash_kv_8v8_t kv8v8;
90 #define PFHASH_BUCKET_OVERFLOW (u32)~0
92 /* Pool of key/value pairs */
95 /* overflow plain-o-hash */
98 /* Pretty-print name */
106 u32 nitems_in_overflow;
109 void pfhash_init (pfhash_t * p, char *name, u32 key_size, u32 value_size,
111 void pfhash_free (pfhash_t * p);
112 u64 pfhash_get (pfhash_t * p, u32 bucket, void *key);
113 void pfhash_set (pfhash_t * p, u32 bucket, void *key, void *value);
114 void pfhash_unset (pfhash_t * p, u32 bucket, void *key);
116 format_function_t format_pfhash;
119 pfhash_prefetch_bucket (pfhash_t * p, u32 bucket)
121 CLIB_PREFETCH (&p->buckets[bucket], CLIB_CACHE_LINE_BYTES, LOAD);
125 pfhash_read_bucket_prefetch_kv (pfhash_t * p, u32 bucket)
127 u32 bucket_contents = p->buckets[bucket];
128 if (PREDICT_TRUE ((bucket_contents & PFHASH_BUCKET_OVERFLOW) == 0))
129 CLIB_PREFETCH (&p->kvp[bucket_contents], CLIB_CACHE_LINE_BYTES, LOAD);
130 return bucket_contents;
134 * pfhash_search_kv_16
135 * See if the supplied 16-byte key matches one of three 16-byte (key,value) pairs.
136 * Return the indicated value, or ~0 if no match
138 * Note: including the overflow test, the fast path is 35 instrs
139 * on x86_64. Elves will steal your keyboard in the middle of the night if
140 * you "improve" it without checking the generated code!
143 pfhash_search_kv_16 (pfhash_t * p, u32 bucket_contents, u32x4 * key)
145 u32x4 diff0, diff1, diff2;
146 u32 is_equal0, is_equal1, is_equal2;
151 if (PREDICT_FALSE (bucket_contents == PFHASH_BUCKET_OVERFLOW))
154 hp = hash_get_mem (p->overflow_hash, key);
160 kv = &p->kvp[bucket_contents].kv16;
162 diff0 = u32x4_sub (kv->kb.k_u32x4[0], key[0]);
163 diff1 = u32x4_sub (kv->kb.k_u32x4[1], key[0]);
164 diff2 = u32x4_sub (kv->kb.k_u32x4[2], key[0]);
166 no_match = is_equal0 = (i16) u32x4_zero_byte_mask (diff0);
167 is_equal1 = (i16) u32x4_zero_byte_mask (diff1);
168 no_match |= is_equal1;
169 is_equal2 = (i16) u32x4_zero_byte_mask (diff2);
170 no_match |= is_equal2;
171 /* If any of the three items matched, no_match will be zero after this line */
172 no_match = ~no_match;
174 rv = (is_equal0 & kv->values[0])
175 | (is_equal1 & kv->values[1]) | (is_equal2 & kv->values[2]) | no_match;
181 pfhash_search_kv_8 (pfhash_t * p, u32 bucket_contents, u64 * key)
186 if (PREDICT_FALSE (bucket_contents == PFHASH_BUCKET_OVERFLOW))
189 hp = hash_get_mem (p->overflow_hash, key);
195 kv = &p->kvp[bucket_contents].kv8;
197 rv = (kv->kb.k_u64[0] == key[0]) ? kv->values[0] : rv;
198 rv = (kv->kb.k_u64[1] == key[0]) ? kv->values[1] : rv;
199 rv = (kv->kb.k_u64[2] == key[0]) ? kv->values[2] : rv;
200 rv = (kv->kb.k_u64[3] == key[0]) ? kv->values[3] : rv;
201 rv = (kv->kb.k_u64[4] == key[0]) ? kv->values[4] : rv;
207 pfhash_search_kv_8v8 (pfhash_t * p, u32 bucket_contents, u64 * key)
212 if (PREDICT_FALSE (bucket_contents == PFHASH_BUCKET_OVERFLOW))
215 hp = hash_get_mem (p->overflow_hash, key);
221 kv = &p->kvp[bucket_contents].kv8v8;
223 rv = (kv->kb.k_u64[0] == key[0]) ? kv->values[0] : rv;
224 rv = (kv->kb.k_u64[1] == key[0]) ? kv->values[1] : rv;
225 rv = (kv->kb.k_u64[2] == key[0]) ? kv->values[2] : rv;
226 rv = (kv->kb.k_u64[3] == key[0]) ? kv->values[3] : rv;
232 pfhash_search_kv_4 (pfhash_t * p, u32 bucket_contents, u32 * key)
236 u32 zbm[2], winner_index;
239 if (PREDICT_FALSE (bucket_contents == PFHASH_BUCKET_OVERFLOW))
242 hp = hash_get_mem (p->overflow_hash, key);
248 kv = &p->kvp[bucket_contents].kv4;
250 vector_key = u32x4_splat (key[0]);
252 is_equal[0] = (kv->kb.k_u32x4[0] == vector_key);
253 is_equal[1] = (kv->kb.k_u32x4[1] == vector_key);
254 zbm[0] = ~u32x4_zero_byte_mask (is_equal[0]) & 0xFFFF;
255 zbm[1] = ~u32x4_zero_byte_mask (is_equal[1]) & 0xFFFF;
257 if (PREDICT_FALSE ((zbm[0] == 0) && (zbm[1] == 0)))
260 winner_index = min_log2 (zbm[0]) >> 2;
261 winner_index = zbm[1] ? (4 + (min_log2 (zbm[1]) >> 2)) : winner_index;
263 return kv->values[winner_index];
266 #endif /* CLIB_HAVE_VEC128 */
268 #endif /* included_clib_pfhash_h */
271 * fd.io coding-style-patch-verification: ON
274 * eval: (c-set-style "gnu")