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