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__ |
35 | static_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 | |
46 | template <typename queue_t, typename entry_t> |
47 | struct 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 | |
55 | template <typename queue_t> |
56 | struct 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 | |
64 | template <typename queue_t> |
65 | struct 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 | |
74 | template <typename queue_t> |
75 | struct 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 | |
84 | template <typename queue_t> |
85 | struct 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 | */ |
125 | template <typename queue_t, typename entry_t> |
126 | struct 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 | |
147 | private: |
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 | |
322 | public: |
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 | \ |
415 | using pqueue_t = pqueue<queue_t, entry_t>; \ |
416 | \ |
417 | extern "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 \ |
426 | priority_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 \ |
438 | priority_queue_remove(queue_t que, entry_t elt) \ |
439 | { \ |
440 | return pqueue_t::remove(que, elt); \ |
441 | } \ |
442 | \ |
443 | __pqueue_overloadable extern bool \ |
444 | priority_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 \ |
450 | priority_queue_entry_increased(queue_t que, entry_t elt) \ |
451 | { \ |
452 | return pqueue_t::entry_increased(que, elt); \ |
453 | } \ |
454 | \ |
455 | } |
456 | |
457 | PRIORITY_QUEUE_MAKE_IMPL(pqueue_min_t, |
458 | struct priority_queue_min *, priority_queue_entry_t); |
459 | PRIORITY_QUEUE_MAKE_IMPL(pqueue_max_t, |
460 | struct priority_queue_max *, priority_queue_entry_t); |
461 | |
462 | PRIORITY_QUEUE_MAKE_IMPL(pqueue_sched_min_t, |
463 | struct priority_queue_sched_min *, priority_queue_entry_sched_t); |
464 | PRIORITY_QUEUE_MAKE_IMPL(pqueue_sched_max_t, |
465 | struct priority_queue_sched_max *, priority_queue_entry_sched_t); |
466 | |
467 | PRIORITY_QUEUE_MAKE_IMPL(pqueue_deadline_min_t, |
468 | struct priority_queue_deadline_min *, priority_queue_entry_deadline_t); |
469 | PRIORITY_QUEUE_MAKE_IMPL(pqueue_deadline_max_t, |
470 | struct priority_queue_deadline_max *, priority_queue_entry_deadline_t); |
471 | |
472 | PRIORITY_QUEUE_MAKE_IMPL(pqueue_sched_stable_min_t, |
473 | struct priority_queue_sched_stable_min *, priority_queue_entry_stable_t); |
474 | PRIORITY_QUEUE_MAKE_IMPL(pqueue_sched_stable_max_t, |
475 | struct priority_queue_sched_stable_max *, priority_queue_entry_stable_t); |
476 | |