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