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