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 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     default:
 195         return (nhs);
 196         break;
 197     }
 198
 199     dpo_id_t via_dpo = DPO_INVALID;
 200
 201     /*
 202      * The next object in the graph after the imposition of the label
 203      * will be the DPO contributed by the path through which the packets
 204      * are to be sent. We stack the MPLS Label DPO on this path DPO
 205      */
 206     fib_path_contribute_forwarding(path_ext->fpe_path_index,
 207                                    parent_fct,
 208                                    &via_dpo);
 209
 210     if (dpo_is_drop(&via_dpo) ||
 211         load_balance_is_drop(&via_dpo))
 212     {
 213         /*
 214          * don't stack a path extension on a drop. doing so will create
 215          * a LB bucket entry on drop, and we will lose a percentage of traffic.
 216          */
 217     }
 218     else
 219     {
 220         vec_add2(nhs, nh, 1);
 221         nh->path_weight = fib_path_get_weight(path_ext->fpe_path_index);
 222         nh->path_index = path_ext->fpe_path_index;
 223         dpo_copy(&nh->path_dpo, &via_dpo);
 224
 225         /*
 226          * The label is stackable for this chain type
 227          * construct the mpls header that will be imposed in the data-path
 228          */
 229         if (!fib_path_ext_is_imp_null(path_ext))
 230         {
 231             /*
 232              * we use the parent protocol for the label so that
 233              * we pickup the correct MPLS imposition nodes to do
 234              * ip[46] processing.
 235              */
 236             dpo_proto_t chain_proto;
 237             mpls_eos_bit_t eos;
 238             index_t mldi;
 239
 240             eos = (child_fct == FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS ?
 241                    MPLS_NON_EOS :
 242                    MPLS_EOS);
 243             chain_proto = fib_forw_chain_type_to_dpo_proto(child_fct);
 244
 245             mldi = mpls_label_dpo_create(path_ext->fpe_label_stack,
 246                                          eos, 255, 0,
 247                                          chain_proto,
 248                                          &nh->path_dpo);
 249
 250             dpo_set(&nh->path_dpo,
 251                     DPO_MPLS_LABEL,
 252                     chain_proto,
 253                     mldi);
 254         }
 255     }
 256     dpo_reset(&via_dpo);
 257
 258     return (nhs);
 259 }
 260
 261 fib_path_ext_t *
 262 fib_path_ext_list_find (const fib_path_ext_list_t *list,
 263                         fib_path_ext_type_t ext_type,
 264                         const fib_route_path_t *rpath)
 265 {
 266     fib_path_ext_t *path_ext;
 267
 268     vec_foreach(path_ext, list->fpel_exts)
 269     {
 270         if ((path_ext->fpe_type == ext_type) &&
 271             !fib_path_ext_cmp(path_ext, rpath) )
 272         {
 273             return (path_ext);
 274         }
 275     }
 276     return (NULL);
 277 }
 278
 279 fib_path_ext_t *
 280 fib_path_ext_list_find_by_path_index (const fib_path_ext_list_t *list,
 281                                       fib_node_index_t path_index)
 282 {
 283     fib_path_ext_t *path_ext;
 284
 285     vec_foreach(path_ext, list->fpel_exts)
 286     {
 287         if (path_ext->fpe_path_index == path_index)
 288         {
 289             return (path_ext);
 290         }
 291     }
 292     return (NULL);
 293 }
 294
 295
 296 fib_path_ext_t *
 297 fib_path_ext_list_push_back (fib_path_ext_list_t *list,
 298                              fib_node_index_t path_list_index,
 299                              fib_path_ext_type_t ext_type,
 300                              const fib_route_path_t *rpath)
 301 {
 302     fib_path_ext_t *path_ext;
 303
 304     path_ext = fib_path_ext_list_find(list, ext_type, rpath);
 305
 306     if (NULL == path_ext)
 307     {
 308         vec_add2(list->fpel_exts, path_ext, 1);
 309         fib_path_ext_init(path_ext, path_list_index, ext_type, rpath);
 310     }
 311
 312     return (path_ext);
 313 }
 314
 315 /*
 316  * insert, sorted, a path extension to the entry's list.
 317  * It's not strictly necessary to sort the path extensions, since each
 318  * extension has the path index to which it resolves. However, by being
 319  * sorted the load-balance produced has a deterministic order, not an order
 320  * based on the sequence of extension additions. this is a considerable benefit.
 321  */
 322 fib_path_ext_t *
 323 fib_path_ext_list_insert (fib_path_ext_list_t *list,
 324                           fib_node_index_t path_list_index,
 325                           fib_path_ext_type_t ext_type,
 326                           const fib_route_path_t *rpath)
 327 {
 328     fib_path_ext_t new_path_ext, *path_ext;
 329     int i = 0;
 330
 331     if (0 == fib_path_ext_list_length(list))
 332     {
 333         return (fib_path_ext_list_push_back(list, path_list_index,
 334                                             ext_type, rpath));
 335     }
 336
 337     fib_path_ext_init(&new_path_ext, path_list_index, ext_type, rpath);
 338
 339     vec_foreach(path_ext, list->fpel_exts)
 340     {
 341         if (fib_path_ext_cmp(path_ext, rpath) < 0)
 342         {
 343             i++;
 344         }
 345         else
 346         {
 347             break;
 348         }
 349     }
 350     vec_insert_elts(list->fpel_exts, &new_path_ext, 1, i);
 351
 352     return (&(list->fpel_exts[i]));
 353 }
 354
 355 void
 356 fib_path_ext_list_resolve (fib_path_ext_list_t *list,
 357                            fib_node_index_t path_list_index)
 358 {
 359     fib_path_ext_t *path_ext;
 360
 361     vec_foreach(path_ext, list->fpel_exts)
 362     {
 363         fib_path_ext_resolve(path_ext, path_list_index);
 364     };
 365 }
 366
 367 void
 368 fib_path_ext_list_remove (fib_path_ext_list_t *list,
 369                           fib_path_ext_type_t ext_type,
 370                           const fib_route_path_t *rpath)
 371 {
 372     fib_path_ext_t *path_ext;
 373
 374     path_ext = fib_path_ext_list_find(list, ext_type, rpath);
 375
 376     if (NULL != path_ext)
 377     {
 378         /*
 379          * delete the element moving the remaining elements down 1 position.
 380          * this preserves the sorted order.
 381          */
 382         vec_free(path_ext->fpe_label_stack);
 383         vec_delete(list->fpel_exts, 1, (path_ext - list->fpel_exts));
 384     }
 385 }
 386
 387 void
 388 fib_path_ext_list_flush (fib_path_ext_list_t *list)
 389 {
 390     fib_path_ext_t *path_ext;
 391
 392     vec_foreach(path_ext, list->fpel_exts)
 393     {
 394         vec_free(path_ext->fpe_label_stack);
 395     };
 396     vec_free(list->fpel_exts);
 397     list->fpel_exts = NULL;
 398 }
 399
 400 u8*
 401 format_fib_path_ext_list (u8 * s, va_list * args)
 402 {
 403     fib_path_ext_list_t *list;
 404     fib_path_ext_t *path_ext;
 405
 406     list = va_arg (*args, fib_path_ext_list_t *);
 407
 408     if (fib_path_ext_list_length(list))
 409     {
 410         s = format(s, "    Extensions:");
 411         vec_foreach(path_ext, list->fpel_exts)
 412         {
 413             s = format(s, "\n     %U", format_fib_path_ext, path_ext);
 414         };
 415     }
 416
 417     return (s);
 418 }
 419
 420 int
 421 fib_path_ext_list_length (const fib_path_ext_list_t *list)
 422 {
 423     return (vec_len(list->fpel_exts));
 424 }