FD.io VPP  v18.07-rc0-415-g6c78436
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  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  fib_prefix_t prefix;
130  u32 index;
131 
132  /*
133  * find the index in the vector of the entry we are removing
134  */
135  index = vec_search(import->faei_importeds, entry_index);
136 
137  if (index < vec_len(import->faei_importeds))
138  {
139  /*
140  * this is an entry that was previsouly imported
141  */
142  fib_entry_get_prefix(entry_index, &prefix);
143 
144  fib_table_entry_special_remove(import->faei_import_fib,
145  &prefix,
146  FIB_SOURCE_AE);
147 
148  fib_entry_unlock(entry_index);
149  vec_del1(import->faei_importeds, index);
150  }
151 }
152 
153 static void
155  fib_node_index_t entry_index)
156 {
157  fib_node_index_t *existing;
158  fib_prefix_t prefix;
159 
160  /*
161  * ensure we only add the exported entry once, since
162  * sourcing prefixes in the table is reference counted
163  */
164  vec_foreach(existing, import->faei_importeds)
165  {
166  if (*existing == entry_index)
167  {
168  return;
169  }
170  }
171 
172  /*
173  * this is the first time this export entry has been imported
174  * Add it to the import FIB and to the list of importeds
175  */
176  fib_entry_get_prefix(entry_index, &prefix);
177 
178  /*
179  * don't import entries that have the same prefix the import entry
180  */
181  if (0 != fib_prefix_cmp(&prefix,
182  &import->faei_prefix))
183  {
184  const dpo_id_t *dpo;
185 
186  dpo = fib_entry_contribute_ip_forwarding(entry_index);
187 
188  if (dpo_id_is_valid(dpo) && !dpo_is_drop(dpo))
189  {
190  fib_table_entry_special_dpo_add(import->faei_import_fib,
191  &prefix,
193  (fib_entry_get_flags(entry_index) |
196 
197  fib_entry_lock(entry_index);
198  vec_add1(import->faei_importeds, entry_index);
199  }
200  /*
201  * else
202  * the entry currently has no valid forwarding. when it
203  * does it will export itself
204  */
205  }
206 }
207 
208 /**
209  * Call back when walking a connected prefix's covered prefixes for import
210  */
211 static int
213  fib_node_index_t covered,
214  void *ctx)
215 {
216  fib_ae_import_t *import = ctx;
217 
218  fib_entry_import_add(import, covered);
219 
220  return (0);
221 }
222 
223 /*
224  * fib_entry_ae_import_add
225  *
226  * Add an importer to a connected entry
227  */
228 static void
230  fib_ae_import_t *import)
231 {
232  fib_entry_t *entry;
233 
234  import->faei_exporter = (export - fib_ae_export_pool);
235  entry = fib_entry_get(export->faee_ei);
236 
237  fib_entry_cover_walk(entry,
239  import);
240 }
241 
242 void
244  fib_node_index_t export_fib)
245 {
247  fib_ae_import_t *import;
248  fib_node_index_t fei;
249 
250  /*
251  * save index for later post-realloc retreival
252  */
253  fei = fib_entry_get_index(fib_entry);
254 
255  pool_get(fib_ae_import_pool, import);
256 
257  import->faei_import_fib = fib_entry->fe_fib_index;
258  import->faei_export_fib = export_fib;
259  import->faei_prefix = fib_entry->fe_prefix;
260  import->faei_import_entry = fib_entry_get_index(fib_entry);
261  import->faei_export_sibling = ~0;
262 
263  /*
264  * do an exact match in the export table
265  */
266  import->faei_export_entry =
267  fib_table_lookup_exact_match(import->faei_export_fib,
268  &import->faei_prefix);
269 
270  if (FIB_NODE_INDEX_INVALID == import->faei_export_entry)
271  {
272  /*
273  * no exact matching entry in the export table. can't be good.
274  * track the next best thing
275  */
276  import->faei_export_entry =
277  fib_table_lookup(import->faei_export_fib,
278  &import->faei_prefix);
279  import->faei_exporter = FIB_NODE_INDEX_INVALID;
280  }
281  else
282  {
283  /*
284  * found the entry in the export table. import the
285  * the prefixes that it covers.
286  * only if the prefix found in the export FIB really is
287  * attached do we want to import its covered
288  */
290  fib_entry_get_flags_i(fib_entry_get(import->faei_export_entry)))
291  {
292  fib_ae_export_t *export;
293 
294  export = fib_entry_ae_add_or_lock(import->faei_export_entry);
295  vec_add1(export->faee_importers, (import - fib_ae_import_pool));
296  fib_ae_export_import_add(export, import);
297  }
298  }
299 
300  /*
301  * track the entry in the export table so we can update appropriately
302  * when it changes.
303  * Exporting prefixes will have allocated new fib_entry_t objects, so the pool
304  * may have realloc'd.
305  */
306  fib_entry = fib_entry_get(fei);
307  import->faei_export_sibling =
308  fib_entry_cover_track(fib_entry_get(import->faei_export_entry), fei);
309 
310  fed = fib_entry_delegate_find_or_add(fib_entry,
312  fed->fd_index = (import - fib_ae_import_pool);
313 }
314 
315 /**
316  * \brief All the imported entries need to be pruged
317  */
318 void
320 {
322 
323  fed = fib_entry_delegate_get(fib_entry,
325 
326  if (NULL != fed)
327  {
328  fib_node_index_t *import_index;
329  fib_entry_t *export_entry;
330  fib_ae_import_t *import;
331  fib_ae_export_t *export;
332 
333  import = pool_elt_at_index(fib_ae_import_pool, fed->fd_index);
334 
335  /*
336  * remove each imported entry
337  */
338  vec_foreach(import_index, import->faei_importeds)
339  {
340  fib_prefix_t prefix;
341 
342  fib_entry_get_prefix(*import_index, &prefix);
343 
344  fib_table_entry_delete(import->faei_import_fib,
345  &prefix,
346  FIB_SOURCE_AE);
347  fib_entry_unlock(*import_index);
348  }
349  vec_free(import->faei_importeds);
350 
351  /*
352  * stop tracking the export entry
353  */
354  if (~0 != import->faei_export_sibling)
355  {
356  fib_entry_cover_untrack(fib_entry_get(import->faei_export_entry),
357  import->faei_export_sibling);
358  }
359  import->faei_export_sibling = ~0;
360 
361  /*
362  * remove this import tracker from the export's list,
363  * if it is attached to one. It won't be in the case the tracked
364  * export entry is not an attached exact match.
365  */
366  if (FIB_NODE_INDEX_INVALID != import->faei_exporter)
367  {
369 
370  export_entry = fib_entry_get(import->faei_export_entry);
371 
372  fed = fib_entry_delegate_get(export_entry,
374  ASSERT(NULL != fed);
375 
376  export = pool_elt_at_index(fib_ae_export_pool, fed->fd_index);
377 
378  u32 index = vec_search(export->faee_importers,
379  (import - fib_ae_import_pool));
380 
381  ASSERT(index < vec_len(export->faee_importers));
382  vec_del1(export->faee_importers, index);
383 
384  /*
385  * free the exporter if there are no longer importers
386  */
387  if (0 == --export->faee_locks)
388  {
389  pool_put(fib_ae_export_pool, export);
390  fib_entry_delegate_remove(export_entry,
392  }
393  }
394 
395  /*
396  * free the import tracker
397  */
398  pool_put(fib_ae_import_pool, import);
399  fib_entry_delegate_remove(fib_entry,
401  }
402 }
403 
404 void
406  fib_node_index_t covered)
407 {
409 
410  fed = fib_entry_delegate_get(cover,
412 
413  if (NULL != fed)
414  {
415  /*
416  * the covering prefix is exporting to other tables
417  */
418  fib_node_index_t *import_index;
419  fib_ae_import_t *import;
420  fib_ae_export_t *export;
421 
422  export = pool_elt_at_index(fib_ae_export_pool, fed->fd_index);
423 
424  /*
425  * export the covered entry to each of the importers
426  */
427  vec_foreach(import_index, export->faee_importers)
428  {
429  import = pool_elt_at_index(fib_ae_import_pool, *import_index);
430 
431  fib_entry_import_add(import, covered);
432  }
433  }
434 }
435 
436 void
438  fib_node_index_t covered)
439 {
441 
442  fed = fib_entry_delegate_get(cover,
444 
445  if (NULL != fed)
446  {
447  /*
448  * the covering prefix is exporting to other tables
449  */
450  fib_node_index_t *import_index;
451  fib_ae_import_t *import;
452  fib_ae_export_t *export;
453 
454  export = pool_elt_at_index(fib_ae_export_pool, fed->fd_index);
455 
456  /*
457  * remove the covered entry from each of the importers
458  */
459  vec_foreach(import_index, export->faee_importers)
460  {
461  import = pool_elt_at_index(fib_ae_import_pool, *import_index);
462 
463  fib_entry_import_remove(import, covered);
464  }
465  }
466 }
467 
468 static void
470 {
472 
473  fed = fib_entry_delegate_get(fib_entry,
475 
476  if (NULL != fed)
477  {
478  fib_ae_import_t *import;
479  u32 export_fib;
480 
481  /*
482  * safe the temporaries we need from the existing import
483  * since it will be toast after the purge.
484  */
485  import = pool_elt_at_index(fib_ae_import_pool, fed->fd_index);
486  export_fib = import->faei_export_fib;
487 
488  /*
489  * keep it simple. purge anything that was previously imported.
490  * then re-evaluate the need to import.
491  */
492  fib_attached_export_purge(fib_entry);
493  fib_attached_export_import(fib_entry, export_fib);
494  }
495 }
496 
497 /**
498  * \brief If this entry is tracking a cover (in another table)
499  * then that cover has changed. re-evaluate import.
500  */
501 void
503 {
505 }
506 
507 /**
508  * \brief If this entry is tracking a cover (in another table)
509  * then that cover has been updated. re-evaluate import.
510  */
511 void
513 {
515 }
516 
517 u8*
519  u8* s)
520 {
521  fib_node_index_t *index;
522  fib_ae_import_t *import;
523 
524  import = pool_elt_at_index(fib_ae_import_pool, impi);
525 
526  s = format(s, "\n Attached-Import:%d:[", (import - fib_ae_import_pool));
527  s = format(s, "export-prefix:%U ", format_fib_prefix, &import->faei_prefix);
528  s = format(s, "export-entry:%d ", import->faei_export_entry);
529  s = format(s, "export-sibling:%d ", import->faei_export_sibling);
530  s = format(s, "exporter:%d ", import->faei_exporter);
531  s = format(s, "export-fib:%d ", import->faei_export_fib);
532 
533  s = format(s, "import-entry:%d ", import->faei_import_entry);
534  s = format(s, "import-fib:%d ", import->faei_import_fib);
535 
536  s = format(s, "importeds:[");
537  vec_foreach(index, import->faei_importeds)
538  {
539  s = format(s, "%d, ", *index);
540  }
541  s = format(s, "]]");
542 
543  return (s);
544 }
545 
546 u8*
548  u8* s)
549 {
550  fib_node_index_t *index;
551  fib_ae_export_t *export;
552 
553  export = pool_elt_at_index(fib_ae_export_pool, expi);
554 
555  s = format(s, "\n Attached-Export:%d:[", (export - fib_ae_export_pool));
556  s = format(s, "export-entry:%d ", export->faee_ei);
557 
558  s = format(s, "importers:[");
559  vec_foreach(index, export->faee_importers)
560  {
561  s = format(s, "%d, ", *index);
562  }
563  s = format(s, "]]");
564 
565  return (s);
566 }
void fib_entry_unlock(fib_node_index_t fib_entry_index)
Definition: fib_entry.c:1587
An entry in a FIB table.
Definition: fib_entry.h:453
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
void fib_entry_get_prefix(fib_node_index_t fib_entry_index, fib_prefix_t *pfx)
Definition: fib_entry.c:1616
#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:478
#define vec_add1(V, E)
Add 1 element to end of vector (unspecified alignment).
Definition: vec.h:523
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:116
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:466
Definition: fib_entry.h:272
#define pool_get(P, E)
Allocate an object E from a pool P (unspecified alignment).
Definition: pool.h:227
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:176
Aggregrate type for a prefix.
Definition: fib_types.h:188
fib_node_index_t fib_entry_get_index(const fib_entry_t *fib_entry)
Definition: fib_entry.c:57
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:942
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:274
#define pool_elt_at_index(p, i)
Returns pointer to element at given index.
Definition: pool.h:461
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:273
#define vec_del1(v, i)
Delete the element at index I.
Definition: vec.h:806
const dpo_id_t * load_balance_get_bucket(index_t lbi, u32 bucket)
Definition: load_balance.c:294
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:339
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:45
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:1577
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)
long ctx[MAX_CONNS]
Definition: main.c:126
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:104
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.
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:462
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:276