vnet/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 "fib_attached_export.h"
  20 #include "fib_entry_cover.h"
  21 #include "fib_entry_src.h"
  22
  23 /**
  24  * A description of the need to import routes from the export table
  25  */
  26 typedef struct fib_ae_import_t_
  27 {
  28     /**
  29      * The entry in the epxort table that this importer
  30      * is importing covereds from
  31      */
  32     fib_node_index_t faei_export_entry;
  33
  34     /**
  35      * The attached entry in the import table
  36      */
  37     fib_node_index_t faei_import_entry;
  38     /**
  39      * the sibling index on the cover
  40      */
  41     u32 faei_export_sibling;
  42
  43     /**
  44      * The index of the exporter tracker. Not set if the
  45      * export entry is not valid for export
  46      */
  47     fib_node_index_t faei_exporter;
  48
  49     /**
  50      * A vector/list of imported entry indicies
  51      */
  52     fib_node_index_t *faei_importeds;
  53
  54     /**
  55      * The FIB index and prefix we are tracking
  56      */
  57     fib_node_index_t faei_export_fib;
  58     fib_prefix_t faei_prefix;
  59
  60     /**
  61      * The FIB index we are importing into
  62      */
  63     fib_node_index_t faei_import_fib;
  64 } fib_ae_import_t;
  65
  66 /**
  67  * A description of the need to export routes to one or more export tables
  68  */
  69 typedef struct fib_ae_export_t_ {
  70     /**
  71      * The vector/list of import tracker indicies
  72      */
  73     fib_node_index_t *faee_importers;
  74
  75     /**
  76      * THe connected entry this export is acting on behalf of
  77      */
  78     fib_node_index_t faee_ei;
  79
  80     /**
  81      * Reference counting locks
  82      */
  83     u32 faee_locks;
  84 } fib_ae_export_t;
  85
  86 /*
  87  * memory pools for the importers and exportes
  88  */
  89 static fib_ae_import_t *fib_ae_import_pool;
  90 static fib_ae_export_t *fib_ae_export_pool;
  91
  92 static fib_ae_export_t *
  93 fib_entry_ae_add_or_lock (fib_node_index_t connected)
  94 {
  95     fib_ae_export_t *export;
  96     fib_entry_t *entry;
  97
  98     entry = fib_entry_get(connected);
  99
 100     if (FIB_NODE_INDEX_INVALID == entry->fe_export)
 101     {
 102         pool_get(fib_ae_export_pool, export);
 103         memset(export, 0, sizeof(*export));
 104
 105         entry->fe_export = (export - fib_ae_export_pool);
 106         export->faee_ei = connected;
 107     }
 108     else
 109     {
 110         export = pool_elt_at_index(fib_ae_export_pool, entry->fe_export);
 111     }
 112
 113     export->faee_locks++;
 114
 115     return (export);
 116 }
 117
 118 static void
 119 fib_entry_import_remove (fib_ae_import_t *import,
 120                          fib_node_index_t entry_index)
 121 {
 122     fib_prefix_t prefix;
 123     u32 index;
 124
 125     /*
 126      * find the index in the vector of the entry we are removing
 127      */
 128     index = vec_search(import->faei_importeds, entry_index);
 129
 130     if (index < vec_len(import->faei_importeds))
 131     {
 132         /*
 133          * this is an entry that was previsouly imported
 134          */
 135         fib_entry_get_prefix(entry_index, &prefix);
 136
 137         fib_table_entry_special_remove(import->faei_import_fib,
 138                                        &prefix,
 139                                        FIB_SOURCE_AE);
 140
 141         fib_entry_unlock(entry_index);
 142         vec_del1(import->faei_importeds, index);
 143     }
 144 }
 145
 146 static void
 147 fib_entry_import_add (fib_ae_import_t *import,
 148                       fib_node_index_t entry_index)
 149 {
 150     fib_node_index_t *existing;
 151     fib_prefix_t prefix;
 152
 153     /*
 154      * ensure we only add the exported entry once, since
 155      * sourcing prefixes in the table is reference counted
 156      */
 157     vec_foreach(existing, import->faei_importeds)
 158     {
 159         if (*existing == entry_index)
 160         {
 161             return;
 162         }
 163     }
 164
 165     /*
 166      * this is the first time this export entry has been imported
 167      * Add it to the import FIB and to the list of importeds
 168      */
 169     fib_entry_get_prefix(entry_index, &prefix);
 170
 171     /*
 172      * don't import entries that have the same prefix the import entry
 173      */
 174     if (0 != fib_prefix_cmp(&prefix,
 175                             &import->faei_prefix))
 176     {
 177         const dpo_id_t *dpo;
 178
 179         dpo = fib_entry_contribute_ip_forwarding(entry_index);
 180
 181         if (dpo_id_is_valid(dpo))
 182         {
 183             fib_table_entry_special_dpo_add(import->faei_import_fib,
 184                                             &prefix,
 185                                             FIB_SOURCE_AE,
 186                                             FIB_ENTRY_FLAG_EXCLUSIVE,
 187                                             load_balance_get_bucket(dpo->dpoi_index, 0));
 188
 189             fib_entry_lock(entry_index);
 190             vec_add1(import->faei_importeds, entry_index);
 191         }
 192         /*
 193          * else
 194          *   the entry currently has no valid forwarding. when it
 195          * does it will export itself
 196          */
 197     }
 198 }
 199
 200 /**
 201  * Call back when walking a connected prefix's covered prefixes for import
 202  */
 203 static int
 204 fib_entry_covered_walk_import (fib_entry_t *cover,
 205                                fib_node_index_t covered,
 206                                void *ctx)
 207 {
 208     fib_ae_import_t *import = ctx;
 209
 210     fib_entry_import_add(import, covered);
 211
 212     return (0);
 213 }
 214
 215 /*
 216  * fib_entry_ae_import_add
 217  *
 218  * Add an importer to a connected entry
 219  */
 220 static void
 221 fib_ae_export_import_add (fib_ae_export_t *export,
 222                           fib_ae_import_t *import)
 223 {
 224     fib_entry_t *entry;
 225
 226     import->faei_exporter = (export - fib_ae_export_pool);
 227     entry = fib_entry_get(export->faee_ei);
 228
 229     fib_entry_cover_walk(entry,
 230                          fib_entry_covered_walk_import,
 231                          import);
 232 }
 233
 234 void
 235 fib_attached_export_import (fib_entry_t *fib_entry,
 236                             fib_node_index_t export_fib)
 237 {
 238     fib_ae_import_t *import;
 239
 240     pool_get(fib_ae_import_pool, import);
 241
 242     import->faei_import_fib = fib_entry->fe_fib_index;
 243     import->faei_export_fib = export_fib;
 244     import->faei_prefix = fib_entry->fe_prefix;
 245     import->faei_import_entry = fib_entry_get_index(fib_entry);
 246     import->faei_export_sibling = ~0;
 247
 248     /*
 249      * do an exact match in the export table
 250      */
 251     import->faei_export_entry =
 252         fib_table_lookup_exact_match(import->faei_export_fib,
 253                                      &import->faei_prefix);
 254
 255     if (FIB_NODE_INDEX_INVALID == import->faei_export_entry)
 256     {
 257         /*
 258          * no exact matching entry in the export table. can't be good.
 259          * track the next best thing
 260          */
 261         import->faei_export_entry =
 262             fib_table_lookup(import->faei_export_fib,
 263                              &import->faei_prefix);
 264         import->faei_exporter = FIB_NODE_INDEX_INVALID;
 265     }
 266     else
 267     {
 268         /*
 269          * found the entry in the export table. import the
 270          * the prefixes that it covers.
 271          * only if the prefix found in the export FIB really is
 272          * attached do we want to import its covered
 273          */
 274         if (FIB_ENTRY_FLAG_ATTACHED &
 275             fib_entry_get_flags_i(fib_entry_get(import->faei_export_entry)))
 276         {
 277             fib_ae_export_t *export;
 278
 279             export = fib_entry_ae_add_or_lock(import->faei_export_entry);
 280             vec_add1(export->faee_importers, (import - fib_ae_import_pool));
 281             fib_ae_export_import_add(export, import);
 282         }
 283     }
 284
 285     /*
 286      * track the entry in the export table so we can update appropriately
 287      * when it changes
 288      */
 289     import->faei_export_sibling =
 290         fib_entry_cover_track(fib_entry_get(import->faei_export_entry),
 291                               fib_entry_get_index(fib_entry));
 292
 293     fib_entry->fe_import = (import - fib_ae_import_pool);
 294 }
 295
 296 /**
 297  * \brief All the imported entries need to be pruged
 298  */
 299 void
 300 fib_attached_export_purge (fib_entry_t *fib_entry)
 301 {
 302     if (FIB_NODE_INDEX_INVALID != fib_entry->fe_import)
 303     {
 304         fib_node_index_t *import_index;
 305         fib_entry_t *export_entry;
 306         fib_ae_import_t *import;
 307         fib_ae_export_t *export;
 308
 309         import = pool_elt_at_index(fib_ae_import_pool,
 310                                    fib_entry->fe_import);
 311
 312         /*
 313          * remove each imported entry
 314          */
 315         vec_foreach(import_index, import->faei_importeds)
 316         {
 317             fib_prefix_t prefix;
 318
 319             fib_entry_get_prefix(*import_index, &prefix);
 320
 321             fib_table_entry_delete(import->faei_import_fib,
 322                                    &prefix,
 323                                    FIB_SOURCE_AE);
 324             fib_entry_unlock(*import_index);
 325         }
 326         vec_free(import->faei_importeds);
 327
 328         /*
 329          * stop tracking the export entry
 330          */
 331         if (~0 != import->faei_export_sibling)
 332         {
 333             fib_entry_cover_untrack(fib_entry_get(import->faei_export_entry),
 334                                     import->faei_export_sibling);
 335         }
 336         import->faei_export_sibling = ~0;
 337
 338         /*
 339          * remove this import tracker from the export's list,
 340          * if it is attached to one. It won't be in the case the tracked
 341          * export entry is not an attached exact match.
 342          */
 343         if (FIB_NODE_INDEX_INVALID != import->faei_exporter)
 344         {
 345             export_entry = fib_entry_get(import->faei_export_entry);
 346             ASSERT(FIB_NODE_INDEX_INVALID != export_entry->fe_export);
 347             export = pool_elt_at_index(fib_ae_export_pool, export_entry->fe_export);
 348
 349             u32 index = vec_search(export->faee_importers,
 350                                    (import - fib_ae_import_pool));
 351
 352             ASSERT(index < vec_len(export->faee_importers));
 353             vec_del1(export->faee_importers, index);
 354
 355             /*
 356              * free the exporter if there are no longer importers
 357              */
 358             if (0 == --export->faee_locks)
 359             {
 360                 pool_put(fib_ae_export_pool, export);
 361                 export_entry->fe_export = FIB_NODE_INDEX_INVALID;
 362             }
 363         }
 364
 365         /*
 366          * free the import tracker
 367          */
 368         pool_put(fib_ae_import_pool, import);
 369         fib_entry->fe_import = FIB_NODE_INDEX_INVALID;
 370     }
 371 }
 372
 373 void
 374 fib_attached_export_covered_added (fib_entry_t *cover,
 375                                    fib_node_index_t covered)
 376 {
 377     if (FIB_NODE_INDEX_INVALID != cover->fe_export)
 378     {
 379         /*
 380          * the covering prefix is exporting to other tables
 381          */
 382         fib_node_index_t *import_index;
 383         fib_ae_import_t *import;
 384         fib_ae_export_t *export;
 385
 386         export = pool_elt_at_index(fib_ae_export_pool, cover->fe_export);
 387
 388         /*
 389          * export the covered entry to each of the importers
 390          */
 391         vec_foreach(import_index, export->faee_importers)
 392         {
 393             import = pool_elt_at_index(fib_ae_import_pool, *import_index);
 394
 395             fib_entry_import_add(import, covered);
 396         }
 397     }
 398 }
 399
 400 void
 401 fib_attached_export_covered_removed (fib_entry_t *cover,
 402                                      fib_node_index_t covered)
 403 {
 404     if (FIB_NODE_INDEX_INVALID != cover->fe_export)
 405     {
 406         /*
 407          * the covering prefix is exporting to other tables
 408          */
 409         fib_node_index_t *import_index;
 410         fib_ae_import_t *import;
 411         fib_ae_export_t *export;
 412
 413         export = pool_elt_at_index(fib_ae_export_pool, cover->fe_export);
 414
 415         /*
 416          * remove the covered entry from each of the importers
 417          */
 418         vec_foreach(import_index, export->faee_importers)
 419         {
 420             import = pool_elt_at_index(fib_ae_import_pool, *import_index);
 421
 422             fib_entry_import_remove(import, covered);
 423         }
 424     }
 425 }
 426
 427 static void
 428 fib_attached_export_cover_modified_i (fib_entry_t *fib_entry)
 429 {
 430     if (FIB_NODE_INDEX_INVALID != fib_entry->fe_import)
 431     {
 432         fib_ae_import_t *import;
 433         u32 export_fib;
 434
 435         /*
 436          * safe the temporaries we need from the existing import
 437          * since it will be toast after the purge.
 438          */
 439         import = pool_elt_at_index(fib_ae_import_pool, fib_entry->fe_import);
 440         export_fib = import->faei_export_fib;
 441
 442         /*
 443          * keep it simple. purge anything that was previously imported.
 444          * then re-evaluate the need to import.
 445          */
 446         fib_attached_export_purge(fib_entry);
 447         fib_attached_export_import(fib_entry, export_fib);
 448     }
 449 }
 450
 451 /**
 452  * \brief If this entry is tracking a cover (in another table)
 453  *        then that cover has changed. re-evaluate import.
 454  */
 455 void
 456 fib_attached_export_cover_change (fib_entry_t *fib_entry)
 457 {
 458     fib_attached_export_cover_modified_i(fib_entry);
 459 }
 460
 461 /**
 462  * \brief If this entry is tracking a cover (in another table)
 463  *        then that cover has been updated. re-evaluate import.
 464  */
 465 void
 466 fib_attached_export_cover_update (fib_entry_t *fib_entry)
 467 {
 468     fib_attached_export_cover_modified_i(fib_entry);
 469 }
 470
 471 u8*
 472 fib_ae_import_format (fib_node_index_t import_index,
 473                       u8* s)
 474 {
 475     if (FIB_NODE_INDEX_INVALID != import_index)
 476     {
 477         fib_node_index_t *index;
 478         fib_ae_import_t *import;
 479
 480         import = pool_elt_at_index(fib_ae_import_pool, import_index);
 481
 482         s = format(s, "\n  Attached-Import:%d:[", (import - fib_ae_import_pool));
 483         s = format(s, "export-prefix:%U ", format_fib_prefix, &import->faei_prefix);
 484         s = format(s, "export-entry:%d ", import->faei_export_entry);
 485         s = format(s, "export-sibling:%d ", import->faei_export_sibling);
 486         s = format(s, "exporter:%d ", import->faei_exporter);
 487         s = format(s, "export-fib:%d ", import->faei_export_fib);
 488
 489         s = format(s, "import-entry:%d ", import->faei_import_entry);
 490         s = format(s, "import-fib:%d ", import->faei_import_fib);
 491
 492         s = format(s, "importeds:[");
 493         vec_foreach(index, import->faei_importeds)
 494         {
 495             s = format(s, "%d, ", *index);
 496         }
 497             s = format(s, "]]");
 498     }
 499
 500     return (s);
 501 }
 502
 503 u8*
 504 fib_ae_export_format (fib_node_index_t export_index, u8*s)
 505 {
 506     if (FIB_NODE_INDEX_INVALID != export_index)
 507     {
 508         fib_node_index_t *index;
 509         fib_ae_export_t *export;
 510
 511         export = pool_elt_at_index(fib_ae_export_pool, export_index);
 512
 513         s = format(s, "\n  Attached-Export:%d:[", (export - fib_ae_export_pool));
 514         s = format(s, "export-entry:%d ", export->faee_ei);
 515
 516         s = format(s, "importers:[");
 517         vec_foreach(index, export->faee_importers)
 518         {
 519             s = format(s, "%d, ", *index);
 520         }
 521         s = format(s, "]]");
 522     }
 523     return (s);
 524 }