FD.io VPP  v18.07-rc0-415-g6c78436
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 (512<<20)
29 
30 /* Ager scan interval is 1 minute for aging */
31 #define L2FIB_AGE_SCAN_INTERVAL (60.0)
32 
33 /* MAC event scan delay is 100 msec unless specified by MAC event client */
34 #define L2FIB_EVENT_SCAN_DELAY_DEFAULT (0.1)
35 
36 /* Max MACs in a event message is 100 unless specified by MAC event client */
37 #define L2FIB_EVENT_MAX_MACS_DEFAULT (100)
38 
39 /* MAC event learn limit is 1000 unless specified by MAC event client */
40 #define L2FIB_EVENT_LEARN_LIMIT_DEFAULT (1000)
41 
42 typedef struct
43 {
44 
45  /* hash table */
46  BVT (clib_bihash) mac_table;
47 
48  /* per swif vector of sequence number for interface based flush of MACs */
50 
51  /* last event or ager scan duration */
54 
55  /* delay between event scans, default to 100 msec */
57 
58  /* max macs in evet message, default to 100 entries */
60 
61  /* convenience variables */
64 } l2fib_main_t;
65 
67 
68 /*
69  * The L2fib key is the mac address and bridge domain ID
70  */
71 typedef struct
72 {
73  union
74  {
75  struct
76  {
78  u8 mac[6];
79  } fields;
80  struct
81  {
84  } words;
86  };
88 
90 
91 
92 typedef struct
93 {
94  union
95  {
96  struct
97  {
99  u8 bd;
100  };
102  };
104 
105 /*
106  * The l2fib entry results
107  */
108 typedef struct
109 {
110  union
111  {
112  struct
113  {
114  u32 sw_if_index; /* output sw_if_index (L3 intf if bvi==1) */
115 
116  u8 static_mac:1; /* static mac, no MAC move */
117  u8 age_not:1; /* not subject to age */
118  u8 bvi:1; /* mac is for a bridged virtual interface */
119  u8 filter:1; /* drop packets to/from this mac */
120  u8 lrn_evt:1; /* MAC learned to be sent in L2 MAC event */
121  u8 lrn_mov:1; /* MAC learned is a MAC move */
122  u8 unused:2;
123 
124  u8 timestamp; /* timestamp for aging */
125  l2fib_seq_num_t sn; /* bd/int seq num */
126  } fields;
128  };
130 
132 
133 /* L2 MAC event entry action enums (see mac_entry definition in l2.api) */
134 typedef enum
135 {
140 
141 /**
142  * Compute the hash for the given key and return
143  * the corresponding bucket index
144  */
147 {
148  u32 result;
149  u32 temp_a;
150  u32 temp_b;
151 
152  result = 0xa5a5a5a5; /* some seed */
153  temp_a = key->words.w0;
154  temp_b = key->words.w1;
155  hash_mix32 (temp_a, temp_b, result);
156 
157  return result % L2FIB_NUM_BUCKETS;
158 }
159 
160 /**
161  * make address sanitizer skip this:
162  * The 6-Bytes mac-address is cast into an 8-Bytes u64, with 2 additional Bytes.
163  * l2fib_make_key() does read those two Bytes but does not use them.
164  */
165 always_inline u64 __attribute__ ((no_sanitize_address))
166 l2fib_make_key (u8 * mac_address, u16 bd_index)
167 {
168  u64 temp;
169 
170  /*
171  * The mac address in memory is A:B:C:D:E:F
172  * The bd id in register is H:L
173  */
174 #if CLIB_ARCH_IS_LITTLE_ENDIAN
175  /*
176  * Create the in-register key as F:E:D:C:B:A:H:L
177  * In memory the key is L:H:A:B:C:D:E:F
178  */
179  temp = *((u64 *) (mac_address)) << 16;
180  temp = (temp & ~0xffff) | (u64) (bd_index);
181 #else
182  /*
183  * Create the in-register key as H:L:A:B:C:D:E:F
184  * In memory the key is H:L:A:B:C:D:E:F
185  */
186  temp = *((u64 *) (mac_address)) >> 16;
187  temp = temp | (((u64) bd_index) << 48);
188 #endif
189 
190  return temp;
191 }
192 
193 
194 
195 /**
196  * Lookup the entry for mac and bd_index in the mac table for 1 packet.
197  * Cached_key and cached_result are used as a one-entry cache.
198  * The function reads and updates them as needed.
199  *
200  * mac0 and bd_index0 are the keys. The entry is written to result0.
201  * If the entry was not found, result0 is set to ~0.
202  *
203  * key0 and bucket0 return with the computed key and hash bucket,
204  * convenient if the entry needs to be updated afterward.
205  * If the cached_result was used, bucket0 is set to ~0.
206  */
207 
209 l2fib_lookup_1 (BVT (clib_bihash) * mac_table,
210  l2fib_entry_key_t * cached_key,
211  l2fib_entry_result_t * cached_result,
212  u8 * mac0,
213  u16 bd_index0,
214  l2fib_entry_key_t * key0,
215  u32 * bucket0, l2fib_entry_result_t * result0)
216 {
217  /* set up key */
218  key0->raw = l2fib_make_key (mac0, bd_index0);
219  *bucket0 = ~0;
220 
221  if (key0->raw == cached_key->raw)
222  {
223  /* Hit in the one-entry cache */
224  result0->raw = cached_result->raw;
225  }
226  else
227  {
228  /* Do a regular mac table lookup */
229  BVT (clib_bihash_kv) kv;
230 
231  kv.key = key0->raw;
232  kv.value = ~0ULL;
233  BV (clib_bihash_search_inline) (mac_table, &kv);
234  result0->raw = kv.value;
235 
236  /* Update one-entry cache */
237  cached_key->raw = key0->raw;
238  cached_result->raw = result0->raw;
239  }
240 }
241 
242 
243 /**
244  * Lookup the entry for mac and bd_index in the mac table for 2 packets.
245  * The lookups for the two packets are interleaved.
246  *
247  * Cached_key and cached_result are used as a one-entry cache.
248  * The function reads and updates them as needed.
249  *
250  * mac0 and bd_index0 are the keys. The entry is written to result0.
251  * If the entry was not found, result0 is set to ~0. The same
252  * holds for mac1/bd_index1/result1.
253  */
255 l2fib_lookup_2 (BVT (clib_bihash) * mac_table,
256  l2fib_entry_key_t * cached_key,
257  l2fib_entry_result_t * cached_result,
258  u8 * mac0,
259  u8 * mac1,
260  u16 bd_index0,
261  u16 bd_index1,
262  l2fib_entry_key_t * key0,
263  l2fib_entry_key_t * key1,
264  u32 * bucket0,
265  u32 * bucket1,
266  l2fib_entry_result_t * result0,
267  l2fib_entry_result_t * result1)
268 {
269  /* set up key */
270  key0->raw = l2fib_make_key (mac0, bd_index0);
271  key1->raw = l2fib_make_key (mac1, bd_index1);
272 
273  if ((key0->raw == cached_key->raw) && (key1->raw == cached_key->raw))
274  {
275  /* Both hit in the one-entry cache */
276  result0->raw = cached_result->raw;
277  result1->raw = cached_result->raw;
278  *bucket0 = ~0;
279  *bucket1 = ~0;
280 
281  }
282  else
283  {
284  BVT (clib_bihash_kv) kv0, kv1;
285 
286  /*
287  * Do a regular mac table lookup
288  * Interleave lookups for packet 0 and packet 1
289  */
290  kv0.key = key0->raw;
291  kv1.key = key1->raw;
292  kv0.value = ~0ULL;
293  kv1.value = ~0ULL;
294 
295  BV (clib_bihash_search_inline) (mac_table, &kv0);
296  BV (clib_bihash_search_inline) (mac_table, &kv1);
297 
298  result0->raw = kv0.value;
299  result1->raw = kv1.value;
300 
301  /* Update one-entry cache */
302  cached_key->raw = key1->raw;
303  cached_result->raw = result1->raw;
304  }
305 }
306 
308 l2fib_lookup_4 (BVT (clib_bihash) * mac_table,
309  l2fib_entry_key_t * cached_key,
310  l2fib_entry_result_t * cached_result,
311  u8 * mac0,
312  u8 * mac1,
313  u8 * mac2,
314  u8 * mac3,
315  u16 bd_index0,
316  u16 bd_index1,
317  u16 bd_index2,
318  u16 bd_index3,
319  l2fib_entry_key_t * key0,
320  l2fib_entry_key_t * key1,
321  l2fib_entry_key_t * key2,
322  l2fib_entry_key_t * key3,
323  u32 * bucket0,
324  u32 * bucket1,
325  u32 * bucket2,
326  u32 * bucket3,
327  l2fib_entry_result_t * result0,
328  l2fib_entry_result_t * result1,
329  l2fib_entry_result_t * result2,
330  l2fib_entry_result_t * result3)
331 {
332  /* set up key */
333  key0->raw = l2fib_make_key (mac0, bd_index0);
334  key1->raw = l2fib_make_key (mac1, bd_index1);
335  key2->raw = l2fib_make_key (mac2, bd_index2);
336  key3->raw = l2fib_make_key (mac3, bd_index3);
337 
338  if ((key0->raw == cached_key->raw) && (key1->raw == cached_key->raw) &&
339  (key2->raw == cached_key->raw) && (key3->raw == cached_key->raw))
340  {
341  /* Both hit in the one-entry cache */
342  result0->raw = cached_result->raw;
343  result1->raw = cached_result->raw;
344  result2->raw = cached_result->raw;
345  result3->raw = cached_result->raw;
346  *bucket0 = ~0;
347  *bucket1 = ~0;
348  *bucket2 = ~0;
349  *bucket3 = ~0;
350 
351  }
352  else
353  {
354  BVT (clib_bihash_kv) kv0, kv1, kv2, kv3;
355 
356  /*
357  * Do a regular mac table lookup
358  * Interleave lookups for packet 0 and packet 1
359  */
360  kv0.key = key0->raw;
361  kv1.key = key1->raw;
362  kv2.key = key2->raw;
363  kv3.key = key3->raw;
364  kv0.value = ~0ULL;
365  kv1.value = ~0ULL;
366  kv2.value = ~0ULL;
367  kv3.value = ~0ULL;
368 
369  BV (clib_bihash_search_inline) (mac_table, &kv0);
370  BV (clib_bihash_search_inline) (mac_table, &kv1);
371  BV (clib_bihash_search_inline) (mac_table, &kv2);
372  BV (clib_bihash_search_inline) (mac_table, &kv3);
373 
374  result0->raw = kv0.value;
375  result1->raw = kv1.value;
376  result2->raw = kv2.value;
377  result3->raw = kv3.value;
378 
379  /* Update one-entry cache */
380  cached_key->raw = key1->raw;
381  cached_result->raw = result1->raw;
382  }
383 }
384 
385 void l2fib_clear_table (void);
386 
387 void
388 l2fib_add_entry (u8 * mac,
389  u32 bd_index,
390  u32 sw_if_index, u8 static_mac, u8 drop_mac, u8 bvi_mac);
391 
392 static inline void
393 l2fib_add_fwd_entry (u8 * mac, u32 bd_index, u32 sw_if_index, u8 static_mac,
394  u8 bvi_mac)
395 {
396  l2fib_add_entry (mac, bd_index, sw_if_index, static_mac, 0, bvi_mac);
397 }
398 
399 static inline void
400 l2fib_add_filter_entry (u8 * mac, u32 bd_index)
401 {
402  l2fib_add_entry (mac, bd_index, ~0, 1, 1, 0);
403 }
404 
405 u32 l2fib_del_entry (u8 * mac, u32 bd_index, u32 sw_if_index);
406 
408 
409 void l2fib_flush_int_mac (vlib_main_t * vm, u32 sw_if_index);
410 
411 void l2fib_flush_bd_mac (vlib_main_t * vm, u32 bd_index);
412 
413 void l2fib_flush_all_mac (vlib_main_t * vm);
414 
415 void
416 l2fib_table_dump (u32 bd_index, l2fib_entry_key_t ** l2fe_key,
417  l2fib_entry_result_t ** l2fe_res);
418 
419 u8 *format_vnet_sw_if_index_name_with_NA (u8 * s, va_list * args);
420 
422 l2fib_swif_seq_num (u32 sw_if_index)
423 {
424  l2fib_main_t *mp = &l2fib_main;
425  return vec_elt_at_index (mp->swif_seq_num, sw_if_index);
426 }
427 
430 {
431  l2fib_main_t *mp = &l2fib_main;
432  vec_validate (mp->swif_seq_num, sw_if_index);
433  return l2fib_swif_seq_num (sw_if_index);
434 }
435 
436 BVT (clib_bihash) * get_mac_table (void);
437 
438 #endif
439 
440 /*
441  * fd.io coding-style-patch-verification: ON
442  *
443  * Local Variables:
444  * eval: (c-set-style "gnu")
445  * End:
446  */
#define vec_validate(V, I)
Make sure vector is long enough for given index (no header, unspecified alignment) ...
Definition: vec.h:437
f64 evt_scan_duration
Definition: l2_fib.h:52
vlib_main_t * vlib_main
Definition: l2_fib.h:62
vnet_main_t * vnet_main
Definition: l2_fib.h:63
unsigned long u64
Definition: types.h:89
u32 l2fib_del_entry(u8 *mac, u32 bd_index, u32 sw_if_index)
Delete an entry from the l2fib.
Definition: l2_fib.c:662
u32 w1
Definition: l2_fib.h:83
static_always_inline u8 * l2fib_swif_seq_num(u32 sw_if_index)
Definition: l2_fib.h:422
u32 max_macs_in_event
Definition: l2_fib.h:59
Definition: l2_fib.h:108
unsigned char u8
Definition: types.h:56
double f64
Definition: types.h:142
u32 w0
Definition: l2_fib.h:82
#define static_always_inline
Definition: clib.h:93
#define always_inline
Definition: clib.h:92
#define vec_elt_at_index(v, i)
Get vector value at index i checking that i is in bounds.
void l2fib_flush_all_mac(vlib_main_t *vm)
Flush all non static MACs - flushes all valid BDs.
Definition: l2_fib.c:802
unsigned int u32
Definition: types.h:88
void l2fib_add_entry(u8 *mac, u32 bd_index, u32 sw_if_index, u8 static_mac, u8 drop_mac, u8 bvi_mac)
Add an entry to the l2fib.
Definition: l2_fib.c:375
f64 event_scan_delay
Definition: l2_fib.h:56
static_always_inline u8 * l2fib_valid_swif_seq_num(u32 sw_if_index)
Definition: l2_fib.h:429
unsigned short u16
Definition: types.h:57
BVT(clib_bihash)*get_mac_table(void)
Definition: l2_fib.c:944
STATIC_ASSERT_SIZEOF(l2fib_entry_key_t, 8)
int clib_bihash_search_inline(clib_bihash *h, clib_bihash_kv *in_out_kv)
Search a bi-hash table.
#define L2FIB_NUM_BUCKETS
Definition: l2_fib.h:27
static void l2fib_add_fwd_entry(u8 *mac, u32 bd_index, u32 sw_if_index, u8 static_mac, u8 bvi_mac)
Definition: l2_fib.h:393
u64 raw
Definition: l2_fib.h:127
u32 sw_if_index
Definition: l2_fib.h:114
struct l2fib_entry_key_t::@235::@238 words
vlib_main_t * vm
Definition: buffer.c:294
l2fib_seq_num_t sn
Definition: l2_fib.h:125
u8 * swif_seq_num
Definition: l2_fib.h:49
f64 age_scan_duration
Definition: l2_fib.h:53
void l2fib_flush_bd_mac(vlib_main_t *vm, u32 bd_index)
Flush all non static MACs in a bridge domain.
Definition: l2_fib.c:791
#define hash_mix32(a0, b0, c0)
Definition: hash.h:539
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:255
void l2fib_clear_table(void)
Definition: l2_fib.c:317
Definition: l2_fib.h:71
static void l2fib_add_filter_entry(u8 *mac, u32 bd_index)
Definition: l2_fib.h:400
void l2fib_table_dump(u32 bd_index, l2fib_entry_key_t **l2fe_key, l2fib_entry_result_t **l2fe_res)
Definition: l2_fib.c:86
void l2fib_flush_int_mac(vlib_main_t *vm, u32 sw_if_index)
Flush all non static MACs from an interface.
Definition: l2_fib.c:781
u8 timestamp
Definition: l2_fib.h:124
l2_mac_event_action_t
Definition: l2_fib.h:134
u8 * format_vnet_sw_if_index_name_with_NA(u8 *s, va_list *args)
Format sw_if_index.
Definition: l2_fib.c:70
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:146
static u64 l2fib_make_key(u8 *mac_address, u16 bd_index)
make address sanitizer skip this: The 6-Bytes mac-address is cast into an 8-Bytes u64...
Definition: l2_fib.h:166
u16 bd_index
Definition: l2_fib.h:77
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:308
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:209
l2fib_main_t l2fib_main
Definition: l2_fib.c:55
u64 raw
Definition: l2_fib.h:85
void l2fib_start_ager_scan(vlib_main_t *vm)
Kick off ager to scan MACs to age/delete MAC entries.
Definition: l2_fib.c:758