vppinfra/vppinfra/test_vec.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   Copyright (c) 2001, 2002, 2003 Eliot Dresselhaus
  17   Written by Fred Delley <fdelley@cisco.com> .
  18
  19   Permission is hereby granted, free of charge, to any person obtaining
  20   a copy of this software and associated documentation files (the
  21   "Software"), to deal in the Software without restriction, including
  22   without limitation the rights to use, copy, modify, merge, publish,
  23   distribute, sublicense, and/or sell copies of the Software, and to
  24   permit persons to whom the Software is furnished to do so, subject to
  25   the following conditions:
  26
  27   The above copyright notice and this permission notice shall be
  28   included in all copies or substantial portions of the Software.
  29
  30   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  31   EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  32   MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  33   NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  34   LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  35   OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  36   WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  37 */
  38
  39 #ifdef CLIB_LINUX_KERNEL
  40 # include <linux/unistd.h>
  41 #endif
  42
  43 #ifdef CLIB_UNIX
  44 # include <unistd.h>
  45 # include <stdlib.h>
  46 # include <stdio.h>
  47 #endif
  48
  49 #include <vppinfra/clib.h>
  50 #include <vppinfra/mheap.h>
  51 #include <vppinfra/format.h>
  52 #include <vppinfra/error.h>
  53 #include <vppinfra/random.h>
  54 #include <vppinfra/time.h>
  55
  56 #include "test_vec.h"
  57
  58 static int verbose;
  59 #define if_verbose(format,args...) \
  60   if (verbose) { clib_warning(format, ## args); }
  61
  62 #define MAX_CHANGE 100
  63
  64
  65 typedef enum {
  66   /* Values have to be sequential and start with 0. */
  67   OP_IS_VEC_RESIZE = 0,
  68   OP_IS_VEC_ADD1,
  69   OP_IS_VEC_ADD2,
  70   OP_IS_VEC_ADD,
  71   OP_IS_VEC_INSERT,
  72   OP_IS_VEC_INSERT_ELTS,
  73   OP_IS_VEC_DELETE,
  74   OP_IS_VEC_DUP,
  75   OP_IS_VEC_IS_EQUAL,
  76   OP_IS_VEC_ZERO,
  77   OP_IS_VEC_SET,
  78   OP_IS_VEC_VALIDATE,
  79   OP_IS_VEC_FREE,
  80   OP_IS_VEC_INIT,
  81   OP_IS_VEC_CLONE,
  82   OP_IS_VEC_APPEND,
  83   OP_IS_VEC_PREPEND,
  84   /* Operations on vectors with custom headers. */
  85   OP_IS_VEC_INIT_H,
  86   OP_IS_VEC_RESIZE_H,
  87   OP_IS_VEC_FREE_H,
  88   OP_MAX,
  89 } op_t;
  90
  91 #define FIRST_VEC_OP            OP_IS_VEC_RESIZE
  92 #define LAST_VEC_OP             OP_IS_VEC_PREPEND
  93 #define FIRST_VEC_HDR_OP        OP_IS_VEC_INIT_H
  94 #define LAST_VEC_HDR_OP         OP_IS_VEC_FREE_H
  95
  96 uword g_prob_ratio[] = {
  97   [OP_IS_VEC_RESIZE]            = 5,
  98   [OP_IS_VEC_ADD1]              = 5,
  99   [OP_IS_VEC_ADD2]              = 5,
 100   [OP_IS_VEC_ADD]               = 5,
 101   [OP_IS_VEC_INSERT]            = 5,
 102   [OP_IS_VEC_INSERT_ELTS]       = 5,
 103   [OP_IS_VEC_DELETE]            = 30,
 104   [OP_IS_VEC_DUP]               = 5,
 105   [OP_IS_VEC_IS_EQUAL]          = 5,
 106   [OP_IS_VEC_ZERO]              = 2,
 107   [OP_IS_VEC_SET]               = 3,
 108   [OP_IS_VEC_VALIDATE]          = 5,
 109   [OP_IS_VEC_FREE]              = 5,
 110   [OP_IS_VEC_INIT]              = 5,
 111   [OP_IS_VEC_CLONE]             = 5,
 112   [OP_IS_VEC_APPEND]            = 5,
 113   [OP_IS_VEC_PREPEND]           = 5,
 114   /* Operations on vectors with custom headers. */
 115   [OP_IS_VEC_INIT_H]            = 5,
 116   [OP_IS_VEC_RESIZE_H]          = 5,
 117   [OP_IS_VEC_FREE_H]            = 5,
 118 };
 119
 120 op_t * g_prob;
 121 op_t * g_prob_wh;
 122
 123 uword g_call_stats[OP_MAX];
 124
 125
 126 /* A structure for both vector headers and vector elements might be useful to
 127    uncover potential alignement issues. */
 128
 129 typedef struct {
 130   u8 field1[4];
 131   CLIB_PACKED (u32 field2);
 132 } hdr_t;
 133
 134 typedef struct {
 135   u8 field1[3];
 136   CLIB_PACKED (u32 field2);
 137 } elt_t;
 138
 139
 140 #ifdef CLIB_UNIX
 141 u32 g_seed = 0xdeadbabe;
 142 uword g_verbose = 1;
 143 #endif
 144
 145 op_t * g_op_prob;
 146 uword g_set_verbose_at = ~0;
 147 uword g_dump_period = ~0;
 148
 149
 150 static u8 * format_vec_op_type (u8 * s, va_list * args)
 151 {
 152   op_t op = va_arg (*args, int);
 153
 154   switch (op)
 155     {
 156 #define _(n)                                    \
 157       case OP_IS_##n:                           \
 158         s = format (s, "OP_IS_" #n);            \
 159         break;
 160
 161       _(VEC_RESIZE); _(VEC_ADD1); _(VEC_ADD2); _(VEC_ADD); _(VEC_INSERT);
 162       _(VEC_INSERT_ELTS); _(VEC_DELETE); _(VEC_DUP); _(VEC_IS_EQUAL);
 163       _(VEC_ZERO); _(VEC_SET); _(VEC_VALIDATE); _(VEC_FREE); _(VEC_INIT);
 164       _(VEC_CLONE); _(VEC_APPEND); _(VEC_PREPEND); _(VEC_INIT_H); _(VEC_RESIZE_H);
 165       _(VEC_FREE_H);
 166
 167     default:
 168       s = format (s, "Unknown vec op (%d)", op);
 169       break;
 170     }
 171
 172 #undef _
 173
 174   return s;
 175 }
 176
 177 static void dump_call_stats (uword * stats)
 178 {
 179   uword i;
 180
 181   fformat (stdout, "Call Stats\n----------\n");
 182
 183   for (i = 0; i < OP_MAX; i++)
 184     fformat (stdout, "%-8d %U\n", stats[i], format_vec_op_type, i);
 185 }
 186
 187
 188 /* XXX - Purposely low value for debugging the validator. Will be set it to a
 189    more sensible value later. */
 190 #define MAX_VEC_LEN 10
 191
 192 #define create_random_vec_wh(elt_type, len, hdr_bytes, seed)                    \
 193 ({                                                                              \
 194   elt_type * _v(v) = NULL;                                                      \
 195   uword _v(l) = (len);                                                          \
 196   uword _v(h) = (hdr_bytes);                                                    \
 197   u8 * _v(hdr);                                                                 \
 198                                                                                 \
 199   if (_v(l) == 0)                                                               \
 200     goto __done__;                                                              \
 201                                                                                 \
 202   /* ~0 means select random length between 0 and MAX_VEC_LEN. */                \
 203   if (_v(l) == ~0)                                                              \
 204     _v(l) = bounded_random_u32 (&(seed), 0, MAX_VEC_LEN);                       \
 205                                                                                 \
 206   _v(v) = _vec_resize (NULL, _v(l), _v(l) * sizeof (elt_type), _v(h), 0);       \
 207   fill_with_random_data (_v(v), vec_bytes (_v(v)), (seed));                     \
 208                                                                                 \
 209   /* Fill header with random data as well. */                                   \
 210   if (_v(h) > 0)                                                                \
 211     {                                                                           \
 212       _v(hdr) = vec_header (_v(v), _v(h));                                      \
 213       fill_with_random_data (_v(hdr), _v(h), (seed));                           \
 214     }                                                                           \
 215                                                                                 \
 216 __done__:                                                                       \
 217   _v(v);                                                                        \
 218 })
 219
 220 #define create_random_vec(elt_type, len, seed) \
 221 create_random_vec_wh (elt_type, len, 0, seed)
 222
 223 #define compute_vec_hash(hash, vec)                     \
 224 ({                                                      \
 225   u8 * _v(v) = (u8 *) (vec);                            \
 226   uword _v(n) = vec_len (vec) * sizeof ((vec)[0]);      \
 227   u8 _v(hh) = (u8) (hash);                              \
 228                                                         \
 229   compute_mem_hash (_v(hh), _v(v), _v(n));              \
 230 })
 231
 232 static elt_t * validate_vec_free (elt_t * vec)
 233 {
 234   vec_free (vec);
 235   ASSERT (vec == NULL);
 236   return vec;
 237 }
 238
 239 static elt_t * validate_vec_free_h (elt_t * vec, uword hdr_bytes)
 240 {
 241   vec_free_h (vec, hdr_bytes);
 242   ASSERT (vec == NULL);
 243   return vec;
 244 }
 245
 246 static void validate_vec_hdr (elt_t * vec, uword hdr_bytes)
 247 {
 248   u8 * hdr;
 249   u8 * hdr_end;
 250   vec_header_t * vh;
 251
 252   if (! vec)
 253     return;
 254
 255   vh = _vec_find (vec);
 256   hdr = vec_header (vec, hdr_bytes);
 257   hdr_end = vec_header_end (hdr, hdr_bytes);
 258
 259   ASSERT (hdr_end == (u8 *) vec);
 260   ASSERT ((u8 *) vh - (u8 *) hdr >= hdr_bytes);
 261 }
 262
 263 static void validate_vec_len (elt_t * vec)
 264 {
 265   u8 * ptr;
 266   u8 * end;
 267   uword len;
 268   uword bytes;
 269   uword i;
 270   elt_t * elt;
 271
 272   if (! vec)
 273     return;
 274
 275   ptr = (u8 *) vec;
 276   end = (u8 *) vec_end (vec);
 277   len = vec_len (vec);
 278   bytes = sizeof (vec[0]) * len;
 279
 280   ASSERT (bytes == vec_bytes (vec));
 281   ASSERT ((ptr + bytes) == end);
 282
 283   i = 0;
 284
 285   /* XXX - TODO: confirm that auto-incrementing in vec_is_member() would not
 286      have the expected result. */
 287   while (vec_is_member (vec, (__typeof__(vec[0]) *) ptr))
 288     {
 289       ptr++;
 290       i++;
 291     }
 292
 293   ASSERT (ptr == end);
 294   ASSERT (i == bytes);
 295
 296   i = 0;
 297
 298   vec_foreach (elt, vec)
 299     i++;
 300
 301   ASSERT (i == len);
 302 }
 303
 304 static void validate_vec (elt_t * vec, uword hdr_bytes)
 305 {
 306   validate_vec_hdr (vec, hdr_bytes);
 307   validate_vec_len (vec);
 308
 309   if (! vec || vec_len (vec) == 0)
 310     {
 311       VERBOSE3 ("Vector at %p has zero elements.\n\n", vec);
 312     }
 313   else
 314     {
 315       if (hdr_bytes > 0)
 316         VERBOSE3 ("Header: %U\n",
 317                   format_hex_bytes, vec_header (vec, sizeof (vec[0])),
 318                   sizeof (vec[0]));
 319
 320       VERBOSE3 ("%U\n\n",
 321                 format_hex_bytes, vec, vec_len (vec) * sizeof (vec[0]));
 322     }
 323 }
 324
 325 static elt_t * validate_vec_resize (elt_t * vec, uword num_elts)
 326 {
 327   uword len1 = vec_len (vec);
 328   uword len2;
 329   u8 hash = compute_vec_hash (0, vec);
 330
 331   vec_resize (vec, num_elts);
 332   len2 = vec_len (vec);
 333
 334   ASSERT (len2 == len1 + num_elts);
 335   ASSERT (compute_vec_hash (hash, vec) == 0);
 336   validate_vec (vec, 0);
 337   return vec;
 338 }
 339
 340 static elt_t * validate_vec_resize_h (elt_t * vec,
 341                                      uword num_elts, uword hdr_bytes)
 342 {
 343   uword len1, len2;
 344   u8 * end1, * end2;
 345   u8 * hdr = NULL;
 346   u8 hash, hdr_hash;
 347
 348   len1 = vec_len (vec);
 349
 350   if (vec)
 351     hdr = vec_header (vec, hdr_bytes);
 352
 353   hash = compute_vec_hash (0, vec);
 354   hdr_hash = compute_mem_hash (0, hdr, hdr_bytes);
 355
 356   vec_resize_ha (vec, num_elts, hdr_bytes, 0);
 357   len2 = vec_len (vec);
 358
 359   ASSERT (len2 == len1 + num_elts);
 360
 361   end1 = (u8 *) (vec + len1);
 362   end2 = (u8 *) vec_end (vec);
 363
 364   while (end1 != end2)
 365     {
 366       ASSERT (*end1 == 0);
 367       end1++;
 368     }
 369
 370   if (vec)
 371     hdr = vec_header (vec, hdr_bytes);
 372
 373   ASSERT (compute_vec_hash (hash, vec) == 0);
 374   ASSERT (compute_mem_hash (hdr_hash, hdr, hdr_bytes) == 0);
 375   validate_vec (vec, 1);
 376   return vec;
 377 }
 378
 379 static elt_t * generic_validate_vec_add (elt_t * vec,
 380                                          uword num_elts, uword is_add2)
 381 {
 382   uword len1 = vec_len (vec);
 383   uword len2;
 384   u8 hash = compute_vec_hash (0, vec);
 385   elt_t * new;
 386
 387   if (is_add2)
 388     {
 389       vec_add2 (vec, new, num_elts);
 390     }
 391   else
 392     {
 393       new = create_random_vec (elt_t, num_elts, g_seed);
 394
 395       VERBOSE3 ("%U\n", format_hex_bytes, new, vec_len (new) * sizeof (new[0]));
 396
 397       /* Add the hash value of the new elements to that of the old vector. */
 398       hash = compute_vec_hash (hash, new);
 399
 400       if (num_elts == 1)
 401         vec_add1 (vec, new[0]);
 402       else if (num_elts > 1)
 403         vec_add (vec, new, num_elts);
 404
 405       vec_free (new);
 406     }
 407
 408   len2 = vec_len (vec);
 409   ASSERT (len2 == len1 + num_elts);
 410
 411   ASSERT (compute_vec_hash (hash, vec) == 0);
 412   validate_vec (vec, 0);
 413   return vec;
 414 }
 415
 416 static elt_t * validate_vec_add1 (elt_t * vec)
 417 {
 418   return generic_validate_vec_add (vec, 1, 0);
 419 }
 420
 421 static elt_t * validate_vec_add2 (elt_t * vec, uword num_elts)
 422 {
 423   return generic_validate_vec_add (vec, num_elts, 1);
 424 }
 425
 426 static elt_t * validate_vec_add (elt_t * vec, uword num_elts)
 427 {
 428   return generic_validate_vec_add (vec, num_elts, 0);
 429 }
 430
 431 static elt_t * validate_vec_insert (elt_t * vec,
 432                                     uword num_elts, uword start_elt)
 433 {
 434   uword len1 = vec_len (vec);
 435   uword len2;
 436   u8 hash;
 437
 438   /* vec_insert() would not handle it properly. */
 439   if (start_elt > len1 || num_elts == 0)
 440     return vec;
 441
 442   hash = compute_vec_hash (0, vec);
 443   vec_insert (vec, num_elts, start_elt);
 444   len2 = vec_len (vec);
 445
 446   ASSERT (len2 == len1 + num_elts);
 447   ASSERT (compute_vec_hash (hash, vec) == 0);
 448   validate_vec (vec, 0);
 449   return vec;
 450 }
 451
 452 static elt_t * validate_vec_insert_elts (elt_t * vec,
 453                                          uword num_elts, uword start_elt)
 454 {
 455   uword len1 = vec_len (vec);
 456   uword len2;
 457   elt_t * new;
 458   u8 hash;
 459
 460   /* vec_insert_elts() would not handle it properly. */
 461   if (start_elt > len1 || num_elts == 0)
 462     return vec;
 463
 464   new = create_random_vec (elt_t, num_elts, g_seed);
 465
 466   VERBOSE3 ("%U\n", format_hex_bytes, new, vec_len (new) * sizeof (new[0]));
 467
 468   /* Add the hash value of the new elements to that of the old vector. */
 469   hash = compute_vec_hash (0, vec);
 470   hash = compute_vec_hash (hash, new);
 471
 472   vec_insert_elts (vec, new, num_elts, start_elt);
 473   len2 = vec_len (vec);
 474
 475   vec_free (new);
 476
 477   ASSERT (len2 == len1 + num_elts);
 478   ASSERT (compute_vec_hash (hash, vec) == 0);
 479   validate_vec (vec, 0);
 480   return vec;
 481 }
 482
 483 static elt_t * validate_vec_delete (elt_t * vec,
 484                                     uword num_elts, uword start_elt)
 485 {
 486   uword len1 = vec_len (vec);
 487   uword len2;
 488   u8 * start;
 489   u8 hash;
 490   u8 hash_del;
 491
 492   /* vec_delete() would not handle it properly. */
 493   if (start_elt + num_elts > len1)
 494     return vec;
 495
 496   start = (u8 *) vec + (start_elt * sizeof (vec[0]));
 497
 498   hash = compute_vec_hash (0, vec);
 499   hash_del = compute_mem_hash (0, start, num_elts * sizeof (vec[0]));
 500   hash ^= hash_del;
 501
 502   vec_delete (vec, num_elts, start_elt);
 503   len2 = vec_len (vec);
 504
 505   ASSERT (len2 == len1 - num_elts);
 506   ASSERT (compute_vec_hash (hash, vec) == 0);
 507   validate_vec (vec, 0);
 508   return vec;
 509 }
 510
 511 static elt_t * validate_vec_dup (elt_t * vec)
 512 {
 513   elt_t * new;
 514   u8 hash;
 515
 516   hash = compute_vec_hash (0, vec);
 517   new = vec_dup (vec);
 518
 519   ASSERT (compute_vec_hash (hash, new) == 0);
 520
 521   validate_vec (new, 0);
 522   return new;
 523 }
 524
 525 static elt_t * validate_vec_zero (elt_t * vec)
 526 {
 527   u8 * ptr;
 528   u8 * end;
 529
 530   vec_zero (vec);
 531
 532   ptr = (u8 *) vec;
 533   end = (u8 *) (vec + vec_len (vec));
 534
 535   while (ptr != end)
 536     {
 537       ASSERT (ptr < (u8 *) vec_end (vec));
 538       ASSERT (ptr[0] == 0);
 539       ptr++;
 540     }
 541
 542   validate_vec (vec, 0);
 543   return vec;
 544 }
 545
 546 static void validate_vec_is_equal (elt_t * vec)
 547 {
 548   elt_t * new = NULL;
 549
 550   if (vec_len (vec) <= 0)
 551     return;
 552
 553   new = vec_dup (vec);
 554   ASSERT (vec_is_equal (new, vec));
 555   vec_free (new);
 556 }
 557
 558 static elt_t * validate_vec_set (elt_t * vec)
 559 {
 560   uword i;
 561   uword len = vec_len (vec);
 562   elt_t * new;
 563
 564   if (! vec)
 565     return NULL;
 566
 567   new = create_random_vec (elt_t, 1, g_seed);
 568
 569   VERBOSE3 ("%U\n", format_hex_bytes, new, vec_len (new) * sizeof (new[0]));
 570
 571   vec_set (vec, new[0]);
 572
 573   for (i = 0; i < len; i++)
 574     ASSERT (memcmp (&vec[i], &new[0], sizeof (vec[0])) == 0);
 575
 576   vec_free (new);
 577   validate_vec (vec, 0);
 578   return vec;
 579 }
 580
 581 static elt_t * validate_vec_validate (elt_t * vec, uword index)
 582 {
 583   uword len = vec_len (vec);
 584   word num_new = index - len + 1;
 585   u8 * ptr;
 586   u8 * end;
 587   u8 hash = compute_vec_hash (0, vec);
 588
 589   if (num_new < 0)
 590     num_new = 0;
 591
 592   vec_validate (vec, index);
 593
 594   /* Old len but new vec pointer! */
 595   ptr = (u8 *) (vec + len);
 596   end = (u8 *) (vec + len + num_new);
 597
 598   ASSERT (len + num_new == vec_len (vec));
 599   ASSERT (compute_vec_hash (hash, vec) == 0);
 600
 601   while (ptr != end)
 602     {
 603       ASSERT (ptr < (u8 *) vec_end (vec));
 604       ASSERT (ptr[0] == 0);
 605       ptr++;
 606     }
 607
 608   validate_vec (vec, 0);
 609   return vec;
 610 }
 611
 612 static elt_t * validate_vec_init (uword num_elts)
 613 {
 614   u8 * ptr;
 615   u8 * end;
 616   uword len;
 617   elt_t * new;
 618
 619   new = vec_new (elt_t, num_elts);
 620   len = vec_len (new);
 621
 622   ASSERT (len == num_elts);
 623
 624   ptr = (u8 *) new;
 625   end = (u8 *) (new + len);
 626
 627   while (ptr != end)
 628     {
 629       ASSERT (ptr < (u8 *) vec_end (new));
 630       ASSERT (ptr[0] == 0);
 631       ptr++;
 632     }
 633
 634   validate_vec (new, 0);
 635   return new;
 636 }
 637
 638 static elt_t * validate_vec_init_h (uword num_elts, uword hdr_bytes)
 639 {
 640   uword i = 0;
 641   u8 * ptr;
 642   u8 * end;
 643   uword len;
 644   elt_t * new;
 645
 646   new = vec_new_ha (elt_t, num_elts, hdr_bytes, 0);
 647   len = vec_len (new);
 648
 649   ASSERT (len == num_elts);
 650
 651   /* We have 2 zero-regions to check: header & vec data (skip _VEC struct). */
 652   for (i = 0; i < 2; i++)
 653     {
 654       if (i == 0)
 655         {
 656           ptr = (u8 *) vec_header (new, hdr_bytes);
 657           end = ptr + hdr_bytes;
 658         }
 659       else
 660         {
 661           ptr = (u8 *) new;
 662           end = (u8 *) (new + len);
 663         }
 664
 665       while (ptr != end)
 666         {
 667           ASSERT (ptr < (u8 *) vec_end (new));
 668           ASSERT (ptr[0] == 0);
 669           ptr++;
 670         }
 671     }
 672
 673   validate_vec (new, 1);
 674   return new;
 675 }
 676
 677 /* XXX - I don't understand the purpose of the vec_clone() call. */
 678 static elt_t * validate_vec_clone (elt_t * vec)
 679 {
 680   elt_t * new;
 681
 682   vec_clone (new, vec);
 683
 684   ASSERT (vec_len (new) == vec_len (vec));
 685   ASSERT (compute_vec_hash (0, new) == 0);
 686   validate_vec (new, 0);
 687   return new;
 688 }
 689
 690 static elt_t * validate_vec_append (elt_t * vec)
 691 {
 692   elt_t * new;
 693   uword num_elts = bounded_random_u32 (&g_seed, 0, MAX_CHANGE);
 694   uword len;
 695   u8 hash = 0;
 696
 697   new = create_random_vec (elt_t, num_elts, g_seed);
 698
 699   len = vec_len (vec) + vec_len (new);
 700   hash = compute_vec_hash (0, vec);
 701   hash = compute_vec_hash (hash, new);
 702
 703   vec_append (vec, new);
 704   vec_free (new);
 705
 706   ASSERT (vec_len (vec) == len);
 707   ASSERT (compute_vec_hash (hash, vec) == 0);
 708   validate_vec (vec, 0);
 709   return vec;
 710 }
 711
 712 static elt_t * validate_vec_prepend (elt_t * vec)
 713 {
 714   elt_t * new;
 715   uword num_elts = bounded_random_u32 (&g_seed, 0, MAX_CHANGE);
 716   uword len;
 717   u8 hash = 0;
 718
 719   new = create_random_vec (elt_t, num_elts, g_seed);
 720
 721   len = vec_len (vec) + vec_len (new);
 722   hash = compute_vec_hash (0, vec);
 723   hash = compute_vec_hash (hash, new);
 724
 725   vec_prepend (vec, new);
 726   vec_free (new);
 727
 728   ASSERT (vec_len (vec) == len);
 729   ASSERT (compute_vec_hash (hash, vec) == 0);
 730   validate_vec (vec, 0);
 731   return vec;
 732 }
 733
 734 static void run_validator_wh (uword iter)
 735 {
 736   elt_t * vec;
 737   uword i;
 738   uword op;
 739   uword num_elts;
 740   uword len;
 741   uword dump_time;
 742   f64 time[3]; /* [0]: start, [1]: last, [2]: current */
 743
 744   vec = create_random_vec_wh (elt_t, ~0, sizeof (hdr_t), g_seed);
 745   validate_vec (vec, 0);
 746   VERBOSE2 ("Start with len %d\n", vec_len (vec));
 747
 748   time[0] = unix_time_now ();
 749   time[1] = time[0];
 750   dump_time = g_dump_period;
 751
 752   for (i = 1; i <= iter; i++)
 753     {
 754       if (i >= g_set_verbose_at)
 755         g_verbose = 2;
 756
 757       op = bounded_random_u32 (&g_seed, 0, vec_len (g_prob_wh) - 1);
 758       op = g_prob_wh[op];
 759
 760       switch (op)
 761         {
 762         case OP_IS_VEC_INIT_H:
 763           num_elts = bounded_random_u32 (&g_seed, 0, MAX_CHANGE);
 764           vec_free_h (vec, sizeof (hdr_t));
 765           VERBOSE2 ("vec_init_h(), new elts %d\n", num_elts);
 766           vec = validate_vec_init_h (num_elts, sizeof (hdr_t));
 767           break;
 768
 769         case OP_IS_VEC_RESIZE_H:
 770           len = vec_len (vec);
 771           num_elts = bounded_random_u32 (&g_seed, len, len + MAX_CHANGE);
 772           VERBOSE2 ("vec_resize_h(), %d new elts.\n", num_elts);
 773           vec = validate_vec_resize_h (vec, num_elts, sizeof (hdr_t));
 774           break;
 775
 776         case OP_IS_VEC_FREE_H:
 777           VERBOSE2 ("vec_free_h()\n");
 778           vec = validate_vec_free_h (vec, sizeof (hdr_t));
 779           break;
 780
 781         default:
 782           ASSERT (0);
 783           break;
 784         }
 785
 786       g_call_stats[op]++;
 787
 788       if (i == dump_time)
 789         {
 790           time[2] = unix_time_now ();
 791           VERBOSE1 ("%d vec ops in %f secs. (last %d in %f secs.).\n",
 792                     i, time[2] - time[0], g_dump_period, time[2] - time[1]);
 793           time[1] = time[2];
 794           dump_time += g_dump_period;
 795
 796           VERBOSE1 ("vec len %d\n", vec_len (vec));
 797           VERBOSE2 ("%U\n\n",
 798                     format_hex_bytes, vec, vec_len (vec) * sizeof (vec[0]));
 799         }
 800
 801       VERBOSE2 ("len %d\n", vec_len (vec));
 802     }
 803
 804   validate_vec (vec, sizeof (hdr_t));
 805   vec_free_h (vec, sizeof (hdr_t));
 806 }
 807
 808 static void run_validator (uword iter)
 809 {
 810   elt_t * vec;
 811   elt_t * new;
 812   uword i;
 813   uword op;
 814   uword num_elts;
 815   uword index;
 816   uword len;
 817   uword dump_time;
 818   f64 time[3]; /* [0]: start, [1]: last, [2]: current */
 819
 820   vec = create_random_vec (elt_t, ~0, g_seed);
 821   validate_vec (vec, 0);
 822   VERBOSE2 ("Start with len %d\n", vec_len (vec));
 823
 824   time[0] = unix_time_now ();
 825   time[1] = time[0];
 826   dump_time = g_dump_period;
 827
 828   for (i = 1; i <= iter; i++)
 829     {
 830       if (i >= g_set_verbose_at)
 831         g_verbose = 2;
 832
 833       op = bounded_random_u32 (&g_seed, 0, vec_len (g_prob) - 1);
 834       op = g_prob[op];
 835
 836       switch (op)
 837         {
 838         case OP_IS_VEC_RESIZE:
 839           len = vec_len (vec);
 840           num_elts = bounded_random_u32 (&g_seed, len, len + MAX_CHANGE);
 841           VERBOSE2 ("vec_resize(), %d new elts.\n", num_elts);
 842           vec = validate_vec_resize (vec, num_elts);
 843           break;
 844
 845         case OP_IS_VEC_ADD1:
 846           VERBOSE2 ("vec_add1()\n");
 847           vec = validate_vec_add1 (vec);
 848           break;
 849
 850         case OP_IS_VEC_ADD2:
 851           num_elts = bounded_random_u32 (&g_seed, 0, MAX_CHANGE);
 852           VERBOSE2 ("vec_add2(), %d new elts.\n", num_elts);
 853           vec = validate_vec_add2 (vec, num_elts);
 854           break;
 855
 856         case OP_IS_VEC_ADD:
 857           num_elts = bounded_random_u32 (&g_seed, 0, MAX_CHANGE);
 858           VERBOSE2 ("vec_add(), %d new elts.\n", num_elts);
 859           vec = validate_vec_add (vec, num_elts);
 860           break;
 861
 862         case OP_IS_VEC_INSERT:
 863           len = vec_len (vec);
 864           num_elts = bounded_random_u32 (&g_seed, 0, MAX_CHANGE);
 865           index = bounded_random_u32 (&g_seed, 0,
 866                                       (len > 0) ? (len - 1) : (0));
 867           VERBOSE2 ("vec_insert(), %d new elts, index %d.\n", num_elts, index);
 868           vec = validate_vec_insert (vec, num_elts, index);
 869           break;
 870
 871         case OP_IS_VEC_INSERT_ELTS:
 872           len = vec_len (vec);
 873           num_elts = bounded_random_u32 (&g_seed, 0, MAX_CHANGE);
 874           index = bounded_random_u32 (&g_seed, 0,
 875                                       (len > 0) ? (len - 1) : (0));
 876           VERBOSE2 ("vec_insert_elts(), %d new elts, index %d.\n",
 877                     num_elts, index);
 878           vec = validate_vec_insert_elts (vec, num_elts, index);
 879           break;
 880
 881         case OP_IS_VEC_DELETE:
 882           len = vec_len (vec);
 883           index = bounded_random_u32 (&g_seed, 0, len - 1);
 884           num_elts = bounded_random_u32 (&g_seed, 0,
 885                                          (len > index) ? (len - index) : (0));
 886           VERBOSE2 ("vec_delete(), %d elts, index %d.\n", num_elts, index);
 887           vec = validate_vec_delete (vec, num_elts, index);
 888           break;
 889
 890         case OP_IS_VEC_DUP:
 891           VERBOSE2 ("vec_dup()\n");
 892           new = validate_vec_dup (vec);
 893           vec_free (new);
 894           break;
 895
 896         case OP_IS_VEC_IS_EQUAL:
 897           VERBOSE2 ("vec_is_equal()\n");
 898           validate_vec_is_equal (vec);
 899           break;
 900
 901         case OP_IS_VEC_ZERO:
 902           VERBOSE2 ("vec_zero()\n");
 903           vec = validate_vec_zero (vec);
 904           break;
 905
 906         case OP_IS_VEC_SET:
 907           VERBOSE2 ("vec_set()\n");
 908           vec = validate_vec_set (vec);
 909           break;
 910
 911         case OP_IS_VEC_VALIDATE:
 912           len = vec_len (vec);
 913           index = bounded_random_u32 (&g_seed, 0, len - 1 + MAX_CHANGE);
 914           VERBOSE2 ("vec_validate(), index %d\n", index);
 915           vec = validate_vec_validate (vec, index);
 916           break;
 917
 918         case OP_IS_VEC_FREE:
 919           VERBOSE2 ("vec_free()\n");
 920           vec = validate_vec_free (vec);
 921           break;
 922
 923         case OP_IS_VEC_INIT:
 924           num_elts = bounded_random_u32 (&g_seed, 0, MAX_CHANGE);
 925           vec_free (vec);
 926           VERBOSE2 ("vec_init(), new elts %d\n", num_elts);
 927           vec = validate_vec_init (num_elts);
 928           break;
 929
 930         case OP_IS_VEC_CLONE:
 931           VERBOSE2 ("vec_clone()\n");
 932           new = validate_vec_clone (vec);
 933           vec_free (new);
 934           break;
 935
 936         case OP_IS_VEC_APPEND:
 937           VERBOSE2 ("vec_append()\n");
 938           vec = validate_vec_append (vec);
 939           break;
 940
 941         case OP_IS_VEC_PREPEND:
 942           VERBOSE2 ("vec_prepend()\n");
 943           vec = validate_vec_prepend (vec);
 944           break;
 945
 946         default:
 947           ASSERT (0);
 948           break;
 949         }
 950
 951       g_call_stats[op]++;
 952
 953       if (i == dump_time)
 954         {
 955           time[2] = unix_time_now ();
 956           VERBOSE1 ("%d vec ops in %f secs. (last %d in %f secs.).\n",
 957                     i, time[2] - time[0], g_dump_period, time[2] - time[1]);
 958           time[1] = time[2];
 959           dump_time += g_dump_period;
 960
 961           VERBOSE1 ("vec len %d\n", vec_len (vec));
 962           VERBOSE2 ("%U\n\n",
 963                     format_hex_bytes, vec, vec_len (vec) * sizeof (vec[0]));
 964         }
 965
 966       VERBOSE2 ("len %d\n", vec_len (vec));
 967     }
 968
 969   validate_vec (vec, 0);
 970   vec_free (vec);
 971 }
 972
 973 static void prob_init (void)
 974 {
 975   uword i, j, ratio, len, index;
 976
 977   /* Create the vector to implement the statistical profile:
 978    vec [ op1 op1 op1 op2 op3 op3 op3 op4 op4 .... ] */
 979   for (i = FIRST_VEC_OP; i <= LAST_VEC_OP; i++)
 980     {
 981       ratio = g_prob_ratio[i];
 982       if (ratio <= 0)
 983         continue;
 984
 985       len = vec_len (g_prob);
 986       index = len - 1 + ratio;
 987       ASSERT (index >= 0);
 988
 989       /* Pre-allocate new elements. */
 990       vec_validate (g_prob, index);
 991
 992       for (j = len; j <= index; j++)
 993         g_prob[j] = i;
 994     }
 995
 996   /* Operations on vectors with headers. */
 997   for (i = FIRST_VEC_HDR_OP; i <= LAST_VEC_HDR_OP; i++)
 998     {
 999       ratio = g_prob_ratio[i];
1000       if (ratio <= 0)
1001         continue;
1002
1003       len = vec_len (g_prob_wh);
1004       index = len - 1 + ratio;
1005       ASSERT (index >= 0);
1006
1007       /* Pre-allocate new elements. */
1008       vec_validate (g_prob_wh, index);
1009
1010       for (j = len; j <= index; j++)
1011         g_prob_wh[j] = i;
1012     }
1013
1014   VERBOSE3 ("prob_vec, len %d\n%U\n", vec_len (g_prob),
1015              format_hex_bytes, g_prob, vec_len (g_prob) * sizeof (g_prob[0]));
1016   VERBOSE3 ("prob_vec_wh, len %d\n%U\n", vec_len (g_prob_wh),
1017              format_hex_bytes, g_prob_wh,
1018             vec_len (g_prob_wh) * sizeof (g_prob_wh[0]));
1019 }
1020
1021 static void prob_free (void)
1022 {
1023   vec_free (g_prob);
1024   vec_free (g_prob_wh);
1025 }
1026
1027 int test_vec_main (unformat_input_t * input)
1028 {
1029   uword iter = 1000;
1030   uword help = 0;
1031   uword big = 0;
1032
1033   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
1034     {
1035       if (0 == unformat (input, "iter %d", &iter)
1036           && 0 == unformat (input, "seed %d", &g_seed)
1037           && 0 == unformat (input, "verbose %d", &g_verbose)
1038           && 0 == unformat (input, "set %d", &g_set_verbose_at)
1039           && 0 == unformat (input, "dump %d", &g_dump_period)
1040           && 0 == unformat (input, "help %=", &help, 1)
1041           && 0 == unformat (input, "big %=", &big, 1))
1042         {
1043           clib_error ("unknown input `%U'", format_unformat_error, input);
1044           goto usage;
1045         }
1046     }
1047
1048   if (big)
1049     {
1050       u8 * bigboy = 0;
1051       u64 one_gig = (1<<30);
1052       u64 size;
1053       u64 index;
1054
1055       fformat (stdout, "giant vector test...");
1056       size = 5ULL * one_gig;
1057
1058       vec_validate (bigboy, size);
1059
1060       for (index = size; index >= 0; index--)
1061         bigboy[index] = index & 0xff;
1062       return 0;
1063     }
1064
1065
1066   if (help)
1067     goto usage;
1068
1069   prob_init ();
1070   run_validator (iter);
1071   run_validator_wh (iter);
1072   if (verbose) dump_call_stats (g_call_stats);
1073   prob_free ();
1074
1075   if (verbose) { memory_snap (); }
1076   return 0;
1077
1078  usage:
1079   fformat (stdout, "Usage: test_vec iter <N> seed <N> verbose <N> "
1080            "set <N> dump <N>\n");
1081   if (help)
1082     return 0;
1083
1084   return -1;
1085 }
1086
1087 #ifdef CLIB_UNIX
1088 int main (int argc, char * argv[])
1089 {
1090   unformat_input_t i;
1091   int ret;
1092
1093   mheap_alloc (0, (uword)10ULL<<30);
1094
1095   verbose = (argc > 1);
1096   unformat_init_command_line (&i, argv);
1097   ret = test_vec_main (&i);
1098   unformat_free (&i);
1099
1100   return ret;
1101 }
1102 #endif /* CLIB_UNIX */