libkern/c++/priority_queue.cpp

   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);