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_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         clib_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     u32 index;
 130
 131     /*
 132      * find the index in the vector of the entry we are removing
 133      */
 134     index = vec_search(import->faei_importeds, entry_index);
 135
 136     if (index < vec_len(import->faei_importeds))
 137     {
 138         /*
 139          * this is an entry that was previously imported
 140          */
 141         fib_table_entry_special_remove(import->faei_import_fib,
 142                                        fib_entry_get_prefix(entry_index),
 143                                        FIB_SOURCE_AE);
 144
 145         fib_entry_unlock(entry_index);
 146         vec_del1(import->faei_importeds, index);
 147     }
 148 }
 149
 150 static void
 151 fib_entry_import_add (fib_ae_import_t *import,
 152                       fib_node_index_t entry_index)
 153 {
 154     fib_node_index_t *existing;
 155     const fib_prefix_t *prefix;
 156
 157     /*
 158      * ensure we only add the exported entry once, since
 159      * sourcing prefixes in the table is reference counted
 160      */
 161     vec_foreach(existing, import->faei_importeds)
 162     {
 163         if (*existing == entry_index)
 164         {
 165             return;
 166         }
 167     }
 168
 169     /*
 170      * this is the first time this export entry has been imported
 171      * Add it to the import FIB and to the list of importeds
 172      */
 173     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,
 179                             &import->faei_prefix))
 180     {
 181         const dpo_id_t *dpo;
 182
 183         dpo = fib_entry_contribute_ip_forwarding(entry_index);
 184
 185         if (dpo_id_is_valid(dpo) && !dpo_is_drop(dpo))
 186         {
 187             fib_table_entry_special_dpo_add(import->faei_import_fib,
 188                                             prefix,
 189                                             FIB_SOURCE_AE,
 190                                             (fib_entry_get_flags(entry_index) |
 191                                              FIB_ENTRY_FLAG_EXCLUSIVE),
 192                                             load_balance_get_bucket(dpo->dpoi_index, 0));
 193
 194             fib_entry_lock(entry_index);
 195             vec_add1(import->faei_importeds, entry_index);
 196         }
 197         /*
 198          * else
 199          *   the entry currently has no valid forwarding. when it
 200          * does it will export itself
 201          */
 202     }
 203 }
 204
 205 /**
 206  * Call back when walking a connected prefix's covered prefixes for import
 207  */
 208 static int
 209 fib_entry_covered_walk_import (fib_entry_t *cover,
 210                                fib_node_index_t covered,
 211                                void *ctx)
 212 {
 213     fib_ae_import_t *import = ctx;
 214
 215     fib_entry_import_add(import, covered);
 216
 217     return (0);
 218 }
 219
 220 /*
 221  * fib_entry_ae_import_add
 222  *
 223  * Add an importer to a connected entry
 224  */
 225 static void
 226 fib_ae_export_import_add (fib_ae_export_t *export,
 227                           fib_ae_import_t *import)
 228 {
 229     fib_entry_t *entry;
 230
 231     import->faei_exporter = (export - fib_ae_export_pool);
 232     entry = fib_entry_get(export->faee_ei);
 233
 234     fib_entry_cover_walk(entry,
 235                          fib_entry_covered_walk_import,
 236                          import);
 237 }
 238
 239 void
 240 fib_attached_export_import (fib_entry_t *fib_entry,
 241                             fib_node_index_t export_fib)
 242 {
 243     fib_entry_delegate_t *fed;
 244     fib_ae_import_t *import;
 245     fib_node_index_t fei;
 246
 247     /*
 248      * save index for later post-realloc retrieval
 249      */
 250     fei = fib_entry_get_index(fib_entry);
 251
 252     pool_get(fib_ae_import_pool, import);
 253
 254     import->faei_import_fib = fib_entry->fe_fib_index;
 255     import->faei_export_fib = export_fib;
 256     import->faei_prefix = fib_entry->fe_prefix;
 257     import->faei_import_entry = fib_entry_get_index(fib_entry);
 258     import->faei_export_sibling = ~0;
 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         import->faei_exporter = FIB_NODE_INDEX_INVALID;
 277     }
 278     else
 279     {
 280         /*
 281          * found the entry in the export table. import the
 282          * the prefixes that it covers.
 283          * only if the prefix found in the export FIB really is
 284          * attached do we want to import its covered
 285          */
 286         if (FIB_ENTRY_FLAG_ATTACHED &
 287             fib_entry_get_flags_i(fib_entry_get(import->faei_export_entry)))
 288         {
 289             fib_ae_export_t *export;
 290
 291             export = fib_entry_ae_add_or_lock(import->faei_export_entry);
 292             vec_add1(export->faee_importers, (import - fib_ae_import_pool));
 293             fib_ae_export_import_add(export, import);
 294         }
 295     }
 296
 297     /*
 298      * track the entry in the export table so we can update appropriately
 299      * when it changes.
 300      * Exporting prefixes will have allocated new fib_entry_t objects, so the pool
 301      * may have realloc'd.
 302      */
 303     fib_entry = fib_entry_get(fei);
 304     import->faei_export_sibling =
 305         fib_entry_cover_track(fib_entry_get(import->faei_export_entry), fei);
 306
 307     fed = fib_entry_delegate_find_or_add(fib_entry,
 308                                          FIB_ENTRY_DELEGATE_ATTACHED_IMPORT);
 309     fed->fd_index = (import - fib_ae_import_pool);
 310 }
 311
 312 /**
 313  * \brief All the imported entries need to be purged
 314  */
 315 void
 316 fib_attached_export_purge (fib_entry_t *fib_entry)
 317 {
 318     fib_entry_delegate_t *fed;
 319
 320     fed = fib_entry_delegate_get(fib_entry,
 321                                  FIB_ENTRY_DELEGATE_ATTACHED_IMPORT);
 322
 323     if (NULL != fed)
 324     {
 325         fib_node_index_t *import_index;
 326         fib_entry_t *export_entry;
 327         fib_ae_import_t *import;
 328         fib_ae_export_t *export;
 329
 330         import = pool_elt_at_index(fib_ae_import_pool, fed->fd_index);
 331
 332         /*
 333          * remove each imported entry
 334          */
 335         vec_foreach(import_index, import->faei_importeds)
 336         {
 337             fib_table_entry_delete(import->faei_import_fib,
 338                                    fib_entry_get_prefix(*import_index),
 339                                    FIB_SOURCE_AE);
 340             fib_entry_unlock(*import_index);
 341         }
 342         vec_free(import->faei_importeds);
 343
 344         /*
 345          * stop tracking the export entry
 346          */
 347         if (~0 != import->faei_export_sibling)
 348         {
 349             fib_entry_cover_untrack(fib_entry_get(import->faei_export_entry),
 350                                     import->faei_export_sibling);
 351         }
 352         import->faei_export_sibling = ~0;
 353
 354         /*
 355          * remove this import tracker from the export's list,
 356          * if it is attached to one. It won't be in the case the tracked
 357          * export entry is not an attached exact match.
 358          */
 359         if (FIB_NODE_INDEX_INVALID != import->faei_exporter)
 360         {
 361             fib_entry_delegate_t *fed;
 362
 363             export_entry = fib_entry_get(import->faei_export_entry);
 364
 365             fed = fib_entry_delegate_get(export_entry,
 366                                          FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
 367             ASSERT(NULL != fed);
 368
 369             export = pool_elt_at_index(fib_ae_export_pool, fed->fd_index);
 370
 371             u32 index = vec_search(export->faee_importers,
 372                                    (import - fib_ae_import_pool));
 373
 374             ASSERT(index < vec_len(export->faee_importers));
 375             vec_del1(export->faee_importers, index);
 376
 377             /*
 378              * free the exporter if there are no longer importers
 379              */
 380             if (0 == --export->faee_locks)
 381             {
 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_get(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_get(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_get(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 }