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         else if (child_fct == FIB_FORW_CHAIN_TYPE_MPLS_EOS)
 259         {
 260             /*
 261              * MPLS EOS packets using an imp-null. Insert the disposition.
 262              */
 263             fib_path_stack_mpls_disp(nh->path_index,
 264                                      fib_forw_chain_type_to_dpo_proto(parent_fct),
 265                                      &nh->path_dpo);
 266         }
 267     }
 268     dpo_reset(&via_dpo);
 269
 270     return (nhs);
 271 }
 272
 273 fib_path_ext_t *
 274 fib_path_ext_list_find (const fib_path_ext_list_t *list,
 275                         fib_path_ext_type_t ext_type,
 276                         const fib_route_path_t *rpath)
 277 {
 278     fib_path_ext_t *path_ext;
 279
 280     vec_foreach(path_ext, list->fpel_exts)
 281     {
 282         if ((path_ext->fpe_type == ext_type) &&
 283             !fib_path_ext_cmp(path_ext, rpath) )
 284         {
 285             return (path_ext);
 286         }
 287     }
 288     return (NULL);
 289 }
 290
 291 fib_path_ext_t *
 292 fib_path_ext_list_find_by_path_index (const fib_path_ext_list_t *list,
 293                                       fib_node_index_t path_index)
 294 {
 295     fib_path_ext_t *path_ext;
 296
 297     vec_foreach(path_ext, list->fpel_exts)
 298     {
 299         if (path_ext->fpe_path_index == path_index)
 300         {
 301             return (path_ext);
 302         }
 303     }
 304     return (NULL);
 305 }
 306
 307
 308 fib_path_ext_t *
 309 fib_path_ext_list_push_back (fib_path_ext_list_t *list,
 310                              fib_node_index_t path_list_index,
 311                              fib_path_ext_type_t ext_type,
 312                              const fib_route_path_t *rpath)
 313 {
 314     fib_path_ext_t *path_ext;
 315
 316     path_ext = fib_path_ext_list_find(list, ext_type, rpath);
 317
 318     if (NULL == path_ext)
 319     {
 320         vec_add2(list->fpel_exts, path_ext, 1);
 321         fib_path_ext_init(path_ext, path_list_index, ext_type, rpath);
 322     }
 323
 324     return (path_ext);
 325 }
 326
 327 /*
 328  * insert, sorted, a path extension to the entry's list.
 329  * It's not strictly necessary to sort the path extensions, since each
 330  * extension has the path index to which it resolves. However, by being
 331  * sorted the load-balance produced has a deterministic order, not an order
 332  * based on the sequence of extension additions. this is a considerable benefit.
 333  */
 334 fib_path_ext_t *
 335 fib_path_ext_list_insert (fib_path_ext_list_t *list,
 336                           fib_node_index_t path_list_index,
 337                           fib_path_ext_type_t ext_type,
 338                           const fib_route_path_t *rpath)
 339 {
 340     fib_path_ext_t new_path_ext, *path_ext;
 341     int i = 0;
 342
 343     if (0 == fib_path_ext_list_length(list))
 344     {
 345         return (fib_path_ext_list_push_back(list, path_list_index,
 346                                             ext_type, rpath));
 347     }
 348
 349     fib_path_ext_init(&new_path_ext, path_list_index, ext_type, rpath);
 350
 351     vec_foreach(path_ext, list->fpel_exts)
 352     {
 353         int res = fib_path_ext_cmp(path_ext, rpath);
 354
 355         if (0 == res)
 356         {
 357             /*
 358              * don't add duplicate extensions. modify instead
 359              */
 360             vec_free(path_ext->fpe_label_stack);
 361             *path_ext = new_path_ext;
 362             goto done;
 363         }
 364         else if (res < 0)
 365         {
 366             i++;
 367         }
 368         else
 369         {
 370             break;
 371         }
 372     }
 373     vec_insert_elts(list->fpel_exts, &new_path_ext, 1, i);
 374 done:
 375     return (&(list->fpel_exts[i]));
 376 }
 377
 378 void
 379 fib_path_ext_list_resolve (fib_path_ext_list_t *list,
 380                            fib_node_index_t path_list_index)
 381 {
 382     fib_path_ext_t *path_ext;
 383
 384     vec_foreach(path_ext, list->fpel_exts)
 385     {
 386         fib_path_ext_resolve(path_ext, path_list_index);
 387     };
 388 }
 389
 390 void
 391 fib_path_ext_list_remove (fib_path_ext_list_t *list,
 392                           fib_path_ext_type_t ext_type,
 393                           const fib_route_path_t *rpath)
 394 {
 395     fib_path_ext_t *path_ext;
 396
 397     path_ext = fib_path_ext_list_find(list, ext_type, rpath);
 398
 399     if (NULL != path_ext)
 400     {
 401         /*
 402          * delete the element moving the remaining elements down 1 position.
 403          * this preserves the sorted order.
 404          */
 405         vec_free(path_ext->fpe_label_stack);
 406         vec_delete(list->fpel_exts, 1, (path_ext - list->fpel_exts));
 407     }
 408 }
 409
 410 void
 411 fib_path_ext_list_flush (fib_path_ext_list_t *list)
 412 {
 413     fib_path_ext_t *path_ext;
 414
 415     vec_foreach(path_ext, list->fpel_exts)
 416     {
 417         vec_free(path_ext->fpe_label_stack);
 418     };
 419     vec_free(list->fpel_exts);
 420     list->fpel_exts = NULL;
 421 }
 422
 423 u8*
 424 format_fib_path_ext_list (u8 * s, va_list * args)
 425 {
 426     fib_path_ext_list_t *list;
 427     fib_path_ext_t *path_ext;
 428
 429     list = va_arg (*args, fib_path_ext_list_t *);
 430
 431     if (fib_path_ext_list_length(list))
 432     {
 433         s = format(s, "    Extensions:");
 434         vec_foreach(path_ext, list->fpel_exts)
 435         {
 436             s = format(s, "\n     %U", format_fib_path_ext, path_ext);
 437         };
 438     }
 439
 440     return (s);
 441 }
 442
 443 int
 444 fib_path_ext_list_length (const fib_path_ext_list_t *list)
 445 {
 446     return (vec_len(list->fpel_exts));
 447 }