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 (256<<20)
  29
  30 typedef struct
  31 {
  32
  33   /* hash table */
  34   BVT (clib_bihash) mac_table;
  35
  36   /* per swif vector of sequence number for interface based flush of MACs */
  37   u8 *swif_seq_num;
  38
  39   /* convenience variables */
  40   vlib_main_t *vlib_main;
  41   vnet_main_t *vnet_main;
  42 } l2fib_main_t;
  43
  44 extern l2fib_main_t l2fib_main;
  45
  46 /*
  47  * The L2fib key is the mac address and bridge domain ID
  48  */
  49 typedef struct
  50 {
  51   union
  52   {
  53     struct
  54     {
  55       u16 bd_index;
  56       u8 mac[6];
  57     } fields;
  58     struct
  59     {
  60       u32 w0;
  61       u32 w1;
  62     } words;
  63     u64 raw;
  64   };
  65 } l2fib_entry_key_t;
  66
  67 STATIC_ASSERT_SIZEOF (l2fib_entry_key_t, 8);
  68
  69
  70 typedef struct
  71 {
  72   union
  73   {
  74     struct
  75     {
  76       u8 swif;
  77       u8 bd;
  78     };
  79     u16 as_u16;
  80   };
  81 } l2fib_seq_num_t;
  82
  83 /*
  84  * The l2fib entry results
  85  */
  86 typedef struct
  87 {
  88   union
  89   {
  90     struct
  91     {
  92       u32 sw_if_index;          /* output sw_if_index (L3 interface if bvi==1) */
  93
  94       u8 static_mac:1;          /* static mac, no dataplane learning */
  95       u8 bvi:1;                 /* mac is for a bridged virtual interface */
  96       u8 filter:1;              /* drop packets to/from this mac */
  97       u8 unused1:5;
  98       u8 timestamp;             /* timestamp for aging */
  99       l2fib_seq_num_t sn;       /* bd/int seq num */
 100     } fields;
 101     u64 raw;
 102   };
 103 } l2fib_entry_result_t;
 104
 105 STATIC_ASSERT_SIZEOF (l2fib_entry_result_t, 8);
 106
 107 /**
 108  * Compute the hash for the given key and return
 109  * the corresponding bucket index
 110  */
 111 always_inline u32
 112 l2fib_compute_hash_bucket (l2fib_entry_key_t * key)
 113 {
 114   u32 result;
 115   u32 temp_a;
 116   u32 temp_b;
 117
 118   result = 0xa5a5a5a5;          /* some seed */
 119   temp_a = key->words.w0;
 120   temp_b = key->words.w1;
 121   hash_mix32 (temp_a, temp_b, result);
 122
 123   return result % L2FIB_NUM_BUCKETS;
 124 }
 125
 126 always_inline u64
 127 l2fib_make_key (u8 * mac_address, u16 bd_index)
 128 {
 129   u64 temp;
 130
 131   /*
 132    * The mac address in memory is A:B:C:D:E:F
 133    * The bd id in register is H:L
 134    */
 135 #if CLIB_ARCH_IS_LITTLE_ENDIAN
 136   /*
 137    * Create the in-register key as F:E:D:C:B:A:H:L
 138    * In memory the key is L:H:A:B:C:D:E:F
 139    */
 140   temp = *((u64 *) (mac_address)) << 16;
 141   temp = (temp & ~0xffff) | (u64) (bd_index);
 142 #else
 143   /*
 144    * Create the in-register key as H:L:A:B:C:D:E:F
 145    * In memory the key is H:L:A:B:C:D:E:F
 146    */
 147   temp = *((u64 *) (mac_address)) >> 16;
 148   temp = temp | (((u64) bd_index) << 48);
 149 #endif
 150
 151   return temp;
 152 }
 153
 154
 155
 156 /**
 157  * Lookup the entry for mac and bd_index in the mac table for 1 packet.
 158  * Cached_key and cached_result are used as a one-entry cache.
 159  * The function reads and updates them as needed.
 160  *
 161  * mac0 and bd_index0 are the keys. The entry is written to result0.
 162  * If the entry was not found, result0 is set to ~0.
 163  *
 164  * key0 and bucket0 return with the computed key and hash bucket,
 165  * convenient if the entry needs to be updated afterward.
 166  * If the cached_result was used, bucket0 is set to ~0.
 167  */
 168
 169 static_always_inline void
 170 l2fib_lookup_1 (BVT (clib_bihash) * mac_table,
 171                 l2fib_entry_key_t * cached_key,
 172                 l2fib_entry_result_t * cached_result,
 173                 u8 * mac0,
 174                 u16 bd_index0,
 175                 l2fib_entry_key_t * key0,
 176                 u32 * bucket0, l2fib_entry_result_t * result0)
 177 {
 178   /* set up key */
 179   key0->raw = l2fib_make_key (mac0, bd_index0);
 180   *bucket0 = ~0;
 181
 182   if (key0->raw == cached_key->raw)
 183     {
 184       /* Hit in the one-entry cache */
 185       result0->raw = cached_result->raw;
 186     }
 187   else
 188     {
 189       /* Do a regular mac table lookup */
 190       BVT (clib_bihash_kv) kv;
 191
 192       kv.key = key0->raw;
 193       kv.value = ~0ULL;
 194       BV (clib_bihash_search_inline) (mac_table, &kv);
 195       result0->raw = kv.value;
 196
 197       /* Update one-entry cache */
 198       cached_key->raw = key0->raw;
 199       cached_result->raw = result0->raw;
 200     }
 201 }
 202
 203
 204 /**
 205  * Lookup the entry for mac and bd_index in the mac table for 2 packets.
 206  * The lookups for the two packets are interleaved.
 207  *
 208  * Cached_key and cached_result are used as a one-entry cache.
 209  * The function reads and updates them as needed.
 210  *
 211  * mac0 and bd_index0 are the keys. The entry is written to result0.
 212  * If the entry was not found, result0 is set to ~0. The same
 213  * holds for mac1/bd_index1/result1.
 214  */
 215 static_always_inline void
 216 l2fib_lookup_2 (BVT (clib_bihash) * mac_table,
 217                 l2fib_entry_key_t * cached_key,
 218                 l2fib_entry_result_t * cached_result,
 219                 u8 * mac0,
 220                 u8 * mac1,
 221                 u16 bd_index0,
 222                 u16 bd_index1,
 223                 l2fib_entry_key_t * key0,
 224                 l2fib_entry_key_t * key1,
 225                 u32 * bucket0,
 226                 u32 * bucket1,
 227                 l2fib_entry_result_t * result0,
 228                 l2fib_entry_result_t * result1)
 229 {
 230   /* set up key */
 231   key0->raw = l2fib_make_key (mac0, bd_index0);
 232   key1->raw = l2fib_make_key (mac1, bd_index1);
 233
 234   if ((key0->raw == cached_key->raw) && (key1->raw == cached_key->raw))
 235     {
 236       /* Both hit in the one-entry cache */
 237       result0->raw = cached_result->raw;
 238       result1->raw = cached_result->raw;
 239       *bucket0 = ~0;
 240       *bucket1 = ~0;
 241
 242     }
 243   else
 244     {
 245       BVT (clib_bihash_kv) kv0, kv1;
 246
 247       /*
 248        * Do a regular mac table lookup
 249        * Interleave lookups for packet 0 and packet 1
 250        */
 251       kv0.key = key0->raw;
 252       kv1.key = key1->raw;
 253       kv0.value = ~0ULL;
 254       kv1.value = ~0ULL;
 255
 256       BV (clib_bihash_search_inline) (mac_table, &kv0);
 257       BV (clib_bihash_search_inline) (mac_table, &kv1);
 258
 259       result0->raw = kv0.value;
 260       result1->raw = kv1.value;
 261
 262       /* Update one-entry cache */
 263       cached_key->raw = key1->raw;
 264       cached_result->raw = result1->raw;
 265     }
 266 }
 267
 268 static_always_inline void
 269 l2fib_lookup_4 (BVT (clib_bihash) * mac_table,
 270                 l2fib_entry_key_t * cached_key,
 271                 l2fib_entry_result_t * cached_result,
 272                 u8 * mac0,
 273                 u8 * mac1,
 274                 u8 * mac2,
 275                 u8 * mac3,
 276                 u16 bd_index0,
 277                 u16 bd_index1,
 278                 u16 bd_index2,
 279                 u16 bd_index3,
 280                 l2fib_entry_key_t * key0,
 281                 l2fib_entry_key_t * key1,
 282                 l2fib_entry_key_t * key2,
 283                 l2fib_entry_key_t * key3,
 284                 u32 * bucket0,
 285                 u32 * bucket1,
 286                 u32 * bucket2,
 287                 u32 * bucket3,
 288                 l2fib_entry_result_t * result0,
 289                 l2fib_entry_result_t * result1,
 290                 l2fib_entry_result_t * result2,
 291                 l2fib_entry_result_t * result3)
 292 {
 293   /* set up key */
 294   key0->raw = l2fib_make_key (mac0, bd_index0);
 295   key1->raw = l2fib_make_key (mac1, bd_index1);
 296   key2->raw = l2fib_make_key (mac2, bd_index2);
 297   key3->raw = l2fib_make_key (mac3, bd_index3);
 298
 299   if ((key0->raw == cached_key->raw) && (key1->raw == cached_key->raw) &&
 300       (key2->raw == cached_key->raw) && (key3->raw == cached_key->raw))
 301     {
 302       /* Both hit in the one-entry cache */
 303       result0->raw = cached_result->raw;
 304       result1->raw = cached_result->raw;
 305       result2->raw = cached_result->raw;
 306       result3->raw = cached_result->raw;
 307       *bucket0 = ~0;
 308       *bucket1 = ~0;
 309       *bucket2 = ~0;
 310       *bucket3 = ~0;
 311
 312     }
 313   else
 314     {
 315       BVT (clib_bihash_kv) kv0, kv1, kv2, kv3;
 316
 317       /*
 318        * Do a regular mac table lookup
 319        * Interleave lookups for packet 0 and packet 1
 320        */
 321       kv0.key = key0->raw;
 322       kv1.key = key1->raw;
 323       kv2.key = key2->raw;
 324       kv3.key = key3->raw;
 325       kv0.value = ~0ULL;
 326       kv1.value = ~0ULL;
 327       kv2.value = ~0ULL;
 328       kv3.value = ~0ULL;
 329
 330       BV (clib_bihash_search_inline) (mac_table, &kv0);
 331       BV (clib_bihash_search_inline) (mac_table, &kv1);
 332       BV (clib_bihash_search_inline) (mac_table, &kv2);
 333       BV (clib_bihash_search_inline) (mac_table, &kv3);
 334
 335       result0->raw = kv0.value;
 336       result1->raw = kv1.value;
 337       result2->raw = kv2.value;
 338       result3->raw = kv3.value;
 339
 340       /* Update one-entry cache */
 341       cached_key->raw = key1->raw;
 342       cached_result->raw = result1->raw;
 343     }
 344 }
 345
 346 void l2fib_clear_table (void);
 347
 348 void
 349 l2fib_add_entry (u64 mac,
 350                  u32 bd_index,
 351                  u32 sw_if_index, u32 static_mac, u32 drop_mac, u32 bvi_mac);
 352
 353 static inline void
 354 l2fib_add_fwd_entry (u64 mac, u32 bd_index, u32 sw_if_index, u32 static_mac,
 355                      u32 bvi_mac)
 356 {
 357   l2fib_add_entry (mac, bd_index, sw_if_index, static_mac, 0, bvi_mac);
 358 }
 359
 360 static inline void
 361 l2fib_add_filter_entry (u64 mac, u32 bd_index)
 362 {
 363   l2fib_add_entry (mac, bd_index, ~0, 1, 1, 0);
 364 }
 365
 366 u32 l2fib_del_entry (u64 mac, u32 bd_index);
 367
 368 void l2fib_start_ager_scan (vlib_main_t * vm);
 369
 370 void l2fib_flush_int_mac (vlib_main_t * vm, u32 sw_if_index);
 371
 372 void l2fib_flush_bd_mac (vlib_main_t * vm, u32 bd_index);
 373
 374 void l2fib_flush_all_mac (vlib_main_t * vm);
 375
 376 void
 377 l2fib_table_dump (u32 bd_index, l2fib_entry_key_t ** l2fe_key,
 378                   l2fib_entry_result_t ** l2fe_res);
 379
 380 u8 *format_vnet_sw_if_index_name_with_NA (u8 * s, va_list * args);
 381
 382 static_always_inline u8 *
 383 l2fib_swif_seq_num (u32 sw_if_index)
 384 {
 385   l2fib_main_t *mp = &l2fib_main;
 386   vec_validate (mp->swif_seq_num, sw_if_index);
 387   return vec_elt_at_index (mp->swif_seq_num, sw_if_index);
 388 }
 389
 390 BVT (clib_bihash) * get_mac_table (void);
 391
 392 #endif
 393
 394 /*
 395  * fd.io coding-style-patch-verification: ON
 396  *
 397  * Local Variables:
 398  * eval: (c-set-style "gnu")
 399  * End:
 400  */