1/*
2 * Copyright (c) 2018 Apple Inc. All rights reserved.
3 *
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. The rights granted to you under the License
10 * may not be used to create, or enable the creation or redistribution of,
11 * unlawful or unlicensed copies of an Apple operating system, or to
12 * circumvent, violate, or enable the circumvention or violation of, any
13 * terms of an Apple operating system software license agreement.
14 *
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
17 *
18 * The Original Code and all software distributed under the License are
19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
23 * Please see the License for the specific language governing rights and
24 * limitations under the License.
25 *
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
27 */
28
29#if KERNEL
30#include <kern/priority_queue.h>
31#include <mach/vm_param.h>
32#include <vm/vm_memtag.h>
33
34#ifdef __LP64__
35static_assert(PRIORITY_QUEUE_ENTRY_CHILD_BITS >= VM_KERNEL_POINTER_SIGNIFICANT_BITS,
36 "Priority Queue child pointer packing failed");
37#endif
38#endif // KERNEL
39
40#pragma mark priority queue helpers
41
42/*
43 * These traits allow to parametrize `struct pqueue` below.
44 */
45
46template <typename queue_t, typename entry_t>
47struct pqueue_entry_traits {
48 /*
49 * Explain how to compare two elements in the natural order.
50 */
51 static inline int
52 compare(queue_t que, entry_t a, entry_t b);
53};
54
55template <typename queue_t>
56struct pqueue_entry_traits<queue_t, priority_queue_entry_t> {
57 static inline int
58 compare(queue_t que, priority_queue_entry_t e1, priority_queue_entry_t e2)
59 {
60 return que->pq_cmp_fn(e1, e2);
61 }
62};
63
64template <typename queue_t>
65struct pqueue_entry_traits<queue_t, priority_queue_entry_deadline_t> {
66 static inline int
67 compare(queue_t que __unused,
68 priority_queue_entry_deadline_t e1, priority_queue_entry_deadline_t e2)
69 {
70 return priority_heap_compare_ints(e1->deadline, e2->deadline);
71 }
72};
73
74template <typename queue_t>
75struct pqueue_entry_traits<queue_t, priority_queue_entry_sched_t> {
76 static inline int
77 compare(queue_t que __unused,
78 priority_queue_entry_sched_t e1, priority_queue_entry_sched_t e2)
79 {
80 return (int)e2->key - (int)e1->key;
81 }
82};
83
84template <typename queue_t>
85struct pqueue_entry_traits<queue_t, priority_queue_entry_stable_t> {
86 static inline int
87 compare(queue_t que __unused,
88 priority_queue_entry_stable_t e1, priority_queue_entry_stable_t e2)
89 {
90 /*
91 * the key is (2 * pri + preempted) so preempted entries
92 * sort "higher" than non preempted entries at the same priority.
93 */
94 if (e1->key != e2->key) {
95 return (int)e2->key - (int)e1->key;
96 }
97 if (e1->stamp != e2->stamp) {
98 /*
99 * preempted entries: younger (bigger timestamp) is "higher"
100 * non preempted entries: older (smaller timestamp) is "higher"
101 */
102 if (e1->key & PRIORITY_QUEUE_ENTRY_PREEMPTED) {
103 return e1->stamp < e2->stamp ? 1 : -1;
104 } else {
105 return e1->stamp > e2->stamp ? 1 : -1;
106 }
107 }
108 return 0;
109 }
110};
111
112#pragma mark main template
113
114/*
115 * Template for our priority queue.
116 *
117 * It is parametrized with:
118 * - `queue_t`: the queue type
119 * - `entry_t`: the element type
120 *
121 * It will use:
122 * - priority_queue_is_min_heap() to determine if it is a min/max heap
123 * - pqueue_entry_traits<queue_t, entry_t>::compare for the ordering
124 */
125template <typename queue_t, typename entry_t>
126struct pqueue {
127 using entry_traits = pqueue_entry_traits<queue_t, entry_t>;
128
129 static inline void
130 pack_child(entry_t e, const entry_t child)
131 {
132#if CONFIG_KERNEL_TAGGING
133 e->tag = vm_memtag_extract_tag((vm_offset_t)child);
134#endif /* CONFIG_KERNEL_TAGGING */
135 e->child = (long)child;
136 }
137
138 static inline entry_t
139 unpack_child(entry_t e)
140 {
141#if CONFIG_KERNEL_TAGGING
142 return (entry_t)(vm_memtag_add_ptr_tag(e->child, e->tag));
143#endif /* CONFIG_KERNEL_TAGGING */
144 return (entry_t)e->child;
145 }
146
147private:
148 static inline bool
149 merge_parent_is_subtree_b(queue_t que, entry_t subtree_a, entry_t subtree_b)
150 {
151 if (priority_queue_is_max_heap((queue_t)nullptr)) {
152 return entry_traits::compare(que, subtree_a, subtree_b) > 0;
153 }
154 return entry_traits::compare(que, subtree_a, subtree_b) < 0;
155 }
156
157 static inline entry_t
158 merge_pair_inline(queue_t que, entry_t subtree_a, entry_t subtree_b)
159 {
160 entry_t merge_result = NULL;
161 if (subtree_a == NULL) {
162 merge_result = subtree_b;
163 } else if (subtree_b == NULL || (subtree_a == subtree_b)) {
164 merge_result = subtree_a;
165 } else {
166 entry_t parent = subtree_a;
167 entry_t child = subtree_b;
168 if (merge_parent_is_subtree_b(que, subtree_a, subtree_b)) {
169 parent = subtree_b;
170 child = subtree_a;
171 }
172 /* Insert the child as the first element in the parent's child list */
173 child->next = unpack_child(e: parent);
174 child->prev = parent;
175 if (unpack_child(e: parent) != NULL) {
176 unpack_child(e: parent)->prev = child;
177 }
178 /* Create the parent child relationship */
179 pack_child(e: parent, child);
180 parent->next = NULL;
181 parent->prev = NULL;
182 merge_result = parent;
183 }
184 return merge_result;
185 }
186
187 OS_NOINLINE
188 static entry_t
189 merge_pair(queue_t que, entry_t subtree_a, entry_t subtree_b)
190 {
191 return merge_pair_inline(que, subtree_a, subtree_b);
192 }
193
194 OS_NOINLINE
195 static entry_t
196 meld_pair(queue_t que, entry_t elt)
197 {
198 entry_t pq_meld_result = NULL;
199 entry_t pair_list = NULL;
200
201 assert(elt); // caller needs to check this.
202
203 /* Phase 1: */
204 /* Split the list into a set of pairs going front to back. */
205 /* Hook these pairs onto an intermediary list in reverse order of traversal.*/
206
207 do {
208 /* Consider two elements at a time for pairing */
209 entry_t pair_item_a = elt;
210 entry_t pair_item_b = elt->next;
211 if (pair_item_b == NULL) {
212 /* Odd number of elements in the list; link the odd element */
213 /* as it is on the intermediate list. */
214 pair_item_a->prev = pair_list;
215 pair_list = pair_item_a;
216 break;
217 }
218 /* Found two elements to pair up */
219 elt = pair_item_b->next;
220 entry_t pair = merge_pair_inline(que, subtree_a: pair_item_a, subtree_b: pair_item_b);
221 /* Link the pair onto the intermediary list */
222 pair->prev = pair_list;
223 pair_list = pair;
224 } while (elt != NULL);
225
226 /* Phase 2: Merge all the pairs in the pair_list */
227 do {
228 elt = pair_list->prev;
229 pq_meld_result = merge_pair_inline(que, subtree_a: pq_meld_result, subtree_b: pair_list);
230 pair_list = elt;
231 } while (pair_list != NULL);
232
233 return pq_meld_result;
234 }
235
236 static inline void
237 list_clear(entry_t e)
238 {
239 e->next = e->prev = NULL;
240 }
241
242 static inline void
243 list_remove(entry_t elt)
244 {
245 assert(elt->prev != NULL);
246 /* Check if elt is head of list at its level; */
247 /* If yes, make the next node the head at that level */
248 /* Else, remove elt from the list at that level */
249 if (unpack_child(e: elt->prev) == elt) {
250 pack_child(e: elt->prev, child: elt->next);
251 } else {
252 elt->prev->next = elt->next;
253 }
254 /* Update prev for next element in list */
255 if (elt->next != NULL) {
256 elt->next->prev = elt->prev;
257 }
258 list_clear(e: elt);
259 }
260
261 static inline bool
262 sift_down(queue_t que, entry_t elt)
263 {
264 bool was_root = (que->pq_root == elt);
265
266 if (!was_root) {
267 remove_non_root(que, elt);
268 insert(que, elt, clear: false);
269 } else if (unpack_child(e: elt)) {
270 remove_root(que, old_root: elt);
271 insert(que, elt, clear: false);
272 } else {
273 /*
274 * If the queue is reduced to a single element,
275 * we have nothing to do.
276 *
277 * It is important not to, so that pq_root remains
278 * non null at all times during priority changes,
279 * so that unsynchronized peeking at the "emptiness"
280 * of the priority queue works as expected.
281 */
282 }
283 return was_root;
284 }
285
286 static inline bool
287 sift_up(queue_t que, entry_t elt)
288 {
289 if (elt == que->pq_root) {
290 return true;
291 }
292
293 /* Remove the element from its current level list */
294 list_remove(elt);
295 /* Re-insert the element into the heap with a merge */
296 return insert(que, elt, clear: false);
297 }
298
299 static inline entry_t
300 remove_non_root(queue_t que, entry_t elt)
301 {
302 entry_t child, new_root;
303
304 /* To remove a non-root element with children levels, */
305 /* - Remove element from its current level list */
306 /* - Pairwise split all the elements in the child level list */
307 /* - Meld all these splits (right-to-left) to form new subtree */
308 /* - Merge the root subtree with the newly formed subtree */
309 list_remove(elt);
310
311 child = unpack_child(e: elt);
312 if (child) {
313 child = meld_pair(que, elt: child);
314 new_root = merge_pair(que, subtree_a: que->pq_root, subtree_b: child);
315 que->pq_root = new_root;
316 pack_child(e: elt, child: nullptr);
317 }
318
319 return elt;
320 }
321
322public:
323
324 /*
325 * exposed interfaces
326 */
327
328 OS_NOINLINE
329 static void
330 destroy(queue_t que, uintptr_t offset, void (^callback)(void *e))
331 {
332 assert(callback != NULL);
333 entry_t head = que->pq_root;
334 entry_t tail = head;
335
336 while (head != NULL) {
337 entry_t child_list = unpack_child(e: head);
338 if (child_list) {
339 tail->next = child_list;
340 while (tail->next) {
341 tail = tail->next;
342 }
343 }
344
345 entry_t elt = head;
346 head = head->next;
347 callback((void *)((char *)elt - offset));
348 }
349
350 /* poison the queue now that it's destroyed */
351 que->pq_root = (entry_t)(~0ul);
352 }
353
354 static inline bool
355 insert(queue_t que, entry_t elt, bool clear = true)
356 {
357 if (clear) {
358 list_clear(e: elt);
359 pack_child(e: elt, child: nullptr);
360 }
361 return (que->pq_root = merge_pair(que, subtree_a: que->pq_root, subtree_b: elt)) == elt;
362 }
363
364 static inline entry_t
365 remove_root(queue_t que, entry_t old_root)
366 {
367 entry_t new_root = unpack_child(e: old_root);
368
369 if (new_root) {
370 que->pq_root = meld_pair(que, elt: new_root);
371 pack_child(e: old_root, child: nullptr);
372 } else {
373 que->pq_root = NULL;
374 }
375 return old_root;
376 }
377
378 static inline bool
379 remove(queue_t que, entry_t elt)
380 {
381 if (elt == que->pq_root) {
382 remove_root(que, old_root: elt);
383 return true;
384 } else {
385 remove_non_root(que, elt);
386 return false;
387 }
388 }
389
390 static inline bool
391 entry_increased(queue_t que, entry_t elt)
392 {
393 if (priority_queue_is_max_heap(que)) {
394 return sift_up(que, elt);
395 } else {
396 return sift_down(que, elt);
397 }
398 }
399
400 static inline bool
401 entry_decreased(queue_t que, entry_t elt)
402 {
403 if (priority_queue_is_min_heap(que)) {
404 return sift_up(que, elt);
405 } else {
406 return sift_down(que, elt);
407 }
408 }
409};
410
411#pragma mark instantiation
412
413#define PRIORITY_QUEUE_MAKE_IMPL(pqueue_t, queue_t, entry_t) \
414 \
415using pqueue_t = pqueue<queue_t, entry_t>; \
416 \
417extern "C" { \
418 \
419__pqueue_overloadable void \
420_priority_queue_destroy(queue_t que, uintptr_t offset, void (^cb)(void *e)) \
421{ \
422 pqueue_t::destroy(que, offset, cb); \
423} \
424 \
425__pqueue_overloadable extern bool \
426priority_queue_insert(queue_t que, entry_t elt) \
427{ \
428 return pqueue_t::insert(que, elt); \
429} \
430 \
431__pqueue_overloadable extern entry_t \
432_priority_queue_remove_root(queue_t que) \
433{ \
434 return pqueue_t::remove_root(que, que->pq_root); \
435} \
436 \
437__pqueue_overloadable extern bool \
438priority_queue_remove(queue_t que, entry_t elt) \
439{ \
440 return pqueue_t::remove(que, elt); \
441} \
442 \
443__pqueue_overloadable extern bool \
444priority_queue_entry_decreased(queue_t que, entry_t elt) \
445{ \
446 return pqueue_t::entry_decreased(que, elt); \
447} \
448 \
449__pqueue_overloadable extern bool \
450priority_queue_entry_increased(queue_t que, entry_t elt) \
451{ \
452 return pqueue_t::entry_increased(que, elt); \
453} \
454 \
455}
456
457PRIORITY_QUEUE_MAKE_IMPL(pqueue_min_t,
458 struct priority_queue_min *, priority_queue_entry_t);
459PRIORITY_QUEUE_MAKE_IMPL(pqueue_max_t,
460 struct priority_queue_max *, priority_queue_entry_t);
461
462PRIORITY_QUEUE_MAKE_IMPL(pqueue_sched_min_t,
463 struct priority_queue_sched_min *, priority_queue_entry_sched_t);
464PRIORITY_QUEUE_MAKE_IMPL(pqueue_sched_max_t,
465 struct priority_queue_sched_max *, priority_queue_entry_sched_t);
466
467PRIORITY_QUEUE_MAKE_IMPL(pqueue_deadline_min_t,
468 struct priority_queue_deadline_min *, priority_queue_entry_deadline_t);
469PRIORITY_QUEUE_MAKE_IMPL(pqueue_deadline_max_t,
470 struct priority_queue_deadline_max *, priority_queue_entry_deadline_t);
471
472PRIORITY_QUEUE_MAKE_IMPL(pqueue_sched_stable_min_t,
473 struct priority_queue_sched_stable_min *, priority_queue_entry_stable_t);
474PRIORITY_QUEUE_MAKE_IMPL(pqueue_sched_stable_max_t,
475 struct priority_queue_sched_stable_max *, priority_queue_entry_stable_t);
476