FD.io VPP  v17.07.01-10-g3be13f0
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  */
132 
133 
134 static inline
136 {
137  ip4_main_t * im = &ip4_main;
138  uword * p;
139 
140  p = hash_get (im->fib_index_by_table_id, table_id);
141  if (!p)
142  return ~0;
143 
144  return p[0];
145 }
146 
148 
151  const ip4_address_t * addr)
152 {
155 
156  mtrie = &ip4_fib_get(fib_index)->mtrie;
157 
158  leaf = ip4_fib_mtrie_lookup_step_one (mtrie, addr);
159  leaf = ip4_fib_mtrie_lookup_step (mtrie, leaf, addr, 2);
160  leaf = ip4_fib_mtrie_lookup_step (mtrie, leaf, addr, 3);
161 
162  return (ip4_fib_mtrie_leaf_get_adj_index(leaf));
163 }
164 
165 
166 #endif
167 
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:264
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:197
void ip4_fib_table_destroy(u32 fib_index)
Definition: ip4_fib.c:157
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:751
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:376
u32 * fib_index_by_sw_if_index
Table index indexed by software interface.
Definition: ip4.h:99
u32 ip4_fib_table_find_or_create_and_lock(u32 table_id)
Get or create an IPv4 fib.
Definition: ip4_fib.c:201
u32 table_id
Definition: ip4_fib.h:51
#define always_inline
Definition: clib.h:84
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:311
u32 index
Definition: ip4_fib.h:54
u32 ip4_fib_mtrie_leaf_t
Definition: ip4_mtrie.h:52
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:187
The identity of a DPO is a combination of its type and its instance number/index of objects of that t...
Definition: dpo.h:152
#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:397
uword * fib_index_by_table_id
Hash table mapping table id to fib index.
Definition: ip4.h:109
struct ip4_fib_t_ ip4_fib_t
The IPv4 FIB.
void ip4_fib_table_entry_remove(ip4_fib_t *fib, const ip4_address_t *addr, u32 len)
Definition: ip4_fib.c:341
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:367
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:28
static u32 ip4_fib_index_from_table_id(u32 table_id)
Definition: ip4_fib.h:135
fib_node_index_t ip4_fib_table_lookup(const ip4_fib_t *fib, const ip4_address_t *addr, u32 len)
Definition: ip4_fib.c:288
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:219
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:402
u32 ip4_fib_table_get_index_for_sw_if_index(u32 sw_if_index)
Definition: ip4_fib.c:221
IPv4 main type.
Definition: ip4.h:83
static index_t ip4_fib_forwarding_lookup(u32 fib_index, const ip4_address_t *addr)
Definition: ip4_fib.h:150
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:91
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:1168
u32 ip4_fib_table_create_and_lock(void)
Definition: ip4_fib.c:215
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:240
vhost_vring_addr_t addr
Definition: vhost-user.h:82