[apple/xnu.git] / osfmk / kern / priority_queue.h

/*
 * Copyright (c) 2018 Apple Inc. All rights reserved.
 *
 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
 *
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. The rights granted to you under the License
 * may not be used to create, or enable the creation or redistribution of,
 * unlawful or unlicensed copies of an Apple operating system, or to
 * circumvent, violate, or enable the circumvention or violation of, any
 * terms of an Apple operating system software license agreement.
 *
 * Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this file.
 *
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 *
 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
 */

#ifndef _KERN_PRIORITY_QUEUE_H_
#define _KERN_PRIORITY_QUEUE_H_

#if KERNEL
#include <kern/kern_types.h>
#include <kern/macro_help.h>
#include <kern/assert.h>
#endif

#include <stdbool.h>
#include <sys/cdefs.h>

#pragma GCC visibility push(hidden)

__BEGIN_DECLS

/*
 * A generic priorty ordered queue implementation based on pairing heaps.
 *
 * Reference Papers:
 * - A Back-to-Basics Empirical Study of Priority Queues (https://arxiv.org/abs/1403.0252)
 * - The Pairing Heap: A New Form of Self-Adjusting Heap
 *   (https://www.cs.cmu.edu/~sleator/papers/pairing-heaps.pdf)
 *
 * The XNU implementation is a basic version of the pairing heap.
 * It allows for O(1) insertion and amortized O(log n) deletion.
 *
 * It is not a stable data structure by default since adding stability would
 * need more pointers and hence more memory.
 *
 * Type of queues
 *
 *         There are several types of priority queues, with types named:
 *
 *         struct priority_queue_<subtype>_<min|max>
 *
 *         In the rest of this header, `struct priority_queue` is used as
 *         a generic type to mean any priority_queue type.
 *
 *         min/max refers to whether the priority queue is a min or a max heap.
 *
 *         the subtype can be:
 *
 *         - sched, in which case the key is built in the linkage and assumed to
 *           be a scheduler priority.
 *
 *         - sched_stable, in which case the key is a combination of:
 *             * a scheduler priority
 *             * whether the entry was preempted or not
 *             * a timestamp.
 *
 *         - generic, in which case a comparison function must be passed to
 *           the priority_queue_init.
 *
 * Element Linkage:
 *
 *         Both types use a common queue head and linkage pattern.
 *         The head of a priority queue is declared as:
 *
 *              struct priority_queue_<subtype>_<min|max> pq_head;
 *
 *         Elements in this queue are linked together using one of the struct
 *         priority_queue_entry_<subtype> objects embedded within a structure:
 *
 *              struct some_data {
 *                      int field1;
 *                      int field2;
 *                      ...
 *                      struct priority_queue_entry link;
 *                      ...
 *                      int last_field;
 *              };
 *         struct some_data is referred to as the queue "element"
 *
 *         This method uses the next, prev and child pointers of the struct
 *         priority_queue_entry linkage object embedded in a queue element to
 *         point to other elements in the queue. The head of the priority queue
 *         (the priority_queue object) will point to the root of the pairing
 *         heap (NULL if heap is empty). This method allows multiple chains
 *         through a given object, by embedding multiple priority_queue_entry
 *         objects in the structure, while simultaneously providing fast removal
 *         and insertion into the heap using only priority_queue_entry object
 *         pointers.
 */


/*
 * Priority keys maintained by the data structure.
 * Since the priority is packed in the node itself, it restricts keys to be 16-bits only.
 */
#define PRIORITY_QUEUE_KEY_NONE             0
typedef uint16_t priority_queue_key_t;

#ifdef __LP64__

/*
 * For 64-bit platforms, pack the priority key into the child pointer
 * The packing/unpacking is done using a compiler trick to sign extend long.
 * This avoids additional NULL checks which are needed in typical packing
 * implementation. The idea is to define the packed location as a long and
 * for unpacking simply cast it to a full pointer which sign extends it.
 */
#define PRIORITY_QUEUE_ENTRY_CHILD_BITS     48
#define PRIORITY_QUEUE_ENTRY_KEY_BITS       16

typedef struct priority_queue_entry {
	struct priority_queue_entry        *next;
	struct priority_queue_entry        *prev;
	long                                __key: PRIORITY_QUEUE_ENTRY_KEY_BITS;
	long                                child: PRIORITY_QUEUE_ENTRY_CHILD_BITS;
} *priority_queue_entry_t;

typedef struct priority_queue_entry_deadline {
	struct priority_queue_entry_deadline *next;
	struct priority_queue_entry_deadline *prev;
	long                                  __key: PRIORITY_QUEUE_ENTRY_KEY_BITS;
	long                                  child: PRIORITY_QUEUE_ENTRY_CHILD_BITS;
	uint64_t                              deadline;
} *priority_queue_entry_deadline_t;

typedef struct priority_queue_entry_sched {
	struct priority_queue_entry_sched  *next;
	struct priority_queue_entry_sched  *prev;
	long                                key: PRIORITY_QUEUE_ENTRY_KEY_BITS;
	long                                child: PRIORITY_QUEUE_ENTRY_CHILD_BITS;
} *priority_queue_entry_sched_t;

typedef struct priority_queue_entry_stable {
	struct priority_queue_entry_stable *next;
	struct priority_queue_entry_stable *prev;
	long                                key: PRIORITY_QUEUE_ENTRY_KEY_BITS;
	long                                child: PRIORITY_QUEUE_ENTRY_CHILD_BITS;
	uint64_t                            stamp;
} *priority_queue_entry_stable_t;

#else /* __LP64__ */

typedef struct priority_queue_entry {
	struct priority_queue_entry        *next;
	struct priority_queue_entry        *prev;
	long                                child;
} *priority_queue_entry_t;

typedef struct priority_queue_entry_deadline {
	struct priority_queue_entry_deadline *next;
	struct priority_queue_entry_deadline *prev;
	long                                  child;
	uint64_t                              deadline;
} *priority_queue_entry_deadline_t;

/*
 * For 32-bit platforms, use an extra field to store the key since child pointer packing
 * is not an option. The child is maintained as a long to use the same packing/unpacking
 * routines that work for 64-bit platforms.
 */
typedef struct priority_queue_entry_sched {
	struct priority_queue_entry_sched  *next;
	struct priority_queue_entry_sched  *prev;
	long                                child;
	priority_queue_key_t                key;
} *priority_queue_entry_sched_t;

typedef struct priority_queue_entry_stable {
	struct priority_queue_entry_stable *next;
	struct priority_queue_entry_stable *prev;
	long                                child;
	priority_queue_key_t                key;
	uint64_t                            stamp;
} *priority_queue_entry_stable_t;

#endif /* __LP64__ */

/*
 * Comparator block prototype
 * Args:
 *      - elements to compare
 * Return:
 * comparision result to indicate relative ordering of elements according to the heap type
 */
typedef int (^priority_queue_compare_fn_t)(struct priority_queue_entry *e1,
    struct priority_queue_entry *e2);

#define priority_heap_compare_ints(a, b) ((a) < (b) ? 1 : -1)

#define priority_heap_make_comparator(name1, name2, type, field, ...) \
	(^int(priority_queue_entry_t __e1, priority_queue_entry_t __e2){        \
	    type *name1 = pqe_element_fast(__e1, type, field);                  \
	    type *name2 = pqe_element_fast(__e2, type, field);                  \
	    __VA_ARGS__;                                                        \
	})

/*
 * Type for any priority queue, only used for documentation purposes.
 */
struct priority_queue;

/*
 * Type of generic heaps
 */
struct priority_queue_min {
	struct priority_queue_entry *pq_root;
	priority_queue_compare_fn_t  pq_cmp_fn;
};
struct priority_queue_max {
	struct priority_queue_entry *pq_root;
	priority_queue_compare_fn_t  pq_cmp_fn;
};

/*
 * Type of deadline heaps
 */
struct priority_queue_deadline_min {
	struct priority_queue_entry_deadline *pq_root;
};
struct priority_queue_deadline_max {
	struct priority_queue_entry_deadline *pq_root;
};

/*
 * Type of scheduler priority based heaps
 */
struct priority_queue_sched_min {
	struct priority_queue_entry_sched *pq_root;
};
struct priority_queue_sched_max {
	struct priority_queue_entry_sched *pq_root;
};

/*
 * Type of scheduler priority based stable heaps
 */
struct priority_queue_sched_stable_min {
	struct priority_queue_entry_stable *pq_root;
};
struct priority_queue_sched_stable_max {
	struct priority_queue_entry_stable *pq_root;
};

#pragma mark generic interface

#define PRIORITY_QUEUE_INITIALIZER { .pq_root = NULL }

#define __pqueue_overloadable  __attribute__((overloadable))

#define priority_queue_is_min_heap(pq) _Generic(pq, \
	struct priority_queue_min *: true, \
	struct priority_queue_max *: false, \
	struct priority_queue_deadline_min *: true, \
	struct priority_queue_deadline_max *: false, \
	struct priority_queue_sched_min *: true, \
	struct priority_queue_sched_max *: false, \
	struct priority_queue_sched_stable_min *: true, \
	struct priority_queue_sched_stable_max *: false)

#define priority_queue_is_max_heap(pq) \
	(!priority_queue_is_min_heap(pq))

/*
 *      Macro:          pqe_element_fast
 *      Function:
 *              Convert a priority_queue_entry_t to a queue element pointer.
 *              Get a pointer to the user-defined element containing
 *              a given priority_queue_entry_t
 *
 *              The fast variant assumes that `qe` is not NULL
 *      Header:
 *              pqe_element_fast(qe, type, field)
 *                      <priority_queue_entry_t> qe
 *                      <type> type of element in priority queue
 *                      <field> chain field in (*<type>)
 *      Returns:
 *              <type *> containing qe
 */
#define pqe_element_fast(qe, type, field)  __container_of(qe, type, field)

/*
 *      Macro:          pqe_element
 *      Function:
 *              Convert a priority_queue_entry_t to a queue element pointer.
 *              Get a pointer to the user-defined element containing
 *              a given priority_queue_entry_t
 *
 *              The non fast variant handles NULL `qe`
 *      Header:
 *              pqe_element(qe, type, field)
 *                      <priority_queue_entry_t> qe
 *                      <type> type of element in priority queue
 *                      <field> chain field in (*<type>)
 *      Returns:
 *              <type *> containing qe
 */
#define pqe_element(qe, type, field)  ({                                        \
	__auto_type _tmp_entry = (qe);                                          \
	_tmp_entry ? pqe_element_fast(_tmp_entry, type, field) : ((type *)NULL);\
})

/*
 * Priority Queue functionality routines
 */

/*
 *      Macro:          priority_queue_empty
 *      Function:
 *              Tests whether a priority queue is empty.
 *      Header:
 *              boolean_t priority_queue_empty(pq)
 *                      <struct priority_queue *> pq
 */
#define priority_queue_empty(pq)         ((pq)->pq_root == NULL)

/*
 *      Macro:          priority_queue_init
 *      Function:
 *              Initialize a <struct priority_queue *>.
 *      Header:
 *              priority_queue_init(pq)
 *                      <struct priority_queue *> pq
 *                      (optional) <cmp_fn> comparator function
 *      Returns:
 *              None
 */
__pqueue_overloadable
extern void
priority_queue_init(struct priority_queue *pq, ...);

/*
 *      Macro:          priority_queue_entry_init
 *      Function:
 *              Initialize a priority_queue_entry_t
 *      Header:
 *              priority_queue_entry_init(qe)
 *                      <priority_queue_entry_t> qe
 *      Returns:
 *              None
 */
#define priority_queue_entry_init(qe) \
	__builtin_bzero(qe, sizeof(*(qe)))

/*
 *      Macro:          priority_queue_destroy
 *      Function:
 *              Destroy a priority queue safely. This routine accepts a callback
 *              to handle any cleanup for elements in the priority queue. The queue does
 *              not maintain its invariants while getting destroyed. The priority queue and
 *              the linkage nodes need to be re-initialized before re-using them.
 *      Header:
 *              priority_queue_destroy(pq, type, field, callback)
 *                      <struct priority_queue *> pq
 *                      <callback> callback for each element
 *
 *      Returns:
 *              None
 */
#define priority_queue_destroy(pq, type, field, callback)                       \
MACRO_BEGIN                                                                     \
	void (^__callback)(type *) = (callback); /* type check */               \
	_priority_queue_destroy(pq, offsetof(type, field),                      \
	    (void (^)(void *))(__callback));                                    \
MACRO_END

/*
 *      Macro:          priority_queue_min
 *      Function:
 *              Lookup the minimum in a min-priority queue.
 *
 *      Header:
 *              priority_queue_min(pq, type, field)
 *                      <struct priority_queue *> pq
 *                      <type> type of element in priority queue
 *                      <field> chain field in (*<type>)
 *      Returns:
 *              <type *> root element
 */
#define priority_queue_min(pq, type, field) ({                                  \
	static_assert(priority_queue_is_min_heap(pq), "queue is min heap");     \
	pqe_element((pq)->pq_root, type, field);                                \
})

/*
 *      Macro:          priority_queue_max
 *      Function:
 *              Lookup the maximum element in a max-priority queue.
 *
 *      Header:
 *              priority_queue_max(pq, type, field)
 *                      <struct priority_queue *> pq
 *                      <type> type of element in priority queue
 *                      <field> chain field in (*<type>)
 *      Returns:
 *              <type *> root element
 */
#define priority_queue_max(pq, type, field) ({                                  \
	static_assert(priority_queue_is_max_heap(pq), "queue is max heap");     \
	pqe_element((pq)->pq_root, type, field);                                \
})

/*
 *      Macro:          priority_queue_insert
 *      Function:
 *              Insert an element into the priority queue
 *
 *              The caller must have set the key prio to insertion
 *
 *      Header:
 *              priority_queue_insert(pq, elt, new_key)
 *                      <struct priority_queue *> pq
 *                      <priority_queue_entry_t> elt
 *      Returns:
 *              Whether the inserted element became the new root
 */
extern bool
priority_queue_insert(struct priority_queue *pq,
    struct priority_queue_entry *elt) __pqueue_overloadable;

/*
 *      Macro:          priority_queue_remove_min
 *      Function:
 *              Remove the minimum element in a min-heap priority queue.
 *      Header:
 *              priority_queue_remove_min(pq, type, field)
 *                      <struct priority_queue *> pq
 *                      <type> type of element in priority queue
 *                      <field> chain field in (*<type>)
 *      Returns:
 *              <type *> max element
 */
#define priority_queue_remove_min(pq, type, field) ({                           \
	static_assert(priority_queue_is_min_heap(pq), "queue is min heap");     \
	pqe_element(_priority_queue_remove_root(pq), type, field);              \
})

/*
 *      Macro:          priority_queue_remove_max
 *      Function:
 *              Remove the maximum element in a max-heap priority queue.
 *      Header:
 *              priority_queue_remove_max(pq, type, field)
 *                      <struct priority_queue *> pq
 *                      <type> type of element in priority queue
 *                      <field> chain field in (*<type>)
 *      Returns:
 *              <type *> max element
 */
#define priority_queue_remove_max(pq, type, field) ({                           \
	static_assert(priority_queue_is_max_heap(pq), "queue is max heap");     \
	pqe_element(_priority_queue_remove_root(pq), type, field);              \
})

/*
 *      Macro:          priority_queue_remove
 *      Function:
 *              Removes an element from the priority queue
 *      Header:
 *              priority_queue_remove(pq, elt)
 *                      <struct priority_queue *> pq
 *                      <priority_queue_entry_t> elt
 *      Returns:
 *              Whether the removed element was the root
 */
extern bool
priority_queue_remove(struct priority_queue *pq,
    struct priority_queue_entry *elt) __pqueue_overloadable;


/*
 *      Macro:          priority_queue_entry_decreased
 *
 *      Function:
 *              Signal the priority queue that the entry priority has decreased.
 *
 *              The new value for the element priority must have been set
 *              prior to calling this function.
 *
 *      Header:
 *              priority_queue_entry_decreased(pq, elt)
 *                      <struct priority_queue *> pq
 *                      <priority_queue_entry_t> elt
 *      Returns:
 *              Whether the update caused the root or its key to change.
 */
extern bool
priority_queue_entry_decreased(struct priority_queue *pq,
    struct priority_queue_entry *elt) __pqueue_overloadable;

/*
 *      Macro:          priority_queue_entry_increased
 *
 *      Function:
 *              Signal the priority queue that the entry priority has increased.
 *
 *              The new value for the element priority must have been set
 *              prior to calling this function.
 *
 *      Header:
 *              priority_queue_entry_increased(pq, elt, new_key)
 *                      <struct priority_queue *> pq
 *                      <priority_queue_entry_t> elt
 *      Returns:
 *              Whether the update caused the root or its key to change.
 */
extern bool
priority_queue_entry_increased(struct priority_queue *pq,
    struct priority_queue_entry *elt) __pqueue_overloadable;


#pragma mark priority_queue_sched_*

__enum_decl(priority_queue_entry_sched_modifier_t, uint8_t, {
	PRIORITY_QUEUE_ENTRY_NONE      = 0,
	PRIORITY_QUEUE_ENTRY_PREEMPTED = 1,
});

#define priority_queue_is_sched_heap(pq) _Generic(pq, \
	struct priority_queue_sched_min *: true, \
	struct priority_queue_sched_max *: true, \
	struct priority_queue_sched_stable_min *: true, \
	struct priority_queue_sched_stable_max *: true, \
	default: false)

/*
 *      Macro:          priority_queue_entry_set_sched_pri
 *
 *      Function:
 *              Sets the scheduler priority on an entry supporting this concept.
 *
 *              The priority is expected to fit on 8 bits.
 *              An optional sorting modifier.
 *
 *      Header:
 *              priority_queue_entry_set_sched_pri(pq, elt, pri, modifier)
 *                      <struct priority_queue *> pq
 *                      <priority_queue_entry_t> elt
 *                      <uint8_t> pri
 *                      <priority_queue_entry_sched_modifier_t> modifier
 */
#define priority_queue_entry_set_sched_pri(pq, elt, pri, modifier)              \
MACRO_BEGIN                                                                     \
	static_assert(priority_queue_is_sched_heap(pq), "is a sched heap");     \
	(elt)->key = (priority_queue_key_t)(((pri) << 8) + (modifier));         \
MACRO_END

/*
 *      Macro:          priority_queue_entry_sched_pri
 *
 *      Function:
 *              Return the scheduler priority on an entry supporting this
 *              concept.
 *
 *      Header:
 *              priority_queue_entry_sched_pri(pq, elt)
 *                      <struct priority_queue *> pq
 *                      <priority_queue_entry_t> elt
 *
 *      Returns:
 *              The scheduler priority of this entry
 */
#define priority_queue_entry_sched_pri(pq, elt) ({                              \
	static_assert(priority_queue_is_sched_heap(pq), "is a sched heap");     \
	(priority_queue_key_t)((elt)->key >> 8);                                \
})

/*
 *      Macro:          priority_queue_entry_sched_modifier
 *
 *      Function:
 *              Return the scheduler modifier on an entry supporting this
 *              concept.
 *
 *      Header:
 *              priority_queue_entry_sched_modifier(pq, elt)
 *                      <struct priority_queue *> pq
 *                      <priority_queue_entry_t> elt
 *
 *      Returns:
 *              The scheduler priority of this entry
 */
#define priority_queue_entry_sched_modifier(pq, elt) ({                         \
	static_assert(priority_queue_is_sched_heap(pq), "is a sched heap");     \
	(priority_queue_entry_sched_modifier_t)(elt)->key;                      \
})

/*
 *      Macro:          priority_queue_min_sched_pri
 *
 *      Function:
 *              Return the scheduler priority of the minimum element
 *              of a scheduler priority queue.
 *
 *      Header:
 *              priority_queue_min_sched_pri(pq)
 *                      <struct priority_queue *> pq
 *
 *      Returns:
 *              The scheduler priority of this entry
 */
#define priority_queue_min_sched_pri(pq) ({                                     \
	static_assert(priority_queue_is_min_heap(pq), "queue is min heap");     \
	priority_queue_entry_sched_pri(pq, (pq)->pq_root);                      \
})

/*
 *      Macro:          priority_queue_max_sched_pri
 *
 *      Function:
 *              Return the scheduler priority of the maximum element
 *              of a scheduler priority queue.
 *
 *      Header:
 *              priority_queue_max_sched_pri(pq)
 *                      <struct priority_queue *> pq
 *
 *      Returns:
 *              The scheduler priority of this entry
 */
#define priority_queue_max_sched_pri(pq) ({                                     \
	static_assert(priority_queue_is_max_heap(pq), "queue is max heap");     \
	priority_queue_entry_sched_pri(pq, (pq)->pq_root);                      \
})


#pragma mark implementation details

#define PRIORITY_QUEUE_MAKE_BASE(pqueue_t, pqelem_t) \
                                                                                \
__pqueue_overloadable extern void                                               \
_priority_queue_destroy(pqueue_t pq, uintptr_t offset, void (^cb)(void *));     \
                                                                                \
__pqueue_overloadable extern bool                                               \
priority_queue_insert(pqueue_t que, pqelem_t elt);                              \
                                                                                \
__pqueue_overloadable extern pqelem_t                                           \
_priority_queue_remove_root(pqueue_t que);                                      \
                                                                                \
__pqueue_overloadable extern bool                                               \
priority_queue_remove(pqueue_t que, pqelem_t elt);                              \
                                                                                \
__pqueue_overloadable extern bool                                               \
priority_queue_entry_decreased(pqueue_t que, pqelem_t elt);                     \
                                                                                \
__pqueue_overloadable extern bool                                               \
priority_queue_entry_increased(pqueue_t que, pqelem_t elt)

#define PRIORITY_QUEUE_MAKE(pqueue_t, pqelem_t) \
__pqueue_overloadable                                                           \
static inline void                                                              \
priority_queue_init(pqueue_t que)                                               \
{                                                                               \
	__builtin_bzero(que, sizeof(*que));                                     \
}                                                                               \
                                                                                \
PRIORITY_QUEUE_MAKE_BASE(pqueue_t, pqelem_t)

#define PRIORITY_QUEUE_MAKE_CB(pqueue_t, pqelem_t) \
__pqueue_overloadable                                                           \
static inline void                                                              \
priority_queue_init(pqueue_t pq, priority_queue_compare_fn_t cmp_fn)            \
{                                                                               \
	pq->pq_root = NULL;                                                     \
	pq->pq_cmp_fn = cmp_fn;                                                 \
}                                                                               \
                                                                                \
PRIORITY_QUEUE_MAKE_BASE(pqueue_t, pqelem_t)

PRIORITY_QUEUE_MAKE_CB(struct priority_queue_min *, priority_queue_entry_t);
PRIORITY_QUEUE_MAKE_CB(struct priority_queue_max *, priority_queue_entry_t);

PRIORITY_QUEUE_MAKE(struct priority_queue_deadline_min *, priority_queue_entry_deadline_t);
PRIORITY_QUEUE_MAKE(struct priority_queue_deadline_max *, priority_queue_entry_deadline_t);

PRIORITY_QUEUE_MAKE(struct priority_queue_sched_min *, priority_queue_entry_sched_t);
PRIORITY_QUEUE_MAKE(struct priority_queue_sched_max *, priority_queue_entry_sched_t);

PRIORITY_QUEUE_MAKE(struct priority_queue_sched_stable_min *, priority_queue_entry_stable_t);
PRIORITY_QUEUE_MAKE(struct priority_queue_sched_stable_max *, priority_queue_entry_stable_t);

__END_DECLS

#pragma GCC visibility pop

#endif /* _KERN_PRIORITY_QUEUE_H_ */