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 comparepqueue_entry_traits58 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 comparepqueue_entry_traits67 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 comparepqueue_entry_traits77 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 comparepqueue_entry_traits87 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 pack_childpqueue130 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 unpack_childpqueue139 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 merge_parent_is_subtree_bpqueue149 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 merge_pair_inlinepqueue158 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(parent); 174 child->prev = parent; 175 if (unpack_child(parent) != NULL) { 176 unpack_child(parent)->prev = child; 177 } 178 /* Create the parent child relationship */ 179 pack_child(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 merge_pairpqueue189 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 meld_pairpqueue196 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, pair_item_a, 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, pq_meld_result, pair_list); 230 pair_list = elt; 231 } while (pair_list != NULL); 232 233 return pq_meld_result; 234 } 235 236 static inline void list_clearpqueue237 list_clear(entry_t e) 238 { 239 e->next = e->prev = NULL; 240 } 241 242 static inline void list_removepqueue243 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(elt->prev) == elt) { 250 pack_child(elt->prev, 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(elt); 259 } 260 261 static inline bool sift_downpqueue262 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, false); 269 } else if (unpack_child(elt)) { 270 remove_root(que, elt); 271 insert(que, elt, 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 sift_uppqueue287 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, false); 297 } 298 299 static inline entry_t remove_non_rootpqueue300 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(elt); 312 if (child) { 313 child = meld_pair(que, child); 314 new_root = merge_pair(que, que->pq_root, child); 315 que->pq_root = new_root; 316 pack_child(elt, 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(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 insertpqueue355 insert(queue_t que, entry_t elt, bool clear = true) 356 { 357 if (clear) { 358 list_clear(elt); 359 pack_child(elt, nullptr); 360 } 361 return (que->pq_root = merge_pair(que, que->pq_root, elt)) == elt; 362 } 363 364 static inline entry_t remove_rootpqueue365 remove_root(queue_t que, entry_t old_root) 366 { 367 entry_t new_root = unpack_child(old_root); 368 369 if (new_root) { 370 que->pq_root = meld_pair(que, new_root); 371 pack_child(old_root, nullptr); 372 } else { 373 que->pq_root = NULL; 374 } 375 return old_root; 376 } 377 378 static inline bool removepqueue379 remove(queue_t que, entry_t elt) 380 { 381 if (elt == que->pq_root) { 382 remove_root(que, elt); 383 return true; 384 } else { 385 remove_non_root(que, elt); 386 return false; 387 } 388 } 389 390 static inline bool entry_increasedpqueue391 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 entry_decreasedpqueue401 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