module/splat/splat-list.c

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