src/vnet/l2/l2_fib.h

   1 /*
   2  * l2_fib.h : layer 2 forwarding table (aka mac table)
   3  *
   4  * Copyright (c) 2013 Cisco and/or its affiliates.
   5  * Licensed under the Apache License, Version 2.0 (the "License");
   6  * you may not use this file except in compliance with the License.
   7  * You may obtain a copy of the License at:
   8  *
   9  *     http://www.apache.org/licenses/LICENSE-2.0
  10  *
  11  * Unless required by applicable law or agreed to in writing, software
  12  * distributed under the License is distributed on an "AS IS" BASIS,
  13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14  * See the License for the specific language governing permissions and
  15  * limitations under the License.
  16  */
  17
  18 #ifndef included_l2fib_h
  19 #define included_l2fib_h
  20
  21 #include <vlib/vlib.h>
  22 #include <vppinfra/bihash_8_8.h>
  23
  24 /*
  25  * The size of the hash table
  26  */
  27 #define L2FIB_NUM_BUCKETS (64 * 1024)
  28 #define L2FIB_MEMORY_SIZE (512<<20)
  29
  30 /* Ager scan interval is 1 minute for aging */
  31 #define L2FIB_AGE_SCAN_INTERVAL         (60.0)
  32
  33 /* MAC event scan delay is 100 msec unless specified by MAC event client */
  34 #define L2FIB_EVENT_SCAN_DELAY_DEFAULT  (0.1)
  35
  36 /* Max MACs in a event message is 100 unless specified by MAC event client */
  37 #define L2FIB_EVENT_MAX_MACS_DEFAULT    (100)
  38
  39 /* MAC event learn limit is 1000 unless specified by MAC event client */
  40 #define L2FIB_EVENT_LEARN_LIMIT_DEFAULT (1000)
  41
  42 typedef struct
  43 {
  44
  45   /* hash table */
  46   BVT (clib_bihash) mac_table;
  47
  48   /* per swif vector of sequence number for interface based flush of MACs */
  49   u8 *swif_seq_num;
  50
  51   /* last event or ager scan duration */
  52   f64 evt_scan_duration;
  53   f64 age_scan_duration;
  54
  55   /* delay between event scans, default to 100 msec */
  56   f64 event_scan_delay;
  57
  58   /* max macs in event message, default to 100 entries */
  59   u32 max_macs_in_event;
  60
  61   /* convenience variables */
  62   vlib_main_t *vlib_main;
  63   vnet_main_t *vnet_main;
  64 } l2fib_main_t;
  65
  66 extern l2fib_main_t l2fib_main;
  67
  68 /*
  69  * The L2fib key is the mac address and bridge domain ID
  70  */
  71 typedef struct
  72 {
  73   union
  74   {
  75     struct
  76     {
  77       u16 bd_index;
  78       u8 mac[6];
  79     } fields;
  80     struct
  81     {
  82       u32 w0;
  83       u32 w1;
  84     } words;
  85     u64 raw;
  86   };
  87 } l2fib_entry_key_t;
  88
  89 STATIC_ASSERT_SIZEOF (l2fib_entry_key_t, 8);
  90
  91
  92 typedef struct
  93 {
  94   union
  95   {
  96     struct
  97     {
  98       u8 swif;
  99       u8 bd;
 100     };
 101     u16 as_u16;
 102   };
 103 } l2fib_seq_num_t;
 104
 105 /**
 106  * Flags associated with an L2 Fib Entry
 107  *   - static mac, no MAC move
 108  *   - not subject to age
 109  *   - mac is for a bridged virtual interface
 110  *   - drop packets to/from this mac
 111  *   - MAC learned to be sent in L2 MAC event
 112  *   -MAC learned is a MAC move
 113  */
 114 #define foreach_l2fib_entry_result_attr       \
 115   _(STATIC,  0, "static")                     \
 116   _(AGE_NOT, 1, "age-not")                    \
 117   _(BVI,     2, "bvi")                        \
 118   _(FILTER,  3, "filter")                     \
 119   _(LRN_EVT, 4, "learn-event")                \
 120   _(LRN_MOV, 5, "learn-move")
 121
 122 typedef enum l2fib_entry_result_flags_t_
 123 {
 124   L2FIB_ENTRY_RESULT_FLAG_NONE = 0,
 125 #define _(a,v,s) L2FIB_ENTRY_RESULT_FLAG_##a = (1 << v),
 126   foreach_l2fib_entry_result_attr
 127 #undef _
 128 } __attribute__ ((packed)) l2fib_entry_result_flags_t;
 129
 130 STATIC_ASSERT_SIZEOF (l2fib_entry_result_flags_t, 1);
 131
 132 /*
 133  * The l2fib entry results
 134  */
 135 typedef struct l2fib_entry_result_t_
 136 {
 137   union
 138   {
 139     struct
 140     {
 141       u32 sw_if_index;          /* output sw_if_index (L3 intf if bvi==1) */
 142       l2fib_entry_result_flags_t flags;
 143
 144       u8 timestamp;             /* timestamp for aging */
 145       l2fib_seq_num_t sn;       /* bd/int seq num */
 146     } fields;
 147     u64 raw;
 148   };
 149 } l2fib_entry_result_t;
 150
 151 STATIC_ASSERT_SIZEOF (l2fib_entry_result_t, 8);
 152
 153 #define _(a,v,s)                                                        \
 154   always_inline int                                                     \
 155   l2fib_entry_result_is_set_##a (const l2fib_entry_result_t *r) {       \
 156     return (r->fields.flags & L2FIB_ENTRY_RESULT_FLAG_##a);             \
 157   }
 158 foreach_l2fib_entry_result_attr
 159 #undef _
 160 #define _(a,v,s)                                                        \
 161   always_inline void                                                    \
 162   l2fib_entry_result_set_##a (l2fib_entry_result_t *r) {       \
 163     r->fields.flags |= L2FIB_ENTRY_RESULT_FLAG_##a;             \
 164   }
 165   foreach_l2fib_entry_result_attr
 166 #undef _
 167 #define _(a,v,s)                                                        \
 168   always_inline void                                                    \
 169   l2fib_entry_result_clear_##a (l2fib_entry_result_t *r) {       \
 170     r->fields.flags &= ~L2FIB_ENTRY_RESULT_FLAG_##a;             \
 171   }
 172   foreach_l2fib_entry_result_attr
 173 #undef _
 174   static inline void
 175 l2fib_entry_result_set_bits (l2fib_entry_result_t * r,
 176                              l2fib_entry_result_flags_t bits)
 177 {
 178   r->fields.flags |= bits;
 179 }
 180
 181 static inline void
 182 l2fib_entry_result_clear_bits (l2fib_entry_result_t * r,
 183                                l2fib_entry_result_flags_t bits)
 184 {
 185   r->fields.flags &= ~bits;
 186 }
 187
 188 /* L2 MAC event entry action enums (see mac_entry definition in l2.api) */
 189 typedef enum
 190 {
 191   MAC_EVENT_ACTION_ADD = 0,
 192   MAC_EVENT_ACTION_DELETE = 1,
 193   MAC_EVENT_ACTION_MOVE = 2,
 194 } l2_mac_event_action_t;
 195
 196 /**
 197  * Compute the hash for the given key and return
 198  * the corresponding bucket index
 199  */
 200 always_inline u32
 201 l2fib_compute_hash_bucket (l2fib_entry_key_t * key)
 202 {
 203   u32 result;
 204   u32 temp_a;
 205   u32 temp_b;
 206
 207   result = 0xa5a5a5a5;          /* some seed */
 208   temp_a = key->words.w0;
 209   temp_b = key->words.w1;
 210   hash_mix32 (temp_a, temp_b, result);
 211
 212   return result % L2FIB_NUM_BUCKETS;
 213 }
 214
 215 /**
 216  * make address sanitizer skip this:
 217  * The 6-Bytes mac-address is cast into an 8-Bytes u64, with 2 additional Bytes.
 218  * l2fib_make_key() does read those two Bytes but does not use them.
 219  */
 220 always_inline u64 __attribute__ ((no_sanitize_address))
 221 l2fib_make_key (const u8 * mac_address, u16 bd_index)
 222 {
 223   u64 temp;
 224
 225   /*
 226    * The mac address in memory is A:B:C:D:E:F
 227    * The bd id in register is H:L
 228    */
 229 #if CLIB_ARCH_IS_LITTLE_ENDIAN
 230   /*
 231    * Create the in-register key as F:E:D:C:B:A:H:L
 232    * In memory the key is L:H:A:B:C:D:E:F
 233    */
 234   temp = *((u64 *) (mac_address)) << 16;
 235   temp = (temp & ~0xffff) | (u64) (bd_index);
 236 #else
 237   /*
 238    * Create the in-register key as H:L:A:B:C:D:E:F
 239    * In memory the key is H:L:A:B:C:D:E:F
 240    */
 241   temp = *((u64 *) (mac_address)) >> 16;
 242   temp = temp | (((u64) bd_index) << 48);
 243 #endif
 244
 245   return temp;
 246 }
 247
 248
 249
 250 /**
 251  * Lookup the entry for mac and bd_index in the mac table for 1 packet.
 252  * Cached_key and cached_result are used as a one-entry cache.
 253  * The function reads and updates them as needed.
 254  *
 255  * mac0 and bd_index0 are the keys. The entry is written to result0.
 256  * If the entry was not found, result0 is set to ~0.
 257  *
 258  * key0 and bucket0 return with the computed key and hash bucket,
 259  * convenient if the entry needs to be updated afterward.
 260  * If the cached_result was used, bucket0 is set to ~0.
 261  */
 262
 263 static_always_inline void
 264 l2fib_lookup_1 (BVT (clib_bihash) * mac_table,
 265                 l2fib_entry_key_t * cached_key,
 266                 l2fib_entry_result_t * cached_result,
 267                 u8 * mac0,
 268                 u16 bd_index0,
 269                 l2fib_entry_key_t * key0,
 270                 u32 * bucket0, l2fib_entry_result_t * result0)
 271 {
 272   /* set up key */
 273   key0->raw = l2fib_make_key (mac0, bd_index0);
 274   *bucket0 = ~0;
 275
 276   if (key0->raw == cached_key->raw)
 277     {
 278       /* Hit in the one-entry cache */
 279       result0->raw = cached_result->raw;
 280     }
 281   else
 282     {
 283       /* Do a regular mac table lookup */
 284       BVT (clib_bihash_kv) kv;
 285
 286       kv.key = key0->raw;
 287       kv.value = ~0ULL;
 288       BV (clib_bihash_search_inline) (mac_table, &kv);
 289       result0->raw = kv.value;
 290
 291       /* Update one-entry cache */
 292       cached_key->raw = key0->raw;
 293       cached_result->raw = result0->raw;
 294     }
 295 }
 296
 297
 298 /**
 299  * Lookup the entry for mac and bd_index in the mac table for 2 packets.
 300  * The lookups for the two packets are interleaved.
 301  *
 302  * Cached_key and cached_result are used as a one-entry cache.
 303  * The function reads and updates them as needed.
 304  *
 305  * mac0 and bd_index0 are the keys. The entry is written to result0.
 306  * If the entry was not found, result0 is set to ~0. The same
 307  * holds for mac1/bd_index1/result1.
 308  */
 309 static_always_inline void
 310 l2fib_lookup_2 (BVT (clib_bihash) * mac_table,
 311                 l2fib_entry_key_t * cached_key,
 312                 l2fib_entry_result_t * cached_result,
 313                 u8 * mac0,
 314                 u8 * mac1,
 315                 u16 bd_index0,
 316                 u16 bd_index1,
 317                 l2fib_entry_key_t * key0,
 318                 l2fib_entry_key_t * key1,
 319                 u32 * bucket0,
 320                 u32 * bucket1,
 321                 l2fib_entry_result_t * result0,
 322                 l2fib_entry_result_t * result1)
 323 {
 324   /* set up key */
 325   key0->raw = l2fib_make_key (mac0, bd_index0);
 326   key1->raw = l2fib_make_key (mac1, bd_index1);
 327
 328   if ((key0->raw == cached_key->raw) && (key1->raw == cached_key->raw))
 329     {
 330       /* Both hit in the one-entry cache */
 331       result0->raw = cached_result->raw;
 332       result1->raw = cached_result->raw;
 333       *bucket0 = ~0;
 334       *bucket1 = ~0;
 335
 336     }
 337   else
 338     {
 339       BVT (clib_bihash_kv) kv0, kv1;
 340
 341       /*
 342        * Do a regular mac table lookup
 343        * Interleave lookups for packet 0 and packet 1
 344        */
 345       kv0.key = key0->raw;
 346       kv1.key = key1->raw;
 347       kv0.value = ~0ULL;
 348       kv1.value = ~0ULL;
 349
 350       BV (clib_bihash_search_inline) (mac_table, &kv0);
 351       BV (clib_bihash_search_inline) (mac_table, &kv1);
 352
 353       result0->raw = kv0.value;
 354       result1->raw = kv1.value;
 355
 356       /* Update one-entry cache */
 357       cached_key->raw = key1->raw;
 358       cached_result->raw = result1->raw;
 359     }
 360 }
 361
 362 static_always_inline void
 363 l2fib_lookup_4 (BVT (clib_bihash) * mac_table,
 364                 l2fib_entry_key_t * cached_key,
 365                 l2fib_entry_result_t * cached_result,
 366                 const u8 * mac0,
 367                 const u8 * mac1,
 368                 const u8 * mac2,
 369                 const u8 * mac3,
 370                 u16 bd_index0,
 371                 u16 bd_index1,
 372                 u16 bd_index2,
 373                 u16 bd_index3,
 374                 l2fib_entry_key_t * key0,
 375                 l2fib_entry_key_t * key1,
 376                 l2fib_entry_key_t * key2,
 377                 l2fib_entry_key_t * key3,
 378                 u32 * bucket0,
 379                 u32 * bucket1,
 380                 u32 * bucket2,
 381                 u32 * bucket3,
 382                 l2fib_entry_result_t * result0,
 383                 l2fib_entry_result_t * result1,
 384                 l2fib_entry_result_t * result2,
 385                 l2fib_entry_result_t * result3)
 386 {
 387   /* set up key */
 388   key0->raw = l2fib_make_key (mac0, bd_index0);
 389   key1->raw = l2fib_make_key (mac1, bd_index1);
 390   key2->raw = l2fib_make_key (mac2, bd_index2);
 391   key3->raw = l2fib_make_key (mac3, bd_index3);
 392
 393   if ((key0->raw == cached_key->raw) && (key1->raw == cached_key->raw) &&
 394       (key2->raw == cached_key->raw) && (key3->raw == cached_key->raw))
 395     {
 396       /* Both hit in the one-entry cache */
 397       result0->raw = cached_result->raw;
 398       result1->raw = cached_result->raw;
 399       result2->raw = cached_result->raw;
 400       result3->raw = cached_result->raw;
 401       *bucket0 = ~0;
 402       *bucket1 = ~0;
 403       *bucket2 = ~0;
 404       *bucket3 = ~0;
 405
 406     }
 407   else
 408     {
 409       BVT (clib_bihash_kv) kv0, kv1, kv2, kv3;
 410
 411       /*
 412        * Do a regular mac table lookup
 413        * Interleave lookups for packet 0 and packet 1
 414        */
 415       kv0.key = key0->raw;
 416       kv1.key = key1->raw;
 417       kv2.key = key2->raw;
 418       kv3.key = key3->raw;
 419       kv0.value = ~0ULL;
 420       kv1.value = ~0ULL;
 421       kv2.value = ~0ULL;
 422       kv3.value = ~0ULL;
 423
 424       BV (clib_bihash_search_inline) (mac_table, &kv0);
 425       BV (clib_bihash_search_inline) (mac_table, &kv1);
 426       BV (clib_bihash_search_inline) (mac_table, &kv2);
 427       BV (clib_bihash_search_inline) (mac_table, &kv3);
 428
 429       result0->raw = kv0.value;
 430       result1->raw = kv1.value;
 431       result2->raw = kv2.value;
 432       result3->raw = kv3.value;
 433
 434       /* Update one-entry cache */
 435       cached_key->raw = key1->raw;
 436       cached_result->raw = result1->raw;
 437     }
 438 }
 439
 440 void l2fib_clear_table (void);
 441
 442 void
 443 l2fib_add_entry (const u8 * mac,
 444                  u32 bd_index,
 445                  u32 sw_if_index, l2fib_entry_result_flags_t flags);
 446
 447 static inline void
 448 l2fib_add_filter_entry (const u8 * mac, u32 bd_index)
 449 {
 450   l2fib_add_entry (mac, bd_index, ~0,
 451                    (L2FIB_ENTRY_RESULT_FLAG_FILTER |
 452                     L2FIB_ENTRY_RESULT_FLAG_STATIC));
 453 }
 454
 455 u32 l2fib_del_entry (const u8 * mac, u32 bd_index, u32 sw_if_index);
 456
 457 void l2fib_start_ager_scan (vlib_main_t * vm);
 458
 459 void l2fib_flush_int_mac (vlib_main_t * vm, u32 sw_if_index);
 460
 461 void l2fib_flush_bd_mac (vlib_main_t * vm, u32 bd_index);
 462
 463 void l2fib_flush_all_mac (vlib_main_t * vm);
 464
 465 void
 466 l2fib_table_dump (u32 bd_index, l2fib_entry_key_t ** l2fe_key,
 467                   l2fib_entry_result_t ** l2fe_res);
 468
 469 u8 *format_vnet_sw_if_index_name_with_NA (u8 * s, va_list * args);
 470
 471 static_always_inline u8 *
 472 l2fib_swif_seq_num (u32 sw_if_index)
 473 {
 474   l2fib_main_t *mp = &l2fib_main;
 475   return vec_elt_at_index (mp->swif_seq_num, sw_if_index);
 476 }
 477
 478 static_always_inline u8 *
 479 l2fib_valid_swif_seq_num (u32 sw_if_index)
 480 {
 481   l2fib_main_t *mp = &l2fib_main;
 482   vec_validate (mp->swif_seq_num, sw_if_index);
 483   return l2fib_swif_seq_num (sw_if_index);
 484 }
 485
 486 BVT (clib_bihash) * get_mac_table (void);
 487
 488 #endif
 489
 490 /*
 491  * fd.io coding-style-patch-verification: ON
 492  *
 493  * Local Variables:
 494  * eval: (c-set-style "gnu")
 495  * End:
 496  */