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), T_META_TAG_VM_PREFERRED);
28
29 static int
compare_numbers_descending(const void * a,const void * b)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
dump_pqueue_entry(priority_queue_entry_sched_t e,int depth)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
dump_pqueue(struct priority_queue_sched_max * pq)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 < c2.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