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