src/vnet/feature/registration.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/vnet.h>
  17 #include <vnet/ip/ip.h>
  18 #include <vnet/mpls/mpls.h>
  19
  20 /**
  21  * @file
  22  * @brief Feature Subgraph Ordering.
  23
  24     Dynamically compute feature subgraph ordering by performing a
  25     topological sort across a set of "feature A before feature B" and
  26     "feature C after feature B" constraints.
  27
  28     Use the topological sort result to set up vnet_config_main_t's for
  29     use at runtime.
  30
  31     Feature subgraph arcs are simple enough. They start at specific
  32     fixed nodes, and end at specific fixed nodes.  In between, a
  33     per-interface current feature configuration dictates which
  34     additional nodes each packet visits. Each so-called feature node
  35     can [of course] drop any specific packet.
  36
  37     See ip4_forward.c, ip6_forward.c in this directory to see the
  38     current rx-unicast, rx-multicast, and tx feature subgraph arc
  39     definitions.
  40
  41     Let's say that we wish to add a new feature to the ip4 unicast
  42     feature subgraph arc, which needs to run before @c ip4-lookup.  In
  43     either base code or a plugin,
  44     <CODE><PRE>
  45     \#include <vnet/feature/feature.h>
  46     </PRE></CODE>
  47
  48     and add the new feature as shown:
  49
  50     <CODE><PRE>
  51     VNET_FEATURE_INIT (ip4_lookup, static) =
  52     {
  53       .arch_name = "ip4-unicast",
  54       .node_name = "my-ip4-unicast-feature",
  55       .runs_before = VLIB_FEATURES ("ip4-lookup")
  56     };
  57     </PRE></CODE>
  58
  59     Here's the standard coding pattern to enable / disable
  60     @c my-ip4-unicast-feature on an interface:
  61
  62     <CODE><PRE>
  63
  64     sw_if_index = <interface-handle>
  65     vnet_feature_enable_disable ("ip4-unicast", "my-ip4-unicast-feature",
  66                                  sw_if_index, 1 );
  67     </PRE></CODE>
  68
  69     Here's how to obtain the correct next node index in packet
  70     processing code, aka in the implementation of @c my-ip4-unicast-feature:
  71
  72     <CODE><PRE>
  73     vnet_feature_next (sw_if_index0, &next0, b0);
  74
  75     </PRE></CODE>
  76
  77     Nodes are free to drop or otherwise redirect packets. Packets
  78     which "pass" should be enqueued via the next0 arc computed by
  79     vnet_feature_next.
  80 */
  81
  82
  83 static int
  84 comma_split (u8 * s, u8 ** a, u8 ** b)
  85 {
  86   *a = s;
  87
  88   while (*s && *s != ',')
  89     s++;
  90
  91   if (*s == ',')
  92     *s = 0;
  93   else
  94     return 1;
  95
  96   *b = (u8 *) (s + 1);
  97   return 0;
  98 }
  99
 100 /**
 101  * @brief Initialize a feature graph arc
 102  * @param vm vlib main structure pointer
 103  * @param vcm vnet config main structure pointer
 104  * @param feature_start_nodes names of start-nodes which use this
 105  *        feature graph arc
 106  * @param num_feature_start_nodes number of start-nodes
 107  * @param first_reg first element in
 108  *        [an __attribute__((constructor)) function built, or
 109  *        otherwise created] singly-linked list of feature registrations
 110  * @param first_const first element in
 111  *        [an __attribute__((constructor)) function built, or
 112  *        otherwise created] singly-linked list of bulk order constraints
 113  * @param [out] in_feature_nodes returned vector of
 114  *        topologically-sorted feature node names, for use in
 115  *        show commands
 116  * @returns 0 on success, otherwise an error message. Errors
 117  *        are fatal since they invariably involve mistyped node-names, or
 118  *        genuinely missing node-names
 119  */
 120 clib_error_t *
 121 vnet_feature_arc_init (vlib_main_t * vm,
 122                        vnet_config_main_t * vcm,
 123                        char **feature_start_nodes,
 124                        int num_feature_start_nodes,
 125                        char *last_in_arc,
 126                        vnet_feature_registration_t * first_reg,
 127                        vnet_feature_constraint_registration_t *
 128                        first_const_set, char ***in_feature_nodes)
 129 {
 130   uword *index_by_name;
 131   uword *reg_by_index;
 132   u8 **node_names = 0;
 133   u8 *node_name;
 134   char *prev_name;
 135   char **these_constraints;
 136   char *this_constraint_c;
 137   u8 **constraints = 0;
 138   u8 *constraint_tuple;
 139   u8 *this_constraint;
 140   u8 **orig, **closure;
 141   uword *p;
 142   int i, j, k;
 143   u8 *a_name, *b_name;
 144   int a_index, b_index;
 145   int n_features;
 146   u32 *result = 0;
 147   vnet_feature_registration_t *this_reg = 0;
 148   vnet_feature_constraint_registration_t *this_const_set = 0;
 149   char **feature_nodes = 0;
 150   hash_pair_t *hp;
 151   u8 **keys_to_delete = 0;
 152
 153   index_by_name = hash_create_string (0, sizeof (uword));
 154   reg_by_index = hash_create (0, sizeof (uword));
 155
 156   this_reg = first_reg;
 157
 158   /* Autogenerate <node> before <last-in-arc> constraints */
 159   if (last_in_arc)
 160     {
 161       while (this_reg)
 162         {
 163           /* If this isn't the last node in the arc... */
 164           if (clib_strcmp (this_reg->node_name, last_in_arc))
 165             {
 166               /*
 167                * Add an explicit constraint so this feature will run
 168                * before the last node in the arc
 169                */
 170               constraint_tuple = format (0, "%s,%s%c", this_reg->node_name,
 171                                          last_in_arc, 0);
 172               vec_add1 (constraints, constraint_tuple);
 173             }
 174           this_reg = this_reg->next_in_arc;
 175         }
 176       this_reg = first_reg;
 177     }
 178
 179   /* pass 1, collect feature node names, construct a before b pairs */
 180   while (this_reg)
 181     {
 182       node_name = format (0, "%s%c", this_reg->node_name, 0);
 183       hash_set (reg_by_index, vec_len (node_names), (uword) this_reg);
 184
 185       hash_set_mem (index_by_name, node_name, vec_len (node_names));
 186
 187       vec_add1 (node_names, node_name);
 188
 189       these_constraints = this_reg->runs_before;
 190       while (these_constraints && these_constraints[0])
 191         {
 192           this_constraint_c = these_constraints[0];
 193
 194           constraint_tuple = format (0, "%s,%s%c", node_name,
 195                                      this_constraint_c, 0);
 196           vec_add1 (constraints, constraint_tuple);
 197           these_constraints++;
 198         }
 199
 200       these_constraints = this_reg->runs_after;
 201       while (these_constraints && these_constraints[0])
 202         {
 203           this_constraint_c = these_constraints[0];
 204
 205           constraint_tuple = format (0, "%s,%s%c",
 206                                      this_constraint_c, node_name, 0);
 207           vec_add1 (constraints, constraint_tuple);
 208           these_constraints++;
 209         }
 210
 211       this_reg = this_reg->next_in_arc;
 212     }
 213
 214   /* pass 2, collect bulk "a then b then c then d" constraints */
 215   this_const_set = first_const_set;
 216   while (this_const_set)
 217     {
 218       these_constraints = this_const_set->node_names;
 219
 220       prev_name = 0;
 221       /* Across the list of constraints */
 222       while (these_constraints && these_constraints[0])
 223         {
 224           this_constraint_c = these_constraints[0];
 225           p = hash_get_mem (index_by_name, this_constraint_c);
 226           if (p == 0)
 227             {
 228               clib_warning
 229                 ("bulk constraint feature node '%s' not found for arc '%s'",
 230                  this_constraint_c);
 231               these_constraints++;
 232               continue;
 233             }
 234
 235           if (prev_name == 0)
 236             {
 237               prev_name = this_constraint_c;
 238               these_constraints++;
 239               continue;
 240             }
 241
 242           constraint_tuple = format (0, "%s,%s%c", prev_name,
 243                                      this_constraint_c, 0);
 244           vec_add1 (constraints, constraint_tuple);
 245           prev_name = this_constraint_c;
 246           these_constraints++;
 247         }
 248
 249       this_const_set = this_const_set->next_in_arc;
 250     }
 251
 252   n_features = vec_len (node_names);
 253   orig = clib_ptclosure_alloc (n_features);
 254
 255   for (i = 0; i < vec_len (constraints); i++)
 256     {
 257       this_constraint = constraints[i];
 258
 259       if (comma_split (this_constraint, &a_name, &b_name))
 260         return clib_error_return (0, "comma_split failed!");
 261
 262       p = hash_get_mem (index_by_name, a_name);
 263       /*
 264        * Note: the next two errors mean that something is
 265        * b0rked. As in: if you code "A depends on B," and you forget
 266        * to define a FEATURE_INIT macro for B, you lose.
 267        * Nonexistent graph nodes are tolerated.
 268        */
 269       if (p == 0)
 270         {
 271           clib_warning ("feature node '%s' not found (before '%s', arc '%s')",
 272                         a_name, b_name, first_reg->arc_name);
 273           continue;
 274         }
 275       a_index = p[0];
 276
 277       p = hash_get_mem (index_by_name, b_name);
 278       if (p == 0)
 279         {
 280           clib_warning ("feature node '%s' not found (after '%s', arc '%s')",
 281                         b_name, a_name, first_reg->arc_name);
 282           continue;
 283         }
 284       b_index = p[0];
 285
 286       /* add a before b to the original set of constraints */
 287       orig[a_index][b_index] = 1;
 288       vec_free (this_constraint);
 289     }
 290
 291   /* Compute the positive transitive closure of the original constraints */
 292   closure = clib_ptclosure (orig);
 293
 294   /* Compute a partial order across feature nodes, if one exists. */
 295 again:
 296   for (i = 0; i < n_features; i++)
 297     {
 298       for (j = 0; j < n_features; j++)
 299         {
 300           if (closure[i][j])
 301             goto item_constrained;
 302         }
 303       /* Item i can be output */
 304       vec_add1 (result, i);
 305       {
 306         for (k = 0; k < n_features; k++)
 307           closure[k][i] = 0;
 308         /*
 309          * Add a "Magic" a before a constraint.
 310          * This means we'll never output it again
 311          */
 312         closure[i][i] = 1;
 313         goto again;
 314       }
 315     item_constrained:
 316       ;
 317     }
 318
 319   /* see if we got a partial order... */
 320   if (vec_len (result) != n_features)
 321     return clib_error_return
 322       (0, "Arc '%s': failed to find a suitable feature order!",
 323        first_reg->arc_name);
 324
 325   /*
 326    * We win.
 327    * Bind the index variables, and output the feature node name vector
 328    * using the partial order we just computed. Result is in stack
 329    * order, because the entry with the fewest constraints (e.g. none)
 330    * is output first, etc.
 331    */
 332
 333   for (i = n_features - 1; i >= 0; i--)
 334     {
 335       p = hash_get (reg_by_index, result[i]);
 336       ASSERT (p != 0);
 337       this_reg = (vnet_feature_registration_t *) p[0];
 338       if (this_reg->feature_index_ptr)
 339         *this_reg->feature_index_ptr = n_features - (i + 1);
 340       this_reg->feature_index = n_features - (i + 1);
 341       vec_add1 (feature_nodes, this_reg->node_name);
 342     }
 343
 344   /* Set up the config infrastructure */
 345   vnet_config_init (vm, vcm,
 346                     feature_start_nodes,
 347                     num_feature_start_nodes,
 348                     feature_nodes, vec_len (feature_nodes));
 349
 350   /* Save a copy for show command */
 351   *in_feature_nodes = feature_nodes;
 352
 353   /* Finally, clean up all the shit we allocated */
 354   /* *INDENT-OFF* */
 355   hash_foreach_pair (hp, index_by_name,
 356   ({
 357     vec_add1 (keys_to_delete, (u8 *)hp->key);
 358   }));
 359   /* *INDENT-ON* */
 360   hash_free (index_by_name);
 361   for (i = 0; i < vec_len (keys_to_delete); i++)
 362     vec_free (keys_to_delete[i]);
 363   vec_free (keys_to_delete);
 364   hash_free (reg_by_index);
 365   vec_free (result);
 366   clib_ptclosure_free (orig);
 367   clib_ptclosure_free (closure);
 368   return 0;
 369 }
 370
 371 /*
 372  * fd.io coding-style-patch-verification: ON
 373  *
 374  * Local Variables:
 375  * eval: (c-set-style "gnu")
 376  * End:
 377  */