1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
|
/*
* 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.
*/
/**
* @brief The IPv4 FIB
*
* FIBs are composed of two prefix data-bases (akak tables). The non-forwarding
* table contains all the routes that the control plane has programmed, the
* forwarding table contains the sub-set of those routes that can be used to
* forward packets.
* In the IPv4 FIB the non-forwarding table is an array of hash tables indexed
* by mask length, the forwarding table is an mtrie
*
* This IPv4 FIB is used by the protocol independent FIB. So directly using
* this APIs in client code is not encouraged. However, this IPv4 FIB can be
* used if all the client wants is an IPv4 prefix data-base
*/
#ifndef __IP4_FIB_H__
#define __IP4_FIB_H__
#include <vlib/vlib.h>
#include <vnet/ip/ip.h>
#include <vnet/fib/fib_entry.h>
#include <vnet/fib/fib_table.h>
#include <vnet/ip/ip4_mtrie.h>
typedef struct ip4_fib_t_
{
/** Required for pool_get_aligned */
CLIB_CACHE_LINE_ALIGN_MARK(cacheline0);
/**
* Mtrie for fast lookups. Hash is used to maintain overlapping prefixes.
* First member so it's in the first cacheline.
*/
ip4_mtrie_16_t mtrie;
/* Hash table for each prefix length mapping. */
uword *fib_entry_by_dst_address[33];
/* Table ID (hash key) for this FIB. */
u32 table_id;
/* Index into FIB vector. */
u32 index;
} ip4_fib_t;
extern fib_node_index_t ip4_fib_table_lookup(const ip4_fib_t *fib,
const ip4_address_t *addr,
u32 len);
extern fib_node_index_t ip4_fib_table_lookup_exact_match(const ip4_fib_t *fib,
const ip4_address_t *addr,
u32 len);
extern void ip4_fib_table_entry_remove(ip4_fib_t *fib,
const ip4_address_t *addr,
u32 len);
extern void ip4_fib_table_entry_insert(ip4_fib_t *fib,
const ip4_address_t *addr,
u32 len,
fib_node_index_t fib_entry_index);
extern void ip4_fib_table_destroy(u32 fib_index);
extern void ip4_fib_table_fwding_dpo_update(ip4_fib_t *fib,
const ip4_address_t *addr,
u32 len,
const dpo_id_t *dpo);
extern 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);
extern u32 ip4_fib_table_lookup_lb (ip4_fib_t *fib,
const ip4_address_t * dst);
/**
* @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 ip4_fib_table_walk(ip4_fib_t *fib,
fib_table_walk_fn_t fn,
void *ctx);
/**
* @brief Walk all entries in a sub-tree of the 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 ip4_fib_table_sub_tree_walk(ip4_fib_t *fib,
const fib_prefix_t *root,
fib_table_walk_fn_t fn,
void *ctx);
/**
* @brief Get the FIB at the given index
*/
static inline ip4_fib_t *
ip4_fib_get (u32 index)
{
return (pool_elt_at_index(ip4_main.v4_fibs, index));
}
always_inline u32
ip4_fib_lookup (ip4_main_t * im, u32 sw_if_index, ip4_address_t * dst)
{
return (ip4_fib_table_lookup_lb(
ip4_fib_get(vec_elt (im->fib_index_by_sw_if_index, sw_if_index)),
dst));
}
/**
* @brief Get or create an IPv4 fib.
*
* Get or create an IPv4 fib with the provided table ID.
*
* @param table_id
* When set to \c ~0, an arbitrary and unused fib ID is picked
* and can be retrieved with \c ret->table_id.
* Otherwise, the fib ID to be used to retrieve or create the desired fib.
* @returns A pointer to the retrieved or created fib.
*
*/
extern u32 ip4_fib_table_find_or_create_and_lock(u32 table_id,
fib_source_t src);
extern u32 ip4_fib_table_create_and_lock(fib_source_t src);
extern u8 *format_ip4_fib_table_memory(u8 * s, va_list * args);
static inline
u32 ip4_fib_index_from_table_id (u32 table_id)
{
ip4_main_t * im = &ip4_main;
uword * p;
p = hash_get (im->fib_index_by_table_id, table_id);
if (!p)
return ~0;
return p[0];
}
extern u32 ip4_fib_table_get_index_for_sw_if_index(u32 sw_if_index);
always_inline index_t
ip4_fib_forwarding_lookup (u32 fib_index,
const ip4_address_t * addr)
{
ip4_mtrie_leaf_t leaf;
ip4_mtrie_16_t * mtrie;
mtrie = &ip4_fib_get(fib_index)->mtrie;
leaf = ip4_mtrie_16_lookup_step_one (mtrie, addr);
leaf = ip4_mtrie_16_lookup_step (mtrie, leaf, addr, 2);
leaf = ip4_mtrie_16_lookup_step (mtrie, leaf, addr, 3);
return (ip4_mtrie_leaf_get_adj_index(leaf));
}
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)
{
ip4_mtrie_leaf_t leaf[2];
ip4_mtrie_16_t * mtrie[2];
mtrie[0] = &ip4_fib_get(fib_index0)->mtrie;
mtrie[1] = &ip4_fib_get(fib_index1)->mtrie;
leaf[0] = ip4_mtrie_16_lookup_step_one (mtrie[0], addr0);
leaf[1] = ip4_mtrie_16_lookup_step_one (mtrie[1], addr1);
leaf[0] = ip4_mtrie_16_lookup_step (mtrie[0], leaf[0], addr0, 2);
leaf[1] = ip4_mtrie_16_lookup_step (mtrie[1], leaf[1], addr1, 2);
leaf[0] = ip4_mtrie_16_lookup_step (mtrie[0], leaf[0], addr0, 3);
leaf[1] = ip4_mtrie_16_lookup_step (mtrie[1], leaf[1], addr1, 3);
*lb0 = ip4_mtrie_leaf_get_adj_index(leaf[0]);
*lb1 = ip4_mtrie_leaf_get_adj_index(leaf[1]);
}
static_always_inline void
ip4_fib_forwarding_lookup_x4 (u32 fib_index0,
u32 fib_index1,
u32 fib_index2,
u32 fib_index3,
const ip4_address_t * addr0,
const ip4_address_t * addr1,
const ip4_address_t * addr2,
const ip4_address_t * addr3,
index_t *lb0,
index_t *lb1,
index_t *lb2,
index_t *lb3)
{
ip4_mtrie_leaf_t leaf[4];
ip4_mtrie_16_t * mtrie[4];
mtrie[0] = &ip4_fib_get(fib_index0)->mtrie;
mtrie[1] = &ip4_fib_get(fib_index1)->mtrie;
mtrie[2] = &ip4_fib_get(fib_index2)->mtrie;
mtrie[3] = &ip4_fib_get(fib_index3)->mtrie;
leaf[0] = ip4_mtrie_16_lookup_step_one (mtrie[0], addr0);
leaf[1] = ip4_mtrie_16_lookup_step_one (mtrie[1], addr1);
leaf[2] = ip4_mtrie_16_lookup_step_one (mtrie[2], addr2);
leaf[3] = ip4_mtrie_16_lookup_step_one (mtrie[3], addr3);
leaf[0] = ip4_mtrie_16_lookup_step (mtrie[0], leaf[0], addr0, 2);
leaf[1] = ip4_mtrie_16_lookup_step (mtrie[1], leaf[1], addr1, 2);
leaf[2] = ip4_mtrie_16_lookup_step (mtrie[2], leaf[2], addr2, 2);
leaf[3] = ip4_mtrie_16_lookup_step (mtrie[3], leaf[3], addr3, 2);
leaf[0] = ip4_mtrie_16_lookup_step (mtrie[0], leaf[0], addr0, 3);
leaf[1] = ip4_mtrie_16_lookup_step (mtrie[1], leaf[1], addr1, 3);
leaf[2] = ip4_mtrie_16_lookup_step (mtrie[2], leaf[2], addr2, 3);
leaf[3] = ip4_mtrie_16_lookup_step (mtrie[3], leaf[3], addr3, 3);
*lb0 = ip4_mtrie_leaf_get_adj_index(leaf[0]);
*lb1 = ip4_mtrie_leaf_get_adj_index(leaf[1]);
*lb2 = ip4_mtrie_leaf_get_adj_index(leaf[2]);
*lb3 = ip4_mtrie_leaf_get_adj_index(leaf[3]);
}
#endif
|
