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 = pool_elt_at_index (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   pool_get (pelts, e);
 100   e->data = 1;
 101   he = pool_elt_at_index (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   pool_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       pool_get (pelts, e);
 124       e->data = i;
 125       he = pool_elt_at_index (pelts, head);
 126       clib_llist_add (pelts, ll_test, e, he);
 127     }
 128
 129   he = pool_elt_at_index (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   /* *INDENT-OFF* */
 136   clib_llist_foreach (pelts, ll_test, he, e, ({
 137     if (i != e->data)
 138       LLIST_TEST (0, "incorrect element i = %u data = %u", i, e->data);
 139     i--;
 140   }));
 141   /* *INDENT-ON* */
 142
 143   LLIST_TEST (i == -1, "head insertion works i = %d", i);
 144
 145   /*
 146    * Remove elements from head
 147    */
 148   i = 99;
 149   e = clib_llist_next (pelts, ll_test, he);
 150   while (e != he)
 151     {
 152       next = clib_llist_next (pelts, ll_test, e);
 153       clib_llist_remove (pelts, ll_test, e);
 154       pool_put (pelts, e);
 155       i--;
 156       e = next;
 157     }
 158
 159   he = pool_elt_at_index (pelts, head);
 160   list_test_is_sane (pelts, ll_test, he);
 161   LLIST_TEST (clib_llist_is_empty (pelts, ll_test, he),
 162               "list should be empty");
 163   LLIST_TEST (pool_elts (pelts) == 1, "pool should have only 1 element");
 164
 165   /*
 166    * Add tail elements to ll_test2 and test
 167    */
 168   head2 = clib_llist_make_head (pelts, ll_test2);
 169   for (i = 0; i < 100; i++)
 170     {
 171       pool_get (pelts, e);
 172       e->data = i;
 173       he2 = pool_elt_at_index (pelts, head2);
 174       clib_llist_add_tail (pelts, ll_test2, e, he2);
 175     }
 176
 177   he2 = pool_elt_at_index (pelts, head2);
 178   list_test_is_sane (pelts, ll_test2, he2);
 179   LLIST_TEST (!clib_llist_is_empty (pelts, ll_test2, he2),
 180               "list should not be empty");
 181
 182   i--;
 183   /* *INDENT-OFF* */
 184   clib_llist_foreach_reverse (pelts, ll_test2, he2, e, ({
 185     if (i != e->data)
 186         LLIST_TEST (0, "incorrect element i = %u data = %u", i, e->data);
 187     i--;
 188   }));
 189   /* *INDENT-ON* */
 190   LLIST_TEST (i == -1, "tail insertion works");
 191
 192   /*
 193    * Remove in from ll_test2 and add to ll_test
 194    */
 195   i = 0;
 196   he = pool_elt_at_index (pelts, head);
 197   e = clib_llist_next (pelts, ll_test2, he2);
 198   while (e != he2)
 199     {
 200       next = clib_llist_next (pelts, ll_test2, e);
 201
 202       if (e->data != i)
 203         LLIST_TEST (0, "incorrect element i = %u data = %u", i, e->data);
 204
 205       clib_llist_remove (pelts, ll_test2, e);
 206       clib_llist_add_tail (pelts, ll_test, e, he);
 207       i++;
 208       e = next;
 209     }
 210
 211   he = pool_elt_at_index (pelts, head);
 212   he2 = pool_elt_at_index (pelts, head2);
 213   list_test_is_sane (pelts, ll_test, he);
 214   LLIST_TEST (!clib_llist_is_empty (pelts, ll_test, he),
 215               "shoud not be empty");
 216   LLIST_TEST (clib_llist_is_empty (pelts, ll_test2, he2), "shoud be empty");
 217
 218   i = 0;
 219
 220   /* *INDENT-OFF* */
 221   clib_llist_foreach (pelts, ll_test, he, e, ({
 222     if (i != e->data)
 223         LLIST_TEST (0, "incorrect element i = %u data = %u", i, e->data);
 224     i++;
 225   }));
 226   /* *INDENT-ON* */
 227
 228   LLIST_TEST (i == 100, "move from ll_test2 to ll_test worked i %u", i);
 229
 230   /*
 231    * Delete and insert at random position
 232    */
 233   e = pool_elt_at_index (pelts, head);
 234   for (i = 0; i < 10; i++)
 235     e = clib_llist_next (pelts, ll_test, e);
 236
 237   next = clib_llist_next (pelts, ll_test, e);
 238   nnext = clib_llist_next (pelts, ll_test, next);
 239
 240   LLIST_TEST (e->data == 9, "data should be 9 is %u", e->data);
 241   LLIST_TEST (next->data == 10, "data should be 10");
 242   LLIST_TEST (nnext->data == 11, "data should be 11");
 243
 244   clib_llist_remove (pelts, ll_test, next);
 245   pool_put (pelts, next);
 246   memset (next, 0xfc, sizeof (*next));
 247
 248   next = clib_llist_next (pelts, ll_test, e);
 249   LLIST_TEST (next->data == 11, "data should be 11");
 250   LLIST_TEST (next == nnext, "should be nnext");
 251
 252   pool_get (pelts, next);
 253   next->data = 10;
 254   clib_llist_insert (pelts, ll_test, next, e);
 255
 256   next = clib_llist_next (pelts, ll_test, e);
 257   LLIST_TEST (next->data == 10, "new next data should be 10");
 258   next = clib_llist_next (pelts, ll_test, next);
 259   LLIST_TEST (nnext == next, "next should be linked to old nnext");
 260
 261   he = pool_elt_at_index (pelts, head);
 262   list_test_is_sane (pelts, ll_test, he);
 263
 264   /*
 265    * Make a new list that uses ll_test anchor
 266    */
 267
 268   head3 = clib_llist_make_head (pelts, ll_test);
 269   for (i = 0; i < 10; i++)
 270     {
 271       pool_get (pelts, e);
 272       e->data = 300 + i;
 273       he3 = pool_elt_at_index (pelts, head3);
 274       clib_llist_add (pelts, ll_test, e, he3);
 275     }
 276
 277   he = pool_elt_at_index (pelts, head);
 278   he3 = pool_elt_at_index (pelts, head3);
 279   list_test_is_sane (pelts, ll_test, he3);
 280   e = clib_llist_prev (pelts, ll_test, he);
 281   old_tail = e->data;
 282
 283   /*
 284    * Splice third list into the tail of the first
 285    */
 286   clib_llist_splice (pelts, ll_test, e, he3);
 287
 288   list_test_is_sane (pelts, ll_test, he);
 289   LLIST_TEST (clib_llist_is_empty (pelts, ll_test, he3), "should be empty");
 290
 291   e = clib_llist_prev (pelts, ll_test, he);
 292   LLIST_TEST (e->data == 300, "data for last spliced should be 300 is %u",
 293               e->data);
 294   for (i = 0; i < 10; i++)
 295     {
 296       if (e->data != 300 + i)
 297         LLIST_TEST (0, "incorrect element i = %u data = %u", i, e->data);
 298       e = clib_llist_prev (pelts, ll_test, e);
 299     }
 300
 301   LLIST_TEST (e->data == old_tail, "data should be old tail %u is %u",
 302               old_tail, e->data);
 303
 304   /*
 305    * Cleanup
 306    */
 307   pool_free (pelts);
 308   return 0;
 309 }
 310
 311 static clib_error_t *
 312 llist_test (vlib_main_t * vm,
 313             unformat_input_t * input, vlib_cli_command_t * cmd_arg)
 314 {
 315   int res = 0;
 316
 317   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
 318     {
 319       if (unformat (input, "basic"))
 320         {
 321           res = llist_test_basic (vm, input);
 322         }
 323       else if (unformat (input, "all"))
 324         {
 325           if ((res = llist_test_basic (vm, input)))
 326             goto done;
 327         }
 328       else
 329         break;
 330     }
 331
 332 done:
 333   if (res)
 334     return clib_error_return (0, "llist unit test failed");
 335   return 0;
 336 }
 337
 338 /* *INDENT-OFF* */
 339 VLIB_CLI_COMMAND (llist_test_command, static) =
 340 {
 341   .path = "test llist",
 342   .short_help = "internal llist unit tests",
 343   .function = llist_test,
 344 };
 345 /* *INDENT-ON* */
 346
 347 /*
 348  * fd.io coding-style-patch-verification: ON
 349  *
 350  * Local Variables:
 351  * eval: (c-set-style "gnu")
 352  * End:
 353  */