FD.io VPP  v21.01.1
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 (256 * 1024)
28 #define L2FIB_MEMORY_SIZE (128<<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  /* number of buckets in the hash table */
50 
51  /* hash table memory size */
53 
54  /* hash table initialized */
56 
57  /* last event or ager scan duration */
60 
61  /* delay between event scans, default to 100 msec */
63 
64  /* max macs in event message, default to 100 entries */
66 
67  /* convenience variables */
70 } l2fib_main_t;
71 
73 
74 /*
75  * The L2fib key is the mac address and bridge domain ID
76  */
77 typedef struct
78 {
79  union
80  {
81  struct
82  {
84  u8 mac[6];
85  } fields;
86  struct
87  {
90  } words;
92  };
94 
96 
97 /**
98  * A combined representation of the sequence number associated
99  * with the interface and the BD.
100  * The BD is in higher bits, the interface in the lower bits, but
101  * the order is not important.
102  *
103  * It's convenient to represent this as an union of two u8s,
104  * but then in the DP one is forced to do short writes, followed
105  * by long reads, which is a sure thing for a stall
106  */
108 
109 static_always_inline l2fib_seq_num_t
110 l2_fib_mk_seq_num (u8 bd_sn, u8 if_sn)
111 {
112  return (((u16) bd_sn) << 8) | if_sn;
113 }
114 
115 static_always_inline l2fib_seq_num_t
116 l2_fib_update_seq_num (l2fib_seq_num_t sn, u8 if_sn)
117 {
118  sn &= 0xff00;
119  sn |= if_sn;
120 
121  return (sn);
122 }
123 
124 extern void l2_fib_extract_seq_num (l2fib_seq_num_t sn, u8 * bd_sn,
125  u8 * if_sn);
126 extern u8 *format_l2_fib_seq_num (u8 * s, va_list * a);
127 
128 /**
129  * Flags associated with an L2 Fib Entry
130  * - static mac, no MAC move
131  * - not subject to age
132  * - mac is for a bridged virtual interface
133  * - drop packets to/from this mac
134  * - MAC learned to be sent in L2 MAC event
135  * -MAC learned is a MAC move
136  */
137 #define foreach_l2fib_entry_result_attr \
138  _(STATIC, 0, "static") \
139  _(AGE_NOT, 1, "age-not") \
140  _(BVI, 2, "bvi") \
141  _(FILTER, 3, "filter") \
142  _(LRN_EVT, 4, "learn-event") \
143  _(LRN_MOV, 5, "learn-move")
144 
146 {
148 #define _(a,v,s) L2FIB_ENTRY_RESULT_FLAG_##a = (1 << v),
150 #undef _
151 } __attribute__ ((packed)) l2fib_entry_result_flags_t;
152 
153 STATIC_ASSERT_SIZEOF (l2fib_entry_result_flags_t, 1);
154 
155 extern u8 *format_l2fib_entry_result_flags (u8 * s, va_list * args);
156 
157 /*
158  * The l2fib entry results
159  */
160 typedef struct l2fib_entry_result_t_
161 {
162  union
163  {
164  struct
165  {
166  u32 sw_if_index; /* output sw_if_index (L3 intf if bvi==1) */
167  l2fib_entry_result_flags_t flags;
168 
169  u8 timestamp; /* timestamp for aging */
170  l2fib_seq_num_t sn; /* bd/int seq num */
171  } fields;
173  };
175 
177 
178 #define _(a,v,s) \
179  always_inline int \
180  l2fib_entry_result_is_set_##a (const l2fib_entry_result_t *r) { \
181  return (r->fields.flags & L2FIB_ENTRY_RESULT_FLAG_##a); \
182  }
184 #undef _
185 #define _(a,v,s) \
186  always_inline void \
187  l2fib_entry_result_set_##a (l2fib_entry_result_t *r) { \
188  r->fields.flags |= L2FIB_ENTRY_RESULT_FLAG_##a; \
189  }
191 #undef _
192 #define _(a,v,s) \
193  always_inline void \
194  l2fib_entry_result_clear_##a (l2fib_entry_result_t *r) { \
195  r->fields.flags &= ~L2FIB_ENTRY_RESULT_FLAG_##a; \
196  }
198 #undef _
199  static inline void
201  l2fib_entry_result_flags_t bits)
202 {
203  r->fields.flags |= bits;
204 }
205 
206 static inline void
208  l2fib_entry_result_flags_t bits)
209 {
210  r->fields.flags &= ~bits;
211 }
212 
213 /* L2 MAC event entry action enums (see mac_entry definition in l2.api) */
214 typedef enum
215 {
220 
221 /**
222  * Compute the hash for the given key and return
223  * the corresponding bucket index
224  */
227 {
228  u32 result;
229  u32 temp_a;
230  u32 temp_b;
231 
232  result = 0xa5a5a5a5; /* some seed */
233  temp_a = key->words.w0;
234  temp_b = key->words.w1;
235  hash_mix32 (temp_a, temp_b, result);
236 
237  return result % L2FIB_NUM_BUCKETS;
238 }
239 
241 l2fib_make_key (const u8 * mac_address, u16 bd_index)
242 {
243  u64 temp;
244 
245  /*
246  * The mac address in memory is A:B:C:D:E:F
247  * The bd id in register is H:L
248  */
249 #if CLIB_ARCH_IS_LITTLE_ENDIAN
250  /*
251  * Create the in-register key as F:E:D:C:B:A:H:L
252  * In memory the key is L:H:A:B:C:D:E:F
253  */
254  temp = CLIB_MEM_OVERFLOW_LOAD (*, (u64 *) mac_address) << 16;
255  temp = (temp & ~0xffff) | (u64) (bd_index);
256 #else
257  /*
258  * Create the in-register key as H:L:A:B:C:D:E:F
259  * In memory the key is H:L:A:B:C:D:E:F
260  */
261  temp = CLIB_MEM_OVERFLOW_LOAD (*, (u64 *) mac_address) >> 16;
262  temp = temp | (((u64) bd_index) << 48);
263 #endif
264 
265  return temp;
266 }
267 
268 
269 
270 /**
271  * Lookup the entry for mac and bd_index in the mac table for 1 packet.
272  * Cached_key and cached_result are used as a one-entry cache.
273  * The function reads and updates them as needed.
274  *
275  * mac0 and bd_index0 are the keys. The entry is written to result0.
276  * If the entry was not found, result0 is set to ~0.
277  *
278  * key0 return with the computed key, convenient if the entry needs,
279  * to be updated afterward.
280  */
281 
283 l2fib_lookup_1 (BVT (clib_bihash) * mac_table,
284  l2fib_entry_key_t * cached_key,
285  l2fib_entry_result_t * cached_result,
286  u8 * mac0,
287  u16 bd_index0,
288  l2fib_entry_key_t * key0, l2fib_entry_result_t * result0)
289 {
290  /* set up key */
291  key0->raw = l2fib_make_key (mac0, bd_index0);
292 
293  if (key0->raw == cached_key->raw)
294  {
295  /* Hit in the one-entry cache */
296  result0->raw = cached_result->raw;
297  }
298  else
299  {
300  /* Do a regular mac table lookup */
301  BVT (clib_bihash_kv) kv;
302 
303  kv.key = key0->raw;
304  kv.value = ~0ULL;
305  BV (clib_bihash_search_inline) (mac_table, &kv);
306  result0->raw = kv.value;
307 
308  /* Update one-entry cache */
309  cached_key->raw = key0->raw;
310  cached_result->raw = result0->raw;
311  }
312 }
313 
314 
315 /**
316  * Lookup the entry for mac and bd_index in the mac table for 2 packets.
317  * The lookups for the two packets are interleaved.
318  *
319  * Cached_key and cached_result are used as a one-entry cache.
320  * The function reads and updates them as needed.
321  *
322  * mac0 and bd_index0 are the keys. The entry is written to result0.
323  * If the entry was not found, result0 is set to ~0. The same
324  * holds for mac1/bd_index1/result1.
325  */
327 l2fib_lookup_2 (BVT (clib_bihash) * mac_table,
328  l2fib_entry_key_t * cached_key,
329  l2fib_entry_result_t * cached_result,
330  u8 * mac0,
331  u8 * mac1,
332  u16 bd_index0,
333  u16 bd_index1,
334  l2fib_entry_key_t * key0,
335  l2fib_entry_key_t * key1,
336  l2fib_entry_result_t * result0,
337  l2fib_entry_result_t * result1)
338 {
339  /* set up key */
340  key0->raw = l2fib_make_key (mac0, bd_index0);
341  key1->raw = l2fib_make_key (mac1, bd_index1);
342 
343  if ((key0->raw == cached_key->raw) && (key1->raw == cached_key->raw))
344  {
345  /* Both hit in the one-entry cache */
346  result0->raw = cached_result->raw;
347  result1->raw = cached_result->raw;
348  }
349  else
350  {
351  BVT (clib_bihash_kv) kv0, kv1;
352 
353  /*
354  * Do a regular mac table lookup
355  * Interleave lookups for packet 0 and packet 1
356  */
357  kv0.key = key0->raw;
358  kv1.key = key1->raw;
359  kv0.value = ~0ULL;
360  kv1.value = ~0ULL;
361 
362  BV (clib_bihash_search_inline) (mac_table, &kv0);
363  BV (clib_bihash_search_inline) (mac_table, &kv1);
364 
365  result0->raw = kv0.value;
366  result1->raw = kv1.value;
367 
368  /* Update one-entry cache */
369  cached_key->raw = key1->raw;
370  cached_result->raw = result1->raw;
371  }
372 }
373 
375 l2fib_lookup_4 (BVT (clib_bihash) * mac_table,
376  l2fib_entry_key_t * cached_key,
377  l2fib_entry_result_t * cached_result,
378  const u8 * mac0,
379  const u8 * mac1,
380  const u8 * mac2,
381  const u8 * mac3,
382  u16 bd_index0,
383  u16 bd_index1,
384  u16 bd_index2,
385  u16 bd_index3,
386  l2fib_entry_key_t * key0,
387  l2fib_entry_key_t * key1,
388  l2fib_entry_key_t * key2,
389  l2fib_entry_key_t * key3,
390  l2fib_entry_result_t * result0,
391  l2fib_entry_result_t * result1,
392  l2fib_entry_result_t * result2,
393  l2fib_entry_result_t * result3)
394 {
395  /* set up key */
396  key0->raw = l2fib_make_key (mac0, bd_index0);
397  key1->raw = l2fib_make_key (mac1, bd_index1);
398  key2->raw = l2fib_make_key (mac2, bd_index2);
399  key3->raw = l2fib_make_key (mac3, bd_index3);
400 
401  if ((key0->raw == cached_key->raw) && (key1->raw == cached_key->raw) &&
402  (key2->raw == cached_key->raw) && (key3->raw == cached_key->raw))
403  {
404  /* Both hit in the one-entry cache */
405  result0->raw = cached_result->raw;
406  result1->raw = cached_result->raw;
407  result2->raw = cached_result->raw;
408  result3->raw = cached_result->raw;
409  }
410  else
411  {
412  BVT (clib_bihash_kv) kv0, kv1, kv2, kv3;
413 
414  /*
415  * Do a regular mac table lookup
416  * Interleave lookups for packet 0 and packet 1
417  */
418  kv0.key = key0->raw;
419  kv1.key = key1->raw;
420  kv2.key = key2->raw;
421  kv3.key = key3->raw;
422  kv0.value = ~0ULL;
423  kv1.value = ~0ULL;
424  kv2.value = ~0ULL;
425  kv3.value = ~0ULL;
426 
427  BV (clib_bihash_search_inline) (mac_table, &kv0);
428  BV (clib_bihash_search_inline) (mac_table, &kv1);
429  BV (clib_bihash_search_inline) (mac_table, &kv2);
430  BV (clib_bihash_search_inline) (mac_table, &kv3);
431 
432  result0->raw = kv0.value;
433  result1->raw = kv1.value;
434  result2->raw = kv2.value;
435  result3->raw = kv3.value;
436 
437  /* Update one-entry cache */
438  cached_key->raw = key1->raw;
439  cached_result->raw = result1->raw;
440  }
441 }
442 
443 void l2fib_clear_table (void);
444 
445 void l2fib_table_init (void);
446 
447 void
448 l2fib_add_entry (const u8 * mac,
449  u32 bd_index,
450  u32 sw_if_index, l2fib_entry_result_flags_t flags);
451 
452 static inline void
453 l2fib_add_filter_entry (const u8 * mac, u32 bd_index)
454 {
455  l2fib_add_entry (mac, bd_index, ~0,
456  (L2FIB_ENTRY_RESULT_FLAG_FILTER |
457  L2FIB_ENTRY_RESULT_FLAG_STATIC));
458 }
459 
460 u32 l2fib_del_entry (const u8 * mac, u32 bd_index, u32 sw_if_index);
461 
463 
464 void l2fib_flush_int_mac (vlib_main_t * vm, u32 sw_if_index);
465 
466 void l2fib_flush_bd_mac (vlib_main_t * vm, u32 bd_index);
467 
468 void l2fib_flush_all_mac (vlib_main_t * vm);
469 
470 void
471 l2fib_table_dump (u32 bd_index, l2fib_entry_key_t ** l2fe_key,
472  l2fib_entry_result_t ** l2fe_res);
473 
474 u8 *format_vnet_sw_if_index_name_with_NA (u8 * s, va_list * args);
475 
476 BVT (clib_bihash) * get_mac_table (void);
477 
478 #endif
479 
480 /*
481  * fd.io coding-style-patch-verification: ON
482  *
483  * Local Variables:
484  * eval: (c-set-style "gnu")
485  * End:
486  */
u16 l2fib_seq_num_t
A combined representation of the sequence number associated with the interface and the BD...
Definition: l2_fib.h:107
f64 evt_scan_duration
Definition: l2_fib.h:58
struct l2fib_entry_result_t_::@471::@473 fields
vlib_main_t * vlib_main
Definition: l2_fib.h:68
a
Definition: bitmap.h:544
vnet_main_t * vnet_main
Definition: l2_fib.h:69
unsigned long u64
Definition: types.h:89
u64 raw
Definition: l2_fib.h:172
u32 w1
Definition: l2_fib.h:89
l2fib_entry_result_flags_t flags
Definition: l2_fib.h:167
u32 max_macs_in_event
Definition: l2_fib.h:65
enum l2fib_entry_result_flags_t_ l2fib_entry_result_flags_t
unsigned char u8
Definition: types.h:56
double f64
Definition: types.h:142
Definition: l2_fib.h:160
u32 w0
Definition: l2_fib.h:88
#define static_always_inline
Definition: clib.h:109
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, l2fib_entry_result_t *result0)
Lookup the entry for mac and bd_index in the mac table for 1 packet.
Definition: l2_fib.h:283
static void l2fib_entry_result_clear_bits(l2fib_entry_result_t *r, l2fib_entry_result_flags_t bits)
Definition: l2_fib.h:207
uword mac_table_memory_size
Definition: l2_fib.h:52
void l2fib_flush_all_mac(vlib_main_t *vm)
Flush all non static MACs - flushes all valid BDs.
Definition: l2_fib.c:876
unsigned int u32
Definition: types.h:88
struct l2fib_entry_result_t_ l2fib_entry_result_t
static_always_inline l2fib_seq_num_t l2_fib_update_seq_num(l2fib_seq_num_t sn, u8 if_sn)
Definition: l2_fib.h:116
u32 sw_if_index
Definition: l2_fib.h:166
struct l2fib_entry_key_t::@467::@470 words
f64 event_scan_delay
Definition: l2_fib.h:62
unsigned short u16
Definition: types.h:57
u8 mac_table_initialized
Definition: l2_fib.h:55
u8 * format_l2fib_entry_result_flags(u8 *s, va_list *args)
Definition: l2_fib.c:57
void l2fib_add_entry(const u8 *mac, u32 bd_index, u32 sw_if_index, l2fib_entry_result_flags_t flags)
Add an entry to the l2fib.
Definition: l2_fib.c:443
#define always_inline
Definition: ipsec.h:28
BVT(clib_bihash) *get_mac_table(void)
Definition: l2_fib.c:1019
static_always_inline void l2fib_lookup_4(BVT(clib_bihash) *mac_table, l2fib_entry_key_t *cached_key, l2fib_entry_result_t *cached_result, const u8 *mac0, const u8 *mac1, const u8 *mac2, const 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, l2fib_entry_result_t *result0, l2fib_entry_result_t *result1, l2fib_entry_result_t *result2, l2fib_entry_result_t *result3)
Definition: l2_fib.h:375
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
l2fib_seq_num_t sn
Definition: l2_fib.h:170
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, 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:327
l2fib_entry_result_flags_t_
Definition: l2_fib.h:145
f64 age_scan_duration
Definition: l2_fib.h:59
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:865
#define hash_mix32(a0, b0, c0)
Definition: hash.h:539
static u64 l2fib_make_key(const u8 *mac_address, u16 bd_index)
Definition: l2_fib.h:241
u8 timestamp
Definition: l2_fib.h:169
void l2_fib_extract_seq_num(l2fib_seq_num_t sn, u8 *bd_sn, u8 *if_sn)
Definition: l2_fib.c:150
void l2fib_clear_table(void)
Definition: l2_fib.c:384
Definition: l2_fib.h:77
void l2fib_table_dump(u32 bd_index, l2fib_entry_key_t **l2fe_key, l2fib_entry_result_t **l2fe_res)
Definition: l2_fib.c:133
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:855
typedef key
Definition: ipsec_types.api:86
#define foreach_l2fib_entry_result_attr
Flags associated with an L2 Fib Entry.
Definition: l2_fib.h:137
void l2fib_table_init(void)
Definition: l2_fib.c:370
u32 l2fib_del_entry(const u8 *mac, u32 bd_index, u32 sw_if_index)
Delete an entry from the l2fib.
Definition: l2_fib.c:732
l2_mac_event_action_t
Definition: l2_fib.h:214
u64 uword
Definition: types.h:112
u8 * format_vnet_sw_if_index_name_with_NA(u8 *s, va_list *args)
Format sw_if_index.
Definition: l2_fib.c:90
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:226
u16 bd_index
Definition: l2_fib.h:83
static void l2fib_add_filter_entry(const u8 *mac, u32 bd_index)
Definition: l2_fib.h:453
static_always_inline l2fib_seq_num_t l2_fib_mk_seq_num(u8 bd_sn, u8 if_sn)
Definition: l2_fib.h:110
u8 * format_l2_fib_seq_num(u8 *s, va_list *a)
Definition: l2_fib.c:157
static foreach_l2fib_entry_result_attr void l2fib_entry_result_set_bits(l2fib_entry_result_t *r, l2fib_entry_result_flags_t bits)
Definition: l2_fib.h:200
#define CLIB_MEM_OVERFLOW_LOAD(f, src)
Definition: sanitizer.h:49
manual_print typedef u8 mac_address[6]
uword mac_table_n_buckets
Definition: l2_fib.h:49
l2fib_main_t l2fib_main
Definition: l2_fib.c:54
u64 raw
Definition: l2_fib.h:91
void l2fib_start_ager_scan(vlib_main_t *vm)
Kick off ager to scan MACs to age/delete MAC entries.
Definition: l2_fib.c:832