[apple/xnu.git] / tests / priority_queue.cpp

#include <darwintest.h>
#include <darwintest_utils.h>
#include <stdio.h>
#include <assert.h>
#include <setjmp.h>
#include <algorithm>

#define DEVELOPMENT 0
#define DEBUG 0
#define XNU_KERNEL_PRIVATE 1

#define OS_REFCNT_DEBUG 1
#define STRESS_TESTS 0

#define __container_of(ptr, type, field) __extension__({ \
	        const __typeof__(((type *)nullptr)->field) *__ptr = (ptr); \
	        (type *)((uintptr_t)__ptr - offsetof(type, field)); \
	})

#pragma clang diagnostic ignored "-Watomic-implicit-seq-cst"
#pragma clang diagnostic ignored "-Wc++98-compat"

#include "../osfmk/kern/macro_help.h"
#include "../osfmk/kern/priority_queue.h"
#include "../libkern/c++/priority_queue.cpp"

T_GLOBAL_META(T_META_RUN_CONCURRENTLY(true));

static int
compare_numbers_descending(const void * a, const void * b)
{
	const uint16_t x = *(const uint16_t *)a;
	const uint16_t y = *(const uint16_t *)b;
	if (x > y) {
		return -1;
	} else if (x < y) {
		return 1;
	} else {
		return 0;
	}
}

#define PRIORITY_QUEUE_NODES    8

typedef union test_node {
	struct {
		struct priority_queue_entry e;
		uint32_t node_key;
	};
	struct priority_queue_entry_sched ke;
	struct priority_queue_entry_stable se;
} *test_node_t;

static void
dump_pqueue_entry(priority_queue_entry_sched_t e, int depth)
{
	priority_queue_entry_sched_t t;

	printf("%*s [%02d] %p\n", depth * 4, "", e->key, (void *)e);
	t = pqueue_sched_max_t::unpack_child(e);
	if (t) {
		dump_pqueue_entry(t, depth + 1);
	}
	while (e->next) {
		e = e->next;
		dump_pqueue_entry(e, depth);
	}
}

__unused
static void
dump_pqueue(struct priority_queue_sched_max *pq)
{
	dump_pqueue_entry(pq->pq_root, 0);
	printf("\n");
}

T_DECL(priority_queue_sched_max, "Basic sched priority queue testing")
{
	/* Configuration for the test */
	static uint16_t priority_list[] = { 20, 3, 7, 6, 50, 2, 8, 12};

	struct priority_queue_sched_max pq;
	uint16_t increase_pri = 100;
	uint16_t decrease_pri = 90;
	uint16_t key = 0;
	boolean_t update_result = false;
	test_node_t node = NULL;

	priority_queue_init(&pq);

	/* Add all priorities to the first priority queue */
	for (int i = 0; i < PRIORITY_QUEUE_NODES; i++) {
		node = new test_node;
		T_QUIET; T_ASSERT_NOTNULL(node, NULL);

		priority_queue_entry_init(&node->ke);
		priority_queue_entry_set_sched_pri(&pq, &node->ke, priority_list[i], 0);
		priority_queue_insert(&pq, &node->ke);
	}

	/* Test the priority increase operation by updating the last node added (7) */
	priority_queue_entry_set_sched_pri(&pq, &node->ke, increase_pri, 0);
	update_result = priority_queue_entry_increased(&pq, &node->ke);
	T_ASSERT_TRUE(update_result, "increase key updated root");
	key = priority_queue_max_sched_pri(&pq);
	T_ASSERT_EQ(key, increase_pri, "verify priority_queue_entry_increased() operation");

	/* Test the priority decrease operation by updating the last node added */
	priority_queue_entry_set_sched_pri(&pq, &node->ke, decrease_pri, 0);
	update_result = priority_queue_entry_decreased(&pq, &node->ke);
	T_ASSERT_TRUE(update_result, "decrease key updated root");
	key = priority_queue_max_sched_pri(&pq);
	T_ASSERT_EQ(key, decrease_pri, "verify priority_queue_entry_decreased() operation");

	/* Update our local priority list as well */
	priority_list[PRIORITY_QUEUE_NODES - 1] = decrease_pri;

	/* Sort the local list in descending order */
	qsort(priority_list, PRIORITY_QUEUE_NODES, sizeof(priority_list[0]), compare_numbers_descending);

	priority_queue_entry_sched_t k = NULL;

	node = pqe_element_fast(k, test_node, ke);

	/* Test the maximum operation by comparing max node with local list */
	for (int i = 0; i < PRIORITY_QUEUE_NODES; i++) {
		key = priority_queue_max_sched_pri(&pq);
		T_ASSERT_EQ(key, priority_list[i], "[%d] priority queue max node removal", i);
		node = priority_queue_remove_max(&pq, test_node, ke);
		delete node;
	}

	T_ASSERT_TRUE(priority_queue_empty(&pq), "queue is empty");
	priority_queue_destroy(&pq, union test_node, ke, ^(test_node_t n) {
		T_FAIL("Called with %p", n);
	});
}

T_DECL(priority_queue_max, "Basic generic priority queue testing")
{
	/* Configuration for the test */
	static uint16_t priority_list[] = { 20, 3, 7, 6, 50, 2, 8, 12};

	struct priority_queue_max pq;
	uint16_t increase_pri = 100;
	uint16_t decrease_pri = 90;
	test_node_t result;
	boolean_t update_result = false;
	test_node_t node = NULL;

	priority_queue_compare_fn_t cmp_fn =
	    priority_heap_make_comparator(a, b, union test_node, e, {
		if (a->node_key != b->node_key) {
		        return priority_heap_compare_ints(a->node_key, b->node_key);
		}
		return 0;
	});

	priority_queue_init(&pq, cmp_fn);

	/* Add all priorities to the first priority queue */
	for (int i = 0; i < PRIORITY_QUEUE_NODES; i++) {
		node = new test_node;
		T_QUIET; T_ASSERT_NOTNULL(node, NULL);

		priority_queue_entry_init(&node->e);
		node->node_key = priority_list[i];
		priority_queue_insert(&pq, &node->e);
	}

	/* Test the priority increase operation by updating the last node added (8) */
	node->node_key = increase_pri;
	update_result = priority_queue_entry_increased(&pq, &node->e);
	T_ASSERT_TRUE(update_result, "increase key updated root");
	result = priority_queue_max(&pq, union test_node, e);
	T_ASSERT_EQ(result->node_key, increase_pri, "verify priority_queue_entry_increased() operation");


	/* Test the priority decrease operation by updating the last node added */
	node->node_key = decrease_pri;
	update_result = priority_queue_entry_decreased(&pq, &node->e);
	T_ASSERT_TRUE(update_result, "decrease key updated root");
	result = priority_queue_max(&pq, union test_node, e);
	T_ASSERT_EQ(result->node_key, decrease_pri, "verify priority_queue_entry_decreased() operation");

	/* Update our local priority list as well */
	priority_list[PRIORITY_QUEUE_NODES - 1] = decrease_pri;

	/* Sort the local list in descending order */
	qsort(priority_list, PRIORITY_QUEUE_NODES, sizeof(priority_list[0]), compare_numbers_descending);

	/* Test the maximum operation by comparing max node with local list */
	for (int i = 0; i < PRIORITY_QUEUE_NODES; i++) {
		result = priority_queue_remove_max(&pq, union test_node, e);
		T_ASSERT_EQ(result->node_key, priority_list[i],
		    "[%d] priority queue max node removal", i);
		delete result;
	}

	T_ASSERT_TRUE(priority_queue_empty(&pq), "queue is empty");
	priority_queue_destroy(&pq, union test_node, e, ^(test_node_t n) {
		T_FAIL("Called with %p", n);
	});
}

T_DECL(priority_queue_sched_stable_max, "Basic stable sched priority queue testing")
{
	/* Configuration for the test */
	static struct config {
		uint16_t pri;
		priority_queue_entry_sched_modifier_t modifier;
		uint64_t stamp;
	} config[] = {
		{ 20, PRIORITY_QUEUE_ENTRY_NONE, 8 },
		{  3, PRIORITY_QUEUE_ENTRY_NONE, 7 },
		{  3, PRIORITY_QUEUE_ENTRY_PREEMPTED, 6 },
		{  6, PRIORITY_QUEUE_ENTRY_NONE, 5 },
		{ 50, PRIORITY_QUEUE_ENTRY_PREEMPTED, 4 },
		{ 50, PRIORITY_QUEUE_ENTRY_PREEMPTED, 3 },
		{ 50, PRIORITY_QUEUE_ENTRY_NONE, 2 },
		{ 50, PRIORITY_QUEUE_ENTRY_NONE, 1 },
	};

	struct priority_queue_sched_stable_max pq;
	test_node_t node = NULL;

	priority_queue_init(&pq);

	/* Add all priorities to the first priority queue */
	for (int i = 0; i < PRIORITY_QUEUE_NODES; i++) {
		node = new test_node;
		T_QUIET; T_ASSERT_NOTNULL(node, NULL);

		priority_queue_entry_init(node);
		node->se.stamp = config[i].stamp;
		priority_queue_entry_set_sched_pri(&pq, &node->se,
		    config[i].pri, config[i].modifier);
		priority_queue_insert(&pq, &node->se);
	}

	/* Sort the local list in descending order */
	qsort_b(config, PRIORITY_QUEUE_NODES, sizeof(struct config), ^(const void *a, const void *b){
		const struct config &c1 = *(const struct config *)a;
		const struct config &c2 = *(const struct config *)b;
		if (c1.pri != c2.pri) {
		        return c1.pri < c2.pri ? 1 : -1;
		}
		if (c1.modifier != c2.modifier) {
		        return c1.modifier < c2.modifier ? 1 : -1;
		}
		if (c1.stamp != c2.stamp) {
		        if (c1.modifier) {
		                /* younger is better */
		                return c1.stamp < c1.stamp ? 1 : -1;
			} else {
		                /* older is better */
		                return c1.stamp > c2.stamp ? 1 : -1;
			}
		}
		return 0;
	});

	/* Test the maximum operation by comparing max node with local list */
	for (int i = 0; i < PRIORITY_QUEUE_NODES; i++) {
		node = priority_queue_max(&pq, union test_node, se);
		T_LOG("[%d]: { pri: %2d, modifier: %d, stamp: %lld }\n",
		    i, config[i].pri, config[i].modifier, config[i].stamp);
		auto pri = priority_queue_entry_sched_pri(&pq, &node->se);
		T_ASSERT_EQ(pri, config[i].pri,
		    "[%d] priority queue max node removal", i);
		auto modifier = priority_queue_entry_sched_modifier(&pq, &node->se);
		T_ASSERT_EQ(modifier, config[i].modifier,
		    "[%d] priority queue max node removal", i);
		T_ASSERT_EQ(node->se.stamp, config[i].stamp,
		    "[%d] priority queue max node removal", i);
		priority_queue_remove_max(&pq, union test_node, se);
		delete node;
	}

	T_ASSERT_TRUE(priority_queue_empty(&pq), "queue is empty");
	priority_queue_destroy(&pq, union test_node, se, ^(test_node_t n) {
		T_FAIL("Called with %p", n);
	});
}
Commit	Line	Data
f427ee49 A	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	}