FD.io VPP  v17.04-9-g99c0734
Vector Packet Processing
pfhash.h
Go to the documentation of this file.
1 /*
2  Copyright (c) 2013 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 
17 #ifndef included_clib_pfhash_h
18 #define included_clib_pfhash_h
19 
20 
21 #include <vppinfra/clib.h>
22 #include <vppinfra/hash.h>
23 #include <vppinfra/pool.h>
24 
25 #if defined(CLIB_HAVE_VEC128) && ! defined (__ALTIVEC__)
26 
27 typedef struct
28 {
29  /* 3 x 16 = 48 key bytes */
30  union
31  {
32  u32x4 k_u32x4[3];
33  u64 k_u64[6];
34  } kb;
35  /* 3 x 4 = 12 value bytes */
36  u32 values[3];
37  u32 pad;
38 } pfhash_kv_16_t;
39 
40 typedef struct
41 {
42  /* 5 x 8 = 40 key bytes */
43  union
44  {
45  u64 k_u64[5];
46  } kb;
47 
48  /* 5 x 4 = 20 value bytes */
49  u32 values[5];
50  u32 pad;
51 } pfhash_kv_8_t;
52 
53 typedef struct
54 {
55  /* 4 x 8 = 32 key bytes */
56  union
57  {
58  u64 k_u64[4];
59  } kb;
60 
61  /* 4 x 8 = 32 value bytes */
62  u64 values[4];
63 } pfhash_kv_8v8_t;
64 
65 typedef struct
66 {
67  /* 8 x 4 = 32 key bytes */
68  union
69  {
70  u32x4 k_u32x4[2];
71  u32 kb[8];
72  } kb;
73 
74  /* 8 x 4 = 32 value bytes */
75  u32 values[8];
76 } pfhash_kv_4_t;
77 
78 typedef union
79 {
80  pfhash_kv_16_t kv16;
81  pfhash_kv_8_t kv8;
82  pfhash_kv_8v8_t kv8v8;
83  pfhash_kv_4_t kv4;
84 } pfhash_kv_t;
85 
86 typedef struct
87 {
88  /* Bucket vector */
89  u32 *buckets;
90 #define PFHASH_BUCKET_OVERFLOW (u32)~0
91 
92  /* Pool of key/value pairs */
93  pfhash_kv_t *kvp;
94 
95  /* overflow plain-o-hash */
96  uword *overflow_hash;
97 
98  /* Pretty-print name */
99  u8 *name;
100 
101  u32 key_size;
102  u32 value_size;
103 
104  u32 overflow_count;
105  u32 nitems;
106  u32 nitems_in_overflow;
107 } pfhash_t;
108 
109 void pfhash_init (pfhash_t * p, char *name, u32 key_size, u32 value_size,
110  u32 nbuckets);
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);
115 
116 format_function_t format_pfhash;
117 
118 static inline void
119 pfhash_prefetch_bucket (pfhash_t * p, u32 bucket)
120 {
121  CLIB_PREFETCH (&p->buckets[bucket], CLIB_CACHE_LINE_BYTES, LOAD);
122 }
123 
124 static inline u32
125 pfhash_read_bucket_prefetch_kv (pfhash_t * p, u32 bucket)
126 {
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;
131 }
132 
133 /*
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
137  *
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!
141  */
142 static inline u32
143 pfhash_search_kv_16 (pfhash_t * p, u32 bucket_contents, u32x4 * key)
144 {
145  u32x4 diff0, diff1, diff2;
146  u32 is_equal0, is_equal1, is_equal2;
147  u32 no_match;
148  pfhash_kv_16_t *kv;
149  u32 rv;
150 
151  if (PREDICT_FALSE (bucket_contents == PFHASH_BUCKET_OVERFLOW))
152  {
153  uword *hp;
154  hp = hash_get_mem (p->overflow_hash, key);
155  if (hp)
156  return hp[0];
157  return (u32) ~ 0;
158  }
159 
160  kv = &p->kvp[bucket_contents].kv16;
161 
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]);
165 
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;
173 
174  rv = (is_equal0 & kv->values[0])
175  | (is_equal1 & kv->values[1]) | (is_equal2 & kv->values[2]) | no_match;
176 
177  return rv;
178 }
179 
180 static inline u32
181 pfhash_search_kv_8 (pfhash_t * p, u32 bucket_contents, u64 * key)
182 {
183  pfhash_kv_8_t *kv;
184  u32 rv = (u32) ~ 0;
185 
186  if (PREDICT_FALSE (bucket_contents == PFHASH_BUCKET_OVERFLOW))
187  {
188  uword *hp;
189  hp = hash_get_mem (p->overflow_hash, key);
190  if (hp)
191  return hp[0];
192  return (u32) ~ 0;
193  }
194 
195  kv = &p->kvp[bucket_contents].kv8;
196 
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;
202 
203  return rv;
204 }
205 
206 static inline u64
207 pfhash_search_kv_8v8 (pfhash_t * p, u32 bucket_contents, u64 * key)
208 {
209  pfhash_kv_8v8_t *kv;
210  u64 rv = (u64) ~ 0;
211 
212  if (PREDICT_FALSE (bucket_contents == PFHASH_BUCKET_OVERFLOW))
213  {
214  uword *hp;
215  hp = hash_get_mem (p->overflow_hash, key);
216  if (hp)
217  return hp[0];
218  return (u64) ~ 0;
219  }
220 
221  kv = &p->kvp[bucket_contents].kv8v8;
222 
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;
227 
228  return rv;
229 }
230 
231 static inline u32
232 pfhash_search_kv_4 (pfhash_t * p, u32 bucket_contents, u32 * key)
233 {
234  u32x4 vector_key;
235  u32x4 is_equal[2];
236  u32 zbm[2], winner_index;
237  pfhash_kv_4_t *kv;
238 
239  if (PREDICT_FALSE (bucket_contents == PFHASH_BUCKET_OVERFLOW))
240  {
241  uword *hp;
242  hp = hash_get_mem (p->overflow_hash, key);
243  if (hp)
244  return hp[0];
245  return (u32) ~ 0;
246  }
247 
248  kv = &p->kvp[bucket_contents].kv4;
249 
250  vector_key = u32x4_splat (key[0]);
251 
252  is_equal[0] = u32x4_is_equal (kv->kb.k_u32x4[0], vector_key);
253  is_equal[1] = u32x4_is_equal (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;
256 
257  if (PREDICT_FALSE ((zbm[0] == 0) && (zbm[1] == 0)))
258  return (u32) ~ 0;
259 
260  winner_index = min_log2 (zbm[0]) >> 2;
261  winner_index = zbm[1] ? (4 + (min_log2 (zbm[1]) >> 2)) : winner_index;
262 
263  return kv->values[winner_index];
264 }
265 
266 #endif /* CLIB_HAVE_VEC128 */
267 
268 #endif /* included_clib_pfhash_h */
269 
270 /*
271  * fd.io coding-style-patch-verification: ON
272  *
273  * Local Variables:
274  * eval: (c-set-style "gnu")
275  * End:
276  */
static u32x4 u32x4_is_equal(u32x4 x, u32x4 y)
Definition: vector_sse2.h:504
u8 pad[3]
log2 (size of the packing page block)
Definition: bihash_doc.h:61
#define PREDICT_TRUE(x)
Definition: clib.h:98
Fixed length block allocator.
u8 *( format_function_t)(u8 *s, va_list *args)
Definition: format.h:48
static uword min_log2(uword x)
Definition: clib.h:189
unsigned long long u32x4
Definition: ixge.c:28
unsigned long u64
Definition: types.h:89
#define PREDICT_FALSE(x)
Definition: clib.h:97
#define CLIB_PREFETCH(addr, size, type)
Definition: cache.h:82
unsigned int u32
Definition: types.h:88
u64 uword
Definition: types.h:112
#define u32x4_splat(i)
unsigned char u8
Definition: types.h:56
#define hash_get_mem(h, key)
Definition: hash.h:268
short i16
Definition: types.h:46
#define CLIB_CACHE_LINE_BYTES
Definition: cache.h:67
static u32 u32x4_zero_byte_mask(u32x4 x)