FD.io VPP  v16.12-rc0-308-g931be3a
Vector Packet Processing
ip4_mtrie.h
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2015 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  * ip/ip4_fib.h: ip4 mtrie fib
17  *
18  * Copyright (c) 2012 Eliot Dresselhaus
19  *
20  * Permission is hereby granted, free of charge, to any person obtaining
21  * a copy of this software and associated documentation files (the
22  * "Software"), to deal in the Software without restriction, including
23  * without limitation the rights to use, copy, modify, merge, publish,
24  * distribute, sublicense, and/or sell copies of the Software, and to
25  * permit persons to whom the Software is furnished to do so, subject to
26  * the following conditions:
27  *
28  * The above copyright notice and this permission notice shall be
29  * included in all copies or substantial portions of the Software.
30  *
31  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
32  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
33  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
34  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
35  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
36  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
37  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
38  */
39 
40 #ifndef included_ip_ip4_fib_h
41 #define included_ip_ip4_fib_h
42 
43 #include <vppinfra/cache.h>
44 #include <vppinfra/vector.h>
45 #include <vnet/ip/lookup.h>
46 #include <vnet/ip/ip4_packet.h> /* for ip4_address_t */
47 
48 /* ip4 fib leafs: 4 ply 8-8-8-8 mtrie.
49  1 + 2*adj_index for terminal leaves.
50  0 + 2*next_ply_index for non-terminals.
51  1 => empty (adjacency index of zero is special miss adjacency). */
53 
54 #define IP4_FIB_MTRIE_LEAF_EMPTY (1 + 2*0)
55 #define IP4_FIB_MTRIE_LEAF_ROOT (0 + 2*0)
56 
58 { return n == IP4_FIB_MTRIE_LEAF_EMPTY; }
59 
61 { return n != IP4_FIB_MTRIE_LEAF_EMPTY; }
62 
64 { return n & 1; }
65 
67 {
69  return n >> 1;
70 }
71 
72 always_inline ip4_fib_mtrie_leaf_t ip4_fib_mtrie_leaf_set_adj_index (u32 adj_index)
73 {
74  ip4_fib_mtrie_leaf_t l;
75  l = 1 + 2*adj_index;
76  ASSERT (ip4_fib_mtrie_leaf_get_adj_index (l) == adj_index);
77  return l;
78 }
79 
81 { return (n & 1) == 0; }
82 
84 {
86  return n >> 1;
87 }
88 
90 {
91  ip4_fib_mtrie_leaf_t l;
92  l = 0 + 2*i;
94  return l;
95 }
96 
97 /* One ply of the 4 ply mtrie fib. */
98 typedef struct {
99  union {
100  ip4_fib_mtrie_leaf_t leaves[256];
101 
102 #ifdef CLIB_HAVE_VEC128
103  u32x4 leaves_as_u32x4[256 / 4];
104 #endif
105  };
106 
107  /* Prefix length for terminal leaves. */
108  u8 dst_address_bits_of_leaves[256];
109 
110  /* Number of non-empty leafs (whether terminal or not). */
112 
113  /* Pad to cache line boundary. */
115  - 1 * sizeof (i32)];
117 
118 _Static_assert(0 == sizeof(ip4_fib_mtrie_ply_t) % CLIB_CACHE_LINE_BYTES,
119  "IP4 Mtrie ply cache line");
120 
121 typedef struct {
122  /* Pool of plies. Index zero is root ply. */
123  ip4_fib_mtrie_ply_t * ply_pool;
124 
125  /* Special case leaf for default route 0.0.0.0/0. */
126  ip4_fib_mtrie_leaf_t default_leaf;
128 
130 
131 struct ip4_fib_t;
132 
133 void ip4_fib_mtrie_add_del_route (struct ip4_fib_t * f,
134  ip4_address_t dst_address,
135  u32 dst_address_length,
136  u32 adj_index,
137  u32 is_del);
138 
139 /* Returns adjacency index. */
141 
143 
144 /* Lookup step. Processes 1 byte of 4 byte ip4 address. */
145 always_inline ip4_fib_mtrie_leaf_t
147  ip4_fib_mtrie_leaf_t current_leaf,
148  const ip4_address_t * dst_address,
149  u32 dst_address_byte_index)
150 {
151  ip4_fib_mtrie_leaf_t next_leaf;
152  ip4_fib_mtrie_ply_t * ply;
153  uword current_is_terminal = ip4_fib_mtrie_leaf_is_terminal (current_leaf);
154 
155  ply = m->ply_pool + (current_is_terminal ? 0 : (current_leaf >> 1));
156  next_leaf = ply->leaves[dst_address->as_u8[dst_address_byte_index]];
157  next_leaf = current_is_terminal ? current_leaf : next_leaf;
158 
159  return next_leaf;
160 }
161 
162 #endif /* included_ip_ip4_fib_h */
u8 pad[3]
log2 (size of the packing page block)
Definition: bihash_doc.h:61
sll srl srl sll sra u16x4 i
Definition: vector_sse2.h:343
u32 ip4_mtrie_lookup_address(ip4_fib_mtrie_t *m, ip4_address_t dst)
Definition: ip4_mtrie.c:137
static u32 ip4_fib_mtrie_leaf_get_next_ply_index(ip4_fib_mtrie_leaf_t n)
Definition: ip4_mtrie.h:83
Definitions for all things IP (v4|v6) unicast and multicast lookup related.
void ip4_fib_mtrie_add_del_route(struct ip4_fib_t *f, ip4_address_t dst_address, u32 dst_address_length, u32 adj_index, u32 is_del)
Definition: ip4_mtrie.c:364
static u32 ip4_fib_mtrie_leaf_is_next_ply(ip4_fib_mtrie_leaf_t n)
Definition: ip4_mtrie.h:80
static ip4_fib_mtrie_leaf_t ip4_fib_mtrie_leaf_set_next_ply_index(u32 i)
Definition: ip4_mtrie.h:89
#define IP4_FIB_MTRIE_LEAF_EMPTY
Definition: ip4_mtrie.h:54
ip4_fib_mtrie_ply_t * ply_pool
Definition: ip4_mtrie.h:123
static ip4_fib_mtrie_leaf_t ip4_fib_mtrie_lookup_step(ip4_fib_mtrie_t *m, ip4_fib_mtrie_leaf_t current_leaf, const ip4_address_t *dst_address, u32 dst_address_byte_index)
Definition: ip4_mtrie.h:146
#define always_inline
Definition: clib.h:84
unsigned long long u32x4
Definition: ixge.c:28
int i32
Definition: types.h:81
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)
Definition: ip4_mtrie.h:66
void ip4_fib_mtrie_init(ip4_fib_mtrie_t *m)
Definition: ip4.h:48
static ip4_fib_mtrie_leaf_t ip4_fib_mtrie_leaf_set_adj_index(u32 adj_index)
Definition: ip4_mtrie.h:72
#define ASSERT(truth)
ip4_fib_mtrie_leaf_t leaves[256]
Definition: ip4_mtrie.h:100
unsigned int u32
Definition: types.h:88
static u32 ip4_fib_mtrie_leaf_is_non_empty(ip4_fib_mtrie_leaf_t n)
Definition: ip4_mtrie.h:60
u8 *( format_function_t)(u8 *s, va_list *args)
Definition: format.h:48
u64 uword
Definition: types.h:112
format_function_t format_ip4_fib_mtrie
Definition: ip4_mtrie.h:142
unsigned char u8
Definition: types.h:56
static u32 ip4_fib_mtrie_leaf_is_empty(ip4_fib_mtrie_leaf_t n)
Definition: ip4_mtrie.h:57
#define CLIB_CACHE_LINE_BYTES
Definition: cache.h:67
static u32 ip4_fib_mtrie_leaf_is_terminal(ip4_fib_mtrie_leaf_t n)
Definition: ip4_mtrie.h:63
ip4_fib_mtrie_leaf_t default_leaf
Definition: ip4_mtrie.h:126