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 evet 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  * The l2fib entry results
 107  */
 108 typedef struct
 109 {
 110   union
 111   {
 112     struct
 113     {
 114       u32 sw_if_index;          /* output sw_if_index (L3 intf if bvi==1) */
 115
 116       u8 static_mac:1;          /* static mac, no MAC move */
 117       u8 age_not:1;             /* not subject to age */
 118       u8 bvi:1;                 /* mac is for a bridged virtual interface */
 119       u8 filter:1;              /* drop packets to/from this mac */
 120       u8 lrn_evt:1;             /* MAC learned to be sent in L2 MAC event */
 121       u8 lrn_mov:1;             /* MAC learned is a MAC move */
 122       u8 unused:2;
 123
 124       u8 timestamp;             /* timestamp for aging */
 125       l2fib_seq_num_t sn;       /* bd/int seq num */
 126     } fields;
 127     u64 raw;
 128   };
 129 } l2fib_entry_result_t;
 130
 131 STATIC_ASSERT_SIZEOF (l2fib_entry_result_t, 8);
 132
 133 /* L2 MAC event entry action enums (see mac_entry definition in l2.api) */
 134 typedef enum
 135 {
 136   MAC_EVENT_ACTION_ADD = 0,
 137   MAC_EVENT_ACTION_DELETE = 1,
 138   MAC_EVENT_ACTION_MOVE = 2,
 139 } l2_mac_event_action_t;
 140
 141 /**
 142  * Compute the hash for the given key and return
 143  * the corresponding bucket index
 144  */
 145 always_inline u32
 146 l2fib_compute_hash_bucket (l2fib_entry_key_t * key)
 147 {
 148   u32 result;
 149   u32 temp_a;
 150   u32 temp_b;
 151
 152   result = 0xa5a5a5a5;          /* some seed */
 153   temp_a = key->words.w0;
 154   temp_b = key->words.w1;
 155   hash_mix32 (temp_a, temp_b, result);
 156
 157   return result % L2FIB_NUM_BUCKETS;
 158 }
 159
 160 /**
 161  * make address sanitizer skip this:
 162  * The 6-Bytes mac-address is cast into an 8-Bytes u64, with 2 additional Bytes.
 163  * l2fib_make_key() does read those two Bytes but does not use them.
 164  */
 165 always_inline u64 __attribute__ ((no_sanitize_address))
 166 l2fib_make_key (u8 * mac_address, u16 bd_index)
 167 {
 168   u64 temp;
 169
 170   /*
 171    * The mac address in memory is A:B:C:D:E:F
 172    * The bd id in register is H:L
 173    */
 174 #if CLIB_ARCH_IS_LITTLE_ENDIAN
 175   /*
 176    * Create the in-register key as F:E:D:C:B:A:H:L
 177    * In memory the key is L:H:A:B:C:D:E:F
 178    */
 179   temp = *((u64 *) (mac_address)) << 16;
 180   temp = (temp & ~0xffff) | (u64) (bd_index);
 181 #else
 182   /*
 183    * Create the in-register key as H:L:A:B:C:D:E:F
 184    * In memory the key is H:L:A:B:C:D:E:F
 185    */
 186   temp = *((u64 *) (mac_address)) >> 16;
 187   temp = temp | (((u64) bd_index) << 48);
 188 #endif
 189
 190   return temp;
 191 }
 192
 193
 194
 195 /**
 196  * Lookup the entry for mac and bd_index in the mac table for 1 packet.
 197  * Cached_key and cached_result are used as a one-entry cache.
 198  * The function reads and updates them as needed.
 199  *
 200  * mac0 and bd_index0 are the keys. The entry is written to result0.
 201  * If the entry was not found, result0 is set to ~0.
 202  *
 203  * key0 and bucket0 return with the computed key and hash bucket,
 204  * convenient if the entry needs to be updated afterward.
 205  * If the cached_result was used, bucket0 is set to ~0.
 206  */
 207
 208 static_always_inline void
 209 l2fib_lookup_1 (BVT (clib_bihash) * mac_table,
 210                 l2fib_entry_key_t * cached_key,
 211                 l2fib_entry_result_t * cached_result,
 212                 u8 * mac0,
 213                 u16 bd_index0,
 214                 l2fib_entry_key_t * key0,
 215                 u32 * bucket0, l2fib_entry_result_t * result0)
 216 {
 217   /* set up key */
 218   key0->raw = l2fib_make_key (mac0, bd_index0);
 219   *bucket0 = ~0;
 220
 221   if (key0->raw == cached_key->raw)
 222     {
 223       /* Hit in the one-entry cache */
 224       result0->raw = cached_result->raw;
 225     }
 226   else
 227     {
 228       /* Do a regular mac table lookup */
 229       BVT (clib_bihash_kv) kv;
 230
 231       kv.key = key0->raw;
 232       kv.value = ~0ULL;
 233       BV (clib_bihash_search_inline) (mac_table, &kv);
 234       result0->raw = kv.value;
 235
 236       /* Update one-entry cache */
 237       cached_key->raw = key0->raw;
 238       cached_result->raw = result0->raw;
 239     }
 240 }
 241
 242
 243 /**
 244  * Lookup the entry for mac and bd_index in the mac table for 2 packets.
 245  * The lookups for the two packets are interleaved.
 246  *
 247  * Cached_key and cached_result are used as a one-entry cache.
 248  * The function reads and updates them as needed.
 249  *
 250  * mac0 and bd_index0 are the keys. The entry is written to result0.
 251  * If the entry was not found, result0 is set to ~0. The same
 252  * holds for mac1/bd_index1/result1.
 253  */
 254 static_always_inline void
 255 l2fib_lookup_2 (BVT (clib_bihash) * mac_table,
 256                 l2fib_entry_key_t * cached_key,
 257                 l2fib_entry_result_t * cached_result,
 258                 u8 * mac0,
 259                 u8 * mac1,
 260                 u16 bd_index0,
 261                 u16 bd_index1,
 262                 l2fib_entry_key_t * key0,
 263                 l2fib_entry_key_t * key1,
 264                 u32 * bucket0,
 265                 u32 * bucket1,
 266                 l2fib_entry_result_t * result0,
 267                 l2fib_entry_result_t * result1)
 268 {
 269   /* set up key */
 270   key0->raw = l2fib_make_key (mac0, bd_index0);
 271   key1->raw = l2fib_make_key (mac1, bd_index1);
 272
 273   if ((key0->raw == cached_key->raw) && (key1->raw == cached_key->raw))
 274     {
 275       /* Both hit in the one-entry cache */
 276       result0->raw = cached_result->raw;
 277       result1->raw = cached_result->raw;
 278       *bucket0 = ~0;
 279       *bucket1 = ~0;
 280
 281     }
 282   else
 283     {
 284       BVT (clib_bihash_kv) kv0, kv1;
 285
 286       /*
 287        * Do a regular mac table lookup
 288        * Interleave lookups for packet 0 and packet 1
 289        */
 290       kv0.key = key0->raw;
 291       kv1.key = key1->raw;
 292       kv0.value = ~0ULL;
 293       kv1.value = ~0ULL;
 294
 295       BV (clib_bihash_search_inline) (mac_table, &kv0);
 296       BV (clib_bihash_search_inline) (mac_table, &kv1);
 297
 298       result0->raw = kv0.value;
 299       result1->raw = kv1.value;
 300
 301       /* Update one-entry cache */
 302       cached_key->raw = key1->raw;
 303       cached_result->raw = result1->raw;
 304     }
 305 }
 306
 307 static_always_inline void
 308 l2fib_lookup_4 (BVT (clib_bihash) * mac_table,
 309                 l2fib_entry_key_t * cached_key,
 310                 l2fib_entry_result_t * cached_result,
 311                 u8 * mac0,
 312                 u8 * mac1,
 313                 u8 * mac2,
 314                 u8 * mac3,
 315                 u16 bd_index0,
 316                 u16 bd_index1,
 317                 u16 bd_index2,
 318                 u16 bd_index3,
 319                 l2fib_entry_key_t * key0,
 320                 l2fib_entry_key_t * key1,
 321                 l2fib_entry_key_t * key2,
 322                 l2fib_entry_key_t * key3,
 323                 u32 * bucket0,
 324                 u32 * bucket1,
 325                 u32 * bucket2,
 326                 u32 * bucket3,
 327                 l2fib_entry_result_t * result0,
 328                 l2fib_entry_result_t * result1,
 329                 l2fib_entry_result_t * result2,
 330                 l2fib_entry_result_t * result3)
 331 {
 332   /* set up key */
 333   key0->raw = l2fib_make_key (mac0, bd_index0);
 334   key1->raw = l2fib_make_key (mac1, bd_index1);
 335   key2->raw = l2fib_make_key (mac2, bd_index2);
 336   key3->raw = l2fib_make_key (mac3, bd_index3);
 337
 338   if ((key0->raw == cached_key->raw) && (key1->raw == cached_key->raw) &&
 339       (key2->raw == cached_key->raw) && (key3->raw == cached_key->raw))
 340     {
 341       /* Both hit in the one-entry cache */
 342       result0->raw = cached_result->raw;
 343       result1->raw = cached_result->raw;
 344       result2->raw = cached_result->raw;
 345       result3->raw = cached_result->raw;
 346       *bucket0 = ~0;
 347       *bucket1 = ~0;
 348       *bucket2 = ~0;
 349       *bucket3 = ~0;
 350
 351     }
 352   else
 353     {
 354       BVT (clib_bihash_kv) kv0, kv1, kv2, kv3;
 355
 356       /*
 357        * Do a regular mac table lookup
 358        * Interleave lookups for packet 0 and packet 1
 359        */
 360       kv0.key = key0->raw;
 361       kv1.key = key1->raw;
 362       kv2.key = key2->raw;
 363       kv3.key = key3->raw;
 364       kv0.value = ~0ULL;
 365       kv1.value = ~0ULL;
 366       kv2.value = ~0ULL;
 367       kv3.value = ~0ULL;
 368
 369       BV (clib_bihash_search_inline) (mac_table, &kv0);
 370       BV (clib_bihash_search_inline) (mac_table, &kv1);
 371       BV (clib_bihash_search_inline) (mac_table, &kv2);
 372       BV (clib_bihash_search_inline) (mac_table, &kv3);
 373
 374       result0->raw = kv0.value;
 375       result1->raw = kv1.value;
 376       result2->raw = kv2.value;
 377       result3->raw = kv3.value;
 378
 379       /* Update one-entry cache */
 380       cached_key->raw = key1->raw;
 381       cached_result->raw = result1->raw;
 382     }
 383 }
 384
 385 void l2fib_clear_table (void);
 386
 387 void
 388 l2fib_add_entry (u8 * mac,
 389                  u32 bd_index,
 390                  u32 sw_if_index, u8 static_mac, u8 drop_mac, u8 bvi_mac);
 391
 392 static inline void
 393 l2fib_add_fwd_entry (u8 * mac, u32 bd_index, u32 sw_if_index, u8 static_mac,
 394                      u8 bvi_mac)
 395 {
 396   l2fib_add_entry (mac, bd_index, sw_if_index, static_mac, 0, bvi_mac);
 397 }
 398
 399 static inline void
 400 l2fib_add_filter_entry (u8 * mac, u32 bd_index)
 401 {
 402   l2fib_add_entry (mac, bd_index, ~0, 1, 1, 0);
 403 }
 404
 405 u32 l2fib_del_entry (u8 * mac, u32 bd_index);
 406
 407 void l2fib_start_ager_scan (vlib_main_t * vm);
 408
 409 void l2fib_flush_int_mac (vlib_main_t * vm, u32 sw_if_index);
 410
 411 void l2fib_flush_bd_mac (vlib_main_t * vm, u32 bd_index);
 412
 413 void l2fib_flush_all_mac (vlib_main_t * vm);
 414
 415 void
 416 l2fib_table_dump (u32 bd_index, l2fib_entry_key_t ** l2fe_key,
 417                   l2fib_entry_result_t ** l2fe_res);
 418
 419 u8 *format_vnet_sw_if_index_name_with_NA (u8 * s, va_list * args);
 420
 421 static_always_inline u8 *
 422 l2fib_swif_seq_num (u32 sw_if_index)
 423 {
 424   l2fib_main_t *mp = &l2fib_main;
 425   return vec_elt_at_index (mp->swif_seq_num, sw_if_index);
 426 }
 427
 428 static_always_inline u8 *
 429 l2fib_valid_swif_seq_num (u32 sw_if_index)
 430 {
 431   l2fib_main_t *mp = &l2fib_main;
 432   vec_validate (mp->swif_seq_num, sw_if_index);
 433   return l2fib_swif_seq_num (sw_if_index);
 434 }
 435
 436 BVT (clib_bihash) * get_mac_table (void);
 437
 438 #endif
 439
 440 /*
 441  * fd.io coding-style-patch-verification: ON
 442  *
 443  * Local Variables:
 444  * eval: (c-set-style "gnu")
 445  * End:
 446  */