src/vnet/fib/fib_table.h - fdio/vpp - Gitiles

 /*
  * Copyright (c) 2016 Cisco and/or its affiliates.
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at:
  *
  *     http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */

 #ifndef __FIB_TABLE_H__
 #define __FIB_TABLE_H__

 #include <vnet/ip/ip.h>
 #include <vnet/adj/adj.h>
 #include <vnet/fib/fib_entry.h>
 #include <vnet/mpls/mpls.h>
 #include <vnet/mpls/packet.h>

 /**
  * Keep a lock per-source and a total
  */
 #define FIB_TABLE_N_LOCKS (FIB_SOURCE_MAX+1)
 #define FIB_TABLE_TOTAL_LOCKS FIB_SOURCE_MAX

 /**
  * Flags for the source data
  */
 typedef enum fib_table_attribute_t_ {
     /**
      * Marker. Add new values after this one.
      */
     FIB_TABLE_ATTRIBUTE_FIRST,
     /**
      * the table is for IP6 link local addresses
      */
     FIB_TABLE_ATTRIBUTE_IP6_LL = FIB_TABLE_ATTRIBUTE_FIRST,
     /**
      * Marker. add new entries before this one.
      */
     FIB_TABLE_ATTRIBUTE_LAST = FIB_TABLE_ATTRIBUTE_IP6_LL,
 } fib_table_attribute_t;

 #define FIB_TABLE_ATTRIBUTE_MAX (FIB_TABLE_ATTRIBUTE_LAST+1)

 #define FIB_TABLE_ATTRIBUTES {		         \
     [FIB_TABLE_ATTRIBUTE_IP6_LL]  = "ip6-ll",	 \
 }

 #define FOR_EACH_FIB_TABLE_ATTRIBUTE(_item)      	\
     for (_item = FIB_TABLE_ATTRIBUTE_FIRST;		\
 	 _item < FIB_TABLE_ATTRIBUTE_MAX;		\
 	 _item++)

 typedef enum fib_table_flags_t_ {
     FIB_TABLE_FLAG_NONE   = 0,
     FIB_TABLE_FLAG_IP6_LL  = (1 << FIB_TABLE_ATTRIBUTE_IP6_LL),
 } __attribute__ ((packed)) fib_table_flags_t;

 /**
  * @brief
  *   A protocol Independent FIB table
  */
 typedef struct fib_table_t_
 {
     /**
      * Which protocol this table serves. Used to switch on the union above.
      */
     fib_protocol_t ft_proto;

     /**
      * Table flags
      */
     fib_table_flags_t ft_flags;

     /**
      * per-source number of locks on the table
      */
     u16 ft_locks[FIB_TABLE_N_LOCKS];

     /**
      * Table ID (hash key) for this FIB.
      */
     u32 ft_table_id;

     /**
      * Index into FIB vector.
      */
     fib_node_index_t ft_index;

     /**
      * flow hash configuration
      */
     u32 ft_flow_hash_config;

     /**
      * Per-source route counters
      */
     u32 ft_src_route_counts[FIB_SOURCE_MAX];

     /**
      * Total route counters
      */
     u32 ft_total_route_counts;

     /**
      * Table description
      */
     u8* ft_desc;
 } fib_table_t;

 /**
  * @brief
  *  Format the description/name of the table
  */
 extern u8* format_fib_table_name(u8* s, va_list *ap);

 /**
  * @brief
  *  Perfom a longest prefix match in the non-forwarding table
  *
  * @param fib_index
  *  The index of the FIB
  *
  * @param prefix
  *  The prefix to lookup
  *
  * @return
  *  The index of the fib_entry_t for the best match, which may be the default route
  */
 extern fib_node_index_t fib_table_lookup(u32 fib_index,
 					 const fib_prefix_t *prefix);

 /**
  * @brief
  *  Perfom an exact match in the non-forwarding table
  *
  * @param fib_index
  *  The index of the FIB
  *
  * @param prefix
  *  The prefix to lookup
  *
  * @return
  *  The index of the fib_entry_t for the exact match, or INVALID
  *  is there is no match.
  */
 extern fib_node_index_t fib_table_lookup_exact_match(u32 fib_index,
 						     const fib_prefix_t *prefix);

 /**
  * @brief
  *  Get the less specific (covering) prefix
  *
  * @param fib_index
  *  The index of the FIB
  *
  * @param prefix
  *  The prefix to lookup
  *
  * @return
  *  The index of the less specific fib_entry_t.
  */
 extern fib_node_index_t fib_table_get_less_specific(u32 fib_index,
 						    const fib_prefix_t *prefix);

 /**
  * @brief
  *  Add a 'special' entry to the FIB.
  *  A special entry is an entry that the FIB is not expect to resolve
  *  via the usual mechanisms (i.e. recurisve or neighbour adj DB lookup).
  *  Instead the will link to a DPO valid for the source and/or the flags.
  *  This add is reference counting per-source. So n 'removes' are required
  *  for n 'adds', if the entry is no longer required.
  *  If the source needs to provide non-default forwarding use:
  *  fib_table_entry_special_dpo_add()
  *
  * @param fib_index
  *  The index of the FIB
  *
  * @param prefix
  *  The prefix to add
  *
  * @param source
  *  The ID of the client/source adding the entry.
  *
  * @param flags
  *  Flags for the entry.
  *
  * @return
  *  the index of the fib_entry_t that is created (or exists already).
  */
 extern fib_node_index_t fib_table_entry_special_add(u32 fib_index,
 						    const fib_prefix_t *prefix,
 						    fib_source_t source,
 						    fib_entry_flag_t flags);

 /**
  * @brief
  *  Add a 'special' entry to the FIB that links to the DPO passed
  *  A special entry is an entry that the FIB is not expect to resolve
  *  via the usual mechanisms (i.e. recurisve or neighbour adj DB lookup).
  *  Instead the client/source provides the DPO to link to.
  *  This add is reference counting per-source. So n 'removes' are required
  *  for n 'adds', if the entry is no longer required.
  *
   * @param fib_index
  *  The index of the FIB
  *
  * @param prefix
  *  The prefix to add
  *
  * @param source
  *  The ID of the client/source adding the entry.
  *
  * @param flags
  *  Flags for the entry.
  *
  * @param dpo
  *  The DPO to link to.
  *
  * @return
  *  the index of the fib_entry_t that is created (or existed already).
  */
 extern fib_node_index_t fib_table_entry_special_dpo_add(u32 fib_index,
                                                         const fib_prefix_t *prefix,
                                                         fib_source_t source,
                                                         fib_entry_flag_t stype,
                                                         const dpo_id_t *dpo);

 /**
  * @brief
  *  Update a 'special' entry to the FIB that links to the DPO passed
  *  A special entry is an entry that the FIB is not expect to resolve
  *  via the usual mechanisms (i.e. recurisve or neighbour adj DB lookup).
  *  Instead the client/source provides the DPO to link to.
  *  Special entries are add/remove reference counted per-source. So n
  * 'removes' are required for n 'adds', if the entry is no longer required.
  *  An 'update' is an 'add' if no 'add' has already been called, otherwise an 'add'
  * is therefore assumed to act on the reference instance of that add.
  *
  * @param fib_entry_index
  *  The index of the FIB entry to update
  *
  * @param source
  *  The ID of the client/source adding the entry.
  *
  * @param flags
  *  Flags for the entry.
  *
  * @param dpo
  *  The DPO to link to.
  *
  * @return
  *  the index of the fib_entry_t that is created (or existed already).
  */
 extern fib_node_index_t fib_table_entry_special_dpo_update (u32 fib_index,
 							    const fib_prefix_t *prefix,
 							    fib_source_t source,
 							    fib_entry_flag_t stype,
 							    const dpo_id_t *dpo);

 /**
  * @brief
  *  Remove a 'special' entry from the FIB.
  *  This add is reference counting per-source. So n 'removes' are required
  *  for n 'adds', if the entry is no longer required.
  *
  * @param fib_index
  *  The index of the FIB
  *
  * @param prefix
  *  The prefix to remove
  *
  * @param source
  *  The ID of the client/source adding the entry.
  *
  */
 extern void fib_table_entry_special_remove(u32 fib_index,
 					   const fib_prefix_t *prefix,
 					   fib_source_t source);

 /**
  * @brief
  *  Add one path to an entry (aka route) in the FIB. If the entry does not
  *  exist, it will be created.
  * See the documentation for fib_route_path_t for more descirptions of
  * the path parameters.
  *
  * @param fib_index
  *  The index of the FIB
  *
  * @param prefix
  *  The prefix for the entry to add
  *
  * @param source
  *  The ID of the client/source adding the entry.
  *
  * @param flags
  *  Flags for the entry.
  *
  * @paran next_hop_proto
  *  The protocol of the next hop. This cannot be derived in the event that
  * the next hop is all zeros.
  *
  * @param next_hop
  *  The address of the next-hop.
  *
  * @param sw_if_index
  *  The index of the interface.
  *
  * @param next_hop_fib_index,
  *  The fib index of the next-hop for recursive resolution
  *
  * @param next_hop_weight
  *  [un]equal cost path weight
  *
  * @param  next_hop_label_stack
  *  The path's out-going label stack. NULL is there is none.
  *
  * @param  pf
  *  Flags for the path
  *
  * @return
  *  the index of the fib_entry_t that is created (or existed already).
  */
 extern fib_node_index_t fib_table_entry_path_add(u32 fib_index,
 						 const fib_prefix_t *prefix,
 						 fib_source_t source,
 						 fib_entry_flag_t flags,
 						 dpo_proto_t next_hop_proto,
 						 const ip46_address_t *next_hop,
 						 u32 next_hop_sw_if_index,
 						 u32 next_hop_fib_index,
 						 u32 next_hop_weight,
 						 mpls_label_t *next_hop_label_stack,
 						 fib_route_path_flags_t pf);
 /**
  * @brief
  *  Add n paths to an entry (aka route) in the FIB. If the entry does not
  *  exist, it will be created.
  * See the documentation for fib_route_path_t for more descirptions of
  * the path parameters.
  *
  * @param fib_index
  *  The index of the FIB
  *
  * @param prefix
  *  The prefix for the entry to add
  *
  * @param source
  *  The ID of the client/source adding the entry.
  *
  * @param flags
  *  Flags for the entry.
  *
  * @param rpaths
  *  A vector of paths. Not const since they may be modified.
  *
  * @return
  *  the index of the fib_entry_t that is created (or existed already).
  */
 extern fib_node_index_t fib_table_entry_path_add2(u32 fib_index,
 						  const fib_prefix_t *prefix,
 						  fib_source_t source,
 						  fib_entry_flag_t flags,
 						  fib_route_path_t *rpath);

 /**
  * @brief
  * remove one path to an entry (aka route) in the FIB. If this is the entry's
  * last path, then the entry will be removed, unless it has other sources.
  * See the documentation for fib_route_path_t for more descirptions of
  * the path parameters.
  *
  * @param fib_index
  *  The index of the FIB
  *
  * @param prefix
  *  The prefix for the entry to add
  *
  * @param source
  *  The ID of the client/source adding the entry.
  *
  * @paran next_hop_proto
  *  The protocol of the next hop. This cannot be derived in the event that
  * the next hop is all zeros.
  *
  * @param next_hop
  *  The address of the next-hop.
  *
  * @param sw_if_index
  *  The index of the interface.
  *
  * @param next_hop_fib_index,
  *  The fib index of the next-hop for recursive resolution
  *
  * @param next_hop_weight
  *  [un]equal cost path weight
  *
  * @param  pf
  *  Flags for the path
  */
 extern void fib_table_entry_path_remove(u32 fib_index,
 					const fib_prefix_t *prefix,
 					fib_source_t source,
 					dpo_proto_t next_hop_proto,
 					const ip46_address_t *next_hop,
 					u32 next_hop_sw_if_index,
 					u32 next_hop_fib_index,
 					u32 next_hop_weight,
 					fib_route_path_flags_t pf);

 /**
  * @brief
  * Remove n paths to an entry (aka route) in the FIB. If this is the entry's
  * last path, then the entry will be removed, unless it has other sources.
  * See the documentation for fib_route_path_t for more descirptions of
  * the path parameters.
  *
  * @param fib_index
  *  The index of the FIB
  *
  * @param prefix
  *  The prefix for the entry to add
  *
  * @param source
  *  The ID of the client/source adding the entry.
  *
  * @param rpaths
  *  A vector of paths.
  */
 extern void fib_table_entry_path_remove2(u32 fib_index,
 					 const fib_prefix_t *prefix,
 					 fib_source_t source,
 					 fib_route_path_t *paths);

 /**
  * @brief
  *  Update an entry to have a new set of paths. If the entry does not
  *  exist, it will be created.
  * The difference between an 'path-add' and an update, is that path-add is
  * an incremental addition of paths, whereas an update is a wholesale swap.
  *
  * @param fib_index
  *  The index of the FIB
  *
  * @param prefix
  *  The prefix for the entry to add
  *
  * @param source
  *  The ID of the client/source adding the entry.
  *
  * @param rpaths
  *  A vector of paths. Not const since they may be modified.
  *
  * @return
  *  the index of the fib_entry_t that is created (or existed already).
  */
 extern fib_node_index_t fib_table_entry_update(u32 fib_index,
 					       const fib_prefix_t *prefix,
 					       fib_source_t source,
 					       fib_entry_flag_t flags,
 					       fib_route_path_t *paths);

 /**
  * @brief
  *  Update the entry to have just one path. If the entry does not
  *  exist, it will be created.
  * See the documentation for fib_route_path_t for more descirptions of
  * the path parameters.
  *
  * @param fib_index
  *  The index of the FIB
  *
  * @param prefix
  *  The prefix for the entry to add
  *
  * @param source
  *  The ID of the client/source adding the entry.
  *
  * @param flags
  *  Flags for the entry.
  *
  * @paran next_hop_proto
  *  The protocol of the next hop. This cannot be derived in the event that
  * the next hop is all zeros.
  *
  * @param next_hop
  *  The address of the next-hop.
  *
  * @param sw_if_index
  *  The index of the interface.
  *
  * @param next_hop_fib_index,
  *  The fib index of the next-hop for recursive resolution
  *
  * @param next_hop_weight
  *  [un]equal cost path weight
  *
  * @param  next_hop_label_stack
  *  The path's out-going label stack. NULL is there is none.
  *
  * @param  pf
  *  Flags for the path
  *
  * @return
  *  the index of the fib_entry_t that is created (or existed already).
  */
 extern fib_node_index_t fib_table_entry_update_one_path(u32 fib_index,
 							const fib_prefix_t *prefix,
 							fib_source_t source,
 							fib_entry_flag_t flags,
 							dpo_proto_t next_hop_proto,
 							const ip46_address_t *next_hop,
 							u32 next_hop_sw_if_index,
 							u32 next_hop_fib_index,
 							u32 next_hop_weight,
 							mpls_label_t *next_hop_label_stack,
 							fib_route_path_flags_t pf);

 /**
  * @brief
  *  Add a MPLS local label for the prefix/route. If the entry does not
  *  exist, it will be created. In theory more than one local label can be
  *  added, but this is not yet supported.
  *
  * @param fib_index
  *  The index of the FIB
  *
  * @param prefix
  *  The prefix for the entry to which to add the label
  *
  * @param label
  *  The MPLS label to add
  *
  * @return
  *  the index of the fib_entry_t that is created (or existed already).
  */
 extern fib_node_index_t fib_table_entry_local_label_add(u32 fib_index,
 							const fib_prefix_t *prefix,
 							mpls_label_t label);
 /**
  * @brief
  *  remove a MPLS local label for the prefix/route.
  *
  * @param fib_index
  *  The index of the FIB
  *
  * @param prefix
  *  The prefix for the entry to which to add the label
  *
  * @param label
  *  The MPLS label to add
  */
 extern void fib_table_entry_local_label_remove(u32 fib_index,
 					       const fib_prefix_t *prefix,
 					       mpls_label_t label);

 /**
  * @brief
  *  Delete a FIB entry. If the entry has no more sources, then it is
  * removed from the table.
  *
  * @param fib_index
  *  The index of the FIB
  *
  * @param prefix
  *  The prefix for the entry to remove
  *
  * @param source
  *  The ID of the client/source adding the entry.
  */
 extern void fib_table_entry_delete(u32 fib_index,
 				   const fib_prefix_t *prefix,
 				   fib_source_t source);

 /**
  * @brief
  *  Delete a FIB entry. If the entry has no more sources, then it is
  * removed from the table.
  *
  * @param entry_index
  *  The index of the FIB entry
  *
  * @param source
  *  The ID of the client/source adding the entry.
  */
 extern void fib_table_entry_delete_index(fib_node_index_t entry_index,
 					 fib_source_t source);

 /**
  * @brief
  *  Flush all entries from a table for the source
  *
  * @param fib_index
  *  The index of the FIB
  *
  * @paran proto
  *  The protocol of the entries in the table
  *
  * @param source
  *  the source to flush
  */
 extern void fib_table_flush(u32 fib_index,
 			    fib_protocol_t proto,
 			    fib_source_t source);

 /**
  * @brief
  *  Get the index of the FIB bound to the interface
  *
  * @paran proto
  *  The protocol of the FIB (and thus the entries therein)
  *
  * @param sw_if_index
  *  The interface index
  *
  * @return fib_index
  *  The index of the FIB
  */
 extern u32 fib_table_get_index_for_sw_if_index(fib_protocol_t proto,
 					       u32 sw_if_index);

 /**
  * @brief
  *  Get the Table-ID of the FIB bound to the interface
  *
  * @paran proto
  *  The protocol of the FIB (and thus the entries therein)
  *
  * @param sw_if_index
  *  The interface index
  *
  * @return fib_index
  *  The tableID of the FIB
  */
 extern u32 fib_table_get_table_id_for_sw_if_index(fib_protocol_t proto,
 						  u32 sw_if_index);

 /**
  * @brief
  *  Get the index of the FIB for a Table-ID. This DOES NOT create the
  * FIB if it does not exist.
  *
  * @paran proto
  *  The protocol of the FIB (and thus the entries therein)
  *
  * @param table-id
  *  The Table-ID
  *
  * @return fib_index
  *  The index of the FIB, which may be INVALID.
  */
 extern u32 fib_table_find(fib_protocol_t proto, u32 table_id);


 /**
  * @brief
  *  Get the index of the FIB for a Table-ID. This DOES create the
  * FIB if it does not exist.
  *
  * @paran proto
  *  The protocol of the FIB (and thus the entries therein)
  *
  * @param table-id
  *  The Table-ID
  *
  * @return fib_index
  *  The index of the FIB
  *
  * @param source
  *  The ID of the client/source.
  */
 extern u32 fib_table_find_or_create_and_lock(fib_protocol_t proto,
 					     u32 table_id,
                                              fib_source_t source);

 /**
  * @brief
  *  Get the index of the FIB for a Table-ID. This DOES create the
  * FIB if it does not exist.
  *
  * @paran proto
  *  The protocol of the FIB (and thus the entries therein)
  *
  * @param table-id
  *  The Table-ID
  *
  * @return fib_index
  *  The index of the FIB
  *
  * @param source
  *  The ID of the client/source.
  *
  * @param name
  *  The client is choosing the name they want the table to have
  */
 extern u32 fib_table_find_or_create_and_lock_w_name(fib_protocol_t proto,
                                                     u32 table_id,
                                                     fib_source_t source,
                                                     const u8 *name);

 /**
  * @brief
  *  Create a new table with no table ID. This means it does not get
  * added to the hash-table and so can only be found by using the index returned.
  *
  * @paran proto
  *  The protocol of the FIB (and thus the entries therein)
  *
  * @param fmt
  *  A string to describe the table
  *
  * @param source
  *  The ID of the client/source.
  *
  * @return fib_index
  *  The index of the FIB
  */
 extern u32 fib_table_create_and_lock(fib_protocol_t proto,
                                      fib_source_t source,
                                      const char *const fmt,
                                      ...);

 /**
  * @brief
  *  Get the flow hash configured used by the table
  *
  * @param fib_index
  *  The index of the FIB
  *
  * @paran proto
  *  The protocol the packets the flow hash will be calculated for.
  *
  * @return The flow hash config
  */
 extern flow_hash_config_t fib_table_get_flow_hash_config(u32 fib_index,
 							 fib_protocol_t proto);

 /**
  * @brief
  *  Get the flow hash configured used by the protocol
  *
  * @paran proto
  *  The protocol of the FIB (and thus the entries therein)
  *
  * @return The flow hash config
  */
 extern flow_hash_config_t fib_table_get_default_flow_hash_config(fib_protocol_t proto);

 /**
  * @brief
  *  Set the flow hash configured used by the table
  *
  * @param fib_index
  *  The index of the FIB
  *
  * @paran proto
  *  The protocol of the FIB (and thus the entries therein)
  *
  * @param hash_config
  *  The flow-hash config to set
  *
  * @return none
  */
 extern void fib_table_set_flow_hash_config(u32 fib_index,
                                            fib_protocol_t proto,
                                            flow_hash_config_t hash_config);

 /**
  * @brief
  * Take a reference counting lock on the table
  *
  * @param fib_index
  *  The index of the FIB
  *
  * @paran proto
  *  The protocol of the FIB (and thus the entries therein)
  *
  * @param source
  *  The ID of the client/source.
  */
 extern void fib_table_unlock(u32 fib_index,
 			     fib_protocol_t proto,
                              fib_source_t source);

 /**
  * @brief
  * Release a reference counting lock on the table. When the last lock
  * has gone. the FIB is deleted.
  *
  * @param fib_index
  *  The index of the FIB
  *
  * @paran proto
  *  The protocol of the FIB (and thus the entries therein)
  *
  * @param source
  *  The ID of the client/source.
  */
 extern void fib_table_lock(u32 fib_index,
 			   fib_protocol_t proto,
                            fib_source_t source);

 /**
  * @brief
  * Return the number of entries in the FIB added by a given source.
  *
  * @param fib_index
  *  The index of the FIB
  *
  * @paran proto
  *  The protocol of the FIB (and thus the entries therein)
  *
  * @return number of sourced entries.
  */
 extern u32 fib_table_get_num_entries(u32 fib_index,
 				     fib_protocol_t proto,
 				     fib_source_t source);

 /**
  * @brief
  * Get a pointer to a FIB table
  */
 extern fib_table_t *fib_table_get(fib_node_index_t index,
 				  fib_protocol_t proto);

 /**
  * @brief return code controlling how a table walk proceeds
  */
 typedef enum fib_table_walk_rc_t_
 {
     /**
      * Continue on to the next entry
      */
     FIB_TABLE_WALK_CONTINUE,
     /**
      * Do no traverse down this sub-tree
      */
     FIB_TABLE_WALK_SUB_TREE_STOP,
     /**
      * Stop the walk completely
      */
     FIB_TABLE_WALK_STOP,
 } fib_table_walk_rc_t;

 /**
  * @brief Call back function when walking entries in a FIB table
  */
 typedef fib_table_walk_rc_t (*fib_table_walk_fn_t)(fib_node_index_t fei,
                                                    void *ctx);

 /**
  * @brief Walk all entries in a FIB table
  * N.B: This is NOT safe to deletes. If you need to delete walk the whole
  * table and store elements in a vector, then delete the elements
  */
 extern void fib_table_walk(u32 fib_index,
                            fib_protocol_t proto,
                            fib_table_walk_fn_t fn,
                            void *ctx);

 /**
  * @brief Walk all entries in a sub-tree FIB table. The 'root' paraneter
  * is the prefix at the root of the sub-tree.
  * N.B: This is NOT safe to deletes. If you need to delete walk the whole
  * table and store elements in a vector, then delete the elements
  */
 extern void fib_table_sub_tree_walk(u32 fib_index,
                                     fib_protocol_t proto,
                                     const fib_prefix_t *root,
                                     fib_table_walk_fn_t fn,
                                     void *ctx);

 /**
  * @brief format (display) the memory used by the FIB tables
  */
 extern u8 *format_fib_table_memory(u8 *s, va_list *args);

 #endif
	/*
	* Copyright (c) 2016 Cisco and/or its affiliates.
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at:
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/

	#ifndef __FIB_TABLE_H__
	#define __FIB_TABLE_H__

	#include <vnet/ip/ip.h>
	#include <vnet/adj/adj.h>
	#include <vnet/fib/fib_entry.h>
	#include <vnet/mpls/mpls.h>
	#include <vnet/mpls/packet.h>

	/**
	* Keep a lock per-source and a total
	*/
	#define FIB_TABLE_N_LOCKS (FIB_SOURCE_MAX+1)
	#define FIB_TABLE_TOTAL_LOCKS FIB_SOURCE_MAX

	/**
	* Flags for the source data
	*/
	typedef enum fib_table_attribute_t_ {
	/**
	* Marker. Add new values after this one.
	*/
	FIB_TABLE_ATTRIBUTE_FIRST,
	/**
	* the table is for IP6 link local addresses
	*/
	FIB_TABLE_ATTRIBUTE_IP6_LL = FIB_TABLE_ATTRIBUTE_FIRST,
	/**
	* Marker. add new entries before this one.
	*/
	FIB_TABLE_ATTRIBUTE_LAST = FIB_TABLE_ATTRIBUTE_IP6_LL,
	} fib_table_attribute_t;

	#define FIB_TABLE_ATTRIBUTE_MAX (FIB_TABLE_ATTRIBUTE_LAST+1)

	#define FIB_TABLE_ATTRIBUTES { \
	[FIB_TABLE_ATTRIBUTE_IP6_LL] = "ip6-ll", \
	}

	#define FOR_EACH_FIB_TABLE_ATTRIBUTE(_item) \
	for (_item = FIB_TABLE_ATTRIBUTE_FIRST; \
	_item < FIB_TABLE_ATTRIBUTE_MAX; \
	_item++)

	typedef enum fib_table_flags_t_ {
	FIB_TABLE_FLAG_NONE = 0,
	FIB_TABLE_FLAG_IP6_LL = (1 << FIB_TABLE_ATTRIBUTE_IP6_LL),
	} __attribute__ ((packed)) fib_table_flags_t;

	/**
	* @brief
	* A protocol Independent FIB table
	*/
	typedef struct fib_table_t_
	{
	/**
	* Which protocol this table serves. Used to switch on the union above.
	*/
	fib_protocol_t ft_proto;

	/**
	* Table flags
	*/
	fib_table_flags_t ft_flags;

	/**
	* per-source number of locks on the table
	*/
	u16 ft_locks[FIB_TABLE_N_LOCKS];

	/**
	* Table ID (hash key) for this FIB.
	*/
	u32 ft_table_id;

	/**
	* Index into FIB vector.
	*/
	fib_node_index_t ft_index;

	/**
	* flow hash configuration
	*/
	u32 ft_flow_hash_config;

	/**
	* Per-source route counters
	*/
	u32 ft_src_route_counts[FIB_SOURCE_MAX];

	/**
	* Total route counters
	*/
	u32 ft_total_route_counts;

	/**
	* Table description
	*/
	u8* ft_desc;
	} fib_table_t;

	/**
	* @brief
	* Format the description/name of the table
	*/
	extern u8* format_fib_table_name(u8* s, va_list *ap);

	/**
	* @brief
	* Perfom a longest prefix match in the non-forwarding table
	*
	* @param fib_index
	* The index of the FIB
	*
	* @param prefix
	* The prefix to lookup
	*
	* @return
	* The index of the fib_entry_t for the best match, which may be the default route
	*/
	extern fib_node_index_t fib_table_lookup(u32 fib_index,
	const fib_prefix_t *prefix);

	/**
	* @brief
	* Perfom an exact match in the non-forwarding table
	*
	* @param fib_index
	* The index of the FIB
	*
	* @param prefix
	* The prefix to lookup
	*
	* @return
	* The index of the fib_entry_t for the exact match, or INVALID
	* is there is no match.
	*/
	extern fib_node_index_t fib_table_lookup_exact_match(u32 fib_index,
	const fib_prefix_t *prefix);

	/**
	* @brief
	* Get the less specific (covering) prefix
	*
	* @param fib_index
	* The index of the FIB
	*
	* @param prefix
	* The prefix to lookup
	*
	* @return
	* The index of the less specific fib_entry_t.
	*/
	extern fib_node_index_t fib_table_get_less_specific(u32 fib_index,
	const fib_prefix_t *prefix);

	/**
	* @brief
	* Add a 'special' entry to the FIB.
	* A special entry is an entry that the FIB is not expect to resolve
	* via the usual mechanisms (i.e. recurisve or neighbour adj DB lookup).
	* Instead the will link to a DPO valid for the source and/or the flags.
	* This add is reference counting per-source. So n 'removes' are required
	* for n 'adds', if the entry is no longer required.
	* If the source needs to provide non-default forwarding use:
	* fib_table_entry_special_dpo_add()
	*
	* @param fib_index
	* The index of the FIB
	*
	* @param prefix
	* The prefix to add
	*
	* @param source
	* The ID of the client/source adding the entry.
	*
	* @param flags
	* Flags for the entry.
	*
	* @return
	* the index of the fib_entry_t that is created (or exists already).
	*/
	extern fib_node_index_t fib_table_entry_special_add(u32 fib_index,
	const fib_prefix_t *prefix,
	fib_source_t source,
	fib_entry_flag_t flags);

	/**
	* @brief
	* Add a 'special' entry to the FIB that links to the DPO passed
	* A special entry is an entry that the FIB is not expect to resolve
	* via the usual mechanisms (i.e. recurisve or neighbour adj DB lookup).
	* Instead the client/source provides the DPO to link to.
	* This add is reference counting per-source. So n 'removes' are required
	* for n 'adds', if the entry is no longer required.
	*
	* @param fib_index
	* The index of the FIB
	*
	* @param prefix
	* The prefix to add
	*
	* @param source
	* The ID of the client/source adding the entry.
	*
	* @param flags
	* Flags for the entry.
	*
	* @param dpo
	* The DPO to link to.
	*
	* @return
	* the index of the fib_entry_t that is created (or existed already).
	*/
	extern fib_node_index_t fib_table_entry_special_dpo_add(u32 fib_index,
	const fib_prefix_t *prefix,
	fib_source_t source,
	fib_entry_flag_t stype,
	const dpo_id_t *dpo);

	/**
	* @brief
	* Update a 'special' entry to the FIB that links to the DPO passed
	* A special entry is an entry that the FIB is not expect to resolve
	* via the usual mechanisms (i.e. recurisve or neighbour adj DB lookup).
	* Instead the client/source provides the DPO to link to.
	* Special entries are add/remove reference counted per-source. So n
	* 'removes' are required for n 'adds', if the entry is no longer required.
	* An 'update' is an 'add' if no 'add' has already been called, otherwise an 'add'
	* is therefore assumed to act on the reference instance of that add.
	*
	* @param fib_entry_index
	* The index of the FIB entry to update
	*
	* @param source
	* The ID of the client/source adding the entry.
	*
	* @param flags
	* Flags for the entry.
	*
	* @param dpo
	* The DPO to link to.
	*
	* @return
	* the index of the fib_entry_t that is created (or existed already).
	*/
	extern fib_node_index_t fib_table_entry_special_dpo_update (u32 fib_index,
	const fib_prefix_t *prefix,
	fib_source_t source,
	fib_entry_flag_t stype,
	const dpo_id_t *dpo);

	/**
	* @brief
	* Remove a 'special' entry from the FIB.
	* This add is reference counting per-source. So n 'removes' are required
	* for n 'adds', if the entry is no longer required.
	*
	* @param fib_index
	* The index of the FIB
	*
	* @param prefix
	* The prefix to remove
	*
	* @param source
	* The ID of the client/source adding the entry.
	*
	*/
	extern void fib_table_entry_special_remove(u32 fib_index,
	const fib_prefix_t *prefix,
	fib_source_t source);

	/**
	* @brief
	* Add one path to an entry (aka route) in the FIB. If the entry does not
	* exist, it will be created.
	* See the documentation for fib_route_path_t for more descirptions of
	* the path parameters.
	*
	* @param fib_index
	* The index of the FIB
	*
	* @param prefix
	* The prefix for the entry to add
	*
	* @param source
	* The ID of the client/source adding the entry.
	*
	* @param flags
	* Flags for the entry.
	*
	* @paran next_hop_proto
	* The protocol of the next hop. This cannot be derived in the event that
	* the next hop is all zeros.
	*
	* @param next_hop
	* The address of the next-hop.
	*
	* @param sw_if_index
	* The index of the interface.
	*
	* @param next_hop_fib_index,
	* The fib index of the next-hop for recursive resolution
	*
	* @param next_hop_weight
	* [un]equal cost path weight
	*
	* @param next_hop_label_stack
	* The path's out-going label stack. NULL is there is none.
	*
	* @param pf
	* Flags for the path
	*
	* @return
	* the index of the fib_entry_t that is created (or existed already).
	*/
	extern fib_node_index_t fib_table_entry_path_add(u32 fib_index,
	const fib_prefix_t *prefix,
	fib_source_t source,
	fib_entry_flag_t flags,
	dpo_proto_t next_hop_proto,
	const ip46_address_t *next_hop,
	u32 next_hop_sw_if_index,
	u32 next_hop_fib_index,
	u32 next_hop_weight,
	mpls_label_t *next_hop_label_stack,
	fib_route_path_flags_t pf);
	/**
	* @brief
	* Add n paths to an entry (aka route) in the FIB. If the entry does not
	* exist, it will be created.
	* See the documentation for fib_route_path_t for more descirptions of
	* the path parameters.
	*
	* @param fib_index
	* The index of the FIB
	*
	* @param prefix
	* The prefix for the entry to add
	*
	* @param source
	* The ID of the client/source adding the entry.
	*
	* @param flags
	* Flags for the entry.
	*
	* @param rpaths
	* A vector of paths. Not const since they may be modified.
	*
	* @return
	* the index of the fib_entry_t that is created (or existed already).
	*/
	extern fib_node_index_t fib_table_entry_path_add2(u32 fib_index,
	const fib_prefix_t *prefix,
	fib_source_t source,
	fib_entry_flag_t flags,
	fib_route_path_t *rpath);

	/**
	* @brief
	* remove one path to an entry (aka route) in the FIB. If this is the entry's
	* last path, then the entry will be removed, unless it has other sources.
	* See the documentation for fib_route_path_t for more descirptions of
	* the path parameters.
	*
	* @param fib_index
	* The index of the FIB
	*
	* @param prefix
	* The prefix for the entry to add
	*
	* @param source
	* The ID of the client/source adding the entry.
	*
	* @paran next_hop_proto
	* The protocol of the next hop. This cannot be derived in the event that
	* the next hop is all zeros.
	*
	* @param next_hop
	* The address of the next-hop.
	*
	* @param sw_if_index
	* The index of the interface.
	*
	* @param next_hop_fib_index,
	* The fib index of the next-hop for recursive resolution
	*
	* @param next_hop_weight
	* [un]equal cost path weight
	*
	* @param pf
	* Flags for the path
	*/
	extern void fib_table_entry_path_remove(u32 fib_index,
	const fib_prefix_t *prefix,
	fib_source_t source,
	dpo_proto_t next_hop_proto,
	const ip46_address_t *next_hop,
	u32 next_hop_sw_if_index,
	u32 next_hop_fib_index,
	u32 next_hop_weight,
	fib_route_path_flags_t pf);

	/**
	* @brief
	* Remove n paths to an entry (aka route) in the FIB. If this is the entry's
	* last path, then the entry will be removed, unless it has other sources.
	* See the documentation for fib_route_path_t for more descirptions of
	* the path parameters.
	*
	* @param fib_index
	* The index of the FIB
	*
	* @param prefix
	* The prefix for the entry to add
	*
	* @param source
	* The ID of the client/source adding the entry.
	*
	* @param rpaths
	* A vector of paths.
	*/
	extern void fib_table_entry_path_remove2(u32 fib_index,
	const fib_prefix_t *prefix,
	fib_source_t source,
	fib_route_path_t *paths);

	/**
	* @brief
	* Update an entry to have a new set of paths. If the entry does not
	* exist, it will be created.
	* The difference between an 'path-add' and an update, is that path-add is
	* an incremental addition of paths, whereas an update is a wholesale swap.
	*
	* @param fib_index
	* The index of the FIB
	*
	* @param prefix
	* The prefix for the entry to add
	*
	* @param source
	* The ID of the client/source adding the entry.
	*
	* @param rpaths
	* A vector of paths. Not const since they may be modified.
	*
	* @return
	* the index of the fib_entry_t that is created (or existed already).
	*/
	extern fib_node_index_t fib_table_entry_update(u32 fib_index,
	const fib_prefix_t *prefix,
	fib_source_t source,
	fib_entry_flag_t flags,
	fib_route_path_t *paths);

	/**
	* @brief
	* Update the entry to have just one path. If the entry does not
	* exist, it will be created.
	* See the documentation for fib_route_path_t for more descirptions of
	* the path parameters.
	*
	* @param fib_index
	* The index of the FIB
	*
	* @param prefix
	* The prefix for the entry to add
	*
	* @param source
	* The ID of the client/source adding the entry.
	*
	* @param flags
	* Flags for the entry.
	*
	* @paran next_hop_proto
	* The protocol of the next hop. This cannot be derived in the event that
	* the next hop is all zeros.
	*
	* @param next_hop
	* The address of the next-hop.
	*
	* @param sw_if_index
	* The index of the interface.
	*
	* @param next_hop_fib_index,
	* The fib index of the next-hop for recursive resolution
	*
	* @param next_hop_weight
	* [un]equal cost path weight
	*
	* @param next_hop_label_stack
	* The path's out-going label stack. NULL is there is none.
	*
	* @param pf
	* Flags for the path
	*
	* @return
	* the index of the fib_entry_t that is created (or existed already).
	*/
	extern fib_node_index_t fib_table_entry_update_one_path(u32 fib_index,
	const fib_prefix_t *prefix,
	fib_source_t source,
	fib_entry_flag_t flags,
	dpo_proto_t next_hop_proto,
	const ip46_address_t *next_hop,
	u32 next_hop_sw_if_index,
	u32 next_hop_fib_index,
	u32 next_hop_weight,
	mpls_label_t *next_hop_label_stack,
	fib_route_path_flags_t pf);

	/**
	* @brief
	* Add a MPLS local label for the prefix/route. If the entry does not
	* exist, it will be created. In theory more than one local label can be
	* added, but this is not yet supported.
	*
	* @param fib_index
	* The index of the FIB
	*
	* @param prefix
	* The prefix for the entry to which to add the label
	*
	* @param label
	* The MPLS label to add
	*
	* @return
	* the index of the fib_entry_t that is created (or existed already).
	*/
	extern fib_node_index_t fib_table_entry_local_label_add(u32 fib_index,
	const fib_prefix_t *prefix,
	mpls_label_t label);
	/**
	* @brief
	* remove a MPLS local label for the prefix/route.
	*
	* @param fib_index
	* The index of the FIB
	*
	* @param prefix
	* The prefix for the entry to which to add the label
	*
	* @param label
	* The MPLS label to add
	*/
	extern void fib_table_entry_local_label_remove(u32 fib_index,
	const fib_prefix_t *prefix,
	mpls_label_t label);

	/**
	* @brief
	* Delete a FIB entry. If the entry has no more sources, then it is
	* removed from the table.
	*
	* @param fib_index
	* The index of the FIB
	*
	* @param prefix
	* The prefix for the entry to remove
	*
	* @param source
	* The ID of the client/source adding the entry.
	*/
	extern void fib_table_entry_delete(u32 fib_index,
	const fib_prefix_t *prefix,
	fib_source_t source);

	/**
	* @brief
	* Delete a FIB entry. If the entry has no more sources, then it is
	* removed from the table.
	*
	* @param entry_index
	* The index of the FIB entry
	*
	* @param source
	* The ID of the client/source adding the entry.
	*/
	extern void fib_table_entry_delete_index(fib_node_index_t entry_index,
	fib_source_t source);

	/**
	* @brief
	* Flush all entries from a table for the source
	*
	* @param fib_index
	* The index of the FIB
	*
	* @paran proto
	* The protocol of the entries in the table
	*
	* @param source
	* the source to flush
	*/
	extern void fib_table_flush(u32 fib_index,
	fib_protocol_t proto,
	fib_source_t source);

	/**
	* @brief
	* Get the index of the FIB bound to the interface
	*
	* @paran proto
	* The protocol of the FIB (and thus the entries therein)
	*
	* @param sw_if_index
	* The interface index
	*
	* @return fib_index
	* The index of the FIB
	*/
	extern u32 fib_table_get_index_for_sw_if_index(fib_protocol_t proto,
	u32 sw_if_index);

	/**
	* @brief
	* Get the Table-ID of the FIB bound to the interface
	*
	* @paran proto
	* The protocol of the FIB (and thus the entries therein)
	*
	* @param sw_if_index
	* The interface index
	*
	* @return fib_index
	* The tableID of the FIB
	*/
	extern u32 fib_table_get_table_id_for_sw_if_index(fib_protocol_t proto,
	u32 sw_if_index);

	/**
	* @brief
	* Get the index of the FIB for a Table-ID. This DOES NOT create the
	* FIB if it does not exist.
	*
	* @paran proto
	* The protocol of the FIB (and thus the entries therein)
	*
	* @param table-id
	* The Table-ID
	*
	* @return fib_index
	* The index of the FIB, which may be INVALID.
	*/
	extern u32 fib_table_find(fib_protocol_t proto, u32 table_id);


	/**
	* @brief
	* Get the index of the FIB for a Table-ID. This DOES create the
	* FIB if it does not exist.
	*
	* @paran proto
	* The protocol of the FIB (and thus the entries therein)
	*
	* @param table-id
	* The Table-ID
	*
	* @return fib_index
	* The index of the FIB
	*
	* @param source
	* The ID of the client/source.
	*/
	extern u32 fib_table_find_or_create_and_lock(fib_protocol_t proto,
	u32 table_id,
	fib_source_t source);

	/**
	* @brief
	* Get the index of the FIB for a Table-ID. This DOES create the
	* FIB if it does not exist.
	*
	* @paran proto
	* The protocol of the FIB (and thus the entries therein)
	*
	* @param table-id
	* The Table-ID
	*
	* @return fib_index
	* The index of the FIB
	*
	* @param source
	* The ID of the client/source.
	*
	* @param name
	* The client is choosing the name they want the table to have
	*/
	extern u32 fib_table_find_or_create_and_lock_w_name(fib_protocol_t proto,
	u32 table_id,
	fib_source_t source,
	const u8 *name);

	/**
	* @brief
	* Create a new table with no table ID. This means it does not get
	* added to the hash-table and so can only be found by using the index returned.
	*
	* @paran proto
	* The protocol of the FIB (and thus the entries therein)
	*
	* @param fmt
	* A string to describe the table
	*
	* @param source
	* The ID of the client/source.
	*
	* @return fib_index
	* The index of the FIB
	*/
	extern u32 fib_table_create_and_lock(fib_protocol_t proto,
	fib_source_t source,
	const char *const fmt,
	...);

	/**
	* @brief
	* Get the flow hash configured used by the table
	*
	* @param fib_index
	* The index of the FIB
	*
	* @paran proto
	* The protocol the packets the flow hash will be calculated for.
	*
	* @return The flow hash config
	*/
	extern flow_hash_config_t fib_table_get_flow_hash_config(u32 fib_index,
	fib_protocol_t proto);

	/**
	* @brief
	* Get the flow hash configured used by the protocol
	*
	* @paran proto
	* The protocol of the FIB (and thus the entries therein)
	*
	* @return The flow hash config
	*/
	extern flow_hash_config_t fib_table_get_default_flow_hash_config(fib_protocol_t proto);

	/**
	* @brief
	* Set the flow hash configured used by the table
	*
	* @param fib_index
	* The index of the FIB
	*
	* @paran proto
	* The protocol of the FIB (and thus the entries therein)
	*
	* @param hash_config
	* The flow-hash config to set
	*
	* @return none
	*/
	extern void fib_table_set_flow_hash_config(u32 fib_index,
	fib_protocol_t proto,
	flow_hash_config_t hash_config);

	/**
	* @brief
	* Take a reference counting lock on the table
	*
	* @param fib_index
	* The index of the FIB
	*
	* @paran proto
	* The protocol of the FIB (and thus the entries therein)
	*
	* @param source
	* The ID of the client/source.
	*/
	extern void fib_table_unlock(u32 fib_index,
	fib_protocol_t proto,
	fib_source_t source);

	/**
	* @brief
	* Release a reference counting lock on the table. When the last lock
	* has gone. the FIB is deleted.
	*
	* @param fib_index
	* The index of the FIB
	*
	* @paran proto
	* The protocol of the FIB (and thus the entries therein)
	*
	* @param source
	* The ID of the client/source.
	*/
	extern void fib_table_lock(u32 fib_index,
	fib_protocol_t proto,
	fib_source_t source);

	/**
	* @brief
	* Return the number of entries in the FIB added by a given source.
	*
	* @param fib_index
	* The index of the FIB
	*
	* @paran proto
	* The protocol of the FIB (and thus the entries therein)
	*
	* @return number of sourced entries.
	*/
	extern u32 fib_table_get_num_entries(u32 fib_index,
	fib_protocol_t proto,
	fib_source_t source);

	/**
	* @brief
	* Get a pointer to a FIB table
	*/
	extern fib_table_t *fib_table_get(fib_node_index_t index,
	fib_protocol_t proto);

	/**
	* @brief return code controlling how a table walk proceeds
	*/
	typedef enum fib_table_walk_rc_t_
	{
	/**
	* Continue on to the next entry
	*/
	FIB_TABLE_WALK_CONTINUE,
	/**
	* Do no traverse down this sub-tree
	*/
	FIB_TABLE_WALK_SUB_TREE_STOP,
	/**
	* Stop the walk completely
	*/
	FIB_TABLE_WALK_STOP,
	} fib_table_walk_rc_t;

	/**
	* @brief Call back function when walking entries in a FIB table
	*/
	typedef fib_table_walk_rc_t (*fib_table_walk_fn_t)(fib_node_index_t fei,
	void *ctx);

	/**
	* @brief Walk all entries in a FIB table
	* N.B: This is NOT safe to deletes. If you need to delete walk the whole
	* table and store elements in a vector, then delete the elements
	*/
	extern void fib_table_walk(u32 fib_index,
	fib_protocol_t proto,
	fib_table_walk_fn_t fn,
	void *ctx);

	/**
	* @brief Walk all entries in a sub-tree FIB table. The 'root' paraneter
	* is the prefix at the root of the sub-tree.
	* N.B: This is NOT safe to deletes. If you need to delete walk the whole
	* table and store elements in a vector, then delete the elements
	*/
	extern void fib_table_sub_tree_walk(u32 fib_index,
	fib_protocol_t proto,
	const fib_prefix_t *root,
	fib_table_walk_fn_t fn,
	void *ctx);

	/**
	* @brief format (display) the memory used by the FIB tables
	*/
	extern u8 format_fib_table_memory(u8 s, va_list *args);

	#endif