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