FD.io VPP  v17.01.1-3-gc6833f8
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/dpo/load_balance.h>
52 #include <vnet/dpo/drop_dpo.h>
53 #include <vnet/dpo/punt_dpo.h>
54 #include <vnet/dpo/lookup_dpo.h>
55 #include <vnet/mpls/mpls.h>
56 
57 /**
58  * All lookups in an MPLS_FIB table must result in a DPO of type load-balance.
59  * This is the default result which links to drop
60  */
62 
63 /**
64  * FIXME
65  */
66 #define MPLS_FLOW_HASH_DEFAULT 0
67 
68 static inline u32
70  mpls_eos_bit_t eos)
71 {
72  ASSERT(eos <= 1);
73  return (label << 1 | eos);
74 }
75 
76 u32
78 {
79  mpls_main_t *mm = &mpls_main;
80  uword * p;
81 
82  p = hash_get (mm->fib_index_by_table_id, table_id);
83  if (!p)
85 
86  return p[0];
87 }
88 
89 static u32
91 {
92  dpo_id_t dpo = DPO_INVALID;
93  fib_table_t *fib_table;
94  mpls_eos_bit_t eos;
95  mpls_fib_t *mf;
96  int i;
97 
99  memset(fib_table, 0, sizeof(*fib_table));
100 
101  fib_table->ft_proto = FIB_PROTOCOL_MPLS;
102  fib_table->ft_index =
103  (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 =
108  table_id;
109  fib_table->ft_flow_hash_config =
111  fib_table->v4.fwd_classify_table_index = ~0;
112  fib_table->v4.rev_classify_table_index = ~0;
113 
115 
117  {
120  0,
122  }
123 
124  mf = &fib_table->mpls;
125  mf->mf_entries = hash_create(0, sizeof(fib_node_index_t));
126  for (i = 0; i < MPLS_FIB_DB_SIZE; i++)
127  {
128  /*
129  * initialise each DPO in the data-path lookup table
130  * to be the special MPLS drop
131  */
133  }
134 
135  /*
136  * non-default forwarding for the special labels.
137  */
138  fib_prefix_t prefix = {
140  .fp_payload_proto = DPO_PROTO_MPLS,
141  };
142 
143  /*
144  * PUNT the router alert, both EOS and non-eos
145  */
148  {
149  prefix.fp_eos = eos;
151  &prefix,
155  }
156 
157  /*
158  * IPv4 explicit NULL EOS lookup in the interface's IPv4 table
159  */
162  prefix.fp_eos = MPLS_EOS;
163 
168  &dpo);
170  &prefix,
173  &dpo);
174 
176  prefix.fp_eos = MPLS_NON_EOS;
177 
182  &dpo);
184  &prefix,
187  &dpo);
188 
189  /*
190  * IPv6 explicit NULL EOS lookup in the interface's IPv6 table
191  */
194  prefix.fp_eos = MPLS_EOS;
195 
200  &dpo);
202  &prefix,
205  &dpo);
206 
208  prefix.fp_eos = MPLS_NON_EOS;
213  &dpo);
215  &prefix,
218  &dpo);
219 
220  return (fib_table->ft_index);
221 }
222 
223 u32
225 {
226  u32 index;
227 
228  index = mpls_fib_index_from_table_id(table_id);
229  if (~0 == index)
230  return mpls_fib_create_with_table_id(table_id);
231 
233 
234  return (index);
235 }
236 u32
238 {
239  return (mpls_fib_create_with_table_id(~0));
240 }
241 
242 void
244 {
245  fib_table_t *fib_table = (fib_table_t*)mf;
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_delete(mf->mf_entries);
275 
276  pool_put(mpls_main.fibs, fib_table);
277 }
278 
281  mpls_label_t label,
282  mpls_eos_bit_t eos)
283 {
284  uword *p;
285 
286  p = hash_get(mf->mf_entries, mpls_fib_entry_mk_key(label, eos));
287 
288  if (NULL == p)
289  return FIB_NODE_INDEX_INVALID;
290 
291  return p[0];
292 }
293 
294 void
296  mpls_label_t label,
297  mpls_eos_bit_t eos,
298  fib_node_index_t lfei)
299 {
300  hash_set(mf->mf_entries, mpls_fib_entry_mk_key(label, eos), lfei);
301 }
302 
303 void
305  mpls_label_t label,
306  mpls_eos_bit_t eos)
307 {
308  hash_unset(mf->mf_entries, mpls_fib_entry_mk_key(label, eos));
309 }
310 
311 void
313  mpls_label_t label,
314  mpls_eos_bit_t eos,
315  const dpo_id_t *dpo)
316 {
317  mpls_label_t key;
318 
320 
321  key = mpls_fib_entry_mk_key(label, eos);
322 
323  mf->mf_lbs[key] = dpo->dpoi_index;
324 }
325 
326 void
328  mpls_label_t label,
329  mpls_eos_bit_t eos)
330 {
331  mpls_label_t key;
332 
333  key = mpls_fib_entry_mk_key(label, eos);
334 
335  mf->mf_lbs[key] = mpls_fib_drop_dpo_index;
336 }
337 
340 {
341  // FIXME.
342  return (0);
343 }
344 
345 static void
347  vlib_main_t * vm)
348 {
349  fib_node_index_t lfei, *lfeip, *lfeis = NULL;
350  mpls_label_t key;
351 
352  hash_foreach(key, lfei, mpls_fib->mf_entries,
353  ({
354  vec_add1(lfeis, lfei);
355  }));
356 
358 
359  vec_foreach(lfeip, lfeis)
360  {
361  vlib_cli_output (vm, "%U",
362  format_fib_entry, *lfeip,
364  }
365  vec_free(lfeis);
366 }
367 
368 static void
370  mpls_label_t label,
371  vlib_main_t * vm)
372 {
373  fib_node_index_t lfei;
374  mpls_eos_bit_t eos;
375 
377  {
378  lfei = mpls_fib_table_lookup(mpls_fib, label, eos);
379 
380  if (FIB_NODE_INDEX_INVALID != lfei)
381  {
382  vlib_cli_output (vm, "%U",
384  }
385  }
386 }
387 
388 static clib_error_t *
390  unformat_input_t * input,
391  vlib_cli_command_t * cmd)
392 {
393  fib_table_t * fib_table;
394  mpls_label_t label;
395  int table_id;
396 
397  table_id = -1;
398  label = MPLS_LABEL_INVALID;
399 
401  {
402  /* if (unformat (input, "brief") || unformat (input, "summary") */
403  /* || unformat (input, "sum")) */
404  /* verbose = 0; */
405 
406  if (unformat (input, "%d", &label))
407  continue;
408  else if (unformat (input, "table %d", &table_id))
409  ;
410  else
411  break;
412  }
413 
414  pool_foreach (fib_table, mpls_main.fibs,
415  ({
416  if (table_id >= 0 && table_id != fib_table->ft_table_id)
417  continue;
418 
419  vlib_cli_output (vm, "%v, fib_index %d",
420  fib_table->ft_desc, mpls_main.fibs - fib_table);
421 
422  if (MPLS_LABEL_INVALID == label)
423  {
424  mpls_fib_table_show_all(&(fib_table->mpls), vm);
425  }
426  else
427  {
428  mpls_fib_table_show_one(&(fib_table->mpls), label, vm);
429  }
430  }));
431 
432  return 0;
433 }
434 
435 VLIB_CLI_COMMAND (mpls_fib_show_command, static) = {
436  .path = "show mpls fib",
437  .short_help = "show mpls fib [summary] [table <n>]",
438  .function = mpls_fib_show,
439 };
static void mpls_fib_table_show_all(const mpls_fib_t *mpls_fib, vlib_main_t *vm)
Definition: mpls_fib.c:346
fib_protocol_t fp_proto
protocol type
Definition: fib_types.h:154
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:304
#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
uword unformat(unformat_input_t *i, char *fmt,...)
Definition: unformat.c:966
#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:280
void fib_table_lock(u32 fib_index, fib_protocol_t proto)
Release a reference counting lock on the table.
Definition: fib_table.c:1062
#define FIB_ENTRY_FORMAT_DETAIL
Definition: fib_entry.h:416
static clib_error_t * mpls_fib_show(vlib_main_t *vm, unformat_input_t *input, vlib_cli_command_t *cmd)
Definition: mpls_fib.c:389
#define UNFORMAT_END_OF_INPUT
Definition: format.h:143
#define NULL
Definition: clib.h:55
static index_t mpls_fib_drop_dpo_index
An MPLS_FIB table;.
Definition: mpls_fib.c:61
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:224
#define MPLS_IETF_ROUTER_ALERT_LABEL
Definition: mpls_types.h:14
void mpls_fib_table_destroy(mpls_fib_t *mf)
Definition: mpls_fib.c:243
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:295
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:178
static u32 mpls_fib_entry_mk_key(mpls_label_t label, mpls_eos_bit_t eos)
Definition: mpls_fib.c:69
#define pool_foreach(VAR, POOL, BODY)
Iterate through pool.
Definition: pool.h:348
#define hash_foreach(key_var, value_var, h, body)
Definition: hash.h:418
Aggregrate type for a prefix.
Definition: fib_types.h:145
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:1388
The identity of a DPO is a combination of its type and its instance number/index of objects of that t...
Definition: dpo.h:138
static void hash_delete(void *bob)
Definition: hash.h:687
#define hash_get(h, key)
Definition: hash.h:248
Definition: fib_entry.h:220
dpo_type_t dpoi_type
the type
Definition: dpo.h:142
load-balancing over a choice of [un]equal cost paths
Definition: dpo.h:102
#define MPLS_FIB_DB_SIZE
Definition: mpls.h:39
#define pool_put(P, E)
Free an object E in pool P.
Definition: pool.h:214
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:369
void vlib_cli_output(vlib_main_t *vm, char *fmt,...)
Definition: cli.c:576
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:66
#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:237
fib_node_index_t ft_index
Index into FIB vector.
Definition: fib_table.h:61
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
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:300
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:808
static u32 mpls_fib_create_with_table_id(u32 table_id)
Definition: mpls_fib.c:90
#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:77
mpls_label_t fp_label
Definition: fib_types.h:171
#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:327
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:312
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:160
u64 uword
Definition: types.h:112
index_t dpoi_index
the index of objects of that type
Definition: dpo.h:154
#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:920
#define DPO_INVALID
An initialiser for DPOs declared on the stack.
Definition: dpo.h:165
#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
static uword unformat_check_input(unformat_input_t *i)
Definition: format.h:169
#define vec_foreach(var, vec)
Vector iterator.
struct _unformat_input_t unformat_input_t
#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
uword * fib_index_by_table_id
A hash table to lookup the mpls_fib by table ID.
Definition: mpls.h:71
flow_hash_config_t mpls_fib_table_get_flow_hash_config(u32 fib_index)
Definition: mpls_fib.c:339
A protocol Independent FIB table.
Definition: fib_table.h:29
mpls_eos_bit_t fp_eos
Definition: fib_types.h:172
enum mpls_eos_bit_t_ mpls_eos_bit_t