FD.io VPP  v17.04.2-2-ga8f93f8
Vector Packet Processing
l2_fib.h
Go to the documentation of this file.
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  {
40  u8 mac[6];
41  } fields;
42  struct
43  {
46  } words;
48  };
50 
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;
73  };
75 
77 
78 /**
79  * Compute the hash for the given key and return
80  * the corresponding bucket index
81  */
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 
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 
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  */
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 
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 
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  */
struct l2fib_entry_key_t::@146::@149 words
u32 w1
Definition: l2_fib.h:45
Definition: l2_fib.h:56
u32 w0
Definition: l2_fib.h:44
#define static_always_inline
Definition: clib.h:85
#define always_inline
Definition: clib.h:84
unsigned long u64
Definition: types.h:89
void l2fib_add_entry(u64 mac, u32 bd_index, u32 sw_if_index, u32 static_mac, u32 drop_mac, u32 bvi_mac)
Add an entry to the l2fib.
Definition: l2_fib.c:315
u8 int_sn
Definition: l2_fib.h:69
BVT(clib_bihash)*get_mac_table(void)
Definition: l2_fib.c:852
STATIC_ASSERT_SIZEOF(l2fib_entry_key_t, 8)
#define L2FIB_NUM_BUCKETS
Definition: l2_fib.h:27
u64 raw
Definition: l2_fib.h:72
u32 sw_if_index
Definition: l2_fib.h:62
u32 l2fib_del_entry(u64 mac, u32 bd_index)
Delete an entry from the l2fib.
Definition: l2_fib.c:622
void l2fib_flush_bd_mac(vlib_main_t *vm, u32 bd_index)
Flush all learned MACs in a bridge domain.
Definition: l2_fib.c:751
#define hash_mix32(a0, b0, c0)
Definition: hash.h:515
static_always_inline void l2fib_lookup_2(BVT(clib_bihash)*mac_table, l2fib_entry_key_t *cached_key, l2fib_entry_result_t *cached_result, u8 *mac0, u8 *mac1, u16 bd_index0, u16 bd_index1, l2fib_entry_key_t *key0, l2fib_entry_key_t *key1, u32 *bucket0, u32 *bucket1, l2fib_entry_result_t *result0, l2fib_entry_result_t *result1)
Lookup the entry for mac and bd_index in the mac table for 2 packets.
Definition: l2_fib.h:187
unsigned int u32
Definition: types.h:88
Definition: l2_fib.h:33
void l2fib_clear_table(uint keep_static)
Definition: l2_fib.c:260
void l2fib_table_dump(u32 bd_index, l2fib_entry_key_t **l2fe_key, l2fib_entry_result_t **l2fe_res)
Definition: l2_fib.c:73
void l2fib_flush_int_mac(vlib_main_t *vm, u32 sw_if_index)
Flush all learned MACs from an interface.
Definition: l2_fib.c:739
u8 timestamp
Definition: l2_fib.h:68
unsigned short u16
Definition: types.h:57
unsigned char u8
Definition: types.h:56
u8 * format_vnet_sw_if_index_name_with_NA(u8 *s, va_list *args)
Format sw_if_index.
Definition: l2_fib.c:60
static u32 l2fib_compute_hash_bucket(l2fib_entry_key_t *key)
Compute the hash for the given key and return the corresponding bucket index.
Definition: l2_fib.h:83
static u64 l2fib_make_key(u8 *mac_address, u16 bd_index)
Definition: l2_fib.h:98
u16 bd_index
Definition: l2_fib.h:39
static_always_inline void l2fib_lookup_4(BVT(clib_bihash)*mac_table, l2fib_entry_key_t *cached_key, l2fib_entry_result_t *cached_result, u8 *mac0, u8 *mac1, u8 *mac2, u8 *mac3, u16 bd_index0, u16 bd_index1, u16 bd_index2, u16 bd_index3, l2fib_entry_key_t *key0, l2fib_entry_key_t *key1, l2fib_entry_key_t *key2, l2fib_entry_key_t *key3, u32 *bucket0, u32 *bucket1, u32 *bucket2, u32 *bucket3, l2fib_entry_result_t *result0, l2fib_entry_result_t *result1, l2fib_entry_result_t *result2, l2fib_entry_result_t *result3)
Definition: l2_fib.h:240
static_always_inline void l2fib_lookup_1(BVT(clib_bihash)*mac_table, l2fib_entry_key_t *cached_key, l2fib_entry_result_t *cached_result, u8 *mac0, u16 bd_index0, l2fib_entry_key_t *key0, u32 *bucket0, l2fib_entry_result_t *result0)
Lookup the entry for mac and bd_index in the mac table for 1 packet.
Definition: l2_fib.h:141
u8 bd_sn
Definition: l2_fib.h:70
u64 raw
Definition: l2_fib.h:47
void l2fib_start_ager_scan(vlib_main_t *vm)
Kick off ager to scan MACs to age/delete MAC entries.
Definition: l2_fib.c:720