FD.io VPP  v18.01.2-1-g9b554f3
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  /**
42  * Mtrie for fast lookups. Hash is used to maintain overlapping prefixes.
43  * First member so it's in the first cacheline.
44  */
46 
47  /* Hash table for each prefix length mapping. */
49 
50  /* Table ID (hash key) for this FIB. */
52 
53  /* Index into FIB vector. */
55 
56  /* N-tuple classifier indices */
59 
60 } ip4_fib_t;
61 
63  const ip4_address_t *addr,
64  u32 len);
66  const ip4_address_t *addr,
67  u32 len);
68 
69 extern void ip4_fib_table_entry_remove(ip4_fib_t *fib,
70  const ip4_address_t *addr,
71  u32 len);
72 
73 extern void ip4_fib_table_entry_insert(ip4_fib_t *fib,
74  const ip4_address_t *addr,
75  u32 len,
76  fib_node_index_t fib_entry_index);
77 extern void ip4_fib_table_destroy(u32 fib_index);
78 
80  const ip4_address_t *addr,
81  u32 len,
82  const dpo_id_t *dpo);
83 
85  const ip4_address_t *addr,
86  u32 len,
87  const dpo_id_t *dpo,
88  fib_node_index_t cover_index);
90  const ip4_address_t * dst);
91 
92 /**
93  * @brief Walk all entries in a FIB table
94  * N.B: This is NOT safe to deletes. If you need to delete walk the whole
95  * table and store elements in a vector, then delete the elements
96  */
97 extern void ip4_fib_table_walk(ip4_fib_t *fib,
99  void *ctx);
100 
101 /**
102  * @brief Get the FIB at the given index
103  */
104 static inline ip4_fib_t *
106 {
107  return (pool_elt_at_index(ip4_main.v4_fibs, index));
108 }
109 
111 ip4_fib_lookup (ip4_main_t * im, u32 sw_if_index, ip4_address_t * dst)
112 {
113  return (ip4_fib_table_lookup_lb(
114  ip4_fib_get(vec_elt (im->fib_index_by_sw_if_index, sw_if_index)),
115  dst));
116 }
117 
118 /**
119  * @brief Get or create an IPv4 fib.
120  *
121  * Get or create an IPv4 fib with the provided table ID.
122  *
123  * @param table_id
124  * When set to \c ~0, an arbitrary and unused fib ID is picked
125  * and can be retrieved with \c ret->table_id.
126  * Otherwise, the fib ID to be used to retrieve or create the desired fib.
127  * @returns A pointer to the retrieved or created fib.
128  *
129  */
131  fib_source_t src);
133 
134 extern u8 *format_ip4_fib_table_memory(u8 * s, va_list * args);
135 
136 static inline
138 {
139  ip4_main_t * im = &ip4_main;
140  uword * p;
141 
142  p = hash_get (im->fib_index_by_table_id, table_id);
143  if (!p)
144  return ~0;
145 
146  return p[0];
147 }
148 
150 
153  const ip4_address_t * addr)
154 {
157 
158  mtrie = &ip4_fib_get(fib_index)->mtrie;
159 
160  leaf = ip4_fib_mtrie_lookup_step_one (mtrie, addr);
161  leaf = ip4_fib_mtrie_lookup_step (mtrie, leaf, addr, 2);
162  leaf = ip4_fib_mtrie_lookup_step (mtrie, leaf, addr, 3);
163 
164  return (ip4_fib_mtrie_leaf_get_adj_index(leaf));
165 }
166 
167 
168 #endif
169 
static u32 ip4_fib_lookup(ip4_main_t *im, u32 sw_if_index, ip4_address_t *dst)
Definition: ip4_fib.h:111
u32 ip4_fib_table_lookup_lb(ip4_fib_t *fib, const ip4_address_t *dst)
Definition: ip4_fib.c:269
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:161
int(* 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:798
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
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:390
u32 * fib_index_by_sw_if_index
Table index indexed by software interface.
Definition: ip4.h:111
u32 table_id
Definition: ip4_fib.h:51
#define always_inline
Definition: clib.h:92
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:316
u32 index
Definition: ip4_fib.h:54
u32 ip4_fib_mtrie_leaf_t
Definition: ip4_mtrie.h:52
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:205
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:166
#define hash_get(h, key)
Definition: hash.h:248
#define pool_elt_at_index(p, i)
Returns pointer to element at given index.
Definition: pool.h:459
uword * fib_index_by_table_id
Hash table mapping table id to fib index.
Definition: ip4.h:121
enum fib_source_t_ fib_source_t
The different sources that can create a route.
struct ip4_fib_t_ ip4_fib_t
The IPv4 FIB.
u32 ip4_fib_table_create_and_lock(fib_source_t src)
Definition: ip4_fib.c:220
void ip4_fib_table_entry_remove(ip4_fib_t *fib, const ip4_address_t *addr, u32 len)
Definition: ip4_fib.c:351
ip4_fib_mtrie_t mtrie
Mtrie for fast lookups.
Definition: ip4_fib.h:45
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:381
static ip4_fib_t * ip4_fib_get(u32 index)
Get the FIB at the given index.
Definition: ip4_fib.h:105
u32 fib_node_index_t
A typedef of a node index.
Definition: fib_types.h:29
static u32 ip4_fib_index_from_table_id(u32 table_id)
Definition: ip4_fib.h:137
fib_node_index_t ip4_fib_table_lookup(const ip4_fib_t *fib, const ip4_address_t *addr, u32 len)
Definition: ip4_fib.c:293
unsigned int u32
Definition: types.h:88
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:416
long ctx[MAX_CONNS]
Definition: main.c:122
u32 ip4_fib_table_get_index_for_sw_if_index(u32 sw_if_index)
Definition: ip4_fib.c:226
IPv4 main type.
Definition: ip4.h:95
static index_t ip4_fib_forwarding_lookup(u32 fib_index, const ip4_address_t *addr)
Definition: ip4_fib.h:152
u64 uword
Definition: types.h:112
#define vec_elt(v, i)
Get vector value at index i.
struct ip4_fib_t_ * v4_fibs
Vector of MTries.
Definition: ip4.h:103
unsigned char u8
Definition: types.h:56
u32 rev_classify_table_index
Definition: ip4_fib.h:58
u32 fwd_classify_table_index
Definition: ip4_fib.h:57
uword * fib_entry_by_dst_address[33]
Definition: ip4_fib.h:48
ip4_main_t ip4_main
Global ip4 main structure.
Definition: ip4_forward.c:1181
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:245
vhost_vring_addr_t addr
Definition: vhost-user.h:83
u8 * format_ip4_fib_table_memory(u8 *s, va_list *args)
Definition: ip4_fib.c:497