FD.io VPP  v17.07.01-10-g3be13f0
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
87 {
88  dpo_id_t dpo = DPO_INVALID;
89  fib_table_t *fib_table;
90  mpls_eos_bit_t eos;
91  mpls_fib_t *mf;
92  int i;
93 
96 
97  ASSERT((fib_table - mpls_main.fibs) ==
98  (mf - mpls_main.mpls_fibs));
99 
100  memset(fib_table, 0, sizeof(*fib_table));
101 
102  fib_table->ft_proto = FIB_PROTOCOL_MPLS;
103  fib_table->ft_index = (fib_table - mpls_main.fibs);
104 
105  hash_set (mpls_main.fib_index_by_table_id, table_id, fib_table->ft_index);
106 
107  fib_table->ft_table_id = table_id;
109 
111 
113  {
116  0,
118  }
119 
120  mf->mf_entries = hash_create(0, sizeof(fib_node_index_t));
121  for (i = 0; i < MPLS_FIB_DB_SIZE; i++)
122  {
123  /*
124  * initialise each DPO in the data-path lookup table
125  * to be the special MPLS drop
126  */
128  }
129 
130  /*
131  * non-default forwarding for the special labels.
132  */
133  fib_prefix_t prefix = {
135  .fp_payload_proto = DPO_PROTO_MPLS,
136  };
137 
138  /*
139  * PUNT the router alert, both EOS and non-eos
140  */
143  {
144  prefix.fp_eos = eos;
146  &prefix,
150  }
151 
152  /*
153  * IPv4 explicit NULL EOS lookup in the interface's IPv4 table
154  */
157  prefix.fp_eos = MPLS_EOS;
158 
164  &dpo);
166  &prefix,
169  &dpo);
170 
172  prefix.fp_eos = MPLS_NON_EOS;
173 
179  &dpo);
181  &prefix,
184  &dpo);
185 
186  /*
187  * IPv6 explicit NULL EOS lookup in the interface's IPv6 table
188  */
191  prefix.fp_eos = MPLS_EOS;
192 
198  &dpo);
200  &prefix,
203  &dpo);
204 
206  prefix.fp_eos = MPLS_NON_EOS;
212  &dpo);
214  &prefix,
217  &dpo);
218 
219  return (fib_table->ft_index);
220 }
221 
222 u32
224 {
225  u32 index;
226 
227  index = mpls_fib_index_from_table_id(table_id);
228  if (~0 == index)
229  return mpls_fib_create_with_table_id(table_id);
230 
232 
233  return (index);
234 }
235 u32
237 {
238  return (mpls_fib_create_with_table_id(~0));
239 }
240 
241 void
243 {
244  fib_table_t *fib_table = pool_elt_at_index(mpls_main.fibs, fib_index);
246  fib_prefix_t prefix = {
248  };
249  mpls_label_t special_labels[] = {
253  };
254  mpls_eos_bit_t eos;
255  u32 ii;
256 
257  for (ii = 0; ii < ARRAY_LEN(special_labels); ii++)
258  {
260  {
261  prefix.fp_label = special_labels[ii];
262  prefix.fp_eos = eos;
263 
264  fib_table_entry_delete(fib_table->ft_index,
265  &prefix,
267  }
268  }
269  if (~0 != fib_table->ft_table_id)
270  {
272  fib_table->ft_table_id);
273  }
274  hash_free(mf->mf_entries);
275 
277  pool_put(mpls_main.fibs, fib_table);
278 }
279 
282  mpls_label_t label,
283  mpls_eos_bit_t eos)
284 {
285  uword *p;
286 
287  p = hash_get(mf->mf_entries, mpls_fib_entry_mk_key(label, eos));
288 
289  if (NULL == p)
290  return FIB_NODE_INDEX_INVALID;
291 
292  return p[0];
293 }
294 
295 void
297  mpls_label_t label,
298  mpls_eos_bit_t eos,
299  fib_node_index_t lfei)
300 {
301  hash_set(mf->mf_entries, mpls_fib_entry_mk_key(label, eos), lfei);
302 }
303 
304 void
306  mpls_label_t label,
307  mpls_eos_bit_t eos)
308 {
309  hash_unset(mf->mf_entries, mpls_fib_entry_mk_key(label, eos));
310 }
311 
312 void
314  mpls_label_t label,
315  mpls_eos_bit_t eos,
316  const dpo_id_t *dpo)
317 {
318  mpls_label_t key;
319 
320  ASSERT((DPO_LOAD_BALANCE == dpo->dpoi_type) ||
321  (DPO_REPLICATE == dpo->dpoi_type));
322  if (CLIB_DEBUG > 0)
323  {
324  if (DPO_REPLICATE == dpo->dpoi_type)
326  if (DPO_LOAD_BALANCE == dpo->dpoi_type)
328  }
329  key = mpls_fib_entry_mk_key(label, eos);
330 
331  mf->mf_lbs[key] = dpo->dpoi_index;
332 }
333 
334 void
336  mpls_label_t label,
337  mpls_eos_bit_t eos)
338 {
339  mpls_label_t key;
340 
341  key = mpls_fib_entry_mk_key(label, eos);
342 
343  mf->mf_lbs[key] = mpls_fib_drop_dpo_index;
344 }
345 
346 void
349  void *ctx)
350 {
351  fib_node_index_t lfei;
352  mpls_label_t key;
353 
354  hash_foreach(key, lfei, mpls_fib->mf_entries,
355  ({
356  fn(lfei, ctx);
357  }));
358 }
359 
360 static void
362  vlib_main_t * vm)
363 {
364  fib_node_index_t lfei, *lfeip, *lfeis = NULL;
365  mpls_label_t key;
366 
367  hash_foreach(key, lfei, mpls_fib->mf_entries,
368  ({
369  vec_add1(lfeis, lfei);
370  }));
371 
373 
374  vec_foreach(lfeip, lfeis)
375  {
376  vlib_cli_output (vm, "%U",
377  format_fib_entry, *lfeip,
379  }
380  vec_free(lfeis);
381 }
382 
383 static void
385  mpls_label_t label,
386  vlib_main_t * vm)
387 {
388  fib_node_index_t lfei;
389  mpls_eos_bit_t eos;
390 
392  {
393  lfei = mpls_fib_table_lookup(mpls_fib, label, eos);
394 
395  if (FIB_NODE_INDEX_INVALID != lfei)
396  {
397  vlib_cli_output (vm, "%U",
399  }
400  }
401 }
402 
403 static clib_error_t *
405  unformat_input_t * input,
406  vlib_cli_command_t * cmd)
407 {
408  fib_table_t * fib_table;
409  mpls_label_t label;
410  int table_id;
411 
412  table_id = -1;
413  label = MPLS_LABEL_INVALID;
414 
416  {
417  /* if (unformat (input, "brief") || unformat (input, "summary") */
418  /* || unformat (input, "sum")) */
419  /* verbose = 0; */
420 
421  if (unformat (input, "%d", &label))
422  continue;
423  else if (unformat (input, "table %d", &table_id))
424  ;
425  else
426  break;
427  }
428 
429  pool_foreach (fib_table, mpls_main.fibs,
430  ({
431  if (table_id >= 0 && table_id != fib_table->ft_table_id)
432  continue;
433 
434  vlib_cli_output (vm, "%v, fib_index %d",
435  fib_table->ft_desc, mpls_main.fibs - fib_table);
436 
437  if (MPLS_LABEL_INVALID == label)
438  {
439  mpls_fib_table_show_all(mpls_fib_get(fib_table->ft_index), vm);
440  }
441  else
442  {
443  mpls_fib_table_show_one(mpls_fib_get(fib_table->ft_index), label, vm);
444  }
445  }));
446 
447  return 0;
448 }
449 
450 VLIB_CLI_COMMAND (mpls_fib_show_command, static) = {
451  .path = "show mpls fib",
452  .short_help = "show mpls fib [summary] [table <n>]",
453  .function = mpls_fib_show,
454 };
static void mpls_fib_table_show_all(const mpls_fib_t *mpls_fib, vlib_main_t *vm)
Definition: mpls_fib.c:361
fib_protocol_t fp_proto
protocol type
Definition: fib_types.h:169
u8 * format_fib_entry(u8 *s, va_list *args)
Definition: fib_entry.c:87
void mpls_fib_table_entry_remove(mpls_fib_t *mf, mpls_label_t label, mpls_eos_bit_t eos)
Definition: mpls_fib.c:305
#define hash_set(h, key, value)
Definition: hash.h:254
sll srl srl sll sra u16x4 i
Definition: vector_sse2.h:337
fib_protocol_t ft_proto
Which protocol this table serves.
Definition: fib_table.h:34
#define hash_unset(h, key)
Definition: hash.h:260
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:281
void fib_table_lock(u32 fib_index, fib_protocol_t proto)
Release a reference counting lock on the table.
Definition: fib_table.c:1159
void mpls_fib_table_destroy(u32 fib_index)
Definition: mpls_fib.c:242
#define FIB_ENTRY_FORMAT_DETAIL
Definition: fib_entry.h:435
static clib_error_t * mpls_fib_show(vlib_main_t *vm, unformat_input_t *input, vlib_cli_command_t *cmd)
Definition: mpls_fib.c:404
#define NULL
Definition: clib.h:55
int(* 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:751
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:24
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
u32 mpls_fib_table_find_or_create_and_lock(u32 table_id)
Definition: mpls_fib.c:223
#define MPLS_IETF_ROUTER_ALERT_LABEL
Definition: mpls_types.h:28
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:296
index_t load_balance_create(u32 n_buckets, dpo_proto_t lb_proto, flow_hash_config_t fhc)
Definition: load_balance.c:193
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:193
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:376
#define MPLS_FIB_DB_SIZE
Definition: mpls_fib.h:34
#define hash_foreach(key_var, value_var, h, body)
Definition: hash.h:418
#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:58
Aggregrate type for a prefix.
Definition: fib_types.h:160
const dpo_id_t * punt_dpo_get(dpo_proto_t proto)
Definition: punt_dpo.c:25
int fib_entry_cmp_for_sort(void *i1, void *i2)
Definition: fib_entry.c:1484
The identity of a DPO is a combination of its type and its instance number/index of objects of that t...
Definition: dpo.h:152
#define hash_get(h, key)
Definition: hash.h:248
Definition: fib_entry.h:237
#define pool_elt_at_index(p, i)
Returns pointer to element at given index.
Definition: pool.h:397
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:347
dpo_type_t dpoi_type
the type
Definition: dpo.h:156
struct _unformat_input_t unformat_input_t
load-balancing over a choice of [un]equal cost paths
Definition: dpo.h:104
#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:286
#define pool_put(P, E)
Free an object E in pool P.
Definition: pool.h:241
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:127
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:384
struct fib_table_t_ * fibs
A pool of all the MPLS FIBs.
Definition: mpls.h:45
#define pool_get_aligned(P, E, A)
Allocate an object E from a pool P (general version).
Definition: pool.h:169
u32 mpls_fib_table_create_and_lock(void)
Definition: mpls_fib.c:236
fib_node_index_t ft_index
Index into FIB vector.
Definition: fib_table.h:49
#define UNFORMAT_END_OF_INPUT
Definition: format.h:143
mpls_main_t mpls_main
Definition: mpls.c:25
u32 ft_table_id
Table ID (hash key) for this FIB.
Definition: fib_table.h:44
u32 ft_flow_hash_config
flow hash configuration
Definition: fib_table.h:54
#define MPLS_LABEL_INVALID
Definition: mpls_types.h:48
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:340
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:835
static u32 mpls_fib_create_with_table_id(u32 table_id)
Definition: mpls_fib.c:86
#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:28
#define ARRAY_LEN(x)
Definition: clib.h:59
u32 mpls_fib_index_from_table_id(u32 table_id)
Definition: mpls_fib.c:73
mpls_label_t fp_label
Definition: fib_types.h:186
#define VLIB_CLI_COMMAND(x,...)
Definition: cli.h:154
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:290
#define FOR_EACH_MPLS_EOS_BIT(_eos)
Definition: packet.h:45
#define hash_create(elts, value_bytes)
Definition: hash.h:658
#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:335
uword * mf_entries
A hash table of entries.
Definition: mpls_fib.h:47
unsigned int u32
Definition: types.h:88
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:313
void load_balance_set_bucket(index_t lbi, u32 bucket, const dpo_id_t *next)
Definition: load_balance.c:210
u64 uword
Definition: types.h:112
index_t dpoi_index
the index of objects of that type
Definition: dpo.h:168
#define FIB_NODE_INDEX_INVALID
Definition: fib_types.h:29
#define INDEX_INVALID
Invalid index - used when no index is known blazoned capitals INVALID speak volumes where ~0 does not...
Definition: dpo.h:47
#define vec_sort_with_function(vec, f)
Sort a vector using the supplied element comparison function.
Definition: vec.h:960
#define DPO_INVALID
An initialiser for DPOs declared on the stack.
Definition: dpo.h:179
#define MPLS_IETF_IPV6_EXPLICIT_NULL_LABEL
Definition: mpls_types.h:29
Special sources.
Definition: fib_entry.h:40
#define vec_foreach(var, vec)
Vector iterator.
#define CLIB_CACHE_LINE_BYTES
Definition: cache.h:67
index_t mf_lbs[MPLS_FIB_DB_SIZE]
The load-balance indices keyed by 21 bit label+eos bit.
Definition: mpls_fib.h:53
void vlib_cli_output(vlib_main_t *vm, char *fmt,...)
Definition: cli.c:680
uword * fib_index_by_table_id
A hash table to lookup the mpls_fib by table ID.
Definition: mpls.h:51
struct mpls_fib_t_ * mpls_fibs
A pool of all the MPLS FIBs.
Definition: mpls.h:48
uword unformat(unformat_input_t *i, const char *fmt,...)
Definition: unformat.c:972
static uword unformat_check_input(unformat_input_t *i)
Definition: format.h:169
A protocol Independent FIB table.
Definition: fib_table.h:29
mpls_eos_bit_t fp_eos
Definition: fib_types.h:187
enum mpls_eos_bit_t_ mpls_eos_bit_t