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