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>
23 #include <vnet/dpo/drop_dpo.h>
26 * A description of the need to import routes from the export table
28 typedef struct fib_ae_import_t_
31 * The entry in the export table that this importer
32 * is importing covereds from
34 fib_node_index_t faei_export_entry;
37 * The attached entry in the import table
39 fib_node_index_t faei_import_entry;
41 * the sibling index on the cover
43 u32 faei_export_sibling;
46 * The index of the exporter tracker. Not set if the
47 * export entry is not valid for export
49 fib_node_index_t faei_exporter;
52 * A vector/list of imported entry indicies
54 fib_node_index_t *faei_importeds;
57 * The FIB index and prefix we are tracking
59 fib_node_index_t faei_export_fib;
60 fib_prefix_t faei_prefix;
63 * The FIB index we are importing into
65 fib_node_index_t faei_import_fib;
69 * A description of the need to export routes to one or more export tables
71 typedef struct fib_ae_export_t_ {
73 * The vector/list of import tracker indicies
75 fib_node_index_t *faee_importers;
78 * THe connected entry this export is acting on behalf of
80 fib_node_index_t faee_ei;
83 * Reference counting locks
89 * memory pools for the importers and exporters
91 static fib_ae_import_t *fib_ae_import_pool;
92 static fib_ae_export_t *fib_ae_export_pool;
94 static fib_ae_export_t *
95 fib_entry_ae_add_or_lock (fib_node_index_t connected)
97 fib_entry_delegate_t *fed;
98 fib_ae_export_t *export;
101 entry = fib_entry_get(connected);
102 fed = fib_entry_delegate_find(entry,
103 FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
107 fed = fib_entry_delegate_find_or_add(entry,
108 FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
109 pool_get_zero(fib_ae_export_pool, 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)
131 * find the index in the vector of the entry we are removing
133 index = vec_search(import->faei_importeds, entry_index);
135 if (index < vec_len(import->faei_importeds))
138 * this is an entry that was previously imported
140 fib_table_entry_special_remove(import->faei_import_fib,
141 fib_entry_get_prefix(entry_index),
144 fib_entry_unlock(entry_index);
145 vec_del1(import->faei_importeds, index);
150 fib_entry_import_add (fib_ae_import_t *import,
151 fib_node_index_t entry_index)
153 fib_node_index_t *existing;
157 * ensure we only add the exported entry once, since
158 * sourcing prefixes in the table is reference counted
160 vec_foreach(existing, import->faei_importeds)
162 if (*existing == entry_index)
169 * this is the first time this export entry has been imported
170 * Add it to the import FIB and to the list of importeds.
171 * make a copy of the prefix in case the underlying entry reallocs.
173 fib_prefix_copy(&prefix, fib_entry_get_prefix(entry_index));
176 * don't import entries that have the same prefix the import entry
178 if (0 != fib_prefix_cmp(&prefix, &import->faei_prefix))
182 dpo = fib_entry_contribute_ip_forwarding(entry_index);
184 if (dpo_id_is_valid(dpo) && !dpo_is_drop(dpo))
186 fib_table_entry_special_dpo_add(import->faei_import_fib,
189 (fib_entry_get_flags(entry_index) |
190 FIB_ENTRY_FLAG_EXCLUSIVE),
191 load_balance_get_bucket(dpo->dpoi_index, 0));
193 fib_entry_lock(entry_index);
194 vec_add1(import->faei_importeds, entry_index);
198 * the entry currently has no valid forwarding. when it
199 * does it will export itself
205 * Call back when walking a connected prefix's covered prefixes for import
208 fib_entry_covered_walk_import (fib_entry_t *cover,
209 fib_node_index_t covered,
212 fib_ae_import_t *import = ctx;
214 fib_entry_import_add(import, covered);
216 return (WALK_CONTINUE);
220 * fib_entry_ae_import_add
222 * Add an importer to a connected entry
225 fib_ae_export_import_add (fib_ae_export_t *export,
226 fib_ae_import_t *import)
230 import->faei_exporter = (export - fib_ae_export_pool);
231 entry = fib_entry_get(export->faee_ei);
233 fib_entry_cover_walk(entry,
234 fib_entry_covered_walk_import,
239 fib_attached_export_import (fib_entry_t *fib_entry,
240 fib_node_index_t export_fib)
242 fib_entry_delegate_t *fed;
243 fib_ae_import_t *import;
244 fib_node_index_t fei;
247 * save index for later post-realloc retrieval
249 fei = fib_entry_get_index(fib_entry);
251 pool_get_zero(fib_ae_import_pool, import);
253 import->faei_import_fib = fib_entry->fe_fib_index;
254 import->faei_export_fib = export_fib;
255 import->faei_prefix = fib_entry->fe_prefix;
256 import->faei_import_entry = fib_entry_get_index(fib_entry);
257 import->faei_export_sibling = ~0;
258 import->faei_exporter = FIB_NODE_INDEX_INVALID;
261 * do an exact match in the export table
263 import->faei_export_entry =
264 fib_table_lookup_exact_match(import->faei_export_fib,
265 &import->faei_prefix);
267 if (FIB_NODE_INDEX_INVALID == import->faei_export_entry)
270 * no exact matching entry in the export table. can't be good.
271 * track the next best thing
273 import->faei_export_entry =
274 fib_table_lookup(import->faei_export_fib,
275 &import->faei_prefix);
280 * found the entry in the export table. import the
281 * the prefixes that it covers.
282 * only if the prefix found in the export FIB really is
283 * attached do we want to import its covered
285 if (FIB_ENTRY_FLAG_ATTACHED &
286 fib_entry_get_flags_i(fib_entry_get(import->faei_export_entry)))
288 fib_ae_export_t *export;
290 export = fib_entry_ae_add_or_lock(import->faei_export_entry);
291 vec_add1(export->faee_importers, (import - fib_ae_import_pool));
292 fib_ae_export_import_add(export, import);
297 * track the entry in the export table so we can update appropriately
299 * Exporting prefixes will have allocated new fib_entry_t objects, so the pool
300 * may have realloc'd.
302 fib_entry = fib_entry_get(fei);
303 import->faei_export_sibling =
304 fib_entry_cover_track(fib_entry_get(import->faei_export_entry), fei);
306 fed = fib_entry_delegate_find_or_add(fib_entry,
307 FIB_ENTRY_DELEGATE_ATTACHED_IMPORT);
308 fed->fd_index = (import - fib_ae_import_pool);
312 * \brief All the imported entries need to be purged
315 fib_attached_export_purge (fib_entry_t *fib_entry)
317 fib_entry_delegate_t *fed;
319 fed = fib_entry_delegate_find(fib_entry,
320 FIB_ENTRY_DELEGATE_ATTACHED_IMPORT);
324 fib_node_index_t *import_index;
325 fib_entry_t *export_entry;
326 fib_ae_import_t *import;
327 fib_ae_export_t *export;
329 import = pool_elt_at_index(fib_ae_import_pool, fed->fd_index);
332 * remove each imported entry
334 vec_foreach(import_index, import->faei_importeds)
336 fib_table_entry_delete(import->faei_import_fib,
337 fib_entry_get_prefix(*import_index),
339 fib_entry_unlock(*import_index);
341 vec_free(import->faei_importeds);
344 * stop tracking the export entry
346 if (~0 != import->faei_export_sibling)
348 fib_entry_cover_untrack(fib_entry_get(import->faei_export_entry),
349 import->faei_export_sibling);
351 import->faei_export_sibling = ~0;
354 * remove this import tracker from the export's list,
355 * if it is attached to one. It won't be in the case the tracked
356 * export entry is not an attached exact match.
358 if (FIB_NODE_INDEX_INVALID != import->faei_exporter)
360 fib_entry_delegate_t *fed;
362 export_entry = fib_entry_get(import->faei_export_entry);
364 fed = fib_entry_delegate_find(export_entry,
365 FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
366 ALWAYS_ASSERT(NULL != fed);
368 export = pool_elt_at_index(fib_ae_export_pool, fed->fd_index);
370 u32 index = vec_search(export->faee_importers,
371 (import - fib_ae_import_pool));
373 ASSERT(index < vec_len(export->faee_importers));
374 vec_del1(export->faee_importers, index);
377 * free the exporter if there are no longer importers
379 if (0 == --export->faee_locks)
381 pool_put(fib_ae_export_pool, export);
382 fib_entry_delegate_remove(export_entry,
383 FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
388 * free the import tracker
390 pool_put(fib_ae_import_pool, import);
391 fib_entry_delegate_remove(fib_entry,
392 FIB_ENTRY_DELEGATE_ATTACHED_IMPORT);
397 fib_attached_export_covered_added (fib_entry_t *cover,
398 fib_node_index_t covered)
400 fib_entry_delegate_t *fed;
402 fed = fib_entry_delegate_find(cover,
403 FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
408 * the covering prefix is exporting to other tables
410 fib_node_index_t *import_index;
411 fib_ae_import_t *import;
412 fib_ae_export_t *export;
414 export = pool_elt_at_index(fib_ae_export_pool, fed->fd_index);
417 * export the covered entry to each of the importers
419 vec_foreach(import_index, export->faee_importers)
421 import = pool_elt_at_index(fib_ae_import_pool, *import_index);
423 fib_entry_import_add(import, covered);
429 fib_attached_export_covered_removed (fib_entry_t *cover,
430 fib_node_index_t covered)
432 fib_entry_delegate_t *fed;
434 fed = fib_entry_delegate_find(cover,
435 FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
440 * the covering prefix is exporting to other tables
442 fib_node_index_t *import_index;
443 fib_ae_import_t *import;
444 fib_ae_export_t *export;
446 export = pool_elt_at_index(fib_ae_export_pool, fed->fd_index);
449 * remove the covered entry from each of the importers
451 vec_foreach(import_index, export->faee_importers)
453 import = pool_elt_at_index(fib_ae_import_pool, *import_index);
455 fib_entry_import_remove(import, covered);
461 fib_attached_export_cover_modified_i (fib_entry_t *fib_entry)
463 fib_entry_delegate_t *fed;
465 fed = fib_entry_delegate_find(fib_entry,
466 FIB_ENTRY_DELEGATE_ATTACHED_IMPORT);
470 fib_ae_import_t *import;
474 * safe the temporaries we need from the existing import
475 * since it will be toast after the purge.
477 import = pool_elt_at_index(fib_ae_import_pool, fed->fd_index);
478 export_fib = import->faei_export_fib;
481 * keep it simple. purge anything that was previously imported.
482 * then re-evaluate the need to import.
484 fib_attached_export_purge(fib_entry);
485 fib_attached_export_import(fib_entry, export_fib);
490 * \brief If this entry is tracking a cover (in another table)
491 * then that cover has changed. re-evaluate import.
494 fib_attached_export_cover_change (fib_entry_t *fib_entry)
496 fib_attached_export_cover_modified_i(fib_entry);
500 * \brief If this entry is tracking a cover (in another table)
501 * then that cover has been updated. re-evaluate import.
504 fib_attached_export_cover_update (fib_entry_t *fib_entry)
506 fib_attached_export_cover_modified_i(fib_entry);
510 fib_ae_import_format (fib_node_index_t impi,
513 fib_node_index_t *index;
514 fib_ae_import_t *import;
516 import = pool_elt_at_index(fib_ae_import_pool, impi);
518 s = format(s, "\n Attached-Import:%d:[", (import - fib_ae_import_pool));
519 s = format(s, "export-prefix:%U ", format_fib_prefix, &import->faei_prefix);
520 s = format(s, "export-entry:%d ", import->faei_export_entry);
521 s = format(s, "export-sibling:%d ", import->faei_export_sibling);
522 s = format(s, "exporter:%d ", import->faei_exporter);
523 s = format(s, "export-fib:%d ", import->faei_export_fib);
525 s = format(s, "import-entry:%d ", import->faei_import_entry);
526 s = format(s, "import-fib:%d ", import->faei_import_fib);
528 s = format(s, "importeds:[");
529 vec_foreach(index, import->faei_importeds)
531 s = format(s, "%d, ", *index);
539 fib_ae_export_format (fib_node_index_t expi,
542 fib_node_index_t *index;
543 fib_ae_export_t *export;
545 export = pool_elt_at_index(fib_ae_export_pool, expi);
547 s = format(s, "\n Attached-Export:%d:[", (export - fib_ae_export_pool));
548 s = format(s, "export-entry:%d ", export->faee_ei);
550 s = format(s, "importers:[");
551 vec_foreach(index, export->faee_importers)
553 s = format(s, "%d, ", *index);