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   union {
  35     struct {
  36       u16 bd_index;
  37       u8  mac[6];
  38     } fields;
  39     struct {
  40       u32 w0;
  41       u32 w1;
  42     } words;
  43     u64 raw;
  44   };
  45 } l2fib_entry_key_t;
  46
  47 /*
  48  * The l2fib entry results
  49  */
  50 typedef struct {
  51   union {
  52     struct {
  53       u32 sw_if_index;   // output sw_if_index (L3 interface if bvi==1)
  54
  55       u8  static_mac:1;  // static mac, no dataplane learning
  56       u8  bvi:1;         // mac is for a bridged virtual interface
  57       u8  filter:1;      // drop packets to/from this mac
  58       u8  refresh:1;     // refresh flag for aging
  59       u8  unused1:4;
  60       u8  timestamp;     // timestamp for aging
  61       u16 unused2;
  62     } fields;
  63     u64 raw;
  64   };
  65 } l2fib_entry_result_t;
  66
  67
  68 // Compute the hash for the given key and return the corresponding bucket index
  69 always_inline
  70 u32 l2fib_compute_hash_bucket (l2fib_entry_key_t *key) {
  71   u32 result;
  72   u32 temp_a;
  73   u32 temp_b;
  74
  75   result = 0xa5a5a5a5;  // some seed
  76   temp_a = key->words.w0;
  77   temp_b = key->words.w1;
  78   hash_mix32(temp_a, temp_b, result);
  79
  80   return result % L2FIB_NUM_BUCKETS;
  81 }
  82
  83 always_inline
  84 u64 l2fib_make_key (u8 * mac_address, u16 bd_index) {
  85   u64 temp;
  86
  87   // The mac address in memory is A:B:C:D:E:F
  88   // The bd id in register is H:L
  89 #if CLIB_ARCH_IS_LITTLE_ENDIAN
  90   // Create the in-register key as F:E:D:C:B:A:H:L
  91   // In memory the key is L:H:A:B:C:D:E:F
  92   temp = *((u64 *)(mac_address - 2));
  93   temp = (temp & ~0xffff) | (u64)(bd_index);
  94 #else
  95   // Create the in-register key as H:L:A:B:C:D:E:F
  96   // In memory the key is H:L:A:B:C:D:E:F
  97   temp = *((u64 *)(mac_address)) >> 16;
  98   temp = temp | (bd_index << 48);
  99 #endif
 100
 101   return temp;
 102 }
 103
 104
 105
 106 // Lookup the entry for mac and bd_index in the mac table for 1 packet.
 107 // Cached_key and cached_result are used as a one-entry cache.
 108 // The function reads and updates them as needed.
 109 //
 110 // mac0 and bd_index0 are the keys. The entry is written to result0.
 111 // If the entry was not found, result0 is set to ~0.
 112 //
 113 // key0 and bucket0 return with the computed key and hash bucket,
 114 // convenient if the entry needs to be updated afterward.
 115 // If the cached_result was used, bucket0 is set to ~0.
 116
 117 static_always_inline void
 118 l2fib_lookup_1 (BVT(clib_bihash) * mac_table,
 119                 l2fib_entry_key_t * cached_key,
 120                 l2fib_entry_result_t * cached_result,
 121                 u8 * mac0,
 122                 u16 bd_index0,
 123                 l2fib_entry_key_t * key0,
 124                 u32 * bucket0,
 125                 l2fib_entry_result_t *result0)
 126 {
 127   // set up key
 128   key0->raw = l2fib_make_key (mac0, bd_index0);
 129   *bucket0 = ~0;
 130
 131   if (key0->raw == cached_key->raw) {
 132     // Hit in the one-entry cache
 133     result0->raw = cached_result->raw;
 134   } else {
 135     // Do a regular mac table lookup
 136     BVT(clib_bihash_kv) kv;
 137
 138     kv.key = key0->raw;
 139     kv.value = ~0ULL;
 140     BV(clib_bihash_search_inline) (mac_table, &kv);
 141     result0->raw = kv.value;
 142
 143     // Update one-entry cache
 144     cached_key->raw = key0->raw;
 145     cached_result->raw = result0->raw;
 146   }
 147 }
 148
 149
 150 // Lookup the entry for mac and bd_index in the mac table for 2 packets.
 151 // The lookups for the two packets are interleaved.
 152 //
 153 // Cached_key and cached_result are used as a one-entry cache.
 154 // The function reads and updates them as needed.
 155 //
 156 // mac0 and bd_index0 are the keys. The entry is written to result0.
 157 // If the entry was not found, result0 is set to ~0. The same
 158 // holds for mac1/bd_index1/result1.
 159
 160 static_always_inline void
 161 l2fib_lookup_2 (BVT(clib_bihash) * mac_table,
 162                 l2fib_entry_key_t * cached_key,
 163                 l2fib_entry_result_t * cached_result,
 164                 u8 * mac0,
 165                 u8 * mac1,
 166                 u16 bd_index0,
 167                 u16 bd_index1,
 168                 l2fib_entry_key_t * key0,
 169                 l2fib_entry_key_t * key1,
 170                 u32 * bucket0,
 171                 u32 * bucket1,
 172                 l2fib_entry_result_t *result0,
 173                 l2fib_entry_result_t *result1)
 174 {
 175   // set up key
 176   key0->raw = l2fib_make_key (mac0, bd_index0);
 177   key1->raw = l2fib_make_key (mac1, bd_index1);
 178
 179   if ((key0->raw == cached_key->raw) &&
 180        (key1->raw == cached_key->raw)) {
 181     // Both hit in the one-entry cache
 182     result0->raw = cached_result->raw;
 183     result1->raw = cached_result->raw;
 184     *bucket0 = ~0;
 185     *bucket1 = ~0;
 186
 187   } else {
 188     BVT(clib_bihash_kv) kv0, kv1;
 189
 190     // Do a regular mac table lookup
 191     // Interleave lookups for packet 0 and packet 1
 192     kv0.key = key0->raw;
 193     kv1.key = key1->raw;
 194     kv0.value = ~0ULL;
 195     kv1.value = ~0ULL;
 196
 197     BV(clib_bihash_search_inline) (mac_table, &kv0);
 198     BV(clib_bihash_search_inline) (mac_table, &kv1);
 199
 200     result0->raw = kv0.value;
 201     result1->raw = kv1.value;
 202
 203     // Update one-entry cache
 204     cached_key->raw = key1->raw;
 205     cached_result->raw = result1->raw;
 206   }
 207 }
 208
 209
 210 BVT(clib_bihash) *get_mac_table(void);
 211 void l2fib_clear_table (uint keep_static);
 212 void l2fib_add_entry (u64   mac,
 213                       u32   bd_index,
 214                       u32   sw_if_index,
 215                       u32   static_mac,
 216                       u32   drop_mac,
 217                       u32   bvi_mac);
 218 u32 l2fib_del_entry (u64   mac,
 219                      u32   bd_index);
 220
 221 void l2fib_table_dump (u32 bd_index, l2fib_entry_key_t **l2fe_key,
 222                       l2fib_entry_result_t **l2fe_res);
 223
 224 u8 * format_vnet_sw_if_index_name_with_NA (u8 * s, va_list * args);
 225
 226 #endif