tests/lib/test_idalloc.c

   1 #ifdef HAVE_CONFIG_H
   2 #include "config.h"
   3 #endif
   4
   5 #include "id_alloc.h"
   6
   7 #include <inttypes.h>
   8 #include <string.h>
   9 #include <assert.h>
  10 #include <stdio.h>
  11
  12 #define IDS_PER_PAGE (1<<(IDALLOC_OFFSET_BITS + IDALLOC_WORD_BITS))
  13 char allocated_markers[IDS_PER_PAGE*3];
  14
  15 int main(int argc, char **argv)
  16 {
  17         int i, val;
  18         uint32_t pg;
  19         struct id_alloc *a;
  20
  21         /* 1. Rattle test, shake it a little and make sure it doesn't make any
  22          * noise :)
  23          */
  24         a = idalloc_new("Rattle test");
  25         for (i = 0; i < 1000000; i++)
  26                 assert(idalloc_allocate(a) != 0);
  27
  28         idalloc_destroy(a);
  29
  30         /* 2. Reserve a few low IDs, make sure they are skipped by normal
  31          * allocation.
  32          */
  33         a = idalloc_new("Low Reservations");
  34         assert(idalloc_reserve(a, 1) == 1);
  35         assert(idalloc_reserve(a, 3) == 3);
  36         assert(idalloc_reserve(a, 5) == 5);
  37         for (i = 0; i < 100; i++) {
  38                 val = idalloc_allocate(a);
  39                 assert(val != 1 && val != 3 && val != 5);
  40         }
  41         idalloc_destroy(a);
  42
  43         /* 3. Single page testing. Check that IDs are kept unique, and all IDs
  44          * in the existing page are allocated before a new page is added.
  45          */
  46         memset(allocated_markers, 0, sizeof(allocated_markers));
  47         allocated_markers[IDALLOC_INVALID] = 1;
  48
  49         a = idalloc_new("Single Page");
  50
  51         /* reserve the rest of the first page */
  52         for (i = 0; i < IDS_PER_PAGE - 1; i++) {
  53                 val = idalloc_allocate(a);
  54                 assert(val < IDS_PER_PAGE);
  55                 assert(allocated_markers[val] == 0);
  56                 assert(a->capacity == IDS_PER_PAGE);
  57                 allocated_markers[val] = 1;
  58         }
  59         /* Check that the count is right */
  60         assert(a->allocated == IDS_PER_PAGE);
  61
  62         /* Free some IDs out of the middle. */
  63         idalloc_free(a, 300);
  64         allocated_markers[300] = 0;
  65         idalloc_free(a, 400);
  66         allocated_markers[400] = 0;
  67         idalloc_free(a, 500);
  68         allocated_markers[500] = 0;
  69
  70         assert(a->allocated == IDS_PER_PAGE-3);
  71
  72         /* Allocate the three IDs back and make sure they are pulled from the
  73          * set just freed
  74          */
  75         for (i = 0; i < 3; i++) {
  76                 val = idalloc_allocate(a);
  77                 assert(val < IDS_PER_PAGE);
  78                 assert(allocated_markers[val] == 0);
  79                 assert(a->capacity == IDS_PER_PAGE);
  80                 allocated_markers[val] = 1;
  81         }
  82         idalloc_destroy(a);
  83
  84         /* 4. Multi-page testing. */
  85         memset(allocated_markers, 0, sizeof(allocated_markers));
  86         allocated_markers[IDALLOC_INVALID] = 1;
  87
  88         a = idalloc_new("Multi-page");
  89
  90         /* reserve the rest of the first page and all of the second and third */
  91         for (i = 0; i < 3 * IDS_PER_PAGE - 1; i++) {
  92                 val = idalloc_allocate(a);
  93                 assert(val < 3*IDS_PER_PAGE);
  94                 assert(allocated_markers[val] == 0);
  95                 allocated_markers[val] = 1;
  96         }
  97         assert(a->capacity == 3*IDS_PER_PAGE);
  98         assert(a->allocated == 3*IDS_PER_PAGE);
  99
 100         /* Free two IDs from each page. */
 101         for (i = 0; i < 3; i++) {
 102                 idalloc_free(a, 7 + i*IDS_PER_PAGE);
 103                 allocated_markers[7 + i*IDS_PER_PAGE] = 0;
 104
 105                 idalloc_free(a, 4 + i*IDS_PER_PAGE);
 106                 allocated_markers[4 + i*IDS_PER_PAGE] = 0;
 107         }
 108
 109         assert(a->allocated == 3*IDS_PER_PAGE - 6);
 110
 111         /* Allocate the six IDs back and make sure they are pulled from the set
 112          * just freed.
 113          */
 114         for (i = 0; i < 6; i++) {
 115                 val = idalloc_allocate(a);
 116                 assert(val < 3*IDS_PER_PAGE);
 117                 assert(allocated_markers[val] == 0);
 118                 assert(a->capacity == 3*IDS_PER_PAGE);
 119                 allocated_markers[val] = 1;
 120         }
 121
 122         assert(a->capacity == 3*IDS_PER_PAGE);
 123         assert(a->allocated == 3*IDS_PER_PAGE);
 124
 125         /* Walk each allocated ID. Free it, then re-allocate it back. */
 126         for (i = 1; i < 3 * IDS_PER_PAGE - 1; i++) {
 127                 idalloc_free(a, i);
 128                 val = idalloc_allocate(a);
 129                 assert(val == i);
 130                 assert(a->capacity == 3*IDS_PER_PAGE);
 131                 assert(a->allocated == 3*IDS_PER_PAGE);
 132         }
 133         idalloc_destroy(a);
 134
 135         /* 5. Weird Reservations
 136          * idalloc_reserve exists primarily to black out low numbered IDs that
 137          * are reserved for special cases. However, we will test it for more
 138          * complex use cases to avoid unpleasant surprises.
 139          */
 140
 141         memset(allocated_markers, 0, sizeof(allocated_markers));
 142         allocated_markers[IDALLOC_INVALID] = 1;
 143
 144         a = idalloc_new("Weird Reservations");
 145
 146         /* Start with 3 pages fully allocated. */
 147         for (i = 0; i < 3 * IDS_PER_PAGE - 1; i++) {
 148                 val = idalloc_allocate(a);
 149                 assert(val < 3*IDS_PER_PAGE);
 150                 assert(allocated_markers[val] == 0);
 151                 allocated_markers[val] = 1;
 152         }
 153         assert(a->capacity == 3*IDS_PER_PAGE);
 154         assert(a->allocated == 3*IDS_PER_PAGE);
 155
 156         /* Free a bit out of each of the three pages. Then reserve one of the
 157          * three freed IDs. Finally, allocate the other two freed IDs. Do this
 158          * each of three ways. (Reserve out of the first, seconds then third
 159          * page.)
 160          * The intent here is to exercise the rare cases on reserve_bit's
 161          * linked-list removal in the case that it is not removing the first
 162          * page with a free bit in its list of pages with free bits.
 163          */
 164
 165         for (pg = 0; pg < 3; pg++) {
 166                 /* free a bit out of each of the three pages */
 167                 for (i = 0; i < 3; i++) {
 168                         idalloc_free(a, i*IDS_PER_PAGE + 17);
 169                         allocated_markers[i*IDS_PER_PAGE + 17] = 0;
 170                 }
 171
 172                 assert(a->capacity == 3*IDS_PER_PAGE);
 173                 assert(a->allocated == 3*IDS_PER_PAGE-3);
 174
 175                 /* Reserve one of the freed IDs */
 176                 assert(idalloc_reserve(a, pg*IDS_PER_PAGE + 17) ==
 177                        pg*IDS_PER_PAGE + 17);
 178                 allocated_markers[pg*IDS_PER_PAGE + 17] = 1;
 179
 180                 assert(a->capacity == 3*IDS_PER_PAGE);
 181                 assert(a->allocated == 3*IDS_PER_PAGE-2);
 182
 183                 /* Allocate the other two back */
 184                 for (i = 0; i < 2; i++) {
 185                         val = idalloc_allocate(a);
 186                         assert(val < 3*IDS_PER_PAGE);
 187                         assert(allocated_markers[val] == 0);
 188                         allocated_markers[val] = 1;
 189                 }
 190                 assert(a->capacity == 3*IDS_PER_PAGE);
 191                 assert(a->allocated == 3*IDS_PER_PAGE);
 192         }
 193         idalloc_destroy(a);
 194
 195         puts("ID Allocator test successful.\n");
 196         return 0;
 197 }