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