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