FD.io VPP  v17.07.01-10-g3be13f0
Vector Packet Processing
ip4_mfib.c
Go to the documentation of this file.
1 /*
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:
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 #include <vnet/mfib/ip4_mfib.h>
17 
18 #include <vnet/mfib/mfib_table.h>
19 #include <vnet/mfib/mfib_entry.h>
20 
21 static const mfib_prefix_t ip4_specials[] = {
22  {
23  /* (*,*)/0 */
24  .fp_src_addr = {
25  .ip4.data_u32 = 0,
26  },
27  .fp_grp_addr = {
28  .ip4.data_u32 = 0,
29  },
30  .fp_len = 0,
31  .fp_proto = FIB_PROTOCOL_IP4,
32  },
33 };
34 
35 static u32
37 {
38  mfib_table_t *mfib_table;
39 
41  memset(mfib_table, 0, sizeof(*mfib_table));
42 
43  mfib_table->mft_proto = FIB_PROTOCOL_IP4;
44  mfib_table->mft_index =
45  mfib_table->v4.index =
46  (mfib_table - ip4_main.mfibs);
47 
49  table_id,
50  mfib_table->mft_index);
51 
52  mfib_table->mft_table_id =
53  mfib_table->v4.table_id =
54  table_id;
55 
57 
58  /*
59  * add the special entries into the new FIB
60  */
61  int ii;
62 
63  for (ii = 0; ii < ARRAY_LEN(ip4_specials); ii++)
64  {
65  mfib_prefix_t prefix = ip4_specials[ii];
66 
67  prefix.fp_src_addr.ip4.data_u32 =
68  clib_host_to_net_u32(prefix.fp_src_addr.ip4.data_u32);
69  prefix.fp_grp_addr.ip4.data_u32 =
70  clib_host_to_net_u32(prefix.fp_grp_addr.ip4.data_u32);
71 
73  &prefix,
77  }
78 
79  return (mfib_table->mft_index);
80 }
81 
82 void
84 {
85  mfib_table_t *mfib_table = (mfib_table_t*)mfib;
86  int ii;
87 
88  /*
89  * remove all the specials we added when the table was created.
90  */
91  for (ii = 0; ii < ARRAY_LEN(ip4_specials); ii++)
92  {
93  fib_node_index_t mfei;
94  mfib_prefix_t prefix = ip4_specials[ii];
95 
96  prefix.fp_src_addr.ip4.data_u32 =
97  clib_host_to_net_u32(prefix.fp_src_addr.ip4.data_u32);
98  prefix.fp_grp_addr.ip4.data_u32 =
99  clib_host_to_net_u32(prefix.fp_grp_addr.ip4.data_u32);
100 
101  mfei = mfib_table_lookup(mfib_table->mft_index, &prefix);
103  }
104 
105  /*
106  * validate no more routes.
107  */
108  ASSERT(0 == mfib_table->mft_total_route_counts);
109  ASSERT(~0 != mfib_table->mft_table_id);
110 
112  pool_put(ip4_main.mfibs, mfib_table);
113 }
114 
115 u32
117 {
118  u32 index;
119 
120  index = ip4_mfib_index_from_table_id(table_id);
121  if (~0 == index)
122  return ip4_create_mfib_with_table_id(table_id);
124 
125  return (index);
126 }
127 
128 u32
130 {
131  if (sw_if_index >= vec_len(ip4_main.mfib_index_by_sw_if_index))
132  {
133  /*
134  * This is the case for interfaces that are not yet mapped to
135  * a IP table
136  */
137  return (~0);
138  }
139  return (ip4_main.mfib_index_by_sw_if_index[sw_if_index]);
140 }
141 
142 #define IPV4_MFIB_GRP_LEN(_len)\
143  (_len > 32 ? 32 : _len)
144 
145 #define IP4_MFIB_MK_KEY(_grp, _src, _len, _key) \
146 { \
147  _key = ((u64)(_grp->data_u32 & \
148  ip4_main.fib_masks[IPV4_MFIB_GRP_LEN(_len)])) << 32; \
149  _key |= _src->data_u32; \
150 }
151 #define IP4_MFIB_MK_GRP_KEY(_grp, _len, _key) \
152 { \
153  _key = ((u64)(_grp->data_u32 & \
154  ip4_main.fib_masks[IPV4_MFIB_GRP_LEN(_len)])) << 32; \
155 }
156 
157 /*
158  * ip4_fib_table_lookup_exact_match
159  *
160  * Exact match prefix lookup
161  */
164  const ip4_address_t *grp,
165  const ip4_address_t *src,
166  u32 len)
167 {
168  uword * hash, * result;
169  u64 key;
170 
171  hash = mfib->fib_entry_by_dst_address[len];
172  IP4_MFIB_MK_KEY(grp, src, len, key);
173 
174  result = hash_get(hash, key);
175 
176  if (NULL != result) {
177  return (result[0]);
178  }
179  return (FIB_NODE_INDEX_INVALID);
180 }
181 
182 /*
183  * ip4_fib_table_lookup
184  *
185  * Longest prefix match
186  */
189  const ip4_address_t *src,
190  const ip4_address_t *grp,
191  u32 len)
192 {
193  uword * hash, * result;
194  i32 mask_len;
195  u64 key;
196 
197  mask_len = len;
198 
199  if (PREDICT_TRUE(64 == mask_len))
200  {
201  hash = mfib->fib_entry_by_dst_address[mask_len];
202  IP4_MFIB_MK_KEY(grp, src, mask_len, key);
203 
204  result = hash_get (hash, key);
205 
206  if (NULL != result) {
207  return (result[0]);
208  }
209  }
210 
211  for (mask_len = 32; mask_len >= 0; mask_len--)
212  {
213  hash = mfib->fib_entry_by_dst_address[mask_len];
214  IP4_MFIB_MK_GRP_KEY(grp, mask_len, key);
215 
216  result = hash_get (hash, key);
217 
218  if (NULL != result) {
219  return (result[0]);
220  }
221  }
222  return (FIB_NODE_INDEX_INVALID);
223 }
224 
225 void
227  const ip4_address_t *grp,
228  const ip4_address_t *src,
229  u32 len,
230  fib_node_index_t fib_entry_index)
231 {
232  uword * hash, * result;
233  u64 key;
234 
235  IP4_MFIB_MK_KEY(grp, src, len, key);
236  hash = mfib->fib_entry_by_dst_address[len];
237  result = hash_get (hash, key);
238 
239  if (NULL == result) {
240  /*
241  * adding a new entry
242  */
243  if (NULL == hash) {
244  hash = hash_create (32 /* elts */, sizeof (uword));
246  }
247  hash = hash_set(hash, key, fib_entry_index);
248  mfib->fib_entry_by_dst_address[len] = hash;
249  }
250  else
251  {
252  ASSERT(0);
253  }
254 }
255 
256 void
258  const ip4_address_t *grp,
259  const ip4_address_t *src,
260  u32 len)
261 {
262  uword * hash, * result;
263  u64 key;
264 
265  IP4_MFIB_MK_KEY(grp, src, len, key);
266  hash = mfib->fib_entry_by_dst_address[len];
267  result = hash_get (hash, key);
268 
269  if (NULL == result)
270  {
271  /*
272  * removing a non-existant entry. i'll allow it.
273  */
274  }
275  else
276  {
277  hash_unset(hash, key);
278  }
279 
280  mfib->fib_entry_by_dst_address[len] = hash;
281 }
282 
283 void
286  void *ctx)
287 {
288  int i;
289 
290  for (i = 0; i < ARRAY_LEN (mfib->fib_entry_by_dst_address); i++)
291  {
292  uword * hash = mfib->fib_entry_by_dst_address[i];
293 
294  if (NULL != hash)
295  {
296  hash_pair_t * p;
297 
298  hash_foreach_pair (p, hash,
299  ({
300  fn(p->value[0], ctx);
301  }));
302  }
303  }
304 }
305 
306 static void
308  vlib_main_t * vm)
309 {
310  fib_node_index_t *mfib_entry_indicies;
311  fib_node_index_t *mfib_entry_index;
312  int i;
313 
314  mfib_entry_indicies = NULL;
315 
316  for (i = 0; i < ARRAY_LEN (mfib->fib_entry_by_dst_address); i++)
317  {
318  uword * hash = mfib->fib_entry_by_dst_address[i];
319 
320  if (NULL != hash)
321  {
322  hash_pair_t * p;
323 
324  hash_foreach_pair (p, hash,
325  ({
326  vec_add1(mfib_entry_indicies, p->value[0]);
327  }));
328  }
329  }
330 
331  vec_sort_with_function(mfib_entry_indicies, mfib_entry_cmp_for_sort);
332 
333  vec_foreach(mfib_entry_index, mfib_entry_indicies)
334  {
335  vlib_cli_output(vm, "%U",
337  *mfib_entry_index,
339  }
340 
341  vec_free(mfib_entry_indicies);
342 }
343 
344 static void
346  vlib_main_t * vm,
347  ip4_address_t *src,
348  ip4_address_t *grp,
349  u32 mask_len)
350 {
351  vlib_cli_output(vm, "%U",
353  ip4_mfib_table_lookup(mfib, src, grp, mask_len),
355 }
356 
357 static clib_error_t *
359  unformat_input_t * input,
360  vlib_cli_command_t * cmd)
361 {
362  ip4_main_t * im4 = &ip4_main;
363  mfib_table_t *mfib_table;
364  int verbose, matching;
365  ip4_address_t grp, src = {{0}};
366  u32 mask = 32;
367  int i, table_id = -1, fib_index = ~0;
368 
369  verbose = 1;
370  matching = 0;
371 
373  {
374  if (unformat (input, "brief") || unformat (input, "summary")
375  || unformat (input, "sum"))
376  verbose = 0;
377 
378  else if (unformat (input, "%U %U",
379  unformat_ip4_address, &src,
380  unformat_ip4_address, &grp))
381  {
382  matching = 1;
383  mask = 64;
384  }
385  else if (unformat (input, "%U/%d", unformat_ip4_address, &grp, &mask))
386  {
387  memset(&src, 0, sizeof(src));
388  matching = 1;
389  }
390  else if (unformat (input, "%U", unformat_ip4_address, &grp))
391  {
392  memset(&src, 0, sizeof(src));
393  matching = 1;
394  mask = 32;
395  }
396  else if (unformat (input, "table %d", &table_id))
397  ;
398  else if (unformat (input, "index %d", &fib_index))
399  ;
400  else
401  break;
402  }
403 
404  pool_foreach (mfib_table, im4->mfibs,
405  ({
406  ip4_mfib_t *mfib = &mfib_table->v4;
407 
408  if (table_id >= 0 && table_id != (int)mfib->table_id)
409  continue;
410  if (fib_index != ~0 && fib_index != (int)mfib->index)
411  continue;
412 
413  vlib_cli_output (vm, "%U, fib_index %d",
414  format_mfib_table_name, mfib->index, FIB_PROTOCOL_IP4,
415  mfib->index);
416 
417  /* Show summary? */
418  if (! verbose)
419  {
420  vlib_cli_output (vm, "%=20s%=16s", "Prefix length", "Count");
421  for (i = 0; i < ARRAY_LEN (mfib->fib_entry_by_dst_address); i++)
422  {
423  uword * hash = mfib->fib_entry_by_dst_address[i];
424  uword n_elts = hash_elts (hash);
425  if (n_elts > 0)
426  vlib_cli_output (vm, "%20d%16d", i, n_elts);
427  }
428  continue;
429  }
430 
431  if (!matching)
432  {
433  ip4_mfib_table_show_all(mfib, vm);
434  }
435  else
436  {
437  ip4_mfib_table_show_one(mfib, vm, &src, &grp, mask);
438  }
439  }));
440 
441  return 0;
442 }
443 
444 /*?
445  * This command displays the IPv4 MulticasrFIB Tables (VRF Tables) and
446  * the route entries for each table.
447  *
448  * @note This command will run for a long time when the FIB tables are
449  * comprised of millions of entries. For those senarios, consider displaying
450  * a single table or summary mode.
451  *
452  * @cliexpar
453  * Example of how to display all the IPv4 Multicast FIB tables:
454  * @cliexstart{show ip fib}
455  * ipv4-VRF:0, fib_index 0
456  * (*, 0.0.0.0/0): flags:D,
457  * Interfaces:
458  * multicast-ip4-chain
459  * [@1]: dpo-drop ip4
460  * (*, 232.1.1.1/32):
461  * Interfaces:
462  * test-eth1: Forward,
463  * test-eth2: Forward,
464  * test-eth0: Accept,
465  * multicast-ip4-chain
466  * [@2]: dpo-replicate: [index:1 buckets:2 to:[0:0]]
467  * [0] [@1]: ipv4-mcast: test-eth1: IP4: d0:d1:d2:d3:d4:01 -> 01:00:05:00:00:00
468  * [1] [@1]: ipv4-mcast: test-eth2: IP4: d0:d1:d2:d3:d4:02 -> 01:00:05:00:00:00
469  *
470  * @cliexend
471  * Example of how to display a summary of all IPv4 FIB tables:
472  * @cliexstart{show ip fib summary}
473  * ipv4-VRF:0, fib_index 0, flow hash: src dst sport dport proto
474  * Prefix length Count
475  * 0 1
476  * 8 2
477  * 32 4
478  * ipv4-VRF:7, fib_index 1, flow hash: src dst sport dport proto
479  * Prefix length Count
480  * 0 1
481  * 8 2
482  * 24 2
483  * 32 4
484  * @cliexend
485  ?*/
486 /* *INDENT-OFF* */
487 VLIB_CLI_COMMAND (ip4_show_mfib_command, static) = {
488  .path = "show ip mfib",
489  .short_help = "show ip mfib [summary] [table <table-id>] [index <fib-id>] [<grp-addr>[/<mask>]] [<grp-addr>] [<src-addr> <grp-addr>]",
490  .function = ip4_show_mfib,
491 };
492 /* *INDENT-ON* */
#define MFIB_ENTRY_FORMAT_DETAIL
Definition: mfib_entry.h:88
static clib_error_t * ip4_show_mfib(vlib_main_t *vm, unformat_input_t *input, vlib_cli_command_t *cmd)
Definition: ip4_mfib.c:358
ip46_address_t fp_src_addr
Definition: mfib_types.h:47
#define hash_set(h, key, value)
Definition: hash.h:254
fib_node_index_t mfib_table_lookup(u32 fib_index, const mfib_prefix_t *prefix)
Perfom a longest prefix match in the non-forwarding table.
Definition: mfib_table.c:65
sll srl srl sll sra u16x4 i
Definition: vector_sse2.h:337
#define hash_unset(h, key)
Definition: hash.h:260
u32 index
Definition: ip4.h:56
u32 ip4_mfib_table_find_or_create_and_lock(u32 table_id)
Get or create an IPv4 fib.
Definition: ip4_mfib.c:116
#define PREDICT_TRUE(x)
Definition: clib.h:98
u32 ip4_mfib_table_get_index_for_sw_if_index(u32 sw_if_index)
Definition: ip4_mfib.c:129
#define NULL
Definition: clib.h:55
#define vec_add1(V, E)
Add 1 element to end of vector (unspecified alignment).
Definition: vec.h:522
static void ip4_mfib_table_show_one(ip4_mfib_t *mfib, vlib_main_t *vm, ip4_address_t *src, ip4_address_t *grp, u32 mask_len)
Definition: ip4_mfib.c:345
u32 mft_total_route_counts
Total route counters.
Definition: mfib_table.h:65
fib_node_index_t mfib_table_entry_update(u32 fib_index, const mfib_prefix_t *prefix, mfib_source_t source, fib_rpf_id_t rpf_id, mfib_entry_flags_t entry_flags)
Add a new (with no replication) or lock an existing entry.
Definition: mfib_table.c:165
#define MFIB_ENTRY_FORMAT_BRIEF
Definition: mfib_entry.h:87
uword value[0]
Definition: hash.h:164
u32 * mfib_index_by_sw_if_index
Table index indexed by software interface.
Definition: ip4.h:102
#define pool_foreach(VAR, POOL, BODY)
Iterate through pool.
Definition: pool.h:376
unformat_function_t unformat_ip4_address
Definition: format.h:76
#define MFIB_RPF_ID_NONE
Definition: fib_types.h:317
fib_node_index_t mft_index
Index into FIB vector.
Definition: mfib_table.h:60
void mfib_table_entry_delete_index(fib_node_index_t mfib_entry_index, mfib_source_t source)
Delete a FIB entry.
Definition: mfib_table.c:380
#define IP4_MFIB_MK_GRP_KEY(_grp, _len, _key)
Definition: ip4_mfib.c:151
int i32
Definition: types.h:81
unsigned long u64
Definition: types.h:89
static void hash_set_flags(void *v, uword flags)
Definition: hash.h:152
struct mfib_table_t_ * mfibs
Vector of MFIBs.
Definition: ip4.h:94
void ip4_mfib_table_walk(ip4_mfib_t *mfib, mfib_table_walk_fn_t fn, void *ctx)
Walk the IP4 mfib table.
Definition: ip4_mfib.c:284
#define hash_get(h, key)
Definition: hash.h:248
void ip4_mfib_table_entry_remove(ip4_mfib_t *mfib, const ip4_address_t *grp, const ip4_address_t *src, u32 len)
Definition: ip4_mfib.c:257
struct _unformat_input_t unformat_input_t
#define IP4_MFIB_MK_KEY(_grp, _src, _len, _key)
Definition: ip4_mfib.c:145
#define pool_put(P, E)
Free an object E in pool P.
Definition: pool.h:241
Definition: ip4.h:47
int mfib_entry_cmp_for_sort(void *i1, void *i2)
Definition: mfib_entry.c:1058
#define pool_get_aligned(P, E, A)
Allocate an object E from a pool P (general version).
Definition: pool.h:169
#define UNFORMAT_END_OF_INPUT
Definition: format.h:143
fib_node_index_t ip4_mfib_table_lookup_exact_match(const ip4_mfib_t *mfib, const ip4_address_t *grp, const ip4_address_t *src, u32 len)
Definition: ip4_mfib.c:163
u8 * format_mfib_entry(u8 *s, va_list *args)
Definition: mfib_entry.c:171
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:340
u32 fib_node_index_t
A typedef of a node index.
Definition: fib_types.h:28
#define ARRAY_LEN(x)
Definition: clib.h:59
Aggregrate type for a prefix.
Definition: mfib_types.h:24
#define VLIB_CLI_COMMAND(x,...)
Definition: cli.h:154
uword * fib_entry_by_dst_address[65]
Definition: ip4.h:50
#define hash_create(elts, value_bytes)
Definition: hash.h:658
#define ASSERT(truth)
unsigned int u32
Definition: types.h:88
IPv4 main type.
Definition: ip4.h:83
fib_node_index_t ip4_mfib_table_lookup(const ip4_mfib_t *mfib, const ip4_address_t *src, const ip4_address_t *grp, u32 len)
The IPv4 Multicast-FIB.
Definition: ip4_mfib.c:188
void ip4_mfib_table_entry_insert(ip4_mfib_t *mfib, const ip4_address_t *grp, const ip4_address_t *src, u32 len, fib_node_index_t fib_entry_index)
Definition: ip4_mfib.c:226
fib_protocol_t mft_proto
Which protocol this table serves.
Definition: mfib_table.h:45
u32 mft_table_id
Table ID (hash key) for this FIB.
Definition: mfib_table.h:55
static u32 ip4_create_mfib_with_table_id(u32 table_id)
Definition: ip4_mfib.c:36
u64 uword
Definition: types.h:112
static void ip4_mfib_table_show_all(ip4_mfib_t *mfib, vlib_main_t *vm)
Definition: ip4_mfib.c:307
#define FIB_NODE_INDEX_INVALID
Definition: fib_types.h:29
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
#define hash_foreach_pair(p, v, body)
Iterate over hash pairs.
Definition: hash.h:349
#define vec_sort_with_function(vec, f)
Sort a vector using the supplied element comparison function.
Definition: vec.h:960
void mfib_table_lock(u32 fib_index, fib_protocol_t proto)
Release a reference counting lock on the table.
Definition: mfib_table.c:489
int(* mfib_table_walk_fn_t)(fib_node_index_t fei, void *ctx)
Call back function when walking entries in a FIB table.
Definition: mfib_table.h:367
ip4_mfib_t v4
Definition: mfib_table.h:38
A protocol Independent IP multicast FIB table.
Definition: mfib_table.h:29
ip4_main_t ip4_main
Global ip4 main structure.
Definition: ip4_forward.c:1168
#define vec_foreach(var, vec)
Vector iterator.
u32 table_id
Definition: ip4.h:53
uword * mfib_index_by_table_id
Hash table mapping table id to multicast fib index.
Definition: ip4.h:113
#define CLIB_CACHE_LINE_BYTES
Definition: cache.h:67
static u32 ip4_mfib_index_from_table_id(u32 table_id)
Definition: ip4_mfib.h:79
#define HASH_FLAG_NO_AUTO_SHRINK
Definition: hash.h:64
void vlib_cli_output(vlib_main_t *vm, char *fmt,...)
Definition: cli.c:680
void ip4_mfib_table_destroy(ip4_mfib_t *mfib)
Definition: ip4_mfib.c:83
uword unformat(unformat_input_t *i, const char *fmt,...)
Definition: unformat.c:972
ip46_address_t fp_grp_addr
The address type is not deriveable from the fp_addr member.
Definition: mfib_types.h:46
static uword unformat_check_input(unformat_input_t *i)
Definition: format.h:169