vnet/vnet/classify/vnet_classify.h

   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 <stdarg.h>
  19
  20 #include <vlib/vlib.h>
  21 #include <vnet/vnet.h>
  22 #include <vnet/pg/pg.h>
  23 #include <vnet/ethernet/ethernet.h>
  24 #include <vnet/ethernet/packet.h>
  25 #include <vnet/ip/ip_packet.h>
  26 #include <vnet/ip/ip4_packet.h>
  27 #include <vnet/ip/ip6_packet.h>
  28 #include <vlib/cli.h>
  29 #include <vnet/l2/l2_input.h>
  30 #include <vnet/l2/feat_bitmap.h>
  31 #include <vnet/api_errno.h>     /* for API error numbers */
  32
  33 #include <vppinfra/error.h>
  34 #include <vppinfra/hash.h>
  35 #include <vppinfra/cache.h>
  36 #include <vppinfra/xxhash.h>
  37
  38 extern vlib_node_registration_t ip4_classify_node;
  39 extern vlib_node_registration_t ip6_classify_node;
  40
  41 #define CLASSIFY_TRACE 0
  42
  43 #if !defined( __aarch64__) && !defined(__arm__)
  44 #define CLASSIFY_USE_SSE //Allow usage of SSE operations
  45 #endif
  46
  47 #define U32X4_ALIGNED(p) PREDICT_TRUE((((intptr_t)p) & 0xf) == 0)
  48
  49 /*
  50  * Classify table option to process packets
  51  *  CLASSIFY_FLAG_USE_CURR_DATA:
  52  *   - classify packets starting from VPP node’s current data pointer
  53  */
  54 #define CLASSIFY_FLAG_USE_CURR_DATA              1
  55
  56 /*
  57  * Classify session action
  58  *  CLASSIFY_ACTION_SET_IP4_FIB_INDEX:
  59  *   - Classified IP packets will be looked up
  60  *     from the specified ipv4 fib table
  61  *  CLASSIFY_ACTION_SET_IP6_FIB_INDEX:
  62  *   - Classified IP packets will be looked up
  63  *     from the specified ipv6 fib table
  64  */
  65 #define CLASSIFY_ACTION_SET_IP4_FIB_INDEX       1
  66 #define CLASSIFY_ACTION_SET_IP6_FIB_INDEX       2
  67
  68 struct _vnet_classify_main;
  69 typedef struct _vnet_classify_main vnet_classify_main_t;
  70
  71 #define foreach_size_in_u32x4                   \
  72 _(1)                                            \
  73 _(2)                                            \
  74 _(3)                                            \
  75 _(4)                                            \
  76 _(5)
  77
  78 typedef CLIB_PACKED(struct _vnet_classify_entry {
  79   /* Graph node next index */
  80   u32 next_index;
  81
  82   /* put into vnet_buffer(b)->l2_classfy.opaque_index */
  83   union {
  84     struct {
  85       u32 opaque_index;
  86       /* advance on hit, note it's a signed quantity... */
  87       i32 advance;
  88     };
  89     u64 opaque_count;
  90   };
  91
  92   /* Really only need 1 bit */
  93   u8 flags;
  94 #define VNET_CLASSIFY_ENTRY_FREE        (1<<0)
  95
  96   u8 action;
  97   u16 metadata;
  98
  99   /* Hit counter, last heard time */
 100   union {
 101     u64 hits;
 102     struct _vnet_classify_entry * next_free;
 103   };
 104
 105   f64 last_heard;
 106
 107   /* Must be aligned to a 16-octet boundary */
 108   u32x4 key[0];
 109 }) vnet_classify_entry_t;
 110
 111 static inline int vnet_classify_entry_is_free (vnet_classify_entry_t * e)
 112 {
 113   return e->flags & VNET_CLASSIFY_ENTRY_FREE;
 114 }
 115
 116 static inline int vnet_classify_entry_is_busy (vnet_classify_entry_t * e)
 117 {
 118   return ((e->flags & VNET_CLASSIFY_ENTRY_FREE) == 0);
 119 }
 120
 121 /* Need these to con the vector allocator */
 122 #define _(size)                                 \
 123 typedef CLIB_PACKED(struct {                    \
 124   u32 pad0[4];                                  \
 125   u64 pad1[2];                                  \
 126   u32x4 key[size];                              \
 127 }) vnet_classify_entry_##size##_t;
 128 foreach_size_in_u32x4;
 129 #undef _
 130
 131 typedef struct {
 132   union {
 133     struct {
 134       u32 offset;
 135       u8 pad[3];
 136       u8 log2_pages;
 137     };
 138     u64 as_u64;
 139   };
 140 } vnet_classify_bucket_t;
 141
 142 typedef struct {
 143   /* Mask to apply after skipping N vectors */
 144   u32x4 *mask;
 145   /* Buckets and entries */
 146   vnet_classify_bucket_t * buckets;
 147   vnet_classify_entry_t * entries;
 148
 149   /* Config parameters */
 150   u32 match_n_vectors;
 151   u32 skip_n_vectors;
 152   u32 nbuckets;
 153   u32 log2_nbuckets;
 154   int entries_per_page;
 155   u32 active_elements;
 156   u32 current_data_flag;
 157   int current_data_offset;
 158   u32 data_offset;
 159   /* Index of next table to try */
 160   u32 next_table_index;
 161
 162   /* Miss next index, return if next_table_index = 0 */
 163   u32 miss_next_index;
 164
 165   /* Per-bucket working copies, one per thread */
 166   vnet_classify_entry_t ** working_copies;
 167   vnet_classify_bucket_t saved_bucket;
 168
 169   /* Free entry freelists */
 170   vnet_classify_entry_t **freelists;
 171
 172   u8 * name;
 173
 174   /* Private allocation arena, protected by the writer lock */
 175   void * mheap;
 176
 177   /* Writer (only) lock for this table */
 178   volatile u32 * writer_lock;
 179
 180 } vnet_classify_table_t;
 181
 182 struct _vnet_classify_main {
 183   /* Table pool */
 184   vnet_classify_table_t * tables;
 185
 186   /* Registered next-index, opaque unformat fcns */
 187   unformat_function_t ** unformat_l2_next_index_fns;
 188   unformat_function_t ** unformat_ip_next_index_fns;
 189   unformat_function_t ** unformat_acl_next_index_fns;
 190   unformat_function_t ** unformat_policer_next_index_fns;
 191   unformat_function_t ** unformat_opaque_index_fns;
 192
 193   /* convenience variables */
 194   vlib_main_t * vlib_main;
 195   vnet_main_t * vnet_main;
 196 };
 197
 198 extern vnet_classify_main_t vnet_classify_main;
 199
 200 u8 * format_classify_table (u8 * s, va_list * args);
 201
 202 u64 vnet_classify_hash_packet (vnet_classify_table_t * t, u8 * h);
 203
 204 static inline u64
 205 vnet_classify_hash_packet_inline (vnet_classify_table_t * t,
 206                                   u8 * h)
 207 {
 208   u32x4 *mask;
 209
 210   union {
 211     u32x4 as_u32x4;
 212     u64 as_u64[2];
 213   } xor_sum __attribute__((aligned(sizeof(u32x4))));
 214
 215   ASSERT(t);
 216   mask = t->mask;
 217 #ifdef CLASSIFY_USE_SSE
 218   if (U32X4_ALIGNED(h)) {  //SSE can't handle unaligned data
 219     u32x4 *data = (u32x4 *)h;
 220     xor_sum.as_u32x4  = data[0 + t->skip_n_vectors] & mask[0];
 221     switch (t->match_n_vectors)
 222     {
 223       case 5:
 224         xor_sum.as_u32x4 ^= data[4 + t->skip_n_vectors] & mask[4];
 225         /* FALLTHROUGH */
 226       case 4:
 227         xor_sum.as_u32x4 ^= data[3 + t->skip_n_vectors] & mask[3];
 228         /* FALLTHROUGH */
 229       case 3:
 230         xor_sum.as_u32x4 ^= data[2 + t->skip_n_vectors] & mask[2];
 231         /* FALLTHROUGH */
 232       case 2:
 233         xor_sum.as_u32x4 ^= data[1 + t->skip_n_vectors] & mask[1];
 234         /* FALLTHROUGH */
 235       case 1:
 236         break;
 237       default:
 238         abort();
 239     }
 240   } else
 241 #endif /* CLASSIFY_USE_SSE */
 242   {
 243     u32 skip_u64 = t->skip_n_vectors * 2;
 244     u64 *data64 = (u64 *)h;
 245     xor_sum.as_u64[0] = data64[0 + skip_u64] & ((u64 *)mask)[0];
 246     xor_sum.as_u64[1] = data64[1 + skip_u64] & ((u64 *)mask)[1];
 247     switch (t->match_n_vectors)
 248     {
 249       case 5:
 250         xor_sum.as_u64[0]  ^= data64[8 + skip_u64] & ((u64 *)mask)[8];
 251         xor_sum.as_u64[1]  ^= data64[9 + skip_u64] & ((u64 *)mask)[9];
 252         /* FALLTHROUGH */
 253       case 4:
 254         xor_sum.as_u64[0]  ^= data64[6 + skip_u64] & ((u64 *)mask)[6];
 255         xor_sum.as_u64[1]  ^= data64[7 + skip_u64] & ((u64 *)mask)[7];
 256         /* FALLTHROUGH */
 257       case 3:
 258         xor_sum.as_u64[0]  ^= data64[4 + skip_u64] & ((u64 *)mask)[4];
 259         xor_sum.as_u64[1]  ^= data64[5 + skip_u64] & ((u64 *)mask)[5];
 260         /* FALLTHROUGH */
 261       case 2:
 262         xor_sum.as_u64[0]  ^= data64[2 + skip_u64] & ((u64 *)mask)[2];
 263         xor_sum.as_u64[1]  ^= data64[3 + skip_u64] & ((u64 *)mask)[3];
 264         /* FALLTHROUGH */
 265       case 1:
 266         break;
 267
 268       default:
 269         abort();
 270     }
 271   }
 272
 273   return clib_xxhash (xor_sum.as_u64[0] ^ xor_sum.as_u64[1]);
 274 }
 275
 276 static inline void
 277 vnet_classify_prefetch_bucket (vnet_classify_table_t * t, u64 hash)
 278 {
 279   u32 bucket_index;
 280
 281   ASSERT (is_pow2(t->nbuckets));
 282
 283   bucket_index = hash & (t->nbuckets - 1);
 284
 285   CLIB_PREFETCH(&t->buckets[bucket_index], CLIB_CACHE_LINE_BYTES, LOAD);
 286 }
 287
 288 static inline vnet_classify_entry_t *
 289 vnet_classify_get_entry (vnet_classify_table_t * t, uword offset)
 290 {
 291   u8 * hp = t->mheap;
 292   u8 * vp = hp + offset;
 293
 294   return (void *) vp;
 295 }
 296
 297 static inline uword vnet_classify_get_offset (vnet_classify_table_t * t,
 298                                               vnet_classify_entry_t * v)
 299 {
 300   u8 * hp, * vp;
 301
 302   hp = (u8 *) t->mheap;
 303   vp = (u8 *) v;
 304
 305   ASSERT((vp - hp) < 0x100000000ULL);
 306   return vp - hp;
 307 }
 308
 309 static inline vnet_classify_entry_t *
 310 vnet_classify_entry_at_index (vnet_classify_table_t * t,
 311                               vnet_classify_entry_t * e,
 312                               u32 index)
 313 {
 314   u8 * eu8;
 315
 316   eu8 = (u8 *)e;
 317
 318   eu8 += index * (sizeof (vnet_classify_entry_t) +
 319                   (t->match_n_vectors * sizeof (u32x4)));
 320
 321   return (vnet_classify_entry_t *) eu8;
 322 }
 323
 324 static inline void
 325 vnet_classify_prefetch_entry (vnet_classify_table_t * t,
 326                               u64 hash)
 327 {
 328   u32 bucket_index;
 329   u32 value_index;
 330   vnet_classify_bucket_t * b;
 331   vnet_classify_entry_t * e;
 332
 333   bucket_index = hash & (t->nbuckets - 1);
 334
 335   b = &t->buckets[bucket_index];
 336
 337   if (b->offset == 0)
 338     return;
 339
 340   hash >>= t->log2_nbuckets;
 341
 342   e = vnet_classify_get_entry (t, b->offset);
 343   value_index = hash & ((1<<b->log2_pages)-1);
 344
 345   e = vnet_classify_entry_at_index (t, e, value_index);
 346
 347   CLIB_PREFETCH(e, CLIB_CACHE_LINE_BYTES, LOAD);
 348 }
 349
 350 vnet_classify_entry_t *
 351 vnet_classify_find_entry (vnet_classify_table_t * t,
 352                           u8 * h, u64 hash, f64 now);
 353
 354 static inline vnet_classify_entry_t *
 355 vnet_classify_find_entry_inline (vnet_classify_table_t * t,
 356                                  u8 * h, u64 hash, f64 now)
 357   {
 358   vnet_classify_entry_t * v;
 359   u32x4 *mask, *key;
 360   union {
 361     u32x4 as_u32x4;
 362     u64 as_u64[2];
 363   } result __attribute__((aligned(sizeof(u32x4))));
 364   vnet_classify_bucket_t * b;
 365   u32 value_index;
 366   u32 bucket_index;
 367   int i;
 368
 369   bucket_index = hash & (t->nbuckets-1);
 370   b = &t->buckets[bucket_index];
 371   mask = t->mask;
 372
 373   if (b->offset == 0)
 374     return 0;
 375
 376   hash >>= t->log2_nbuckets;
 377
 378   v = vnet_classify_get_entry (t, b->offset);
 379   value_index = hash & ((1<<b->log2_pages)-1);
 380   v = vnet_classify_entry_at_index (t, v, value_index);
 381
 382 #ifdef CLASSIFY_USE_SSE
 383   if (U32X4_ALIGNED(h)) {
 384     u32x4 *data = (u32x4 *) h;
 385     for (i = 0; i < t->entries_per_page; i++) {
 386       key = v->key;
 387       result.as_u32x4 = (data[0 + t->skip_n_vectors] & mask[0]) ^ key[0];
 388       switch (t->match_n_vectors)
 389       {
 390         case 5:
 391           result.as_u32x4 |= (data[4 + t->skip_n_vectors] & mask[4]) ^ key[4];
 392           /* FALLTHROUGH */
 393         case 4:
 394           result.as_u32x4 |= (data[3 + t->skip_n_vectors] & mask[3]) ^ key[3];
 395           /* FALLTHROUGH */
 396         case 3:
 397           result.as_u32x4 |= (data[2 + t->skip_n_vectors] & mask[2]) ^ key[2];
 398           /* FALLTHROUGH */
 399         case 2:
 400           result.as_u32x4 |= (data[1 + t->skip_n_vectors] & mask[1]) ^ key[1];
 401           /* FALLTHROUGH */
 402         case 1:
 403           break;
 404         default:
 405           abort();
 406       }
 407
 408       if (u32x4_zero_byte_mask (result.as_u32x4) == 0xffff) {
 409         if (PREDICT_TRUE(now)) {
 410           v->hits++;
 411           v->last_heard = now;
 412         }
 413         return (v);
 414       }
 415       v = vnet_classify_entry_at_index (t, v, 1);
 416     }
 417   } else
 418 #endif /* CLASSIFY_USE_SSE */
 419   {
 420     u32 skip_u64 = t->skip_n_vectors * 2;
 421     u64 *data64 = (u64 *)h;
 422     for (i = 0; i < t->entries_per_page; i++) {
 423       key = v->key;
 424
 425       result.as_u64[0] = (data64[0 + skip_u64] & ((u64 *)mask)[0]) ^ ((u64 *)key)[0];
 426       result.as_u64[1] = (data64[1 + skip_u64] & ((u64 *)mask)[1]) ^ ((u64 *)key)[1];
 427       switch (t->match_n_vectors)
 428       {
 429         case 5:
 430           result.as_u64[0] |= (data64[8 + skip_u64] & ((u64 *)mask)[8]) ^ ((u64 *)key)[8];
 431           result.as_u64[1] |= (data64[9 + skip_u64] & ((u64 *)mask)[9]) ^ ((u64 *)key)[9];
 432           /* FALLTHROUGH */
 433         case 4:
 434           result.as_u64[0] |= (data64[6 + skip_u64] & ((u64 *)mask)[6]) ^ ((u64 *)key)[6];
 435           result.as_u64[1] |= (data64[7 + skip_u64] & ((u64 *)mask)[7]) ^ ((u64 *)key)[7];
 436           /* FALLTHROUGH */
 437         case 3:
 438           result.as_u64[0] |= (data64[4 + skip_u64] & ((u64 *)mask)[4]) ^ ((u64 *)key)[4];
 439           result.as_u64[1] |= (data64[5 + skip_u64] & ((u64 *)mask)[5]) ^ ((u64 *)key)[5];
 440           /* FALLTHROUGH */
 441         case 2:
 442           result.as_u64[0] |= (data64[2 + skip_u64] & ((u64 *)mask)[2]) ^ ((u64 *)key)[2];
 443           result.as_u64[1] |= (data64[3 + skip_u64] & ((u64 *)mask)[3]) ^ ((u64 *)key)[3];
 444           /* FALLTHROUGH */
 445         case 1:
 446           break;
 447         default:
 448           abort();
 449       }
 450
 451       if (result.as_u64[0] == 0 && result.as_u64[1] == 0) {
 452         if (PREDICT_TRUE(now)) {
 453           v->hits++;
 454           v->last_heard = now;
 455         }
 456         return (v);
 457       }
 458
 459       v = vnet_classify_entry_at_index (t, v, 1);
 460     }
 461   }
 462   return 0;
 463   }
 464
 465 vnet_classify_table_t *
 466 vnet_classify_new_table (vnet_classify_main_t *cm,
 467                          u8 * mask, u32 nbuckets, u32 memory_size,
 468                          u32 skip_n_vectors,
 469                          u32 match_n_vectors);
 470
 471 int vnet_classify_add_del_session (vnet_classify_main_t * cm,
 472                                    u32 table_index,
 473                                    u8 * match,
 474                                    u32 hit_next_index,
 475                                    u32 opaque_index,
 476                                    i32 advance,
 477                                    u8 action,
 478                                    u32 metadata,
 479                                    int is_add);
 480
 481 int vnet_classify_add_del_table (vnet_classify_main_t * cm,
 482                                  u8 * mask,
 483                                  u32 nbuckets,
 484                                  u32 memory_size,
 485                                  u32 skip,
 486                                  u32 match,
 487                                  u32 next_table_index,
 488                                  u32 miss_next_index,
 489                                  u32 * table_index,
 490                                  u8 current_data_flag,
 491                                  i16 current_data_offset,
 492                                  int is_add,
 493                                  int del_chain);
 494
 495 unformat_function_t unformat_ip4_mask;
 496 unformat_function_t unformat_ip6_mask;
 497 unformat_function_t unformat_l3_mask;
 498 unformat_function_t unformat_l2_mask;
 499 unformat_function_t unformat_classify_mask;
 500 unformat_function_t unformat_l2_next_index;
 501 unformat_function_t unformat_ip_next_index;
 502 unformat_function_t unformat_ip4_match;
 503 unformat_function_t unformat_ip6_match;
 504 unformat_function_t unformat_l3_match;
 505 unformat_function_t unformat_vlan_tag;
 506 unformat_function_t unformat_l2_match;
 507 unformat_function_t unformat_classify_match;
 508
 509 void vnet_classify_register_unformat_ip_next_index_fn
 510 (unformat_function_t * fn);
 511
 512 void vnet_classify_register_unformat_l2_next_index_fn
 513 (unformat_function_t * fn);
 514
 515 void vnet_classify_register_unformat_acl_next_index_fn
 516 (unformat_function_t * fn);
 517
 518 void  vnet_classify_register_unformat_policer_next_index_fn
 519 (unformat_function_t * fn);
 520
 521 void vnet_classify_register_unformat_opaque_index_fn (unformat_function_t * fn);
 522
 523 #endif /* __included_vnet_classify_h__ */