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 (256 * 1024)
  28 #define L2FIB_MEMORY_SIZE (128<<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   /* number of buckets in the hash table */
  49   uword mac_table_n_buckets;
  50
  51   /* hash table memory size */
  52   uword mac_table_memory_size;
  53
  54   /* hash table initialized */
  55   u8 mac_table_initialized;
  56
  57   /* last event or ager scan duration */
  58   f64 evt_scan_duration;
  59   f64 age_scan_duration;
  60
  61   /* delay between event scans, default to 100 msec */
  62   f64 event_scan_delay;
  63
  64   /* max macs in event message, default to 100 entries */
  65   u32 max_macs_in_event;
  66
  67   /* convenience variables */
  68   vlib_main_t *vlib_main;
  69   vnet_main_t *vnet_main;
  70 } l2fib_main_t;
  71
  72 extern l2fib_main_t l2fib_main;
  73
  74 /*
  75  * The L2fib key is the mac address and bridge domain ID
  76  */
  77 typedef struct
  78 {
  79   union
  80   {
  81     struct
  82     {
  83       u16 bd_index;
  84       u8 mac[6];
  85     } fields;
  86     struct
  87     {
  88       u32 w0;
  89       u32 w1;
  90     } words;
  91     u64 raw;
  92   };
  93 } l2fib_entry_key_t;
  94
  95 STATIC_ASSERT_SIZEOF (l2fib_entry_key_t, 8);
  96
  97 /**
  98  * A combined representation of the sequence number associated
  99  * with the interface and the BD.
 100  * The BD is in higher bits, the interface in the lower bits, but
 101  * the order is not important.
 102  *
 103  * It's convenient to represent this as an union of two u8s,
 104  * but then in the DP one is forced to do short writes, followed
 105  * by long reads, which is a sure thing for a stall
 106  */
 107 typedef u16 l2fib_seq_num_t;
 108
 109 static_always_inline l2fib_seq_num_t
 110 l2_fib_mk_seq_num (u8 bd_sn, u8 if_sn)
 111 {
 112   return (((u16) bd_sn) << 8) | if_sn;
 113 }
 114
 115 static_always_inline l2fib_seq_num_t
 116 l2_fib_update_seq_num (l2fib_seq_num_t sn, u8 if_sn)
 117 {
 118   sn &= 0xff00;
 119   sn |= if_sn;
 120
 121   return (sn);
 122 }
 123
 124 extern void l2_fib_extract_seq_num (l2fib_seq_num_t sn, u8 * bd_sn,
 125                                     u8 * if_sn);
 126 extern u8 *format_l2_fib_seq_num (u8 * s, va_list * a);
 127
 128 /**
 129  * Flags associated with an L2 Fib Entry
 130  *   - static mac, no MAC move
 131  *   - not subject to age
 132  *   - mac is for a bridged virtual interface
 133  *   - drop packets to/from this mac
 134  *   - MAC learned to be sent in L2 MAC event
 135  *   -MAC learned is a MAC move
 136  */
 137 #define foreach_l2fib_entry_result_attr       \
 138   _(STATIC,  0, "static")                     \
 139   _(AGE_NOT, 1, "age-not")                    \
 140   _(BVI,     2, "bvi")                        \
 141   _(FILTER,  3, "filter")                     \
 142   _(LRN_EVT, 4, "learn-event")                \
 143   _(LRN_MOV, 5, "learn-move")
 144
 145 typedef enum l2fib_entry_result_flags_t_
 146 {
 147   L2FIB_ENTRY_RESULT_FLAG_NONE = 0,
 148 #define _(a,v,s) L2FIB_ENTRY_RESULT_FLAG_##a = (1 << v),
 149   foreach_l2fib_entry_result_attr
 150 #undef _
 151 } __attribute__ ((packed)) l2fib_entry_result_flags_t;
 152
 153 STATIC_ASSERT_SIZEOF (l2fib_entry_result_flags_t, 1);
 154
 155 extern u8 *format_l2fib_entry_result_flags (u8 * s, va_list * args);
 156
 157 /*
 158  * The l2fib entry results
 159  */
 160 typedef struct l2fib_entry_result_t_
 161 {
 162   union
 163   {
 164     struct
 165     {
 166       u32 sw_if_index;          /* output sw_if_index (L3 intf if bvi==1) */
 167       l2fib_entry_result_flags_t flags;
 168
 169       u8 timestamp;             /* timestamp for aging */
 170       l2fib_seq_num_t sn;       /* bd/int seq num */
 171     } fields;
 172     u64 raw;
 173   };
 174 } l2fib_entry_result_t;
 175
 176 STATIC_ASSERT_SIZEOF (l2fib_entry_result_t, 8);
 177
 178 #define _(a,v,s)                                                        \
 179   always_inline int                                                     \
 180   l2fib_entry_result_is_set_##a (const l2fib_entry_result_t *r) {       \
 181     return (r->fields.flags & L2FIB_ENTRY_RESULT_FLAG_##a);             \
 182   }
 183 foreach_l2fib_entry_result_attr
 184 #undef _
 185 #define _(a,v,s)                                                        \
 186   always_inline void                                                    \
 187   l2fib_entry_result_set_##a (l2fib_entry_result_t *r) {       \
 188     r->fields.flags |= L2FIB_ENTRY_RESULT_FLAG_##a;             \
 189   }
 190   foreach_l2fib_entry_result_attr
 191 #undef _
 192 #define _(a,v,s)                                                        \
 193   always_inline void                                                    \
 194   l2fib_entry_result_clear_##a (l2fib_entry_result_t *r) {       \
 195     r->fields.flags &= ~L2FIB_ENTRY_RESULT_FLAG_##a;             \
 196   }
 197   foreach_l2fib_entry_result_attr
 198 #undef _
 199   static inline void
 200 l2fib_entry_result_set_bits (l2fib_entry_result_t * r,
 201                              l2fib_entry_result_flags_t bits)
 202 {
 203   r->fields.flags |= bits;
 204 }
 205
 206 static inline void
 207 l2fib_entry_result_clear_bits (l2fib_entry_result_t * r,
 208                                l2fib_entry_result_flags_t bits)
 209 {
 210   r->fields.flags &= ~bits;
 211 }
 212
 213 /* L2 MAC event entry action enums (see mac_entry definition in l2.api) */
 214 typedef enum
 215 {
 216   MAC_EVENT_ACTION_ADD = 0,
 217   MAC_EVENT_ACTION_DELETE = 1,
 218   MAC_EVENT_ACTION_MOVE = 2,
 219 } l2_mac_event_action_t;
 220
 221 /**
 222  * Compute the hash for the given key and return
 223  * the corresponding bucket index
 224  */
 225 always_inline u32
 226 l2fib_compute_hash_bucket (l2fib_entry_key_t * key)
 227 {
 228   u32 result;
 229   u32 temp_a;
 230   u32 temp_b;
 231
 232   result = 0xa5a5a5a5;          /* some seed */
 233   temp_a = key->words.w0;
 234   temp_b = key->words.w1;
 235   hash_mix32 (temp_a, temp_b, result);
 236
 237   return result % L2FIB_NUM_BUCKETS;
 238 }
 239
 240 always_inline u64
 241 l2fib_make_key (const u8 * mac_address, u16 bd_index)
 242 {
 243   u64 temp;
 244
 245   /*
 246    * The mac address in memory is A:B:C:D:E:F
 247    * The bd id in register is H:L
 248    */
 249 #if CLIB_ARCH_IS_LITTLE_ENDIAN
 250   /*
 251    * Create the in-register key as F:E:D:C:B:A:H:L
 252    * In memory the key is L:H:A:B:C:D:E:F
 253    */
 254   temp = CLIB_MEM_OVERFLOW_LOAD ((u64 *) mac_address) << 16;
 255   temp = (temp & ~0xffff) | (u64) (bd_index);
 256 #else
 257   /*
 258    * Create the in-register key as H:L:A:B:C:D:E:F
 259    * In memory the key is H:L:A:B:C:D:E:F
 260    */
 261   temp = CLIB_MEM_OVERFLOW_LOAD ((u64 *) mac_address) >> 16;
 262   temp = temp | (((u64) bd_index) << 48);
 263 #endif
 264
 265   return temp;
 266 }
 267
 268
 269
 270 /**
 271  * Lookup the entry for mac and bd_index in the mac table for 1 packet.
 272  * Cached_key and cached_result are used as a one-entry cache.
 273  * The function reads and updates them as needed.
 274  *
 275  * mac0 and bd_index0 are the keys. The entry is written to result0.
 276  * If the entry was not found, result0 is set to ~0.
 277  *
 278  * key0 return with the computed key, convenient if the entry needs,
 279  * to be updated afterward.
 280  */
 281
 282 static_always_inline void
 283 l2fib_lookup_1 (BVT (clib_bihash) * mac_table,
 284                 l2fib_entry_key_t * cached_key,
 285                 l2fib_entry_result_t * cached_result,
 286                 u8 * mac0,
 287                 u16 bd_index0,
 288                 l2fib_entry_key_t * key0, l2fib_entry_result_t * result0)
 289 {
 290   /* set up key */
 291   key0->raw = l2fib_make_key (mac0, bd_index0);
 292
 293   if (key0->raw == cached_key->raw)
 294     {
 295       /* Hit in the one-entry cache */
 296       result0->raw = cached_result->raw;
 297     }
 298   else
 299     {
 300       /* Do a regular mac table lookup */
 301       BVT (clib_bihash_kv) kv;
 302
 303       kv.key = key0->raw;
 304       kv.value = ~0ULL;
 305       BV (clib_bihash_search_inline) (mac_table, &kv);
 306       result0->raw = kv.value;
 307
 308       /* Update one-entry cache */
 309       cached_key->raw = key0->raw;
 310       cached_result->raw = result0->raw;
 311     }
 312 }
 313
 314
 315 /**
 316  * Lookup the entry for mac and bd_index in the mac table for 2 packets.
 317  * The lookups for the two packets are interleaved.
 318  *
 319  * Cached_key and cached_result are used as a one-entry cache.
 320  * The function reads and updates them as needed.
 321  *
 322  * mac0 and bd_index0 are the keys. The entry is written to result0.
 323  * If the entry was not found, result0 is set to ~0. The same
 324  * holds for mac1/bd_index1/result1.
 325  */
 326 static_always_inline void
 327 l2fib_lookup_2 (BVT (clib_bihash) * mac_table,
 328                 l2fib_entry_key_t * cached_key,
 329                 l2fib_entry_result_t * cached_result,
 330                 u8 * mac0,
 331                 u8 * mac1,
 332                 u16 bd_index0,
 333                 u16 bd_index1,
 334                 l2fib_entry_key_t * key0,
 335                 l2fib_entry_key_t * key1,
 336                 l2fib_entry_result_t * result0,
 337                 l2fib_entry_result_t * result1)
 338 {
 339   /* set up key */
 340   key0->raw = l2fib_make_key (mac0, bd_index0);
 341   key1->raw = l2fib_make_key (mac1, bd_index1);
 342
 343   if ((key0->raw == cached_key->raw) && (key1->raw == cached_key->raw))
 344     {
 345       /* Both hit in the one-entry cache */
 346       result0->raw = cached_result->raw;
 347       result1->raw = cached_result->raw;
 348     }
 349   else
 350     {
 351       BVT (clib_bihash_kv) kv0, kv1;
 352
 353       /*
 354        * Do a regular mac table lookup
 355        * Interleave lookups for packet 0 and packet 1
 356        */
 357       kv0.key = key0->raw;
 358       kv1.key = key1->raw;
 359       kv0.value = ~0ULL;
 360       kv1.value = ~0ULL;
 361
 362       BV (clib_bihash_search_inline) (mac_table, &kv0);
 363       BV (clib_bihash_search_inline) (mac_table, &kv1);
 364
 365       result0->raw = kv0.value;
 366       result1->raw = kv1.value;
 367
 368       /* Update one-entry cache */
 369       cached_key->raw = key1->raw;
 370       cached_result->raw = result1->raw;
 371     }
 372 }
 373
 374 static_always_inline void
 375 l2fib_lookup_4 (BVT (clib_bihash) * mac_table,
 376                 l2fib_entry_key_t * cached_key,
 377                 l2fib_entry_result_t * cached_result,
 378                 const u8 * mac0,
 379                 const u8 * mac1,
 380                 const u8 * mac2,
 381                 const u8 * mac3,
 382                 u16 bd_index0,
 383                 u16 bd_index1,
 384                 u16 bd_index2,
 385                 u16 bd_index3,
 386                 l2fib_entry_key_t * key0,
 387                 l2fib_entry_key_t * key1,
 388                 l2fib_entry_key_t * key2,
 389                 l2fib_entry_key_t * key3,
 390                 l2fib_entry_result_t * result0,
 391                 l2fib_entry_result_t * result1,
 392                 l2fib_entry_result_t * result2,
 393                 l2fib_entry_result_t * result3)
 394 {
 395   /* set up key */
 396   key0->raw = l2fib_make_key (mac0, bd_index0);
 397   key1->raw = l2fib_make_key (mac1, bd_index1);
 398   key2->raw = l2fib_make_key (mac2, bd_index2);
 399   key3->raw = l2fib_make_key (mac3, bd_index3);
 400
 401   if ((key0->raw == cached_key->raw) && (key1->raw == cached_key->raw) &&
 402       (key2->raw == cached_key->raw) && (key3->raw == cached_key->raw))
 403     {
 404       /* Both hit in the one-entry cache */
 405       result0->raw = cached_result->raw;
 406       result1->raw = cached_result->raw;
 407       result2->raw = cached_result->raw;
 408       result3->raw = cached_result->raw;
 409     }
 410   else
 411     {
 412       BVT (clib_bihash_kv) kv0, kv1, kv2, kv3;
 413
 414       /*
 415        * Do a regular mac table lookup
 416        * Interleave lookups for packet 0 and packet 1
 417        */
 418       kv0.key = key0->raw;
 419       kv1.key = key1->raw;
 420       kv2.key = key2->raw;
 421       kv3.key = key3->raw;
 422       kv0.value = ~0ULL;
 423       kv1.value = ~0ULL;
 424       kv2.value = ~0ULL;
 425       kv3.value = ~0ULL;
 426
 427       BV (clib_bihash_search_inline) (mac_table, &kv0);
 428       BV (clib_bihash_search_inline) (mac_table, &kv1);
 429       BV (clib_bihash_search_inline) (mac_table, &kv2);
 430       BV (clib_bihash_search_inline) (mac_table, &kv3);
 431
 432       result0->raw = kv0.value;
 433       result1->raw = kv1.value;
 434       result2->raw = kv2.value;
 435       result3->raw = kv3.value;
 436
 437       /* Update one-entry cache */
 438       cached_key->raw = key1->raw;
 439       cached_result->raw = result1->raw;
 440     }
 441 }
 442
 443 void l2fib_clear_table (void);
 444
 445 void l2fib_table_init (void);
 446
 447 void
 448 l2fib_add_entry (const u8 * mac,
 449                  u32 bd_index,
 450                  u32 sw_if_index, l2fib_entry_result_flags_t flags);
 451
 452 static inline void
 453 l2fib_add_filter_entry (const u8 * mac, u32 bd_index)
 454 {
 455   l2fib_add_entry (mac, bd_index, ~0,
 456                    (L2FIB_ENTRY_RESULT_FLAG_FILTER |
 457                     L2FIB_ENTRY_RESULT_FLAG_STATIC));
 458 }
 459
 460 u32 l2fib_del_entry (const u8 * mac, u32 bd_index, u32 sw_if_index);
 461
 462 void l2fib_start_ager_scan (vlib_main_t * vm);
 463
 464 void l2fib_flush_int_mac (vlib_main_t * vm, u32 sw_if_index);
 465
 466 void l2fib_flush_bd_mac (vlib_main_t * vm, u32 bd_index);
 467
 468 void l2fib_flush_all_mac (vlib_main_t * vm);
 469
 470 void
 471 l2fib_table_dump (u32 bd_index, l2fib_entry_key_t ** l2fe_key,
 472                   l2fib_entry_result_t ** l2fe_res);
 473
 474 u8 *format_vnet_sw_if_index_name_with_NA (u8 * s, va_list * args);
 475
 476 BVT (clib_bihash) * get_mac_table (void);
 477
 478 #endif
 479
 480 /*
 481  * fd.io coding-style-patch-verification: ON
 482  *
 483  * Local Variables:
 484  * eval: (c-set-style "gnu")
 485  * End:
 486  */