FD.io VPP  v17.04.2-2-ga8f93f8
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 ip4_fib_mtrie_leaf_is_empty (ip4_fib_mtrie_leaf_t n)
59 {
60  return n == IP4_FIB_MTRIE_LEAF_EMPTY;
61 }
62 
64 ip4_fib_mtrie_leaf_is_non_empty (ip4_fib_mtrie_leaf_t n)
65 {
66  return n != IP4_FIB_MTRIE_LEAF_EMPTY;
67 }
68 
70 ip4_fib_mtrie_leaf_is_terminal (ip4_fib_mtrie_leaf_t n)
71 {
72  return n & 1;
73 }
74 
76 ip4_fib_mtrie_leaf_get_adj_index (ip4_fib_mtrie_leaf_t n)
77 {
79  return n >> 1;
80 }
81 
82 always_inline ip4_fib_mtrie_leaf_t
84 {
85  ip4_fib_mtrie_leaf_t l;
86  l = 1 + 2 * adj_index;
87  ASSERT (ip4_fib_mtrie_leaf_get_adj_index (l) == adj_index);
88  return l;
89 }
90 
92 ip4_fib_mtrie_leaf_is_next_ply (ip4_fib_mtrie_leaf_t n)
93 {
94  return (n & 1) == 0;
95 }
96 
98 ip4_fib_mtrie_leaf_get_next_ply_index (ip4_fib_mtrie_leaf_t n)
99 {
101  return n >> 1;
102 }
103 
104 always_inline ip4_fib_mtrie_leaf_t
106 {
107  ip4_fib_mtrie_leaf_t l;
108  l = 0 + 2 * i;
110  return l;
111 }
112 
113 /* One ply of the 4 ply mtrie fib. */
114 typedef struct
115 {
116  union
117  {
118  ip4_fib_mtrie_leaf_t leaves[256];
119 
120 #ifdef CLIB_HAVE_VEC128
121  u32x4 leaves_as_u32x4[256 / 4];
122 #endif
123  };
124 
125  /* Prefix length for terminal leaves. */
126  u8 dst_address_bits_of_leaves[256];
127 
128  /* Number of non-empty leafs (whether terminal or not). */
130 
131  /* Pad to cache line boundary. */
132  u8 pad[CLIB_CACHE_LINE_BYTES - 1 * sizeof (i32)];
133 }
135 
136 STATIC_ASSERT (0 == sizeof (ip4_fib_mtrie_ply_t) % CLIB_CACHE_LINE_BYTES,
137  "IP4 Mtrie ply cache line");
138 
139 typedef struct
140 {
141  /* Pool of plies. Index zero is root ply. */
142  ip4_fib_mtrie_ply_t *ply_pool;
143 
144  /* Special case leaf for default route 0.0.0.0/0. */
145  ip4_fib_mtrie_leaf_t default_leaf;
147 
149 
150 struct ip4_fib_t;
151 
152 void ip4_fib_mtrie_add_del_route (struct ip4_fib_t *f,
153  ip4_address_t dst_address,
154  u32 dst_address_length,
155  u32 adj_index, u32 is_del);
156 
157 /* Returns adjacency index. */
159 
161 
162 /* Lookup step. Processes 1 byte of 4 byte ip4 address. */
163 always_inline ip4_fib_mtrie_leaf_t
165  ip4_fib_mtrie_leaf_t current_leaf,
166  const ip4_address_t * dst_address,
167  u32 dst_address_byte_index)
168 {
169  ip4_fib_mtrie_leaf_t next_leaf;
170  ip4_fib_mtrie_ply_t *ply;
171  uword current_is_terminal = ip4_fib_mtrie_leaf_is_terminal (current_leaf);
172 
173  ply = m->ply_pool + (current_is_terminal ? 0 : (current_leaf >> 1));
174  next_leaf = ply->leaves[dst_address->as_u8[dst_address_byte_index]];
175  next_leaf = current_is_terminal ? current_leaf : next_leaf;
176 
177  return next_leaf;
178 }
179 
180 #endif /* included_ip_ip4_fib_h */
181 
182 /*
183  * fd.io coding-style-patch-verification: ON
184  *
185  * Local Variables:
186  * eval: (c-set-style "gnu")
187  * End:
188  */
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:144
static u32 ip4_fib_mtrie_leaf_get_next_ply_index(ip4_fib_mtrie_leaf_t n)
Definition: ip4_mtrie.h:98
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:387
static u32 ip4_fib_mtrie_leaf_is_next_ply(ip4_fib_mtrie_leaf_t n)
Definition: ip4_mtrie.h:92
u8 *( format_function_t)(u8 *s, va_list *args)
Definition: format.h:48
static ip4_fib_mtrie_leaf_t ip4_fib_mtrie_leaf_set_next_ply_index(u32 i)
Definition: ip4_mtrie.h:105
#define IP4_FIB_MTRIE_LEAF_EMPTY
Definition: ip4_mtrie.h:54
ip4_fib_mtrie_ply_t * ply_pool
Definition: ip4_mtrie.h:142
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:164
#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:76
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:83
STATIC_ASSERT(0==sizeof(ip4_fib_mtrie_ply_t)%CLIB_CACHE_LINE_BYTES,"IP4 Mtrie ply cache line")
#define ASSERT(truth)
ip4_fib_mtrie_leaf_t leaves[256]
Definition: ip4_mtrie.h:118
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:64
u64 uword
Definition: types.h:112
format_function_t format_ip4_fib_mtrie
Definition: ip4_mtrie.h:160
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:58
#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:70
ip4_fib_mtrie_leaf_t default_leaf
Definition: ip4_mtrie.h:145