FD.io VPP  v18.07-rc0-415-g6c78436
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  /* Required for pool_get_aligned */
61  CLIB_CACHE_LINE_ALIGN_MARK(cacheline0);
62 } ip4_fib_t;
63 
65  const ip4_address_t *addr,
66  u32 len);
68  const ip4_address_t *addr,
69  u32 len);
70 
71 extern void ip4_fib_table_entry_remove(ip4_fib_t *fib,
72  const ip4_address_t *addr,
73  u32 len);
74 
75 extern void ip4_fib_table_entry_insert(ip4_fib_t *fib,
76  const ip4_address_t *addr,
77  u32 len,
78  fib_node_index_t fib_entry_index);
79 extern void ip4_fib_table_destroy(u32 fib_index);
80 
82  const ip4_address_t *addr,
83  u32 len,
84  const dpo_id_t *dpo);
85 
87  const ip4_address_t *addr,
88  u32 len,
89  const dpo_id_t *dpo,
90  fib_node_index_t cover_index);
92  const ip4_address_t * dst);
93 
94 /**
95  * @brief Walk all entries in a FIB table
96  * N.B: This is NOT safe to deletes. If you need to delete walk the whole
97  * table and store elements in a vector, then delete the elements
98  */
99 extern void ip4_fib_table_walk(ip4_fib_t *fib,
101  void *ctx);
102 
103 /**
104  * @brief Walk all entries in a sub-tree of the FIB table
105  * N.B: This is NOT safe to deletes. If you need to delete walk the whole
106  * table and store elements in a vector, then delete the elements
107  */
108 extern void ip4_fib_table_sub_tree_walk(ip4_fib_t *fib,
109  const fib_prefix_t *root,
111  void *ctx);
112 
113 /**
114  * @brief Get the FIB at the given index
115  */
116 static inline ip4_fib_t *
118 {
119  return (pool_elt_at_index(ip4_main.v4_fibs, index));
120 }
121 
123 ip4_fib_lookup (ip4_main_t * im, u32 sw_if_index, ip4_address_t * dst)
124 {
125  return (ip4_fib_table_lookup_lb(
126  ip4_fib_get(vec_elt (im->fib_index_by_sw_if_index, sw_if_index)),
127  dst));
128 }
129 
130 /**
131  * @brief Get or create an IPv4 fib.
132  *
133  * Get or create an IPv4 fib with the provided table ID.
134  *
135  * @param table_id
136  * When set to \c ~0, an arbitrary and unused fib ID is picked
137  * and can be retrieved with \c ret->table_id.
138  * Otherwise, the fib ID to be used to retrieve or create the desired fib.
139  * @returns A pointer to the retrieved or created fib.
140  *
141  */
143  fib_source_t src);
145 
146 extern u8 *format_ip4_fib_table_memory(u8 * s, va_list * args);
147 
148 static inline
150 {
151  ip4_main_t * im = &ip4_main;
152  uword * p;
153 
154  p = hash_get (im->fib_index_by_table_id, table_id);
155  if (!p)
156  return ~0;
157 
158  return p[0];
159 }
160 
162 
165  const ip4_address_t * addr)
166 {
169 
170  mtrie = &ip4_fib_get(fib_index)->mtrie;
171 
172  leaf = ip4_fib_mtrie_lookup_step_one (mtrie, addr);
173  leaf = ip4_fib_mtrie_lookup_step (mtrie, leaf, addr, 2);
174  leaf = ip4_fib_mtrie_lookup_step (mtrie, leaf, addr, 3);
175 
176  return (ip4_fib_mtrie_leaf_get_adj_index(leaf));
177 }
178 
179 
180 #endif
181 
static u32 ip4_fib_lookup(ip4_main_t *im, u32 sw_if_index, ip4_address_t *dst)
Definition: ip4_fib.h:123
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
CLIB_CACHE_LINE_ALIGN_MARK(cacheline0)
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
unsigned char u8
Definition: types.h:56
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:433
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
Aggregrate type for a prefix.
Definition: fib_types.h:188
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: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:168
#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:461
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:117
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:149
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:871
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
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:126
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:164
#define vec_elt(v, i)
Get vector value at index i.
struct ip4_fib_t_ * v4_fibs
Vector of MTries.
Definition: ip4.h:103
u64 uword
Definition: types.h:112
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:832
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:570