FD.io VPP  v20.09-64-g4f7b92f0a
Vector Packet Processing
mpls_fib.c
Go to the documentation of this file.
1 /*
2  * mpls_fib.h: The Label/MPLS FIB
3  *
4  * Copyright (c) 2012 Cisco and/or its affiliates.
5  * Licensed under the Apache License, Version 2.0 (the "License");
6  * you may not use this file except in compliance with the License.
7  * You may obtain a copy of the License at:
8  *
9  * http://www.apache.org/licenses/LICENSE-2.0
10  *
11  * Unless required by applicable law or agreed to in writing, software
12  * distributed under the License is distributed on an "AS IS" BASIS,
13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  * See the License for the specific language governing permissions and
15  * limitations under the License.
16  */
17 /**
18  * An MPLS_FIB table;
19  *
20  * The entries in the table are programmed wtih one or more MOIs. These MOIs
21  * may result in different forwarding actions for end-of-stack (EOS) and non-EOS
22  * packets. Whether the two actions are the same more often than they are
23  * different, or vice versa, is a function of the deployment in which the router
24  * is used and thus not predictable.
25  * The desgin choice to make with an MPLS_FIB table is:
26  * 1 - 20 bit key: label only.
27  * When the EOS and non-EOS actions differ the result is a 'EOS-choice' object.
28  * 2 - 21 bit key: label and EOS-bit.
29  * The result is then the specific action based on EOS-bit.
30  *
31  * 20 bit key:
32  * Advantages:
33  * - lower memory overhead, since there are few DB entries.
34  * Disadvantages:
35  * - slower DP performance in the case the chains differ, as more objects are
36  * encounterd in the switch path
37  *
38  * 21 bit key:
39  * Advantages:
40  * - faster DP performance
41  * Disadvantages
42  * - increased memory footprint.
43  *
44  * Switching between schemes based on observed/measured action similarity is not
45  * considered on the grounds of complexity and flip-flopping.
46  *
47  * VPP mantra - favour performance over memory. We choose a 21 bit key.
48  */
49 
50 #include <vnet/fib/fib_table.h>
51 #include <vnet/fib/mpls_fib.h>
52 #include <vnet/dpo/load_balance.h>
53 #include <vnet/dpo/drop_dpo.h>
54 #include <vnet/dpo/punt_dpo.h>
55 #include <vnet/dpo/lookup_dpo.h>
56 #include <vnet/mpls/mpls.h>
57 
58 /**
59  * All lookups in an MPLS_FIB table must result in a DPO of type load-balance.
60  * This is the default result which links to drop
61  */
63 
64 static inline u32
66  mpls_eos_bit_t eos)
67 {
68  ASSERT(eos <= 1);
69  return (label << 1 | eos);
70 }
71 
72 u32
74 {
75  mpls_main_t *mm = &mpls_main;
76  uword * p;
77 
78  p = hash_get (mm->fib_index_by_table_id, table_id);
79  if (!p)
81 
82  return p[0];
83 }
84 
85 static u32
88 {
89  dpo_id_t dpo = DPO_INVALID;
90  fib_table_t *fib_table;
91  mpls_eos_bit_t eos;
92  mpls_fib_t *mf;
93  int i;
94 
95  pool_get(mpls_main.fibs, fib_table);
97 
98  ASSERT((fib_table - mpls_main.fibs) ==
99  (mf - mpls_main.mpls_fibs));
100 
101  clib_memset(fib_table, 0, sizeof(*fib_table));
102 
103  fib_table->ft_proto = FIB_PROTOCOL_MPLS;
104  fib_table->ft_index = (fib_table - mpls_main.fibs);
105 
106  hash_set (mpls_main.fib_index_by_table_id, table_id, fib_table->ft_index);
107 
108  fib_table->ft_table_id = table_id;
110 
111  fib_table_lock(fib_table->ft_index, FIB_PROTOCOL_MPLS, src);
112 
114  {
117  0,
119  }
120 
121  mf->mf_entries = hash_create(0, sizeof(fib_node_index_t));
122  for (i = 0; i < MPLS_FIB_DB_SIZE; i++)
123  {
124  /*
125  * initialise each DPO in the data-path lookup table
126  * to be the special MPLS drop
127  */
129  }
130 
131  /*
132  * non-default forwarding for the special labels.
133  */
134  fib_prefix_t prefix = {
135  .fp_proto = FIB_PROTOCOL_MPLS,
136  .fp_payload_proto = DPO_PROTO_MPLS,
137  };
138 
139  /*
140  * PUNT the router alert, both EOS and non-eos
141  */
144  {
145  prefix.fp_eos = eos;
147  &prefix,
151  }
152 
153  /*
154  * IPv4 explicit NULL EOS lookup in the interface's IPv4 table
155  */
158  prefix.fp_eos = MPLS_EOS;
159 
165  &dpo);
167  &prefix,
170  &dpo);
171 
173  prefix.fp_eos = MPLS_NON_EOS;
174 
180  &dpo);
182  &prefix,
185  &dpo);
186 
187  /*
188  * IPv6 explicit NULL EOS lookup in the interface's IPv6 table
189  */
192  prefix.fp_eos = MPLS_EOS;
193 
199  &dpo);
201  &prefix,
204  &dpo);
205 
207  prefix.fp_eos = MPLS_NON_EOS;
213  &dpo);
215  &prefix,
218  &dpo);
219 
220  return (fib_table->ft_index);
221 }
222 
223 u32
226 {
227  u32 index;
228 
229  index = mpls_fib_index_from_table_id(table_id);
230  if (~0 == index)
231  return mpls_fib_create_with_table_id(table_id, src);
232 
233  fib_table_lock(index, FIB_PROTOCOL_MPLS, src);
234 
235  return (index);
236 }
237 u32
239 {
240  return (mpls_fib_create_with_table_id(~0, src));
241 }
242 
243 void
245 {
246  fib_table_t *fib_table = pool_elt_at_index(mpls_main.fibs, fib_index);
248  fib_prefix_t prefix = {
249  .fp_proto = FIB_PROTOCOL_MPLS,
250  };
251  mpls_label_t special_labels[] = {
255  };
256  mpls_eos_bit_t eos;
257  u32 ii;
258 
259  for (ii = 0; ii < ARRAY_LEN(special_labels); ii++)
260  {
262  {
263  prefix.fp_label = special_labels[ii];
264  prefix.fp_eos = eos;
265 
266  fib_table_entry_delete(fib_table->ft_index,
267  &prefix,
269  }
270  }
271  if (~0 != fib_table->ft_table_id)
272  {
274  fib_table->ft_table_id);
275  }
276  hash_free(mf->mf_entries);
277 
278  vec_free(fib_table->ft_src_route_counts);
280  pool_put(mpls_main.fibs, fib_table);
281 }
282 
286  mpls_eos_bit_t eos)
287 {
288  uword *p;
289 
290  p = hash_get(mf->mf_entries, mpls_fib_entry_mk_key(label, eos));
291 
292  if (NULL == p)
293  return FIB_NODE_INDEX_INVALID;
294 
295  return p[0];
296 }
297 
298 void
301  mpls_eos_bit_t eos,
302  fib_node_index_t lfei)
303 {
304  hash_set(mf->mf_entries, mpls_fib_entry_mk_key(label, eos), lfei);
305 }
306 
307 void
310  mpls_eos_bit_t eos)
311 {
312  hash_unset(mf->mf_entries, mpls_fib_entry_mk_key(label, eos));
313 }
314 
315 void
318  mpls_eos_bit_t eos,
319  const dpo_id_t *dpo)
320 {
322 
323  ASSERT((DPO_LOAD_BALANCE == dpo->dpoi_type) ||
324  (DPO_REPLICATE == dpo->dpoi_type));
325  if (CLIB_DEBUG > 0)
326  {
327  if (DPO_REPLICATE == dpo->dpoi_type)
329  if (DPO_LOAD_BALANCE == dpo->dpoi_type)
331  }
332  key = mpls_fib_entry_mk_key(label, eos);
333 
334  mf->mf_lbs[key] = dpo->dpoi_index;
335 }
336 
337 void
340  mpls_eos_bit_t eos)
341 {
343 
344  key = mpls_fib_entry_mk_key(label, eos);
345 
347 }
348 
349 void
352  void *ctx)
353 {
354  fib_node_index_t lfei;
356 
357  hash_foreach(key, lfei, mpls_fib->mf_entries,
358  ({
359  fn(lfei, ctx);
360  }));
361 }
362 
363 u8 *
364 format_mpls_fib_table_memory (u8 * s, va_list * args)
365 {
366  u64 n_tables, mem;
367 
368  n_tables = pool_elts(mpls_main.fibs);
369  mem = n_tables * sizeof(mpls_fib_t);
370  s = format(s, "%=30s %=6ld %=12ld\n", "MPLS", n_tables, mem);
371 
372  return (s);
373 }
374 
375 static void
377  vlib_main_t * vm)
378 {
379  fib_node_index_t lfei, *lfeip, *lfeis = NULL;
381 
382  hash_foreach(key, lfei, mpls_fib->mf_entries,
383  ({
384  vec_add1(lfeis, lfei);
385  }));
386 
388 
389  vec_foreach(lfeip, lfeis)
390  {
391  vlib_cli_output (vm, "%U",
392  format_fib_entry, *lfeip,
394  }
395  vec_free(lfeis);
396 }
397 
398 static void
401  vlib_main_t * vm)
402 {
403  fib_node_index_t lfei;
404  mpls_eos_bit_t eos;
405 
407  {
408  lfei = mpls_fib_table_lookup(mpls_fib, label, eos);
409 
410  if (FIB_NODE_INDEX_INVALID != lfei)
411  {
412  vlib_cli_output (vm, "%U",
414  }
415  }
416 }
417 
418 static clib_error_t *
420  unformat_input_t * input,
421  vlib_cli_command_t * cmd)
422 {
423  fib_table_t * fib_table;
425  int table_id;
426 
427  table_id = -1;
428  label = MPLS_LABEL_INVALID;
429 
431  {
432  /* if (unformat (input, "brief") || unformat (input, "summary") */
433  /* || unformat (input, "sum")) */
434  /* verbose = 0; */
435 
436  if (unformat (input, "%d", &label))
437  continue;
438  else if (unformat (input, "table %d", &table_id))
439  ;
440  else
441  break;
442  }
443 
444  pool_foreach (fib_table, mpls_main.fibs,
445  ({
446  fib_source_t source;
447  u8 *s = NULL;
448 
449  if (table_id >= 0 && table_id != fib_table->ft_table_id)
450  continue;
451 
452  s = format (s, "%v, fib_index:%d locks:[",
453  fib_table->ft_desc, mpls_main.fibs - fib_table);
454  vec_foreach_index(source, fib_table->ft_locks)
455  {
456  if (0 != fib_table->ft_locks[source])
457  {
458  s = format(s, "%U:%d, ",
459  format_fib_source, source,
460  fib_table->ft_locks[source]);
461  }
462  }
463  vlib_cli_output (vm, "%v]", s);
464 
465  if (MPLS_LABEL_INVALID == label)
466  {
468  }
469  else
470  {
471  mpls_fib_table_show_one(mpls_fib_get(fib_table->ft_index), label, vm);
472  }
473  }));
474 
475  return 0;
476 }
477 
478 VLIB_CLI_COMMAND (mpls_fib_show_command, static) = {
479  .path = "show mpls fib",
480  .short_help = "show mpls fib [summary] [table <n>]",
481  .function = mpls_fib_show,
482 };
static void mpls_fib_table_show_all(const mpls_fib_t *mpls_fib, vlib_main_t *vm)
Definition: mpls_fib.c:376
u8 * format_fib_entry(u8 *s, va_list *args)
Definition: fib_entry.c:130
enum fib_source_t_ fib_source_t
The different sources that can create a route.
void mpls_fib_table_entry_remove(mpls_fib_t *mf, mpls_label_t label, mpls_eos_bit_t eos)
Definition: mpls_fib.c:308
#define hash_set(h, key, value)
Definition: hash.h:255
fib_protocol_t ft_proto
Which protocol this table serves.
Definition: fib_table.h:76
#define hash_unset(h, key)
Definition: hash.h:261
fib_node_index_t mpls_fib_table_lookup(const mpls_fib_t *mf, mpls_label_t label, mpls_eos_bit_t eos)
Definition: mpls_fib.c:284
void mpls_fib_table_destroy(u32 fib_index)
Definition: mpls_fib.c:244
#define FIB_ENTRY_FORMAT_DETAIL
Definition: fib_entry.h:360
unsigned long u64
Definition: types.h:89
static clib_error_t * mpls_fib_show(vlib_main_t *vm, unformat_input_t *input, vlib_cli_command_t *cmd)
Definition: mpls_fib.c:419
clib_memset(h->entries, 0, sizeof(h->entries[0]) *entries)
static index_t mpls_fib_drop_dpo_index
An MPLS_FIB table;.
Definition: mpls_fib.c:62
u32 mpls_label_t
A label value only, i.e.
Definition: packet.h:26
u32 index_t
A Data-Path Object is an object that represents actions that are applied to packets are they are swit...
Definition: dpo.h:41
#define MPLS_IETF_ROUTER_ALERT_LABEL
Definition: mpls_types.h:28
vl_api_address_t src
Definition: gre.api:54
vlib_main_t * vm
Definition: in2out_ed.c:1582
u8 * format(u8 *s, const char *fmt,...)
Definition: format.c:424
vl_api_prefix_t prefix
Definition: ip.api:144
#define pool_get(P, E)
Allocate an object E from a pool P (unspecified alignment).
Definition: pool.h:252
unsigned char u8
Definition: types.h:56
void mpls_fib_table_entry_insert(mpls_fib_t *mf, mpls_label_t label, mpls_eos_bit_t eos, fib_node_index_t lfei)
Definition: mpls_fib.c:299
index_t load_balance_create(u32 n_buckets, dpo_proto_t lb_proto, flow_hash_config_t fhc)
Definition: load_balance.c:263
const dpo_id_t * drop_dpo_get(dpo_proto_t proto)
Definition: drop_dpo.c:25
dpo_proto_t fp_payload_proto
This protocol determines the payload protocol of packets that will be forwarded by this entry once th...
Definition: fib_types.h:236
static u32 mpls_fib_entry_mk_key(mpls_label_t label, mpls_eos_bit_t eos)
Definition: mpls_fib.c:65
#define pool_foreach(VAR, POOL, BODY)
Iterate through pool.
Definition: pool.h:513
#define MPLS_FIB_DB_SIZE
Definition: mpls_fib.h:34
#define hash_foreach(key_var, value_var, h, body)
Definition: hash.h:442
#define MPLS_IS_REPLICATE
The top bit of the index, which is the result of the MPLS lookup is used to determine if the DPO is a...
Definition: mpls_types.h:66
Aggregate type for a prefix.
Definition: fib_types.h:203
const dpo_id_t * punt_dpo_get(dpo_proto_t proto)
Definition: punt_dpo.c:25
unsigned int u32
Definition: types.h:88
int fib_entry_cmp_for_sort(void *i1, void *i2)
Definition: fib_entry.c:1623
The identity of a DPO is a combination of its type and its instance number/index of objects of that t...
Definition: dpo.h:170
#define hash_get(h, key)
Definition: hash.h:249
Definition: fib_entry.h:116
#define pool_elt_at_index(p, i)
Returns pointer to element at given index.
Definition: pool.h:534
u32 mpls_fib_table_find_or_create_and_lock(u32 table_id, fib_source_t src)
Definition: mpls_fib.c:224
void mpls_fib_table_walk(mpls_fib_t *mpls_fib, fib_table_walk_fn_t fn, void *ctx)
Walk all entries in a FIB table N.B: This is NOT safe to deletes.
Definition: mpls_fib.c:350
dpo_type_t dpoi_type
the type
Definition: dpo.h:174
long ctx[MAX_CONNS]
Definition: main.c:144
struct _unformat_input_t unformat_input_t
load-balancing over a choice of [un]equal cost paths
Definition: dpo.h:102
#define MPLS_FLOW_HASH_DEFAULT
There are no options for controlling the MPLS flow hash.
Definition: mpls_fib.h:39
#define hash_free(h)
Definition: hash.h:310
struct mpls_fib_t_ mpls_fib_t
#define pool_put(P, E)
Free an object E in pool P.
Definition: pool.h:302
u32 label
Definition: fib_types.api:25
void lookup_dpo_add_or_lock_w_fib_index(fib_node_index_t fib_index, dpo_proto_t proto, lookup_cast_t cast, lookup_input_t input, lookup_table_t table_config, dpo_id_t *dpo)
Definition: lookup_dpo.c:137
static void mpls_fib_table_show_one(const mpls_fib_t *mpls_fib, mpls_label_t label, vlib_main_t *vm)
Definition: mpls_fib.c:399
struct fib_table_t_ * fibs
A pool of all the MPLS FIBs.
Definition: mpls.h:47
#define pool_get_aligned(P, E, A)
Allocate an object E from a pool P with alignment A.
Definition: pool.h:246
fib_node_index_t ft_index
Index into FIB vector.
Definition: fib_table.h:97
#define UNFORMAT_END_OF_INPUT
Definition: format.h:145
mpls_main_t mpls_main
Definition: mpls.c:25
u32 ft_table_id
Table ID (hash key) for this FIB.
Definition: fib_table.h:92
u32 ft_flow_hash_config
flow hash configuration
Definition: fib_table.h:102
sll srl srl sll sra u16x4 i
Definition: vector_sse42.h:317
#define MPLS_LABEL_INVALID
Definition: mpls_types.h:48
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:380
void fib_table_entry_delete(u32 fib_index, const fib_prefix_t *prefix, fib_source_t source)
Delete a FIB entry.
Definition: fib_table.c:886
#define MPLS_IETF_IPV4_EXPLICIT_NULL_LABEL
Definition: mpls_types.h:27
u32 fib_node_index_t
A typedef of a node index.
Definition: fib_types.h:30
#define ARRAY_LEN(x)
Definition: clib.h:67
u32 mpls_fib_index_from_table_id(u32 table_id)
Definition: mpls_fib.c:73
fib_table_walk_rc_t(* fib_table_walk_fn_t)(fib_node_index_t fei, void *ctx)
Call back function when walking entries in a FIB table.
Definition: fib_table.h:930
void fib_table_lock(u32 fib_index, fib_protocol_t proto, fib_source_t source)
Release a reference counting lock on the table.
Definition: fib_table.c:1310
mpls_label_t fp_label
Definition: fib_types.h:229
#define VLIB_CLI_COMMAND(x,...)
Definition: cli.h:158
fib_node_index_t fib_table_entry_special_dpo_add(u32 fib_index, const fib_prefix_t *prefix, fib_source_t source, fib_entry_flag_t flags, const dpo_id_t *dpo)
Add a &#39;special&#39; entry to the FIB that links to the DPO passed A special entry is an entry that the FI...
Definition: fib_table.c:324
#define FOR_EACH_MPLS_EOS_BIT(_eos)
Definition: packet.h:73
#define hash_create(elts, value_bytes)
Definition: hash.h:696
#define ASSERT(truth)
void mpls_fib_forwarding_table_reset(mpls_fib_t *mf, mpls_label_t label, mpls_eos_bit_t eos)
Definition: mpls_fib.c:338
uword * mf_entries
A hash table of entries.
Definition: mpls_fib.h:52
void vlib_cli_output(vlib_main_t *vm, char *fmt,...)
Definition: cli.c:696
static mpls_fib_t * mpls_fib_get(fib_node_index_t index)
Definition: mpls_fib.h:62
void mpls_fib_forwarding_table_update(mpls_fib_t *mf, mpls_label_t label, mpls_eos_bit_t eos, const dpo_id_t *dpo)
Definition: mpls_fib.c:316
void load_balance_set_bucket(index_t lbi, u32 bucket, const dpo_id_t *next)
Definition: load_balance.c:280
typedef key
Definition: ipsec_types.api:85
index_t dpoi_index
the index of objects of that type
Definition: dpo.h:186
#define FIB_NODE_INDEX_INVALID
Definition: fib_types.h:31
#define INDEX_INVALID
Invalid index - used when no index is known blazoned capitals INVALID speak volumes where ~0 does not...
Definition: dpo.h:47
u64 uword
Definition: types.h:112
#define vec_sort_with_function(vec, f)
Sort a vector using the supplied element comparison function.
Definition: vec.h:1055
u32 table_id
Definition: wireguard.api:100
#define DPO_INVALID
An initialiser for DPOs declared on the stack.
Definition: dpo.h:197
u32 index
Definition: flow_types.api:221
#define MPLS_IETF_IPV6_EXPLICIT_NULL_LABEL
Definition: mpls_types.h:29
u32 * ft_src_route_counts
Per-source route counters.
Definition: fib_table.h:107
void * mem
u8 * format_mpls_fib_table_memory(u8 *s, va_list *args)
Definition: mpls_fib.c:364
#define vec_foreach(var, vec)
Vector iterator.
Special sources.
Definition: fib_source.h:42
#define CLIB_CACHE_LINE_BYTES
Definition: cache.h:59
u32 mpls_fib_table_create_and_lock(fib_source_t src)
Definition: mpls_fib.c:238
index_t mf_lbs[MPLS_FIB_DB_SIZE]
The load-balance indices keyed by 21 bit label+eos bit.
Definition: mpls_fib.h:58
uword * fib_index_by_table_id
A hash table to lookup the mpls_fib by table ID.
Definition: mpls.h:53
static u32 mpls_fib_create_with_table_id(u32 table_id, fib_source_t src)
Definition: mpls_fib.c:86
struct mpls_fib_t_ * mpls_fibs
A pool of all the MPLS FIBs.
Definition: mpls.h:50
uword unformat(unformat_input_t *i, const char *fmt,...)
Definition: unformat.c:978
static uword unformat_check_input(unformat_input_t *i)
Definition: format.h:171
A protocol Independent FIB table.
Definition: fib_table.h:71
mpls_eos_bit_t fp_eos
Definition: fib_types.h:230
enum mpls_eos_bit_t_ mpls_eos_bit_t
static uword pool_elts(void *v)
Number of active elements in a pool.
Definition: pool.h:128