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