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:
7 * http://www.apache.org/licenses/LICENSE-2.0
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.
16 * ip/ip4_fib.h: ip4 mtrie fib
18 * Copyright (c) 2012 Eliot Dresselhaus
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:
28 * The above copyright notice and this permission notice shall be
29 * included in all copies or substantial portions of the Software.
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.
40 #ifndef included_ip_ip4_fib_h
41 #define included_ip_ip4_fib_h
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 */
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). */
52 typedef u32 ip4_fib_mtrie_leaf_t;
54 #define IP4_FIB_MTRIE_LEAF_EMPTY (1 + 2*0)
57 * @brief One ply of the 4 ply mtrie fib.
62 * The leaves/slots/buckets to be filed with leafs
66 ip4_fib_mtrie_leaf_t leaves[256];
68 #ifdef CLIB_HAVE_VEC128
69 u32x4 leaves_as_u32x4[256 / 4];
74 * Prefix length for leaves/ply.
76 u8 dst_address_bits_of_leaves[256];
79 * Number of non-empty leafs (whether terminal or not).
81 i32 n_non_empty_leafs;
84 * The length of the ply's coviering prefix. Also a measure of its depth
85 * If a leaf in a slot has a mask length longer than this then it is
86 * 'non-empty'. Otherwise it is the value of the cover.
88 i32 dst_address_bits_base;
90 /* Pad to cache line boundary. */
91 u8 pad[CLIB_CACHE_LINE_BYTES - 2 * sizeof (i32)];
95 STATIC_ASSERT (0 == sizeof (ip4_fib_mtrie_ply_t) % CLIB_CACHE_LINE_BYTES,
96 "IP4 Mtrie ply cache line");
100 /* Pool of plies. Index zero is root ply. */
101 ip4_fib_mtrie_ply_t *ply_pool;
104 void ip4_fib_mtrie_init (ip4_fib_mtrie_t * m);
108 void ip4_fib_mtrie_add_del_route (struct ip4_fib_t *f,
109 ip4_address_t dst_address,
110 u32 dst_address_length,
111 u32 adj_index, u32 is_del);
113 format_function_t format_ip4_fib_mtrie;
116 ip4_fib_mtrie_leaf_is_terminal (ip4_fib_mtrie_leaf_t n)
122 ip4_fib_mtrie_leaf_get_adj_index (ip4_fib_mtrie_leaf_t n)
124 ASSERT (ip4_fib_mtrie_leaf_is_terminal (n));
128 /* Lookup step. Processes 1 byte of 4 byte ip4 address. */
129 always_inline ip4_fib_mtrie_leaf_t
130 ip4_fib_mtrie_lookup_step (const ip4_fib_mtrie_t * m,
131 ip4_fib_mtrie_leaf_t current_leaf,
132 const ip4_address_t * dst_address,
133 u32 dst_address_byte_index)
135 ip4_fib_mtrie_ply_t *ply;
136 uword current_is_terminal = ip4_fib_mtrie_leaf_is_terminal (current_leaf);
138 if (!current_is_terminal)
140 ply = m->ply_pool + (current_leaf >> 1);
141 return (ply->leaves[dst_address->as_u8[dst_address_byte_index]]);
147 /* Lookup step. Processes 1 byte of 4 byte ip4 address. */
148 always_inline ip4_fib_mtrie_leaf_t
149 ip4_fib_mtrie_lookup_step_one (const ip4_fib_mtrie_t * m,
150 const ip4_address_t * dst_address)
152 ip4_fib_mtrie_leaf_t next_leaf;
153 ip4_fib_mtrie_ply_t *ply;
156 next_leaf = ply->leaves[dst_address->as_u8[0]];
161 #endif /* included_ip_ip4_fib_h */
164 * fd.io coding-style-patch-verification: ON
167 * eval: (c-set-style "gnu")