FD.io VPP  v19.08.3-2-gbabecb413
Vector Packet Processing
vnet_classify.h
Go to the documentation of this file.
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 #ifndef __included_vnet_classify_h__
16 #define __included_vnet_classify_h__
17 
18 #include <vnet/vnet.h>
19 #include <vnet/api_errno.h> /* for API error numbers */
20 
21 #include <vppinfra/error.h>
22 #include <vppinfra/hash.h>
23 #include <vppinfra/cache.h>
24 #include <vppinfra/xxhash.h>
25 
28 
29 #define CLASSIFY_TRACE 0
30 
31 /*
32  * Classify table option to process packets
33  * CLASSIFY_FLAG_USE_CURR_DATA:
34  * - classify packets starting from VPP node’s current data pointer
35  */
36 #define CLASSIFY_FLAG_USE_CURR_DATA 1
37 
38 /*
39  * Classify session action
40  * CLASSIFY_ACTION_SET_IP4_FIB_INDEX:
41  * - Classified IP packets will be looked up
42  * from the specified ipv4 fib table
43  * CLASSIFY_ACTION_SET_IP6_FIB_INDEX:
44  * - Classified IP packets will be looked up
45  * from the specified ipv6 fib table
46  */
48 {
52 } __attribute__ ((packed)) vnet_classify_action_t;
53 
54 struct _vnet_classify_main;
55 typedef struct _vnet_classify_main vnet_classify_main_t;
56 
57 #define foreach_size_in_u32x4 \
58 _(1) \
59 _(2) \
60 _(3) \
61 _(4) \
62 _(5)
63 
64 /* *INDENT-OFF* */
65 typedef CLIB_PACKED(struct _vnet_classify_entry {
66  /* Graph node next index */
67  u32 next_index;
68 
69  /* put into vnet_buffer(b)->l2_classfy.opaque_index */
70  union {
71  struct {
72  u32 opaque_index;
73  /* advance on hit, note it's a signed quantity... */
74  i32 advance;
75  };
76  u64 opaque_count;
77  };
78 
79  /* Really only need 1 bit */
80  u8 flags;
81 #define VNET_CLASSIFY_ENTRY_FREE (1<<0)
82 
84  u16 metadata;
85 
86  /* Hit counter, last heard time */
87  union {
88  u64 hits;
89  struct _vnet_classify_entry * next_free;
90  };
91 
92  f64 last_heard;
93 
94  /* Must be aligned to a 16-octet boundary */
95  u32x4 key[0];
96 }) vnet_classify_entry_t;
97 /* *INDENT-ON* */
98 
99 static inline int
100 vnet_classify_entry_is_free (vnet_classify_entry_t * e)
101 {
102  return e->flags & VNET_CLASSIFY_ENTRY_FREE;
103 }
104 
105 static inline int
106 vnet_classify_entry_is_busy (vnet_classify_entry_t * e)
107 {
108  return ((e->flags & VNET_CLASSIFY_ENTRY_FREE) == 0);
109 }
110 
111 /* Need these to con the vector allocator */
112 /* *INDENT-OFF* */
113 #define _(size) \
114 typedef CLIB_PACKED(struct { \
115  u32 pad0[4]; \
116  u64 pad1[2]; \
117  u32x4 key[size]; \
118 }) vnet_classify_entry_##size##_t;
120 /* *INDENT-ON* */
121 #undef _
122 
123 typedef struct
124 {
125  union
126  {
127  struct
128  {
131  u8 pad[2];
133  };
135  };
137 
138 typedef struct
139 {
140  CLIB_CACHE_LINE_ALIGN_MARK (cacheline0);
141  /* Mask to apply after skipping N vectors */
143  /* Buckets and entries */
145  vnet_classify_entry_t *entries;
146 
147  /* Config parameters */
158  /* Index of next table to try */
160 
161  /* Miss next index, return if next_table_index = 0 */
163 
164  /* Per-bucket working copies, one per thread */
165  vnet_classify_entry_t **working_copies;
168 
169  /* Free entry freelists */
170  vnet_classify_entry_t **freelists;
171 
173 
174  /* Private allocation arena, protected by the writer lock */
175  void *mheap;
176 
177  /* Writer (only) lock for this table */
179 
181 
182 typedef struct
183 {
184  int refcnt;
187 
188 struct _vnet_classify_main
189 {
190  /* Table pool */
191  vnet_classify_table_t *tables;
192 
193  /* Registered next-index, opaque unformat fcns */
194  unformat_function_t **unformat_l2_next_index_fns;
195  unformat_function_t **unformat_ip_next_index_fns;
196  unformat_function_t **unformat_acl_next_index_fns;
197  unformat_function_t **unformat_policer_next_index_fns;
198  unformat_function_t **unformat_opaque_index_fns;
199 
200  /* Pool of filter sets */
201  vnet_classify_filter_set_t *filter_sets;
202 
203  /* Per-interface filter set map. [0] is used for pcap */
204  u32 *filter_set_by_sw_if_index;
205 
206  /* convenience variables */
209 };
210 
212 
213 u8 *format_classify_table (u8 * s, va_list * args);
214 
216 
217 static inline u64
219 {
220  u32x4 *mask;
221 
222  union
223  {
224  u32x4 as_u32x4;
225  u64 as_u64[2];
226  } xor_sum __attribute__ ((aligned (sizeof (u32x4))));
227 
228  ASSERT (t);
229  mask = t->mask;
230 #ifdef CLIB_HAVE_VEC128
231  u32x4u *data = (u32x4u *) h;
232  xor_sum.as_u32x4 = data[0 + t->skip_n_vectors] & mask[0];
233  switch (t->match_n_vectors)
234  {
235  case 5:
236  xor_sum.as_u32x4 ^= data[4 + t->skip_n_vectors] & mask[4];
237  /* FALLTHROUGH */
238  case 4:
239  xor_sum.as_u32x4 ^= data[3 + t->skip_n_vectors] & mask[3];
240  /* FALLTHROUGH */
241  case 3:
242  xor_sum.as_u32x4 ^= data[2 + t->skip_n_vectors] & mask[2];
243  /* FALLTHROUGH */
244  case 2:
245  xor_sum.as_u32x4 ^= data[1 + t->skip_n_vectors] & mask[1];
246  /* FALLTHROUGH */
247  case 1:
248  break;
249  default:
250  abort ();
251  }
252 #else
253  u32 skip_u64 = t->skip_n_vectors * 2;
254  u64 *data64 = (u64 *) h;
255  xor_sum.as_u64[0] = data64[0 + skip_u64] & ((u64 *) mask)[0];
256  xor_sum.as_u64[1] = data64[1 + skip_u64] & ((u64 *) mask)[1];
257  switch (t->match_n_vectors)
258  {
259  case 5:
260  xor_sum.as_u64[0] ^= data64[8 + skip_u64] & ((u64 *) mask)[8];
261  xor_sum.as_u64[1] ^= data64[9 + skip_u64] & ((u64 *) mask)[9];
262  /* FALLTHROUGH */
263  case 4:
264  xor_sum.as_u64[0] ^= data64[6 + skip_u64] & ((u64 *) mask)[6];
265  xor_sum.as_u64[1] ^= data64[7 + skip_u64] & ((u64 *) mask)[7];
266  /* FALLTHROUGH */
267  case 3:
268  xor_sum.as_u64[0] ^= data64[4 + skip_u64] & ((u64 *) mask)[4];
269  xor_sum.as_u64[1] ^= data64[5 + skip_u64] & ((u64 *) mask)[5];
270  /* FALLTHROUGH */
271  case 2:
272  xor_sum.as_u64[0] ^= data64[2 + skip_u64] & ((u64 *) mask)[2];
273  xor_sum.as_u64[1] ^= data64[3 + skip_u64] & ((u64 *) mask)[3];
274  /* FALLTHROUGH */
275  case 1:
276  break;
277 
278  default:
279  abort ();
280  }
281 #endif /* CLIB_HAVE_VEC128 */
282 
283  return clib_xxhash (xor_sum.as_u64[0] ^ xor_sum.as_u64[1]);
284 }
285 
286 static inline void
288 {
289  u32 bucket_index;
290 
291  ASSERT (is_pow2 (t->nbuckets));
292 
293  bucket_index = hash & (t->nbuckets - 1);
294 
295  CLIB_PREFETCH (&t->buckets[bucket_index], CLIB_CACHE_LINE_BYTES, LOAD);
296 }
297 
298 static inline vnet_classify_entry_t *
300 {
301  u8 *hp = t->mheap;
302  u8 *vp = hp + offset;
303 
304  return (void *) vp;
305 }
306 
307 static inline uword
309  vnet_classify_entry_t * v)
310 {
311  u8 *hp, *vp;
312 
313  hp = (u8 *) t->mheap;
314  vp = (u8 *) v;
315 
316  ASSERT ((vp - hp) < 0x100000000ULL);
317  return vp - hp;
318 }
319 
320 static inline vnet_classify_entry_t *
322  vnet_classify_entry_t * e, u32 index)
323 {
324  u8 *eu8;
325 
326  eu8 = (u8 *) e;
327 
328  eu8 += index * (sizeof (vnet_classify_entry_t) +
329  (t->match_n_vectors * sizeof (u32x4)));
330 
331  return (vnet_classify_entry_t *) eu8;
332 }
333 
334 static inline void
336 {
337  u32 bucket_index;
338  u32 value_index;
340  vnet_classify_entry_t *e;
341 
342  bucket_index = hash & (t->nbuckets - 1);
343 
344  b = &t->buckets[bucket_index];
345 
346  if (b->offset == 0)
347  return;
348 
349  hash >>= t->log2_nbuckets;
350 
351  e = vnet_classify_get_entry (t, b->offset);
352  value_index = hash & ((1 << b->log2_pages) - 1);
353 
354  e = vnet_classify_entry_at_index (t, e, value_index);
355 
357 }
358 
359 vnet_classify_entry_t *vnet_classify_find_entry (vnet_classify_table_t * t,
360  u8 * h, u64 hash, f64 now);
361 
362 static inline vnet_classify_entry_t *
364  u8 * h, u64 hash, f64 now)
365 {
366  vnet_classify_entry_t *v;
367  u32x4 *mask, *key;
368  union
369  {
370  u32x4 as_u32x4;
371  u64 as_u64[2];
372  } result __attribute__ ((aligned (sizeof (u32x4))));
374  u32 value_index;
375  u32 bucket_index;
376  u32 limit;
377  int i;
378 
379  bucket_index = hash & (t->nbuckets - 1);
380  b = &t->buckets[bucket_index];
381  mask = t->mask;
382 
383  if (b->offset == 0)
384  return 0;
385 
386  hash >>= t->log2_nbuckets;
387 
388  v = vnet_classify_get_entry (t, b->offset);
389  value_index = hash & ((1 << b->log2_pages) - 1);
390  limit = t->entries_per_page;
391  if (PREDICT_FALSE (b->linear_search))
392  {
393  value_index = 0;
394  limit *= (1 << b->log2_pages);
395  }
396 
397  v = vnet_classify_entry_at_index (t, v, value_index);
398 
399 #ifdef CLIB_HAVE_VEC128
400  u32x4u *data = (u32x4u *) h;
401  for (i = 0; i < limit; i++)
402  {
403  key = v->key;
404  result.as_u32x4 = (data[0 + t->skip_n_vectors] & mask[0]) ^ key[0];
405  switch (t->match_n_vectors)
406  {
407  case 5:
408  result.as_u32x4 |= (data[4 + t->skip_n_vectors] & mask[4]) ^ key[4];
409  /* FALLTHROUGH */
410  case 4:
411  result.as_u32x4 |= (data[3 + t->skip_n_vectors] & mask[3]) ^ key[3];
412  /* FALLTHROUGH */
413  case 3:
414  result.as_u32x4 |= (data[2 + t->skip_n_vectors] & mask[2]) ^ key[2];
415  /* FALLTHROUGH */
416  case 2:
417  result.as_u32x4 |= (data[1 + t->skip_n_vectors] & mask[1]) ^ key[1];
418  /* FALLTHROUGH */
419  case 1:
420  break;
421  default:
422  abort ();
423  }
424 
425  if (u32x4_zero_byte_mask (result.as_u32x4) == 0xffff)
426  {
427  if (PREDICT_TRUE (now))
428  {
429  v->hits++;
430  v->last_heard = now;
431  }
432  return (v);
433  }
434  v = vnet_classify_entry_at_index (t, v, 1);
435  }
436 #else
437  u32 skip_u64 = t->skip_n_vectors * 2;
438  u64 *data64 = (u64 *) h;
439  for (i = 0; i < limit; i++)
440  {
441  key = v->key;
442 
443  result.as_u64[0] =
444  (data64[0 + skip_u64] & ((u64 *) mask)[0]) ^ ((u64 *) key)[0];
445  result.as_u64[1] =
446  (data64[1 + skip_u64] & ((u64 *) mask)[1]) ^ ((u64 *) key)[1];
447  switch (t->match_n_vectors)
448  {
449  case 5:
450  result.as_u64[0] |=
451  (data64[8 + skip_u64] & ((u64 *) mask)[8]) ^ ((u64 *) key)[8];
452  result.as_u64[1] |=
453  (data64[9 + skip_u64] & ((u64 *) mask)[9]) ^ ((u64 *) key)[9];
454  /* FALLTHROUGH */
455  case 4:
456  result.as_u64[0] |=
457  (data64[6 + skip_u64] & ((u64 *) mask)[6]) ^ ((u64 *) key)[6];
458  result.as_u64[1] |=
459  (data64[7 + skip_u64] & ((u64 *) mask)[7]) ^ ((u64 *) key)[7];
460  /* FALLTHROUGH */
461  case 3:
462  result.as_u64[0] |=
463  (data64[4 + skip_u64] & ((u64 *) mask)[4]) ^ ((u64 *) key)[4];
464  result.as_u64[1] |=
465  (data64[5 + skip_u64] & ((u64 *) mask)[5]) ^ ((u64 *) key)[5];
466  /* FALLTHROUGH */
467  case 2:
468  result.as_u64[0] |=
469  (data64[2 + skip_u64] & ((u64 *) mask)[2]) ^ ((u64 *) key)[2];
470  result.as_u64[1] |=
471  (data64[3 + skip_u64] & ((u64 *) mask)[3]) ^ ((u64 *) key)[3];
472  /* FALLTHROUGH */
473  case 1:
474  break;
475  default:
476  abort ();
477  }
478 
479  if (result.as_u64[0] == 0 && result.as_u64[1] == 0)
480  {
481  if (PREDICT_TRUE (now))
482  {
483  v->hits++;
484  v->last_heard = now;
485  }
486  return (v);
487  }
488 
489  v = vnet_classify_entry_at_index (t, v, 1);
490  }
491 #endif /* CLIB_HAVE_VEC128 */
492  return 0;
493 }
494 
496  u8 * mask, u32 nbuckets,
497  u32 memory_size,
498  u32 skip_n_vectors,
499  u32 match_n_vectors);
500 
502  u32 table_index,
503  u8 * match,
504  u32 hit_next_index,
505  u32 opaque_index,
506  i32 advance,
507  u8 action, u32 metadata, int is_add);
508 
510  u8 * mask,
511  u32 nbuckets,
512  u32 memory_size,
513  u32 skip,
514  u32 match,
515  u32 next_table_index,
516  u32 miss_next_index,
517  u32 * table_index,
518  u8 current_data_flag,
519  i16 current_data_offset,
520  int is_add, int del_chain);
521 
536 
538  (unformat_function_t * fn);
539 
541  (unformat_function_t * fn);
542 
544  (unformat_function_t * fn);
545 
547  (unformat_function_t * fn);
548 
550  fn);
551 
552 #endif /* __included_vnet_classify_h__ */
553 
554 /*
555  * fd.io coding-style-patch-verification: ON
556  *
557  * Local Variables:
558  * eval: (c-set-style "gnu")
559  * End:
560  */
u64 vnet_classify_hash_packet(vnet_classify_table_t *t, u8 *h)
unformat_function_t unformat_ip4_match
vnet_classify_entry_t ** working_copies
unformat_function_t unformat_vlan_tag
u8 pad[3]
log2 (size of the packing page block)
Definition: bihash_doc.h:61
#define CLIB_CACHE_LINE_ALIGN_MARK(mark)
Definition: cache.h:60
u32 flags
Definition: vhost_user.h:141
unformat_function_t unformat_l2_mask
unformat_function_t unformat_ip_next_index
enum vnet_classify_action_t_ vnet_classify_action_t
#define foreach_size_in_u32x4
Definition: vnet_classify.h:57
u64 as_u64
Definition: bihash_doc.h:63
#define PREDICT_TRUE(x)
Definition: clib.h:113
static vnet_classify_entry_t * vnet_classify_find_entry_inline(vnet_classify_table_t *t, u8 *h, u64 hash, f64 now)
unsigned long u64
Definition: types.h:89
#define VNET_CLASSIFY_ENTRY_FREE
unformat_function_t unformat_ip6_mask
static u64 clib_xxhash(u64 key)
Definition: xxhash.h:58
int vnet_classify_add_del_session(vnet_classify_main_t *cm, u32 table_index, u8 *match, u32 hit_next_index, u32 opaque_index, i32 advance, u8 action, u32 metadata, int is_add)
int i
unformat_function_t unformat_classify_match
vnet_classify_table_t * vnet_classify_new_table(vnet_classify_main_t *cm, u8 *mask, u32 nbuckets, u32 memory_size, u32 skip_n_vectors, u32 match_n_vectors)
u8 data[128]
Definition: ipsec.api:251
unformat_function_t unformat_l3_mask
unsigned char u8
Definition: types.h:56
unformat_function_t unformat_ip4_mask
double f64
Definition: types.h:142
unformat_function_t unformat_classify_mask
vnet_classify_action_t_
Definition: vnet_classify.h:47
clib_spinlock_t writer_lock
void vnet_classify_register_unformat_opaque_index_fn(unformat_function_t *fn)
unsigned int u32
Definition: types.h:88
static void vnet_classify_prefetch_bucket(vnet_classify_table_t *t, u64 hash)
u8 * format_classify_table(u8 *s, va_list *args)
static void vnet_classify_prefetch_entry(vnet_classify_table_t *t, u64 hash)
static int vnet_classify_entry_is_free(vnet_classify_entry_t *e)
static u64 vnet_classify_hash_packet_inline(vnet_classify_table_t *t, u8 *h)
unformat_function_t unformat_l3_match
unsigned short u16
Definition: types.h:57
vnet_classify_entry_t * entries
#define PREDICT_FALSE(x)
Definition: clib.h:112
unformat_function_t unformat_l2_next_index
vnet_main_t vnet_main
Definition: misc.c:43
void vnet_classify_register_unformat_policer_next_index_fn(unformat_function_t *fn)
uword() unformat_function_t(unformat_input_t *input, va_list *args)
Definition: format.h:233
static vnet_classify_entry_t * vnet_classify_entry_at_index(vnet_classify_table_t *t, vnet_classify_entry_t *e, u32 index)
static uword vnet_classify_get_offset(vnet_classify_table_t *t, vnet_classify_entry_t *v)
vnet_classify_bucket_t saved_bucket
#define CLIB_PREFETCH(addr, size, type)
Definition: cache.h:80
void vnet_classify_register_unformat_l2_next_index_fn(unformat_function_t *fn)
Definition: vnet_classify.c:87
void vnet_classify_register_unformat_acl_next_index_fn(unformat_function_t *fn)
struct _vnet_classify_main vnet_classify_main_t
Definition: vnet_classify.h:55
signed int i32
Definition: types.h:77
#define ASSERT(truth)
typedef CLIB_PACKED(struct _vnet_classify_entry { u32 next_index;union { struct { u32 opaque_index;i32 advance;};u64 opaque_count;};u8 flags;#define VNET_CLASSIFY_ENTRY_FREE vnet_classify_action_t action;u16 metadata;union { u64 hits;struct _vnet_classify_entry *next_free;};f64 last_heard;u32x4 key[0];}) vnet_classify_entry_t
unformat_function_t unformat_ip6_match
static uword is_pow2(uword x)
Definition: clib.h:236
int vlib_main(vlib_main_t *volatile vm, unformat_input_t *input)
Definition: main.c:2014
static int vnet_classify_entry_is_busy(vnet_classify_entry_t *e)
struct _vlib_node_registration vlib_node_registration_t
template key/value backing page structure
Definition: bihash_doc.h:44
vlib_node_registration_t ip6_classify_node
(constructor) VLIB_REGISTER_NODE (ip6_classify_node)
Definition: ip_classify.c:334
vnet_classify_bucket_t * buckets
u64 uword
Definition: types.h:112
vnet_classify_entry_t * vnet_classify_find_entry(vnet_classify_table_t *t, u8 *h, u64 hash, f64 now)
typedef key
Definition: ipsec.api:247
vlib_node_registration_t ip4_classify_node
(constructor) VLIB_REGISTER_NODE (ip4_classify_node)
Definition: ip_classify.c:313
unformat_function_t unformat_l4_match
void vnet_classify_register_unformat_ip_next_index_fn(unformat_function_t *fn)
Definition: vnet_classify.c:95
struct clib_bihash_value offset
template key/value backing page structure
unsigned long long u32x4
Definition: ixge.c:28
unformat_function_t unformat_l2_match
#define CLIB_CACHE_LINE_BYTES
Definition: cache.h:59
vnet_classify_entry_t ** freelists
vnet_classify_main_t vnet_classify_main
Definition: vnet_classify.c:29
static u32 u32x4_zero_byte_mask(u32x4 x)
static vnet_classify_entry_t * vnet_classify_get_entry(vnet_classify_table_t *t, uword offset)
signed short i16
Definition: types.h:46
int vnet_classify_add_del_table(vnet_classify_main_t *cm, u8 *mask, u32 nbuckets, u32 memory_size, u32 skip, u32 match, u32 next_table_index, u32 miss_next_index, u32 *table_index, u8 current_data_flag, i16 current_data_offset, int is_add, int del_chain)