src/vnet/fib/fib_path_ext.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/mpls/mpls.h>
  17 #include <vnet/dpo/mpls_label_dpo.h>
  18 #include <vnet/dpo/load_balance.h>
  19 #include <vnet/dpo/drop_dpo.h>
  20
  21 #include <vnet/fib/fib_path_ext.h>
  22 #include <vnet/fib/fib_entry_src.h>
  23 #include <vnet/fib/fib_path.h>
  24 #include <vnet/fib/fib_path_list.h>
  25 #include <vnet/fib/fib_internal.h>
  26
  27 const char *fib_path_ext_adj_flags_names[] = FIB_PATH_EXT_ADJ_ATTR_NAMES;
  28
  29 u8 *
  30 format_fib_path_ext (u8 * s, va_list * args)
  31 {
  32     fib_path_ext_t *path_ext;
  33     u32 ii;
  34
  35     path_ext = va_arg (*args, fib_path_ext_t *);
  36
  37     s = format(s, "path:%d ", path_ext->fpe_path_index);
  38
  39     switch (path_ext->fpe_type)
  40     {
  41     case FIB_PATH_EXT_MPLS:
  42         s = format(s, "labels:",
  43                    path_ext->fpe_path_index);
  44         for (ii = 0; ii < vec_len(path_ext->fpe_path.frp_label_stack); ii++)
  45         {
  46             s = format(s, "%U ",
  47                        format_mpls_unicast_label,
  48                        path_ext->fpe_path.frp_label_stack[ii]);
  49         }
  50         break;
  51     case FIB_PATH_EXT_ADJ: {
  52         fib_path_ext_adj_attr_t attr;
  53
  54         s = format(s, "adj-flags:");
  55         if (path_ext->fpe_adj_flags)
  56         {
  57             FOR_EACH_PATH_EXT_ADJ_ATTR(attr)
  58             {
  59                 s = format(s, "%s", fib_path_ext_adj_flags_names[attr]);
  60             }
  61         }
  62         else
  63         {
  64             s = format(s, "None");
  65         }
  66         break;
  67     }
  68     }
  69     return (s);
  70 }
  71
  72 int
  73 fib_path_ext_cmp (fib_path_ext_t *path_ext,
  74                   const fib_route_path_t *rpath)
  75 {
  76     return (fib_route_path_cmp(&path_ext->fpe_path, rpath));
  77 }
  78
  79 static fib_path_list_walk_rc_t
  80 fib_path_ext_match (fib_node_index_t pl_index,
  81                     fib_node_index_t path_index,
  82                     void *ctx)
  83 {
  84     fib_path_ext_t *path_ext = ctx;
  85
  86     if (!fib_path_cmp_w_route_path(path_index,
  87                                    &path_ext->fpe_path))
  88     {
  89         path_ext->fpe_path_index = path_index;
  90         return (FIB_PATH_LIST_WALK_STOP);
  91     }
  92     return (FIB_PATH_LIST_WALK_CONTINUE);
  93 }
  94
  95 void
  96 fib_path_ext_resolve (fib_path_ext_t *path_ext,
  97                       fib_node_index_t path_list_index)
  98 {
  99     /*
 100      * Find the path on the path list that this is an extension for
 101      */
 102     path_ext->fpe_path_index = FIB_NODE_INDEX_INVALID;
 103     fib_path_list_walk(path_list_index,
 104                        fib_path_ext_match,
 105                        path_ext);
 106 }
 107
 108 static void
 109 fib_path_ext_init (fib_path_ext_t *path_ext,
 110                    fib_node_index_t path_list_index,
 111                    fib_path_ext_type_t ext_type,
 112                    const fib_route_path_t *rpath)
 113 {
 114     path_ext->fpe_path = *rpath;
 115     path_ext->fpe_path_index = FIB_NODE_INDEX_INVALID;
 116     path_ext->fpe_adj_flags = FIB_PATH_EXT_ADJ_FLAG_NONE;
 117     path_ext->fpe_type = ext_type;
 118
 119     fib_path_ext_resolve(path_ext, path_list_index);
 120 }
 121
 122 /**
 123  * @brief Return true if the label stack is implicit null
 124  */
 125 static int
 126 fib_path_ext_is_imp_null (fib_path_ext_t *path_ext)
 127 {
 128     return ((1 == vec_len(path_ext->fpe_label_stack)) &&
 129             (MPLS_IETF_IMPLICIT_NULL_LABEL == path_ext->fpe_label_stack[0]));
 130 }
 131
 132 load_balance_path_t *
 133 fib_path_ext_stack (fib_path_ext_t *path_ext,
 134                     fib_forward_chain_type_t child_fct,
 135                     fib_forward_chain_type_t imp_null_fct,
 136                     load_balance_path_t *nhs)
 137 {
 138     fib_forward_chain_type_t parent_fct;
 139     load_balance_path_t *nh;
 140
 141     if (!fib_path_is_resolved(path_ext->fpe_path_index))
 142         return (nhs);
 143
 144     /*
 145      * Since we are stacking this path-extension, it must have a valid out
 146      * label. From the chain type request by the child, determine what
 147      * chain type we will request from the parent.
 148      */
 149     switch (child_fct)
 150     {
 151     case FIB_FORW_CHAIN_TYPE_MPLS_EOS:
 152     {
 153         /*
 154          * The EOS chain is a tricky since, when the path has an imp NULL one cannot know
 155          * the adjacency to link to without knowing what the packets payload protocol
 156          * will be once the label is popped.
 157          */
 158         if (fib_path_ext_is_imp_null(path_ext))
 159         {
 160             parent_fct = imp_null_fct;
 161         }
 162         else
 163         {
 164             /*
 165              * we have a label to stack. packets will thus be labelled when
 166              * they encounter the child, ergo, non-eos.
 167              */
 168             parent_fct = FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS;
 169         }
 170         break;
 171     }
 172     case FIB_FORW_CHAIN_TYPE_UNICAST_IP4:
 173     case FIB_FORW_CHAIN_TYPE_UNICAST_IP6:
 174         if (fib_path_ext_is_imp_null(path_ext))
 175         {
 176             /*
 177              * implicit-null label for the eos or IP chain, need to pick up
 178              * the IP adj
 179              */
 180             parent_fct = child_fct;
 181         }
 182         else
 183         {
 184             /*
 185              * we have a label to stack. packets will thus be labelled when
 186              * they encounter the child, ergo, non-eos.
 187              */
 188             parent_fct = FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS;
 189         }
 190         break;
 191     case FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS:
 192         parent_fct = child_fct;
 193         break;
 194     case FIB_FORW_CHAIN_TYPE_ETHERNET:
 195         parent_fct = FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS;
 196         break;
 197     default:
 198         return (nhs);
 199         break;
 200     }
 201
 202     dpo_id_t via_dpo = DPO_INVALID;
 203
 204     /*
 205      * The next object in the graph after the imposition of the label
 206      * will be the DPO contributed by the path through which the packets
 207      * are to be sent. We stack the MPLS Label DPO on this path DPO
 208      */
 209     fib_path_contribute_forwarding(path_ext->fpe_path_index,
 210                                    parent_fct,
 211                                    &via_dpo);
 212
 213     if (dpo_is_drop(&via_dpo) ||
 214         load_balance_is_drop(&via_dpo))
 215     {
 216         /*
 217          * don't stack a path extension on a drop. doing so will create
 218          * a LB bucket entry on drop, and we will lose a percentage of traffic.
 219          */
 220     }
 221     else
 222     {
 223         vec_add2(nhs, nh, 1);
 224         nh->path_weight = fib_path_get_weight(path_ext->fpe_path_index);
 225         nh->path_index = path_ext->fpe_path_index;
 226         dpo_copy(&nh->path_dpo, &via_dpo);
 227
 228         /*
 229          * The label is stackable for this chain type
 230          * construct the mpls header that will be imposed in the data-path
 231          */
 232         if (!fib_path_ext_is_imp_null(path_ext))
 233         {
 234             /*
 235              * we use the parent protocol for the label so that
 236              * we pickup the correct MPLS imposition nodes to do
 237              * ip[46] processing.
 238              */
 239             dpo_proto_t chain_proto;
 240             mpls_eos_bit_t eos;
 241             index_t mldi;
 242
 243             eos = (child_fct == FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS ?
 244                    MPLS_NON_EOS :
 245                    MPLS_EOS);
 246             chain_proto = fib_forw_chain_type_to_dpo_proto(child_fct);
 247
 248             mldi = mpls_label_dpo_create(path_ext->fpe_label_stack,
 249                                          eos, 255, 0,
 250                                          chain_proto,
 251                                          &nh->path_dpo);
 252
 253             dpo_set(&nh->path_dpo,
 254                     DPO_MPLS_LABEL,
 255                     chain_proto,
 256                     mldi);
 257         }
 258     }
 259     dpo_reset(&via_dpo);
 260
 261     return (nhs);
 262 }
 263
 264 fib_path_ext_t *
 265 fib_path_ext_list_find (const fib_path_ext_list_t *list,
 266                         fib_path_ext_type_t ext_type,
 267                         const fib_route_path_t *rpath)
 268 {
 269     fib_path_ext_t *path_ext;
 270
 271     vec_foreach(path_ext, list->fpel_exts)
 272     {
 273         if ((path_ext->fpe_type == ext_type) &&
 274             !fib_path_ext_cmp(path_ext, rpath) )
 275         {
 276             return (path_ext);
 277         }
 278     }
 279     return (NULL);
 280 }
 281
 282 fib_path_ext_t *
 283 fib_path_ext_list_find_by_path_index (const fib_path_ext_list_t *list,
 284                                       fib_node_index_t path_index)
 285 {
 286     fib_path_ext_t *path_ext;
 287
 288     vec_foreach(path_ext, list->fpel_exts)
 289     {
 290         if (path_ext->fpe_path_index == path_index)
 291         {
 292             return (path_ext);
 293         }
 294     }
 295     return (NULL);
 296 }
 297
 298
 299 fib_path_ext_t *
 300 fib_path_ext_list_push_back (fib_path_ext_list_t *list,
 301                              fib_node_index_t path_list_index,
 302                              fib_path_ext_type_t ext_type,
 303                              const fib_route_path_t *rpath)
 304 {
 305     fib_path_ext_t *path_ext;
 306
 307     path_ext = fib_path_ext_list_find(list, ext_type, rpath);
 308
 309     if (NULL == path_ext)
 310     {
 311         vec_add2(list->fpel_exts, path_ext, 1);
 312         fib_path_ext_init(path_ext, path_list_index, ext_type, rpath);
 313     }
 314
 315     return (path_ext);
 316 }
 317
 318 /*
 319  * insert, sorted, a path extension to the entry's list.
 320  * It's not strictly necessary to sort the path extensions, since each
 321  * extension has the path index to which it resolves. However, by being
 322  * sorted the load-balance produced has a deterministic order, not an order
 323  * based on the sequence of extension additions. this is a considerable benefit.
 324  */
 325 fib_path_ext_t *
 326 fib_path_ext_list_insert (fib_path_ext_list_t *list,
 327                           fib_node_index_t path_list_index,
 328                           fib_path_ext_type_t ext_type,
 329                           const fib_route_path_t *rpath)
 330 {
 331     fib_path_ext_t new_path_ext, *path_ext;
 332     int i = 0;
 333
 334     if (0 == fib_path_ext_list_length(list))
 335     {
 336         return (fib_path_ext_list_push_back(list, path_list_index,
 337                                             ext_type, rpath));
 338     }
 339
 340     fib_path_ext_init(&new_path_ext, path_list_index, ext_type, rpath);
 341
 342     vec_foreach(path_ext, list->fpel_exts)
 343     {
 344         int res = fib_path_ext_cmp(path_ext, rpath);
 345
 346         if (0 == res)
 347         {
 348             /*
 349              * don't add duplicate extensions. modify instead
 350              */
 351             vec_free(path_ext->fpe_label_stack);
 352             *path_ext = new_path_ext;
 353             goto done;
 354         }
 355         else if (res < 0)
 356         {
 357             i++;
 358         }
 359         else
 360         {
 361             break;
 362         }
 363     }
 364     vec_insert_elts(list->fpel_exts, &new_path_ext, 1, i);
 365 done:
 366     return (&(list->fpel_exts[i]));
 367 }
 368
 369 void
 370 fib_path_ext_list_resolve (fib_path_ext_list_t *list,
 371                            fib_node_index_t path_list_index)
 372 {
 373     fib_path_ext_t *path_ext;
 374
 375     vec_foreach(path_ext, list->fpel_exts)
 376     {
 377         fib_path_ext_resolve(path_ext, path_list_index);
 378     };
 379 }
 380
 381 void
 382 fib_path_ext_list_remove (fib_path_ext_list_t *list,
 383                           fib_path_ext_type_t ext_type,
 384                           const fib_route_path_t *rpath)
 385 {
 386     fib_path_ext_t *path_ext;
 387
 388     path_ext = fib_path_ext_list_find(list, ext_type, rpath);
 389
 390     if (NULL != path_ext)
 391     {
 392         /*
 393          * delete the element moving the remaining elements down 1 position.
 394          * this preserves the sorted order.
 395          */
 396         vec_free(path_ext->fpe_label_stack);
 397         vec_delete(list->fpel_exts, 1, (path_ext - list->fpel_exts));
 398     }
 399 }
 400
 401 void
 402 fib_path_ext_list_flush (fib_path_ext_list_t *list)
 403 {
 404     fib_path_ext_t *path_ext;
 405
 406     vec_foreach(path_ext, list->fpel_exts)
 407     {
 408         vec_free(path_ext->fpe_label_stack);
 409     };
 410     vec_free(list->fpel_exts);
 411     list->fpel_exts = NULL;
 412 }
 413
 414 u8*
 415 format_fib_path_ext_list (u8 * s, va_list * args)
 416 {
 417     fib_path_ext_list_t *list;
 418     fib_path_ext_t *path_ext;
 419
 420     list = va_arg (*args, fib_path_ext_list_t *);
 421
 422     if (fib_path_ext_list_length(list))
 423     {
 424         s = format(s, "    Extensions:");
 425         vec_foreach(path_ext, list->fpel_exts)
 426         {
 427             s = format(s, "\n     %U", format_fib_path_ext, path_ext);
 428         };
 429     }
 430
 431     return (s);
 432 }
 433
 434 int
 435 fib_path_ext_list_length (const fib_path_ext_list_t *list)
 436 {
 437     return (vec_len(list->fpel_exts));
 438 }