FD.io VPP  v17.04-9-g99c0734
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 /**
65  * FIXME
66  */
67 #define MPLS_FLOW_HASH_DEFAULT 0
68 
69 static inline u32
71  mpls_eos_bit_t eos)
72 {
73  ASSERT(eos <= 1);
74  return (label << 1 | eos);
75 }
76 
77 u32
79 {
80  mpls_main_t *mm = &mpls_main;
81  uword * p;
82 
83  p = hash_get (mm->fib_index_by_table_id, table_id);
84  if (!p)
86 
87  return p[0];
88 }
89 
90 static u32
92 {
93  dpo_id_t dpo = DPO_INVALID;
94  fib_table_t *fib_table;
95  mpls_eos_bit_t eos;
96  mpls_fib_t *mf;
97  int i;
98 
100  memset(fib_table, 0, sizeof(*fib_table));
101 
102  fib_table->ft_proto = FIB_PROTOCOL_MPLS;
103  fib_table->ft_index =
104  (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 =
109  table_id;
110  fib_table->ft_flow_hash_config =
112  fib_table->v4.fwd_classify_table_index = ~0;
113  fib_table->v4.rev_classify_table_index = ~0;
114 
116 
118  {
121  0,
123  }
124 
125  mf = &fib_table->mpls;
126  mf->mf_entries = hash_create(0, sizeof(fib_node_index_t));
127  for (i = 0; i < MPLS_FIB_DB_SIZE; i++)
128  {
129  /*
130  * initialise each DPO in the data-path lookup table
131  * to be the special MPLS drop
132  */
134  }
135 
136  /*
137  * non-default forwarding for the special labels.
138  */
139  fib_prefix_t prefix = {
141  .fp_payload_proto = DPO_PROTO_MPLS,
142  };
143 
144  /*
145  * PUNT the router alert, both EOS and non-eos
146  */
149  {
150  prefix.fp_eos = eos;
152  &prefix,
156  }
157 
158  /*
159  * IPv4 explicit NULL EOS lookup in the interface's IPv4 table
160  */
163  prefix.fp_eos = MPLS_EOS;
164 
169  &dpo);
171  &prefix,
174  &dpo);
175 
177  prefix.fp_eos = MPLS_NON_EOS;
178 
183  &dpo);
185  &prefix,
188  &dpo);
189 
190  /*
191  * IPv6 explicit NULL EOS lookup in the interface's IPv6 table
192  */
195  prefix.fp_eos = MPLS_EOS;
196 
201  &dpo);
203  &prefix,
206  &dpo);
207 
209  prefix.fp_eos = MPLS_NON_EOS;
214  &dpo);
216  &prefix,
219  &dpo);
220 
221  return (fib_table->ft_index);
222 }
223 
224 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);
232 
234 
235  return (index);
236 }
237 u32
239 {
240  return (mpls_fib_create_with_table_id(~0));
241 }
242 
243 void
245 {
246  fib_table_t *fib_table = (fib_table_t*)mf;
247  fib_prefix_t prefix = {
249  };
250  mpls_label_t special_labels[] = {
254  };
255  mpls_eos_bit_t eos;
256  u32 ii;
257 
258  for (ii = 0; ii < ARRAY_LEN(special_labels); ii++)
259  {
261  {
262  prefix.fp_label = special_labels[ii];
263  prefix.fp_eos = eos;
264 
265  fib_table_entry_delete(fib_table->ft_index,
266  &prefix,
268  }
269  }
270  if (~0 != fib_table->ft_table_id)
271  {
273  fib_table->ft_table_id);
274  }
275  hash_free(mf->mf_entries);
276 
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 
321 
322  key = mpls_fib_entry_mk_key(label, eos);
323 
324  mf->mf_lbs[key] = dpo->dpoi_index;
325 }
326 
327 void
329  mpls_label_t label,
330  mpls_eos_bit_t eos)
331 {
332  mpls_label_t key;
333 
334  key = mpls_fib_entry_mk_key(label, eos);
335 
336  mf->mf_lbs[key] = mpls_fib_drop_dpo_index;
337 }
338 
341 {
342  // FIXME.
343  return (0);
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(&(fib_table->mpls), vm);
440  }
441  else
442  {
443  mpls_fib_table_show_one(&(fib_table->mpls), 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:93
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:343
fib_protocol_t ft_proto
Which protocol this table serves.
Definition: fib_table.h:46
#define hash_unset(h, key)
Definition: hash.h:260
mpls_fib_t mpls
Definition: fib_table.h:40
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:1072
#define FIB_ENTRY_FORMAT_DETAIL
Definition: fib_entry.h:428
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:733
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
void lookup_dpo_add_or_lock_w_fib_index(fib_node_index_t fib_index, dpo_proto_t proto, lookup_input_t input, lookup_table_t table_config, dpo_id_t *dpo)
Definition: lookup_dpo.c:116
u32 mpls_fib_table_find_or_create_and_lock(u32 table_id)
Definition: mpls_fib.c:225
#define MPLS_IETF_ROUTER_ALERT_LABEL
Definition: mpls_types.h:14
void mpls_fib_table_destroy(mpls_fib_t *mf)
Definition: mpls_fib.c:244
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:192
const dpo_id_t * drop_dpo_get(dpo_proto_t proto)
Definition: drop_dpo.c:25
u32 fwd_classify_table_index
Definition: ip4.h:66
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:70
#define pool_foreach(VAR, POOL, BODY)
Iterate through pool.
Definition: pool.h:376
#define hash_foreach(key_var, value_var, h, body)
Definition: hash.h:418
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
u32 rev_classify_table_index
Definition: ip4.h:67
int fib_entry_cmp_for_sort(void *i1, void *i2)
Definition: fib_entry.c:1408
The identity of a DPO is a combination of its type and its instance number/index of objects of that t...
Definition: dpo.h:146
#define hash_get(h, key)
Definition: hash.h:248
Definition: fib_entry.h:231
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:150
struct _unformat_input_t unformat_input_t
load-balancing over a choice of [un]equal cost paths
Definition: dpo.h:104
#define MPLS_FIB_DB_SIZE
Definition: mpls.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
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:68
#define MPLS_FLOW_HASH_DEFAULT
FIXME.
Definition: mpls_fib.c:67
#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:238
fib_node_index_t ft_index
Index into FIB vector.
Definition: fib_table.h:61
#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:56
vlib_main_t * vm
Definition: buffer.c:276
u32 ft_flow_hash_config
flow hash configuration
Definition: fib_table.h:66
#define MPLS_LABEL_INVALID
Definition: mpls_types.h:33
#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:798
static u32 mpls_fib_create_with_table_id(u32 table_id)
Definition: mpls_fib.c:91
#define MPLS_IETF_IPV4_EXPLICIT_NULL_LABEL
Definition: mpls_types.h:13
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:78
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:288
#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:328
uword * mf_entries
A hash table of entries.
Definition: mpls.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:209
u32 flow_hash_config_t
A flow hash configuration is a mask of the flow hash options.
Definition: lookup.h:165
u64 uword
Definition: types.h:112
index_t dpoi_index
the index of objects of that type
Definition: dpo.h:162
#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:173
#define MPLS_IETF_IPV6_EXPLICIT_NULL_LABEL
Definition: mpls_types.h:15
Special sources.
Definition: fib_entry.h:40
ip4_fib_t v4
Definition: fib_table.h:38
#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 indeices keyed by 21 bit label+eos bit.
Definition: mpls.h:53
void vlib_cli_output(vlib_main_t *vm, char *fmt,...)
Definition: cli.c:577
uword * fib_index_by_table_id
A hash table to lookup the mpls_fib by table ID.
Definition: mpls.h:71
uword unformat(unformat_input_t *i, const char *fmt,...)
Definition: unformat.c:971
flow_hash_config_t mpls_fib_table_get_flow_hash_config(u32 fib_index)
Definition: mpls_fib.c:340
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