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 } 286