Line data Source code
1 : /*
2 : * Copyright (c) 2016 Cisco and/or its affiliates.
3 : * Licensed under the Apache License, Version 2.0 (the "License");
4 : * you may not use this file except in compliance with the License.
5 : * You may obtain a copy of the License at:
6 : *
7 : * http://www.apache.org/licenses/LICENSE-2.0
8 : *
9 : * Unless required by applicable law or agreed to in writing, software
10 : * distributed under the License is distributed on an "AS IS" BASIS,
11 : * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 : * See the License for the specific language governing permissions and
13 : * limitations under the License.
14 : */
15 :
16 : #include <vlib/vlib.h>
17 : #include <vnet/ip/format.h>
18 : #include <vnet/ip/lookup.h>
19 : #include <vnet/adj/adj.h>
20 : #include <vnet/dpo/load_balance.h>
21 : #include <vnet/dpo/drop_dpo.h>
22 :
23 : #include <vnet/fib/fib_entry.h>
24 : #include <vnet/fib/fib_walk.h>
25 : #include <vnet/fib/fib_entry_src.h>
26 : #include <vnet/fib/fib_entry_cover.h>
27 : #include <vnet/fib/fib_table.h>
28 : #include <vnet/fib/fib_internal.h>
29 : #include <vnet/fib/fib_attached_export.h>
30 : #include <vnet/fib/fib_path_ext.h>
31 : #include <vnet/fib/fib_entry_delegate.h>
32 : #include <vnet/fib/fib_entry_track.h>
33 :
34 : /*
35 : * Array of strings/names for the FIB sources
36 : */
37 : static const char *fib_attribute_names[] = FIB_ENTRY_ATTRIBUTES;
38 : static const char *fib_src_attribute_names[] = FIB_ENTRY_SRC_ATTRIBUTES;
39 :
40 : /*
41 : * Pool for all fib_entries
42 : */
43 : static fib_entry_t *fib_entry_pool;
44 :
45 : /**
46 : * the logger
47 : */
48 : vlib_log_class_t fib_entry_logger;
49 :
50 : fib_entry_t *
51 2526820 : fib_entry_get (fib_node_index_t index)
52 : {
53 2526820 : return (pool_elt_at_index(fib_entry_pool, index));
54 : }
55 :
56 : static fib_node_t *
57 75976 : fib_entry_get_node (fib_node_index_t index)
58 : {
59 75976 : return ((fib_node_t*)fib_entry_get(index));
60 : }
61 :
62 : fib_node_index_t
63 1234400 : fib_entry_get_index (const fib_entry_t * fib_entry)
64 : {
65 1234400 : return (fib_entry - fib_entry_pool);
66 : }
67 :
68 : fib_protocol_t
69 42566 : fib_entry_get_proto (const fib_entry_t * fib_entry)
70 : {
71 42566 : return (fib_entry->fe_prefix.fp_proto);
72 : }
73 :
74 : dpo_proto_t
75 31872 : fib_entry_get_dpo_proto (const fib_entry_t * fib_entry)
76 : {
77 31872 : return (fib_proto_to_dpo(fib_entry->fe_prefix.fp_proto));
78 : }
79 :
80 : fib_forward_chain_type_t
81 116603 : fib_entry_get_default_chain_type (const fib_entry_t *fib_entry)
82 : {
83 116603 : switch (fib_entry->fe_prefix.fp_proto)
84 : {
85 73742 : case FIB_PROTOCOL_IP4:
86 73742 : return (FIB_FORW_CHAIN_TYPE_UNICAST_IP4);
87 42052 : case FIB_PROTOCOL_IP6:
88 42052 : return (FIB_FORW_CHAIN_TYPE_UNICAST_IP6);
89 809 : case FIB_PROTOCOL_MPLS:
90 809 : if (MPLS_EOS == fib_entry->fe_prefix.fp_eos)
91 421 : return (FIB_FORW_CHAIN_TYPE_MPLS_EOS);
92 : else
93 388 : return (FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS);
94 : }
95 :
96 0 : return (FIB_FORW_CHAIN_TYPE_UNICAST_IP4);
97 : }
98 :
99 : u8 *
100 79 : format_fib_entry_flags (u8 *s, va_list *args)
101 : {
102 : fib_entry_attribute_t attr;
103 79 : fib_entry_flag_t flag = va_arg(*args, int);
104 :
105 948 : FOR_EACH_FIB_ATTRIBUTE(attr) {
106 869 : if ((1<<attr) & flag) {
107 84 : s = format (s, "%s,", fib_attribute_names[attr]);
108 : }
109 : }
110 :
111 79 : return (s);
112 : }
113 :
114 : u8 *
115 216 : format_fib_entry_src_flags (u8 *s, va_list *args)
116 : {
117 : fib_entry_src_attribute_t sattr;
118 216 : fib_entry_src_flag_t flag = va_arg(*args, int);
119 :
120 1512 : FOR_EACH_FIB_SRC_ATTRIBUTE(sattr) {
121 1296 : if ((1<<sattr) & flag) {
122 513 : s = format (s, "%s,", fib_src_attribute_names[sattr]);
123 : }
124 : }
125 :
126 216 : return (s);
127 : }
128 :
129 : u8 *
130 5289 : format_fib_entry (u8 * s, va_list * args)
131 : {
132 : fib_forward_chain_type_t fct;
133 : fib_entry_t *fib_entry;
134 : fib_entry_src_t *src;
135 : fib_node_index_t fei;
136 : fib_source_t source;
137 : int level;
138 :
139 5289 : fei = va_arg (*args, fib_node_index_t);
140 5289 : level = va_arg (*args, int);
141 5289 : fib_entry = fib_entry_get(fei);
142 :
143 5289 : s = format (s, "%U", format_fib_prefix, &fib_entry->fe_prefix);
144 :
145 5289 : if (level >= FIB_ENTRY_FORMAT_DETAIL)
146 : {
147 148 : s = format (s, " fib:%d", fib_entry->fe_fib_index);
148 148 : s = format (s, " index:%d", fib_entry_get_index(fib_entry));
149 148 : s = format (s, " locks:%d", fib_entry->fe_node.fn_locks);
150 :
151 364 : FOR_EACH_SRC_ADDED(fib_entry, src, source,
152 : ({
153 : s = format (s, "\n %U", format_fib_source, source);
154 : s = format (s, " refs:%d", src->fes_ref_count);
155 : if (FIB_ENTRY_FLAG_NONE != src->fes_entry_flags) {
156 : s = format(s, " entry-flags:%U",
157 : format_fib_entry_flags, src->fes_entry_flags);
158 : }
159 : if (FIB_ENTRY_SRC_FLAG_NONE != src->fes_flags) {
160 : s = format(s, " src-flags:%U",
161 : format_fib_entry_src_flags, src->fes_flags);
162 : }
163 : s = fib_entry_src_format(fib_entry, source, s);
164 : s = format (s, "\n");
165 : if (FIB_NODE_INDEX_INVALID != src->fes_pl)
166 : {
167 : s = fib_path_list_format(src->fes_pl, s);
168 : }
169 : s = format(s, "%U", format_fib_path_ext_list, &src->fes_path_exts);
170 : }));
171 :
172 148 : s = format (s, "\n forwarding: ");
173 : }
174 : else
175 : {
176 5141 : s = format (s, "\n");
177 : }
178 :
179 5289 : fct = fib_entry_get_default_chain_type(fib_entry);
180 :
181 5289 : if (!dpo_id_is_valid(&fib_entry->fe_lb))
182 : {
183 66 : s = format (s, " UNRESOLVED\n");
184 66 : return (s);
185 : }
186 : else
187 : {
188 5223 : s = format(s, " %U-chain\n %U",
189 : format_fib_forw_chain_type, fct,
190 : format_dpo_id,
191 : &fib_entry->fe_lb,
192 : 2);
193 5223 : s = format(s, "\n");
194 :
195 5223 : if (level >= FIB_ENTRY_FORMAT_DETAIL2)
196 : {
197 : index_t *fedi;
198 :
199 1 : s = format (s, " Delegates:\n");
200 1 : vec_foreach(fedi, fib_entry->fe_delegates)
201 : {
202 0 : s = format(s, " %U\n", format_fib_entry_delegate, *fedi);
203 : }
204 : }
205 : }
206 :
207 5223 : if (level >= FIB_ENTRY_FORMAT_DETAIL2)
208 : {
209 1 : s = format(s, " Children:");
210 1 : s = fib_node_children_format(fib_entry->fe_node.fn_children, s);
211 : }
212 :
213 5223 : return (s);
214 : }
215 :
216 : static fib_entry_t*
217 56285 : fib_entry_from_fib_node (fib_node_t *node)
218 : {
219 56285 : ASSERT(FIB_NODE_TYPE_ENTRY == node->fn_type);
220 56285 : return ((fib_entry_t*)node);
221 : }
222 :
223 : static void
224 30860 : fib_entry_last_lock_gone (fib_node_t *node)
225 : {
226 : fib_entry_delegate_type_t fdt;
227 : fib_entry_delegate_t *fed;
228 : fib_entry_t *fib_entry;
229 :
230 30860 : fib_entry = fib_entry_from_fib_node(node);
231 :
232 30860 : ASSERT(!dpo_id_is_valid(&fib_entry->fe_lb));
233 :
234 308600 : FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
235 : {
236 : dpo_reset(&fed->fd_dpo);
237 : fib_entry_delegate_remove(fib_entry, fdt);
238 : });
239 :
240 30860 : FIB_ENTRY_DBG(fib_entry, "last-lock");
241 :
242 30860 : fib_node_deinit(&fib_entry->fe_node);
243 :
244 30860 : ASSERT(0 == vec_len(fib_entry->fe_delegates));
245 30860 : vec_free(fib_entry->fe_delegates);
246 30860 : vec_free(fib_entry->fe_srcs);
247 30860 : pool_put(fib_entry_pool, fib_entry);
248 30860 : }
249 :
250 : static fib_entry_src_t*
251 282333 : fib_entry_get_best_src_i (const fib_entry_t *fib_entry)
252 : {
253 : fib_entry_src_t *bsrc;
254 :
255 : /*
256 : * the enum of sources is deliberately arranged in priority order
257 : */
258 282333 : if (0 == vec_len(fib_entry->fe_srcs))
259 : {
260 30853 : bsrc = NULL;
261 : }
262 : else
263 : {
264 251480 : bsrc = vec_elt_at_index(fib_entry->fe_srcs, 0);
265 : }
266 :
267 282333 : return (bsrc);
268 : }
269 :
270 : static fib_source_t
271 111532 : fib_entry_src_get_source (const fib_entry_src_t *esrc)
272 : {
273 111532 : if (NULL != esrc)
274 : {
275 80679 : return (esrc->fes_src);
276 : }
277 30853 : return (FIB_SOURCE_INVALID);
278 : }
279 :
280 : static fib_entry_flag_t
281 41405 : fib_entry_src_get_flags (const fib_entry_src_t *esrc)
282 : {
283 41405 : if (NULL != esrc)
284 : {
285 41405 : return (esrc->fes_entry_flags);
286 : }
287 0 : return (FIB_ENTRY_FLAG_NONE);
288 : }
289 :
290 : fib_entry_flag_t
291 1749 : fib_entry_get_flags (fib_node_index_t fib_entry_index)
292 : {
293 1749 : return (fib_entry_get_flags_i(fib_entry_get(fib_entry_index)));
294 : }
295 :
296 : static void
297 1 : fib_entry_show_memory (void)
298 : {
299 1 : u32 n_srcs = 0, n_exts = 0;
300 : fib_entry_src_t *esrc;
301 : fib_entry_t *entry;
302 :
303 1 : fib_show_memory_usage("Entry",
304 1 : pool_elts(fib_entry_pool),
305 1 : pool_len(fib_entry_pool),
306 : sizeof(fib_entry_t));
307 :
308 8 : pool_foreach (entry, fib_entry_pool)
309 : {
310 7 : n_srcs += vec_len(entry->fe_srcs);
311 14 : vec_foreach(esrc, entry->fe_srcs)
312 : {
313 7 : n_exts += fib_path_ext_list_length(&esrc->fes_path_exts);
314 : }
315 : }
316 :
317 1 : fib_show_memory_usage("Entry Source",
318 : n_srcs, n_srcs, sizeof(fib_entry_src_t));
319 1 : fib_show_memory_usage("Entry Path-Extensions",
320 : n_exts, n_exts,
321 : sizeof(fib_path_ext_t));
322 1 : }
323 :
324 : /**
325 : * @brief Contribute the set of Adjacencies that this entry forwards with
326 : * to build the uRPF list of its children
327 : */
328 : void
329 3306 : fib_entry_contribute_urpf (fib_node_index_t entry_index,
330 : index_t urpf)
331 : {
332 : fib_entry_t *fib_entry;
333 :
334 3306 : fib_entry = fib_entry_get(entry_index);
335 :
336 3306 : return (fib_path_list_contribute_urpf(fib_entry->fe_parent, urpf));
337 : }
338 :
339 : /*
340 : * If the client is request a chain for multicast forwarding then swap
341 : * the chain type to one that can provide such transport.
342 : */
343 : static fib_forward_chain_type_t
344 10865 : fib_entry_chain_type_mcast_to_ucast (fib_forward_chain_type_t fct)
345 : {
346 10865 : switch (fct)
347 : {
348 4 : case FIB_FORW_CHAIN_TYPE_MCAST_IP4:
349 : case FIB_FORW_CHAIN_TYPE_MCAST_IP6:
350 : /*
351 : * we can only transport IP multicast packets if there is an
352 : * LSP.
353 : */
354 4 : fct = FIB_FORW_CHAIN_TYPE_MPLS_EOS;
355 4 : break;
356 10861 : case FIB_FORW_CHAIN_TYPE_MPLS_EOS:
357 : case FIB_FORW_CHAIN_TYPE_UNICAST_IP4:
358 : case FIB_FORW_CHAIN_TYPE_UNICAST_IP6:
359 : case FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS:
360 : case FIB_FORW_CHAIN_TYPE_ETHERNET:
361 : case FIB_FORW_CHAIN_TYPE_NSH:
362 : case FIB_FORW_CHAIN_TYPE_BIER:
363 10861 : break;
364 : }
365 :
366 10865 : return (fct);
367 : }
368 :
369 : /*
370 : * fib_entry_contribute_forwarding
371 : *
372 : * Get an lock the forwarding information (DPO) contributed by the FIB entry.
373 : */
374 : void
375 10865 : fib_entry_contribute_forwarding (fib_node_index_t fib_entry_index,
376 : fib_forward_chain_type_t fct,
377 : dpo_id_t *dpo)
378 : {
379 : fib_entry_delegate_t *fed;
380 : fib_entry_t *fib_entry;
381 :
382 10865 : fib_entry = fib_entry_get(fib_entry_index);
383 :
384 : /*
385 : * mfib children ask for mcast chains. fix these to the appropriate ucast types.
386 : */
387 10865 : fct = fib_entry_chain_type_mcast_to_ucast(fct);
388 :
389 10865 : if (fct == fib_entry_get_default_chain_type(fib_entry))
390 : {
391 8329 : dpo_copy(dpo, &fib_entry->fe_lb);
392 : }
393 : else
394 : {
395 2536 : fed = fib_entry_delegate_find(fib_entry,
396 : fib_entry_chain_type_to_delegate_type(fct));
397 :
398 2536 : if (NULL == fed)
399 : {
400 : /*
401 : * use a temporary DPO lest the delegate realloc in the recursive
402 : * calculation.
403 : */
404 376 : dpo_id_t tmp = DPO_INVALID;
405 :
406 : /*
407 : * on-demand create eos/non-eos.
408 : * There is no on-demand delete because:
409 : * - memory versus complexity & reliability:
410 : * leaving unrequired [n]eos LB arounds wastes memory, cleaning
411 : * then up on the right trigger is more code. i favour the latter.
412 : */
413 376 : fib_entry_src_mk_lb(fib_entry,
414 376 : fib_entry_get_best_source(fib_entry_index),
415 : fct,
416 : &tmp);
417 :
418 376 : fed = fib_entry_delegate_find_or_add(
419 : fib_entry,
420 : fib_entry_chain_type_to_delegate_type(fct));
421 :
422 376 : dpo_copy(&fed->fd_dpo, &tmp);
423 376 : dpo_reset(&tmp);
424 : }
425 :
426 2536 : dpo_copy(dpo, &fed->fd_dpo);
427 : }
428 : /*
429 : * use the drop DPO is nothing else is present
430 : */
431 10865 : if (!dpo_id_is_valid(dpo))
432 : {
433 64 : dpo_copy(dpo, drop_dpo_get(fib_forw_chain_type_to_dpo_proto(fct)));
434 : }
435 :
436 : /*
437 : * don't allow the special index indicating replicate.vs.load-balance
438 : * to escape to the clients
439 : */
440 10865 : dpo->dpoi_index &= ~MPLS_IS_REPLICATE;
441 10865 : }
442 :
443 : const dpo_id_t *
444 16635 : fib_entry_contribute_ip_forwarding (fib_node_index_t fib_entry_index)
445 : {
446 : fib_forward_chain_type_t fct;
447 : fib_entry_t *fib_entry;
448 :
449 16635 : fib_entry = fib_entry_get(fib_entry_index);
450 16635 : fct = fib_entry_get_default_chain_type(fib_entry);
451 :
452 16635 : ASSERT((fct == FIB_FORW_CHAIN_TYPE_UNICAST_IP4 ||
453 : fct == FIB_FORW_CHAIN_TYPE_UNICAST_IP6));
454 :
455 16635 : if (dpo_id_is_valid(&fib_entry->fe_lb))
456 : {
457 16612 : return (&fib_entry->fe_lb);
458 : }
459 :
460 23 : return (drop_dpo_get(fib_forw_chain_type_to_dpo_proto(fct)));
461 : }
462 :
463 : adj_index_t
464 42 : fib_entry_get_adj (fib_node_index_t fib_entry_index)
465 : {
466 : const dpo_id_t *dpo;
467 :
468 42 : dpo = fib_entry_contribute_ip_forwarding(fib_entry_index);
469 :
470 42 : if (dpo_id_is_valid(dpo))
471 : {
472 42 : dpo = load_balance_get_bucket(dpo->dpoi_index, 0);
473 :
474 42 : if (dpo_is_adj(dpo))
475 : {
476 42 : return (dpo->dpoi_index);
477 : }
478 : }
479 0 : return (ADJ_INDEX_INVALID);
480 : }
481 :
482 : fib_node_index_t
483 0 : fib_entry_get_path_list (fib_node_index_t fib_entry_index)
484 : {
485 : fib_entry_t *fib_entry;
486 :
487 0 : fib_entry = fib_entry_get(fib_entry_index);
488 :
489 0 : return (fib_entry->fe_parent);
490 : }
491 :
492 : u32
493 6110 : fib_entry_child_add (fib_node_index_t fib_entry_index,
494 : fib_node_type_t child_type,
495 : fib_node_index_t child_index)
496 : {
497 6110 : return (fib_node_child_add(FIB_NODE_TYPE_ENTRY,
498 : fib_entry_index,
499 : child_type,
500 : child_index));
501 : };
502 :
503 : void
504 5991 : fib_entry_child_remove (fib_node_index_t fib_entry_index,
505 : u32 sibling_index)
506 : {
507 5991 : fib_node_child_remove(FIB_NODE_TYPE_ENTRY,
508 : fib_entry_index,
509 : sibling_index);
510 :
511 5991 : if (0 == fib_node_get_n_children(FIB_NODE_TYPE_ENTRY,
512 : fib_entry_index))
513 : {
514 : /*
515 : * if there are no children left then there is no reason to keep
516 : * the non-default forwarding chains. those chains are built only
517 : * because the children want them.
518 : */
519 : fib_entry_delegate_type_t fdt;
520 : fib_entry_delegate_t *fed;
521 : fib_entry_t *fib_entry;
522 :
523 4173 : fib_entry = fib_entry_get(fib_entry_index);
524 :
525 41730 : FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
526 : {
527 : dpo_reset(&fed->fd_dpo);
528 : fib_entry_delegate_remove(fib_entry, fdt);
529 : });
530 : }
531 5991 : }
532 :
533 : static fib_entry_t *
534 40878 : fib_entry_alloc (u32 fib_index,
535 : const fib_prefix_t *prefix,
536 : fib_node_index_t *fib_entry_index)
537 : {
538 : fib_entry_t *fib_entry;
539 : fib_prefix_t *fep;
540 40878 : u8 need_barrier_sync = pool_get_will_expand (fib_entry_pool);
541 40878 : vlib_main_t *vm = vlib_get_main();
542 40878 : ASSERT (vm->thread_index == 0);
543 :
544 40878 : if (need_barrier_sync)
545 4041 : vlib_worker_thread_barrier_sync (vm);
546 :
547 40878 : pool_get(fib_entry_pool, fib_entry);
548 :
549 40878 : if (need_barrier_sync)
550 4041 : vlib_worker_thread_barrier_release (vm);
551 :
552 40878 : clib_memset(fib_entry, 0, sizeof(*fib_entry));
553 :
554 40878 : fib_node_init(&fib_entry->fe_node,
555 : FIB_NODE_TYPE_ENTRY);
556 :
557 40878 : fib_entry->fe_fib_index = fib_index;
558 :
559 : /*
560 : * the one time we need to update the const prefix is when
561 : * the entry is first created
562 : */
563 40878 : fep = (fib_prefix_t*)&(fib_entry->fe_prefix);
564 40878 : *fep = *prefix;
565 :
566 40878 : if (FIB_PROTOCOL_MPLS == fib_entry->fe_prefix.fp_proto)
567 : {
568 631 : fep->fp_len = 21;
569 631 : if (MPLS_NON_EOS == fep->fp_eos)
570 : {
571 299 : fep->fp_payload_proto = DPO_PROTO_MPLS;
572 : }
573 631 : ASSERT(DPO_PROTO_NONE != fib_entry->fe_prefix.fp_payload_proto);
574 : }
575 :
576 40878 : dpo_reset(&fib_entry->fe_lb);
577 :
578 40878 : *fib_entry_index = fib_entry_get_index(fib_entry);
579 :
580 40878 : return (fib_entry);
581 : }
582 :
583 : static fib_entry_t*
584 78188 : fib_entry_post_flag_update_actions (fib_entry_t *fib_entry,
585 : fib_entry_flag_t old_flags,
586 : u32 new_fib_index)
587 : {
588 : fib_node_index_t fei;
589 :
590 : /*
591 : * save the index so we can recover from pool reallocs
592 : */
593 78188 : fei = fib_entry_get_index(fib_entry);
594 :
595 : /*
596 : * handle changes to attached export for import entries
597 : */
598 78188 : int is_import = (FIB_ENTRY_FLAG_IMPORT & fib_entry_get_flags_i(fib_entry));
599 78188 : int was_import = (FIB_ENTRY_FLAG_IMPORT & old_flags);
600 :
601 78188 : if (!was_import && is_import)
602 : {
603 : /*
604 : * transition from not exported to exported
605 : */
606 :
607 : /*
608 : * there is an assumption here that the entry resolves via only
609 : * one interface and that it is the cross VRF interface.
610 : */
611 11 : if (~0 == new_fib_index)
612 : {
613 10 : u32 sw_if_index = fib_path_list_get_resolving_interface(fib_entry->fe_parent);
614 10 : new_fib_index = fib_table_get_index_for_sw_if_index(
615 10 : fib_entry_get_proto(fib_entry),
616 : sw_if_index);
617 : }
618 11 : fib_attached_export_import(fib_entry, new_fib_index);
619 : }
620 78177 : else if (was_import && !is_import)
621 : {
622 : /*
623 : * transition from exported to not exported
624 : */
625 11 : fib_attached_export_purge(fib_entry);
626 : }
627 78166 : else if (was_import && is_import && ~0 != new_fib_index)
628 : {
629 : /*
630 : * transition from export from one table to another
631 : */
632 3 : fib_attached_export_purge(fib_entry);
633 3 : fib_attached_export_import(fib_entry, new_fib_index);
634 : }
635 : /*
636 : * else
637 : * no change. nothing to do.
638 : */
639 :
640 : /*
641 : * reload the entry address post possible pool realloc
642 : */
643 78188 : fib_entry = fib_entry_get(fei);
644 :
645 : /*
646 : * handle changes to attached export for export entries
647 : */
648 78188 : int is_attached = (FIB_ENTRY_FLAG_ATTACHED & fib_entry_get_flags_i(fib_entry));
649 78188 : int was_attached = (FIB_ENTRY_FLAG_ATTACHED & old_flags);
650 :
651 : if (!was_attached && is_attached)
652 : {
653 : /*
654 : * transition to attached. time to export
655 : */
656 : // FIXME
657 : }
658 : // else FIXME
659 :
660 78188 : return (fib_entry);
661 : }
662 :
663 : static fib_entry_t*
664 47321 : fib_entry_post_install_actions (fib_entry_t *fib_entry,
665 : fib_source_t source,
666 : fib_entry_flag_t old_flags)
667 : {
668 47321 : fib_entry = fib_entry_post_flag_update_actions(fib_entry, old_flags, ~0);
669 47321 : fib_entry = fib_entry_src_action_installed(fib_entry, source);
670 :
671 47321 : return (fib_entry);
672 : }
673 :
674 : fib_node_index_t
675 25012 : fib_entry_create (u32 fib_index,
676 : const fib_prefix_t *prefix,
677 : fib_source_t source,
678 : fib_entry_flag_t flags,
679 : const fib_route_path_t *paths)
680 : {
681 : fib_node_index_t fib_entry_index;
682 : fib_entry_t *fib_entry;
683 :
684 25012 : ASSERT(0 < vec_len(paths));
685 :
686 25012 : fib_entry = fib_entry_alloc(fib_index, prefix, &fib_entry_index);
687 :
688 : /*
689 : * since this is a new entry create, we don't need to check for winning
690 : * sources - there is only one.
691 : */
692 25012 : fib_entry = fib_entry_src_action_add(fib_entry, source, flags,
693 : drop_dpo_get(
694 25012 : fib_proto_to_dpo(
695 25012 : fib_entry_get_proto(fib_entry))));
696 25012 : fib_entry_src_action_path_swap(fib_entry,
697 : source,
698 : flags,
699 : paths);
700 : /*
701 : * handle possible realloc's by refetching the pointer
702 : */
703 25012 : fib_entry = fib_entry_get(fib_entry_index);
704 25012 : fib_entry_src_action_activate(fib_entry, source);
705 :
706 25012 : fib_entry = fib_entry_post_install_actions(fib_entry, source,
707 : FIB_ENTRY_FLAG_NONE);
708 :
709 25012 : FIB_ENTRY_DBG(fib_entry, "create");
710 :
711 25012 : return (fib_entry_index);
712 : }
713 :
714 : fib_node_index_t
715 15866 : fib_entry_create_special (u32 fib_index,
716 : const fib_prefix_t *prefix,
717 : fib_source_t source,
718 : fib_entry_flag_t flags,
719 : const dpo_id_t *dpo)
720 : {
721 : fib_node_index_t fib_entry_index;
722 : fib_entry_t *fib_entry;
723 :
724 : /*
725 : * create and initialize the new enty
726 : */
727 15866 : fib_entry = fib_entry_alloc(fib_index, prefix, &fib_entry_index);
728 :
729 : /*
730 : * create the path-list
731 : */
732 15866 : fib_entry = fib_entry_src_action_add(fib_entry, source, flags, dpo);
733 15866 : fib_entry_src_action_activate(fib_entry, source);
734 :
735 15866 : fib_entry = fib_entry_post_install_actions(fib_entry, source,
736 : FIB_ENTRY_FLAG_NONE);
737 :
738 15866 : FIB_ENTRY_DBG(fib_entry, "create-special");
739 :
740 15866 : return (fib_entry_index);
741 : }
742 :
743 : static void
744 4213 : fib_entry_post_update_actions (fib_entry_t *fib_entry,
745 : fib_source_t source,
746 : fib_entry_flag_t old_flags)
747 : {
748 : /*
749 : * backwalk to children to inform then of the change to forwarding.
750 : */
751 4213 : fib_node_back_walk_ctx_t bw_ctx = {
752 : .fnbw_reason = FIB_NODE_BW_REASON_FLAG_EVALUATE,
753 : };
754 :
755 4213 : fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_get_index(fib_entry), &bw_ctx);
756 :
757 : /*
758 : * then inform any covered prefixes
759 : */
760 4213 : fib_entry_cover_update_notify(fib_entry);
761 :
762 4213 : fib_entry_post_install_actions(fib_entry, source, old_flags);
763 4213 : }
764 :
765 : void
766 0 : fib_entry_recalculate_forwarding (fib_node_index_t fib_entry_index)
767 : {
768 : fib_source_t best_source;
769 : fib_entry_t *fib_entry;
770 : fib_entry_src_t *bsrc;
771 :
772 0 : fib_entry = fib_entry_get(fib_entry_index);
773 :
774 0 : bsrc = fib_entry_get_best_src_i(fib_entry);
775 0 : best_source = fib_entry_src_get_source(bsrc);
776 :
777 0 : fib_entry_src_action_reactivate(fib_entry, best_source);
778 0 : }
779 :
780 : static void
781 9878 : fib_entry_source_change_w_flags (fib_entry_t *fib_entry,
782 : fib_source_t old_source,
783 : fib_entry_flag_t old_flags,
784 : fib_source_t new_source)
785 : {
786 9878 : switch (fib_source_cmp(new_source, old_source))
787 : {
788 294 : case FIB_SOURCE_CMP_BETTER:
789 : /*
790 : * we have a new winning source.
791 : */
792 294 : fib_entry_src_action_deactivate(fib_entry, old_source);
793 294 : fib_entry_src_action_activate(fib_entry, new_source);
794 294 : break;
795 :
796 6016 : case FIB_SOURCE_CMP_WORSE:
797 : /*
798 : * the new source loses. Re-activate the winning sources
799 : * in case it is an interposer and hence relied on the losing
800 : * source's path-list.
801 : */
802 6016 : fib_entry_src_action_reactivate(fib_entry, old_source);
803 6016 : return;
804 :
805 3568 : case FIB_SOURCE_CMP_EQUAL:
806 : /*
807 : * the new source is one this entry already has.
808 : * But the path-list was updated, which will contribute new forwarding,
809 : * so install it.
810 : */
811 3568 : fib_entry_src_action_reactivate(fib_entry, new_source);
812 3568 : break;
813 : }
814 :
815 3862 : fib_entry_post_update_actions(fib_entry, new_source, old_flags);
816 : }
817 :
818 : void
819 6505 : fib_entry_source_change (fib_entry_t *fib_entry,
820 : fib_source_t old_source,
821 : fib_source_t new_source)
822 : {
823 : fib_entry_flag_t old_flags;
824 :
825 6505 : old_flags = fib_entry_get_flags_for_source(
826 : fib_entry_get_index(fib_entry), old_source);
827 :
828 6505 : return (fib_entry_source_change_w_flags(fib_entry, old_source,
829 : old_flags, new_source));
830 : }
831 :
832 : void
833 6092 : fib_entry_special_add (fib_node_index_t fib_entry_index,
834 : fib_source_t source,
835 : fib_entry_flag_t flags,
836 : const dpo_id_t *dpo)
837 : {
838 : fib_source_t best_source;
839 : fib_entry_t *fib_entry;
840 :
841 6092 : fib_entry = fib_entry_get(fib_entry_index);
842 6092 : best_source = fib_entry_get_best_source(fib_entry_index);
843 :
844 6092 : fib_entry = fib_entry_src_action_add(fib_entry, source, flags, dpo);
845 6092 : fib_entry_source_change(fib_entry, best_source, source);
846 6092 : FIB_ENTRY_DBG(fib_entry, "special-add:%U", format_fib_source, source);
847 6092 : }
848 :
849 : void
850 1 : fib_entry_special_update (fib_node_index_t fib_entry_index,
851 : fib_source_t source,
852 : fib_entry_flag_t flags,
853 : const dpo_id_t *dpo)
854 : {
855 : fib_source_t best_source;
856 : fib_entry_t *fib_entry;
857 :
858 1 : fib_entry = fib_entry_get(fib_entry_index);
859 1 : best_source = fib_entry_get_best_source(fib_entry_index);
860 :
861 1 : fib_entry = fib_entry_src_action_update(fib_entry, source, flags, dpo);
862 1 : fib_entry_source_change(fib_entry, best_source, source);
863 :
864 1 : FIB_ENTRY_DBG(fib_entry, "special-updated:%U", format_fib_source, source);
865 1 : }
866 :
867 :
868 : void
869 357 : fib_entry_path_add (fib_node_index_t fib_entry_index,
870 : fib_source_t source,
871 : fib_entry_flag_t flags,
872 : const fib_route_path_t *rpaths)
873 : {
874 : fib_source_t best_source;
875 : fib_entry_t *fib_entry;
876 : fib_entry_src_t *bsrc;
877 :
878 357 : fib_entry = fib_entry_get(fib_entry_index);
879 357 : ASSERT(NULL != fib_entry);
880 :
881 357 : bsrc = fib_entry_get_best_src_i(fib_entry);
882 357 : best_source = fib_entry_src_get_source(bsrc);
883 :
884 357 : fib_entry = fib_entry_src_action_path_add(fib_entry, source, flags, rpaths);
885 :
886 357 : fib_entry_source_change(fib_entry, best_source, source);
887 :
888 357 : FIB_ENTRY_DBG(fib_entry, "path add:%U", format_fib_source, source);
889 357 : }
890 :
891 : static fib_entry_src_flag_t
892 35296 : fib_entry_src_burn_only_inherited (fib_entry_t *fib_entry)
893 : {
894 : fib_entry_src_t *src;
895 : fib_source_t source;
896 35296 : int has_only_inherited_sources = 1;
897 :
898 35304 : FOR_EACH_SRC_ADDED(fib_entry, src, source,
899 : ({
900 : if (!(src->fes_flags & FIB_ENTRY_SRC_FLAG_INHERITED))
901 : {
902 : has_only_inherited_sources = 0;
903 : break;
904 : }
905 : }));
906 35296 : if (has_only_inherited_sources)
907 : {
908 30867 : FOR_EACH_SRC_ADDED(fib_entry, src, source,
909 : ({
910 : fib_entry_src_action_remove(fib_entry, source);
911 : }));
912 30860 : return (FIB_ENTRY_SRC_FLAG_NONE);
913 : }
914 : else
915 : {
916 4436 : return (FIB_ENTRY_SRC_FLAG_ADDED);
917 : }
918 : }
919 :
920 : static fib_entry_src_flag_t
921 31178 : fib_entry_source_removed (fib_entry_t *fib_entry,
922 : fib_entry_flag_t old_flags)
923 : {
924 : const fib_entry_src_t *bsrc;
925 : fib_source_t best_source;
926 :
927 : /*
928 : * if all that is left are inherited sources, then burn them
929 : */
930 31178 : fib_entry_src_burn_only_inherited(fib_entry);
931 :
932 31178 : bsrc = fib_entry_get_best_src_i(fib_entry);
933 31178 : best_source = fib_entry_src_get_source(bsrc);
934 :
935 31178 : if (FIB_SOURCE_INVALID == best_source)
936 : {
937 : /*
938 : * no more sources left. this entry is toast.
939 : */
940 30853 : fib_entry = fib_entry_post_flag_update_actions(fib_entry, old_flags, ~0);
941 30853 : fib_entry_src_action_uninstall(fib_entry);
942 :
943 30853 : return (FIB_ENTRY_SRC_FLAG_NONE);
944 : }
945 : else
946 : {
947 325 : fib_entry_src_action_activate(fib_entry, best_source);
948 : }
949 :
950 325 : fib_entry_post_update_actions(fib_entry, best_source, old_flags);
951 :
952 : /*
953 : * still have sources
954 : */
955 325 : return (FIB_ENTRY_SRC_FLAG_ADDED);
956 : }
957 :
958 : /*
959 : * fib_entry_path_remove
960 : *
961 : * remove a path from the entry.
962 : * return the fib_entry's index if it is still present, INVALID otherwise.
963 : */
964 : fib_entry_src_flag_t
965 5597 : fib_entry_path_remove (fib_node_index_t fib_entry_index,
966 : fib_source_t source,
967 : const fib_route_path_t *rpaths)
968 : {
969 : fib_entry_src_flag_t sflag;
970 : fib_source_t best_source;
971 : fib_entry_flag_t bflags;
972 : fib_entry_t *fib_entry;
973 : fib_entry_src_t *bsrc;
974 :
975 5597 : fib_entry = fib_entry_get(fib_entry_index);
976 5597 : ASSERT(NULL != fib_entry);
977 :
978 5597 : bsrc = fib_entry_get_best_src_i(fib_entry);
979 5597 : best_source = fib_entry_src_get_source(bsrc);
980 5597 : bflags = fib_entry_src_get_flags(bsrc);
981 :
982 5597 : sflag = fib_entry_src_action_path_remove(fib_entry, source, rpaths);
983 :
984 5597 : FIB_ENTRY_DBG(fib_entry, "path remove:%U", format_fib_source, source);
985 :
986 : /*
987 : * if the path list for the source passed is invalid,
988 : * then we need to create a new one. else we are updating
989 : * an existing.
990 : */
991 5597 : switch (fib_source_cmp(source, best_source))
992 : {
993 0 : case FIB_SOURCE_CMP_BETTER:
994 : /*
995 : * Que! removing a path from a source that is better than the
996 : * one this entry is using.
997 : */
998 0 : ASSERT(0);
999 0 : break;
1000 14 : case FIB_SOURCE_CMP_WORSE:
1001 : /*
1002 : * the source is not the best. no need to update forwarding
1003 : */
1004 14 : if (FIB_ENTRY_SRC_FLAG_ADDED & sflag)
1005 : {
1006 : /*
1007 : * the source being removed still has paths
1008 : */
1009 0 : return (FIB_ENTRY_SRC_FLAG_ADDED);
1010 : }
1011 : else
1012 : {
1013 : /*
1014 : * that was the last path from this source, check if those
1015 : * that remain are non-inherited
1016 : */
1017 14 : return (fib_entry_src_burn_only_inherited(fib_entry));
1018 : }
1019 : break;
1020 5583 : case FIB_SOURCE_CMP_EQUAL:
1021 : /*
1022 : * removing a path from the path-list we were using.
1023 : */
1024 5583 : if (!(FIB_ENTRY_SRC_FLAG_ADDED & sflag))
1025 : {
1026 : /*
1027 : * the last path from the source was removed.
1028 : * fallback to lower source
1029 : */
1030 5567 : return (fib_entry_source_removed(fib_entry, bflags));
1031 : }
1032 : else
1033 : {
1034 : /*
1035 : * re-install the new forwarding information
1036 : */
1037 16 : fib_entry_src_action_reactivate(fib_entry, source);
1038 : }
1039 16 : break;
1040 : }
1041 :
1042 16 : fib_entry_post_update_actions(fib_entry, source, bflags);
1043 :
1044 : /*
1045 : * still have sources
1046 : */
1047 16 : return (FIB_ENTRY_SRC_FLAG_ADDED);
1048 : }
1049 :
1050 : /*
1051 : * fib_entry_special_remove
1052 : *
1053 : * remove a special source from the entry.
1054 : * return the fib_entry's index if it is still present, INVALID otherwise.
1055 : */
1056 : fib_entry_src_flag_t
1057 31547 : fib_entry_special_remove (fib_node_index_t fib_entry_index,
1058 : fib_source_t source)
1059 : {
1060 : fib_entry_src_flag_t sflag;
1061 : fib_source_t best_source;
1062 : fib_entry_flag_t bflags;
1063 : fib_entry_t *fib_entry;
1064 : fib_entry_src_t *bsrc;
1065 :
1066 31547 : fib_entry = fib_entry_get(fib_entry_index);
1067 31547 : ASSERT(NULL != fib_entry);
1068 :
1069 31547 : bsrc = fib_entry_get_best_src_i(fib_entry);
1070 31547 : best_source = fib_entry_src_get_source(bsrc);
1071 31547 : bflags = fib_entry_src_get_flags(bsrc);
1072 :
1073 31547 : FIB_ENTRY_DBG(fib_entry, "special remove:%U", format_fib_source, source);
1074 :
1075 31547 : sflag = fib_entry_src_action_remove_or_update_inherit(fib_entry, source);
1076 :
1077 : /*
1078 : * if the path list for the source passed is invalid,
1079 : * then we need to create a new one. else we are updating
1080 : * an existing.
1081 : */
1082 31547 : switch (fib_source_cmp(source, best_source))
1083 : {
1084 11 : case FIB_SOURCE_CMP_BETTER:
1085 : /*
1086 : * Que! removing a path from a source that is better than the
1087 : * one this entry is using. This can only mean it is a source
1088 : * this prefix does not have.
1089 : */
1090 11 : return (FIB_ENTRY_SRC_FLAG_ADDED);
1091 :
1092 5915 : case FIB_SOURCE_CMP_WORSE:
1093 : /*
1094 : * the source is not the best. no need to update forwarding
1095 : */
1096 5915 : if (FIB_ENTRY_SRC_FLAG_ADDED & sflag)
1097 : {
1098 : /*
1099 : * the source being removed still has paths
1100 : */
1101 1811 : return (FIB_ENTRY_SRC_FLAG_ADDED);
1102 : }
1103 : else
1104 : {
1105 : /*
1106 : * that was the last path from this source, check if those
1107 : * that remain are non-inherited
1108 : */
1109 4104 : if (FIB_ENTRY_SRC_FLAG_NONE == fib_entry_src_burn_only_inherited(fib_entry))
1110 : {
1111 : /*
1112 : * no more sources left. this entry is toast.
1113 : */
1114 7 : fib_entry = fib_entry_post_flag_update_actions(fib_entry, bflags, ~0);
1115 7 : fib_entry_src_action_uninstall(fib_entry);
1116 7 : return (FIB_ENTRY_SRC_FLAG_NONE);
1117 : }
1118 :
1119 : /*
1120 : * reactivate the best source so the interposer gets restacked
1121 : */
1122 4097 : fib_entry_src_action_reactivate(fib_entry, best_source);
1123 :
1124 4097 : return (FIB_ENTRY_SRC_FLAG_ADDED);
1125 : }
1126 : break;
1127 :
1128 25621 : case FIB_SOURCE_CMP_EQUAL:
1129 25621 : if (!(FIB_ENTRY_SRC_FLAG_ADDED & sflag))
1130 : {
1131 : /*
1132 : * the source was removed. use the next best.
1133 : */
1134 25611 : return (fib_entry_source_removed(fib_entry, bflags));
1135 : }
1136 : else
1137 : {
1138 : /*
1139 : * re-install the new forwarding information
1140 : */
1141 10 : fib_entry_src_action_reactivate(fib_entry, source);
1142 : }
1143 10 : break;
1144 : }
1145 :
1146 10 : fib_entry_post_update_actions(fib_entry, source, bflags);
1147 :
1148 : /*
1149 : * still have sources
1150 : */
1151 10 : return (FIB_ENTRY_SRC_FLAG_ADDED);
1152 : }
1153 :
1154 : /**
1155 : * fib_entry_inherit
1156 : *
1157 : * If the source on the cover is inheriting then push this source
1158 : * down to the covered.
1159 : */
1160 : void
1161 36564 : fib_entry_inherit (fib_node_index_t cover,
1162 : fib_node_index_t covered)
1163 : {
1164 36564 : fib_entry_src_inherit(fib_entry_get(cover),
1165 : fib_entry_get(covered));
1166 36564 : }
1167 :
1168 : /**
1169 : * fib_entry_delete
1170 : *
1171 : * The source is withdrawing all the paths it provided
1172 : */
1173 : fib_entry_src_flag_t
1174 21293 : fib_entry_delete (fib_node_index_t fib_entry_index,
1175 : fib_source_t source)
1176 : {
1177 21293 : return (fib_entry_special_remove(fib_entry_index, source));
1178 : }
1179 :
1180 : /**
1181 : * fib_entry_update
1182 : *
1183 : * The source has provided a new set of paths that will replace the old.
1184 : */
1185 : void
1186 3373 : fib_entry_update (fib_node_index_t fib_entry_index,
1187 : fib_source_t source,
1188 : fib_entry_flag_t flags,
1189 : const fib_route_path_t *paths)
1190 : {
1191 : fib_source_t best_source;
1192 : fib_entry_flag_t bflags;
1193 : fib_entry_t *fib_entry;
1194 : fib_entry_src_t *bsrc;
1195 :
1196 3373 : fib_entry = fib_entry_get(fib_entry_index);
1197 3373 : ASSERT(NULL != fib_entry);
1198 :
1199 3373 : bsrc = fib_entry_get_best_src_i(fib_entry);
1200 3373 : best_source = fib_entry_src_get_source(bsrc);
1201 3373 : bflags = fib_entry_get_flags_i(fib_entry);
1202 :
1203 3373 : fib_entry = fib_entry_src_action_path_swap(fib_entry,
1204 : source,
1205 : flags,
1206 : paths);
1207 :
1208 3373 : fib_entry_source_change_w_flags(fib_entry, best_source, bflags, source);
1209 3373 : FIB_ENTRY_DBG(fib_entry, "update");
1210 3373 : }
1211 :
1212 :
1213 : /*
1214 : * fib_entry_cover_changed
1215 : *
1216 : * this entry is tracking its cover and that cover has changed.
1217 : */
1218 : void
1219 4240 : fib_entry_cover_changed (fib_node_index_t fib_entry_index)
1220 : {
1221 4240 : fib_entry_src_cover_res_t res = {
1222 : .install = !0,
1223 : .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
1224 : };
1225 : CLIB_UNUSED(fib_source_t source);
1226 : fib_source_t best_source;
1227 : fib_entry_flag_t bflags;
1228 : fib_entry_t *fib_entry;
1229 : fib_entry_src_t *esrc;
1230 : u32 index;
1231 :
1232 4240 : bflags = FIB_ENTRY_FLAG_NONE;
1233 4240 : best_source = FIB_SOURCE_FIRST;
1234 4240 : fib_entry = fib_entry_get(fib_entry_index);
1235 :
1236 4240 : fib_attached_export_cover_change(fib_entry);
1237 :
1238 : /*
1239 : * propagate the notification to each of the added sources
1240 : */
1241 4240 : index = 0;
1242 8529 : FOR_EACH_SRC_ADDED(fib_entry, esrc, source,
1243 : ({
1244 : if (0 == index)
1245 : {
1246 : /*
1247 : * only the best source gets to set the back walk flags
1248 : */
1249 : res = fib_entry_src_action_cover_change(fib_entry, esrc);
1250 : bflags = fib_entry_src_get_flags(esrc);
1251 : best_source = fib_entry_src_get_source(esrc);
1252 : }
1253 : else
1254 : {
1255 : fib_entry_src_action_cover_change(fib_entry, esrc);
1256 : }
1257 : index++;
1258 : }));
1259 :
1260 4240 : if (res.install)
1261 : {
1262 2217 : fib_entry_src_action_reactivate(fib_entry,
1263 2217 : fib_entry_src_get_source(
1264 2217 : fib_entry_get_best_src_i(fib_entry)));
1265 2217 : fib_entry = fib_entry_post_install_actions(fib_entry,
1266 : best_source,
1267 : bflags);
1268 : }
1269 : else
1270 : {
1271 2023 : fib_entry_src_action_uninstall(fib_entry);
1272 : }
1273 :
1274 4240 : if (FIB_NODE_BW_REASON_FLAG_NONE != res.bw_reason)
1275 : {
1276 : /*
1277 : * time for walkies fido.
1278 : */
1279 225 : fib_node_back_walk_ctx_t bw_ctx = {
1280 225 : .fnbw_reason = res.bw_reason,
1281 : };
1282 :
1283 225 : fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_index, &bw_ctx);
1284 : }
1285 4240 : FIB_ENTRY_DBG(fib_entry, "cover-changed");
1286 4240 : }
1287 :
1288 : /*
1289 : * fib_entry_cover_updated
1290 : *
1291 : * this entry is tracking its cover and that cover has been updated
1292 : * (i.e. its forwarding information has changed).
1293 : */
1294 : void
1295 14 : fib_entry_cover_updated (fib_node_index_t fib_entry_index)
1296 : {
1297 14 : fib_entry_src_cover_res_t res = {
1298 : .install = !0,
1299 : .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
1300 : };
1301 : CLIB_UNUSED(fib_source_t source);
1302 : fib_source_t best_source;
1303 : fib_entry_flag_t bflags;
1304 : fib_entry_t *fib_entry;
1305 : fib_entry_src_t *esrc;
1306 : u32 index;
1307 :
1308 14 : bflags = FIB_ENTRY_FLAG_NONE;
1309 14 : best_source = FIB_SOURCE_FIRST;
1310 14 : fib_entry = fib_entry_get(fib_entry_index);
1311 :
1312 14 : fib_attached_export_cover_update(fib_entry);
1313 :
1314 : /*
1315 : * propagate the notification to each of the added sources
1316 : */
1317 14 : index = 0;
1318 29 : FOR_EACH_SRC_ADDED(fib_entry, esrc, source,
1319 : ({
1320 : if (0 == index)
1321 : {
1322 : /*
1323 : * only the best source gets to set the install result
1324 : */
1325 : res = fib_entry_src_action_cover_update(fib_entry, esrc);
1326 : bflags = fib_entry_src_get_flags(esrc);
1327 : best_source = fib_entry_src_get_source(esrc);
1328 : }
1329 : else
1330 : {
1331 : /*
1332 : * contirubting sources can set backwalk flags
1333 : */
1334 : if (esrc->fes_flags & FIB_ENTRY_SRC_FLAG_CONTRIBUTING)
1335 : {
1336 : fib_entry_src_cover_res_t tmp = {
1337 : .install = !0,
1338 : .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
1339 : };
1340 :
1341 : tmp = fib_entry_src_action_cover_update(fib_entry, esrc);
1342 : res.bw_reason |= tmp.bw_reason;
1343 : }
1344 : else
1345 : {
1346 : fib_entry_src_action_cover_update(fib_entry, esrc);
1347 : }
1348 : }
1349 : index++;
1350 : }));
1351 :
1352 14 : if (res.install)
1353 : {
1354 13 : fib_entry_src_action_reactivate(fib_entry,
1355 13 : fib_entry_src_get_source(
1356 13 : fib_entry_get_best_src_i(fib_entry)));
1357 13 : fib_entry = fib_entry_post_install_actions(fib_entry,
1358 : best_source,
1359 : bflags);
1360 : }
1361 : else
1362 : {
1363 1 : fib_entry_src_action_uninstall(fib_entry);
1364 : }
1365 :
1366 14 : if (FIB_NODE_BW_REASON_FLAG_NONE != res.bw_reason)
1367 : {
1368 : /*
1369 : * time for walkies fido.
1370 : */
1371 4 : fib_node_back_walk_ctx_t bw_ctx = {
1372 4 : .fnbw_reason = res.bw_reason,
1373 : };
1374 :
1375 4 : fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_index, &bw_ctx);
1376 : }
1377 14 : FIB_ENTRY_DBG(fib_entry, "cover-updated");
1378 14 : }
1379 :
1380 : int
1381 8452 : fib_entry_recursive_loop_detect (fib_node_index_t entry_index,
1382 : fib_node_index_t **entry_indicies)
1383 : {
1384 : fib_entry_t *fib_entry;
1385 : int was_looped, is_looped;
1386 :
1387 8452 : fib_entry = fib_entry_get(entry_index);
1388 :
1389 8452 : if (FIB_NODE_INDEX_INVALID != fib_entry->fe_parent)
1390 : {
1391 8448 : fib_node_index_t *entries = *entry_indicies;
1392 :
1393 8448 : vec_add1(entries, entry_index);
1394 8448 : was_looped = fib_path_list_is_looped(fib_entry->fe_parent);
1395 8448 : is_looped = fib_path_list_recursive_loop_detect(fib_entry->fe_parent,
1396 : &entries);
1397 :
1398 8448 : *entry_indicies = entries;
1399 :
1400 8448 : if (!!was_looped != !!is_looped)
1401 : {
1402 : /*
1403 : * re-evaluate all the entry's forwarding
1404 : * NOTE: this is an inplace modify
1405 : */
1406 : fib_entry_delegate_type_t fdt;
1407 : fib_entry_delegate_t *fed;
1408 :
1409 210 : FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
1410 : {
1411 : fib_entry_src_mk_lb(fib_entry,
1412 : fib_entry_get_best_source(entry_index),
1413 : fib_entry_delegate_type_to_chain_type(fdt),
1414 : &fed->fd_dpo);
1415 : });
1416 : }
1417 : }
1418 : else
1419 : {
1420 : /*
1421 : * the entry is currently not linked to a path-list. this happens
1422 : * when it is this entry that is re-linking path-lists and has thus
1423 : * broken the loop
1424 : */
1425 4 : is_looped = 0;
1426 : }
1427 :
1428 8452 : return (is_looped);
1429 : }
1430 :
1431 : /*
1432 : * fib_entry_attached_cross_table
1433 : *
1434 : * Return true if the route is attached via an interface that
1435 : * is not in the same table as the route
1436 : */
1437 : static int
1438 7 : fib_entry_attached_cross_table (const fib_entry_t *fib_entry,
1439 : u32 fib_index)
1440 : {
1441 7 : const fib_prefix_t *pfx = &fib_entry->fe_prefix;
1442 :
1443 7 : switch (pfx->fp_proto)
1444 : {
1445 0 : case FIB_PROTOCOL_MPLS:
1446 : /* MPLS routes are never imported/exported */
1447 0 : return (0);
1448 2 : case FIB_PROTOCOL_IP6:
1449 : /* Ignore link local addresses these also can't be imported/exported */
1450 2 : if (ip6_address_is_link_local_unicast (&pfx->fp_addr.ip6))
1451 : {
1452 0 : return (0);
1453 : }
1454 2 : break;
1455 5 : case FIB_PROTOCOL_IP4:
1456 5 : break;
1457 : }
1458 :
1459 7 : return (fib_entry->fe_fib_index != fib_index);
1460 : }
1461 :
1462 : /*
1463 : * fib_entry_back_walk_notify
1464 : *
1465 : * A back walk has reach this entry.
1466 : */
1467 : static fib_node_back_walk_rc_t
1468 25425 : fib_entry_back_walk_notify (fib_node_t *node,
1469 : fib_node_back_walk_ctx_t *ctx)
1470 : {
1471 : fib_source_t best_source;
1472 : fib_entry_t *fib_entry;
1473 : fib_entry_src_t *bsrc;
1474 :
1475 25425 : fib_entry = fib_entry_from_fib_node(node);
1476 25425 : bsrc = fib_entry_get_best_src_i(fib_entry);
1477 25425 : best_source = fib_entry_src_get_source(bsrc);
1478 :
1479 25425 : if (FIB_NODE_BW_REASON_FLAG_INTERFACE_BIND & ctx->fnbw_reason)
1480 : {
1481 : fib_entry_flag_t bflags;
1482 :
1483 7 : bflags = fib_entry_src_get_flags(bsrc);
1484 :
1485 7 : fib_entry_src_action_reactivate(fib_entry, best_source);
1486 :
1487 : /* re-evaluate whether the prefix is cross table */
1488 7 : if (fib_entry_attached_cross_table(
1489 4 : fib_entry, ctx->interface_bind.fnbw_to_fib_index) &&
1490 4 : !(bsrc->fes_entry_flags & FIB_ENTRY_FLAG_NO_ATTACHED_EXPORT))
1491 : {
1492 4 : bsrc->fes_entry_flags |= FIB_ENTRY_FLAG_IMPORT;
1493 : }
1494 : else
1495 : {
1496 3 : bsrc->fes_entry_flags &= ~FIB_ENTRY_FLAG_IMPORT;
1497 : }
1498 :
1499 7 : fib_entry = fib_entry_post_flag_update_actions(
1500 : fib_entry, bflags,
1501 : ctx->interface_bind.fnbw_to_fib_index);
1502 : }
1503 25418 : else if (FIB_NODE_BW_REASON_FLAG_EVALUATE & ctx->fnbw_reason ||
1504 14696 : FIB_NODE_BW_REASON_FLAG_ADJ_UPDATE & ctx->fnbw_reason ||
1505 11716 : FIB_NODE_BW_REASON_FLAG_ADJ_DOWN & ctx->fnbw_reason ||
1506 6165 : FIB_NODE_BW_REASON_FLAG_INTERFACE_UP & ctx->fnbw_reason ||
1507 5371 : FIB_NODE_BW_REASON_FLAG_INTERFACE_DOWN & ctx->fnbw_reason ||
1508 144 : FIB_NODE_BW_REASON_FLAG_INTERFACE_BIND & ctx->fnbw_reason ||
1509 144 : FIB_NODE_BW_REASON_FLAG_INTERFACE_DELETE & ctx->fnbw_reason)
1510 : {
1511 25293 : fib_entry_src_action_reactivate(fib_entry, best_source);
1512 : }
1513 :
1514 : /*
1515 : * all other walk types can be reclassifed to a re-evaluate to
1516 : * all recursive dependents.
1517 : * By reclassifying we ensure that should any of these walk types meet
1518 : * they can be merged.
1519 : */
1520 25425 : ctx->fnbw_reason = FIB_NODE_BW_REASON_FLAG_EVALUATE;
1521 :
1522 : /*
1523 : * ... and nothing is forced sync from now on.
1524 : */
1525 25425 : ctx->fnbw_flags &= ~FIB_NODE_BW_FLAG_FORCE_SYNC;
1526 :
1527 25425 : FIB_ENTRY_DBG(fib_entry, "bw:%U",
1528 : format_fib_node_bw_reason, ctx->fnbw_reason);
1529 :
1530 : /*
1531 : * propagate the backwalk further if we haven't already reached the
1532 : * maximum depth.
1533 : */
1534 25425 : fib_walk_sync(FIB_NODE_TYPE_ENTRY,
1535 : fib_entry_get_index(fib_entry),
1536 : ctx);
1537 :
1538 25425 : return (FIB_NODE_BACK_WALK_CONTINUE);
1539 : }
1540 :
1541 : /*
1542 : * The FIB path-list's graph node virtual function table
1543 : */
1544 : static const fib_node_vft_t fib_entry_vft = {
1545 : .fnv_get = fib_entry_get_node,
1546 : .fnv_last_lock = fib_entry_last_lock_gone,
1547 : .fnv_back_walk = fib_entry_back_walk_notify,
1548 : .fnv_mem_show = fib_entry_show_memory,
1549 : };
1550 :
1551 : u32
1552 93281 : fib_entry_get_resolving_interface (fib_node_index_t entry_index)
1553 : {
1554 : fib_entry_t *fib_entry;
1555 :
1556 93281 : fib_entry = fib_entry_get(entry_index);
1557 :
1558 93279 : return (fib_path_list_get_resolving_interface(fib_entry->fe_parent));
1559 : }
1560 :
1561 : u32
1562 2121 : fib_entry_get_any_resolving_interface (fib_node_index_t entry_index)
1563 : {
1564 : const fib_entry_src_t *src;
1565 : fib_entry_t *fib_entry;
1566 : fib_source_t source;
1567 : u32 sw_if_index;
1568 :
1569 2121 : fib_entry = fib_entry_get(entry_index);
1570 :
1571 2135 : FOR_EACH_SRC_ADDED(fib_entry, src, source,
1572 : ({
1573 : sw_if_index = fib_entry_get_resolving_interface_for_source (entry_index,
1574 : source);
1575 :
1576 : if (~0 != sw_if_index)
1577 : break;
1578 : }));
1579 2121 : return (sw_if_index);
1580 : }
1581 :
1582 : fib_source_t
1583 7571 : fib_entry_get_best_source (fib_node_index_t entry_index)
1584 : {
1585 : fib_entry_t *fib_entry;
1586 : fib_entry_src_t *bsrc;
1587 :
1588 7571 : fib_entry = fib_entry_get(entry_index);
1589 :
1590 7571 : bsrc = fib_entry_get_best_src_i(fib_entry);
1591 7571 : return (fib_entry_src_get_source(bsrc));
1592 : }
1593 :
1594 : /**
1595 : * Return !0 is the entry represents a host prefix
1596 : */
1597 : int
1598 36564 : fib_entry_is_host (fib_node_index_t fib_entry_index)
1599 : {
1600 36564 : return (fib_prefix_is_host(fib_entry_get_prefix(fib_entry_index)));
1601 : }
1602 :
1603 : /**
1604 : * Return !0 is the entry is resolved, i.e. will return a valid forwarding
1605 : * chain
1606 : */
1607 : int
1608 5037 : fib_entry_is_resolved (fib_node_index_t fib_entry_index)
1609 : {
1610 : fib_entry_delegate_t *fed;
1611 : fib_entry_t *fib_entry;
1612 :
1613 5037 : fib_entry = fib_entry_get(fib_entry_index);
1614 :
1615 5037 : fed = fib_entry_delegate_find(fib_entry, FIB_ENTRY_DELEGATE_BFD);
1616 :
1617 5037 : if (NULL == fed)
1618 : {
1619 : /*
1620 : * no BFD tracking - consider it resolved.
1621 : */
1622 5032 : return (!0);
1623 : }
1624 : else
1625 : {
1626 : /*
1627 : * defer to the state of the BFD tracking
1628 : */
1629 5 : return (FIB_BFD_STATE_UP == fed->fd_bfd_state);
1630 : }
1631 : }
1632 :
1633 : void
1634 138 : fib_entry_set_flow_hash_config (fib_node_index_t fib_entry_index,
1635 : flow_hash_config_t hash_config)
1636 : {
1637 : fib_entry_t *fib_entry;
1638 :
1639 138 : fib_entry = fib_entry_get(fib_entry_index);
1640 :
1641 : /*
1642 : * pass the hash-config on to the load-balance object where it is cached.
1643 : * we can ignore LBs in the delegate chains, since they will not be of the
1644 : * correct protocol type (i.e. they are not IP)
1645 : * There's no way, nor need, to change the hash config for MPLS.
1646 : */
1647 138 : if (dpo_id_is_valid(&fib_entry->fe_lb))
1648 : {
1649 : load_balance_t *lb;
1650 :
1651 138 : ASSERT(DPO_LOAD_BALANCE == fib_entry->fe_lb.dpoi_type);
1652 :
1653 138 : lb = load_balance_get(fib_entry->fe_lb.dpoi_index);
1654 :
1655 : /*
1656 : * atomic update for packets in flight
1657 : */
1658 138 : lb->lb_hash_config = hash_config;
1659 : }
1660 138 : }
1661 :
1662 : u32
1663 159404 : fib_entry_get_stats_index (fib_node_index_t fib_entry_index)
1664 : {
1665 : fib_entry_t *fib_entry;
1666 :
1667 159404 : fib_entry = fib_entry_get(fib_entry_index);
1668 :
1669 159404 : return (fib_entry->fe_lb.dpoi_index);
1670 : }
1671 :
1672 : static int
1673 10770 : fib_ip4_address_compare (const ip4_address_t * a1,
1674 : const ip4_address_t * a2)
1675 : {
1676 : /*
1677 : * IP addresses are unsigned ints. the return value here needs to be signed
1678 : * a simple subtraction won't cut it.
1679 : * If the addresses are the same, the sort order is undefined, so phoey.
1680 : */
1681 10770 : return ((clib_net_to_host_u32(a1->data_u32) >
1682 10770 : clib_net_to_host_u32(a2->data_u32) ) ?
1683 10770 : 1 : -1);
1684 : }
1685 :
1686 : static int
1687 4925 : fib_ip6_address_compare (const ip6_address_t * a1,
1688 : const ip6_address_t * a2)
1689 : {
1690 : int i;
1691 21810 : for (i = 0; i < ARRAY_LEN (a1->as_u16); i++)
1692 : {
1693 21810 : int cmp = (clib_net_to_host_u16 (a1->as_u16[i]) -
1694 21810 : clib_net_to_host_u16 (a2->as_u16[i]));
1695 21810 : if (cmp != 0)
1696 4925 : return cmp;
1697 : }
1698 0 : return 0;
1699 : }
1700 :
1701 : static int
1702 117586 : fib_entry_cmp (fib_node_index_t fib_entry_index1,
1703 : fib_node_index_t fib_entry_index2)
1704 : {
1705 : fib_entry_t *fib_entry1, *fib_entry2;
1706 117586 : int cmp = 0;
1707 :
1708 117586 : fib_entry1 = fib_entry_get(fib_entry_index1);
1709 117586 : fib_entry2 = fib_entry_get(fib_entry_index2);
1710 :
1711 117586 : switch (fib_entry1->fe_prefix.fp_proto)
1712 : {
1713 10770 : case FIB_PROTOCOL_IP4:
1714 10770 : cmp = fib_ip4_address_compare(&fib_entry1->fe_prefix.fp_addr.ip4,
1715 : &fib_entry2->fe_prefix.fp_addr.ip4);
1716 10770 : break;
1717 4925 : case FIB_PROTOCOL_IP6:
1718 4925 : cmp = fib_ip6_address_compare(&fib_entry1->fe_prefix.fp_addr.ip6,
1719 : &fib_entry2->fe_prefix.fp_addr.ip6);
1720 4925 : break;
1721 101891 : case FIB_PROTOCOL_MPLS:
1722 101891 : cmp = (fib_entry1->fe_prefix.fp_label - fib_entry2->fe_prefix.fp_label);
1723 :
1724 101891 : if (0 == cmp)
1725 : {
1726 9989 : cmp = (fib_entry1->fe_prefix.fp_eos - fib_entry2->fe_prefix.fp_eos);
1727 : }
1728 101891 : break;
1729 : }
1730 :
1731 117586 : if (0 == cmp) {
1732 0 : cmp = (fib_entry1->fe_prefix.fp_len - fib_entry2->fe_prefix.fp_len);
1733 : }
1734 117586 : return (cmp);
1735 : }
1736 :
1737 : int
1738 117586 : fib_entry_cmp_for_sort (void *i1, void *i2)
1739 : {
1740 117586 : fib_node_index_t *fib_entry_index1 = i1, *fib_entry_index2 = i2;
1741 :
1742 117586 : return (fib_entry_cmp(*fib_entry_index1,
1743 : *fib_entry_index2));
1744 : }
1745 :
1746 : void
1747 123405 : fib_entry_lock (fib_node_index_t fib_entry_index)
1748 : {
1749 : fib_entry_t *fib_entry;
1750 :
1751 123405 : fib_entry = fib_entry_get(fib_entry_index);
1752 :
1753 123405 : fib_node_lock(&fib_entry->fe_node);
1754 123405 : }
1755 :
1756 : void
1757 103319 : fib_entry_unlock (fib_node_index_t fib_entry_index)
1758 : {
1759 : fib_entry_t *fib_entry;
1760 :
1761 103319 : fib_entry = fib_entry_get(fib_entry_index);
1762 :
1763 103319 : fib_node_unlock(&fib_entry->fe_node);
1764 103319 : }
1765 :
1766 : void
1767 575 : fib_entry_module_init (void)
1768 : {
1769 575 : fib_node_register_type(FIB_NODE_TYPE_ENTRY, &fib_entry_vft);
1770 575 : fib_entry_logger = vlib_log_register_class("fib", "entry");
1771 :
1772 575 : fib_entry_track_module_init();
1773 575 : }
1774 :
1775 : fib_route_path_t *
1776 175055 : fib_entry_encode (fib_node_index_t fib_entry_index)
1777 : {
1778 : fib_path_ext_list_t *ext_list;
1779 175055 : fib_path_encode_ctx_t ctx = {
1780 : .rpaths = NULL,
1781 : };
1782 : fib_entry_t *fib_entry;
1783 : fib_entry_src_t *bsrc;
1784 :
1785 175055 : ext_list = NULL;
1786 175055 : fib_entry = fib_entry_get(fib_entry_index);
1787 175055 : bsrc = fib_entry_get_best_src_i(fib_entry);
1788 :
1789 175055 : if (bsrc)
1790 : {
1791 175055 : ext_list = &bsrc->fes_path_exts;
1792 : }
1793 :
1794 175055 : if (FIB_NODE_INDEX_INVALID != fib_entry->fe_parent)
1795 : {
1796 175055 : fib_path_list_walk_w_ext(fib_entry->fe_parent,
1797 : ext_list,
1798 : fib_path_encode,
1799 : &ctx);
1800 : }
1801 :
1802 175055 : return (ctx.rpaths);
1803 : }
1804 :
1805 : const fib_prefix_t *
1806 243262 : fib_entry_get_prefix (fib_node_index_t fib_entry_index)
1807 : {
1808 : fib_entry_t *fib_entry;
1809 :
1810 243262 : fib_entry = fib_entry_get(fib_entry_index);
1811 :
1812 243262 : return (&fib_entry->fe_prefix);
1813 : }
1814 :
1815 : u32
1816 337648 : fib_entry_get_fib_index (fib_node_index_t fib_entry_index)
1817 : {
1818 : fib_entry_t *fib_entry;
1819 :
1820 337648 : fib_entry = fib_entry_get(fib_entry_index);
1821 :
1822 337648 : return (fib_entry->fe_fib_index);
1823 : }
1824 :
1825 : u32
1826 58 : fib_entry_pool_size (void)
1827 : {
1828 58 : return (pool_elts(fib_entry_pool));
1829 : }
1830 :
1831 : #if CLIB_DEBUG > 0
1832 : void
1833 0 : fib_table_assert_empty (const fib_table_t *fib_table)
1834 : {
1835 0 : fib_node_index_t *fei, *feis = NULL;
1836 : fib_entry_t *fib_entry;
1837 :
1838 0 : pool_foreach (fib_entry, fib_entry_pool)
1839 : {
1840 0 : if (fib_entry->fe_fib_index == fib_table->ft_index)
1841 0 : vec_add1 (feis, fib_entry_get_index(fib_entry));
1842 : }
1843 :
1844 0 : if (vec_len(feis))
1845 : {
1846 0 : vec_foreach (fei, feis)
1847 0 : clib_error ("%U", format_fib_entry, *fei, FIB_ENTRY_FORMAT_DETAIL);
1848 : }
1849 :
1850 0 : ASSERT(0);
1851 0 : }
1852 : #endif
1853 :
1854 : static clib_error_t *
1855 3 : show_fib_entry_command (vlib_main_t * vm,
1856 : unformat_input_t * input,
1857 : vlib_cli_command_t * cmd)
1858 : {
1859 : fib_node_index_t fei;
1860 :
1861 3 : if (unformat (input, "%d", &fei))
1862 : {
1863 : /*
1864 : * show one in detail
1865 : */
1866 2 : if (!pool_is_free_index(fib_entry_pool, fei))
1867 : {
1868 1 : vlib_cli_output (vm, "%d@%U",
1869 : fei,
1870 : format_fib_entry, fei,
1871 : FIB_ENTRY_FORMAT_DETAIL2);
1872 : }
1873 : else
1874 : {
1875 1 : vlib_cli_output (vm, "entry %d invalid", fei);
1876 : }
1877 : }
1878 : else
1879 : {
1880 : /*
1881 : * show all
1882 : */
1883 1 : vlib_cli_output (vm, "FIB Entries:");
1884 8 : pool_foreach_index (fei, fib_entry_pool)
1885 : {
1886 7 : vlib_cli_output (vm, "%d@%U",
1887 : fei,
1888 : format_fib_entry, fei,
1889 : FIB_ENTRY_FORMAT_BRIEF);
1890 : }
1891 : }
1892 :
1893 3 : return (NULL);
1894 : }
1895 :
1896 285289 : VLIB_CLI_COMMAND (show_fib_entry, static) = {
1897 : .path = "show fib entry",
1898 : .function = show_fib_entry_command,
1899 : .short_help = "show fib entry",
1900 : };
|
