FD.io VPP  v19.01.3-6-g70449b9b9
Vector Packet Processing
fib_attached_export.c
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2016 Cisco and/or its affiliates.
3  * Licensed under the Apache License, Version 2.0 (the "License");
4  * you may not use this file except in compliance with the License.
5  * You may obtain a copy of the License at:
6  *
7  * http://www.apache.org/licenses/LICENSE-2.0
8  *
9  * Unless required by applicable law or agreed to in writing, software
10  * distributed under the License is distributed on an "AS IS" BASIS,
11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12  * See the License for the specific language governing permissions and
13  * limitations under the License.
14  */
15 
16 #include <vnet/fib/fib_entry.h>
17 #include <vnet/fib/fib_table.h>
18 
21 #include <vnet/fib/fib_entry_src.h>
23 #include <vnet/dpo/drop_dpo.h>
24 
25 /**
26  * A description of the need to import routes from the export table
27  */
28 typedef struct fib_ae_import_t_
29 {
30  /**
31  * The entry in the epxort table that this importer
32  * is importing covereds from
33  */
35 
36  /**
37  * The attached entry in the import table
38  */
40  /**
41  * the sibling index on the cover
42  */
44 
45  /**
46  * The index of the exporter tracker. Not set if the
47  * export entry is not valid for export
48  */
50 
51  /**
52  * A vector/list of imported entry indicies
53  */
55 
56  /**
57  * The FIB index and prefix we are tracking
58  */
61 
62  /**
63  * The FIB index we are importing into
64  */
67 
68 /**
69  * A description of the need to export routes to one or more export tables
70  */
71 typedef struct fib_ae_export_t_ {
72  /**
73  * The vector/list of import tracker indicies
74  */
76 
77  /**
78  * THe connected entry this export is acting on behalf of
79  */
81 
82  /**
83  * Reference counting locks
84  */
87 
88 /*
89  * memory pools for the importers and exportes
90  */
93 
94 static fib_ae_export_t *
96 {
98  fib_ae_export_t *export;
99  fib_entry_t *entry;
100 
101  entry = fib_entry_get(connected);
102  fed = fib_entry_delegate_get(entry,
104 
105  if (NULL == fed)
106  {
107  fed = fib_entry_delegate_find_or_add(entry,
109  pool_get(fib_ae_export_pool, export);
110  clib_memset(export, 0, sizeof(*export));
111 
112  fed->fd_index = (export - fib_ae_export_pool);
113  export->faee_ei = connected;
114  }
115  else
116  {
117  export = pool_elt_at_index(fib_ae_export_pool, fed->fd_index);
118  }
119 
120  export->faee_locks++;
121 
122  return (export);
123 }
124 
125 static void
127  fib_node_index_t entry_index)
128 {
129  u32 index;
130 
131  /*
132  * find the index in the vector of the entry we are removing
133  */
134  index = vec_search(import->faei_importeds, entry_index);
135 
136  if (index < vec_len(import->faei_importeds))
137  {
138  /*
139  * this is an entry that was previsouly imported
140  */
141  fib_table_entry_special_remove(import->faei_import_fib,
142  fib_entry_get_prefix(entry_index),
143  FIB_SOURCE_AE);
144 
145  fib_entry_unlock(entry_index);
146  vec_del1(import->faei_importeds, index);
147  }
148 }
149 
150 static void
152  fib_node_index_t entry_index)
153 {
154  fib_node_index_t *existing;
155  const fib_prefix_t *prefix;
156 
157  /*
158  * ensure we only add the exported entry once, since
159  * sourcing prefixes in the table is reference counted
160  */
161  vec_foreach(existing, import->faei_importeds)
162  {
163  if (*existing == entry_index)
164  {
165  return;
166  }
167  }
168 
169  /*
170  * this is the first time this export entry has been imported
171  * Add it to the import FIB and to the list of importeds
172  */
173  prefix = fib_entry_get_prefix(entry_index);
174 
175  /*
176  * don't import entries that have the same prefix the import entry
177  */
178  if (0 != fib_prefix_cmp(prefix,
179  &import->faei_prefix))
180  {
181  const dpo_id_t *dpo;
182 
183  dpo = fib_entry_contribute_ip_forwarding(entry_index);
184 
185  if (dpo_id_is_valid(dpo) && !dpo_is_drop(dpo))
186  {
187  fib_table_entry_special_dpo_add(import->faei_import_fib,
188  prefix,
190  (fib_entry_get_flags(entry_index) |
193 
194  fib_entry_lock(entry_index);
195  vec_add1(import->faei_importeds, entry_index);
196  }
197  /*
198  * else
199  * the entry currently has no valid forwarding. when it
200  * does it will export itself
201  */
202  }
203 }
204 
205 /**
206  * Call back when walking a connected prefix's covered prefixes for import
207  */
208 static int
210  fib_node_index_t covered,
211  void *ctx)
212 {
213  fib_ae_import_t *import = ctx;
214 
215  fib_entry_import_add(import, covered);
216 
217  return (0);
218 }
219 
220 /*
221  * fib_entry_ae_import_add
222  *
223  * Add an importer to a connected entry
224  */
225 static void
227  fib_ae_import_t *import)
228 {
229  fib_entry_t *entry;
230 
231  import->faei_exporter = (export - fib_ae_export_pool);
232  entry = fib_entry_get(export->faee_ei);
233 
234  fib_entry_cover_walk(entry,
236  import);
237 }
238 
239 void
241  fib_node_index_t export_fib)
242 {
244  fib_ae_import_t *import;
245  fib_node_index_t fei;
246 
247  /*
248  * save index for later post-realloc retreival
249  */
250  fei = fib_entry_get_index(fib_entry);
251 
252  pool_get(fib_ae_import_pool, import);
253 
254  import->faei_import_fib = fib_entry->fe_fib_index;
255  import->faei_export_fib = export_fib;
256  import->faei_prefix = fib_entry->fe_prefix;
257  import->faei_import_entry = fib_entry_get_index(fib_entry);
258  import->faei_export_sibling = ~0;
259 
260  /*
261  * do an exact match in the export table
262  */
263  import->faei_export_entry =
264  fib_table_lookup_exact_match(import->faei_export_fib,
265  &import->faei_prefix);
266 
267  if (FIB_NODE_INDEX_INVALID == import->faei_export_entry)
268  {
269  /*
270  * no exact matching entry in the export table. can't be good.
271  * track the next best thing
272  */
273  import->faei_export_entry =
274  fib_table_lookup(import->faei_export_fib,
275  &import->faei_prefix);
276  import->faei_exporter = FIB_NODE_INDEX_INVALID;
277  }
278  else
279  {
280  /*
281  * found the entry in the export table. import the
282  * the prefixes that it covers.
283  * only if the prefix found in the export FIB really is
284  * attached do we want to import its covered
285  */
287  fib_entry_get_flags_i(fib_entry_get(import->faei_export_entry)))
288  {
289  fib_ae_export_t *export;
290 
291  export = fib_entry_ae_add_or_lock(import->faei_export_entry);
292  vec_add1(export->faee_importers, (import - fib_ae_import_pool));
293  fib_ae_export_import_add(export, import);
294  }
295  }
296 
297  /*
298  * track the entry in the export table so we can update appropriately
299  * when it changes.
300  * Exporting prefixes will have allocated new fib_entry_t objects, so the pool
301  * may have realloc'd.
302  */
303  fib_entry = fib_entry_get(fei);
304  import->faei_export_sibling =
305  fib_entry_cover_track(fib_entry_get(import->faei_export_entry), fei);
306 
307  fed = fib_entry_delegate_find_or_add(fib_entry,
309  fed->fd_index = (import - fib_ae_import_pool);
310 }
311 
312 /**
313  * \brief All the imported entries need to be pruged
314  */
315 void
317 {
319 
320  fed = fib_entry_delegate_get(fib_entry,
322 
323  if (NULL != fed)
324  {
325  fib_node_index_t *import_index;
326  fib_entry_t *export_entry;
327  fib_ae_import_t *import;
328  fib_ae_export_t *export;
329 
330  import = pool_elt_at_index(fib_ae_import_pool, fed->fd_index);
331 
332  /*
333  * remove each imported entry
334  */
335  vec_foreach(import_index, import->faei_importeds)
336  {
337  fib_table_entry_delete(import->faei_import_fib,
338  fib_entry_get_prefix(*import_index),
339  FIB_SOURCE_AE);
340  fib_entry_unlock(*import_index);
341  }
342  vec_free(import->faei_importeds);
343 
344  /*
345  * stop tracking the export entry
346  */
347  if (~0 != import->faei_export_sibling)
348  {
349  fib_entry_cover_untrack(fib_entry_get(import->faei_export_entry),
350  import->faei_export_sibling);
351  }
352  import->faei_export_sibling = ~0;
353 
354  /*
355  * remove this import tracker from the export's list,
356  * if it is attached to one. It won't be in the case the tracked
357  * export entry is not an attached exact match.
358  */
359  if (FIB_NODE_INDEX_INVALID != import->faei_exporter)
360  {
362 
363  export_entry = fib_entry_get(import->faei_export_entry);
364 
365  fed = fib_entry_delegate_get(export_entry,
367  ASSERT(NULL != fed);
368 
369  export = pool_elt_at_index(fib_ae_export_pool, fed->fd_index);
370 
371  u32 index = vec_search(export->faee_importers,
372  (import - fib_ae_import_pool));
373 
374  ASSERT(index < vec_len(export->faee_importers));
375  vec_del1(export->faee_importers, index);
376 
377  /*
378  * free the exporter if there are no longer importers
379  */
380  if (0 == --export->faee_locks)
381  {
382  pool_put(fib_ae_export_pool, export);
383  fib_entry_delegate_remove(export_entry,
385  }
386  }
387 
388  /*
389  * free the import tracker
390  */
391  pool_put(fib_ae_import_pool, import);
392  fib_entry_delegate_remove(fib_entry,
394  }
395 }
396 
397 void
399  fib_node_index_t covered)
400 {
402 
403  fed = fib_entry_delegate_get(cover,
405 
406  if (NULL != fed)
407  {
408  /*
409  * the covering prefix is exporting to other tables
410  */
411  fib_node_index_t *import_index;
412  fib_ae_import_t *import;
413  fib_ae_export_t *export;
414 
415  export = pool_elt_at_index(fib_ae_export_pool, fed->fd_index);
416 
417  /*
418  * export the covered entry to each of the importers
419  */
420  vec_foreach(import_index, export->faee_importers)
421  {
422  import = pool_elt_at_index(fib_ae_import_pool, *import_index);
423 
424  fib_entry_import_add(import, covered);
425  }
426  }
427 }
428 
429 void
431  fib_node_index_t covered)
432 {
434 
435  fed = fib_entry_delegate_get(cover,
437 
438  if (NULL != fed)
439  {
440  /*
441  * the covering prefix is exporting to other tables
442  */
443  fib_node_index_t *import_index;
444  fib_ae_import_t *import;
445  fib_ae_export_t *export;
446 
447  export = pool_elt_at_index(fib_ae_export_pool, fed->fd_index);
448 
449  /*
450  * remove the covered entry from each of the importers
451  */
452  vec_foreach(import_index, export->faee_importers)
453  {
454  import = pool_elt_at_index(fib_ae_import_pool, *import_index);
455 
456  fib_entry_import_remove(import, covered);
457  }
458  }
459 }
460 
461 static void
463 {
465 
466  fed = fib_entry_delegate_get(fib_entry,
468 
469  if (NULL != fed)
470  {
471  fib_ae_import_t *import;
472  u32 export_fib;
473 
474  /*
475  * safe the temporaries we need from the existing import
476  * since it will be toast after the purge.
477  */
478  import = pool_elt_at_index(fib_ae_import_pool, fed->fd_index);
479  export_fib = import->faei_export_fib;
480 
481  /*
482  * keep it simple. purge anything that was previously imported.
483  * then re-evaluate the need to import.
484  */
485  fib_attached_export_purge(fib_entry);
486  fib_attached_export_import(fib_entry, export_fib);
487  }
488 }
489 
490 /**
491  * \brief If this entry is tracking a cover (in another table)
492  * then that cover has changed. re-evaluate import.
493  */
494 void
496 {
498 }
499 
500 /**
501  * \brief If this entry is tracking a cover (in another table)
502  * then that cover has been updated. re-evaluate import.
503  */
504 void
506 {
508 }
509 
510 u8*
512  u8* s)
513 {
514  fib_node_index_t *index;
515  fib_ae_import_t *import;
516 
517  import = pool_elt_at_index(fib_ae_import_pool, impi);
518 
519  s = format(s, "\n Attached-Import:%d:[", (import - fib_ae_import_pool));
520  s = format(s, "export-prefix:%U ", format_fib_prefix, &import->faei_prefix);
521  s = format(s, "export-entry:%d ", import->faei_export_entry);
522  s = format(s, "export-sibling:%d ", import->faei_export_sibling);
523  s = format(s, "exporter:%d ", import->faei_exporter);
524  s = format(s, "export-fib:%d ", import->faei_export_fib);
525 
526  s = format(s, "import-entry:%d ", import->faei_import_entry);
527  s = format(s, "import-fib:%d ", import->faei_import_fib);
528 
529  s = format(s, "importeds:[");
530  vec_foreach(index, import->faei_importeds)
531  {
532  s = format(s, "%d, ", *index);
533  }
534  s = format(s, "]]");
535 
536  return (s);
537 }
538 
539 u8*
541  u8* s)
542 {
543  fib_node_index_t *index;
544  fib_ae_export_t *export;
545 
546  export = pool_elt_at_index(fib_ae_export_pool, expi);
547 
548  s = format(s, "\n Attached-Export:%d:[", (export - fib_ae_export_pool));
549  s = format(s, "export-entry:%d ", export->faee_ei);
550 
551  s = format(s, "importers:[");
552  vec_foreach(index, export->faee_importers)
553  {
554  s = format(s, "%d, ", *index);
555  }
556  s = format(s, "]]");
557 
558  return (s);
559 }
void fib_entry_unlock(fib_node_index_t fib_entry_index)
Definition: fib_entry.c:1635
An entry in a FIB table.
Definition: fib_entry.h:462
fib_node_index_t fib_table_lookup_exact_match(u32 fib_index, const fib_prefix_t *prefix)
Perfom an exact match in the non-forwarding table.
Definition: fib_table.c:95
fib_entry_flag_t fib_entry_get_flags_i(const fib_entry_t *fib_entry)
void fib_attached_export_cover_change(fib_entry_t *fib_entry)
If this entry is tracking a cover (in another table) then that cover has changed. ...
void fib_entry_cover_untrack(fib_entry_t *cover, u32 tracked_index)
A description of the need to import routes from the export table.
fib_node_index_t fd_index
Valid for the attached import cases.
static int dpo_id_is_valid(const dpo_id_t *dpoi)
Return true if the DPO object is valid, i.e.
Definition: dpo.h:207
#define NULL
Definition: clib.h:58
clib_memset(h->entries, 0, sizeof(h->entries[0]) *entries)
const dpo_id_t * fib_entry_contribute_ip_forwarding(fib_node_index_t fib_entry_index)
Definition: fib_entry.c:506
#define vec_add1(V, E)
Add 1 element to end of vector (unspecified alignment).
Definition: vec.h:525
fib_node_index_t faei_exporter
The index of the exporter tracker.
fib_node_index_t faei_import_entry
The attached entry in the import table.
Attached Export source.
Definition: fib_entry.h:120
const fib_prefix_t * fib_entry_get_prefix(fib_node_index_t fib_entry_index)
Definition: fib_entry.c:1678
u8 * format(u8 *s, const char *fmt,...)
Definition: format.c:419
fib_node_index_t faei_export_entry
The entry in the epxort table that this importer is importing covereds from.
u32 fe_fib_index
The index of the FIB table this entry is in.
Definition: fib_entry.h:475
Definition: fib_entry.h:277
#define pool_get(P, E)
Allocate an object E from a pool P (unspecified alignment).
Definition: pool.h:236
static void fib_entry_import_add(fib_ae_import_t *import, fib_node_index_t entry_index)
fib_node_index_t faee_ei
THe connected entry this export is acting on behalf of.
unsigned char u8
Definition: types.h:56
void fib_attached_export_covered_added(fib_entry_t *cover, fib_node_index_t covered)
u32 fib_entry_cover_track(fib_entry_t *cover, fib_node_index_t covered)
void fib_attached_export_purge(fib_entry_t *fib_entry)
All the imported entries need to be pruged.
fib_node_index_t faei_export_fib
The FIB index and prefix we are tracking.
void fib_entry_delegate_remove(fib_entry_t *fib_entry, fib_entry_delegate_type_t type)
void fib_table_entry_special_remove(u32 fib_index, const fib_prefix_t *prefix, fib_source_t source)
Remove a &#39;special&#39; entry from the FIB.
Definition: fib_table.c:407
u8 * fib_ae_export_format(fib_node_index_t expi, u8 *s)
u8 * format_fib_prefix(u8 *s, va_list *args)
Definition: fib_types.c:177
Aggregrate type for a prefix.
Definition: fib_types.h:203
fib_node_index_t fib_entry_get_index(const fib_entry_t *fib_entry)
Definition: fib_entry.c:62
unsigned int u32
Definition: types.h:88
#define vec_search(v, E)
Search a vector for the index of the entry that matches.
Definition: vec.h:944
fib_entry_delegate_t * fib_entry_delegate_get(const fib_entry_t *fib_entry, fib_entry_delegate_type_t type)
fib_node_index_t fib_table_lookup(u32 fib_index, const fib_prefix_t *prefix)
Perfom a longest prefix match in the non-forwarding table.
Definition: fib_table.c:66
Attached import/export functionality.
The identity of a DPO is a combination of its type and its instance number/index of objects of that t...
Definition: dpo.h:168
Definition: fib_entry.h:279
#define pool_elt_at_index(p, i)
Returns pointer to element at given index.
Definition: pool.h:511
struct fib_ae_export_t_ fib_ae_export_t
A description of the need to export routes to one or more export tables.
long ctx[MAX_CONNS]
Definition: main.c:144
#define pool_put(P, E)
Free an object E in pool P.
Definition: pool.h:286
#define vec_del1(v, i)
Delete the element at index I.
Definition: vec.h:808
const dpo_id_t * load_balance_get_bucket(index_t lbi, u32 bucket)
Definition: load_balance.c:317
static void fib_ae_export_import_add(fib_ae_export_t *export, fib_ae_import_t *import)
u8 * fib_ae_import_format(fib_node_index_t impi, u8 *s)
u32 faee_locks
Reference counting locks.
void fib_attached_export_covered_removed(fib_entry_t *cover, fib_node_index_t covered)
#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:853
u32 fib_node_index_t
A typedef of a node index.
Definition: fib_types.h:30
fib_entry_t * fib_entry_get(fib_node_index_t index)
Definition: fib_entry.c:50
u32 faei_export_sibling
the sibling index on the cover
void fib_entry_lock(fib_node_index_t fib_entry_index)
Definition: fib_entry.c:1625
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 ASSERT(truth)
A description of the need to export routes to one or more export tables.
fib_prefix_t faei_prefix
fib_node_index_t * faee_importers
The vector/list of import tracker indicies.
void fib_attached_export_cover_update(fib_entry_t *fib_entry)
If this entry is tracking a cover (in another table) then that cover has been updated.
void fib_attached_export_import(fib_entry_t *fib_entry, fib_node_index_t export_fib)
FIB attached export.
void fib_entry_cover_walk(fib_entry_t *cover, fib_entry_covered_walk_t walk, void *args)
static fib_ae_import_t * fib_ae_import_pool
static fib_ae_export_t * fib_ae_export_pool
int fib_prefix_cmp(const fib_prefix_t *p1, const fib_prefix_t *p2)
Compare two prefixes for equality.
Definition: fib_types.c:105
index_t dpoi_index
the index of objects of that type
Definition: dpo.h:184
#define FIB_NODE_INDEX_INVALID
Definition: fib_types.h:31
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
static void fib_entry_import_remove(fib_ae_import_t *import, fib_node_index_t entry_index)
fib_node_index_t * faei_importeds
A vector/list of imported entry indicies.
typedef prefix
Definition: ip_types.api:35
int dpo_is_drop(const dpo_id_t *dpo)
The Drop DPO will drop all packets, no questions asked.
Definition: drop_dpo.c:33
static void fib_attached_export_cover_modified_i(fib_entry_t *fib_entry)
#define vec_foreach(var, vec)
Vector iterator.
static fib_ae_export_t * fib_entry_ae_add_or_lock(fib_node_index_t connected)
fib_node_index_t faei_import_fib
The FIB index we are importing into.
A Delagate is a means to implmenet the Delagation design pattern; the extension of an objects functio...
fib_entry_delegate_t * fib_entry_delegate_find_or_add(fib_entry_t *fib_entry, fib_entry_delegate_type_t fdt)
static int fib_entry_covered_walk_import(fib_entry_t *cover, fib_node_index_t covered, void *ctx)
Call back when walking a connected prefix&#39;s covered prefixes for import.
const fib_prefix_t fe_prefix
The prefix of the route.
Definition: fib_entry.h:471
struct fib_ae_import_t_ fib_ae_import_t
A description of the need to import routes from the export table.
fib_entry_flag_t fib_entry_get_flags(fib_node_index_t fib_entry_index)
Definition: fib_entry.c:301