FD.io VPP  v19.08-27-gf4dcae4
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 
279  pool_put(mpls_main.fibs, fib_table);
280 }
281 
285  mpls_eos_bit_t eos)
286 {
287  uword *p;
288 
289  p = hash_get(mf->mf_entries, mpls_fib_entry_mk_key(label, eos));
290 
291  if (NULL == p)
292  return FIB_NODE_INDEX_INVALID;
293 
294  return p[0];
295 }
296 
297 void
300  mpls_eos_bit_t eos,
301  fib_node_index_t lfei)
302 {
303  hash_set(mf->mf_entries, mpls_fib_entry_mk_key(label, eos), lfei);
304 }
305 
306 void
309  mpls_eos_bit_t eos)
310 {
311  hash_unset(mf->mf_entries, mpls_fib_entry_mk_key(label, eos));
312 }
313 
314 void
317  mpls_eos_bit_t eos,
318  const dpo_id_t *dpo)
319 {
321 
322  ASSERT((DPO_LOAD_BALANCE == dpo->dpoi_type) ||
323  (DPO_REPLICATE == dpo->dpoi_type));
324  if (CLIB_DEBUG > 0)
325  {
326  if (DPO_REPLICATE == dpo->dpoi_type)
328  if (DPO_LOAD_BALANCE == dpo->dpoi_type)
330  }
331  key = mpls_fib_entry_mk_key(label, eos);
332 
333  mf->mf_lbs[key] = dpo->dpoi_index;
334 }
335 
336 void
339  mpls_eos_bit_t eos)
340 {
342 
343  key = mpls_fib_entry_mk_key(label, eos);
344 
346 }
347 
348 void
351  void *ctx)
352 {
353  fib_node_index_t lfei;
355 
356  hash_foreach(key, lfei, mpls_fib->mf_entries,
357  ({
358  fn(lfei, ctx);
359  }));
360 }
361 
362 u8 *
363 format_mpls_fib_table_memory (u8 * s, va_list * args)
364 {
365  u64 n_tables, mem;
366 
367  n_tables = pool_elts(mpls_main.fibs);
368  mem = n_tables * sizeof(mpls_fib_t);
369  s = format(s, "%=30s %=6ld %=12ld\n", "MPLS", n_tables, mem);
370 
371  return (s);
372 }
373 
374 static void
376  vlib_main_t * vm)
377 {
378  fib_node_index_t lfei, *lfeip, *lfeis = NULL;
380 
381  hash_foreach(key, lfei, mpls_fib->mf_entries,
382  ({
383  vec_add1(lfeis, lfei);
384  }));
385 
387 
388  vec_foreach(lfeip, lfeis)
389  {
390  vlib_cli_output (vm, "%U",
391  format_fib_entry, *lfeip,
393  }
394  vec_free(lfeis);
395 }
396 
397 static void
400  vlib_main_t * vm)
401 {
402  fib_node_index_t lfei;
403  mpls_eos_bit_t eos;
404 
406  {
407  lfei = mpls_fib_table_lookup(mpls_fib, label, eos);
408 
409  if (FIB_NODE_INDEX_INVALID != lfei)
410  {
411  vlib_cli_output (vm, "%U",
413  }
414  }
415 }
416 
417 static clib_error_t *
419  unformat_input_t * input,
420  vlib_cli_command_t * cmd)
421 {
422  fib_table_t * fib_table;
424  int table_id;
425 
426  table_id = -1;
427  label = MPLS_LABEL_INVALID;
428 
430  {
431  /* if (unformat (input, "brief") || unformat (input, "summary") */
432  /* || unformat (input, "sum")) */
433  /* verbose = 0; */
434 
435  if (unformat (input, "%d", &label))
436  continue;
437  else if (unformat (input, "table %d", &table_id))
438  ;
439  else
440  break;
441  }
442 
443  pool_foreach (fib_table, mpls_main.fibs,
444  ({
445  fib_source_t source;
446  u8 *s = NULL;
447 
448  if (table_id >= 0 && table_id != fib_table->ft_table_id)
449  continue;
450 
451  s = format (s, "%v, fib_index:%d locks:[",
452  fib_table->ft_desc, mpls_main.fibs - fib_table);
453  FOR_EACH_FIB_SOURCE(source)
454  {
455  if (0 != fib_table->ft_locks[source])
456  {
457  s = format(s, "%U:%d, ",
458  format_fib_source, source,
459  fib_table->ft_locks[source]);
460  }
461  }
462  vlib_cli_output (vm, "%v]", s);
463 
464  if (MPLS_LABEL_INVALID == label)
465  {
467  }
468  else
469  {
470  mpls_fib_table_show_one(mpls_fib_get(fib_table->ft_index), label, vm);
471  }
472  }));
473 
474  return 0;
475 }
476 
477 VLIB_CLI_COMMAND (mpls_fib_show_command, static) = {
478  .path = "show mpls fib",
479  .short_help = "show mpls fib [summary] [table <n>]",
480  .function = mpls_fib_show,
481 };
static void mpls_fib_table_show_all(const mpls_fib_t *mpls_fib, vlib_main_t *vm)
Definition: mpls_fib.c:375
u8 * format_fib_entry(u8 *s, va_list *args)
Definition: fib_entry.c:141
void mpls_fib_table_entry_remove(mpls_fib_t *mf, mpls_label_t label, mpls_eos_bit_t eos)
Definition: mpls_fib.c:307
#define hash_set(h, key, value)
Definition: hash.h:255
fib_protocol_t ft_proto
Which protocol this table serves.
Definition: fib_table.h:74
#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:283
void mpls_fib_table_destroy(u32 fib_index)
Definition: mpls_fib.c:244
#define FIB_ENTRY_FORMAT_DETAIL
Definition: fib_entry.h:523
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:418
#define NULL
Definition: clib.h:58
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:51
int i
clib_memset(h->entries, 0, sizeof(h->entries[0])*entries)
u8 * format(u8 *s, const char *fmt,...)
Definition: format.c:424
vl_api_mprefix_t prefix
Definition: ip.api:456
#define pool_get(P, E)
Allocate an object E from a pool P (unspecified alignment).
Definition: pool.h:236
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:298
index_t load_balance_create(u32 n_buckets, dpo_proto_t lb_proto, flow_hash_config_t fhc)
Definition: load_balance.c:239
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:493
#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
Aggregrate 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:1613
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:285
#define pool_elt_at_index(p, i)
Returns pointer to element at given index.
Definition: pool.h:514
enum fib_source_t_ fib_source_t
The different sources that can create a route.
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:349
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:286
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:133
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:398
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:230
fib_node_index_t ft_index
Index into FIB vector.
Definition: fib_table.h:94
#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:89
vlib_main_t * vm
Definition: buffer.c:312
u32 ft_flow_hash_config
flow hash configuration
Definition: fib_table.h:99
#define MPLS_LABEL_INVALID
Definition: mpls_types.h:48
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:341
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:864
#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:62
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:882
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:1268
mpls_label_t fp_label
Definition: fib_types.h:229
#define VLIB_CLI_COMMAND(x,...)
Definition: cli.h:155
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:307
#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:337
uword * mf_entries
A hash table of entries.
Definition: mpls_fib.h:52
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:315
void load_balance_set_bucket(index_t lbi, u32 bucket, const dpo_id_t *next)
Definition: load_balance.c:256
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:980
typedef key
Definition: ipsec.api:245
#define DPO_INVALID
An initialiser for DPOs declared on the stack.
Definition: dpo.h:197
#define MPLS_IETF_IPV6_EXPLICIT_NULL_LABEL
Definition: mpls_types.h:29
Special sources.
Definition: fib_entry.h:45
void * mem
u8 * format_mpls_fib_table_memory(u8 *s, va_list *args)
Definition: mpls_fib.c:363
#define vec_foreach(var, vec)
Vector iterator.
u32 table_id
Definition: fib_types.api:118
#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
void vlib_cli_output(vlib_main_t *vm, char *fmt,...)
Definition: cli.c:768
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:69
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