module/splat/splat-list.c

   1 /*
   2  *  This file is part of the SPL: Solaris Porting Layer.
   3  *
   4  *  Copyright (c) 2008 Lawrence Livermore National Security, LLC.
   5  *  Produced at Lawrence Livermore National Laboratory
   6  *  Written by:
   7  *          Brian Behlendorf <behlendorf1@llnl.gov>,
   8  *          Herb Wartens <wartens2@llnl.gov>,
   9  *          Jim Garlick <garlick@llnl.gov>
  10  *  UCRL-CODE-235197
  11  *
  12  *  This is free software; you can redistribute it and/or modify it
  13  *  under the terms of the GNU General Public License as published by
  14  *  the Free Software Foundation; either version 2 of the License, or
  15  *  (at your option) any later version.
  16  *
  17  *  This is distributed in the hope that it will be useful, but WITHOUT
  18  *  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  19  *  FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  20  *  for more details.
  21  *
  22  *  You should have received a copy of the GNU General Public License along
  23  *  with this program; if not, write to the Free Software Foundation, Inc.,
  24  *  51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA.
  25  */
  26
  27 #include "splat-internal.h"
  28
  29 #define SPLAT_SUBSYSTEM_LIST            0x0c00
  30 #define SPLAT_LIST_NAME                 "list"
  31 #define SPLAT_LIST_DESC                 "Kernel List Tests"
  32
  33 #define SPLAT_LIST_TEST1_ID             0x0c01
  34 #define SPLAT_LIST_TEST1_NAME           "create/destroy"
  35 #define SPLAT_LIST_TEST1_DESC           "Create/destroy Test"
  36
  37 #define SPLAT_LIST_TEST2_ID             0x0c02
  38 #define SPLAT_LIST_TEST2_NAME           "ins/rm head"
  39 #define SPLAT_LIST_TEST2_DESC           "Insert/remove head Test"
  40
  41 #define SPLAT_LIST_TEST3_ID             0x0c03
  42 #define SPLAT_LIST_TEST3_NAME           "ins/rm tail"
  43 #define SPLAT_LIST_TEST3_DESC           "Insert/remove tail Test"
  44
  45 #define SPLAT_LIST_TEST4_ID             0x0c04
  46 #define SPLAT_LIST_TEST4_NAME           "insert_after"
  47 #define SPLAT_LIST_TEST4_DESC           "Insert_after Test"
  48
  49 #define SPLAT_LIST_TEST5_ID             0x0c05
  50 #define SPLAT_LIST_TEST5_NAME           "insert_before"
  51 #define SPLAT_LIST_TEST5_DESC           "Insert_before Test"
  52
  53 #define SPLAT_LIST_TEST6_ID             0x0c06
  54 #define SPLAT_LIST_TEST6_NAME           "remove"
  55 #define SPLAT_LIST_TEST6_DESC           "Remove Test"
  56
  57 #define SPLAT_LIST_TEST7_ID             0x0c7
  58 #define SPLAT_LIST_TEST7_NAME           "active"
  59 #define SPLAT_LIST_TEST7_DESC           "Active Test"
  60
  61 /* It is important that li_node is not the first element, this
  62  * ensures the list_d2l/list_object macros are working correctly. */
  63 typedef struct list_item {
  64         int li_data;
  65         list_node_t li_node;
  66 } list_item_t;
  67
  68 #define LIST_ORDER_STACK                0
  69 #define LIST_ORDER_QUEUE                1
  70
  71 static int
  72 splat_list_test1(struct file *file, void *arg)
  73 {
  74         list_t list;
  75
  76         splat_vprint(file, SPLAT_LIST_TEST1_NAME, "Creating list\n%s", "");
  77         list_create(&list, sizeof(list_item_t), offsetof(list_item_t, li_node));
  78
  79         if (!list_is_empty(&list)) {
  80                 splat_vprint(file, SPLAT_LIST_TEST1_NAME,
  81                              "New list NOT empty%s\n", "");
  82                 /* list_destroy() intentionally skipped to avoid assert */
  83                 return -EEXIST;
  84         }
  85
  86         splat_vprint(file, SPLAT_LIST_TEST1_NAME, "Destroying list\n%s", "");
  87         list_destroy(&list);
  88
  89         /* Validate the list has been destroyed */
  90         if (list_link_active(&list.list_head)) {
  91                 splat_vprint(file, SPLAT_LIST_TEST1_NAME,
  92                              "Destroyed list still active%s", "");
  93                 return -EIO;
  94         }
  95
  96         return 0;
  97 }
  98
  99 static int
 100 splat_list_validate(list_t *list, int size, int order, int mult)
 101 {
 102         list_item_t *li;
 103         int i;
 104
 105         /* Walk all items in list from head to verify stack or queue
 106          * ordering.  We bound the for loop by size+1 to ensure that
 107          * we still terminate if there is list corruption.  We also
 108          * intentionally make things a little more complex than they
 109          * need to be by using list_head/list_next for queues, and
 110          * list_tail/list_prev for stacks.  This is simply done for
 111          * coverage and to ensure these function are working right.
 112          */
 113         for (i = 0, li = (order ? list_head(list) : list_tail(list));
 114              i < size + 1 && li != NULL;
 115              i++, li = (order ? list_next(list, li) : list_prev(list, li)))
 116                 if (li->li_data != i * mult)
 117                         return -EIDRM;
 118
 119         if (i != size)
 120                 return -E2BIG;
 121
 122         return 0;
 123 }
 124
 125 static int
 126 splat_list_test2(struct file *file, void *arg)
 127 {
 128         list_t list;
 129         list_item_t *li;
 130         int i, list_size = 8, rc = 0;
 131
 132         splat_vprint(file, SPLAT_LIST_TEST2_NAME, "Creating list\n%s", "");
 133         list_create(&list, sizeof(list_item_t), offsetof(list_item_t, li_node));
 134
 135         /* Insert all items at the list head to form a stack */
 136         splat_vprint(file, SPLAT_LIST_TEST2_NAME,
 137                      "Adding %d items to list head\n", list_size);
 138         for (i = 0; i < list_size; i++) {
 139                 li = kmem_alloc(sizeof(list_item_t), KM_SLEEP);
 140                 if (li == NULL) {
 141                         rc = -ENOMEM;
 142                         goto out;
 143                 }
 144
 145                 list_link_init(&li->li_node);
 146                 li->li_data = i;
 147                 list_insert_head(&list, li);
 148         }
 149
 150         splat_vprint(file, SPLAT_LIST_TEST2_NAME,
 151                      "Validating %d item list is a stack\n", list_size);
 152         rc = splat_list_validate(&list, list_size, LIST_ORDER_STACK, 1);
 153         if (rc)
 154                 splat_vprint(file, SPLAT_LIST_TEST2_NAME,
 155                              "List validation failed, %d\n", rc);
 156 out:
 157         /* Remove all items */
 158         splat_vprint(file, SPLAT_LIST_TEST2_NAME,
 159                      "Removing %d items from list head\n", list_size);
 160         while ((li = list_remove_head(&list)))
 161                 kmem_free(li, sizeof(list_item_t));
 162
 163         splat_vprint(file, SPLAT_LIST_TEST2_NAME, "Destroying list\n%s", "");
 164         list_destroy(&list);
 165
 166         return rc;
 167 }
 168
 169 static int
 170 splat_list_test3(struct file *file, void *arg)
 171 {
 172         list_t list;
 173         list_item_t *li;
 174         int i, list_size = 8, rc = 0;
 175
 176         splat_vprint(file, SPLAT_LIST_TEST3_NAME, "Creating list\n%s", "");
 177         list_create(&list, sizeof(list_item_t), offsetof(list_item_t, li_node));
 178
 179         /* Insert all items at the list tail to form a queue */
 180         splat_vprint(file, SPLAT_LIST_TEST3_NAME,
 181                      "Adding %d items to list tail\n", list_size);
 182         for (i = 0; i < list_size; i++) {
 183                 li = kmem_alloc(sizeof(list_item_t), KM_SLEEP);
 184                 if (li == NULL) {
 185                         rc = -ENOMEM;
 186                         goto out;
 187                 }
 188
 189                 list_link_init(&li->li_node);
 190                 li->li_data = i;
 191                 list_insert_tail(&list, li);
 192         }
 193
 194         splat_vprint(file, SPLAT_LIST_TEST3_NAME,
 195                      "Validating %d item list is a queue\n", list_size);
 196         rc = splat_list_validate(&list, list_size, LIST_ORDER_QUEUE, 1);
 197         if (rc)
 198                 splat_vprint(file, SPLAT_LIST_TEST3_NAME,
 199                              "List validation failed, %d\n", rc);
 200 out:
 201         /* Remove all items */
 202         splat_vprint(file, SPLAT_LIST_TEST3_NAME,
 203                      "Removing %d items from list tail\n", list_size);
 204         while ((li = list_remove_tail(&list)))
 205                 kmem_free(li, sizeof(list_item_t));
 206
 207         splat_vprint(file, SPLAT_LIST_TEST3_NAME, "Destroying list\n%s", "");
 208         list_destroy(&list);
 209
 210         return rc;
 211 }
 212
 213 static int
 214 splat_list_test4(struct file *file, void *arg)
 215 {
 216         list_t list;
 217         list_item_t *li_new, *li_last = NULL;
 218         int i, list_size = 8, rc = 0;
 219
 220         splat_vprint(file, SPLAT_LIST_TEST4_NAME, "Creating list\n%s", "");
 221         list_create(&list, sizeof(list_item_t), offsetof(list_item_t, li_node));
 222
 223         /* Insert all items after the last item to form a queue */
 224         splat_vprint(file, SPLAT_LIST_TEST4_NAME,
 225                      "Adding %d items each after the last item\n", list_size);
 226         for (i = 0; i < list_size; i++) {
 227                 li_new = kmem_alloc(sizeof(list_item_t), KM_SLEEP);
 228                 if (li_new == NULL) {
 229                         rc = -ENOMEM;
 230                         goto out;
 231                 }
 232
 233                 list_link_init(&li_new->li_node);
 234                 li_new->li_data = i;
 235                 list_insert_after(&list, li_last, li_new);
 236                 li_last = li_new;
 237         }
 238
 239         splat_vprint(file, SPLAT_LIST_TEST4_NAME,
 240                      "Validating %d item list is a queue\n", list_size);
 241         rc = splat_list_validate(&list, list_size, LIST_ORDER_QUEUE, 1);
 242         if (rc)
 243                 splat_vprint(file, SPLAT_LIST_TEST4_NAME,
 244                              "List validation failed, %d\n", rc);
 245 out:
 246         /* Remove all items */
 247         splat_vprint(file, SPLAT_LIST_TEST4_NAME,
 248                      "Removing %d items from list tail\n", list_size);
 249         while ((li_new = list_remove_head(&list)))
 250                 kmem_free(li_new, sizeof(list_item_t));
 251
 252         splat_vprint(file, SPLAT_LIST_TEST4_NAME, "Destroying list\n%s", "");
 253         list_destroy(&list);
 254
 255         return rc;
 256 }
 257
 258 static int
 259 splat_list_test5(struct file *file, void *arg)
 260 {
 261         list_t list;
 262         list_item_t *li_new, *li_last = NULL;
 263         int i, list_size = 8, rc = 0;
 264
 265         splat_vprint(file, SPLAT_LIST_TEST5_NAME, "Creating list\n%s", "");
 266         list_create(&list, sizeof(list_item_t), offsetof(list_item_t, li_node));
 267
 268         /* Insert all items before the last item to form a stack */
 269         splat_vprint(file, SPLAT_LIST_TEST5_NAME,
 270                      "Adding %d items each before the last item\n", list_size);
 271         for (i = 0; i < list_size; i++) {
 272                 li_new = kmem_alloc(sizeof(list_item_t), KM_SLEEP);
 273                 if (li_new == NULL) {
 274                         rc = -ENOMEM;
 275                         goto out;
 276                 }
 277
 278                 list_link_init(&li_new->li_node);
 279                 li_new->li_data = i;
 280                 list_insert_before(&list, li_last, li_new);
 281                 li_last = li_new;
 282         }
 283
 284         splat_vprint(file, SPLAT_LIST_TEST5_NAME,
 285                      "Validating %d item list is a queue\n", list_size);
 286         rc = splat_list_validate(&list, list_size, LIST_ORDER_STACK, 1);
 287         if (rc)
 288                 splat_vprint(file, SPLAT_LIST_TEST5_NAME,
 289                              "List validation failed, %d\n", rc);
 290 out:
 291         /* Remove all items */
 292         splat_vprint(file, SPLAT_LIST_TEST5_NAME,
 293                      "Removing %d items from list tail\n", list_size);
 294         while ((li_new = list_remove_tail(&list)))
 295                 kmem_free(li_new, sizeof(list_item_t));
 296
 297         splat_vprint(file, SPLAT_LIST_TEST5_NAME, "Destroying list\n%s", "");
 298         list_destroy(&list);
 299
 300         return rc;
 301 }
 302
 303 static int
 304 splat_list_test6(struct file *file, void *arg)
 305 {
 306         list_t list;
 307         list_item_t *li, *li_prev;
 308         int i, list_size = 8, rc = 0;
 309
 310         splat_vprint(file, SPLAT_LIST_TEST6_NAME, "Creating list\n%s", "");
 311         list_create(&list, sizeof(list_item_t), offsetof(list_item_t, li_node));
 312
 313         /* Insert all items at the list tail to form a queue */
 314         splat_vprint(file, SPLAT_LIST_TEST6_NAME,
 315                      "Adding %d items to list tail\n", list_size);
 316         for (i = 0; i < list_size; i++) {
 317                 li = kmem_alloc(sizeof(list_item_t), KM_SLEEP);
 318                 if (li == NULL) {
 319                         rc = -ENOMEM;
 320                         goto out;
 321                 }
 322
 323                 list_link_init(&li->li_node);
 324                 li->li_data = i;
 325                 list_insert_tail(&list, li);
 326         }
 327
 328         /* Remove all odd items from the queue */
 329         splat_vprint(file, SPLAT_LIST_TEST6_NAME,
 330                      "Removing %d odd items from the list\n", list_size / 2);
 331         for (li = list_head(&list); li != NULL; li = list_next(&list, li)) {
 332                 if (li->li_data % 2 == 1) {
 333                         li_prev = list_prev(&list, li);
 334                         list_remove(&list, li);
 335                         kmem_free(li, sizeof(list_item_t));
 336                         li = li_prev;
 337                 }
 338         }
 339
 340         splat_vprint(file, SPLAT_LIST_TEST6_NAME, "Validating %d item "
 341                      "list is a queue of only even elements\n", list_size / 2);
 342         rc = splat_list_validate(&list, list_size / 2, LIST_ORDER_QUEUE, 2);
 343         if (rc)
 344                 splat_vprint(file, SPLAT_LIST_TEST6_NAME,
 345                              "List validation failed, %d\n", rc);
 346 out:
 347         /* Remove all items */
 348         splat_vprint(file, SPLAT_LIST_TEST6_NAME,
 349                      "Removing %d items from list tail\n", list_size / 2);
 350         while ((li = list_remove_tail(&list)))
 351                 kmem_free(li, sizeof(list_item_t));
 352
 353         splat_vprint(file, SPLAT_LIST_TEST6_NAME, "Destroying list\n%s", "");
 354         list_destroy(&list);
 355
 356         return rc;
 357 }
 358
 359 static int
 360 splat_list_test7(struct file *file, void *arg)
 361 {
 362         list_t list;
 363         list_item_t *li;
 364         int rc = 0;
 365
 366         splat_vprint(file, SPLAT_LIST_TEST7_NAME, "Creating list\n%s", "");
 367         list_create(&list, sizeof(list_item_t), offsetof(list_item_t, li_node));
 368
 369         li = kmem_alloc(sizeof(list_item_t), KM_SLEEP);
 370         if (li == NULL) {
 371                 rc = -ENOMEM;
 372                 goto out;
 373         }
 374
 375         /* Validate newly initialized node is inactive */
 376         splat_vprint(file, SPLAT_LIST_TEST7_NAME, "Init list node\n%s", "");
 377         list_link_init(&li->li_node);
 378         if (list_link_active(&li->li_node)) {
 379                 splat_vprint(file, SPLAT_LIST_TEST7_NAME, "Newly initialized "
 380                             "list node should inactive %p/%p\n",
 381                             li->li_node.prev, li->li_node.next);
 382                 rc = -EINVAL;
 383                 goto out_li;
 384         }
 385
 386         /* Validate node is active when linked in to a list */
 387         splat_vprint(file, SPLAT_LIST_TEST7_NAME, "Insert list node\n%s", "");
 388         list_insert_head(&list, li);
 389         if (!list_link_active(&li->li_node)) {
 390                 splat_vprint(file, SPLAT_LIST_TEST7_NAME, "List node "
 391                             "inserted in list should be active %p/%p\n",
 392                             li->li_node.prev, li->li_node.next);
 393                 rc = -EINVAL;
 394                 goto out;
 395         }
 396
 397         /* Validate node is inactive when removed from list */
 398         splat_vprint(file, SPLAT_LIST_TEST7_NAME, "Remove list node\n%s", "");
 399         list_remove(&list, li);
 400         if (list_link_active(&li->li_node)) {
 401                 splat_vprint(file, SPLAT_LIST_TEST7_NAME, "List node "
 402                             "removed from list should be inactive %p/%p\n",
 403                             li->li_node.prev, li->li_node.next);
 404                 rc = -EINVAL;
 405         }
 406 out_li:
 407         kmem_free(li, sizeof(list_item_t));
 408 out:
 409         /* Remove all items */
 410         while ((li = list_remove_head(&list)))
 411                 kmem_free(li, sizeof(list_item_t));
 412
 413         splat_vprint(file, SPLAT_LIST_TEST7_NAME, "Destroying list\n%s", "");
 414         list_destroy(&list);
 415
 416         return rc;
 417 }
 418
 419 splat_subsystem_t *
 420 splat_list_init(void)
 421 {
 422         splat_subsystem_t *sub;
 423
 424         sub = kmalloc(sizeof(*sub), GFP_KERNEL);
 425         if (sub == NULL)
 426                 return NULL;
 427
 428         memset(sub, 0, sizeof(*sub));
 429         strncpy(sub->desc.name, SPLAT_LIST_NAME, SPLAT_NAME_SIZE);
 430         strncpy(sub->desc.desc, SPLAT_LIST_DESC, SPLAT_DESC_SIZE);
 431         INIT_LIST_HEAD(&sub->subsystem_list);
 432         INIT_LIST_HEAD(&sub->test_list);
 433         spin_lock_init(&sub->test_lock);
 434         sub->desc.id = SPLAT_SUBSYSTEM_LIST;
 435
 436         SPLAT_TEST_INIT(sub, SPLAT_LIST_TEST1_NAME, SPLAT_LIST_TEST1_DESC,
 437                         SPLAT_LIST_TEST1_ID, splat_list_test1);
 438         SPLAT_TEST_INIT(sub, SPLAT_LIST_TEST2_NAME, SPLAT_LIST_TEST2_DESC,
 439                         SPLAT_LIST_TEST2_ID, splat_list_test2);
 440         SPLAT_TEST_INIT(sub, SPLAT_LIST_TEST3_NAME, SPLAT_LIST_TEST3_DESC,
 441                         SPLAT_LIST_TEST3_ID, splat_list_test3);
 442         SPLAT_TEST_INIT(sub, SPLAT_LIST_TEST4_NAME, SPLAT_LIST_TEST4_DESC,
 443                         SPLAT_LIST_TEST4_ID, splat_list_test4);
 444         SPLAT_TEST_INIT(sub, SPLAT_LIST_TEST5_NAME, SPLAT_LIST_TEST5_DESC,
 445                         SPLAT_LIST_TEST5_ID, splat_list_test5);
 446         SPLAT_TEST_INIT(sub, SPLAT_LIST_TEST6_NAME, SPLAT_LIST_TEST6_DESC,
 447                         SPLAT_LIST_TEST6_ID, splat_list_test6);
 448         SPLAT_TEST_INIT(sub, SPLAT_LIST_TEST7_NAME, SPLAT_LIST_TEST7_DESC,
 449                         SPLAT_LIST_TEST7_ID, splat_list_test7);
 450
 451         return sub;
 452 }
 453
 454 void
 455 splat_list_fini(splat_subsystem_t *sub)
 456 {
 457         ASSERT(sub);
 458
 459         SPLAT_TEST_FINI(sub, SPLAT_LIST_TEST7_ID);
 460         SPLAT_TEST_FINI(sub, SPLAT_LIST_TEST6_ID);
 461         SPLAT_TEST_FINI(sub, SPLAT_LIST_TEST5_ID);
 462         SPLAT_TEST_FINI(sub, SPLAT_LIST_TEST4_ID);
 463         SPLAT_TEST_FINI(sub, SPLAT_LIST_TEST3_ID);
 464         SPLAT_TEST_FINI(sub, SPLAT_LIST_TEST2_ID);
 465         SPLAT_TEST_FINI(sub, SPLAT_LIST_TEST1_ID);
 466
 467         kfree(sub);
 468 }
 469
 470 int
 471 splat_list_id(void)
 472 {
 473         return SPLAT_SUBSYSTEM_LIST;
 474 }