LXR linux/lib/test

   1// SPDX-License-Identifier: GPL-2.0+
   2/*
   3 * test_ida.c: Test the IDA API
   4 * Copyright (c) 2016-2018 Microsoft Corporation
   5 * Copyright (c) 2018 Oracle Corporation
   6 * Author: Matthew Wilcox <willy@infradead.org>
   7 */
   8
   9#include <linux/idr.h>
  10#include <linux/module.h>
  11
  12static unsigned int tests_run;
  13static unsigned int tests_passed;
  14
  15#ifdef __KERNEL__
  16void ida_dump(struct ida *ida) { }
  17#endif
  18#define IDA_BUG_ON(ida, x) do {                                         \
  19        tests_run++;                                                    \
  20        if (x) {                                                        \
  21                ida_dump(ida);                                          \
  22                dump_stack();                                           \
  23        } else {                                                        \
  24                tests_passed++;                                         \
  25        }                                                               \
  26} while (0)
  27
  28/*
  29 * Straightforward checks that allocating and freeing IDs work.
  30 */
  31static void ida_check_alloc(struct ida *ida)
  32{
  33        int i, id;
  34
  35        for (i = 0; i < 10000; i++)
  36                IDA_BUG_ON(ida, ida_alloc(ida, GFP_KERNEL) != i);
  37
  38        ida_free(ida, 20);
  39        ida_free(ida, 21);
  40        for (i = 0; i < 3; i++) {
  41                id = ida_alloc(ida, GFP_KERNEL);
  42                IDA_BUG_ON(ida, id < 0);
  43                if (i == 2)
  44                        IDA_BUG_ON(ida, id != 10000);
  45        }
  46
  47        for (i = 0; i < 5000; i++)
  48                ida_free(ida, i);
  49
  50        IDA_BUG_ON(ida, ida_alloc_min(ida, 5000, GFP_KERNEL) != 10001);
  51        ida_destroy(ida);
  52
  53        IDA_BUG_ON(ida, !ida_is_empty(ida));
  54}
  55
  56/* Destroy an IDA with a single entry at @base */
  57static void ida_check_destroy_1(struct ida *ida, unsigned int base)
  58{
  59        IDA_BUG_ON(ida, ida_alloc_min(ida, base, GFP_KERNEL) != base);
  60        IDA_BUG_ON(ida, ida_is_empty(ida));
  61        ida_destroy(ida);
  62        IDA_BUG_ON(ida, !ida_is_empty(ida));
  63}
  64
  65/* Check that ida_destroy and ida_is_empty work */
  66static void ida_check_destroy(struct ida *ida)
  67{
  68        /* Destroy an already-empty IDA */
  69        IDA_BUG_ON(ida, !ida_is_empty(ida));
  70        ida_destroy(ida);
  71        IDA_BUG_ON(ida, !ida_is_empty(ida));
  72
  73        ida_check_destroy_1(ida, 0);
  74        ida_check_destroy_1(ida, 1);
  75        ida_check_destroy_1(ida, 1023);
  76        ida_check_destroy_1(ida, 1024);
  77        ida_check_destroy_1(ida, 12345678);
  78}
  79
  80/*
  81 * Check what happens when we fill a leaf and then delete it.  This may
  82 * discover mishandling of IDR_FREE.
  83 */
  84static void ida_check_leaf(struct ida *ida, unsigned int base)
  85{
  86        unsigned long i;
  87
  88        for (i = 0; i < IDA_BITMAP_BITS; i++) {
  89                IDA_BUG_ON(ida, ida_alloc_min(ida, base, GFP_KERNEL) !=
  90                                base + i);
  91        }
  92
  93        ida_destroy(ida);
  94        IDA_BUG_ON(ida, !ida_is_empty(ida));
  95
  96        IDA_BUG_ON(ida, ida_alloc(ida, GFP_KERNEL) != 0);
  97        IDA_BUG_ON(ida, ida_is_empty(ida));
  98        ida_free(ida, 0);
  99        IDA_BUG_ON(ida, !ida_is_empty(ida));
 100}
 101
 102/*
 103 * Check allocations up to and slightly above the maximum allowed (2^31-1) ID.
 104 * Allocating up to 2^31-1 should succeed, and then allocating the next one
 105 * should fail.
 106 */
 107static void ida_check_max(struct ida *ida)
 108{
 109        unsigned long i, j;
 110
 111        for (j = 1; j < 65537; j *= 2) {
 112                unsigned long base = (1UL << 31) - j;
 113                for (i = 0; i < j; i++) {
 114                        IDA_BUG_ON(ida, ida_alloc_min(ida, base, GFP_KERNEL) !=
 115                                        base + i);
 116                }
 117                IDA_BUG_ON(ida, ida_alloc_min(ida, base, GFP_KERNEL) !=
 118                                -ENOSPC);
 119                ida_destroy(ida);
 120                IDA_BUG_ON(ida, !ida_is_empty(ida));
 121        }
 122}
 123
 124/*
 125 * Check handling of conversions between exceptional entries and full bitmaps.
 126 */
 127static void ida_check_conv(struct ida *ida)
 128{
 129        unsigned long i;
 130
 131        for (i = 0; i < IDA_BITMAP_BITS * 2; i += IDA_BITMAP_BITS) {
 132                IDA_BUG_ON(ida, ida_alloc_min(ida, i + 1, GFP_KERNEL) != i + 1);
 133                IDA_BUG_ON(ida, ida_alloc_min(ida, i + BITS_PER_LONG,
 134                                        GFP_KERNEL) != i + BITS_PER_LONG);
 135                ida_free(ida, i + 1);
 136                ida_free(ida, i + BITS_PER_LONG);
 137                IDA_BUG_ON(ida, !ida_is_empty(ida));
 138        }
 139
 140        for (i = 0; i < IDA_BITMAP_BITS * 2; i++)
 141                IDA_BUG_ON(ida, ida_alloc(ida, GFP_KERNEL) != i);
 142        for (i = IDA_BITMAP_BITS * 2; i > 0; i--)
 143                ida_free(ida, i - 1);
 144        IDA_BUG_ON(ida, !ida_is_empty(ida));
 145
 146        for (i = 0; i < IDA_BITMAP_BITS + BITS_PER_LONG - 4; i++)
 147                IDA_BUG_ON(ida, ida_alloc(ida, GFP_KERNEL) != i);
 148        for (i = IDA_BITMAP_BITS + BITS_PER_LONG - 4; i > 0; i--)
 149                ida_free(ida, i - 1);
 150        IDA_BUG_ON(ida, !ida_is_empty(ida));
 151}
 152
 153static DEFINE_IDA(ida);
 154
 155static int ida_checks(void)
 156{
 157        IDA_BUG_ON(&ida, !ida_is_empty(&ida));
 158        ida_check_alloc(&ida);
 159        ida_check_destroy(&ida);
 160        ida_check_leaf(&ida, 0);
 161        ida_check_leaf(&ida, 1024);
 162        ida_check_leaf(&ida, 1024 * 64);
 163        ida_check_max(&ida);
 164        ida_check_conv(&ida);
 165
 166        printk("IDA: %u of %u tests passed\n", tests_passed, tests_run);
 167        return (tests_run != tests_passed) ? 0 : -EINVAL;
 168}
 169
 170static void ida_exit(void)
 171{
 172}
 173
 174module_init(ida_checks);
 175module_exit(ida_exit);
 176MODULE_AUTHOR("Matthew Wilcox <willy@infradead.org>");
 177MODULE_LICENSE("GPL");
 178