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:
7 * http://www.apache.org/licenses/LICENSE-2.0
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.
16 #include <vnet/fib/fib_entry.h>
17 #include <vnet/fib/fib_table.h>
19 #include <vnet/fib/fib_attached_export.h>
20 #include <vnet/fib/fib_entry_cover.h>
21 #include <vnet/fib/fib_entry_src.h>
22 #include <vnet/fib/fib_entry_delegate.h>
25 * A description of the need to import routes from the export table
27 typedef struct fib_ae_import_t_
30 * The entry in the epxort table that this importer
31 * is importing covereds from
33 fib_node_index_t faei_export_entry;
36 * The attached entry in the import table
38 fib_node_index_t faei_import_entry;
40 * the sibling index on the cover
42 u32 faei_export_sibling;
45 * The index of the exporter tracker. Not set if the
46 * export entry is not valid for export
48 fib_node_index_t faei_exporter;
51 * A vector/list of imported entry indicies
53 fib_node_index_t *faei_importeds;
56 * The FIB index and prefix we are tracking
58 fib_node_index_t faei_export_fib;
59 fib_prefix_t faei_prefix;
62 * The FIB index we are importing into
64 fib_node_index_t faei_import_fib;
68 * A description of the need to export routes to one or more export tables
70 typedef struct fib_ae_export_t_ {
72 * The vector/list of import tracker indicies
74 fib_node_index_t *faee_importers;
77 * THe connected entry this export is acting on behalf of
79 fib_node_index_t faee_ei;
82 * Reference counting locks
88 * memory pools for the importers and exportes
90 static fib_ae_import_t *fib_ae_import_pool;
91 static fib_ae_export_t *fib_ae_export_pool;
93 static fib_ae_export_t *
94 fib_entry_ae_add_or_lock (fib_node_index_t connected)
96 fib_entry_delegate_t *fed;
97 fib_ae_export_t *export;
100 entry = fib_entry_get(connected);
101 fed = fib_entry_delegate_get(entry,
102 FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
106 fed = fib_entry_delegate_find_or_add(entry,
107 FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
108 pool_get(fib_ae_export_pool, export);
109 memset(export, 0, sizeof(*export));
111 fed->fd_index = (export - fib_ae_export_pool);
112 export->faee_ei = connected;
116 export = pool_elt_at_index(fib_ae_export_pool, fed->fd_index);
119 export->faee_locks++;
125 fib_entry_import_remove (fib_ae_import_t *import,
126 fib_node_index_t entry_index)
132 * find the index in the vector of the entry we are removing
134 index = vec_search(import->faei_importeds, entry_index);
136 if (index < vec_len(import->faei_importeds))
139 * this is an entry that was previsouly imported
141 fib_entry_get_prefix(entry_index, &prefix);
143 fib_table_entry_special_remove(import->faei_import_fib,
147 fib_entry_unlock(entry_index);
148 vec_del1(import->faei_importeds, index);
153 fib_entry_import_add (fib_ae_import_t *import,
154 fib_node_index_t entry_index)
156 fib_node_index_t *existing;
160 * ensure we only add the exported entry once, since
161 * sourcing prefixes in the table is reference counted
163 vec_foreach(existing, import->faei_importeds)
165 if (*existing == entry_index)
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
175 fib_entry_get_prefix(entry_index, &prefix);
178 * don't import entries that have the same prefix the import entry
180 if (0 != fib_prefix_cmp(&prefix,
181 &import->faei_prefix))
185 dpo = fib_entry_contribute_ip_forwarding(entry_index);
187 if (dpo_id_is_valid(dpo))
189 fib_table_entry_special_dpo_add(import->faei_import_fib,
192 (fib_entry_get_flags(entry_index) |
193 FIB_ENTRY_FLAG_EXCLUSIVE),
194 load_balance_get_bucket(dpo->dpoi_index, 0));
196 fib_entry_lock(entry_index);
197 vec_add1(import->faei_importeds, entry_index);
201 * the entry currently has no valid forwarding. when it
202 * does it will export itself
208 * Call back when walking a connected prefix's covered prefixes for import
211 fib_entry_covered_walk_import (fib_entry_t *cover,
212 fib_node_index_t covered,
215 fib_ae_import_t *import = ctx;
217 fib_entry_import_add(import, covered);
223 * fib_entry_ae_import_add
225 * Add an importer to a connected entry
228 fib_ae_export_import_add (fib_ae_export_t *export,
229 fib_ae_import_t *import)
233 import->faei_exporter = (export - fib_ae_export_pool);
234 entry = fib_entry_get(export->faee_ei);
236 fib_entry_cover_walk(entry,
237 fib_entry_covered_walk_import,
242 fib_attached_export_import (fib_entry_t *fib_entry,
243 fib_node_index_t export_fib)
245 fib_entry_delegate_t *fed;
246 fib_ae_import_t *import;
247 fib_node_index_t fei;
250 * save index for later post-realloc retreival
252 fei = fib_entry_get_index(fib_entry);
254 pool_get(fib_ae_import_pool, import);
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;
263 * do an exact match in the export table
265 import->faei_export_entry =
266 fib_table_lookup_exact_match(import->faei_export_fib,
267 &import->faei_prefix);
269 if (FIB_NODE_INDEX_INVALID == import->faei_export_entry)
272 * no exact matching entry in the export table. can't be good.
273 * track the next best thing
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;
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
288 if (FIB_ENTRY_FLAG_ATTACHED &
289 fib_entry_get_flags_i(fib_entry_get(import->faei_export_entry)))
291 fib_ae_export_t *export;
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);
300 * track the entry in the export table so we can update appropriately
302 * Exporting prefixes will have allocated new fib_entry_t objects, so the pool
303 * may have realloc'd.
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);
309 fed = fib_entry_delegate_find_or_add(fib_entry,
310 FIB_ENTRY_DELEGATE_ATTACHED_IMPORT);
311 fed->fd_index = (import - fib_ae_import_pool);
315 * \brief All the imported entries need to be pruged
318 fib_attached_export_purge (fib_entry_t *fib_entry)
320 fib_entry_delegate_t *fed;
322 fed = fib_entry_delegate_get(fib_entry,
323 FIB_ENTRY_DELEGATE_ATTACHED_IMPORT);
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;
332 import = pool_elt_at_index(fib_ae_import_pool, fed->fd_index);
335 * remove each imported entry
337 vec_foreach(import_index, import->faei_importeds)
341 fib_entry_get_prefix(*import_index, &prefix);
343 fib_table_entry_delete(import->faei_import_fib,
346 fib_entry_unlock(*import_index);
348 vec_free(import->faei_importeds);
351 * stop tracking the export entry
353 if (~0 != import->faei_export_sibling)
355 fib_entry_cover_untrack(fib_entry_get(import->faei_export_entry),
356 import->faei_export_sibling);
358 import->faei_export_sibling = ~0;
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.
365 if (FIB_NODE_INDEX_INVALID != import->faei_exporter)
367 fib_entry_delegate_t *fed;
369 export_entry = fib_entry_get(import->faei_export_entry);
371 fed = fib_entry_delegate_get(export_entry,
372 FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
375 export = pool_elt_at_index(fib_ae_export_pool, fed->fd_index);
377 u32 index = vec_search(export->faee_importers,
378 (import - fib_ae_import_pool));
380 ASSERT(index < vec_len(export->faee_importers));
381 vec_del1(export->faee_importers, index);
384 * free the exporter if there are no longer importers
386 if (0 == --export->faee_locks)
388 pool_put(fib_ae_export_pool, export);
389 fib_entry_delegate_remove(export_entry,
390 FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
395 * free the import tracker
397 pool_put(fib_ae_import_pool, import);
398 fib_entry_delegate_remove(fib_entry,
399 FIB_ENTRY_DELEGATE_ATTACHED_IMPORT);
404 fib_attached_export_covered_added (fib_entry_t *cover,
405 fib_node_index_t covered)
407 fib_entry_delegate_t *fed;
409 fed = fib_entry_delegate_get(cover,
410 FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
415 * the covering prefix is exporting to other tables
417 fib_node_index_t *import_index;
418 fib_ae_import_t *import;
419 fib_ae_export_t *export;
421 export = pool_elt_at_index(fib_ae_export_pool, fed->fd_index);
424 * export the covered entry to each of the importers
426 vec_foreach(import_index, export->faee_importers)
428 import = pool_elt_at_index(fib_ae_import_pool, *import_index);
430 fib_entry_import_add(import, covered);
436 fib_attached_export_covered_removed (fib_entry_t *cover,
437 fib_node_index_t covered)
439 fib_entry_delegate_t *fed;
441 fed = fib_entry_delegate_get(cover,
442 FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
447 * the covering prefix is exporting to other tables
449 fib_node_index_t *import_index;
450 fib_ae_import_t *import;
451 fib_ae_export_t *export;
453 export = pool_elt_at_index(fib_ae_export_pool, fed->fd_index);
456 * remove the covered entry from each of the importers
458 vec_foreach(import_index, export->faee_importers)
460 import = pool_elt_at_index(fib_ae_import_pool, *import_index);
462 fib_entry_import_remove(import, covered);
468 fib_attached_export_cover_modified_i (fib_entry_t *fib_entry)
470 fib_entry_delegate_t *fed;
472 fed = fib_entry_delegate_get(fib_entry,
473 FIB_ENTRY_DELEGATE_ATTACHED_IMPORT);
477 fib_ae_import_t *import;
481 * safe the temporaries we need from the existing import
482 * since it will be toast after the purge.
484 import = pool_elt_at_index(fib_ae_import_pool, fed->fd_index);
485 export_fib = import->faei_export_fib;
488 * keep it simple. purge anything that was previously imported.
489 * then re-evaluate the need to import.
491 fib_attached_export_purge(fib_entry);
492 fib_attached_export_import(fib_entry, export_fib);
497 * \brief If this entry is tracking a cover (in another table)
498 * then that cover has changed. re-evaluate import.
501 fib_attached_export_cover_change (fib_entry_t *fib_entry)
503 fib_attached_export_cover_modified_i(fib_entry);
507 * \brief If this entry is tracking a cover (in another table)
508 * then that cover has been updated. re-evaluate import.
511 fib_attached_export_cover_update (fib_entry_t *fib_entry)
513 fib_attached_export_cover_modified_i(fib_entry);
517 fib_ae_import_format (fib_entry_t *fib_entry,
520 fib_entry_delegate_t *fed;
522 fed = fib_entry_delegate_get(fib_entry,
523 FIB_ENTRY_DELEGATE_ATTACHED_IMPORT);
527 fib_node_index_t *index;
528 fib_ae_import_t *import;
530 import = pool_elt_at_index(fib_ae_import_pool, fed->fd_index);
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);
539 s = format(s, "import-entry:%d ", import->faei_import_entry);
540 s = format(s, "import-fib:%d ", import->faei_import_fib);
542 s = format(s, "importeds:[");
543 vec_foreach(index, import->faei_importeds)
545 s = format(s, "%d, ", *index);
554 fib_ae_export_format (fib_entry_t *fib_entry,
557 fib_entry_delegate_t *fed;
559 fed = fib_entry_delegate_get(fib_entry,
560 FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
564 fib_node_index_t *index;
565 fib_ae_export_t *export;
567 export = pool_elt_at_index(fib_ae_export_pool, fed->fd_list);
569 s = format(s, "\n Attached-Export:%d:[", (export - fib_ae_export_pool));
570 s = format(s, "export-entry:%d ", export->faee_ei);
572 s = format(s, "importers:[");
573 vec_foreach(index, export->faee_importers)
575 s = format(s, "%d, ", *index);