tests/priority_queue.cpp

   1 #include <darwintest.h>
   2 #include <darwintest_utils.h>
   3 #include <stdio.h>
   4 #include <assert.h>
   5 #include <setjmp.h>
   6 #include <algorithm>
   7
   8 #define DEVELOPMENT 0
   9 #define DEBUG 0
  10 #define XNU_KERNEL_PRIVATE 1
  11
  12 #define OS_REFCNT_DEBUG 1
  13 #define STRESS_TESTS 0
  14
  15 #define __container_of(ptr, type, field) __extension__({ \
  16                 const __typeof__(((type *)nullptr)->field) *__ptr = (ptr); \
  17                 (type *)((uintptr_t)__ptr - offsetof(type, field)); \
  18         })
  19
  20 #pragma clang diagnostic ignored "-Watomic-implicit-seq-cst"
  21 #pragma clang diagnostic ignored "-Wc++98-compat"
  22
  23 #include "../osfmk/kern/macro_help.h"
  24 #include "../osfmk/kern/priority_queue.h"
  25 #include "../libkern/c++/priority_queue.cpp"
  26
  27 T_GLOBAL_META(T_META_RUN_CONCURRENTLY(true));
  28
  29 static int
  30 compare_numbers_descending(const void * a, const void * b)
  31 {
  32         const uint16_t x = *(const uint16_t *)a;
  33         const uint16_t y = *(const uint16_t *)b;
  34         if (x > y) {
  35                 return -1;
  36         } else if (x < y) {
  37                 return 1;
  38         } else {
  39                 return 0;
  40         }
  41 }
  42
  43 #define PRIORITY_QUEUE_NODES    8
  44
  45 typedef union test_node {
  46         struct {
  47                 struct priority_queue_entry e;
  48                 uint32_t node_key;
  49         };
  50         struct priority_queue_entry_sched ke;
  51         struct priority_queue_entry_stable se;
  52 } *test_node_t;
  53
  54 static void
  55 dump_pqueue_entry(priority_queue_entry_sched_t e, int depth)
  56 {
  57         priority_queue_entry_sched_t t;
  58
  59         printf("%*s [%02d] %p\n", depth * 4, "", e->key, (void *)e);
  60         t = pqueue_sched_max_t::unpack_child(e);
  61         if (t) {
  62                 dump_pqueue_entry(t, depth + 1);
  63         }
  64         while (e->next) {
  65                 e = e->next;
  66                 dump_pqueue_entry(e, depth);
  67         }
  68 }
  69
  70 __unused
  71 static void
  72 dump_pqueue(struct priority_queue_sched_max *pq)
  73 {
  74         dump_pqueue_entry(pq->pq_root, 0);
  75         printf("\n");
  76 }
  77
  78 T_DECL(priority_queue_sched_max, "Basic sched priority queue testing")
  79 {
  80         /* Configuration for the test */
  81         static uint16_t priority_list[] = { 20, 3, 7, 6, 50, 2, 8, 12};
  82
  83         struct priority_queue_sched_max pq;
  84         uint16_t increase_pri = 100;
  85         uint16_t decrease_pri = 90;
  86         uint16_t key = 0;
  87         boolean_t update_result = false;
  88         test_node_t node = NULL;
  89
  90         priority_queue_init(&pq);
  91
  92         /* Add all priorities to the first priority queue */
  93         for (int i = 0; i < PRIORITY_QUEUE_NODES; i++) {
  94                 node = new test_node;
  95                 T_QUIET; T_ASSERT_NOTNULL(node, NULL);
  96
  97                 priority_queue_entry_init(&node->ke);
  98                 priority_queue_entry_set_sched_pri(&pq, &node->ke, priority_list[i], 0);
  99                 priority_queue_insert(&pq, &node->ke);
 100         }
 101
 102         /* Test the priority increase operation by updating the last node added (7) */
 103         priority_queue_entry_set_sched_pri(&pq, &node->ke, increase_pri, 0);
 104         update_result = priority_queue_entry_increased(&pq, &node->ke);
 105         T_ASSERT_TRUE(update_result, "increase key updated root");
 106         key = priority_queue_max_sched_pri(&pq);
 107         T_ASSERT_EQ(key, increase_pri, "verify priority_queue_entry_increased() operation");
 108
 109         /* Test the priority decrease operation by updating the last node added */
 110         priority_queue_entry_set_sched_pri(&pq, &node->ke, decrease_pri, 0);
 111         update_result = priority_queue_entry_decreased(&pq, &node->ke);
 112         T_ASSERT_TRUE(update_result, "decrease key updated root");
 113         key = priority_queue_max_sched_pri(&pq);
 114         T_ASSERT_EQ(key, decrease_pri, "verify priority_queue_entry_decreased() operation");
 115
 116         /* Update our local priority list as well */
 117         priority_list[PRIORITY_QUEUE_NODES - 1] = decrease_pri;
 118
 119         /* Sort the local list in descending order */
 120         qsort(priority_list, PRIORITY_QUEUE_NODES, sizeof(priority_list[0]), compare_numbers_descending);
 121
 122         priority_queue_entry_sched_t k = NULL;
 123
 124         node = pqe_element_fast(k, test_node, ke);
 125
 126         /* Test the maximum operation by comparing max node with local list */
 127         for (int i = 0; i < PRIORITY_QUEUE_NODES; i++) {
 128                 key = priority_queue_max_sched_pri(&pq);
 129                 T_ASSERT_EQ(key, priority_list[i], "[%d] priority queue max node removal", i);
 130                 node = priority_queue_remove_max(&pq, test_node, ke);
 131                 delete node;
 132         }
 133
 134         T_ASSERT_TRUE(priority_queue_empty(&pq), "queue is empty");
 135         priority_queue_destroy(&pq, union test_node, ke, ^(test_node_t n) {
 136                 T_FAIL("Called with %p", n);
 137         });
 138 }
 139
 140 T_DECL(priority_queue_max, "Basic generic priority queue testing")
 141 {
 142         /* Configuration for the test */
 143         static uint16_t priority_list[] = { 20, 3, 7, 6, 50, 2, 8, 12};
 144
 145         struct priority_queue_max pq;
 146         uint16_t increase_pri = 100;
 147         uint16_t decrease_pri = 90;
 148         test_node_t result;
 149         boolean_t update_result = false;
 150         test_node_t node = NULL;
 151
 152         priority_queue_compare_fn_t cmp_fn =
 153             priority_heap_make_comparator(a, b, union test_node, e, {
 154                 if (a->node_key != b->node_key) {
 155                         return priority_heap_compare_ints(a->node_key, b->node_key);
 156                 }
 157                 return 0;
 158         });
 159
 160         priority_queue_init(&pq, cmp_fn);
 161
 162         /* Add all priorities to the first priority queue */
 163         for (int i = 0; i < PRIORITY_QUEUE_NODES; i++) {
 164                 node = new test_node;
 165                 T_QUIET; T_ASSERT_NOTNULL(node, NULL);
 166
 167                 priority_queue_entry_init(&node->e);
 168                 node->node_key = priority_list[i];
 169                 priority_queue_insert(&pq, &node->e);
 170         }
 171
 172         /* Test the priority increase operation by updating the last node added (8) */
 173         node->node_key = increase_pri;
 174         update_result = priority_queue_entry_increased(&pq, &node->e);
 175         T_ASSERT_TRUE(update_result, "increase key updated root");
 176         result = priority_queue_max(&pq, union test_node, e);
 177         T_ASSERT_EQ(result->node_key, increase_pri, "verify priority_queue_entry_increased() operation");
 178
 179
 180         /* Test the priority decrease operation by updating the last node added */
 181         node->node_key = decrease_pri;
 182         update_result = priority_queue_entry_decreased(&pq, &node->e);
 183         T_ASSERT_TRUE(update_result, "decrease key updated root");
 184         result = priority_queue_max(&pq, union test_node, e);
 185         T_ASSERT_EQ(result->node_key, decrease_pri, "verify priority_queue_entry_decreased() operation");
 186
 187         /* Update our local priority list as well */
 188         priority_list[PRIORITY_QUEUE_NODES - 1] = decrease_pri;
 189
 190         /* Sort the local list in descending order */
 191         qsort(priority_list, PRIORITY_QUEUE_NODES, sizeof(priority_list[0]), compare_numbers_descending);
 192
 193         /* Test the maximum operation by comparing max node with local list */
 194         for (int i = 0; i < PRIORITY_QUEUE_NODES; i++) {
 195                 result = priority_queue_remove_max(&pq, union test_node, e);
 196                 T_ASSERT_EQ(result->node_key, priority_list[i],
 197                     "[%d] priority queue max node removal", i);
 198                 delete result;
 199         }
 200
 201         T_ASSERT_TRUE(priority_queue_empty(&pq), "queue is empty");
 202         priority_queue_destroy(&pq, union test_node, e, ^(test_node_t n) {
 203                 T_FAIL("Called with %p", n);
 204         });
 205 }
 206
 207 T_DECL(priority_queue_sched_stable_max, "Basic stable sched priority queue testing")
 208 {
 209         /* Configuration for the test */
 210         static struct config {
 211                 uint16_t pri;
 212                 priority_queue_entry_sched_modifier_t modifier;
 213                 uint64_t stamp;
 214         } config[] = {
 215                 { 20, PRIORITY_QUEUE_ENTRY_NONE, 8 },
 216                 {  3, PRIORITY_QUEUE_ENTRY_NONE, 7 },
 217                 {  3, PRIORITY_QUEUE_ENTRY_PREEMPTED, 6 },
 218                 {  6, PRIORITY_QUEUE_ENTRY_NONE, 5 },
 219                 { 50, PRIORITY_QUEUE_ENTRY_PREEMPTED, 4 },
 220                 { 50, PRIORITY_QUEUE_ENTRY_PREEMPTED, 3 },
 221                 { 50, PRIORITY_QUEUE_ENTRY_NONE, 2 },
 222                 { 50, PRIORITY_QUEUE_ENTRY_NONE, 1 },
 223         };
 224
 225         struct priority_queue_sched_stable_max pq;
 226         test_node_t node = NULL;
 227
 228         priority_queue_init(&pq);
 229
 230         /* Add all priorities to the first priority queue */
 231         for (int i = 0; i < PRIORITY_QUEUE_NODES; i++) {
 232                 node = new test_node;
 233                 T_QUIET; T_ASSERT_NOTNULL(node, NULL);
 234
 235                 priority_queue_entry_init(node);
 236                 node->se.stamp = config[i].stamp;
 237                 priority_queue_entry_set_sched_pri(&pq, &node->se,
 238                     config[i].pri, config[i].modifier);
 239                 priority_queue_insert(&pq, &node->se);
 240         }
 241
 242         /* Sort the local list in descending order */
 243         qsort_b(config, PRIORITY_QUEUE_NODES, sizeof(struct config), ^(const void *a, const void *b){
 244                 const struct config &c1 = *(const struct config *)a;
 245                 const struct config &c2 = *(const struct config *)b;
 246                 if (c1.pri != c2.pri) {
 247                         return c1.pri < c2.pri ? 1 : -1;
 248                 }
 249                 if (c1.modifier != c2.modifier) {
 250                         return c1.modifier < c2.modifier ? 1 : -1;
 251                 }
 252                 if (c1.stamp != c2.stamp) {
 253                         if (c1.modifier) {
 254                                 /* younger is better */
 255                                 return c1.stamp < c1.stamp ? 1 : -1;
 256                         } else {
 257                                 /* older is better */
 258                                 return c1.stamp > c2.stamp ? 1 : -1;
 259                         }
 260                 }
 261                 return 0;
 262         });
 263
 264         /* Test the maximum operation by comparing max node with local list */
 265         for (int i = 0; i < PRIORITY_QUEUE_NODES; i++) {
 266                 node = priority_queue_max(&pq, union test_node, se);
 267                 T_LOG("[%d]: { pri: %2d, modifier: %d, stamp: %lld }\n",
 268                     i, config[i].pri, config[i].modifier, config[i].stamp);
 269                 auto pri = priority_queue_entry_sched_pri(&pq, &node->se);
 270                 T_ASSERT_EQ(pri, config[i].pri,
 271                     "[%d] priority queue max node removal", i);
 272                 auto modifier = priority_queue_entry_sched_modifier(&pq, &node->se);
 273                 T_ASSERT_EQ(modifier, config[i].modifier,
 274                     "[%d] priority queue max node removal", i);
 275                 T_ASSERT_EQ(node->se.stamp, config[i].stamp,
 276                     "[%d] priority queue max node removal", i);
 277                 priority_queue_remove_max(&pq, union test_node, se);
 278                 delete node;
 279         }
 280
 281         T_ASSERT_TRUE(priority_queue_empty(&pq), "queue is empty");
 282         priority_queue_destroy(&pq, union test_node, se, ^(test_node_t n) {
 283                 T_FAIL("Called with %p", n);
 284         });
 285 }