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:
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 #include <vnet/fib/fib_table.h>
17 #include <vnet/fib/fib_entry.h>
18 #include <vnet/fib/ip4_fib.h>
21 * ip4_fib_hash_table_lookup_exact_match
23 * Exact match prefix lookup
26 ip4_fib_hash_table_lookup_exact_match (const ip4_fib_hash_t *fib,
27 const ip4_address_t *addr,
30 uword * hash, * result;
33 hash = fib->fib_entry_by_dst_address[len];
34 key = (addr->data_u32 & ip4_main.fib_masks[len]);
36 result = hash_get(hash, key);
41 return (FIB_NODE_INDEX_INVALID);
45 * ip4_fib_hash_table_lookup_adj
47 * Longest prefix match
50 ip4_fib_hash_table_lookup_lb (const ip4_fib_hash_t *fib,
51 const ip4_address_t *addr)
55 fei = ip4_fib_hash_table_lookup(fib, addr, 32);
57 if (FIB_NODE_INDEX_INVALID != fei)
61 dpo = fib_entry_contribute_ip_forwarding(fei);
63 return (dpo->dpoi_index);
65 return (INDEX_INVALID);
69 * ip4_fib_hash_table_lookup
71 * Longest prefix match
74 ip4_fib_hash_table_lookup (const ip4_fib_hash_t *fib,
75 const ip4_address_t *addr,
78 uword * hash, * result;
82 for (mask_len = len; mask_len >= 0; mask_len--)
84 hash = fib->fib_entry_by_dst_address[mask_len];
85 key = (addr->data_u32 & ip4_main.fib_masks[mask_len]);
87 result = hash_get (hash, key);
93 return (FIB_NODE_INDEX_INVALID);
97 ip4_fib_hash_table_entry_insert (ip4_fib_hash_t *fib,
98 const ip4_address_t *addr,
100 fib_node_index_t fib_entry_index)
102 uword * hash, * result;
105 key = (addr->data_u32 & ip4_main.fib_masks[len]);
106 hash = fib->fib_entry_by_dst_address[len];
107 result = hash_get (hash, key);
109 if (NULL == result) {
115 hash = hash_create (32 /* elts */, sizeof (uword));
116 hash_set_flags (hash, HASH_FLAG_NO_AUTO_SHRINK);
119 hash = hash_set(hash, key, fib_entry_index);
120 fib->fib_entry_by_dst_address[len] = hash;
129 ip4_fib_hash_table_entry_remove (ip4_fib_hash_t *fib,
130 const ip4_address_t *addr,
133 uword * hash, * result;
136 key = (addr->data_u32 & ip4_main.fib_masks[len]);
137 hash = fib->fib_entry_by_dst_address[len];
138 result = hash_get (hash, key);
143 * removing a non-existent entry. i'll allow it.
148 hash_unset(hash, key);
151 fib->fib_entry_by_dst_address[len] = hash;
155 ip4_fib_hash_table_walk (ip4_fib_hash_t *fib,
156 fib_table_walk_fn_t fn,
159 fib_prefix_t root = {
160 .fp_proto = FIB_PROTOCOL_IP4,
161 // address and length default to all 0
165 * A full tree walk is the dengenerate case of a sub-tree from
168 return (ip4_fib_hash_table_sub_tree_walk(fib, &root, fn, ctx));
172 ip4_fib_hash_table_sub_tree_walk (ip4_fib_hash_t *fib,
173 const fib_prefix_t *root,
174 fib_table_walk_fn_t fn,
177 fib_prefix_t *sub_trees = NULL;
181 * There is no efficient way to walk this array of hash tables.
182 * so we walk each table with a mask length greater than and equal to
183 * the required root and check it is covered by the root.
185 for (i = root->fp_len;
186 i < ARRAY_LEN (fib->fib_entry_by_dst_address);
189 uword * hash = fib->fib_entry_by_dst_address[i];
196 hash_foreach_pair (p, hash,
199 if (ip4_destination_matches_route(&ip4_main,
204 const fib_prefix_t *sub_tree;
208 * exclude sub-trees the walk does not want to explore
210 vec_foreach(sub_tree, sub_trees)
212 if (ip4_destination_matches_route(&ip4_main,
214 &sub_tree->fp_addr.ip4,
224 switch (fn(p->value[0], ctx))
226 case FIB_TABLE_WALK_CONTINUE:
228 case FIB_TABLE_WALK_SUB_TREE_STOP: {
230 .fp_proto = FIB_PROTOCOL_IP4,
234 vec_add1(sub_trees, pfx);
237 case FIB_TABLE_WALK_STOP: