src/plugins/unittest/llist_test.c

   1 /*
   2  * Copyright (c) 2019 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 #include <vppinfra/llist.h>
  16 #include <vlib/vlib.h>
  17
  18 #define LLIST_TEST_I(_cond, _comment, _args...)                 \
  19 ({                                                              \
  20   int _evald = (_cond);                                         \
  21   if (!(_evald)) {                                              \
  22     fformat(stderr, "FAIL:%d: " _comment "\n",                  \
  23             __LINE__, ##_args);                                 \
  24   } else {                                                      \
  25     fformat(stderr, "PASS:%d: " _comment "\n",                  \
  26             __LINE__, ##_args);                                 \
  27   }                                                             \
  28   _evald;                                                       \
  29 })
  30
  31 #define LLIST_TEST(_cond, _comment, _args...)                   \
  32 {                                                               \
  33     if (!LLIST_TEST_I(_cond, _comment, ##_args)) {              \
  34         return 1;                                               \
  35     }                                                           \
  36 }
  37
  38 typedef struct list_elt
  39 {
  40   clib_llist_anchor_t ll_test;
  41   clib_llist_anchor_t ll_test2;
  42   u32 data;
  43 } list_elt_t;
  44
  45 #define list_elt_is_sane(pl,name,E,P,N)                                 \
  46  (E->name.next == (N) - pl                                              \
  47   && E->name.prev == (P) - pl                                           \
  48   && P->name.next == (E) - pl                                           \
  49   && N->name.prev == (E) - pl)
  50
  51 #define list_test_is_sane(pl,name,h)                                    \
  52 do {                                                                    \
  53   typeof (pl) e;                                                        \
  54   int rv;                                                               \
  55   clib_llist_foreach (pl, name, h, e, ({                                        \
  56     rv = list_elt_is_sane ((pl), name, (e),                             \
  57                            clib_llist_prev (pl,name,e),                 \
  58                            clib_llist_next (pl,name,e));                        \
  59     if (!rv)                                                            \
  60       LLIST_TEST (0, "invalid elt %u prev %u/%u next %u/%u", e - pl,    \
  61                   e->name.prev, clib_llist_prev (pl,name,e) - pl,               \
  62                   e->name.next, clib_llist_next (pl,name,e) - pl);              \
  63   }));                                                                  \
  64 } while (0)
  65
  66 static int
  67 llist_test_basic (vlib_main_t * vm, unformat_input_t * input)
  68 {
  69   list_elt_t *pelts = 0, *he, *he2, *he3, *e, *next, *nnext;
  70   int __clib_unused verbose, i, rv;
  71   clib_llist_index_t head, head2, head3;
  72   u32 old_tail;
  73
  74   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
  75     {
  76       if (unformat (input, "verbose"))
  77         verbose = 1;
  78       else
  79         {
  80           vlib_cli_output (vm, "parse error: '%U'", format_unformat_error,
  81                            input);
  82           return -1;
  83         }
  84     }
  85
  86   head = clib_llist_make_head (pelts, ll_test);
  87   he = clib_llist_elt (pelts, head);
  88
  89   LLIST_TEST (he->ll_test.next == head, "head next points to itself");
  90   LLIST_TEST (he->ll_test.prev == head, "head prev points to itself");
  91   LLIST_TEST (he == clib_llist_next (pelts, ll_test, he),
  92               "should be the same");
  93   LLIST_TEST (he == clib_llist_prev (pelts, ll_test, he),
  94               "should be the same");
  95
  96   /*
  97    * Add and remove one element
  98    */
  99   clib_llist_get (pelts, e);
 100   e->data = 1;
 101   he = clib_llist_elt (pelts, head);
 102   clib_llist_add (pelts, ll_test, e, he);
 103
 104   LLIST_TEST (e->ll_test.next == head, "next should be head");
 105   LLIST_TEST (e->ll_test.prev == head, "prev should be head");
 106   LLIST_TEST (he->ll_test.prev == e - pelts, "prev should be new");
 107   LLIST_TEST (he->ll_test.next == e - pelts, "prev should be new");
 108
 109   clib_llist_remove (pelts, ll_test, e);
 110   clib_llist_put (pelts, e);
 111   LLIST_TEST (he->ll_test.prev == head, "prev should be head");
 112   LLIST_TEST (he->ll_test.prev == head, "next should be head");
 113   LLIST_TEST (he == clib_llist_next (pelts, ll_test, he),
 114               "should be the same");
 115   LLIST_TEST (he == clib_llist_prev (pelts, ll_test, he),
 116               "should be the same");
 117
 118   /*
 119    * Add multiple head elements and test insertion
 120    */
 121   for (i = 0; i < 100; i++)
 122     {
 123       clib_llist_get (pelts, e);
 124       e->data = i;
 125       he = clib_llist_elt (pelts, head);
 126       clib_llist_add (pelts, ll_test, e, he);
 127     }
 128
 129   he = clib_llist_elt (pelts, head);
 130   LLIST_TEST (!clib_llist_is_empty (pelts, ll_test, he),
 131               "shoud not be empty");
 132   list_test_is_sane (pelts, ll_test, he);
 133
 134   i--;
 135   clib_llist_foreach (pelts, ll_test, he, e, ({
 136     if (i != e->data)
 137       LLIST_TEST (0, "incorrect element i = %u data = %u", i, e->data);
 138     i--;
 139   }));
 140
 141   LLIST_TEST (i == -1, "head insertion works i = %d", i);
 142
 143   /*
 144    * Remove elements from head
 145    */
 146   i = 99;
 147   e = clib_llist_next (pelts, ll_test, he);
 148   while (e != he)
 149     {
 150       next = clib_llist_next (pelts, ll_test, e);
 151       clib_llist_remove (pelts, ll_test, e);
 152       clib_llist_put (pelts, e);
 153       i--;
 154       e = next;
 155     }
 156
 157   he = clib_llist_elt (pelts, head);
 158   list_test_is_sane (pelts, ll_test, he);
 159   LLIST_TEST (clib_llist_is_empty (pelts, ll_test, he),
 160               "list should be empty");
 161   LLIST_TEST (clib_llist_elts (pelts) == 1, "pool should have only 1 element");
 162
 163   /*
 164    * Add tail elements to ll_test2 and test
 165    */
 166   head2 = clib_llist_make_head (pelts, ll_test2);
 167   for (i = 0; i < 100; i++)
 168     {
 169       clib_llist_get (pelts, e);
 170       e->data = i;
 171       he2 = clib_llist_elt (pelts, head2);
 172       clib_llist_add_tail (pelts, ll_test2, e, he2);
 173     }
 174
 175   he2 = clib_llist_elt (pelts, head2);
 176   list_test_is_sane (pelts, ll_test2, he2);
 177   LLIST_TEST (!clib_llist_is_empty (pelts, ll_test2, he2),
 178               "list should not be empty");
 179
 180   i--;
 181   clib_llist_foreach_reverse (pelts, ll_test2, he2, e, ({
 182     if (i != e->data)
 183         LLIST_TEST (0, "incorrect element i = %u data = %u", i, e->data);
 184     i--;
 185   }));
 186   LLIST_TEST (i == -1, "tail insertion works");
 187
 188   /*
 189    * Remove in from ll_test2 and add to ll_test
 190    */
 191   i = 0;
 192   he = clib_llist_elt (pelts, head);
 193   e = clib_llist_next (pelts, ll_test2, he2);
 194   while (e != he2)
 195     {
 196       next = clib_llist_next (pelts, ll_test2, e);
 197
 198       if (e->data != i)
 199         LLIST_TEST (0, "incorrect element i = %u data = %u", i, e->data);
 200
 201       clib_llist_remove (pelts, ll_test2, e);
 202       clib_llist_add_tail (pelts, ll_test, e, he);
 203       i++;
 204       e = next;
 205     }
 206
 207   he = clib_llist_elt (pelts, head);
 208   he2 = clib_llist_elt (pelts, head2);
 209   list_test_is_sane (pelts, ll_test, he);
 210   LLIST_TEST (!clib_llist_is_empty (pelts, ll_test, he),
 211               "shoud not be empty");
 212   LLIST_TEST (clib_llist_is_empty (pelts, ll_test2, he2), "shoud be empty");
 213
 214   i = 0;
 215
 216   clib_llist_foreach (pelts, ll_test, he, e, ({
 217     if (i != e->data)
 218         LLIST_TEST (0, "incorrect element i = %u data = %u", i, e->data);
 219     i++;
 220   }));
 221
 222   LLIST_TEST (i == 100, "move from ll_test2 to ll_test worked i %u", i);
 223
 224   /*
 225    * Delete and insert at random position
 226    */
 227   e = clib_llist_elt (pelts, head);
 228   for (i = 0; i < 10; i++)
 229     e = clib_llist_next (pelts, ll_test, e);
 230
 231   next = clib_llist_next (pelts, ll_test, e);
 232   nnext = clib_llist_next (pelts, ll_test, next);
 233
 234   LLIST_TEST (e->data == 9, "data should be 9 is %u", e->data);
 235   LLIST_TEST (next->data == 10, "data should be 10");
 236   LLIST_TEST (nnext->data == 11, "data should be 11");
 237
 238   clib_llist_remove (pelts, ll_test, next);
 239   clib_llist_put (pelts, next);
 240   memset (next, 0xfc, sizeof (*next));
 241
 242   next = clib_llist_next (pelts, ll_test, e);
 243   LLIST_TEST (next->data == 11, "data should be 11");
 244   LLIST_TEST (next == nnext, "should be nnext");
 245
 246   clib_llist_get (pelts, next);
 247   next->data = 10;
 248   clib_llist_insert (pelts, ll_test, next, e);
 249
 250   next = clib_llist_next (pelts, ll_test, e);
 251   LLIST_TEST (next->data == 10, "new next data should be 10");
 252   next = clib_llist_next (pelts, ll_test, next);
 253   LLIST_TEST (nnext == next, "next should be linked to old nnext");
 254
 255   he = clib_llist_elt (pelts, head);
 256   list_test_is_sane (pelts, ll_test, he);
 257
 258   /*
 259    * Make a new list that uses ll_test anchor
 260    */
 261
 262   head3 = clib_llist_make_head (pelts, ll_test);
 263   for (i = 0; i < 10; i++)
 264     {
 265       clib_llist_get (pelts, e);
 266       e->data = 300 + i;
 267       he3 = clib_llist_elt (pelts, head3);
 268       clib_llist_add (pelts, ll_test, e, he3);
 269     }
 270
 271   he = clib_llist_elt (pelts, head);
 272   he3 = clib_llist_elt (pelts, head3);
 273   list_test_is_sane (pelts, ll_test, he3);
 274   e = clib_llist_prev (pelts, ll_test, he);
 275   old_tail = e->data;
 276
 277   /*
 278    * Splice third list into the tail of the first
 279    */
 280   clib_llist_splice (pelts, ll_test, e, he3);
 281
 282   list_test_is_sane (pelts, ll_test, he);
 283   LLIST_TEST (clib_llist_is_empty (pelts, ll_test, he3), "should be empty");
 284
 285   e = clib_llist_prev (pelts, ll_test, he);
 286   LLIST_TEST (e->data == 300, "data for last spliced should be 300 is %u",
 287               e->data);
 288   for (i = 0; i < 10; i++)
 289     {
 290       if (e->data != 300 + i)
 291         LLIST_TEST (0, "incorrect element i = %u data = %u", i, e->data);
 292       e = clib_llist_prev (pelts, ll_test, e);
 293     }
 294
 295   LLIST_TEST (e->data == old_tail, "data should be old tail %u is %u",
 296               old_tail, e->data);
 297
 298   /*
 299    * Cleanup
 300    */
 301   clib_llist_free (pelts);
 302   return 0;
 303 }
 304
 305 static clib_error_t *
 306 llist_test (vlib_main_t * vm,
 307             unformat_input_t * input, vlib_cli_command_t * cmd_arg)
 308 {
 309   int res = 0;
 310
 311   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
 312     {
 313       if (unformat (input, "basic"))
 314         {
 315           res = llist_test_basic (vm, input);
 316         }
 317       else if (unformat (input, "all"))
 318         {
 319           if ((res = llist_test_basic (vm, input)))
 320             goto done;
 321         }
 322       else
 323         break;
 324     }
 325
 326 done:
 327   if (res)
 328     return clib_error_return (0, "llist unit test failed");
 329   return 0;
 330 }
 331
 332 VLIB_CLI_COMMAND (llist_test_command, static) =
 333 {
 334   .path = "test llist",
 335   .short_help = "internal llist unit tests",
 336   .function = llist_test,
 337 };
 338
 339 /*
 340  * fd.io coding-style-patch-verification: ON
 341  *
 342  * Local Variables:
 343  * eval: (c-set-style "gnu")
 344  * End:
 345  */