FD.io VPP  v20.05.1-6-gf53edbc3b
Vector Packet Processing
ip4_fib.h
Go to the documentation of this file.
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  * @brief The IPv4 FIB
17  *
18  * FIBs are composed of two prefix data-bases (akak tables). The non-forwarding
19  * table contains all the routes that the control plane has programmed, the
20  * forwarding table contains the sub-set of those routes that can be used to
21  * forward packets.
22  * In the IPv4 FIB the non-forwarding table is an array of hash tables indexed
23  * by mask length, the forwarding table is an mtrie
24  *
25  * This IPv4 FIB is used by the protocol independent FIB. So directly using
26  * this APIs in client code is not encouraged. However, this IPv4 FIB can be
27  * used if all the client wants is an IPv4 prefix data-base
28  */
29 
30 #ifndef __IP4_FIB_H__
31 #define __IP4_FIB_H__
32 
33 #include <vlib/vlib.h>
34 #include <vnet/ip/ip.h>
35 #include <vnet/fib/fib_entry.h>
36 #include <vnet/fib/fib_table.h>
37 #include <vnet/ip/ip4_mtrie.h>
38 
39 typedef struct ip4_fib_t_
40 {
41  /** Required for pool_get_aligned */
42  CLIB_CACHE_LINE_ALIGN_MARK(cacheline0);
43 
44  /**
45  * Mtrie for fast lookups. Hash is used to maintain overlapping prefixes.
46  * First member so it's in the first cacheline.
47  */
49 
50  /* Hash table for each prefix length mapping. */
52 
53  /* Table ID (hash key) for this FIB. */
55 
56  /* Index into FIB vector. */
58 } ip4_fib_t;
59 
61  const ip4_address_t *addr,
62  u32 len);
64  const ip4_address_t *addr,
65  u32 len);
66 
67 extern void ip4_fib_table_entry_remove(ip4_fib_t *fib,
68  const ip4_address_t *addr,
69  u32 len);
70 
71 extern void ip4_fib_table_entry_insert(ip4_fib_t *fib,
72  const ip4_address_t *addr,
73  u32 len,
74  fib_node_index_t fib_entry_index);
75 extern void ip4_fib_table_destroy(u32 fib_index);
76 
78  const ip4_address_t *addr,
79  u32 len,
80  const dpo_id_t *dpo);
81 
83  const ip4_address_t *addr,
84  u32 len,
85  const dpo_id_t *dpo,
86  fib_node_index_t cover_index);
88  const ip4_address_t * dst);
89 
90 /**
91  * @brief Walk all entries in a FIB table
92  * N.B: This is NOT safe to deletes. If you need to delete walk the whole
93  * table and store elements in a vector, then delete the elements
94  */
95 extern void ip4_fib_table_walk(ip4_fib_t *fib,
97  void *ctx);
98 
99 /**
100  * @brief Walk all entries in a sub-tree of the FIB table
101  * N.B: This is NOT safe to deletes. If you need to delete walk the whole
102  * table and store elements in a vector, then delete the elements
103  */
104 extern void ip4_fib_table_sub_tree_walk(ip4_fib_t *fib,
105  const fib_prefix_t *root,
107  void *ctx);
108 
109 /**
110  * @brief Get the FIB at the given index
111  */
112 static inline ip4_fib_t *
114 {
115  return (pool_elt_at_index(ip4_main.v4_fibs, index));
116 }
117 
120 {
121  return (ip4_fib_table_lookup_lb(
122  ip4_fib_get(vec_elt (im->fib_index_by_sw_if_index, sw_if_index)),
123  dst));
124 }
125 
126 /**
127  * @brief Get or create an IPv4 fib.
128  *
129  * Get or create an IPv4 fib with the provided table ID.
130  *
131  * @param table_id
132  * When set to \c ~0, an arbitrary and unused fib ID is picked
133  * and can be retrieved with \c ret->table_id.
134  * Otherwise, the fib ID to be used to retrieve or create the desired fib.
135  * @returns A pointer to the retrieved or created fib.
136  *
137  */
139  fib_source_t src);
141 
142 extern u8 *format_ip4_fib_table_memory(u8 * s, va_list * args);
143 
144 static inline
146 {
147  ip4_main_t * im = &ip4_main;
148  uword * p;
149 
150  p = hash_get (im->fib_index_by_table_id, table_id);
151  if (!p)
152  return ~0;
153 
154  return p[0];
155 }
156 
158 
161  const ip4_address_t * addr)
162 {
165 
166  mtrie = &ip4_fib_get(fib_index)->mtrie;
167 
168  leaf = ip4_fib_mtrie_lookup_step_one (mtrie, addr);
169  leaf = ip4_fib_mtrie_lookup_step (mtrie, leaf, addr, 2);
170  leaf = ip4_fib_mtrie_lookup_step (mtrie, leaf, addr, 3);
171 
172  return (ip4_fib_mtrie_leaf_get_adj_index(leaf));
173 }
174 
177  u32 fib_index1,
178  const ip4_address_t * addr0,
179  const ip4_address_t * addr1,
180  index_t *lb0,
181  index_t *lb1)
182 {
183  ip4_fib_mtrie_leaf_t leaf[2];
184  ip4_fib_mtrie_t * mtrie[2];
185 
186  mtrie[0] = &ip4_fib_get(fib_index0)->mtrie;
187  mtrie[1] = &ip4_fib_get(fib_index1)->mtrie;
188 
189  leaf[0] = ip4_fib_mtrie_lookup_step_one (mtrie[0], addr0);
190  leaf[1] = ip4_fib_mtrie_lookup_step_one (mtrie[1], addr1);
191  leaf[0] = ip4_fib_mtrie_lookup_step (mtrie[0], leaf[0], addr0, 2);
192  leaf[1] = ip4_fib_mtrie_lookup_step (mtrie[1], leaf[1], addr1, 2);
193  leaf[0] = ip4_fib_mtrie_lookup_step (mtrie[0], leaf[0], addr0, 3);
194  leaf[1] = ip4_fib_mtrie_lookup_step (mtrie[1], leaf[1], addr1, 3);
195 
196  *lb0 = ip4_fib_mtrie_leaf_get_adj_index(leaf[0]);
197  *lb1 = ip4_fib_mtrie_leaf_get_adj_index(leaf[1]);
198 }
199 
200 #endif
201 
static u32 ip4_fib_lookup(ip4_main_t *im, u32 sw_if_index, ip4_address_t *dst)
Definition: ip4_fib.h:119
enum fib_source_t_ fib_source_t
The different sources that can create a route.
u32 ip4_fib_table_lookup_lb(ip4_fib_t *fib, const ip4_address_t *dst)
Definition: ip4_fib.c:273
The mutiway-TRIE.
Definition: ip4_mtrie.h:129
static ip4_fib_mtrie_leaf_t ip4_fib_mtrie_lookup_step(const ip4_fib_mtrie_t *m, ip4_fib_mtrie_leaf_t current_leaf, const ip4_address_t *dst_address, u32 dst_address_byte_index)
Lookup step.
Definition: ip4_mtrie.h:202
void ip4_fib_table_destroy(u32 fib_index)
Definition: ip4_fib.c:159
CLIB_CACHE_LINE_ALIGN_MARK(cacheline0)
Required for pool_get_aligned.
u32 index_t
A Data-Path Object is an object that represents actions that are applied to packets are they are swit...
Definition: dpo.h:41
vl_api_address_t src
Definition: gre.api:54
void ip4_fib_table_fwding_dpo_remove(ip4_fib_t *fib, const ip4_address_t *addr, u32 len, const dpo_id_t *dpo, fib_node_index_t cover_index)
Definition: ip4_fib.c:394
u32 * fib_index_by_sw_if_index
Table index indexed by software interface.
Definition: ip4.h:122
vhost_vring_addr_t addr
Definition: vhost_user.h:254
unsigned char u8
Definition: types.h:56
#define static_always_inline
Definition: clib.h:106
void ip4_fib_table_sub_tree_walk(ip4_fib_t *fib, const fib_prefix_t *root, fib_table_walk_fn_t fn, void *ctx)
Walk all entries in a sub-tree of the FIB table N.B: This is NOT safe to deletes. ...
Definition: ip4_fib.c:435
vl_api_interface_index_t sw_if_index
Definition: gre.api:53
u32 table_id
Definition: ip4_fib.h:54
void ip4_fib_table_entry_insert(ip4_fib_t *fib, const ip4_address_t *addr, u32 len, fib_node_index_t fib_entry_index)
Definition: ip4_fib.c:320
u32 index
Definition: ip4_fib.h:57
u32 ip4_fib_mtrie_leaf_t
Definition: ip4_mtrie.h:52
Aggregate type for a prefix.
Definition: fib_types.h:203
static_always_inline void ip4_fib_forwarding_lookup_x2(u32 fib_index0, u32 fib_index1, const ip4_address_t *addr0, const ip4_address_t *addr1, index_t *lb0, index_t *lb1)
Definition: ip4_fib.h:176
unsigned int u32
Definition: types.h:88
u32 ip4_fib_table_find_or_create_and_lock(u32 table_id, fib_source_t src)
Get or create an IPv4 fib.
Definition: ip4_fib.c:209
static u32 ip4_fib_mtrie_leaf_get_adj_index(ip4_fib_mtrie_leaf_t n)
From the stored slot value extract the LB index value.
Definition: ip4_mtrie.h:192
The identity of a DPO is a combination of its type and its instance number/index of objects of that t...
Definition: dpo.h:170
#define hash_get(h, key)
Definition: hash.h:249
#define pool_elt_at_index(p, i)
Returns pointer to element at given index.
Definition: pool.h:534
uword * fib_index_by_table_id
Hash table mapping table id to fib index.
Definition: ip4.h:132
long ctx[MAX_CONNS]
Definition: main.c:144
struct ip4_fib_t_ ip4_fib_t
The IPv4 FIB.
#define always_inline
Definition: ipsec.h:28
u32 ip4_fib_table_create_and_lock(fib_source_t src)
Definition: ip4_fib.c:224
vl_api_address_t dst
Definition: gre.api:55
void ip4_fib_table_entry_remove(ip4_fib_t *fib, const ip4_address_t *addr, u32 len)
Definition: ip4_fib.c:355
ip4_fib_mtrie_t mtrie
Mtrie for fast lookups.
Definition: ip4_fib.h:48
u8 len
Definition: ip_types.api:92
The IPv4 FIB.
Definition: ip4_fib.h:39
void ip4_fib_table_fwding_dpo_update(ip4_fib_t *fib, const ip4_address_t *addr, u32 len, const dpo_id_t *dpo)
Definition: ip4_fib.c:385
static ip4_fib_t * ip4_fib_get(u32 index)
Get the FIB at the given index.
Definition: ip4_fib.h:113
u32 fib_node_index_t
A typedef of a node index.
Definition: fib_types.h:30
static u32 ip4_fib_index_from_table_id(u32 table_id)
Definition: ip4_fib.h:145
fib_table_walk_rc_t(* fib_table_walk_fn_t)(fib_node_index_t fei, void *ctx)
Call back function when walking entries in a FIB table.
Definition: fib_table.h:930
fib_node_index_t ip4_fib_table_lookup(const ip4_fib_t *fib, const ip4_address_t *addr, u32 len)
Definition: ip4_fib.c:297
static ip4_fib_mtrie_leaf_t ip4_fib_mtrie_lookup_step_one(const ip4_fib_mtrie_t *m, const ip4_address_t *dst_address)
Lookup step number 1.
Definition: ip4_mtrie.h:224
void ip4_fib_table_walk(ip4_fib_t *fib, fib_table_walk_fn_t fn, void *ctx)
Walk all entries in a FIB table N.B: This is NOT safe to deletes.
Definition: ip4_fib.c:418
u32 ip4_fib_table_get_index_for_sw_if_index(u32 sw_if_index)
Definition: ip4_fib.c:230
IPv4 main type.
Definition: ip4.h:106
static index_t ip4_fib_forwarding_lookup(u32 fib_index, const ip4_address_t *addr)
Definition: ip4_fib.h:160
#define vec_elt(v, i)
Get vector value at index i.
struct ip4_fib_t_ * v4_fibs
Vector of MTries.
Definition: ip4.h:114
u64 uword
Definition: types.h:112
uword * fib_entry_by_dst_address[33]
Definition: ip4_fib.h:51
ip4_main_t ip4_main
Global ip4 main structure.
Definition: ip4_forward.c:1144
fib_node_index_t ip4_fib_table_lookup_exact_match(const ip4_fib_t *fib, const ip4_address_t *addr, u32 len)
Definition: ip4_fib.c:249
u8 * format_ip4_fib_table_memory(u8 *s, va_list *args)
Definition: ip4_fib.c:572