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 33 #ifdef __LP64__ 34 static_assert(PRIORITY_QUEUE_ENTRY_CHILD_BITS >= VM_KERNEL_POINTER_SIGNIFICANT_BITS, 35 "Priority Queue child pointer packing failed"); 36 #endif 37 #endif // KERNEL 38 39 #pragma mark priority queue helpers 40 41 /* 42 * These traits allow to parametrize `struct pqueue` below. 43 */ 44 45 template <typename queue_t, typename entry_t> 46 struct pqueue_entry_traits { 47 /* 48 * Explain how to compare two elements in the natural order. 49 */ 50 static inline int 51 compare(queue_t que, entry_t a, entry_t b); 52 }; 53 54 template <typename queue_t> 55 struct pqueue_entry_traits<queue_t, priority_queue_entry_t> { 56 static inline int 57 compare(queue_t que, priority_queue_entry_t e1, priority_queue_entry_t e2) 58 { 59 return que->pq_cmp_fn(e1, e2); 60 } 61 }; 62 63 template <typename queue_t> 64 struct pqueue_entry_traits<queue_t, priority_queue_entry_deadline_t> { 65 static inline int 66 compare(queue_t que __unused, 67 priority_queue_entry_deadline_t e1, priority_queue_entry_deadline_t e2) 68 { 69 return priority_heap_compare_ints(e1->deadline, e2->deadline); 70 } 71 }; 72 73 template <typename queue_t> 74 struct pqueue_entry_traits<queue_t, priority_queue_entry_sched_t> { 75 static inline int 76 compare(queue_t que __unused, 77 priority_queue_entry_sched_t e1, priority_queue_entry_sched_t e2) 78 { 79 return (int)e2->key - (int)e1->key; 80 } 81 }; 82 83 template <typename queue_t> 84 struct pqueue_entry_traits<queue_t, priority_queue_entry_stable_t> { 85 static inline int 86 compare(queue_t que __unused, 87 priority_queue_entry_stable_t e1, priority_queue_entry_stable_t e2) 88 { 89 /* 90 * the key is (2 * pri + preempted) so preempted entries 91 * sort "higher" than non preempted entries at the same priority. 92 */ 93 if (e1->key != e2->key) { 94 return (int)e2->key - (int)e1->key; 95 } 96 if (e1->stamp != e2->stamp) { 97 /* 98 * preempted entries: younger (bigger timestamp) is "higher" 99 * non preempted entries: older (smaller timestamp) is "higher" 100 */ 101 if (e1->key & PRIORITY_QUEUE_ENTRY_PREEMPTED) { 102 return e1->stamp < e2->stamp ? 1 : -1; 103 } else { 104 return e1->stamp > e2->stamp ? 1 : -1; 105 } 106 } 107 return 0; 108 } 109 }; 110 111 #pragma mark main template 112 113 /* 114 * Template for our priority queue. 115 * 116 * It is parametrized with: 117 * - `queue_t`: the queue type 118 * - `entry_t`: the element type 119 * 120 * It will use: 121 * - priority_queue_is_min_heap() to determine if it is a min/max heap 122 * - pqueue_entry_traits<queue_t, entry_t>::compare for the ordering 123 */ 124 template <typename queue_t, typename entry_t> 125 struct pqueue { 126 using entry_traits = pqueue_entry_traits<queue_t, entry_t>; 127 128 static inline void 129 pack_child(entry_t e, const entry_t child) 130 { 131 e->child = (long)child; 132 } 133 134 static inline entry_t 135 unpack_child(entry_t e) 136 { 137 return (entry_t)e->child; 138 } 139 140 private: 141 static inline bool 142 merge_parent_is_subtree_b(queue_t que, entry_t subtree_a, entry_t subtree_b) 143 { 144 if (priority_queue_is_max_heap((queue_t)nullptr)) { 145 return entry_traits::compare(que, subtree_a, subtree_b) > 0; 146 } 147 return entry_traits::compare(que, subtree_a, subtree_b) < 0; 148 } 149 150 static inline entry_t 151 merge_pair_inline(queue_t que, entry_t subtree_a, entry_t subtree_b) 152 { 153 entry_t merge_result = NULL; 154 if (subtree_a == NULL) { 155 merge_result = subtree_b; 156 } else if (subtree_b == NULL || (subtree_a == subtree_b)) { 157 merge_result = subtree_a; 158 } else { 159 entry_t parent = subtree_a; 160 entry_t child = subtree_b; 161 if (merge_parent_is_subtree_b(que, subtree_a, subtree_b)) { 162 parent = subtree_b; 163 child = subtree_a; 164 } 165 /* Insert the child as the first element in the parent's child list */ 166 child->next = unpack_child(parent); 167 child->prev = parent; 168 if (unpack_child(parent) != NULL) { 169 unpack_child(parent)->prev = child; 170 } 171 /* Create the parent child relationship */ 172 pack_child(parent, child); 173 parent->next = NULL; 174 parent->prev = NULL; 175 merge_result = parent; 176 } 177 return merge_result; 178 } 179 180 OS_NOINLINE 181 static entry_t 182 merge_pair(queue_t que, entry_t subtree_a, entry_t subtree_b) 183 { 184 return merge_pair_inline(que, subtree_a, subtree_b); 185 } 186 187 OS_NOINLINE 188 static entry_t 189 meld_pair(queue_t que, entry_t elt) 190 { 191 entry_t pq_meld_result = NULL; 192 entry_t pair_list = NULL; 193 194 assert(elt); // caller needs to check this. 195 196 /* Phase 1: */ 197 /* Split the list into a set of pairs going front to back. */ 198 /* Hook these pairs onto an intermediary list in reverse order of traversal.*/ 199 200 do { 201 /* Consider two elements at a time for pairing */ 202 entry_t pair_item_a = elt; 203 entry_t pair_item_b = elt->next; 204 if (pair_item_b == NULL) { 205 /* Odd number of elements in the list; link the odd element */ 206 /* as it is on the intermediate list. */ 207 pair_item_a->prev = pair_list; 208 pair_list = pair_item_a; 209 break; 210 } 211 /* Found two elements to pair up */ 212 elt = pair_item_b->next; 213 entry_t pair = merge_pair_inline(que, pair_item_a, pair_item_b); 214 /* Link the pair onto the intermediary list */ 215 pair->prev = pair_list; 216 pair_list = pair; 217 } while (elt != NULL); 218 219 /* Phase 2: Merge all the pairs in the pair_list */ 220 do { 221 elt = pair_list->prev; 222 pq_meld_result = merge_pair_inline(que, pq_meld_result, pair_list); 223 pair_list = elt; 224 } while (pair_list != NULL); 225 226 return pq_meld_result; 227 } 228 229 static inline void 230 list_remove(entry_t elt) 231 { 232 assert(elt->prev != NULL); 233 /* Check if elt is head of list at its level; */ 234 /* If yes, make the next node the head at that level */ 235 /* Else, remove elt from the list at that level */ 236 if (unpack_child(elt->prev) == elt) { 237 pack_child(elt->prev, elt->next); 238 } else { 239 elt->prev->next = elt->next; 240 } 241 /* Update prev for next element in list */ 242 if (elt->next != NULL) { 243 elt->next->prev = elt->prev; 244 } 245 } 246 247 static inline bool 248 sift_down(queue_t que, entry_t elt) 249 { 250 bool was_root = remove(que, elt); 251 insert(que, elt); 252 return was_root; 253 } 254 255 static inline bool 256 sift_up(queue_t que, entry_t elt) 257 { 258 if (elt == que->pq_root) { 259 return true; 260 } 261 262 /* Remove the element from its current level list */ 263 list_remove(elt); 264 /* Re-insert the element into the heap with a merge */ 265 return insert(que, elt); 266 } 267 268 static inline entry_t 269 remove_non_root(queue_t que, entry_t elt) 270 { 271 entry_t child, new_root; 272 273 /* To remove a non-root element with children levels, */ 274 /* - Remove element from its current level list */ 275 /* - Pairwise split all the elements in the child level list */ 276 /* - Meld all these splits (right-to-left) to form new subtree */ 277 /* - Merge the root subtree with the newly formed subtree */ 278 list_remove(elt); 279 280 child = unpack_child(elt); 281 if (child) { 282 child = meld_pair(que, child); 283 new_root = merge_pair(que, que->pq_root, child); 284 que->pq_root = new_root; 285 } 286 287 return elt; 288 } 289 290 public: 291 292 /* 293 * exposed interfaces 294 */ 295 296 OS_NOINLINE 297 static void 298 destroy(queue_t que, uintptr_t offset, void (^callback)(void *e)) 299 { 300 assert(callback != NULL); 301 entry_t head = que->pq_root; 302 entry_t tail = head; 303 304 while (head != NULL) { 305 entry_t child_list = unpack_child(head); 306 if (child_list) { 307 tail->next = child_list; 308 while (tail->next) { 309 tail = tail->next; 310 } 311 } 312 313 entry_t elt = head; 314 head = head->next; 315 callback((void *)((char *)elt - offset)); 316 } 317 318 /* poison the queue now that it's destroyed */ 319 que->pq_root = (entry_t)(~0ul); 320 } 321 322 static inline bool 323 insert(queue_t que, entry_t elt) 324 { 325 return (que->pq_root = merge_pair(que, que->pq_root, elt)) == elt; 326 } 327 328 static inline entry_t 329 remove_root(queue_t que, entry_t old_root) 330 { 331 entry_t new_root = unpack_child(old_root); 332 que->pq_root = new_root ? meld_pair(que, new_root) : NULL; 333 return old_root; 334 } 335 336 static inline bool 337 remove(queue_t que, entry_t elt) 338 { 339 if (elt == que->pq_root) { 340 remove_root(que, elt); 341 elt->next = elt->prev = NULL; 342 elt->child = 0; 343 return true; 344 } else { 345 remove_non_root(que, elt); 346 elt->next = elt->prev = NULL; 347 elt->child = 0; 348 return false; 349 } 350 } 351 352 static inline bool 353 entry_increased(queue_t que, entry_t elt) 354 { 355 if (priority_queue_is_max_heap(que)) { 356 return sift_up(que, elt); 357 } else { 358 return sift_down(que, elt); 359 } 360 } 361 362 static inline bool 363 entry_decreased(queue_t que, entry_t elt) 364 { 365 if (priority_queue_is_min_heap(que)) { 366 return sift_up(que, elt); 367 } else { 368 return sift_down(que, elt); 369 } 370 } 371 }; 372 373 #pragma mark instantiation 374 375 #define PRIORITY_QUEUE_MAKE_IMPL(pqueue_t, queue_t, entry_t) \ 376 \ 377 using pqueue_t = pqueue<queue_t, entry_t>; \ 378 \ 379 extern "C" { \ 380 \ 381 __pqueue_overloadable void \ 382 _priority_queue_destroy(queue_t que, uintptr_t offset, void (^cb)(void *e)) \ 383 { \ 384 pqueue_t::destroy(que, offset, cb); \ 385 } \ 386 \ 387 __pqueue_overloadable extern bool \ 388 priority_queue_insert(queue_t que, entry_t elt) \ 389 { \ 390 return pqueue_t::insert(que, elt); \ 391 } \ 392 \ 393 __pqueue_overloadable extern entry_t \ 394 _priority_queue_remove_root(queue_t que) \ 395 { \ 396 return pqueue_t::remove_root(que, que->pq_root); \ 397 } \ 398 \ 399 __pqueue_overloadable extern bool \ 400 priority_queue_remove(queue_t que, entry_t elt) \ 401 { \ 402 return pqueue_t::remove(que, elt); \ 403 } \ 404 \ 405 __pqueue_overloadable extern bool \ 406 priority_queue_entry_decreased(queue_t que, entry_t elt) \ 407 { \ 408 return pqueue_t::entry_decreased(que, elt); \ 409 } \ 410 \ 411 __pqueue_overloadable extern bool \ 412 priority_queue_entry_increased(queue_t que, entry_t elt) \ 413 { \ 414 return pqueue_t::entry_increased(que, elt); \ 415 } \ 416 \ 417 } 418 419 PRIORITY_QUEUE_MAKE_IMPL(pqueue_min_t, 420 struct priority_queue_min *, priority_queue_entry_t); 421 PRIORITY_QUEUE_MAKE_IMPL(pqueue_max_t, 422 struct priority_queue_max *, priority_queue_entry_t); 423 424 PRIORITY_QUEUE_MAKE_IMPL(pqueue_sched_min_t, 425 struct priority_queue_sched_min *, priority_queue_entry_sched_t); 426 PRIORITY_QUEUE_MAKE_IMPL(pqueue_sched_max_t, 427 struct priority_queue_sched_max *, priority_queue_entry_sched_t); 428 429 PRIORITY_QUEUE_MAKE_IMPL(pqueue_deadline_min_t, 430 struct priority_queue_deadline_min *, priority_queue_entry_deadline_t); 431 PRIORITY_QUEUE_MAKE_IMPL(pqueue_deadline_max_t, 432 struct priority_queue_deadline_max *, priority_queue_entry_deadline_t); 433 434 PRIORITY_QUEUE_MAKE_IMPL(pqueue_sched_stable_min_t, 435 struct priority_queue_sched_stable_min *, priority_queue_entry_stable_t); 436 PRIORITY_QUEUE_MAKE_IMPL(pqueue_sched_stable_max_t, 437 struct priority_queue_sched_stable_max *, priority_queue_entry_stable_t); 438