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_remove(entry_t elt) 240 { 241 assert(elt->prev != NULL); 242 /* Check if elt is head of list at its level; */ 243 /* If yes, make the next node the head at that level */ 244 /* Else, remove elt from the list at that level */ 245 if (unpack_child(elt->prev) == elt) { 246 pack_child(elt->prev, elt->next); 247 } else { 248 elt->prev->next = elt->next; 249 } 250 /* Update prev for next element in list */ 251 if (elt->next != NULL) { 252 elt->next->prev = elt->prev; 253 } 254 } 255 256 static inline bool 257 sift_down(queue_t que, entry_t elt) 258 { 259 bool was_root = remove(que, elt); 260 insert(que, elt); 261 return was_root; 262 } 263 264 static inline bool 265 sift_up(queue_t que, entry_t elt) 266 { 267 if (elt == que->pq_root) { 268 return true; 269 } 270 271 /* Remove the element from its current level list */ 272 list_remove(elt); 273 /* Re-insert the element into the heap with a merge */ 274 return insert(que, elt); 275 } 276 277 static inline entry_t 278 remove_non_root(queue_t que, entry_t elt) 279 { 280 entry_t child, new_root; 281 282 /* To remove a non-root element with children levels, */ 283 /* - Remove element from its current level list */ 284 /* - Pairwise split all the elements in the child level list */ 285 /* - Meld all these splits (right-to-left) to form new subtree */ 286 /* - Merge the root subtree with the newly formed subtree */ 287 list_remove(elt); 288 289 child = unpack_child(elt); 290 if (child) { 291 child = meld_pair(que, child); 292 new_root = merge_pair(que, que->pq_root, child); 293 que->pq_root = new_root; 294 } 295 296 return elt; 297 } 298 299 public: 300 301 /* 302 * exposed interfaces 303 */ 304 305 OS_NOINLINE 306 static void 307 destroy(queue_t que, uintptr_t offset, void (^callback)(void *e)) 308 { 309 assert(callback != NULL); 310 entry_t head = que->pq_root; 311 entry_t tail = head; 312 313 while (head != NULL) { 314 entry_t child_list = unpack_child(head); 315 if (child_list) { 316 tail->next = child_list; 317 while (tail->next) { 318 tail = tail->next; 319 } 320 } 321 322 entry_t elt = head; 323 head = head->next; 324 callback((void *)((char *)elt - offset)); 325 } 326 327 /* poison the queue now that it's destroyed */ 328 que->pq_root = (entry_t)(~0ul); 329 } 330 331 static inline bool 332 insert(queue_t que, entry_t elt) 333 { 334 return (que->pq_root = merge_pair(que, que->pq_root, elt)) == elt; 335 } 336 337 static inline entry_t 338 remove_root(queue_t que, entry_t old_root) 339 { 340 entry_t new_root = unpack_child(old_root); 341 que->pq_root = new_root ? meld_pair(que, new_root) : NULL; 342 return old_root; 343 } 344 345 static inline bool 346 remove(queue_t que, entry_t elt) 347 { 348 if (elt == que->pq_root) { 349 remove_root(que, elt); 350 elt->next = elt->prev = NULL; 351 elt->child = 0; 352 #if CONFIG_KERNEL_TBI && KASAN_TBI 353 elt->tag = 0; 354 #endif /* CONFIG_KERNEL_TBI && KASAN_TBI */ 355 return true; 356 } else { 357 remove_non_root(que, elt); 358 elt->next = elt->prev = NULL; 359 elt->child = 0; 360 #if CONFIG_KERNEL_TBI && KASAN_TBI 361 elt->tag = 0; 362 #endif 363 return false; 364 } 365 } 366 367 static inline bool 368 entry_increased(queue_t que, entry_t elt) 369 { 370 if (priority_queue_is_max_heap(que)) { 371 return sift_up(que, elt); 372 } else { 373 return sift_down(que, elt); 374 } 375 } 376 377 static inline bool 378 entry_decreased(queue_t que, entry_t elt) 379 { 380 if (priority_queue_is_min_heap(que)) { 381 return sift_up(que, elt); 382 } else { 383 return sift_down(que, elt); 384 } 385 } 386 }; 387 388 #pragma mark instantiation 389 390 #define PRIORITY_QUEUE_MAKE_IMPL(pqueue_t, queue_t, entry_t) \ 391 \ 392 using pqueue_t = pqueue<queue_t, entry_t>; \ 393 \ 394 extern "C" { \ 395 \ 396 __pqueue_overloadable void \ 397 _priority_queue_destroy(queue_t que, uintptr_t offset, void (^cb)(void *e)) \ 398 { \ 399 pqueue_t::destroy(que, offset, cb); \ 400 } \ 401 \ 402 __pqueue_overloadable extern bool \ 403 priority_queue_insert(queue_t que, entry_t elt) \ 404 { \ 405 return pqueue_t::insert(que, elt); \ 406 } \ 407 \ 408 __pqueue_overloadable extern entry_t \ 409 _priority_queue_remove_root(queue_t que) \ 410 { \ 411 return pqueue_t::remove_root(que, que->pq_root); \ 412 } \ 413 \ 414 __pqueue_overloadable extern bool \ 415 priority_queue_remove(queue_t que, entry_t elt) \ 416 { \ 417 return pqueue_t::remove(que, elt); \ 418 } \ 419 \ 420 __pqueue_overloadable extern bool \ 421 priority_queue_entry_decreased(queue_t que, entry_t elt) \ 422 { \ 423 return pqueue_t::entry_decreased(que, elt); \ 424 } \ 425 \ 426 __pqueue_overloadable extern bool \ 427 priority_queue_entry_increased(queue_t que, entry_t elt) \ 428 { \ 429 return pqueue_t::entry_increased(que, elt); \ 430 } \ 431 \ 432 } 433 434 PRIORITY_QUEUE_MAKE_IMPL(pqueue_min_t, 435 struct priority_queue_min *, priority_queue_entry_t); 436 PRIORITY_QUEUE_MAKE_IMPL(pqueue_max_t, 437 struct priority_queue_max *, priority_queue_entry_t); 438 439 PRIORITY_QUEUE_MAKE_IMPL(pqueue_sched_min_t, 440 struct priority_queue_sched_min *, priority_queue_entry_sched_t); 441 PRIORITY_QUEUE_MAKE_IMPL(pqueue_sched_max_t, 442 struct priority_queue_sched_max *, priority_queue_entry_sched_t); 443 444 PRIORITY_QUEUE_MAKE_IMPL(pqueue_deadline_min_t, 445 struct priority_queue_deadline_min *, priority_queue_entry_deadline_t); 446 PRIORITY_QUEUE_MAKE_IMPL(pqueue_deadline_max_t, 447 struct priority_queue_deadline_max *, priority_queue_entry_deadline_t); 448 449 PRIORITY_QUEUE_MAKE_IMPL(pqueue_sched_stable_min_t, 450 struct priority_queue_sched_stable_min *, priority_queue_entry_stable_t); 451 PRIORITY_QUEUE_MAKE_IMPL(pqueue_sched_stable_max_t, 452 struct priority_queue_sched_stable_max *, priority_queue_entry_stable_t); 453