Line data Source code
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 */
49 : uword mac_table_n_buckets;
50 :
51 : /* hash table memory size */
52 : uword mac_table_memory_size;
53 :
54 : /* hash table initialized */
55 : u8 mac_table_initialized;
56 :
57 : /* last event or ager scan duration */
58 : f64 evt_scan_duration;
59 : f64 age_scan_duration;
60 :
61 : /* delay between event scans, default to 100 msec */
62 : f64 event_scan_delay;
63 :
64 : /* max macs in event message, default to 100 entries */
65 : u32 max_macs_in_event;
66 :
67 : /* convenience variables */
68 : vlib_main_t *vlib_main;
69 : vnet_main_t *vnet_main;
70 : } l2fib_main_t;
71 :
72 : extern l2fib_main_t l2fib_main;
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 : {
83 : u16 bd_index;
84 : u8 mac[6];
85 : } fields;
86 : struct
87 : {
88 : u32 w0;
89 : u32 w1;
90 : } words;
91 : u64 raw;
92 : };
93 : } l2fib_entry_key_t;
94 :
95 : STATIC_ASSERT_SIZEOF (l2fib_entry_key_t, 8);
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 : */
107 : typedef u16 l2fib_seq_num_t;
108 :
109 : static_always_inline l2fib_seq_num_t
110 56213115 : l2_fib_mk_seq_num (u8 bd_sn, u8 if_sn)
111 : {
112 56213115 : return (((u16) bd_sn) << 8) | if_sn;
113 : }
114 :
115 : static_always_inline l2fib_seq_num_t
116 56199400 : l2_fib_update_seq_num (l2fib_seq_num_t sn, u8 if_sn)
117 : {
118 56199400 : sn &= 0xff00;
119 56199400 : sn |= if_sn;
120 :
121 56199400 : 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 :
145 : typedef enum l2fib_entry_result_flags_t_
146 : {
147 : L2FIB_ENTRY_RESULT_FLAG_NONE = 0,
148 : #define _(a,v,s) L2FIB_ENTRY_RESULT_FLAG_##a = (1 << v),
149 : foreach_l2fib_entry_result_attr
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;
172 : u64 raw;
173 : };
174 : } l2fib_entry_result_t;
175 :
176 : STATIC_ASSERT_SIZEOF (l2fib_entry_result_t, 8);
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 : }
183 168644573 : foreach_l2fib_entry_result_attr
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 : }
190 1531 : foreach_l2fib_entry_result_attr
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 : }
197 1768 : foreach_l2fib_entry_result_attr
198 : #undef _
199 : static inline void
200 0 : l2fib_entry_result_set_bits (l2fib_entry_result_t * r,
201 : l2fib_entry_result_flags_t bits)
202 : {
203 0 : r->fields.flags |= bits;
204 0 : }
205 :
206 : static inline void
207 83 : l2fib_entry_result_clear_bits (l2fib_entry_result_t * r,
208 : l2fib_entry_result_flags_t bits)
209 : {
210 83 : r->fields.flags &= ~bits;
211 83 : }
212 :
213 : /* L2 MAC event entry action enums (see mac_entry definition in l2.api) */
214 : typedef enum
215 : {
216 : MAC_EVENT_ACTION_ADD = 0,
217 : MAC_EVENT_ACTION_DELETE = 1,
218 : MAC_EVENT_ACTION_MOVE = 2,
219 : } l2_mac_event_action_t;
220 :
221 : /**
222 : * Compute the hash for the given key and return
223 : * the corresponding bucket index
224 : */
225 : always_inline u32
226 : l2fib_compute_hash_bucket (l2fib_entry_key_t * key)
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 :
240 : always_inline u64
241 112415706 : l2fib_make_key (const u8 * mac_address, u16 bd_index)
242 : {
243 112415706 : l2fib_entry_key_t key = { .fields.bd_index = bd_index };
244 112415706 : clib_memcpy_fast (&key.fields.mac, mac_address, sizeof (key.fields.mac));
245 112415706 : return key.raw;
246 : }
247 :
248 :
249 :
250 : /**
251 : * Lookup the entry for mac and bd_index in the mac table for 1 packet.
252 : * Cached_key and cached_result are used as a one-entry cache.
253 : * The function reads and updates them as needed.
254 : *
255 : * mac0 and bd_index0 are the keys. The entry is written to result0.
256 : * If the entry was not found, result0 is set to ~0.
257 : *
258 : * key0 return with the computed key, convenient if the entry needs,
259 : * to be updated afterward.
260 : */
261 :
262 : static_always_inline void
263 10895630 : l2fib_lookup_1 (BVT (clib_bihash) * mac_table,
264 : l2fib_entry_key_t * cached_key,
265 : l2fib_entry_result_t * cached_result,
266 : u8 * mac0,
267 : u16 bd_index0,
268 : l2fib_entry_key_t * key0, l2fib_entry_result_t * result0)
269 : {
270 : /* set up key */
271 10895630 : key0->raw = l2fib_make_key (mac0, bd_index0);
272 :
273 10895630 : if (key0->raw == cached_key->raw)
274 : {
275 : /* Hit in the one-entry cache */
276 10087050 : result0->raw = cached_result->raw;
277 : }
278 : else
279 : {
280 : /* Do a regular mac table lookup */
281 : BVT (clib_bihash_kv) kv;
282 :
283 808577 : kv.key = key0->raw;
284 808577 : kv.value = ~0ULL;
285 808577 : BV (clib_bihash_search_inline) (mac_table, &kv);
286 808577 : result0->raw = kv.value;
287 :
288 : /* Update one-entry cache */
289 808577 : cached_key->raw = key0->raw;
290 808577 : cached_result->raw = result0->raw;
291 : }
292 10895630 : }
293 :
294 :
295 : /**
296 : * Lookup the entry for mac and bd_index in the mac table for 2 packets.
297 : * The lookups for the two packets are interleaved.
298 : *
299 : * Cached_key and cached_result are used as a one-entry cache.
300 : * The function reads and updates them as needed.
301 : *
302 : * mac0 and bd_index0 are the keys. The entry is written to result0.
303 : * If the entry was not found, result0 is set to ~0. The same
304 : * holds for mac1/bd_index1/result1.
305 : */
306 : static_always_inline void
307 : l2fib_lookup_2 (BVT (clib_bihash) * mac_table,
308 : l2fib_entry_key_t * cached_key,
309 : l2fib_entry_result_t * cached_result,
310 : u8 * mac0,
311 : u8 * mac1,
312 : u16 bd_index0,
313 : u16 bd_index1,
314 : l2fib_entry_key_t * key0,
315 : l2fib_entry_key_t * key1,
316 : l2fib_entry_result_t * result0,
317 : l2fib_entry_result_t * result1)
318 : {
319 : /* set up key */
320 : key0->raw = l2fib_make_key (mac0, bd_index0);
321 : key1->raw = l2fib_make_key (mac1, bd_index1);
322 :
323 : if ((key0->raw == cached_key->raw) && (key1->raw == cached_key->raw))
324 : {
325 : /* Both hit in the one-entry cache */
326 : result0->raw = cached_result->raw;
327 : result1->raw = cached_result->raw;
328 : }
329 : else
330 : {
331 : BVT (clib_bihash_kv) kv0, kv1;
332 :
333 : /*
334 : * Do a regular mac table lookup
335 : * Interleave lookups for packet 0 and packet 1
336 : */
337 : kv0.key = key0->raw;
338 : kv1.key = key1->raw;
339 : kv0.value = ~0ULL;
340 : kv1.value = ~0ULL;
341 :
342 : BV (clib_bihash_search_inline) (mac_table, &kv0);
343 : BV (clib_bihash_search_inline) (mac_table, &kv1);
344 :
345 : result0->raw = kv0.value;
346 : result1->raw = kv1.value;
347 :
348 : /* Update one-entry cache */
349 : cached_key->raw = key1->raw;
350 : cached_result->raw = result1->raw;
351 : }
352 : }
353 :
354 : static_always_inline void
355 25379600 : l2fib_lookup_4 (BVT (clib_bihash) * mac_table,
356 : l2fib_entry_key_t * cached_key,
357 : l2fib_entry_result_t * cached_result,
358 : const u8 * mac0,
359 : const u8 * mac1,
360 : const u8 * mac2,
361 : const u8 * mac3,
362 : u16 bd_index0,
363 : u16 bd_index1,
364 : u16 bd_index2,
365 : u16 bd_index3,
366 : l2fib_entry_key_t * key0,
367 : l2fib_entry_key_t * key1,
368 : l2fib_entry_key_t * key2,
369 : l2fib_entry_key_t * key3,
370 : l2fib_entry_result_t * result0,
371 : l2fib_entry_result_t * result1,
372 : l2fib_entry_result_t * result2,
373 : l2fib_entry_result_t * result3)
374 : {
375 : /* set up key */
376 25379600 : key0->raw = l2fib_make_key (mac0, bd_index0);
377 25379600 : key1->raw = l2fib_make_key (mac1, bd_index1);
378 25379600 : key2->raw = l2fib_make_key (mac2, bd_index2);
379 25379600 : key3->raw = l2fib_make_key (mac3, bd_index3);
380 :
381 25379600 : if ((key0->raw == cached_key->raw) && (key1->raw == cached_key->raw) &&
382 23158200 : (key2->raw == cached_key->raw) && (key3->raw == cached_key->raw))
383 : {
384 : /* Both hit in the one-entry cache */
385 22779900 : result0->raw = cached_result->raw;
386 22779900 : result1->raw = cached_result->raw;
387 22779900 : result2->raw = cached_result->raw;
388 22779900 : result3->raw = cached_result->raw;
389 : }
390 : else
391 : {
392 : BVT (clib_bihash_kv) kv0, kv1, kv2, kv3;
393 :
394 : /*
395 : * Do a regular mac table lookup
396 : * Interleave lookups for packet 0 and packet 1
397 : */
398 2599580 : kv0.key = key0->raw;
399 2599580 : kv1.key = key1->raw;
400 2599580 : kv2.key = key2->raw;
401 2599580 : kv3.key = key3->raw;
402 2599580 : kv0.value = ~0ULL;
403 2599580 : kv1.value = ~0ULL;
404 2599580 : kv2.value = ~0ULL;
405 2599580 : kv3.value = ~0ULL;
406 :
407 2599580 : BV (clib_bihash_search_inline) (mac_table, &kv0);
408 2599580 : BV (clib_bihash_search_inline) (mac_table, &kv1);
409 2599580 : BV (clib_bihash_search_inline) (mac_table, &kv2);
410 2599580 : BV (clib_bihash_search_inline) (mac_table, &kv3);
411 :
412 2599580 : result0->raw = kv0.value;
413 2599580 : result1->raw = kv1.value;
414 2599580 : result2->raw = kv2.value;
415 2599580 : result3->raw = kv3.value;
416 :
417 : /* Update one-entry cache */
418 2599580 : cached_key->raw = key1->raw;
419 2599580 : cached_result->raw = result1->raw;
420 : }
421 25379600 : }
422 :
423 : void l2fib_clear_table (void);
424 :
425 : void l2fib_table_init (void);
426 :
427 : void
428 : l2fib_add_entry (const u8 * mac,
429 : u32 bd_index,
430 : u32 sw_if_index, l2fib_entry_result_flags_t flags);
431 :
432 : static inline void
433 0 : l2fib_add_filter_entry (const u8 * mac, u32 bd_index)
434 : {
435 0 : l2fib_add_entry (mac, bd_index, ~0,
436 : (L2FIB_ENTRY_RESULT_FLAG_FILTER |
437 : L2FIB_ENTRY_RESULT_FLAG_STATIC));
438 0 : }
439 :
440 : u32 l2fib_del_entry (const u8 * mac, u32 bd_index, u32 sw_if_index);
441 :
442 : void l2fib_start_ager_scan (vlib_main_t * vm);
443 :
444 : void l2fib_flush_int_mac (vlib_main_t * vm, u32 sw_if_index);
445 :
446 : void l2fib_flush_bd_mac (vlib_main_t * vm, u32 bd_index);
447 :
448 : void l2fib_flush_all_mac (vlib_main_t * vm);
449 :
450 : void
451 : l2fib_table_dump (u32 bd_index, l2fib_entry_key_t ** l2fe_key,
452 : l2fib_entry_result_t ** l2fe_res);
453 :
454 : u8 *format_vnet_sw_if_index_name_with_NA (u8 * s, va_list * args);
455 :
456 : BVT (clib_bihash) * get_mac_table (void);
457 :
458 : #endif
459 :
460 : /*
461 : * fd.io coding-style-patch-verification: ON
462 : *
463 : * Local Variables:
464 : * eval: (c-set-style "gnu")
465 : * End:
466 : */
|
