FD.io VPP  v17.04.2-2-ga8f93f8
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 
24 /**
25  * A description of the need to import routes from the export table
26  */
27 typedef struct fib_ae_import_t_
28 {
29  /**
30  * The entry in the epxort table that this importer
31  * is importing covereds from
32  */
34 
35  /**
36  * The attached entry in the import table
37  */
39  /**
40  * the sibling index on the cover
41  */
43 
44  /**
45  * The index of the exporter tracker. Not set if the
46  * export entry is not valid for export
47  */
49 
50  /**
51  * A vector/list of imported entry indicies
52  */
54 
55  /**
56  * The FIB index and prefix we are tracking
57  */
60 
61  /**
62  * The FIB index we are importing into
63  */
66 
67 /**
68  * A description of the need to export routes to one or more export tables
69  */
70 typedef struct fib_ae_export_t_ {
71  /**
72  * The vector/list of import tracker indicies
73  */
75 
76  /**
77  * THe connected entry this export is acting on behalf of
78  */
80 
81  /**
82  * Reference counting locks
83  */
86 
87 /*
88  * memory pools for the importers and exportes
89  */
92 
93 static fib_ae_export_t *
95 {
97  fib_ae_export_t *export;
98  fib_entry_t *entry;
99 
100  entry = fib_entry_get(connected);
101  fed = fib_entry_delegate_get(entry,
103 
104  if (NULL == fed)
105  {
106  fed = fib_entry_delegate_find_or_add(entry,
108  pool_get(fib_ae_export_pool, export);
109  memset(export, 0, sizeof(*export));
110 
111  fed->fd_index = (export - fib_ae_export_pool);
112  export->faee_ei = connected;
113  }
114  else
115  {
116  export = pool_elt_at_index(fib_ae_export_pool, fed->fd_index);
117  }
118 
119  export->faee_locks++;
120 
121  return (export);
122 }
123 
124 static void
126  fib_node_index_t entry_index)
127 {
128  fib_prefix_t prefix;
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_entry_get_prefix(entry_index, &prefix);
142 
143  fib_table_entry_special_remove(import->faei_import_fib,
144  &prefix,
145  FIB_SOURCE_AE);
146 
147  fib_entry_unlock(entry_index);
148  vec_del1(import->faei_importeds, index);
149  }
150 }
151 
152 static void
154  fib_node_index_t entry_index)
155 {
156  fib_node_index_t *existing;
157  fib_prefix_t prefix;
158 
159  /*
160  * ensure we only add the exported entry once, since
161  * sourcing prefixes in the table is reference counted
162  */
163  vec_foreach(existing, import->faei_importeds)
164  {
165  if (*existing == entry_index)
166  {
167  return;
168  }
169  }
170 
171  /*
172  * this is the first time this export entry has been imported
173  * Add it to the import FIB and to the list of importeds
174  */
175  fib_entry_get_prefix(entry_index, &prefix);
176 
177  /*
178  * don't import entries that have the same prefix the import entry
179  */
180  if (0 != fib_prefix_cmp(&prefix,
181  &import->faei_prefix))
182  {
183  const dpo_id_t *dpo;
184 
185  dpo = fib_entry_contribute_ip_forwarding(entry_index);
186 
187  if (dpo_id_is_valid(dpo))
188  {
189  fib_table_entry_special_dpo_add(import->faei_import_fib,
190  &prefix,
192  (fib_entry_get_flags(entry_index) |
195 
196  fib_entry_lock(entry_index);
197  vec_add1(import->faei_importeds, entry_index);
198  }
199  /*
200  * else
201  * the entry currently has no valid forwarding. when it
202  * does it will export itself
203  */
204  }
205 }
206 
207 /**
208  * Call back when walking a connected prefix's covered prefixes for import
209  */
210 static int
212  fib_node_index_t covered,
213  void *ctx)
214 {
215  fib_ae_import_t *import = ctx;
216 
217  fib_entry_import_add(import, covered);
218 
219  return (0);
220 }
221 
222 /*
223  * fib_entry_ae_import_add
224  *
225  * Add an importer to a connected entry
226  */
227 static void
229  fib_ae_import_t *import)
230 {
231  fib_entry_t *entry;
232 
233  import->faei_exporter = (export - fib_ae_export_pool);
234  entry = fib_entry_get(export->faee_ei);
235 
236  fib_entry_cover_walk(entry,
238  import);
239 }
240 
241 void
243  fib_node_index_t export_fib)
244 {
246  fib_ae_import_t *import;
247  fib_node_index_t fei;
248 
249  /*
250  * save index for later post-realloc retreival
251  */
252  fei = fib_entry_get_index(fib_entry);
253 
254  pool_get(fib_ae_import_pool, import);
255 
256  import->faei_import_fib = fib_entry->fe_fib_index;
257  import->faei_export_fib = export_fib;
258  import->faei_prefix = fib_entry->fe_prefix;
259  import->faei_import_entry = fib_entry_get_index(fib_entry);
260  import->faei_export_sibling = ~0;
261 
262  /*
263  * do an exact match in the export table
264  */
265  import->faei_export_entry =
266  fib_table_lookup_exact_match(import->faei_export_fib,
267  &import->faei_prefix);
268 
269  if (FIB_NODE_INDEX_INVALID == import->faei_export_entry)
270  {
271  /*
272  * no exact matching entry in the export table. can't be good.
273  * track the next best thing
274  */
275  import->faei_export_entry =
276  fib_table_lookup(import->faei_export_fib,
277  &import->faei_prefix);
278  import->faei_exporter = FIB_NODE_INDEX_INVALID;
279  }
280  else
281  {
282  /*
283  * found the entry in the export table. import the
284  * the prefixes that it covers.
285  * only if the prefix found in the export FIB really is
286  * attached do we want to import its covered
287  */
289  fib_entry_get_flags_i(fib_entry_get(import->faei_export_entry)))
290  {
291  fib_ae_export_t *export;
292 
293  export = fib_entry_ae_add_or_lock(import->faei_export_entry);
294  vec_add1(export->faee_importers, (import - fib_ae_import_pool));
295  fib_ae_export_import_add(export, import);
296  }
297  }
298 
299  /*
300  * track the entry in the export table so we can update appropriately
301  * when it changes.
302  * Exporting prefixes will have allocated new fib_entry_t objects, so the pool
303  * may have realloc'd.
304  */
305  fib_entry = fib_entry_get(fei);
306  import->faei_export_sibling =
307  fib_entry_cover_track(fib_entry_get(import->faei_export_entry), fei);
308 
309  fed = fib_entry_delegate_find_or_add(fib_entry,
311  fed->fd_index = (import - fib_ae_import_pool);
312 }
313 
314 /**
315  * \brief All the imported entries need to be pruged
316  */
317 void
319 {
321 
322  fed = fib_entry_delegate_get(fib_entry,
324 
325  if (NULL != fed)
326  {
327  fib_node_index_t *import_index;
328  fib_entry_t *export_entry;
329  fib_ae_import_t *import;
330  fib_ae_export_t *export;
331 
332  import = pool_elt_at_index(fib_ae_import_pool, fed->fd_index);
333 
334  /*
335  * remove each imported entry
336  */
337  vec_foreach(import_index, import->faei_importeds)
338  {
339  fib_prefix_t prefix;
340 
341  fib_entry_get_prefix(*import_index, &prefix);
342 
343  fib_table_entry_delete(import->faei_import_fib,
344  &prefix,
345  FIB_SOURCE_AE);
346  fib_entry_unlock(*import_index);
347  }
348  vec_free(import->faei_importeds);
349 
350  /*
351  * stop tracking the export entry
352  */
353  if (~0 != import->faei_export_sibling)
354  {
355  fib_entry_cover_untrack(fib_entry_get(import->faei_export_entry),
356  import->faei_export_sibling);
357  }
358  import->faei_export_sibling = ~0;
359 
360  /*
361  * remove this import tracker from the export's list,
362  * if it is attached to one. It won't be in the case the tracked
363  * export entry is not an attached exact match.
364  */
365  if (FIB_NODE_INDEX_INVALID != import->faei_exporter)
366  {
368 
369  export_entry = fib_entry_get(import->faei_export_entry);
370 
371  fed = fib_entry_delegate_get(export_entry,
373  ASSERT(NULL != fed);
374 
375  export = pool_elt_at_index(fib_ae_export_pool, fed->fd_index);
376 
377  u32 index = vec_search(export->faee_importers,
378  (import - fib_ae_import_pool));
379 
380  ASSERT(index < vec_len(export->faee_importers));
381  vec_del1(export->faee_importers, index);
382 
383  /*
384  * free the exporter if there are no longer importers
385  */
386  if (0 == --export->faee_locks)
387  {
388  pool_put(fib_ae_export_pool, export);
389  fib_entry_delegate_remove(export_entry,
391  }
392  }
393 
394  /*
395  * free the import tracker
396  */
397  pool_put(fib_ae_import_pool, import);
398  fib_entry_delegate_remove(fib_entry,
400  }
401 }
402 
403 void
405  fib_node_index_t covered)
406 {
408 
409  fed = fib_entry_delegate_get(cover,
411 
412  if (NULL != fed)
413  {
414  /*
415  * the covering prefix is exporting to other tables
416  */
417  fib_node_index_t *import_index;
418  fib_ae_import_t *import;
419  fib_ae_export_t *export;
420 
421  export = pool_elt_at_index(fib_ae_export_pool, fed->fd_index);
422 
423  /*
424  * export the covered entry to each of the importers
425  */
426  vec_foreach(import_index, export->faee_importers)
427  {
428  import = pool_elt_at_index(fib_ae_import_pool, *import_index);
429 
430  fib_entry_import_add(import, covered);
431  }
432  }
433 }
434 
435 void
437  fib_node_index_t covered)
438 {
440 
441  fed = fib_entry_delegate_get(cover,
443 
444  if (NULL != fed)
445  {
446  /*
447  * the covering prefix is exporting to other tables
448  */
449  fib_node_index_t *import_index;
450  fib_ae_import_t *import;
451  fib_ae_export_t *export;
452 
453  export = pool_elt_at_index(fib_ae_export_pool, fed->fd_index);
454 
455  /*
456  * remove the covered entry from each of the importers
457  */
458  vec_foreach(import_index, export->faee_importers)
459  {
460  import = pool_elt_at_index(fib_ae_import_pool, *import_index);
461 
462  fib_entry_import_remove(import, covered);
463  }
464  }
465 }
466 
467 static void
469 {
471 
472  fed = fib_entry_delegate_get(fib_entry,
474 
475  if (NULL != fed)
476  {
477  fib_ae_import_t *import;
478  u32 export_fib;
479 
480  /*
481  * safe the temporaries we need from the existing import
482  * since it will be toast after the purge.
483  */
484  import = pool_elt_at_index(fib_ae_import_pool, fed->fd_index);
485  export_fib = import->faei_export_fib;
486 
487  /*
488  * keep it simple. purge anything that was previously imported.
489  * then re-evaluate the need to import.
490  */
491  fib_attached_export_purge(fib_entry);
492  fib_attached_export_import(fib_entry, export_fib);
493  }
494 }
495 
496 /**
497  * \brief If this entry is tracking a cover (in another table)
498  * then that cover has changed. re-evaluate import.
499  */
500 void
502 {
504 }
505 
506 /**
507  * \brief If this entry is tracking a cover (in another table)
508  * then that cover has been updated. re-evaluate import.
509  */
510 void
512 {
514 }
515 
516 u8*
518  u8* s)
519 {
521 
522  fed = fib_entry_delegate_get(fib_entry,
524 
525  if (NULL != fed)
526  {
527  fib_node_index_t *index;
528  fib_ae_import_t *import;
529 
530  import = pool_elt_at_index(fib_ae_import_pool, fed->fd_index);
531 
532  s = format(s, "\n Attached-Import:%d:[", (import - fib_ae_import_pool));
533  s = format(s, "export-prefix:%U ", format_fib_prefix, &import->faei_prefix);
534  s = format(s, "export-entry:%d ", import->faei_export_entry);
535  s = format(s, "export-sibling:%d ", import->faei_export_sibling);
536  s = format(s, "exporter:%d ", import->faei_exporter);
537  s = format(s, "export-fib:%d ", import->faei_export_fib);
538 
539  s = format(s, "import-entry:%d ", import->faei_import_entry);
540  s = format(s, "import-fib:%d ", import->faei_import_fib);
541 
542  s = format(s, "importeds:[");
543  vec_foreach(index, import->faei_importeds)
544  {
545  s = format(s, "%d, ", *index);
546  }
547  s = format(s, "]]");
548  }
549 
550  return (s);
551 }
552 
553 u8*
555  u8* s)
556 {
558 
559  fed = fib_entry_delegate_get(fib_entry,
561 
562  if (NULL != fed)
563  {
564  fib_node_index_t *index;
565  fib_ae_export_t *export;
566 
567  export = pool_elt_at_index(fib_ae_export_pool, fed->fd_list);
568 
569  s = format(s, "\n Attached-Export:%d:[", (export - fib_ae_export_pool));
570  s = format(s, "export-entry:%d ", export->faee_ei);
571 
572  s = format(s, "importers:[");
573  vec_foreach(index, export->faee_importers)
574  {
575  s = format(s, "%d, ", *index);
576  }
577  s = format(s, "]]");
578  }
579  return (s);
580 }
void fib_entry_unlock(fib_node_index_t fib_entry_index)
Definition: fib_entry.c:1427
An entry in a FIB table.
Definition: fib_entry.h:373
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:185
void fib_entry_get_prefix(fib_node_index_t fib_entry_index, fib_prefix_t *pfx)
Definition: fib_entry.c:1456
#define NULL
Definition: clib.h:55
const dpo_id_t * fib_entry_contribute_ip_forwarding(fib_node_index_t fib_entry_index)
Definition: fib_entry.c:432
#define vec_add1(V, E)
Add 1 element to end of vector (unspecified alignment).
Definition: vec.h:522
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:104
u8 * format(u8 *s, const char *fmt,...)
Definition: format.c:418
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:386
Definition: fib_entry.h:229
#define pool_get(P, E)
Allocate an object E from a pool P (unspecified alignment).
Definition: pool.h:200
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.
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:388
u8 * format_fib_prefix(u8 *s, va_list *args)
Definition: fib_types.c:150
Aggregrate type for a prefix.
Definition: fib_types.h:160
fib_node_index_t fib_entry_get_index(const fib_entry_t *fib_entry)
Definition: fib_entry.c:56
#define vec_search(v, E)
Search a vector for the index of the entry that matches.
Definition: vec.h:941
fib_entry_delegate_t * fib_entry_delegate_get(const fib_entry_t *fib_entry, fib_entry_delegate_type_t type)
fib_node_list_t fd_list
For the cover tracking.
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:146
Definition: fib_entry.h:231
#define pool_elt_at_index(p, i)
Returns pointer to element at given index.
Definition: pool.h:397
struct fib_ae_export_t_ fib_ae_export_t
A description of the need to export routes to one or more export tables.
#define pool_put(P, E)
Free an object E in pool P.
Definition: pool.h:241
#define vec_del1(v, i)
Delete the element at index I.
Definition: vec.h:805
const dpo_id_t * load_balance_get_bucket(index_t lbi, u32 bucket)
Definition: load_balance.c:282
static void fib_ae_export_import_add(fib_ae_export_t *export, fib_ae_import_t *import)
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: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
u8 * fib_ae_export_format(fib_entry_t *fib_entry, u8 *s)
u32 fib_node_index_t
A typedef of a node index.
Definition: fib_types.h:28
fib_entry_t * fib_entry_get(fib_node_index_t index)
Definition: fib_entry.c:44
u32 faei_export_sibling
the sibling index on the cover
u8 * fib_ae_import_format(fib_entry_t *fib_entry, u8 *s)
void fib_entry_lock(fib_node_index_t fib_entry_index)
Definition: fib_entry.c:1417
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 ASSERT(truth)
unsigned int u32
Definition: types.h:88
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:78
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 vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
unsigned char u8
Definition: types.h:56
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.
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:382
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:278