Line data Source code
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 :
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>
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 export table that this importer
32 : * is importing covereds from
33 : */
34 : fib_node_index_t faei_export_entry;
35 :
36 : /**
37 : * The attached entry in the import table
38 : */
39 : fib_node_index_t faei_import_entry;
40 : /**
41 : * the sibling index on the cover
42 : */
43 : u32 faei_export_sibling;
44 :
45 : /**
46 : * The index of the exporter tracker. Not set if the
47 : * export entry is not valid for export
48 : */
49 : fib_node_index_t faei_exporter;
50 :
51 : /**
52 : * A vector/list of imported entry indicies
53 : */
54 : fib_node_index_t *faei_importeds;
55 :
56 : /**
57 : * The FIB index and prefix we are tracking
58 : */
59 : fib_node_index_t faei_export_fib;
60 : fib_prefix_t faei_prefix;
61 :
62 : /**
63 : * The FIB index we are importing into
64 : */
65 : fib_node_index_t faei_import_fib;
66 : } fib_ae_import_t;
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 : */
75 : fib_node_index_t *faee_importers;
76 :
77 : /**
78 : * THe connected entry this export is acting on behalf of
79 : */
80 : fib_node_index_t faee_ei;
81 :
82 : /**
83 : * Reference counting locks
84 : */
85 : u32 faee_locks;
86 : } fib_ae_export_t;
87 :
88 : /*
89 : * memory pools for the importers and exporters
90 : */
91 : static fib_ae_import_t *fib_ae_import_pool;
92 : static fib_ae_export_t *fib_ae_export_pool;
93 :
94 : static fib_ae_export_t *
95 11 : fib_entry_ae_add_or_lock (fib_node_index_t connected)
96 : {
97 : fib_entry_delegate_t *fed;
98 : fib_ae_export_t *export;
99 : fib_entry_t *entry;
100 :
101 11 : entry = fib_entry_get(connected);
102 11 : fed = fib_entry_delegate_find(entry,
103 : FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
104 :
105 11 : if (NULL == fed)
106 : {
107 10 : fed = fib_entry_delegate_find_or_add(entry,
108 : FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
109 10 : pool_get_zero(fib_ae_export_pool, export);
110 :
111 10 : fed->fd_index = (export - fib_ae_export_pool);
112 10 : export->faee_ei = connected;
113 : }
114 : else
115 : {
116 1 : export = pool_elt_at_index(fib_ae_export_pool, fed->fd_index);
117 : }
118 :
119 11 : export->faee_locks++;
120 :
121 11 : return (export);
122 : }
123 :
124 : static void
125 6 : fib_entry_import_remove (fib_ae_import_t *import,
126 : fib_node_index_t entry_index)
127 : {
128 : u32 index;
129 :
130 : /*
131 : * find the index in the vector of the entry we are removing
132 : */
133 15 : index = vec_search(import->faei_importeds, entry_index);
134 :
135 6 : if (index < vec_len(import->faei_importeds))
136 : {
137 : /*
138 : * this is an entry that was previously imported
139 : */
140 6 : fib_table_entry_special_remove(import->faei_import_fib,
141 : fib_entry_get_prefix(entry_index),
142 : FIB_SOURCE_AE);
143 :
144 6 : fib_entry_unlock(entry_index);
145 6 : vec_del1(import->faei_importeds, index);
146 : }
147 6 : }
148 :
149 : static void
150 35 : fib_entry_import_add (fib_ae_import_t *import,
151 : fib_node_index_t entry_index)
152 : {
153 : fib_node_index_t *existing;
154 : fib_prefix_t prefix;
155 :
156 : /*
157 : * ensure we only add the exported entry once, since
158 : * sourcing prefixes in the table is reference counted
159 : */
160 65 : vec_foreach(existing, import->faei_importeds)
161 : {
162 34 : if (*existing == entry_index)
163 : {
164 4 : return;
165 : }
166 : }
167 :
168 : /*
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.
172 : */
173 31 : fib_prefix_copy(&prefix, fib_entry_get_prefix(entry_index));
174 :
175 : /*
176 : * don't import entries that have the same prefix the import entry
177 : */
178 31 : if (0 != fib_prefix_cmp(&prefix, &import->faei_prefix))
179 : {
180 : const dpo_id_t *dpo;
181 :
182 30 : dpo = fib_entry_contribute_ip_forwarding(entry_index);
183 :
184 30 : if (dpo_id_is_valid(dpo) && !dpo_is_drop(dpo))
185 : {
186 56 : fib_table_entry_special_dpo_add(import->faei_import_fib,
187 : &prefix,
188 : FIB_SOURCE_AE,
189 28 : (fib_entry_get_flags(entry_index) |
190 : FIB_ENTRY_FLAG_EXCLUSIVE),
191 : load_balance_get_bucket(dpo->dpoi_index, 0));
192 :
193 28 : fib_entry_lock(entry_index);
194 28 : vec_add1(import->faei_importeds, entry_index);
195 : }
196 : /*
197 : * else
198 : * the entry currently has no valid forwarding. when it
199 : * does it will export itself
200 : */
201 : }
202 : }
203 :
204 : /**
205 : * Call back when walking a connected prefix's covered prefixes for import
206 : */
207 : static walk_rc_t
208 21 : fib_entry_covered_walk_import (fib_entry_t *cover,
209 : fib_node_index_t covered,
210 : void *ctx)
211 : {
212 21 : fib_ae_import_t *import = ctx;
213 :
214 21 : fib_entry_import_add(import, covered);
215 :
216 21 : return (WALK_CONTINUE);
217 : }
218 :
219 : /*
220 : * fib_entry_ae_import_add
221 : *
222 : * Add an importer to a connected entry
223 : */
224 : static void
225 11 : fib_ae_export_import_add (fib_ae_export_t *export,
226 : fib_ae_import_t *import)
227 : {
228 : fib_entry_t *entry;
229 :
230 11 : import->faei_exporter = (export - fib_ae_export_pool);
231 11 : entry = fib_entry_get(export->faee_ei);
232 :
233 11 : fib_entry_cover_walk(entry,
234 : fib_entry_covered_walk_import,
235 : import);
236 11 : }
237 :
238 : void
239 28 : fib_attached_export_import (fib_entry_t *fib_entry,
240 : fib_node_index_t export_fib)
241 : {
242 : fib_entry_delegate_t *fed;
243 : fib_ae_import_t *import;
244 : fib_node_index_t fei;
245 :
246 : /*
247 : * save index for later post-realloc retrieval
248 : */
249 28 : fei = fib_entry_get_index(fib_entry);
250 :
251 28 : pool_get_zero(fib_ae_import_pool, import);
252 :
253 28 : import->faei_import_fib = fib_entry->fe_fib_index;
254 28 : import->faei_export_fib = export_fib;
255 28 : import->faei_prefix = fib_entry->fe_prefix;
256 28 : import->faei_import_entry = fib_entry_get_index(fib_entry);
257 28 : import->faei_export_sibling = ~0;
258 28 : import->faei_exporter = FIB_NODE_INDEX_INVALID;
259 :
260 : /*
261 : * do an exact match in the export table
262 : */
263 56 : import->faei_export_entry =
264 28 : fib_table_lookup_exact_match(import->faei_export_fib,
265 28 : &import->faei_prefix);
266 :
267 28 : 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 15 : import->faei_export_entry =
274 15 : fib_table_lookup(import->faei_export_fib,
275 15 : &import->faei_prefix);
276 : }
277 : else
278 : {
279 : /*
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
284 : */
285 13 : if (FIB_ENTRY_FLAG_ATTACHED &
286 13 : fib_entry_get_flags_i(fib_entry_get(import->faei_export_entry)))
287 : {
288 : fib_ae_export_t *export;
289 :
290 11 : export = fib_entry_ae_add_or_lock(import->faei_export_entry);
291 11 : vec_add1(export->faee_importers, (import - fib_ae_import_pool));
292 11 : fib_ae_export_import_add(export, import);
293 : }
294 : }
295 :
296 : /*
297 : * track the entry in the export table so we can update appropriately
298 : * when it changes.
299 : * Exporting prefixes will have allocated new fib_entry_t objects, so the pool
300 : * may have realloc'd.
301 : */
302 28 : fib_entry = fib_entry_get(fei);
303 56 : import->faei_export_sibling =
304 28 : fib_entry_cover_track(fib_entry_get(import->faei_export_entry), fei);
305 :
306 28 : fed = fib_entry_delegate_find_or_add(fib_entry,
307 : FIB_ENTRY_DELEGATE_ATTACHED_IMPORT);
308 28 : fed->fd_index = (import - fib_ae_import_pool);
309 28 : }
310 :
311 : /**
312 : * \brief All the imported entries need to be purged
313 : */
314 : void
315 28 : fib_attached_export_purge (fib_entry_t *fib_entry)
316 : {
317 : fib_entry_delegate_t *fed;
318 :
319 28 : fed = fib_entry_delegate_find(fib_entry,
320 : FIB_ENTRY_DELEGATE_ATTACHED_IMPORT);
321 :
322 28 : if (NULL != fed)
323 : {
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;
328 :
329 28 : import = pool_elt_at_index(fib_ae_import_pool, fed->fd_index);
330 :
331 : /*
332 : * remove each imported entry
333 : */
334 50 : vec_foreach(import_index, import->faei_importeds)
335 : {
336 22 : fib_table_entry_delete(import->faei_import_fib,
337 : fib_entry_get_prefix(*import_index),
338 : FIB_SOURCE_AE);
339 22 : fib_entry_unlock(*import_index);
340 : }
341 28 : vec_free(import->faei_importeds);
342 :
343 : /*
344 : * stop tracking the export entry
345 : */
346 28 : if (~0 != import->faei_export_sibling)
347 : {
348 28 : fib_entry_cover_untrack(fib_entry_get(import->faei_export_entry),
349 : import->faei_export_sibling);
350 : }
351 28 : import->faei_export_sibling = ~0;
352 :
353 : /*
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.
357 : */
358 28 : if (FIB_NODE_INDEX_INVALID != import->faei_exporter)
359 : {
360 : fib_entry_delegate_t *fed;
361 :
362 11 : export_entry = fib_entry_get(import->faei_export_entry);
363 :
364 11 : fed = fib_entry_delegate_find(export_entry,
365 : FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
366 11 : ALWAYS_ASSERT(NULL != fed);
367 :
368 11 : export = pool_elt_at_index(fib_ae_export_pool, fed->fd_index);
369 :
370 12 : u32 index = vec_search(export->faee_importers,
371 : (import - fib_ae_import_pool));
372 :
373 11 : ASSERT(index < vec_len(export->faee_importers));
374 11 : vec_del1(export->faee_importers, index);
375 :
376 : /*
377 : * free the exporter if there are no longer importers
378 : */
379 11 : if (0 == --export->faee_locks)
380 : {
381 10 : vec_free (export->faee_importers);
382 10 : pool_put(fib_ae_export_pool, export);
383 10 : fib_entry_delegate_remove(export_entry,
384 : FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
385 : }
386 : }
387 :
388 : /*
389 : * free the import tracker
390 : */
391 28 : pool_put(fib_ae_import_pool, import);
392 28 : fib_entry_delegate_remove(fib_entry,
393 : FIB_ENTRY_DELEGATE_ATTACHED_IMPORT);
394 : }
395 28 : }
396 :
397 : void
398 16288 : fib_attached_export_covered_added (fib_entry_t *cover,
399 : fib_node_index_t covered)
400 : {
401 : fib_entry_delegate_t *fed;
402 :
403 16288 : fed = fib_entry_delegate_find(cover,
404 : FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
405 :
406 16288 : 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 13 : 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 27 : vec_foreach(import_index, export->faee_importers)
421 : {
422 14 : import = pool_elt_at_index(fib_ae_import_pool, *import_index);
423 :
424 14 : fib_entry_import_add(import, covered);
425 : }
426 : }
427 16288 : }
428 :
429 : void
430 7697 : fib_attached_export_covered_removed (fib_entry_t *cover,
431 : fib_node_index_t covered)
432 : {
433 : fib_entry_delegate_t *fed;
434 :
435 7697 : fed = fib_entry_delegate_find(cover,
436 : FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
437 :
438 7697 : 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 5 : 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 11 : vec_foreach(import_index, export->faee_importers)
453 : {
454 6 : import = pool_elt_at_index(fib_ae_import_pool, *import_index);
455 :
456 6 : fib_entry_import_remove(import, covered);
457 : }
458 : }
459 7697 : }
460 :
461 : static void
462 4254 : fib_attached_export_cover_modified_i (fib_entry_t *fib_entry)
463 : {
464 : fib_entry_delegate_t *fed;
465 :
466 4254 : fed = fib_entry_delegate_find(fib_entry,
467 : FIB_ENTRY_DELEGATE_ATTACHED_IMPORT);
468 :
469 4254 : 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 14 : import = pool_elt_at_index(fib_ae_import_pool, fed->fd_index);
479 14 : 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 14 : fib_attached_export_purge(fib_entry);
486 14 : fib_attached_export_import(fib_entry, export_fib);
487 : }
488 4254 : }
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
495 4240 : fib_attached_export_cover_change (fib_entry_t *fib_entry)
496 : {
497 4240 : fib_attached_export_cover_modified_i(fib_entry);
498 4240 : }
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
505 14 : fib_attached_export_cover_update (fib_entry_t *fib_entry)
506 : {
507 14 : fib_attached_export_cover_modified_i(fib_entry);
508 14 : }
509 :
510 : u8*
511 0 : fib_ae_import_format (fib_node_index_t impi,
512 : u8* s)
513 : {
514 : fib_node_index_t *index;
515 : fib_ae_import_t *import;
516 :
517 0 : import = pool_elt_at_index(fib_ae_import_pool, impi);
518 :
519 0 : s = format(s, "\n Attached-Import:%d:[", (import - fib_ae_import_pool));
520 0 : s = format(s, "export-prefix:%U ", format_fib_prefix, &import->faei_prefix);
521 0 : s = format(s, "export-entry:%d ", import->faei_export_entry);
522 0 : s = format(s, "export-sibling:%d ", import->faei_export_sibling);
523 0 : s = format(s, "exporter:%d ", import->faei_exporter);
524 0 : s = format(s, "export-fib:%d ", import->faei_export_fib);
525 :
526 0 : s = format(s, "import-entry:%d ", import->faei_import_entry);
527 0 : s = format(s, "import-fib:%d ", import->faei_import_fib);
528 :
529 0 : s = format(s, "importeds:[");
530 0 : vec_foreach(index, import->faei_importeds)
531 : {
532 0 : s = format(s, "%d, ", *index);
533 : }
534 0 : s = format(s, "]]");
535 :
536 0 : return (s);
537 : }
538 :
539 : u8*
540 0 : fib_ae_export_format (fib_node_index_t expi,
541 : u8* s)
542 : {
543 : fib_node_index_t *index;
544 : fib_ae_export_t *export;
545 :
546 0 : export = pool_elt_at_index(fib_ae_export_pool, expi);
547 :
548 0 : s = format(s, "\n Attached-Export:%d:[", (export - fib_ae_export_pool));
549 0 : s = format(s, "export-entry:%d ", export->faee_ei);
550 :
551 0 : s = format(s, "importers:[");
552 0 : vec_foreach(index, export->faee_importers)
553 : {
554 0 : s = format(s, "%d, ", *index);
555 : }
556 0 : s = format(s, "]]");
557 :
558 0 : return (s);
559 : }
|
