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:
7 * http://www.apache.org/licenses/LICENSE-2.0
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.
16 #ifndef __FIB_TABLE_H__
17 #define __FIB_TABLE_H__
19 #include <vnet/ip/ip.h>
20 #include <vnet/adj/adj.h>
21 #include <vnet/fib/fib_entry.h>
22 #include <vnet/mpls/mpls.h>
23 #include <vnet/mpls/packet.h>
26 * Flags for the source data
28 typedef enum fib_table_attribute_t_ {
30 * Marker. Add new values after this one.
32 FIB_TABLE_ATTRIBUTE_FIRST,
34 * the table is for IP6 link local addresses
36 FIB_TABLE_ATTRIBUTE_IP6_LL = FIB_TABLE_ATTRIBUTE_FIRST,
38 * the table is currently resync-ing
40 FIB_TABLE_ATTRIBUTE_RESYNC,
42 * Marker. add new entries before this one.
44 FIB_TABLE_ATTRIBUTE_LAST = FIB_TABLE_ATTRIBUTE_RESYNC,
45 } fib_table_attribute_t;
47 #define FIB_TABLE_ATTRIBUTE_MAX (FIB_TABLE_ATTRIBUTE_LAST+1)
49 #define FIB_TABLE_ATTRIBUTES { \
50 [FIB_TABLE_ATTRIBUTE_IP6_LL] = "ip6-ll", \
51 [FIB_TABLE_ATTRIBUTE_RESYNC] = "resync", \
54 #define FOR_EACH_FIB_TABLE_ATTRIBUTE(_item) \
55 for (_item = FIB_TABLE_ATTRIBUTE_FIRST; \
56 _item < FIB_TABLE_ATTRIBUTE_MAX; \
59 typedef enum fib_table_flags_t_ {
60 FIB_TABLE_FLAG_NONE = 0,
61 FIB_TABLE_FLAG_IP6_LL = (1 << FIB_TABLE_ATTRIBUTE_IP6_LL),
62 FIB_TABLE_FLAG_RESYNC = (1 << FIB_TABLE_ATTRIBUTE_RESYNC),
63 } __attribute__ ((packed)) fib_table_flags_t;
65 extern u8* format_fib_table_flags(u8 *s, va_list *args);
69 * A protocol Independent FIB table
71 typedef struct fib_table_t_
74 * Which protocol this table serves. Used to switch on the union above.
76 fib_protocol_t ft_proto;
81 fib_table_flags_t ft_flags;
84 * per-source number of locks on the table
90 * Table ID (hash key) for this FIB.
95 * Index into FIB vector.
97 fib_node_index_t ft_index;
100 * flow hash configuration
102 u32 ft_flow_hash_config;
105 * Per-source route counters
107 u32 *ft_src_route_counts;
110 * Total route counters
112 u32 ft_total_route_counts;
115 * Epoch - number of resyncs performed
127 * Format the description/name of the table
129 extern u8* format_fib_table_name(u8* s, va_list *ap);
133 * Perfom a longest prefix match in the non-forwarding table
136 * The index of the FIB
139 * The prefix to lookup
142 * The index of the fib_entry_t for the best match, which may be the default route
144 extern fib_node_index_t fib_table_lookup(u32 fib_index,
145 const fib_prefix_t *prefix);
149 * Perfom an exact match in the non-forwarding table
152 * The index of the FIB
155 * The prefix to lookup
158 * The index of the fib_entry_t for the exact match, or INVALID
159 * is there is no match.
161 extern fib_node_index_t fib_table_lookup_exact_match(u32 fib_index,
162 const fib_prefix_t *prefix);
166 * Get the less specific (covering) prefix
169 * The index of the FIB
172 * The prefix to lookup
175 * The index of the less specific fib_entry_t.
177 extern fib_node_index_t fib_table_get_less_specific(u32 fib_index,
178 const fib_prefix_t *prefix);
182 * Add a 'special' entry to the FIB.
183 * A special entry is an entry that the FIB is not expect to resolve
184 * via the usual mechanisms (i.e. recurisve or neighbour adj DB lookup).
185 * Instead the will link to a DPO valid for the source and/or the flags.
186 * This add is reference counting per-source. So n 'removes' are required
187 * for n 'adds', if the entry is no longer required.
188 * If the source needs to provide non-default forwarding use:
189 * fib_table_entry_special_dpo_add()
192 * The index of the FIB
198 * The ID of the client/source adding the entry.
201 * Flags for the entry.
204 * the index of the fib_entry_t that is created (or exists already).
206 extern fib_node_index_t fib_table_entry_special_add(u32 fib_index,
207 const fib_prefix_t *prefix,
209 fib_entry_flag_t flags);
213 * Add a 'special' entry to the FIB that links to the DPO passed
214 * A special entry is an entry that the FIB is not expect to resolve
215 * via the usual mechanisms (i.e. recurisve or neighbour adj DB lookup).
216 * Instead the client/source provides the DPO to link to.
217 * This add is reference counting per-source. So n 'removes' are required
218 * for n 'adds', if the entry is no longer required.
221 * The index of the FIB
227 * The ID of the client/source adding the entry.
230 * Flags for the entry.
233 * The DPO to link to.
236 * the index of the fib_entry_t that is created (or existed already).
238 extern fib_node_index_t fib_table_entry_special_dpo_add(u32 fib_index,
239 const fib_prefix_t *prefix,
241 fib_entry_flag_t stype,
242 const dpo_id_t *dpo);
246 * Update a 'special' entry to the FIB that links to the DPO passed
247 * A special entry is an entry that the FIB is not expect to resolve
248 * via the usual mechanisms (i.e. recurisve or neighbour adj DB lookup).
249 * Instead the client/source provides the DPO to link to.
250 * Special entries are add/remove reference counted per-source. So n
251 * 'removes' are required for n 'adds', if the entry is no longer required.
252 * An 'update' is an 'add' if no 'add' has already been called, otherwise an 'add'
253 * is therefore assumed to act on the reference instance of that add.
255 * @param fib_entry_index
256 * The index of the FIB entry to update
259 * The ID of the client/source adding the entry.
262 * Flags for the entry.
265 * The DPO to link to.
268 * the index of the fib_entry_t that is created (or existed already).
270 extern fib_node_index_t fib_table_entry_special_dpo_update (u32 fib_index,
271 const fib_prefix_t *prefix,
273 fib_entry_flag_t stype,
274 const dpo_id_t *dpo);
278 * Remove a 'special' entry from the FIB.
279 * This add is reference counting per-source. So n 'removes' are required
280 * for n 'adds', if the entry is no longer required.
283 * The index of the FIB
286 * The prefix to remove
289 * The ID of the client/source adding the entry.
292 extern void fib_table_entry_special_remove(u32 fib_index,
293 const fib_prefix_t *prefix,
294 fib_source_t source);
298 * Add one path to an entry (aka route) in the FIB. If the entry does not
299 * exist, it will be created.
300 * See the documentation for fib_route_path_t for more descirptions of
301 * the path parameters.
304 * The index of the FIB
307 * The prefix for the entry to add
310 * The ID of the client/source adding the entry.
313 * Flags for the entry.
315 * @paran next_hop_proto
316 * The protocol of the next hop. This cannot be derived in the event that
317 * the next hop is all zeros.
320 * The address of the next-hop.
323 * The index of the interface.
325 * @param next_hop_fib_index,
326 * The fib index of the next-hop for recursive resolution
328 * @param next_hop_weight
329 * [un]equal cost path weight
331 * @param next_hop_label_stack
332 * The path's out-going label stack. NULL is there is none.
338 * the index of the fib_entry_t that is created (or existed already).
340 extern fib_node_index_t fib_table_entry_path_add(u32 fib_index,
341 const fib_prefix_t *prefix,
343 fib_entry_flag_t flags,
344 dpo_proto_t next_hop_proto,
345 const ip46_address_t *next_hop,
346 u32 next_hop_sw_if_index,
347 u32 next_hop_fib_index,
349 fib_mpls_label_t *next_hop_label_stack,
350 fib_route_path_flags_t pf);
353 * Add n paths to an entry (aka route) in the FIB. If the entry does not
354 * exist, it will be created.
355 * See the documentation for fib_route_path_t for more descirptions of
356 * the path parameters.
359 * The index of the FIB
362 * The prefix for the entry to add
365 * The ID of the client/source adding the entry.
368 * Flags for the entry.
371 * A vector of paths. Not const since they may be modified.
374 * the index of the fib_entry_t that is created (or existed already).
376 extern fib_node_index_t fib_table_entry_path_add2(u32 fib_index,
377 const fib_prefix_t *prefix,
379 fib_entry_flag_t flags,
380 fib_route_path_t *rpath);
384 * remove one path to an entry (aka route) in the FIB. If this is the entry's
385 * last path, then the entry will be removed, unless it has other sources.
386 * See the documentation for fib_route_path_t for more descirptions of
387 * the path parameters.
390 * The index of the FIB
393 * The prefix for the entry to add
396 * The ID of the client/source adding the entry.
398 * @paran next_hop_proto
399 * The protocol of the next hop. This cannot be derived in the event that
400 * the next hop is all zeros.
403 * The address of the next-hop.
406 * The index of the interface.
408 * @param next_hop_fib_index,
409 * The fib index of the next-hop for recursive resolution
411 * @param next_hop_weight
412 * [un]equal cost path weight
417 extern void fib_table_entry_path_remove(u32 fib_index,
418 const fib_prefix_t *prefix,
420 dpo_proto_t next_hop_proto,
421 const ip46_address_t *next_hop,
422 u32 next_hop_sw_if_index,
423 u32 next_hop_fib_index,
425 fib_route_path_flags_t pf);
429 * Remove n paths to an entry (aka route) in the FIB. If this is the entry's
430 * last path, then the entry will be removed, unless it has other sources.
431 * See the documentation for fib_route_path_t for more descirptions of
432 * the path parameters.
435 * The index of the FIB
438 * The prefix for the entry to add
441 * The ID of the client/source adding the entry.
446 extern void fib_table_entry_path_remove2(u32 fib_index,
447 const fib_prefix_t *prefix,
449 fib_route_path_t *paths);
453 * Update an entry to have a new set of paths. If the entry does not
454 * exist, it will be created.
455 * The difference between an 'path-add' and an update, is that path-add is
456 * an incremental addition of paths, whereas an update is a wholesale swap.
459 * The index of the FIB
462 * The prefix for the entry to add
465 * The ID of the client/source adding the entry.
468 * A vector of paths. Not const since they may be modified.
471 * the index of the fib_entry_t that is created (or existed already).
473 extern fib_node_index_t fib_table_entry_update(u32 fib_index,
474 const fib_prefix_t *prefix,
476 fib_entry_flag_t flags,
477 fib_route_path_t *paths);
481 * Update the entry to have just one path. If the entry does not
482 * exist, it will be created.
483 * See the documentation for fib_route_path_t for more descirptions of
484 * the path parameters.
487 * The index of the FIB
490 * The prefix for the entry to add
493 * The ID of the client/source adding the entry.
496 * Flags for the entry.
498 * @paran next_hop_proto
499 * The protocol of the next hop. This cannot be derived in the event that
500 * the next hop is all zeros.
503 * The address of the next-hop.
506 * The index of the interface.
508 * @param next_hop_fib_index,
509 * The fib index of the next-hop for recursive resolution
511 * @param next_hop_weight
512 * [un]equal cost path weight
514 * @param next_hop_label_stack
515 * The path's out-going label stack. NULL is there is none.
521 * the index of the fib_entry_t that is created (or existed already).
523 extern fib_node_index_t fib_table_entry_update_one_path(u32 fib_index,
524 const fib_prefix_t *prefix,
526 fib_entry_flag_t flags,
527 dpo_proto_t next_hop_proto,
528 const ip46_address_t *next_hop,
529 u32 next_hop_sw_if_index,
530 u32 next_hop_fib_index,
532 fib_mpls_label_t *next_hop_label_stack,
533 fib_route_path_flags_t pf);
537 * Add a MPLS local label for the prefix/route. If the entry does not
538 * exist, it will be created. In theory more than one local label can be
539 * added, but this is not yet supported.
542 * The index of the FIB
545 * The prefix for the entry to which to add the label
548 * The MPLS label to add
551 * the index of the fib_entry_t that is created (or existed already).
553 extern fib_node_index_t fib_table_entry_local_label_add(u32 fib_index,
554 const fib_prefix_t *prefix,
558 * remove a MPLS local label for the prefix/route.
561 * The index of the FIB
564 * The prefix for the entry to which to add the label
567 * The MPLS label to add
569 extern void fib_table_entry_local_label_remove(u32 fib_index,
570 const fib_prefix_t *prefix,
575 * Delete a FIB entry. If the entry has no more sources, then it is
576 * removed from the table.
579 * The index of the FIB
582 * The prefix for the entry to remove
585 * The ID of the client/source adding the entry.
587 extern void fib_table_entry_delete(u32 fib_index,
588 const fib_prefix_t *prefix,
589 fib_source_t source);
593 * Delete a FIB entry. If the entry has no more sources, then it is
594 * removed from the table.
597 * The index of the FIB entry
600 * The ID of the client/source adding the entry.
602 extern void fib_table_entry_delete_index(fib_node_index_t entry_index,
603 fib_source_t source);
607 * Return the stats index for a FIB entry
609 * The table's FIB index
611 * The entry's prefix's
613 extern u32 fib_table_entry_get_stats_index(u32 fib_index,
614 const fib_prefix_t *prefix);
618 * Flush all entries from a table for the source
621 * The index of the FIB
624 * The protocol of the entries in the table
627 * the source to flush
629 extern void fib_table_flush(u32 fib_index,
630 fib_protocol_t proto,
631 fib_source_t source);
635 * Resync all entries from a table for the source
636 * this is the mark part of the mark and sweep algorithm.
637 * All entries in this FIB that are sourced by 'source' are marked
641 * The index of the FIB
644 * The protocol of the entries in the table
647 * the source to flush
649 extern void fib_table_mark(u32 fib_index,
650 fib_protocol_t proto,
651 fib_source_t source);
655 * Signal that the table has converged, i.e. all updates are complete.
656 * this is the sweep part of the mark and sweep algorithm.
657 * All entries in this FIB that are sourced by 'source' and marked
658 * as stale are flushed.
661 * The index of the FIB
664 * The protocol of the entries in the table
667 * the source to flush
669 extern void fib_table_sweep(u32 fib_index,
670 fib_protocol_t proto,
671 fib_source_t source);
675 * Get the index of the FIB bound to the interface
678 * The protocol of the FIB (and thus the entries therein)
681 * The interface index
684 * The index of the FIB
686 extern u32 fib_table_get_index_for_sw_if_index(fib_protocol_t proto,
691 * Get the Table-ID of the FIB bound to the interface
694 * The protocol of the FIB (and thus the entries therein)
697 * The interface index
700 * The tableID of the FIB
702 extern u32 fib_table_get_table_id_for_sw_if_index(fib_protocol_t proto,
707 * Get the Table-ID of the FIB from protocol and index
713 * The protocol of the FIB (and thus the entries therein)
716 * The tableID of the FIB
718 extern u32 fib_table_get_table_id(u32 fib_index, fib_protocol_t proto);
722 * Get the index of the FIB for a Table-ID. This DOES NOT create the
723 * FIB if it does not exist.
726 * The protocol of the FIB (and thus the entries therein)
732 * The index of the FIB, which may be INVALID.
734 extern u32 fib_table_find(fib_protocol_t proto, u32 table_id);
739 * Get the index of the FIB for a Table-ID. This DOES create the
740 * FIB if it does not exist.
743 * The protocol of the FIB (and thus the entries therein)
749 * The index of the FIB
752 * The ID of the client/source.
754 extern u32 fib_table_find_or_create_and_lock(fib_protocol_t proto,
756 fib_source_t source);
760 * Get the index of the FIB for a Table-ID. This DOES create the
761 * FIB if it does not exist.
764 * The protocol of the FIB (and thus the entries therein)
770 * The index of the FIB
773 * The ID of the client/source.
776 * The client is choosing the name they want the table to have
778 extern u32 fib_table_find_or_create_and_lock_w_name(fib_protocol_t proto,
785 * Create a new table with no table ID. This means it does not get
786 * added to the hash-table and so can only be found by using the index returned.
789 * The protocol of the FIB (and thus the entries therein)
792 * A string to describe the table
795 * The ID of the client/source.
798 * The index of the FIB
800 extern u32 fib_table_create_and_lock(fib_protocol_t proto,
802 const char *const fmt,
807 * Get the flow hash configured used by the table
810 * The index of the FIB
813 * The protocol the packets the flow hash will be calculated for.
815 * @return The flow hash config
817 extern flow_hash_config_t fib_table_get_flow_hash_config(u32 fib_index,
818 fib_protocol_t proto);
822 * Get the flow hash configured used by the protocol
825 * The protocol of the FIB (and thus the entries therein)
827 * @return The flow hash config
829 extern flow_hash_config_t fib_table_get_default_flow_hash_config(fib_protocol_t proto);
833 * Set the flow hash configured used by the table
836 * The index of the FIB
839 * The protocol of the FIB (and thus the entries therein)
842 * The flow-hash config to set
846 extern void fib_table_set_flow_hash_config(u32 fib_index,
847 fib_protocol_t proto,
848 flow_hash_config_t hash_config);
852 * Take a reference counting lock on the table
855 * The index of the FIB
858 * The protocol of the FIB (and thus the entries therein)
861 * The ID of the client/source.
863 extern void fib_table_unlock(u32 fib_index,
864 fib_protocol_t proto,
865 fib_source_t source);
869 * Release a reference counting lock on the table. When the last lock
870 * has gone. the FIB is deleted.
873 * The index of the FIB
876 * The protocol of the FIB (and thus the entries therein)
879 * The ID of the client/source.
881 extern void fib_table_lock(u32 fib_index,
882 fib_protocol_t proto,
883 fib_source_t source);
887 * Return the number of entries in the FIB added by a given source.
890 * The index of the FIB
893 * The protocol of the FIB (and thus the entries therein)
895 * @return number of sourced entries.
897 extern u32 fib_table_get_num_entries(u32 fib_index,
898 fib_protocol_t proto,
899 fib_source_t source);
903 * Get a pointer to a FIB table
905 extern fib_table_t *fib_table_get(fib_node_index_t index,
906 fib_protocol_t proto);
909 * @brief return code controlling how a table walk proceeds
911 typedef enum fib_table_walk_rc_t_
914 * Continue on to the next entry
916 FIB_TABLE_WALK_CONTINUE,
918 * Do no traverse down this sub-tree
920 FIB_TABLE_WALK_SUB_TREE_STOP,
922 * Stop the walk completely
925 } fib_table_walk_rc_t;
928 * @brief Call back function when walking entries in a FIB table
930 typedef fib_table_walk_rc_t (*fib_table_walk_fn_t)(fib_node_index_t fei,
934 * @brief Walk all entries in a FIB table
935 * N.B: This is NOT safe to deletes. If you need to delete walk the whole
936 * table and store elements in a vector, then delete the elements
938 extern void fib_table_walk(u32 fib_index,
939 fib_protocol_t proto,
940 fib_table_walk_fn_t fn,
944 * @brief Walk all entries in a FIB table
945 * N.B: This is NOT safe to deletes. If you need to delete walk the whole
946 * table and store elements in a vector, then delete the elements
948 extern void fib_table_walk_w_src(u32 fib_index,
949 fib_protocol_t proto,
951 fib_table_walk_fn_t fn,
955 * @brief Walk all entries in a sub-tree FIB table. The 'root' paraneter
956 * is the prefix at the root of the sub-tree.
957 * N.B: This is NOT safe to deletes. If you need to delete walk the whole
958 * table and store elements in a vector, then delete the elements
960 extern void fib_table_sub_tree_walk(u32 fib_index,
961 fib_protocol_t proto,
962 const fib_prefix_t *root,
963 fib_table_walk_fn_t fn,
967 * @brief format (display) the memory used by the FIB tables
969 extern u8 *format_fib_table_memory(u8 *s, va_list *args);
975 extern void fib_table_assert_empty(const fib_table_t *fib_table);