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 epxort 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 exportes
  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_get(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(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
 126 fib_entry_import_remove (fib_ae_import_t *import,
 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
 154 fib_entry_import_add (fib_ae_import_t *import,
 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,
 192                                             FIB_SOURCE_AE,
 193                                             (fib_entry_get_flags(entry_index) |
 194                                              FIB_ENTRY_FLAG_EXCLUSIVE),
 195                                             load_balance_get_bucket(dpo->dpoi_index, 0));
 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
 212 fib_entry_covered_walk_import (fib_entry_t *cover,
 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
 229 fib_ae_export_import_add (fib_ae_export_t *export,
 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,
 238                          fib_entry_covered_walk_import,
 239                          import);
 240 }
 241
 242 void
 243 fib_attached_export_import (fib_entry_t *fib_entry,
 244                             fib_node_index_t export_fib)
 245 {
 246     fib_entry_delegate_t *fed;
 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          */
 289         if (FIB_ENTRY_FLAG_ATTACHED &
 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,
 311                                          FIB_ENTRY_DELEGATE_ATTACHED_IMPORT);
 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
 319 fib_attached_export_purge (fib_entry_t *fib_entry)
 320 {
 321     fib_entry_delegate_t *fed;
 322
 323     fed = fib_entry_delegate_get(fib_entry,
 324                                  FIB_ENTRY_DELEGATE_ATTACHED_IMPORT);
 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         {
 368             fib_entry_delegate_t *fed;
 369
 370             export_entry = fib_entry_get(import->faei_export_entry);
 371
 372             fed = fib_entry_delegate_get(export_entry,
 373                                          FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
 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,
 391                                           FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
 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,
 400                                   FIB_ENTRY_DELEGATE_ATTACHED_IMPORT);
 401     }
 402 }
 403
 404 void
 405 fib_attached_export_covered_added (fib_entry_t *cover,
 406                                    fib_node_index_t covered)
 407 {
 408     fib_entry_delegate_t *fed;
 409
 410     fed = fib_entry_delegate_get(cover,
 411                                  FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
 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
 437 fib_attached_export_covered_removed (fib_entry_t *cover,
 438                                      fib_node_index_t covered)
 439 {
 440     fib_entry_delegate_t *fed;
 441
 442     fed = fib_entry_delegate_get(cover,
 443                                  FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
 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
 469 fib_attached_export_cover_modified_i (fib_entry_t *fib_entry)
 470 {
 471     fib_entry_delegate_t *fed;
 472
 473     fed = fib_entry_delegate_get(fib_entry,
 474                                  FIB_ENTRY_DELEGATE_ATTACHED_IMPORT);
 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
 502 fib_attached_export_cover_change (fib_entry_t *fib_entry)
 503 {
 504     fib_attached_export_cover_modified_i(fib_entry);
 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
 512 fib_attached_export_cover_update (fib_entry_t *fib_entry)
 513 {
 514     fib_attached_export_cover_modified_i(fib_entry);
 515 }
 516
 517 u8*
 518 fib_ae_import_format (fib_node_index_t impi,
 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*
 547 fib_ae_export_format (fib_node_index_t expi,
 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 }