src/vlib/init.c

   1 /*
   2  * Copyright (c) 2015 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  * init.c: mechanism for functions to be called at init/exit.
  17  *
  18  * Copyright (c) 2008 Eliot Dresselhaus
  19  *
  20  * Permission is hereby granted, free of charge, to any person obtaining
  21  * a copy of this software and associated documentation files (the
  22  * "Software"), to deal in the Software without restriction, including
  23  * without limitation the rights to use, copy, modify, merge, publish,
  24  * distribute, sublicense, and/or sell copies of the Software, and to
  25  * permit persons to whom the Software is furnished to do so, subject to
  26  * the following conditions:
  27  *
  28  * The above copyright notice and this permission notice shall be
  29  * included in all copies or substantial portions of the Software.
  30  *
  31  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  32  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  33  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  34  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  35  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  36  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  37  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  38  */
  39
  40 #include <vlib/vlib.h>
  41 #include <vppinfra/ptclosure.h>
  42
  43 /**
  44  * @file
  45  * @brief Init function ordering and execution implementation
  46  * Topological sort for all classes of init functions, and
  47  * a relatively simple API routine to invoke them.
  48  */
  49
  50 /*? %%clicmd:group_label Init functions %% ?*/
  51
  52 static int
  53 comma_split (u8 * s, u8 ** a, u8 ** b)
  54 {
  55   *a = s;
  56
  57   while (*s && *s != ',')
  58     s++;
  59
  60   if (*s == ',')
  61     *s = 0;
  62   else
  63     return 1;
  64
  65   *b = (u8 *) (s + 1);
  66   return 0;
  67 }
  68
  69 /**
  70  * @brief Topological sorter for init function chains.
  71  * @param head [in/out] address of the listhead to be sorted
  72  * @returns 0 on success, otherwise a clib_error_t *.
  73  */
  74
  75 clib_error_t *vlib_sort_init_exit_functions
  76   (_vlib_init_function_list_elt_t ** head)
  77 {
  78   uword *index_by_name;
  79   uword *reg_by_index;
  80   u8 **init_f_names = 0;
  81   u8 *init_f_name;
  82   char **these_constraints;
  83   char *this_constraint_c;
  84   u8 **constraints = 0;
  85   u8 *constraint_tuple;
  86   u8 *this_constraint;
  87   char *prev_name;
  88   u8 **orig, **closure;
  89   uword *p;
  90   int i, j, k;
  91   u8 *a_name, *b_name;
  92   int a_index, b_index;
  93   int n_init_fns;
  94   u32 *result = 0;
  95   _vlib_init_function_list_elt_t *this_reg = 0;
  96   hash_pair_t *hp;
  97   u8 **keys_to_delete = 0;
  98
  99   /*
 100    * two hash tables: name to index in init_f_names, and
 101    * init function registration pointer by index
 102    */
 103   index_by_name = hash_create_string (0, sizeof (uword));
 104   reg_by_index = hash_create (0, sizeof (uword));
 105
 106   this_reg = *head;
 107
 108   /* pass 1, collect init fcn names, construct a before b pairs */
 109   while (this_reg)
 110     {
 111       init_f_name = format (0, "%s%c", this_reg->name, 0);
 112       hash_set (reg_by_index, vec_len (init_f_names), (uword) this_reg);
 113
 114       hash_set_mem (index_by_name, init_f_name, vec_len (init_f_names));
 115
 116       vec_add1 (init_f_names, init_f_name);
 117
 118       these_constraints = this_reg->runs_before;
 119       while (these_constraints && these_constraints[0])
 120         {
 121           this_constraint_c = these_constraints[0];
 122
 123           constraint_tuple = format (0, "%s,%s%c", init_f_name,
 124                                      this_constraint_c, 0);
 125           vec_add1 (constraints, constraint_tuple);
 126           these_constraints++;
 127         }
 128
 129       these_constraints = this_reg->runs_after;
 130       while (these_constraints && these_constraints[0])
 131         {
 132           this_constraint_c = these_constraints[0];
 133
 134           constraint_tuple = format (0, "%s,%s%c",
 135                                      this_constraint_c, init_f_name, 0);
 136           vec_add1 (constraints, constraint_tuple);
 137           these_constraints++;
 138         }
 139
 140       this_reg = this_reg->next_init_function;
 141     }
 142
 143   /*
 144    * pass 2: collect "a then b then c then d" constraints.
 145    * all init fcns must be known at this point.
 146    */
 147   this_reg = *head;
 148   while (this_reg)
 149     {
 150       these_constraints = this_reg->init_order;
 151
 152       prev_name = 0;
 153       /* Across the list of constraints */
 154       while (these_constraints && these_constraints[0])
 155         {
 156           this_constraint_c = these_constraints[0];
 157           p = hash_get_mem (index_by_name, this_constraint_c);
 158           if (p == 0)
 159             {
 160               clib_warning
 161                 ("order constraint fcn '%s' not found", this_constraint_c);
 162               these_constraints++;
 163               continue;
 164             }
 165
 166           if (prev_name == 0)
 167             {
 168               prev_name = this_constraint_c;
 169               these_constraints++;
 170               continue;
 171             }
 172
 173           constraint_tuple = format (0, "%s,%s%c", prev_name,
 174                                      this_constraint_c, 0);
 175           vec_add1 (constraints, constraint_tuple);
 176           prev_name = this_constraint_c;
 177           these_constraints++;
 178         }
 179       this_reg = this_reg->next_init_function;
 180     }
 181
 182   n_init_fns = vec_len (init_f_names);
 183   orig = clib_ptclosure_alloc (n_init_fns);
 184
 185   for (i = 0; i < vec_len (constraints); i++)
 186     {
 187       this_constraint = constraints[i];
 188
 189       if (comma_split (this_constraint, &a_name, &b_name))
 190         return clib_error_return (0, "comma_split failed!");
 191
 192       p = hash_get_mem (index_by_name, a_name);
 193       /*
 194        * Note: the next two errors mean that something is
 195        * b0rked. As in: if you code "A runs before on B," and you type
 196        * B incorrectly, you lose. Nonexistent init functions are tolerated.
 197        */
 198       if (p == 0)
 199         {
 200           clib_warning ("init function '%s' not found (before '%s')",
 201                         a_name, b_name);
 202           continue;
 203         }
 204       a_index = p[0];
 205
 206       p = hash_get_mem (index_by_name, b_name);
 207       if (p == 0)
 208         {
 209           clib_warning ("init function '%s' not found (after '%s')",
 210                         b_name, a_name);
 211           continue;
 212         }
 213       b_index = p[0];
 214
 215       /* add a before b to the original set of constraints */
 216       orig[a_index][b_index] = 1;
 217       vec_free (this_constraint);
 218     }
 219
 220   /* Compute the positive transitive closure of the original constraints */
 221   closure = clib_ptclosure (orig);
 222
 223   /* Compute a partial order across feature nodes, if one exists. */
 224 again:
 225   for (i = 0; i < n_init_fns; i++)
 226     {
 227       for (j = 0; j < n_init_fns; j++)
 228         {
 229           if (closure[i][j])
 230             goto item_constrained;
 231         }
 232       /* Item i can be output */
 233       vec_add1 (result, i);
 234       {
 235         for (k = 0; k < n_init_fns; k++)
 236           closure[k][i] = 0;
 237         /*
 238          * Add a "Magic" a before a constraint.
 239          * This means we'll never output it again
 240          */
 241         closure[i][i] = 1;
 242         goto again;
 243       }
 244     item_constrained:
 245       ;
 246     }
 247
 248   /* see if we got a partial order... */
 249   if (vec_len (result) != n_init_fns)
 250     return clib_error_return
 251       (0, "Failed to find a suitable init function order!");
 252
 253   /*
 254    * We win.
 255    * Bind the index variables, and output the feature node name vector
 256    * using the partial order we just computed. Result is in stack
 257    * order, because the entry with the fewest constraints (e.g. none)
 258    * is output first, etc.
 259    * Reset the listhead, and add items in result (aka reverse) order.
 260    */
 261   *head = 0;
 262   for (i = 0; i < n_init_fns; i++)
 263     {
 264       p = hash_get (reg_by_index, result[i]);
 265       ASSERT (p != 0);
 266       this_reg = (_vlib_init_function_list_elt_t *) p[0];
 267
 268       this_reg->next_init_function = *head;
 269       *head = this_reg;
 270     }
 271
 272   /* Finally, clean up all the fine data we allocated */
 273   /* *INDENT-OFF* */
 274   hash_foreach_pair (hp, index_by_name,
 275   ({
 276     vec_add1 (keys_to_delete, (u8 *)hp->key);
 277   }));
 278   /* *INDENT-ON* */
 279   hash_free (index_by_name);
 280   for (i = 0; i < vec_len (keys_to_delete); i++)
 281     vec_free (keys_to_delete[i]);
 282   vec_free (keys_to_delete);
 283   hash_free (reg_by_index);
 284   vec_free (result);
 285   clib_ptclosure_free (orig);
 286   clib_ptclosure_free (closure);
 287   return 0;
 288 }
 289
 290 /**
 291  * @brief call a set of init / exit / main-loop enter functions
 292  * @param vm vlib_main_t
 293  * @param head address of the listhead to sort and then invoke
 294  * @returns 0 on success, clib_error_t * on error
 295  *
 296  * The "init_functions_called" hash supports a subtle mix of procedural
 297  * and formally-specified ordering constraints. The following schemes
 298  * are *roughly* equivalent:
 299  *
 300  * static clib_error_t *init_runs_first (vlib_main_t *vm)
 301  * {
 302  *    clib_error_t *error;
 303  *
 304  *    ... do some stuff...
 305  *
 306  *    if ((error = vlib_call_init_function (init_runs_next)))
 307  *      return error;
 308  *    ...
 309  * }
 310  * VLIB_INIT_FUNCTION (init_runs_first);
 311  *
 312  * and
 313  *
 314  * static clib_error_t *init_runs_first (vlib_main_t *vm)
 315  * {
 316  *    ... do some stuff...
 317  * }
 318  * VLIB_INIT_FUNCTION (init_runs_first) =
 319  * {
 320  *     .runs_before = VLIB_INITS("init_runs_next"),
 321  * };
 322  *
 323  * The first form will [most likely] call "init_runs_next" on the
 324  * spot. The second form means that "init_runs_first" runs before
 325  * "init_runs_next," possibly much earlier in the sequence.
 326  *
 327  * Please DO NOT construct sets of init functions where A before B
 328  * actually means A *right before* B. It's not necessary - simply combine
 329  * A and B - and it leads to hugely annoying debugging exercises.
 330  */
 331
 332 static inline clib_error_t *
 333 call_init_exit_functions_internal (vlib_main_t * vm,
 334                                    _vlib_init_function_list_elt_t ** headp,
 335                                    int call_once, int do_sort)
 336 {
 337   clib_error_t *error = 0;
 338   _vlib_init_function_list_elt_t *i;
 339
 340   if (do_sort && (error = vlib_sort_init_exit_functions (headp)))
 341     return (error);
 342
 343   i = *headp;
 344   while (i)
 345     {
 346       if (call_once && !hash_get (vm->init_functions_called, i->f))
 347         {
 348           if (call_once)
 349             hash_set1 (vm->init_functions_called, i->f);
 350           error = i->f (vm);
 351           if (error)
 352             return error;
 353         }
 354       i = i->next_init_function;
 355     }
 356   return error;
 357 }
 358
 359 clib_error_t *
 360 vlib_call_init_exit_functions (vlib_main_t * vm,
 361                                _vlib_init_function_list_elt_t ** headp,
 362                                int call_once)
 363 {
 364   return call_init_exit_functions_internal (vm, headp, call_once,
 365                                             1 /* do_sort */ );
 366 }
 367
 368 clib_error_t *
 369 vlib_call_init_exit_functions_no_sort (vlib_main_t * vm,
 370                                        _vlib_init_function_list_elt_t **
 371                                        headp, int call_once)
 372 {
 373   return call_init_exit_functions_internal (vm, headp, call_once,
 374                                             0 /* do_sort */ );
 375 }
 376
 377 clib_error_t *
 378 vlib_call_all_init_functions (vlib_main_t * vm)
 379 {
 380   /* Call dummy functions to make sure purely static modules are
 381      linked in. */
 382 #define _(f) vlib_##f##_reference ();
 383   foreach_vlib_module_reference;
 384 #undef _
 385
 386   return vlib_call_init_exit_functions
 387     (vm, &vm->init_function_registrations, 1 /* call_once */ );
 388 }
 389
 390 clib_error_t *
 391 vlib_call_all_main_loop_enter_functions (vlib_main_t * vm)
 392 {
 393   return vlib_call_init_exit_functions
 394     (vm, &vm->main_loop_enter_function_registrations, 1 /* call_once */ );
 395 }
 396
 397 clib_error_t *
 398 vlib_call_all_main_loop_exit_functions (vlib_main_t * vm)
 399 {
 400   return vlib_call_init_exit_functions
 401     (vm, &vm->main_loop_exit_function_registrations, 1 /* call_once */ );
 402 }
 403
 404 clib_error_t *
 405 vlib_call_all_config_functions (vlib_main_t * vm,
 406                                 unformat_input_t * input, int is_early)
 407 {
 408   clib_error_t *error = 0;
 409   vlib_config_function_runtime_t *c, **all;
 410   uword *hash = 0, *p;
 411   uword i;
 412
 413   hash = hash_create_string (0, sizeof (uword));
 414   all = 0;
 415
 416   c = vm->config_function_registrations;
 417
 418   while (c)
 419     {
 420       hash_set_mem (hash, c->name, vec_len (all));
 421       vec_add1 (all, c);
 422       unformat_init (&c->input, 0, 0);
 423       c = c->next_registration;
 424     }
 425
 426   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
 427     {
 428       u8 *s, *v;
 429
 430       if (!unformat (input, "%s %v", &s, &v) || !(p = hash_get_mem (hash, s)))
 431         {
 432           error = clib_error_create ("unknown input `%s %v'", s, v);
 433           goto done;
 434         }
 435
 436       c = all[p[0]];
 437       if (vec_len (c->input.buffer) > 0)
 438         vec_add1 (c->input.buffer, ' ');
 439       vec_add (c->input.buffer, v, vec_len (v));
 440       vec_free (v);
 441       vec_free (s);
 442     }
 443
 444   for (i = 0; i < vec_len (all); i++)
 445     {
 446       c = all[i];
 447
 448       /* Is this an early config? Are we doing early configs? */
 449       if (is_early ^ c->is_early)
 450         continue;
 451
 452       /* Already called? */
 453       if (hash_get (vm->init_functions_called, c->function))
 454         continue;
 455       hash_set1 (vm->init_functions_called, c->function);
 456
 457       error = c->function (vm, &c->input);
 458       if (error)
 459         goto done;
 460     }
 461
 462 done:
 463   for (i = 0; i < vec_len (all); i++)
 464     {
 465       c = all[i];
 466       unformat_free (&c->input);
 467     }
 468   vec_free (all);
 469   hash_free (hash);
 470   return error;
 471 }
 472
 473 void
 474 vlib_init_dump (void)
 475 {
 476   vlib_main_t *vm = vlib_get_main ();
 477   int i = 0;
 478
 479   _vlib_init_function_list_elt_t *head, *this;
 480   head = vm->init_function_registrations;
 481
 482   this = head;
 483   while (this)
 484     {
 485       fformat (stdout, "[%d]: %s\n", i++, this->name);
 486       this = this->next_init_function;
 487     }
 488 }
 489
 490 static clib_error_t *
 491 show_init_function_command_fn (vlib_main_t * vm,
 492                                unformat_input_t * input,
 493                                vlib_cli_command_t * cmd)
 494 {
 495   int which = 1;
 496   int verbose = 0;
 497   int i, n_init_fns;
 498   _vlib_init_function_list_elt_t *head, *this;
 499   uword *index_by_name;
 500   uword *reg_by_index;
 501   u8 **init_f_names = 0;
 502   u8 *init_f_name;
 503   uword *p;
 504   _vlib_init_function_list_elt_t *this_reg = 0;
 505   hash_pair_t *hp;
 506   u8 **keys_to_delete = 0;
 507
 508   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
 509     {
 510       if (unformat (input, "init"))
 511         which = 1;
 512       else if (unformat (input, "enter"))
 513         which = 2;
 514       else if (unformat (input, "exit"))
 515         which = 3;
 516       else if (unformat (input, "verbose %d", &verbose))
 517         ;
 518       else if (unformat (input, "verbose"))
 519         verbose = 1;
 520       else
 521         break;
 522     }
 523
 524   switch (which)
 525     {
 526     case 1:
 527       head = vm->init_function_registrations;
 528       break;
 529     case 2:
 530       head = vm->main_loop_enter_function_registrations;
 531       break;
 532     case 3:
 533       head = vm->main_loop_exit_function_registrations;
 534       break;
 535     default:
 536       return clib_error_return (0, "BUG");
 537     }
 538
 539   if (verbose == 0)
 540     {
 541       this = head;
 542       i = 0;
 543       while (this)
 544         {
 545           vlib_cli_output (vm, "[%d]: %s", i++, this->name);
 546           this = this->next_init_function;
 547         }
 548       return 0;
 549     }
 550
 551   index_by_name = hash_create_string (0, sizeof (uword));
 552   reg_by_index = hash_create (0, sizeof (uword));
 553
 554   this_reg = head;
 555   n_init_fns = 0;
 556   /* collect init fcn names */
 557   while (this_reg)
 558     {
 559       init_f_name = format (0, "%s%c", this_reg->name, 0);
 560       hash_set (reg_by_index, vec_len (init_f_names), (uword) this_reg);
 561
 562       hash_set_mem (index_by_name, init_f_name, vec_len (init_f_names));
 563       vec_add1 (init_f_names, init_f_name);
 564       n_init_fns++;
 565       this_reg = this_reg->next_init_function;
 566     }
 567
 568   for (i = 0; i < n_init_fns; i++)
 569     {
 570       p = hash_get (reg_by_index, i);
 571       ASSERT (p != 0);
 572       this_reg = (_vlib_init_function_list_elt_t *) p[0];
 573       vlib_cli_output (vm, "[%d] %s", i, this_reg->name);
 574       {
 575         char **runs_before, **runs_after, **init_order;
 576         runs_before = this_reg->runs_before;
 577         while (runs_before && runs_before[0])
 578           {
 579             _vlib_init_function_list_elt_t *successor;
 580             uword successor_index;
 581             p = hash_get_mem (index_by_name, runs_before[0]);
 582             if (p == 0)
 583               {
 584                 clib_warning ("couldn't find successor '%s'", runs_before[0]);
 585                 runs_before++;
 586                 continue;
 587               }
 588             successor_index = p[0];
 589             p = hash_get (reg_by_index, p[0]);
 590             ASSERT (p != 0);
 591             successor = (_vlib_init_function_list_elt_t *) p[0];
 592             vlib_cli_output (vm, "  before '%s' [%lld]",
 593                              successor->name, successor_index);
 594             runs_before++;
 595           }
 596         runs_after = this_reg->runs_after;
 597         while (runs_after && runs_after[0])
 598           {
 599             _vlib_init_function_list_elt_t *predecessor;
 600             uword predecessor_index;
 601             p = hash_get_mem (index_by_name, runs_after[0]);
 602             if (p == 0)
 603               {
 604                 clib_warning ("couldn't find predecessor '%s'",
 605                               runs_after[0]);
 606                 runs_after++;
 607                 continue;
 608               }
 609             predecessor_index = p[0];
 610             p = hash_get (reg_by_index, p[0]);
 611             ASSERT (p != 0);
 612             predecessor = (_vlib_init_function_list_elt_t *) p[0];
 613             vlib_cli_output (vm, "  after '%s' [%lld]",
 614                              predecessor->name, predecessor_index);
 615             runs_after++;
 616           }
 617         init_order = this_reg->init_order;
 618         while (init_order && init_order[0])
 619           {
 620             _vlib_init_function_list_elt_t *inorder;
 621             uword inorder_index;
 622             p = hash_get_mem (index_by_name, init_order[0]);
 623             if (p == 0)
 624               {
 625                 clib_warning ("couldn't find order element'%s'",
 626                               init_order[0]);
 627                 init_order++;
 628                 continue;
 629               }
 630             inorder_index = p[0];
 631             p = hash_get (reg_by_index, p[0]);
 632             ASSERT (p != 0);
 633             inorder = (_vlib_init_function_list_elt_t *) p[0];
 634             vlib_cli_output (vm, "  in order '%s' [%lld]",
 635                              inorder->name, inorder_index);
 636             init_order++;
 637           }
 638       }
 639     }
 640   /* *INDENT-OFF* */
 641   hash_foreach_pair (hp, index_by_name,
 642   ({
 643     vec_add1 (keys_to_delete, (u8 *)hp->key);
 644   }));
 645   /* *INDENT-ON* */
 646   hash_free (index_by_name);
 647   for (i = 0; i < vec_len (keys_to_delete); i++)
 648     vec_free (keys_to_delete[i]);
 649   vec_free (keys_to_delete);
 650   hash_free (reg_by_index);
 651
 652   return 0;
 653 }
 654
 655 /*?
 656  * Show init function order
 657  *
 658  * @cliexpar
 659  * @cliexstart{show init-function [init | enter | exit] [verbose [nn]]}
 660  * @cliexend
 661  ?*/
 662 /* *INDENT-OFF* */
 663 VLIB_CLI_COMMAND (show_init_function, static) = {
 664   .path = "show init-function",
 665   .short_help = "show init-function [init | enter | exit][verbose [nn]]",
 666   .function = show_init_function_command_fn,
 667 };
 668 /* *INDENT-ON* */
 669
 670
 671 /*
 672  * fd.io coding-style-patch-verification: ON
 673  *
 674  * Local Variables:
 675  * eval: (c-set-style "gnu")
 676  * End:
 677  */