src/vnet/fib/fib_attached_export.c

   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 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     entry = fib_entry_get(connected);
 102     fed = fib_entry_delegate_find(entry,
 103                                   FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
 104
 105     if (NULL == fed)
 106     {
 107         fed = fib_entry_delegate_find_or_add(entry,
 108                                              FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
 109         pool_get_zero(fib_ae_export_pool, 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
 125 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     index = vec_search(import->faei_importeds, entry_index);
 134
 135     if (index < vec_len(import->faei_importeds))
 136     {
 137         /*
 138          * this is an entry that was previously imported
 139          */
 140         fib_table_entry_special_remove(import->faei_import_fib,
 141                                        fib_entry_get_prefix(entry_index),
 142                                        FIB_SOURCE_AE);
 143
 144         fib_entry_unlock(entry_index);
 145         vec_del1(import->faei_importeds, index);
 146     }
 147 }
 148
 149 static void
 150 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     vec_foreach(existing, import->faei_importeds)
 161     {
 162         if (*existing == entry_index)
 163         {
 164             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     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     if (0 != fib_prefix_cmp(&prefix, &import->faei_prefix))
 179     {
 180         const dpo_id_t *dpo;
 181
 182         dpo = fib_entry_contribute_ip_forwarding(entry_index);
 183
 184         if (dpo_id_is_valid(dpo) && !dpo_is_drop(dpo))
 185         {
 186             fib_table_entry_special_dpo_add(import->faei_import_fib,
 187                                             &prefix,
 188                                             FIB_SOURCE_AE,
 189                                             (fib_entry_get_flags(entry_index) |
 190                                              FIB_ENTRY_FLAG_EXCLUSIVE),
 191                                             load_balance_get_bucket(dpo->dpoi_index, 0));
 192
 193             fib_entry_lock(entry_index);
 194             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 fib_entry_covered_walk_import (fib_entry_t *cover,
 209                                fib_node_index_t covered,
 210                                void *ctx)
 211 {
 212     fib_ae_import_t *import = ctx;
 213
 214     fib_entry_import_add(import, covered);
 215
 216     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 fib_ae_export_import_add (fib_ae_export_t *export,
 226                           fib_ae_import_t *import)
 227 {
 228     fib_entry_t *entry;
 229
 230     import->faei_exporter = (export - fib_ae_export_pool);
 231     entry = fib_entry_get(export->faee_ei);
 232
 233     fib_entry_cover_walk(entry,
 234                          fib_entry_covered_walk_import,
 235                          import);
 236 }
 237
 238 void
 239 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     fei = fib_entry_get_index(fib_entry);
 250
 251     pool_get_zero(fib_ae_import_pool, import);
 252
 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;
 259
 260     /*
 261      * do an exact match in the export table
 262      */
 263     import->faei_export_entry =
 264         fib_table_lookup_exact_match(import->faei_export_fib,
 265                                      &import->faei_prefix);
 266
 267     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         import->faei_export_entry =
 274             fib_table_lookup(import->faei_export_fib,
 275                              &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         if (FIB_ENTRY_FLAG_ATTACHED &
 286             fib_entry_get_flags_i(fib_entry_get(import->faei_export_entry)))
 287         {
 288             fib_ae_export_t *export;
 289
 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);
 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     fib_entry = fib_entry_get(fei);
 303     import->faei_export_sibling =
 304         fib_entry_cover_track(fib_entry_get(import->faei_export_entry), fei);
 305
 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);
 309 }
 310
 311 /**
 312  * \brief All the imported entries need to be purged
 313  */
 314 void
 315 fib_attached_export_purge (fib_entry_t *fib_entry)
 316 {
 317     fib_entry_delegate_t *fed;
 318
 319     fed = fib_entry_delegate_find(fib_entry,
 320                                   FIB_ENTRY_DELEGATE_ATTACHED_IMPORT);
 321
 322     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         import = pool_elt_at_index(fib_ae_import_pool, fed->fd_index);
 330
 331         /*
 332          * remove each imported entry
 333          */
 334         vec_foreach(import_index, import->faei_importeds)
 335         {
 336             fib_table_entry_delete(import->faei_import_fib,
 337                                    fib_entry_get_prefix(*import_index),
 338                                    FIB_SOURCE_AE);
 339             fib_entry_unlock(*import_index);
 340         }
 341         vec_free(import->faei_importeds);
 342
 343         /*
 344          * stop tracking the export entry
 345          */
 346         if (~0 != import->faei_export_sibling)
 347         {
 348             fib_entry_cover_untrack(fib_entry_get(import->faei_export_entry),
 349                                     import->faei_export_sibling);
 350         }
 351         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         if (FIB_NODE_INDEX_INVALID != import->faei_exporter)
 359         {
 360             fib_entry_delegate_t *fed;
 361
 362             export_entry = fib_entry_get(import->faei_export_entry);
 363
 364             fed = fib_entry_delegate_find(export_entry,
 365                                           FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
 366             ALWAYS_ASSERT(NULL != fed);
 367
 368             export = pool_elt_at_index(fib_ae_export_pool, fed->fd_index);
 369
 370             u32 index = vec_search(export->faee_importers,
 371                                    (import - fib_ae_import_pool));
 372
 373             ASSERT(index < vec_len(export->faee_importers));
 374             vec_del1(export->faee_importers, index);
 375
 376             /*
 377              * free the exporter if there are no longer importers
 378              */
 379             if (0 == --export->faee_locks)
 380             {
 381                 vec_free (export->faee_importers);
 382                 pool_put(fib_ae_export_pool, export);
 383                 fib_entry_delegate_remove(export_entry,
 384                                           FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
 385             }
 386         }
 387
 388         /*
 389          * free the import tracker
 390          */
 391         pool_put(fib_ae_import_pool, import);
 392         fib_entry_delegate_remove(fib_entry,
 393                                   FIB_ENTRY_DELEGATE_ATTACHED_IMPORT);
 394     }
 395 }
 396
 397 void
 398 fib_attached_export_covered_added (fib_entry_t *cover,
 399                                    fib_node_index_t covered)
 400 {
 401     fib_entry_delegate_t *fed;
 402
 403     fed = fib_entry_delegate_find(cover,
 404                                   FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
 405
 406     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         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         vec_foreach(import_index, export->faee_importers)
 421         {
 422             import = pool_elt_at_index(fib_ae_import_pool, *import_index);
 423
 424             fib_entry_import_add(import, covered);
 425         }
 426     }
 427 }
 428
 429 void
 430 fib_attached_export_covered_removed (fib_entry_t *cover,
 431                                      fib_node_index_t covered)
 432 {
 433     fib_entry_delegate_t *fed;
 434
 435     fed = fib_entry_delegate_find(cover,
 436                                   FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
 437
 438     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         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         vec_foreach(import_index, export->faee_importers)
 453         {
 454             import = pool_elt_at_index(fib_ae_import_pool, *import_index);
 455
 456             fib_entry_import_remove(import, covered);
 457         }
 458     }
 459 }
 460
 461 static void
 462 fib_attached_export_cover_modified_i (fib_entry_t *fib_entry)
 463 {
 464     fib_entry_delegate_t *fed;
 465
 466     fed = fib_entry_delegate_find(fib_entry,
 467                                   FIB_ENTRY_DELEGATE_ATTACHED_IMPORT);
 468
 469     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         import = pool_elt_at_index(fib_ae_import_pool, fed->fd_index);
 479         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         fib_attached_export_purge(fib_entry);
 486         fib_attached_export_import(fib_entry, export_fib);
 487     }
 488 }
 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 fib_attached_export_cover_change (fib_entry_t *fib_entry)
 496 {
 497     fib_attached_export_cover_modified_i(fib_entry);
 498 }
 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 fib_attached_export_cover_update (fib_entry_t *fib_entry)
 506 {
 507     fib_attached_export_cover_modified_i(fib_entry);
 508 }
 509
 510 u8*
 511 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     import = pool_elt_at_index(fib_ae_import_pool, impi);
 518
 519     s = format(s, "\n  Attached-Import:%d:[", (import - fib_ae_import_pool));
 520     s = format(s, "export-prefix:%U ", format_fib_prefix, &import->faei_prefix);
 521     s = format(s, "export-entry:%d ", import->faei_export_entry);
 522     s = format(s, "export-sibling:%d ", import->faei_export_sibling);
 523     s = format(s, "exporter:%d ", import->faei_exporter);
 524     s = format(s, "export-fib:%d ", import->faei_export_fib);
 525
 526     s = format(s, "import-entry:%d ", import->faei_import_entry);
 527     s = format(s, "import-fib:%d ", import->faei_import_fib);
 528
 529     s = format(s, "importeds:[");
 530     vec_foreach(index, import->faei_importeds)
 531     {
 532         s = format(s, "%d, ", *index);
 533     }
 534     s = format(s, "]]");
 535
 536     return (s);
 537 }
 538
 539 u8*
 540 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     export = pool_elt_at_index(fib_ae_export_pool, expi);
 547
 548     s = format(s, "\n  Attached-Export:%d:[", (export - fib_ae_export_pool));
 549     s = format(s, "export-entry:%d ", export->faee_ei);
 550
 551     s = format(s, "importers:[");
 552     vec_foreach(index, export->faee_importers)
 553     {
 554         s = format(s, "%d, ", *index);
 555     }
 556     s = format(s, "]]");
 557
 558     return (s);
 559 }