#include <kern/ast.h>
#include <kern/kern_types.h>
#include <kern/mach_param.h>
#include <kern/queue.h>
#include <kern/sched_prim.h>
#include <kern/simple_lock.h>
#include <kern/spl.h>
#include <kern/waitq.h>
#include <kern/zalloc.h>
#include <libkern/OSAtomic.h>
#include <mach/sync_policy.h>
#include <vm/vm_kern.h>
#include <sys/kdebug.h>
#if CONFIG_WAITQ_DEBUG
#define wqdbg(fmt,...) \
printf("WQ[%s]: " fmt "\n", __func__, ## __VA_ARGS__)
#else
#define wqdbg(fmt,...) do { } while (0)
#endif
#ifdef WAITQ_VERBOSE_DEBUG
#define wqdbg_v(fmt,...) \
printf("WQ[v:%s]: " fmt "\n", __func__, ## __VA_ARGS__)
#else
#define wqdbg_v(fmt,...) do { } while (0)
#endif
#define wqinfo(fmt,...) \
printf("WQ[%s]: " fmt "\n", __func__, ## __VA_ARGS__)
#define wqerr(fmt,...) \
printf("WQ[%s] ERROR: " fmt "\n", __func__, ## __VA_ARGS__)
static thread_t waitq_select_one_locked(struct waitq *waitq, event64_t event,
uint64_t *reserved_preposts,
int priority, spl_t *spl);
static kern_return_t waitq_select_thread_locked(struct waitq *waitq,
event64_t event,
thread_t thread, spl_t *spl);
#define WAITQ_SET_MAX (task_max * 3)
static zone_t waitq_set_zone;
#define P2ROUNDUP(x, align) (-(-((uint32_t)(x)) & -(align)))
#define ROUNDDOWN(x,y) (((x)/(y))*(y))
#ifdef CONFIG_WAITQ_STATS
static __inline__ void waitq_grab_backtrace(uintptr_t bt[NWAITQ_BTFRAMES], int skip);
#endif
#define DEFAULT_MIN_FREE_TABLE_ELEM 100
static uint32_t g_min_free_table_elem;
static uint32_t g_min_free_cache;
static vm_size_t g_wqt_max_tbl_size;
static lck_grp_t g_wqt_lck_grp;
#define NUM_WQ_TABLES 2
#define DEFAULT_MAX_TABLE_SIZE P2ROUNDUP(8 * 1024 * 1024, PAGE_SIZE)
struct wq_id {
union {
uint64_t id;
struct {
uint64_t idx:18,
generation:46;
};
};
};
enum wqt_elem_type {
WQT_FREE = 0,
WQT_ELEM = 1,
WQT_LINK = 2,
WQT_RESERVED = 3,
};
struct wqt_elem {
uint32_t wqt_bits;
uint32_t wqt_next_idx;
struct wq_id wqt_id;
};
#define WQT_IDX_MAX (0x3ffff)
#if defined(DEVELOPMENT) || defined(DEBUG)
uint64_t g_wqt_idx_max = WQT_IDX_MAX;
#endif
#define WQT_BITS_REFCNT_MASK (0x1FFFFFFF)
#define WQT_BITS_REFCNT_SHIFT (0)
#define WQT_BITS_REFCNT (WQT_BITS_REFCNT_MASK << WQT_BITS_REFCNT_SHIFT)
#define WQT_BITS_TYPE_MASK (0x3)
#define WQT_BITS_TYPE_SHIFT (29)
#define WQT_BITS_TYPE (WQT_BITS_TYPE_MASK << WQT_BITS_TYPE_SHIFT)
#define WQT_BITS_VALID_MASK (0x1)
#define WQT_BITS_VALID_SHIFT (31)
#define WQT_BITS_VALID (WQT_BITS_VALID_MASK << WQT_BITS_VALID_SHIFT)
#define wqt_bits_refcnt(bits) \
(((bits) >> WQT_BITS_REFCNT_SHIFT) & WQT_BITS_REFCNT_MASK)
#define wqt_bits_type(bits) \
(((bits) >> WQT_BITS_TYPE_SHIFT) & WQT_BITS_TYPE_MASK)
#define wqt_bits_valid(bits) \
((bits) & WQT_BITS_VALID)
struct wq_table;
typedef void (*wq_table_poison_func)(struct wq_table *, struct wqt_elem *);
struct wq_table {
struct wqt_elem **table;
struct wqt_elem **next_free_slab;
struct wq_id free_list __attribute__((aligned(8)));
uint32_t nelem;
uint32_t used_elem;
uint32_t elem_sz;
uint32_t slab_sz;
uint32_t slab_shift;
uint32_t slab_msk;
uint32_t slab_elem;
zone_t slab_zone;
wq_table_poison_func poison;
lck_mtx_t lock;
uint32_t state;
#if CONFIG_WAITQ_STATS
uint32_t nslabs;
uint64_t nallocs;
uint64_t nreallocs;
uint64_t npreposts;
int64_t nreservations;
uint64_t nreserved_releases;
uint64_t nspins;
uint64_t max_used;
uint64_t avg_used;
uint64_t max_reservations;
uint64_t avg_reservations;
#endif
} __attribute__((aligned(8)));
#define wqt_elem_ofst_slab(slab, slab_msk, ofst) \
\
((struct wqt_elem *)((void *)((uintptr_t)(slab) + ((ofst) & (slab_msk)))))
#if defined(CONFIG_WAITQ_LINK_STATS) || defined(CONFIG_WAITQ_PREPOST_STATS)
static inline struct wqt_elem *
wqt_elem_idx(struct wq_table *table, uint32_t idx)
{
int slab_idx = idx / table->slab_elem;
struct wqt_elem *slab = table->table[slab_idx];
if (!slab)
panic("Invalid index:%d slab:%d (NULL) for table:%p\n",
idx, slab_idx, table);
assert(slab->wqt_id.idx <= idx && (slab->wqt_id.idx + table->slab_elem) > idx);
return wqt_elem_ofst_slab(slab, table->slab_msk, (idx - slab->wqt_id.idx) * table->elem_sz);
}
#else
static inline struct wqt_elem *
wqt_elem_idx(struct wq_table *table, uint32_t idx)
{
uint32_t ofst = idx * table->elem_sz;
struct wqt_elem *slab = table->table[ofst >> table->slab_shift];
if (!slab)
panic("Invalid index:%d slab:%d (NULL) for table:%p\n",
idx, (ofst >> table->slab_shift), table);
assert(slab->wqt_id.idx <= idx && (slab->wqt_id.idx + table->slab_elem) > idx);
return wqt_elem_ofst_slab(slab, table->slab_msk, ofst);
}
#endif
static int __assert_only wqt_elem_in_range(struct wqt_elem *elem,
struct wq_table *table)
{
struct wqt_elem **base = table->table;
uintptr_t e = (uintptr_t)elem;
assert(base != NULL);
while (*base != NULL) {
uintptr_t b = (uintptr_t)(*base);
if (e >= b && e < b + table->slab_sz)
return 1;
base++;
if ((uintptr_t)base >= (uintptr_t)table->table + PAGE_SIZE)
return 0;
}
return 0;
}
static struct wqt_elem *wq_table_get_elem(struct wq_table *table, uint64_t id);
static void wq_table_put_elem(struct wq_table *table, struct wqt_elem *elem);
static int wqt_elem_list_link(struct wq_table *table, struct wqt_elem *parent,
struct wqt_elem *child);
static void wqt_elem_invalidate(struct wqt_elem *elem)
{
uint32_t __assert_only old = OSBitAndAtomic(~WQT_BITS_VALID, &elem->wqt_bits);
OSMemoryBarrier();
assert(((wqt_bits_type(old) != WQT_RESERVED) && (old & WQT_BITS_VALID)) ||
((wqt_bits_type(old) == WQT_RESERVED) && !(old & WQT_BITS_VALID)));
}
static void wqt_elem_mkvalid(struct wqt_elem *elem)
{
uint32_t __assert_only old = OSBitOrAtomic(WQT_BITS_VALID, &elem->wqt_bits);
OSMemoryBarrier();
assert(!(old & WQT_BITS_VALID));
}
static void wqt_elem_set_type(struct wqt_elem *elem, int type)
{
uint32_t old_bits, new_bits;
do {
old_bits = elem->wqt_bits;
new_bits = (old_bits & ~WQT_BITS_TYPE) |
((type & WQT_BITS_TYPE_MASK) << WQT_BITS_TYPE_SHIFT);
} while (OSCompareAndSwap(old_bits, new_bits, &elem->wqt_bits) == FALSE);
OSMemoryBarrier();
}
static void wq_table_bootstrap(void)
{
uint32_t tmp32 = 0;
g_min_free_cache = 0;
g_min_free_table_elem = DEFAULT_MIN_FREE_TABLE_ELEM;
if (PE_parse_boot_argn("wqt_min_free", &tmp32, sizeof(tmp32)) == TRUE)
g_min_free_table_elem = tmp32;
wqdbg("Minimum free table elements: %d", tmp32);
g_wqt_max_tbl_size = DEFAULT_MAX_TABLE_SIZE;
if (PE_parse_boot_argn("wqt_tbl_size", &tmp32, sizeof(tmp32)) == TRUE)
g_wqt_max_tbl_size = (vm_size_t)P2ROUNDUP(tmp32, PAGE_SIZE);
lck_grp_init(&g_wqt_lck_grp, "waitq_table_locks", LCK_GRP_ATTR_NULL);
}
static void wq_table_init(struct wq_table *table, const char *name,
uint32_t max_tbl_elem, uint32_t elem_sz,
wq_table_poison_func poison)
{
kern_return_t kr;
uint32_t slab_sz, slab_shift, slab_msk, slab_elem;
zone_t slab_zone;
size_t max_tbl_sz;
struct wqt_elem *e, **base;
kr = kernel_memory_allocate(kernel_map, (vm_offset_t *)&base,
PAGE_SIZE, 0, KMA_NOPAGEWAIT, VM_KERN_MEMORY_WAITQ);
if (kr != KERN_SUCCESS)
panic("Cannot initialize %s table: "
"kernel_memory_allocate failed:%d\n", name, kr);
memset(base, 0, PAGE_SIZE);
max_tbl_sz = (max_tbl_elem * elem_sz);
max_tbl_sz = P2ROUNDUP(max_tbl_sz, PAGE_SIZE);
slab_sz = (uint32_t)(max_tbl_sz / (PAGE_SIZE / (sizeof(void *))));
if (slab_sz < PAGE_SIZE)
slab_sz = PAGE_SIZE;
slab_shift = 0;
slab_msk = ~0;
for (uint32_t i = 0; i < 31; i++) {
uint32_t bit = (1 << i);
if ((slab_sz & bit) == slab_sz) {
slab_shift = i;
slab_msk = 0;
for (uint32_t j = 0; j < i; j++)
slab_msk |= (1 << j);
break;
}
slab_sz &= ~bit;
}
slab_elem = slab_sz / elem_sz;
wqdbg("Initializing %s zone: slab:%d (%d,0x%x) max:%ld",
name, slab_sz, slab_shift, slab_msk, max_tbl_sz);
slab_zone = zinit(slab_sz, max_tbl_sz, slab_sz, name);
assert(slab_zone != ZONE_NULL);
base[0] = (struct wqt_elem *)zalloc(slab_zone);
if (base[0] == NULL)
panic("Can't allocate a %s table slab from zone:%p",
name, slab_zone);
memset(base[0], 0, slab_sz);
wqdbg("initializing %d links (%d bytes each)...", slab_elem, elem_sz);
for (unsigned l = 0; l < slab_elem; l++) {
e = wqt_elem_ofst_slab(base[0], slab_msk, l * elem_sz);
e->wqt_id.idx = l;
e->wqt_id.generation = 0;
e->wqt_next_idx = l + 1;
}
e = wqt_elem_ofst_slab(base[0], slab_msk, (slab_elem - 1) * elem_sz);
e->wqt_next_idx = WQT_IDX_MAX;
lck_mtx_init(&table->lock, &g_wqt_lck_grp, LCK_ATTR_NULL);
table->slab_sz = slab_sz;
table->slab_shift = slab_shift;
table->slab_msk = slab_msk;
table->slab_elem = slab_elem;
table->slab_zone = slab_zone;
table->elem_sz = elem_sz;
table->nelem = slab_elem;
table->used_elem = 0;
table->elem_sz = elem_sz;
table->poison = poison;
table->table = base;
table->next_free_slab = &base[1];
table->free_list.id = base[0]->wqt_id.id;
#if CONFIG_WAITQ_STATS
table->nslabs = 1;
table->nallocs = 0;
table->nreallocs = 0;
table->npreposts = 0;
table->nreservations = 0;
table->nreserved_releases = 0;
table->max_used = 0;
table->avg_used = 0;
table->max_reservations = 0;
table->avg_reservations = 0;
#endif
}
static void wq_table_grow(struct wq_table *table, uint32_t min_free)
{
struct wqt_elem *slab, **slot;
struct wqt_elem *e = NULL, *first_new_elem, *last_new_elem;
struct wq_id free_id;
uint32_t free_elem;
assert(get_preemption_level() == 0);
assert(table && table->slab_zone);
lck_mtx_lock(&table->lock);
free_elem = table->nelem - table->used_elem;
if (free_elem > min_free) {
lck_mtx_unlock(&table->lock);
return;
}
wqdbg_v("BEGIN");
if (table->next_free_slab == NULL) {
if ((table->nelem - table->used_elem) > 0) {
lck_mtx_unlock(&table->lock);
return;
}
panic("No more room to grow table: %p (nelem: %d, used: %d)",
table, table->nelem, table->used_elem);
}
slot = table->next_free_slab;
table->next_free_slab++;
if ((uintptr_t)table->next_free_slab >= (uintptr_t)table->table + PAGE_SIZE)
table->next_free_slab = NULL;
assert(*slot == NULL);
slab = (struct wqt_elem *)zalloc(table->slab_zone);
if (slab == NULL)
panic("Can't allocate a %s table (%p) slab from zone:%p",
table->slab_zone->zone_name, table, table->slab_zone);
memset(slab, 0, table->slab_sz);
wqdbg_v(" init %d new links...", table->slab_elem);
for (unsigned l = 0; l < table->slab_elem; l++) {
uint32_t idx = l + table->nelem;
if (idx >= (WQT_IDX_MAX - 1))
break;
e = wqt_elem_ofst_slab(slab, table->slab_msk, l * table->elem_sz);
e->wqt_id.idx = idx;
e->wqt_next_idx = idx + 1;
}
last_new_elem = e;
assert(last_new_elem != NULL);
first_new_elem = wqt_elem_ofst_slab(slab, table->slab_msk, 0);
*slot = slab;
if (table->nelem + table->slab_elem >= WQT_IDX_MAX)
table->nelem = WQT_IDX_MAX - 1;
else
table->nelem += table->slab_elem;
#if CONFIG_WAITQ_STATS
table->nslabs += 1;
#endif
free_id = table->free_list;
last_new_elem->wqt_next_idx = free_id.idx;
while (OSCompareAndSwap64(free_id.id, first_new_elem->wqt_id.id,
&table->free_list.id) == FALSE) {
OSMemoryBarrier();
free_id = table->free_list;
last_new_elem->wqt_next_idx = free_id.idx;
}
OSMemoryBarrier();
lck_mtx_unlock(&table->lock);
return;
}
static __attribute__((noinline))
struct wqt_elem *wq_table_alloc_elem(struct wq_table *table, int type, int nelem)
{
int nspins = 0, ntries = 0, nalloc = 0;
uint32_t table_size;
struct wqt_elem *elem = NULL;
struct wq_id free_id, next_id;
static const int max_retries = 500;
if (type != WQT_ELEM && type != WQT_LINK && type != WQT_RESERVED)
panic("wq_table_aloc of invalid elem type:%d from table @%p",
type, table);
assert(nelem > 0);
try_again:
elem = NULL;
if (ntries++ > max_retries) {
struct wqt_elem *tmp;
if (table->used_elem + nelem >= table_size)
panic("No more room to grow table: 0x%p size:%d, used:%d, requested elem:%d",
table, table_size, table->used_elem, nelem);
if (nelem == 1)
panic("Too many alloc retries: %d, table:%p, type:%d, nelem:%d",
ntries, table, type, nelem);
while (nelem > 0) {
tmp = wq_table_alloc_elem(table, type, 1);
if (elem)
wqt_elem_list_link(table, tmp, elem);
elem = tmp;
--nelem;
}
assert(elem != NULL);
return elem;
}
nalloc = 0;
table_size = table->nelem;
if (table->used_elem + nelem >= table_size) {
if (get_preemption_level() != 0) {
#if CONFIG_WAITQ_STATS
table->nspins += 1;
#endif
if (++nspins > 4)
panic("Can't grow table %p with preemption"
" disabled!", table);
delay(1);
goto try_again;
}
wq_table_grow(table, nelem);
goto try_again;
}
free_id = table->free_list;
if (free_id.idx >= table_size)
goto try_again;
for (struct wqt_elem *next_elem = wqt_elem_idx(table, free_id.idx);
nalloc < nelem;
nalloc++) {
elem = next_elem;
next_id.generation = 0;
next_id.idx = next_elem->wqt_next_idx;
if (next_id.idx < table->nelem) {
next_elem = wqt_elem_idx(table, next_id.idx);
next_id.id = next_elem->wqt_id.id;
} else {
goto try_again;
}
}
if (OSCompareAndSwap64(free_id.id, next_id.id,
&table->free_list.id) == FALSE)
goto try_again;
OSMemoryBarrier();
OSAddAtomic(nelem, &table->used_elem);
elem->wqt_next_idx = WQT_IDX_MAX;
elem = wqt_elem_idx(table, free_id.idx);
for (struct wqt_elem *tmp = elem; ; ) {
assert(!wqt_bits_valid(tmp->wqt_bits) &&
(wqt_bits_refcnt(tmp->wqt_bits) == 0));
--nalloc;
tmp->wqt_id.generation += 1;
tmp->wqt_bits = 1;
wqt_elem_set_type(tmp, type);
if (tmp->wqt_next_idx == WQT_IDX_MAX)
break;
assert(tmp->wqt_next_idx != WQT_IDX_MAX);
tmp = wqt_elem_idx(table, tmp->wqt_next_idx);
}
assert(nalloc == 0);
#if CONFIG_WAITQ_STATS
uint64_t nreservations;
table->nallocs += nelem;
if (type == WQT_RESERVED)
OSIncrementAtomic64(&table->nreservations);
nreservations = table->nreservations;
if (table->used_elem > table->max_used)
table->max_used = table->used_elem;
if (nreservations > table->max_reservations)
table->max_reservations = nreservations;
table->avg_used = (table->avg_used + table->used_elem) / 2;
table->avg_reservations = (table->avg_reservations + nreservations) / 2;
#endif
return elem;
}
static void wq_table_realloc_elem(struct wq_table *table, struct wqt_elem *elem, int type)
{
(void)table;
assert(wqt_elem_in_range(elem, table) &&
!wqt_bits_valid(elem->wqt_bits));
#if CONFIG_WAITQ_STATS
table->nreallocs += 1;
if (wqt_bits_type(elem->wqt_bits) == WQT_RESERVED && type != WQT_RESERVED) {
OSDecrementAtomic64(&table->nreservations);
}
table->avg_reservations = (table->avg_reservations + table->nreservations) / 2;
#endif
elem->wqt_id.generation += 1;
elem->wqt_next_idx = WQT_IDX_MAX;
wqt_elem_set_type(elem, type);
return;
}
static void wq_table_free_elem(struct wq_table *table, struct wqt_elem *elem)
{
struct wq_id next_id;
assert(wqt_elem_in_range(elem, table) &&
!wqt_bits_valid(elem->wqt_bits) &&
(wqt_bits_refcnt(elem->wqt_bits) == 0));
OSDecrementAtomic(&table->used_elem);
#if CONFIG_WAITQ_STATS
table->avg_used = (table->avg_used + table->used_elem) / 2;
if (wqt_bits_type(elem->wqt_bits) == WQT_RESERVED)
OSDecrementAtomic64(&table->nreservations);
table->avg_reservations = (table->avg_reservations + table->nreservations) / 2;
#endif
elem->wqt_bits = 0;
if (table->poison)
(table->poison)(table, elem);
again:
next_id = table->free_list;
if (next_id.idx >= table->nelem)
elem->wqt_next_idx = WQT_IDX_MAX;
else
elem->wqt_next_idx = next_id.idx;
OSMemoryBarrier();
if (OSCompareAndSwap64(next_id.id, elem->wqt_id.id,
&table->free_list.id) == FALSE)
goto again;
}
static struct wqt_elem *wq_table_get_elem(struct wq_table *table, uint64_t id)
{
struct wqt_elem *elem;
uint32_t idx, bits, new_bits;
idx = ((struct wq_id *)&id)->idx;
if (idx >= table->nelem)
panic("id:0x%llx : idx:%d > %d", id, idx, table->nelem);
elem = wqt_elem_idx(table, idx);
bits = elem->wqt_bits;
if (!wqt_bits_valid(bits))
return NULL;
if (elem->wqt_id.id != id)
return NULL;
new_bits = bits + 1;
assert(wqt_bits_refcnt(new_bits) > 0);
while (OSCompareAndSwap(bits, new_bits, &elem->wqt_bits) == FALSE) {
bits = elem->wqt_bits;
if (!wqt_bits_valid(bits)) {
return NULL;
}
new_bits = bits + 1;
assert(wqt_bits_refcnt(new_bits) > 0);
}
OSMemoryBarrier();
if (elem->wqt_id.id != id) {
wq_table_put_elem(table, elem);
return NULL;
}
return elem;
}
static void wq_table_put_elem(struct wq_table *table, struct wqt_elem *elem)
{
uint32_t bits, new_bits;
assert(wqt_elem_in_range(elem, table));
bits = elem->wqt_bits;
new_bits = bits - 1;
assert(wqt_bits_refcnt(new_bits) < WQT_BITS_REFCNT_MASK);
while (OSCompareAndSwap(bits, new_bits, &elem->wqt_bits) == FALSE) {
bits = elem->wqt_bits;
new_bits = bits - 1;
assert(wqt_bits_refcnt(new_bits) < WQT_BITS_REFCNT_MASK);
}
OSMemoryBarrier();
if (!wqt_bits_valid(new_bits) && (wqt_bits_refcnt(new_bits) == 0))
wq_table_free_elem(table, elem);
return;
}
static int wqt_elem_list_link(struct wq_table *table, struct wqt_elem *parent, struct wqt_elem *child)
{
int nelem = 1;
assert(wqt_elem_in_range(parent, table));
while (parent->wqt_next_idx != WQT_IDX_MAX) {
assert(parent->wqt_next_idx < table->nelem);
parent = wqt_elem_idx(table, parent->wqt_next_idx);
nelem++;
}
if (child) {
assert(wqt_elem_in_range(child, table));
parent->wqt_next_idx = child->wqt_id.idx;
}
return nelem;
}
static struct wqt_elem *wqt_elem_list_next(struct wq_table *table, struct wqt_elem *head)
{
struct wqt_elem *elem;
if (!head)
return NULL;
if (head->wqt_next_idx >= table->nelem)
return NULL;
elem = wqt_elem_idx(table, head->wqt_next_idx);
assert(wqt_elem_in_range(elem, table));
return elem;
}
static struct wqt_elem *wqt_elem_list_first(struct wq_table *table, uint64_t id)
{
uint32_t idx;
struct wqt_elem *elem = NULL;
if (id == 0)
return NULL;
idx = ((struct wq_id *)&id)->idx;
if (idx > table->nelem)
panic("Invalid element for id:0x%llx", id);
elem = wqt_elem_idx(table, idx);
if (elem->wqt_id.id != id)
return NULL;
if (wqt_bits_valid(elem->wqt_bits) ||
wqt_bits_type(elem->wqt_bits) != WQT_RESERVED ||
wqt_bits_refcnt(elem->wqt_bits) != 1) {
panic("Valid/unreserved element %p (0x%x) in reserved list",
elem, elem->wqt_bits);
}
return elem;
}
static void wqt_elem_reset_next(struct wq_table *table, struct wqt_elem *wqp)
{
(void)table;
if (!wqp)
return;
assert(wqt_elem_in_range(wqp, table));
wqp->wqt_next_idx = WQT_IDX_MAX;
}
static struct wqt_elem *wqt_elem_list_pop(struct wq_table *table, uint64_t *id, int type)
{
struct wqt_elem *first, *next;
if (!id || *id == 0)
return NULL;
first = wqt_elem_list_first(table, *id);
if (!first) {
*id = 0;
return NULL;
}
next = wqt_elem_list_next(table, first);
if (next)
*id = next->wqt_id.id;
else
*id = 0;
wq_table_realloc_elem(table, first, type);
return first;
}
static int wqt_elem_list_release(struct wq_table *table,
struct wqt_elem *head,
int __assert_only type)
{
struct wqt_elem *elem;
struct wq_id free_id;
int nelem = 0;
if (!head)
return 0;
for (elem = head; ; ) {
assert(wqt_elem_in_range(elem, table));
assert(!wqt_bits_valid(elem->wqt_bits) && (wqt_bits_refcnt(elem->wqt_bits) == 1));
assert(wqt_bits_type(elem->wqt_bits) == type);
nelem++;
elem->wqt_bits = 0;
if (table->poison)
(table->poison)(table, elem);
if (elem->wqt_next_idx == WQT_IDX_MAX)
break;
assert(elem->wqt_next_idx < table->nelem);
elem = wqt_elem_idx(table, elem->wqt_next_idx);
}
again:
free_id = table->free_list;
if (free_id.idx >= table->nelem)
elem->wqt_next_idx = WQT_IDX_MAX;
else
elem->wqt_next_idx = free_id.idx;
OSMemoryBarrier();
if (OSCompareAndSwap64(free_id.id, head->wqt_id.id,
&table->free_list.id) == FALSE)
goto again;
OSAddAtomic(-nelem, &table->used_elem);
return nelem;
}
static struct wq_table g_linktable;
enum setid_link_type {
SLT_ALL = -1,
SLT_FREE = WQT_FREE,
SLT_WQS = WQT_ELEM,
SLT_LINK = WQT_LINK,
};
struct setid_link {
struct wqt_elem wqte;
union {
struct {
struct waitq_set *sl_set;
} sl_wqs;
struct {
uint64_t sl_left_setid;
uint64_t sl_right_setid;
} sl_link;
};
#ifdef CONFIG_WAITQ_LINK_STATS
thread_t sl_alloc_th;
task_t sl_alloc_task;
uintptr_t sl_alloc_bt[NWAITQ_BTFRAMES];
uint64_t sl_alloc_ts;
uintptr_t sl_invalidate_bt[NWAITQ_BTFRAMES];
uint64_t sl_invalidate_ts;
uintptr_t sl_mkvalid_bt[NWAITQ_BTFRAMES];
uint64_t sl_mkvalid_ts;
uint64_t sl_free_ts;
#endif
};
#if !defined(CONFIG_WAITQ_LINK_STATS)
_Static_assert((sizeof(struct setid_link) & (sizeof(struct setid_link) - 1)) == 0,
"setid_link struct must be a power of two!");
#endif
#define sl_refcnt(link) \
(wqt_bits_refcnt((link)->wqte.wqt_bits))
#define sl_type(link) \
(wqt_bits_type((link)->wqte.wqt_bits))
#define sl_set_valid(link) \
do { \
wqt_elem_mkvalid(&(link)->wqte); \
lt_do_mkvalid_stats(&(link)->wqte); \
} while (0)
#define sl_is_valid(link) \
wqt_bits_valid((link)->wqte.wqt_bits)
#define sl_set_id wqte.wqt_id
#define SLT_WQS_POISON ((void *)(0xf00df00d))
#define SLT_LINK_POISON (0x0bad0badffffffffull)
static void lt_poison(struct wq_table *table, struct wqt_elem *elem)
{
struct setid_link *sl_link = (struct setid_link *)elem;
(void)table;
switch (sl_type(sl_link)) {
case SLT_WQS:
sl_link->sl_wqs.sl_set = SLT_WQS_POISON;
break;
case SLT_LINK:
sl_link->sl_link.sl_left_setid = SLT_LINK_POISON;
sl_link->sl_link.sl_right_setid = SLT_LINK_POISON;
break;
default:
break;
}
#ifdef CONFIG_WAITQ_LINK_STATS
memset(sl_link->sl_alloc_bt, 0, sizeof(sl_link->sl_alloc_bt));
sl_link->sl_alloc_ts = 0;
memset(sl_link->sl_mkvalid_bt, 0, sizeof(sl_link->sl_mkvalid_bt));
sl_link->sl_mkvalid_ts = 0;
sl_link->sl_alloc_th = THREAD_NULL;
sl_link->sl_free_ts = mach_absolute_time();
#endif
}
#ifdef CONFIG_WAITQ_LINK_STATS
static __inline__ void lt_do_alloc_stats(struct wqt_elem *elem)
{
if (elem) {
struct setid_link *link = (struct setid_link *)elem;
memset(link->sl_alloc_bt, 0, sizeof(link->sl_alloc_bt));
waitq_grab_backtrace(link->sl_alloc_bt, 0);
link->sl_alloc_th = current_thread();
link->sl_alloc_task = current_task();
assert(link->sl_alloc_ts == 0);
link->sl_alloc_ts = mach_absolute_time();
memset(link->sl_invalidate_bt, 0, sizeof(link->sl_invalidate_bt));
link->sl_invalidate_ts = 0;
}
}
static __inline__ void lt_do_invalidate_stats(struct wqt_elem *elem)
{
struct setid_link *link = (struct setid_link *)elem;
if (!elem)
return;
assert(link->sl_mkvalid_ts > 0);
memset(link->sl_invalidate_bt, 0, sizeof(link->sl_invalidate_bt));
link->sl_invalidate_ts = mach_absolute_time();
waitq_grab_backtrace(link->sl_invalidate_bt, 0);
}
static __inline__ void lt_do_mkvalid_stats(struct wqt_elem *elem)
{
struct setid_link *link = (struct setid_link *)elem;
if (!elem)
return;
memset(link->sl_mkvalid_bt, 0, sizeof(link->sl_mkvalid_bt));
link->sl_mkvalid_ts = mach_absolute_time();
waitq_grab_backtrace(link->sl_mkvalid_bt, 0);
}
#else
#define lt_do_alloc_stats(e)
#define lt_do_invalidate_stats(e)
#define lt_do_mkvalid_stats(e)
#endif
static void lt_init(void)
{
uint32_t tablesz = 0, max_links = 0;
if (PE_parse_boot_argn("wql_tsize", &tablesz, sizeof(tablesz)) != TRUE)
tablesz = (uint32_t)g_wqt_max_tbl_size;
tablesz = P2ROUNDUP(tablesz, PAGE_SIZE);
max_links = tablesz / sizeof(struct setid_link);
assert(max_links > 0 && tablesz > 0);
if (max_links > (WQT_IDX_MAX + 1))
max_links = WQT_IDX_MAX + 1;
wqinfo("init linktable with max:%d elements (%d bytes)",
max_links, tablesz);
wq_table_init(&g_linktable, "wqslab.links", max_links,
sizeof(struct setid_link), lt_poison);
}
static void lt_ensure_free_space(void)
{
if (g_linktable.nelem - g_linktable.used_elem < g_min_free_table_elem) {
if (g_linktable.used_elem <= g_linktable.nelem) {
wqdbg_v("Forcing table growth: nelem=%d, used=%d, min_free=%d",
g_linktable.nelem, g_linktable.used_elem,
g_min_free_table_elem);
wq_table_grow(&g_linktable, g_min_free_table_elem);
}
}
}
static struct setid_link *lt_alloc_link(int type)
{
struct wqt_elem *elem;
elem = wq_table_alloc_elem(&g_linktable, type, 1);
lt_do_alloc_stats(elem);
return (struct setid_link *)elem;
}
static void lt_realloc_link(struct setid_link *link, int type)
{
wq_table_realloc_elem(&g_linktable, &link->wqte, type);
#ifdef CONFIG_WAITQ_LINK_STATS
memset(link->sl_alloc_bt, 0, sizeof(link->sl_alloc_bt));
link->sl_alloc_ts = 0;
lt_do_alloc_stats(&link->wqte);
memset(link->sl_invalidate_bt, 0, sizeof(link->sl_invalidate_bt));
link->sl_invalidate_ts = 0;
#endif
}
static void lt_invalidate(struct setid_link *link)
{
wqt_elem_invalidate(&link->wqte);
lt_do_invalidate_stats(&link->wqte);
}
static struct setid_link *lt_get_link(uint64_t setid)
{
struct wqt_elem *elem;
elem = wq_table_get_elem(&g_linktable, setid);
return (struct setid_link *)elem;
}
static void lt_put_link(struct setid_link *link)
{
if (!link)
return;
wq_table_put_elem(&g_linktable, (struct wqt_elem *)link);
}
static struct setid_link *lt_get_reserved(uint64_t setid, int type)
{
struct wqt_elem *elem;
elem = wqt_elem_list_first(&g_linktable, setid);
if (!elem)
return NULL;
wq_table_realloc_elem(&g_linktable, elem, type);
return (struct setid_link *)elem;
}
static inline int waitq_maybe_remove_link(struct waitq *waitq,
uint64_t setid,
struct setid_link *parent,
struct setid_link *left,
struct setid_link *right);
enum {
LINK_WALK_ONE_LEVEL = 0,
LINK_WALK_FULL_DAG = 1,
LINK_WALK_FULL_DAG_UNLOCKED = 2,
};
typedef int (*lt_callback_func)(struct waitq *waitq, void *ctx,
struct setid_link *link);
static __attribute__((noinline))
int walk_setid_links(int walk_type, struct waitq *waitq,
uint64_t setid, int link_type,
void *ctx, lt_callback_func cb)
{
struct setid_link *link;
uint64_t nextid;
int sl_type;
link = lt_get_link(setid);
if (!link)
return WQ_ITERATE_CONTINUE;
setid = nextid = 0;
sl_type = sl_type(link);
if (sl_type == SLT_LINK) {
setid = link->sl_link.sl_left_setid;
nextid = link->sl_link.sl_right_setid;
}
if (link_type == SLT_ALL || link_type == sl_type) {
int ret = cb(waitq, ctx, link);
if (ret != WQ_ITERATE_CONTINUE) {
lt_put_link(link);
return ret;
}
}
if (sl_type == SLT_WQS &&
(walk_type == LINK_WALK_FULL_DAG ||
walk_type == LINK_WALK_FULL_DAG_UNLOCKED)) {
struct waitq_set *wqset = link->sl_wqs.sl_set;
int ret = WQ_ITERATE_CONTINUE;
int get_spl = 0;
int should_unlock = 0;
uint64_t wqset_setid = 0;
spl_t set_spl;
if (waitq_set_is_valid(wqset) && walk_type == LINK_WALK_FULL_DAG) {
if ((!waitq || !waitq_irq_safe(waitq)) &&
waitq_irq_safe(&wqset->wqset_q)) {
get_spl = 1;
set_spl = splsched();
}
waitq_set_lock(wqset);
should_unlock = 1;
}
if (wqset->wqset_id != link->sl_set_id.id) {
if (should_unlock) {
waitq_set_unlock(wqset);
if (get_spl)
splx(set_spl);
}
lt_put_link(link);
return WQ_ITERATE_CONTINUE;
}
wqset_setid = wqset->wqset_q.waitq_set_id;
if (wqset_setid > 0)
ret = walk_setid_links(walk_type, &wqset->wqset_q,
wqset_setid, link_type, ctx, cb);
if (should_unlock) {
waitq_set_unlock(wqset);
if (get_spl)
splx(set_spl);
}
if (ret != WQ_ITERATE_CONTINUE) {
lt_put_link(link);
return ret;
}
}
lt_put_link(link);
if (setid) {
int ret = walk_setid_links(walk_type, waitq, setid, link_type, ctx, cb);
if (ret != WQ_ITERATE_CONTINUE)
return ret;
}
if (nextid)
return walk_setid_links(walk_type, waitq, nextid, link_type, ctx, cb);
return WQ_ITERATE_CONTINUE;
}
static struct wq_table g_prepost_table;
enum wq_prepost_type {
WQP_FREE = WQT_FREE,
WQP_WQ = WQT_ELEM,
WQP_POST = WQT_LINK,
};
struct wq_prepost {
struct wqt_elem wqte;
union {
struct {
struct waitq *wqp_wq_ptr;
} wqp_wq;
struct {
uint64_t wqp_next_id;
uint64_t wqp_wq_id;
} wqp_post;
};
#ifdef CONFIG_WAITQ_PREPOST_STATS
thread_t wqp_alloc_th;
task_t wqp_alloc_task;
uintptr_t wqp_alloc_bt[NWAITQ_BTFRAMES];
#endif
};
#if !defined(CONFIG_WAITQ_PREPOST_STATS)
_Static_assert((sizeof(struct wq_prepost) & (sizeof(struct wq_prepost) - 1)) == 0,
"wq_prepost struct must be a power of two!");
#endif
#define wqp_refcnt(wqp) \
(wqt_bits_refcnt((wqp)->wqte.wqt_bits))
#define wqp_type(wqp) \
(wqt_bits_type((wqp)->wqte.wqt_bits))
#define wqp_set_valid(wqp) \
wqt_elem_mkvalid(&(wqp)->wqte)
#define wqp_is_valid(wqp) \
wqt_bits_valid((wqp)->wqte.wqt_bits)
#define wqp_prepostid wqte.wqt_id
#define WQP_WQ_POISON (0x0bad0badffffffffull)
#define WQP_POST_POISON (0xf00df00df00df00d)
static void wqp_poison(struct wq_table *table, struct wqt_elem *elem)
{
struct wq_prepost *wqp = (struct wq_prepost *)elem;
(void)table;
switch (wqp_type(wqp)) {
case WQP_WQ:
break;
case WQP_POST:
wqp->wqp_post.wqp_next_id = WQP_POST_POISON;
wqp->wqp_post.wqp_wq_id = WQP_POST_POISON;
break;
default:
break;
}
}
#ifdef CONFIG_WAITQ_PREPOST_STATS
static __inline__ void wqp_do_alloc_stats(struct wqt_elem *elem)
{
if (elem) {
struct wq_prepost *wqp = (struct wq_prepost *)elem;
for (;;) {
uint32_t next_idx;
memset(wqp->wqp_alloc_bt, 0, sizeof(wqp->wqp_alloc_bt));
waitq_grab_backtrace(wqp->wqp_alloc_bt, 4);
wqp->wqp_alloc_th = current_thread();
wqp->wqp_alloc_task = current_task();
next_idx = wqp->wqte.wqt_next_idx;
if (next_idx == WQT_IDX_MAX)
break;
assert(next_idx < g_prepost_table.nelem);
wqp = (struct wq_prepost *)wqt_elem_idx(&g_prepost_table,
next_idx);
}
}
}
#else
#define wqp_do_alloc_stats(e)
#endif
static void wqp_init(void)
{
uint32_t tablesz = 0, max_wqp = 0;
if (PE_parse_boot_argn("wqp_tsize", &tablesz, sizeof(tablesz)) != TRUE)
tablesz = (uint32_t)g_wqt_max_tbl_size;
tablesz = P2ROUNDUP(tablesz, PAGE_SIZE);
max_wqp = tablesz / sizeof(struct wq_prepost);
assert(max_wqp > 0 && tablesz > 0);
if (max_wqp > (WQT_IDX_MAX + 1))
max_wqp = WQT_IDX_MAX + 1;
wqinfo("init prepost table with max:%d elements (%d bytes)",
max_wqp, tablesz);
wq_table_init(&g_prepost_table, "wqslab.prepost", max_wqp,
sizeof(struct wq_prepost), wqp_poison);
}
static void wq_prepost_refill_cpu_cache(uint32_t nalloc)
{
struct wqt_elem *new_head, *old_head;
struct wqp_cache *cache;
if (get_preemption_level() != 0)
return;
new_head = wq_table_alloc_elem(&g_prepost_table,
WQT_RESERVED, nalloc);
if (new_head == NULL)
return;
disable_preemption();
cache = &PROCESSOR_DATA(current_processor(), wqp_cache);
cache->avail += nalloc;
if (cache->head == 0 || cache->head == WQT_IDX_MAX) {
cache->head = new_head->wqt_id.id;
goto out;
}
old_head = wqt_elem_list_first(&g_prepost_table, cache->head);
(void)wqt_elem_list_link(&g_prepost_table, new_head, old_head);
cache->head = new_head->wqt_id.id;
out:
enable_preemption();
return;
}
static void wq_prepost_ensure_free_space(void)
{
uint32_t free_elem;
uint32_t min_free;
struct wqp_cache *cache;
if (g_min_free_cache == 0)
g_min_free_cache = (WQP_CACHE_MAX * ml_get_max_cpus());
disable_preemption();
cache = &PROCESSOR_DATA(current_processor(), wqp_cache);
free_elem = cache->avail;
enable_preemption();
if (free_elem < (WQP_CACHE_MAX / 3))
wq_prepost_refill_cpu_cache(WQP_CACHE_MAX - free_elem);
free_elem = g_prepost_table.nelem - g_prepost_table.used_elem;
min_free = g_min_free_table_elem + g_min_free_cache;
if (free_elem < min_free) {
if (g_prepost_table.used_elem <= g_prepost_table.nelem) {
wqdbg_v("Forcing table growth: nelem=%d, used=%d, min_free=%d+%d",
g_prepost_table.nelem, g_prepost_table.used_elem,
g_min_free_table_elem, g_min_free_cache);
wq_table_grow(&g_prepost_table, min_free);
}
}
}
static struct wq_prepost *wq_prepost_alloc(int type, int nelem)
{
struct wqt_elem *elem;
struct wq_prepost *wqp;
struct wqp_cache *cache;
if (type != WQT_RESERVED)
goto do_alloc;
if (nelem == 0)
return NULL;
disable_preemption();
cache = &PROCESSOR_DATA(current_processor(), wqp_cache);
if (nelem <= (int)cache->avail) {
struct wqt_elem *first, *next = NULL;
int nalloc = nelem;
cache->avail -= nelem;
first = wqt_elem_list_first(&g_prepost_table, cache->head);
for (elem = first; elem != NULL && nalloc > 0; elem = next) {
next = wqt_elem_list_next(&g_prepost_table, elem);
if (--nalloc == 0) {
elem->wqt_next_idx = WQT_IDX_MAX;
break;
}
}
assert(nalloc == 0);
if (!next)
cache->head = WQT_IDX_MAX;
else
cache->head = next->wqt_id.id;
assert(!(cache->head == WQT_IDX_MAX && cache->avail > 0));
enable_preemption();
elem = first;
goto out;
}
enable_preemption();
do_alloc:
elem = wq_table_alloc_elem(&g_prepost_table, type, nelem);
if (!elem)
return NULL;
out:
wqp = (struct wq_prepost *)elem;
wqp_do_alloc_stats(elem);
return wqp;
}
static void wq_prepost_invalidate(struct wq_prepost *wqp)
{
wqt_elem_invalidate(&wqp->wqte);
}
static struct wq_prepost *wq_prepost_get(uint64_t wqp_id)
{
struct wqt_elem *elem;
elem = wq_table_get_elem(&g_prepost_table, wqp_id);
return (struct wq_prepost *)elem;
}
static void wq_prepost_put(struct wq_prepost *wqp)
{
wq_table_put_elem(&g_prepost_table, (struct wqt_elem *)wqp);
}
static int wq_prepost_rlink(struct wq_prepost *parent, struct wq_prepost *child)
{
return wqt_elem_list_link(&g_prepost_table, &parent->wqte, &child->wqte);
}
static struct wq_prepost *wq_prepost_get_rnext(struct wq_prepost *head)
{
struct wqt_elem *elem;
struct wq_prepost *wqp;
uint64_t id;
elem = wqt_elem_list_next(&g_prepost_table, &head->wqte);
if (!elem)
return NULL;
id = elem->wqt_id.id;
elem = wq_table_get_elem(&g_prepost_table, id);
if (!elem)
return NULL;
wqp = (struct wq_prepost *)elem;
if (elem->wqt_id.id != id ||
wqp_type(wqp) != WQP_POST ||
wqp->wqp_post.wqp_next_id != head->wqp_prepostid.id) {
wq_table_put_elem(&g_prepost_table, elem);
return NULL;
}
return wqp;
}
static void wq_prepost_reset_rnext(struct wq_prepost *wqp)
{
wqt_elem_reset_next(&g_prepost_table, &wqp->wqte);
}
static int wq_prepost_remove(struct waitq_set *wqset,
struct wq_prepost *wqp)
{
int more_posts = 1;
uint64_t next_id = wqp->wqp_post.wqp_next_id;
uint64_t wqp_id = wqp->wqp_prepostid.id;
struct wq_prepost *prev_wqp, *next_wqp;
assert(wqp_type(wqp) == WQP_POST);
if (next_id == wqp_id) {
wqset->wqset_prepost_id = 0;
more_posts = 0;
goto out;
}
prev_wqp = wq_prepost_get_rnext(wqp);
assert(prev_wqp != NULL);
assert(prev_wqp->wqp_post.wqp_next_id == wqp_id);
assert(prev_wqp->wqp_prepostid.id != wqp_id);
assert(wqp_type(prev_wqp) == WQP_POST);
if (prev_wqp->wqp_prepostid.id == next_id) {
wqset->wqset_prepost_id = prev_wqp->wqp_post.wqp_wq_id;
wq_prepost_invalidate(prev_wqp);
wq_prepost_put(prev_wqp);
more_posts = 0;
goto out;
}
prev_wqp->wqp_post.wqp_next_id = next_id;
next_wqp = wq_prepost_get(next_id);
assert(next_wqp != NULL);
assert(next_wqp != wqp);
assert(next_wqp != prev_wqp);
assert(wqp_type(next_wqp) == WQP_POST);
wq_prepost_reset_rnext(next_wqp);
wq_prepost_rlink(next_wqp, prev_wqp);
if (wqp_id == wqset->wqset_prepost_id)
wqset->wqset_prepost_id = next_id;
wq_prepost_put(prev_wqp);
wq_prepost_put(next_wqp);
out:
wq_prepost_reset_rnext(wqp);
wq_prepost_invalidate(wqp);
return more_posts;
}
static struct wq_prepost *wq_prepost_rfirst(uint64_t id)
{
struct wqt_elem *elem;
elem = wqt_elem_list_first(&g_prepost_table, id);
wqp_do_alloc_stats(elem);
return (struct wq_prepost *)(void *)elem;
}
static struct wq_prepost *wq_prepost_rpop(uint64_t *id, int type)
{
struct wqt_elem *elem;
elem = wqt_elem_list_pop(&g_prepost_table, id, type);
wqp_do_alloc_stats(elem);
return (struct wq_prepost *)(void *)elem;
}
static void wq_prepost_release_rlist(struct wq_prepost *wqp)
{
int nelem = 0;
struct wqp_cache *cache;
struct wqt_elem *elem;
if (!wqp)
return;
elem = &wqp->wqte;
disable_preemption();
cache = &PROCESSOR_DATA(current_processor(), wqp_cache);
if (cache->avail < WQP_CACHE_MAX) {
struct wqt_elem *tmp = NULL;
if (cache->head != WQT_IDX_MAX)
tmp = wqt_elem_list_first(&g_prepost_table, cache->head);
nelem = wqt_elem_list_link(&g_prepost_table, elem, tmp);
cache->head = elem->wqt_id.id;
cache->avail += nelem;
enable_preemption();
return;
}
enable_preemption();
nelem = wqt_elem_list_release(&g_prepost_table, elem, WQT_RESERVED);
#if CONFIG_WAITQ_STATS
g_prepost_table.nreserved_releases += 1;
OSDecrementAtomic64(&g_prepost_table.nreservations);
#endif
}
typedef int (*wqp_callback_func)(struct waitq_set *wqset,
void *ctx,
struct wq_prepost *wqp,
struct waitq *waitq);
static int wq_prepost_foreach_locked(struct waitq_set *wqset,
void *ctx, wqp_callback_func cb)
{
int ret;
struct wq_prepost *wqp, *tmp_wqp;
if (!wqset || !wqset->wqset_prepost_id)
return WQ_ITERATE_SUCCESS;
restart:
wqp = wq_prepost_get(wqset->wqset_prepost_id);
if (!wqp) {
wqset->wqset_prepost_id = 0;
return WQ_ITERATE_SUCCESS;
}
if (wqp_type(wqp) == WQP_WQ) {
uint64_t __assert_only wqp_id = wqp->wqp_prepostid.id;
if (cb)
ret = cb(wqset, ctx, wqp, wqp->wqp_wq.wqp_wq_ptr);
switch (ret) {
case WQ_ITERATE_INVALIDATE_CONTINUE:
assert(wqp_id == wqset->wqset_prepost_id);
wqset->wqset_prepost_id = 0;
case WQ_ITERATE_CONTINUE:
wq_prepost_put(wqp);
ret = WQ_ITERATE_SUCCESS;
break;
case WQ_ITERATE_RESTART:
wq_prepost_put(wqp);
case WQ_ITERATE_DROPPED:
goto restart;
default:
wq_prepost_put(wqp);
break;
}
return ret;
}
assert(wqp->wqp_prepostid.id == wqset->wqset_prepost_id);
assert(wqp_type(wqp) == WQP_POST);
tmp_wqp = wq_prepost_get_rnext(wqp);
assert(tmp_wqp != NULL && wqp_type(tmp_wqp) == WQP_POST);
uint64_t last_id = tmp_wqp->wqp_prepostid.id;
wq_prepost_put(tmp_wqp);
ret = WQ_ITERATE_SUCCESS;
for (;;) {
uint64_t wqp_id, first_id, next_id;
wqp_id = wqp->wqp_prepostid.id;
first_id = wqset->wqset_prepost_id;
next_id = wqp->wqp_post.wqp_next_id;
tmp_wqp = wq_prepost_get(wqp->wqp_post.wqp_wq_id);
if (!tmp_wqp) {
if (wq_prepost_remove(wqset, wqp) == 0) {
wq_prepost_put(wqp);
goto restart;
}
goto next_prepost;
}
assert(wqp_type(tmp_wqp) == WQP_WQ);
if (cb)
ret = cb(wqset, ctx, wqp,
tmp_wqp->wqp_wq.wqp_wq_ptr);
wq_prepost_put(tmp_wqp);
switch (ret) {
case WQ_ITERATE_CONTINUE:
break;
case WQ_ITERATE_INVALIDATE_CONTINUE:
assert(next_id == wqp->wqp_post.wqp_next_id);
if (wq_prepost_remove(wqset, wqp) == 0) {
wq_prepost_put(wqp);
goto restart;
}
goto next_prepost;
case WQ_ITERATE_RESTART:
wq_prepost_put(wqp);
case WQ_ITERATE_DROPPED:
goto restart;
default:
goto finish_prepost_foreach;
}
if (!wqp_is_valid(wqp) ||
(wqp->wqp_post.wqp_next_id != next_id) ||
wqset->wqset_prepost_id != first_id) {
wq_prepost_put(wqp);
goto restart;
}
next_prepost:
if (wqp_id == last_id)
break;
tmp_wqp = wq_prepost_get(next_id);
if (!tmp_wqp) {
panic("Invalid WQP_POST member 0x%llx in waitq set "
"0x%llx prepost list (first:%llx, "
"wqp:%p)",
next_id, wqset->wqset_id, first_id, wqp);
}
wq_prepost_put(wqp);
wqp = tmp_wqp;
assert(wqp_type(wqp) == WQP_POST);
}
finish_prepost_foreach:
wq_prepost_put(wqp);
if (ret == WQ_ITERATE_CONTINUE)
ret = WQ_ITERATE_SUCCESS;
return ret;
}
static int wq_prepost_iterate(uint64_t prepost_id,
void *ctx, wqp_callback_func cb)
{
int ret;
struct wq_prepost *wqp;
if (!prepost_id)
return WQ_ITERATE_SUCCESS;
wqp = wq_prepost_get(prepost_id);
if (!wqp)
return WQ_ITERATE_SUCCESS;
if (wqp_type(wqp) == WQP_WQ) {
ret = WQ_ITERATE_SUCCESS;
if (cb)
ret = cb(NULL, ctx, wqp, wqp->wqp_wq.wqp_wq_ptr);
if (ret != WQ_ITERATE_DROPPED)
wq_prepost_put(wqp);
return ret;
}
assert(wqp->wqp_prepostid.id == prepost_id);
assert(wqp_type(wqp) == WQP_POST);
uint64_t next_id;
ret = WQ_ITERATE_CONTINUE;
do {
struct wq_prepost *tmp_wqp;
struct waitq *wq = NULL;
next_id = wqp->wqp_post.wqp_next_id;
tmp_wqp = wq_prepost_get(wqp->wqp_post.wqp_wq_id);
if (tmp_wqp) {
assert(wqp_type(tmp_wqp) == WQP_WQ);
wq = tmp_wqp->wqp_wq.wqp_wq_ptr;
}
if (cb)
ret = cb(NULL, ctx, wqp, wq);
if (tmp_wqp)
wq_prepost_put(tmp_wqp);
if (ret != WQ_ITERATE_CONTINUE)
break;
tmp_wqp = wq_prepost_get(next_id);
if (!tmp_wqp) {
ret = WQ_ITERATE_ABORTED;
break;
}
wq_prepost_put(wqp);
wqp = tmp_wqp;
assert(wqp_type(wqp) == WQP_POST);
} while (next_id != prepost_id);
if (ret != WQ_ITERATE_DROPPED)
wq_prepost_put(wqp);
if (ret == WQ_ITERATE_CONTINUE)
ret = WQ_ITERATE_SUCCESS;
return ret;
}
struct _is_posted_ctx {
struct waitq *posting_wq;
int did_prepost;
};
static int wq_is_preposted_on_set_cb(struct waitq_set *wqset, void *ctx,
struct wq_prepost *wqp, struct waitq *waitq)
{
struct _is_posted_ctx *pctx = (struct _is_posted_ctx *)ctx;
(void)wqset;
(void)wqp;
if (pctx->posting_wq == waitq)
pctx->did_prepost = 1;
return WQ_ITERATE_CONTINUE;
}
static int wq_is_preposted_on_set(struct waitq *waitq, struct waitq_set *wqset)
{
int ret;
struct _is_posted_ctx pctx;
if (waitq->waitq_prepost_id != 0 &&
wqset->wqset_prepost_id == waitq->waitq_prepost_id)
return 1;
pctx.posting_wq = waitq;
pctx.did_prepost = 0;
ret = wq_prepost_foreach_locked(wqset, (void *)&pctx,
wq_is_preposted_on_set_cb);
return pctx.did_prepost;
}
static struct wq_prepost *wq_get_prepost_obj(uint64_t *reserved, int type)
{
struct wq_prepost *wqp = NULL;
if (reserved && *reserved) {
wqp = wq_prepost_rpop(reserved, type);
} else {
wqp = wq_prepost_alloc(type, 1);
}
if (wqp == NULL)
panic("Couldn't allocate prepost object!");
return wqp;
}
static void wq_prepost_do_post_locked(struct waitq_set *wqset,
struct waitq *waitq,
uint64_t *reserved)
{
struct wq_prepost *wqp_post, *wqp_head, *wqp_tail;
assert(waitq_held(waitq) && waitq_held(&wqset->wqset_q));
if (wq_is_preposted_on_set(waitq, wqset))
return;
if (waitq->waitq_prepost_id == 0) {
struct wq_prepost *wqp;
wqp = wq_get_prepost_obj(reserved, WQP_WQ);
wqp->wqp_wq.wqp_wq_ptr = waitq;
wqp_set_valid(wqp);
waitq->waitq_prepost_id = wqp->wqp_prepostid.id;
wq_prepost_put(wqp);
}
#if CONFIG_WAITQ_STATS
g_prepost_table.npreposts += 1;
#endif
wqdbg_v("preposting waitq %p (0x%llx) to set 0x%llx",
(void *)VM_KERNEL_UNSLIDE_OR_PERM(waitq),
waitq->waitq_prepost_id, wqset->wqset_id);
if (wqset->wqset_prepost_id == 0) {
wqset->wqset_prepost_id = waitq->waitq_prepost_id;
return;
}
wqp_head = wq_prepost_get(wqset->wqset_prepost_id);
if (!wqp_head) {
wqset->wqset_prepost_id = waitq->waitq_prepost_id;
return;
}
assert(wqp_head->wqp_prepostid.id == wqset->wqset_prepost_id);
wqp_post = wq_get_prepost_obj(reserved, WQP_POST);
wqp_post->wqp_post.wqp_wq_id = waitq->waitq_prepost_id;
wqdbg_v("POST 0x%llx :: WQ 0x%llx", wqp_post->wqp_prepostid.id,
waitq->waitq_prepost_id);
if (wqp_type(wqp_head) == WQP_WQ) {
uint64_t wqp_id = wqp_head->wqp_prepostid.id;
wqdbg_v("set 0x%llx previous had 1 WQ prepost (0x%llx): "
"replacing with two POST preposts",
wqset->wqset_id, wqp_id);
wq_prepost_put(wqp_head);
wqp_head = wq_get_prepost_obj(reserved, WQP_POST);
wqp_head->wqp_post.wqp_wq_id = wqp_id;
wqdbg_v("POST 0x%llx :: WQ 0x%llx",
wqp_head->wqp_prepostid.id, wqp_id);
wqp_head->wqp_post.wqp_next_id = wqp_post->wqp_prepostid.id;
wq_prepost_rlink(wqp_head, wqp_post);
wqp_post->wqp_post.wqp_next_id = wqp_head->wqp_prepostid.id;
wq_prepost_rlink(wqp_post, wqp_head);
wqp_set_valid(wqp_head);
wqp_set_valid(wqp_post);
wqset->wqset_prepost_id = wqp_head->wqp_prepostid.id;
wq_prepost_put(wqp_head);
wq_prepost_put(wqp_post);
wqdbg_v("set 0x%llx: 0x%llx/0x%llx -> 0x%llx/0x%llx -> 0x%llx",
wqset->wqset_id, wqset->wqset_prepost_id,
wqp_head->wqp_prepostid.id, wqp_head->wqp_post.wqp_next_id,
wqp_post->wqp_prepostid.id,
wqp_post->wqp_post.wqp_next_id);
return;
}
assert(wqp_type(wqp_head) == WQP_POST);
wqp_tail = wq_prepost_get_rnext(wqp_head);
assert(wqp_tail != NULL);
assert(wqp_tail->wqp_post.wqp_next_id == wqset->wqset_prepost_id);
wq_prepost_reset_rnext(wqp_head);
wq_prepost_rlink(wqp_head, wqp_post);
wqp_post->wqp_post.wqp_next_id = wqp_head->wqp_prepostid.id;
wq_prepost_rlink(wqp_post, wqp_tail);
wqp_tail->wqp_post.wqp_next_id = wqp_post->wqp_prepostid.id;
wqp_set_valid(wqp_post);
wq_prepost_put(wqp_head);
wq_prepost_put(wqp_tail);
wq_prepost_put(wqp_post);
wqdbg_v("set 0x%llx (wqp:0x%llx) last_prepost:0x%llx, "
"new_prepost:0x%llx->0x%llx", wqset->wqset_id,
wqset->wqset_prepost_id, wqp_head->wqp_prepostid.id,
wqp_post->wqp_prepostid.id, wqp_post->wqp_post.wqp_next_id);
return;
}
#if CONFIG_WAITQ_STATS
static void wq_table_stats(struct wq_table *table, struct wq_table_stats *stats)
{
stats->version = WAITQ_STATS_VERSION;
stats->table_elements = table->nelem;
stats->table_used_elems = table->used_elem;
stats->table_elem_sz = table->elem_sz;
stats->table_slabs = table->nslabs;
stats->table_slab_sz = table->slab_sz;
stats->table_num_allocs = table->nallocs;
stats->table_num_preposts = table->npreposts;
stats->table_num_reservations = table->nreservations;
stats->table_max_used = table->max_used;
stats->table_avg_used = table->avg_used;
stats->table_max_reservations = table->max_reservations;
stats->table_avg_reservations = table->avg_reservations;
}
void waitq_link_stats(struct wq_table_stats *stats)
{
if (!stats)
return;
wq_table_stats(&g_linktable, stats);
}
void waitq_prepost_stats(struct wq_table_stats *stats)
{
wq_table_stats(&g_prepost_table, stats);
}
#endif
static struct waitq g_boot_waitq;
static struct waitq *global_waitqs = &g_boot_waitq;
static uint32_t g_num_waitqs = 1;
#define _CAST_TO_EVENT_MASK(event) ((uintptr_t)(event) & ((1ul << _EVENT_MASK_BITS) - 1ul))
static __inline__ uint32_t waitq_hash(char *key, size_t length)
{
uint32_t hash = 0;
size_t i;
for (i = 0; i < length; i++) {
hash += key[i];
hash += (hash << 10);
hash ^= (hash >> 6);
}
hash += (hash << 3);
hash ^= (hash >> 11);
hash += (hash << 15);
hash &= (g_num_waitqs - 1);
return hash;
}
struct waitq *_global_eventq(char *event, size_t event_length)
{
return &global_waitqs[waitq_hash(event, event_length)];
}
struct waitq *global_waitq(int index)
{
return &global_waitqs[index % g_num_waitqs];
}
#if CONFIG_WAITQ_STATS
const uint32_t g_nwaitq_btframes = NWAITQ_BTFRAMES;
struct wq_stats g_boot_stats;
struct wq_stats *g_waitq_stats = &g_boot_stats;
static __inline__ void waitq_grab_backtrace(uintptr_t bt[NWAITQ_BTFRAMES], int skip)
{
uintptr_t buf[NWAITQ_BTFRAMES + skip];
if (skip < 0)
skip = 0;
memset(buf, 0, (NWAITQ_BTFRAMES + skip) * sizeof(uintptr_t));
fastbacktrace(buf, g_nwaitq_btframes + skip);
memcpy(&bt[0], &buf[skip], NWAITQ_BTFRAMES * sizeof(uintptr_t));
}
static __inline__ struct wq_stats *waitq_global_stats(struct waitq *waitq) {
struct wq_stats *wqs;
uint32_t idx;
if (!waitq_is_global(waitq))
return NULL;
idx = (uint32_t)(((uintptr_t)waitq - (uintptr_t)global_waitqs) / sizeof(*waitq));
assert(idx < g_num_waitqs);
wqs = &g_waitq_stats[idx];
return wqs;
}
static __inline__ void waitq_stats_count_wait(struct waitq *waitq)
{
struct wq_stats *wqs = waitq_global_stats(waitq);
if (wqs != NULL) {
wqs->waits++;
waitq_grab_backtrace(wqs->last_wait, 2);
}
}
static __inline__ void waitq_stats_count_wakeup(struct waitq *waitq)
{
struct wq_stats *wqs = waitq_global_stats(waitq);
if (wqs != NULL) {
wqs->wakeups++;
waitq_grab_backtrace(wqs->last_wakeup, 2);
}
}
static __inline__ void waitq_stats_count_clear_wakeup(struct waitq *waitq)
{
struct wq_stats *wqs = waitq_global_stats(waitq);
if (wqs != NULL) {
wqs->wakeups++;
wqs->clears++;
waitq_grab_backtrace(wqs->last_wakeup, 2);
}
}
static __inline__ void waitq_stats_count_fail(struct waitq *waitq)
{
struct wq_stats *wqs = waitq_global_stats(waitq);
if (wqs != NULL) {
wqs->failed_wakeups++;
waitq_grab_backtrace(wqs->last_failed_wakeup, 2);
}
}
#else
#define waitq_stats_count_wait(q) do { } while (0)
#define waitq_stats_count_wakeup(q) do { } while (0)
#define waitq_stats_count_clear_wakeup(q) do { } while (0)
#define waitq_stats_count_fail(q) do { } while (0)
#endif
int waitq_is_valid(struct waitq *waitq)
{
return (waitq != NULL) && ((waitq->waitq_type & ~1) == WQT_QUEUE);
}
int waitq_set_is_valid(struct waitq_set *wqset)
{
return (wqset != NULL) && waitqs_is_set(wqset);
}
int waitq_is_global(struct waitq *waitq)
{
if (waitq >= global_waitqs && waitq < global_waitqs + g_num_waitqs)
return 1;
return 0;
}
int waitq_irq_safe(struct waitq *waitq)
{
return waitq->waitq_irq;
}
static uint32_t waitq_hash_size(void)
{
uint32_t hsize, queues;
if (PE_parse_boot_argn("wqsize", &hsize, sizeof(hsize)))
return (hsize);
queues = thread_max / 11;
hsize = P2ROUNDUP(queues * sizeof(struct waitq), PAGE_SIZE);
return hsize;
}
void waitq_bootstrap(void)
{
kern_return_t kret;
uint32_t whsize, qsz;
wq_table_bootstrap();
lt_init();
wqp_init();
whsize = waitq_hash_size();
qsz = sizeof(struct waitq);
whsize = ROUNDDOWN(whsize, qsz);
g_num_waitqs = whsize / qsz;
for (uint32_t i = 0; i < 31; i++) {
uint32_t bit = (1 << i);
if ((g_num_waitqs & bit) == g_num_waitqs)
break;
g_num_waitqs &= ~bit;
}
assert(g_num_waitqs > 0);
whsize = P2ROUNDUP(g_num_waitqs * qsz, PAGE_SIZE);
wqdbg("allocating %d global queues (%d bytes)", g_num_waitqs, whsize);
kret = kernel_memory_allocate(kernel_map, (vm_offset_t *)&global_waitqs,
whsize, 0, KMA_KOBJECT|KMA_NOPAGEWAIT, VM_KERN_MEMORY_WAITQ);
if (kret != KERN_SUCCESS || global_waitqs == NULL)
panic("kernel_memory_allocate() failed to alloc global_waitqs"
", error: %d, whsize: 0x%x", kret, whsize);
#if CONFIG_WAITQ_STATS
whsize = P2ROUNDUP(g_num_waitqs * sizeof(struct wq_stats), PAGE_SIZE);
kret = kernel_memory_allocate(kernel_map, (vm_offset_t *)&g_waitq_stats,
whsize, 0, KMA_KOBJECT|KMA_NOPAGEWAIT, VM_KERN_MEMORY_WAITQ);
if (kret != KERN_SUCCESS || global_waitqs == NULL)
panic("kernel_memory_allocate() failed to alloc g_waitq_stats"
", error: %d, whsize: 0x%x", kret, whsize);
memset(g_waitq_stats, 0, whsize);
#endif
for (uint32_t i = 0; i < g_num_waitqs; i++) {
waitq_init(&global_waitqs[i], SYNC_POLICY_FIFO|SYNC_POLICY_DISABLE_IRQ);
}
waitq_set_zone = zinit(sizeof(struct waitq_set),
WAITQ_SET_MAX * sizeof(struct waitq_set),
sizeof(struct waitq_set),
"waitq sets");
zone_change(waitq_set_zone, Z_NOENCRYPT, TRUE);
}
#if defined(__i386__) || defined(__x86_64__)
#define hwLockTimeOut LockTimeOutTSC
#else
#define hwLockTimeOut LockTimeOut
#endif
void waitq_lock(struct waitq *wq)
{
if (__improbable(hw_lock_to(&(wq)->waitq_interlock,
hwLockTimeOut * 2) == 0)) {
boolean_t wql_acquired = FALSE;
while (machine_timeout_suspended()) {
#if defined(__i386__) || defined(__x86_64__)
mp_enable_preemption();
#endif
wql_acquired = hw_lock_to(&(wq)->waitq_interlock,
hwLockTimeOut * 2);
if (wql_acquired)
break;
}
if (wql_acquired == FALSE)
panic("waitq deadlock - waitq=%p, cpu=%d\n",
wq, cpu_number());
}
assert(waitq_held(wq));
}
void waitq_unlock(struct waitq *wq)
{
assert(waitq_held(wq));
hw_lock_unlock(&(wq)->waitq_interlock);
}
static inline void thread_clear_waitq_state(thread_t thread)
{
thread->waitq = NULL;
thread->wait_event = NO_EVENT64;
thread->at_safe_point = FALSE;
}
typedef thread_t (*waitq_select_cb)(void *ctx, struct waitq *waitq,
int is_global, thread_t thread);
struct waitq_select_args {
struct waitq *posted_waitq;
struct waitq *waitq;
event64_t event;
waitq_select_cb select_cb;
void *select_ctx;
uint64_t *reserved_preposts;
queue_t threadq;
int max_threads;
int *nthreads;
spl_t *spl;
};
static void do_waitq_select_n_locked(struct waitq_select_args *args);
static int waitq_select_walk_cb(struct waitq *waitq, void *ctx,
struct setid_link *link)
{
int ret = WQ_ITERATE_CONTINUE;
struct waitq_select_args args = *((struct waitq_select_args *)ctx);
struct waitq_set *wqset;
int get_spl = 0;
spl_t set_spl;
(void)waitq;
assert(sl_type(link) == SLT_WQS);
wqset = link->sl_wqs.sl_set;
args.waitq = &wqset->wqset_q;
if (!waitq_irq_safe(waitq) && waitq_irq_safe(&wqset->wqset_q)) {
get_spl = 1;
set_spl = splsched();
}
waitq_set_lock(wqset);
if (wqset->wqset_id != link->sl_set_id.id)
goto out_unlock;
do_waitq_select_n_locked(&args);
if (*(args.nthreads) > 0 ||
(args.threadq && !queue_empty(args.threadq))) {
if (args.max_threads > 0 &&
*(args.nthreads) >= args.max_threads) {
ret = WQ_ITERATE_FOUND;
}
goto out_unlock;
} else {
if (args.event == NO_EVENT64 && waitq_set_can_prepost(wqset)) {
wq_prepost_do_post_locked(wqset, waitq,
args.reserved_preposts);
}
}
out_unlock:
waitq_set_unlock(wqset);
if (get_spl)
splx(set_spl);
return ret;
}
static void do_waitq_select_n_locked(struct waitq_select_args *args)
{
struct waitq *waitq = args->waitq;
int max_threads = args->max_threads;
thread_t thread = THREAD_NULL, first_thread = THREAD_NULL;
int global_q = 0;
unsigned long eventmask = 0;
int *nthreads = args->nthreads;
assert(max_threads != 0);
global_q = waitq_is_global(waitq);
if (global_q) {
eventmask = _CAST_TO_EVENT_MASK(args->event);
if ((waitq->waitq_eventmask & eventmask) != eventmask)
return;
eventmask = 0;
}
qe_foreach_element_safe(thread, &waitq->waitq_queue, links) {
thread_t t = THREAD_NULL;
assert(thread->waitq == waitq);
if (thread->wait_event == args->event) {
t = thread;
if (first_thread == THREAD_NULL)
first_thread = thread;
if (args->select_cb)
t = args->select_cb(args->select_ctx, waitq,
global_q, thread);
if (t != THREAD_NULL) {
*nthreads += 1;
if (args->threadq) {
if (*nthreads == 1)
*(args->spl) = splsched();
thread_lock(t);
thread_clear_waitq_state(t);
re_queue_tail(args->threadq, &t->links);
}
if (*nthreads >= max_threads && max_threads > 0)
break;
}
}
if (t == THREAD_NULL && global_q)
eventmask |= _CAST_TO_EVENT_MASK(thread->wait_event);
}
if (global_q && (queue_empty(&waitq->waitq_queue) || *nthreads == 0))
waitq->waitq_eventmask = (typeof(waitq->waitq_eventmask))eventmask;
if (*nthreads == 0 && first_thread != THREAD_NULL && args->threadq) {
++(*nthreads);
*(args->spl) = splsched();
thread_lock(first_thread);
thread_clear_waitq_state(first_thread);
re_queue_tail(args->threadq, &first_thread->links);
if (global_q && queue_empty(&waitq->waitq_queue))
waitq->waitq_eventmask = 0;
}
if (max_threads > 0 && *nthreads >= max_threads)
return;
if (!waitq->waitq_set_id)
return;
struct setid_link *link = lt_get_link(waitq->waitq_set_id);
if (!link) {
waitq->waitq_set_id = 0;
return;
}
lt_put_link(link);
(void)walk_setid_links(LINK_WALK_ONE_LEVEL, waitq, waitq->waitq_set_id,
SLT_WQS, (void *)args, waitq_select_walk_cb);
}
static __inline__ int waitq_select_n_locked(struct waitq *waitq,
event64_t event,
waitq_select_cb select_cb,
void *select_ctx,
uint64_t *reserved_preposts,
queue_t threadq,
int max_threads, spl_t *spl)
{
int nthreads = 0;
struct waitq_select_args args = {
.posted_waitq = waitq,
.waitq = waitq,
.event = event,
.select_cb = select_cb,
.select_ctx = select_ctx,
.reserved_preposts = reserved_preposts,
.threadq = threadq,
.max_threads = max_threads,
.nthreads = &nthreads,
.spl = spl,
};
do_waitq_select_n_locked(&args);
return nthreads;
}
static thread_t waitq_select_one_cb(void *ctx, struct waitq *waitq,
int is_global, thread_t thread)
{
int fifo_q, realtime;
boolean_t thread_imp_donor = FALSE;
(void)ctx;
(void)waitq;
(void)is_global;
realtime = 0;
fifo_q = 1;
#if IMPORTANCE_INHERITANCE
if (is_global)
fifo_q = 0;
#endif
if (thread->sched_pri >= BASEPRI_REALTIME)
realtime = 1;
#if IMPORTANCE_INHERITANCE
thread_imp_donor = task_is_importance_donor(thread->task);
#endif
if (fifo_q || thread_imp_donor == TRUE
|| realtime || (thread->options & TH_OPT_VMPRIV)) {
return thread;
}
return THREAD_NULL;
}
static thread_t waitq_select_one_locked(struct waitq *waitq, event64_t event,
uint64_t *reserved_preposts,
int priority, spl_t *spl)
{
int nthreads;
queue_head_t threadq;
(void)priority;
queue_init(&threadq);
nthreads = waitq_select_n_locked(waitq, event, waitq_select_one_cb, NULL,
reserved_preposts, &threadq, 1, spl);
if (!queue_empty(&threadq)) {
thread_t t;
queue_entry_t qe = dequeue_head(&threadq);
t = qe_element(qe, struct thread, links);
assert(queue_empty(&threadq));
return t;
}
return THREAD_NULL;
}
struct select_thread_ctx {
thread_t thread;
event64_t event;
spl_t *spl;
};
static int waitq_select_thread_cb(struct waitq *waitq, void *ctx,
struct setid_link *link)
{
struct select_thread_ctx *stctx = (struct select_thread_ctx *)ctx;
struct waitq_set *wqset;
(void)waitq;
thread_t thread = stctx->thread;
event64_t event = stctx->event;
if (sl_type(link) != SLT_WQS)
return WQ_ITERATE_CONTINUE;
wqset = link->sl_wqs.sl_set;
if (!waitq_irq_safe(waitq) && waitq_irq_safe(&wqset->wqset_q)) {
*(stctx->spl) = splsched();
waitq_set_lock(wqset);
thread_lock(thread);
} else {
waitq_set_lock(wqset);
*(stctx->spl) = splsched();
thread_lock(thread);
}
if ((thread->waitq == &wqset->wqset_q)
&& (thread->wait_event == event)) {
remqueue(&thread->links);
thread_clear_waitq_state(thread);
waitq_set_unlock(wqset);
return WQ_ITERATE_FOUND;
}
thread_unlock(thread);
waitq_set_unlock(wqset);
splx(*(stctx->spl));
return WQ_ITERATE_CONTINUE;
}
static kern_return_t waitq_select_thread_locked(struct waitq *waitq,
event64_t event,
thread_t thread, spl_t *spl)
{
struct setid_link *link;
struct select_thread_ctx ctx;
kern_return_t kr;
*spl = splsched();
thread_lock(thread);
if ((thread->waitq == waitq) && (thread->wait_event == event)) {
remqueue(&thread->links);
thread_clear_waitq_state(thread);
return KERN_SUCCESS;
}
thread_unlock(thread);
splx(*spl);
if (!waitq->waitq_set_id)
return KERN_NOT_WAITING;
link = lt_get_link(waitq->waitq_set_id);
if (!link) {
waitq->waitq_set_id = 0;
return KERN_NOT_WAITING;
}
ctx.thread = thread;
ctx.event = event;
ctx.spl = spl;
kr = walk_setid_links(LINK_WALK_FULL_DAG, waitq, waitq->waitq_set_id,
SLT_WQS, (void *)&ctx, waitq_select_thread_cb);
lt_put_link(link);
if (kr == WQ_ITERATE_FOUND)
return KERN_SUCCESS;
return KERN_NOT_WAITING;
}
static int prepost_exists_cb(struct waitq_set __unused *wqset,
void __unused *ctx,
struct wq_prepost __unused *wqp,
struct waitq __unused *waitq)
{
return WQ_ITERATE_FOUND;
}
wait_result_t waitq_assert_wait64_locked(struct waitq *waitq,
event64_t wait_event,
wait_interrupt_t interruptible,
wait_timeout_urgency_t urgency,
uint64_t deadline,
uint64_t leeway,
thread_t thread)
{
wait_result_t wait_result;
int realtime = 0;
if (thread->waitq != NULL)
panic("thread already waiting on %p", thread->waitq);
if (waitq_is_set(waitq)) {
struct waitq_set *wqset = (struct waitq_set *)waitq;
if (wait_event == NO_EVENT64 && waitq_set_maybe_preposted(wqset)) {
int ret;
ret = wq_prepost_foreach_locked(wqset, NULL,
prepost_exists_cb);
if (ret == WQ_ITERATE_FOUND) {
thread->wait_result = THREAD_AWAKENED;
return THREAD_AWAKENED;
}
}
}
if (thread->sched_pri >= BASEPRI_REALTIME)
realtime = 1;
wait_result = thread_mark_wait_locked(thread, interruptible);
if (wait_result == THREAD_WAITING) {
if (!waitq->waitq_fifo
|| (thread->options & TH_OPT_VMPRIV) || realtime)
enqueue_head(&waitq->waitq_queue, &thread->links);
else
enqueue_tail(&waitq->waitq_queue, &thread->links);
thread->wait_event = wait_event;
thread->waitq = waitq;
if (deadline != 0) {
boolean_t act;
act = timer_call_enter_with_leeway(&thread->wait_timer,
NULL,
deadline, leeway,
urgency, FALSE);
if (!act)
thread->wait_timer_active++;
thread->wait_timer_is_set = TRUE;
}
if (waitq_is_global(waitq))
waitq->waitq_eventmask = waitq->waitq_eventmask
| _CAST_TO_EVENT_MASK(wait_event);
waitq_stats_count_wait(waitq);
}
return wait_result;
}
void waitq_pull_thread_locked(struct waitq *waitq, thread_t thread)
{
(void)waitq;
assert(thread->waitq == waitq);
remqueue(&thread->links);
thread_clear_waitq_state(thread);
waitq_stats_count_clear_wakeup(waitq);
if (waitq_is_global(waitq) && queue_empty(&waitq->waitq_queue))
waitq->waitq_eventmask = 0;
}
static __inline__
void maybe_adjust_thread_pri(thread_t thread, int priority) {
if (thread->sched_pri < priority) {
if (priority <= MAXPRI) {
set_sched_pri(thread, priority);
thread->was_promoted_on_wakeup = 1;
thread->sched_flags |= TH_SFLAG_PROMOTED;
}
return;
}
if (priority == WAITQ_PROMOTE_PRIORITY &&
(thread->sched_pri < WAITQ_BOOST_PRIORITY ||
!(thread->sched_flags & TH_SFLAG_WAITQ_PROMOTED))) {
KERNEL_DEBUG_CONSTANT(MACHDBG_CODE(DBG_MACH_SCHED, MACH_WAITQ_PROMOTE) | DBG_FUNC_NONE,
(uintptr_t)thread_tid(thread),
thread->sched_pri, thread->base_pri,
WAITQ_BOOST_PRIORITY, 0);
thread->sched_flags |= TH_SFLAG_WAITQ_PROMOTED;
if (thread->sched_pri < WAITQ_BOOST_PRIORITY)
set_sched_pri(thread, WAITQ_BOOST_PRIORITY);
}
}
void waitq_clear_promotion_locked(struct waitq *waitq, thread_t thread)
{
spl_t s;
assert(waitq_held(waitq));
if (thread == THREAD_NULL)
return;
if (!waitq_irq_safe(waitq))
s = splsched();
thread_lock(thread);
if (thread->sched_flags & TH_SFLAG_WAITQ_PROMOTED) {
thread->sched_flags &= ~TH_SFLAG_WAITQ_PROMOTED;
if (thread->sched_flags & TH_SFLAG_PROMOTED_MASK) {
} else if (thread->sched_flags & TH_SFLAG_DEPRESSED_MASK) {
KERNEL_DEBUG_CONSTANT(MACHDBG_CODE(DBG_MACH_SCHED, MACH_WAITQ_DEMOTE) | DBG_FUNC_NONE,
(uintptr_t)thread_tid(thread),
thread->sched_pri,
thread->base_pri,
DEPRESSPRI, 0);
set_sched_pri(thread, DEPRESSPRI);
} else {
KERNEL_DEBUG_CONSTANT(MACHDBG_CODE(DBG_MACH_SCHED, MACH_WAITQ_DEMOTE) | DBG_FUNC_NONE,
(uintptr_t)thread_tid(thread),
thread->sched_pri,
thread->base_pri,
thread->base_pri, 0);
thread_recompute_sched_pri(thread, FALSE);
}
}
thread_unlock(thread);
if (!waitq_irq_safe(waitq))
splx(s);
}
kern_return_t waitq_wakeup64_all_locked(struct waitq *waitq,
event64_t wake_event,
wait_result_t result,
uint64_t *reserved_preposts,
int priority,
waitq_lock_state_t lock_state)
{
kern_return_t ret;
thread_t thread;
spl_t th_spl;
int nthreads;
queue_head_t wakeup_queue;
assert(waitq_held(waitq));
queue_init(&wakeup_queue);
nthreads = waitq_select_n_locked(waitq, wake_event, NULL, NULL,
reserved_preposts,
&wakeup_queue, -1, &th_spl);
ret = KERN_NOT_WAITING;
#if CONFIG_WAITQ_STATS
qe_foreach_element(thread, &wakeup_queue, links)
waitq_stats_count_wakeup(waitq);
#endif
if (lock_state == WAITQ_UNLOCK)
waitq_unlock(waitq);
qe_foreach_element_safe(thread, &wakeup_queue, links) {
remqueue(&thread->links);
maybe_adjust_thread_pri(thread, priority);
ret = thread_go(thread, result);
assert(ret == KERN_SUCCESS);
thread_unlock(thread);
}
if (nthreads > 0)
splx(th_spl);
else
waitq_stats_count_fail(waitq);
return ret;
}
kern_return_t waitq_wakeup64_one_locked(struct waitq *waitq,
event64_t wake_event,
wait_result_t result,
uint64_t *reserved_preposts,
int priority,
waitq_lock_state_t lock_state)
{
thread_t thread;
spl_t th_spl;
assert(waitq_held(waitq));
thread = waitq_select_one_locked(waitq, wake_event,
reserved_preposts,
priority, &th_spl);
if (thread != THREAD_NULL)
waitq_stats_count_wakeup(waitq);
else
waitq_stats_count_fail(waitq);
if (lock_state == WAITQ_UNLOCK)
waitq_unlock(waitq);
if (thread != THREAD_NULL) {
maybe_adjust_thread_pri(thread, priority);
kern_return_t ret = thread_go(thread, result);
assert(ret == KERN_SUCCESS);
thread_unlock(thread);
splx(th_spl);
return ret;
}
return KERN_NOT_WAITING;
}
thread_t waitq_wakeup64_identity_locked(struct waitq *waitq,
event64_t wake_event,
wait_result_t result,
spl_t *spl,
uint64_t *reserved_preposts,
waitq_lock_state_t lock_state)
{
thread_t thread;
assert(waitq_held(waitq));
thread = waitq_select_one_locked(waitq, wake_event,
reserved_preposts,
WAITQ_ALL_PRIORITIES, spl);
if (thread != THREAD_NULL)
waitq_stats_count_wakeup(waitq);
else
waitq_stats_count_fail(waitq);
if (lock_state == WAITQ_UNLOCK)
waitq_unlock(waitq);
if (thread != THREAD_NULL) {
kern_return_t __assert_only ret;
ret = thread_go(thread, result);
assert(ret == KERN_SUCCESS);
}
return thread;
}
kern_return_t waitq_wakeup64_thread_locked(struct waitq *waitq,
event64_t wake_event,
thread_t thread,
wait_result_t result,
waitq_lock_state_t lock_state)
{
kern_return_t ret;
spl_t th_spl;
assert(waitq_held(waitq));
ret = waitq_select_thread_locked(waitq, wake_event, thread, &th_spl);
if (ret == KERN_SUCCESS)
waitq_stats_count_wakeup(waitq);
else
waitq_stats_count_fail(waitq);
if (lock_state == WAITQ_UNLOCK)
waitq_unlock(waitq);
if (ret != KERN_SUCCESS)
return KERN_NOT_WAITING;
ret = thread_go(thread, result);
assert(ret == KERN_SUCCESS);
thread_unlock(thread);
splx(th_spl);
return ret;
}
kern_return_t waitq_init(struct waitq *waitq, int policy)
{
assert(waitq != NULL);
if ((policy & SYNC_POLICY_FIXED_PRIORITY) != 0)
return KERN_INVALID_ARGUMENT;
waitq->waitq_fifo = ((policy & SYNC_POLICY_REVERSED) == 0);
waitq->waitq_irq = !!(policy & SYNC_POLICY_DISABLE_IRQ);
waitq->waitq_prepost = 0;
waitq->waitq_type = WQT_QUEUE;
waitq->waitq_eventmask = 0;
waitq->waitq_set_id = 0;
waitq->waitq_prepost_id = 0;
hw_lock_init(&waitq->waitq_interlock);
queue_init(&waitq->waitq_queue);
return KERN_SUCCESS;
}
struct wq_unlink_ctx {
struct waitq *unlink_wq;
struct waitq_set *unlink_wqset;
};
static int waitq_unlink_prepost_cb(struct waitq_set __unused *wqset, void *ctx,
struct wq_prepost *wqp, struct waitq *waitq);
static int waitq_unlink_all_cb(struct waitq *waitq, void *ctx,
struct setid_link *link)
{
(void)waitq;
(void)ctx;
if (sl_type(link) == SLT_LINK && sl_is_valid(link))
lt_invalidate(link);
if (sl_type(link) == SLT_WQS) {
struct waitq_set *wqset;
int do_spl = 0;
spl_t spl;
struct wq_unlink_ctx ulctx;
if (waitq->waitq_prepost_id == 0)
goto out;
wqset = link->sl_wqs.sl_set;
assert(wqset != NULL);
if (waitq_set_is_valid(wqset) &&
waitq_irq_safe(&wqset->wqset_q)) {
spl = splsched();
do_spl = 1;
}
waitq_set_lock(wqset);
if (!waitq_set_is_valid(wqset)) {
goto out_unlock;
}
if (!waitq_set_maybe_preposted(wqset))
goto out_unlock;
ulctx.unlink_wq = waitq;
ulctx.unlink_wqset = wqset;
(void)wq_prepost_iterate(wqset->wqset_prepost_id, &ulctx,
waitq_unlink_prepost_cb);
out_unlock:
waitq_set_unlock(wqset);
if (do_spl)
splx(spl);
}
out:
return WQ_ITERATE_CONTINUE;
}
void waitq_deinit(struct waitq *waitq)
{
uint64_t setid = 0;
spl_t s;
if (!waitq_valid(waitq))
return;
if (waitq_irq_safe(waitq))
s = splsched();
waitq_lock(waitq);
if (!waitq_valid(waitq))
goto out;
waitq_unlink_all_locked(waitq, &setid, &s, NULL);
waitq->waitq_type = WQT_INVALID;
assert(queue_empty(&waitq->waitq_queue));
out:
waitq_unlock(waitq);
if (waitq_irq_safe(waitq))
splx(s);
if (setid)
(void)walk_setid_links(LINK_WALK_ONE_LEVEL, waitq, setid,
SLT_ALL, NULL, waitq_unlink_all_cb);
}
static int wqset_clear_prepost_chain_cb(struct waitq_set __unused *wqset,
void __unused *ctx,
struct wq_prepost *wqp,
struct waitq __unused *waitq)
{
if (wqp_type(wqp) == WQP_POST)
wq_prepost_invalidate(wqp);
return WQ_ITERATE_CONTINUE;
}
struct waitq_set *waitq_set_alloc(int policy)
{
struct waitq_set *wqset;
wqset = (struct waitq_set *)zalloc(waitq_set_zone);
if (!wqset)
panic("Can't allocate a new waitq set from zone %p", waitq_set_zone);
kern_return_t ret;
ret = waitq_set_init(wqset, policy, NULL);
if (ret != KERN_SUCCESS) {
zfree(waitq_set_zone, wqset);
wqset = NULL;
}
return wqset;
}
kern_return_t waitq_set_init(struct waitq_set *wqset,
int policy, uint64_t *reserved_link)
{
struct setid_link *link;
kern_return_t ret;
memset(wqset, 0, sizeof(*wqset));
ret = waitq_init(&wqset->wqset_q, policy);
if (ret != KERN_SUCCESS)
return ret;
wqset->wqset_q.waitq_type = WQT_SET;
if (policy & SYNC_POLICY_PREPOST)
wqset->wqset_q.waitq_prepost = 1;
else
wqset->wqset_q.waitq_prepost = 0;
if (reserved_link && *reserved_link != 0) {
link = lt_get_reserved(*reserved_link, SLT_WQS);
*reserved_link = 0;
} else {
link = lt_alloc_link(SLT_WQS);
}
if (!link)
panic("Can't allocate link object for waitq set: %p", wqset);
link->sl_wqs.sl_set = wqset;
sl_set_valid(link);
wqset->wqset_id = link->sl_set_id.id;
wqset->wqset_prepost_id = 0;
lt_put_link(link);
return KERN_SUCCESS;
}
void waitq_set_deinit(struct waitq_set *wqset)
{
struct setid_link *link = NULL;
uint64_t set_id, set_links_id, prepost_id;
int do_spl = 0;
spl_t s;
if (!waitqs_is_set(wqset))
panic("trying to de-initialize an invalid wqset @%p", wqset);
if (waitq_irq_safe(&wqset->wqset_q)) {
s = splsched();
do_spl = 1;
}
waitq_set_lock(wqset);
set_id = wqset->wqset_id;
link = lt_get_link(set_id);
if (link)
lt_invalidate(link);
if (!link || wqset->wqset_id != set_id || set_id != link->sl_set_id.id) {
if (link)
lt_put_link(link);
waitq_set_unlock(wqset);
if (do_spl)
splx(s);
return;
}
assert(link != NULL && sl_type(link) == SLT_WQS);
wqset->wqset_id = 0;
wqset->wqset_q.waitq_type = WQT_INVALID;
wqset->wqset_q.waitq_fifo = 0;
wqset->wqset_q.waitq_prepost = 0;
wqset->wqset_q.waitq_eventmask = 0;
prepost_id = wqset->wqset_prepost_id;
wqset->wqset_prepost_id = 0;
set_links_id = 0;
waitq_unlink_all_locked(&wqset->wqset_q, &set_links_id, &s, NULL);
waitq_set_unlock(wqset);
if (do_spl)
splx(s);
while (sl_refcnt(link) > 1)
delay(1);
lt_put_link(link);
if (set_links_id)
(void)walk_setid_links(LINK_WALK_ONE_LEVEL, NULL, set_links_id,
SLT_ALL, NULL, waitq_unlink_all_cb);
(void)wq_prepost_iterate(prepost_id, NULL, wqset_clear_prepost_chain_cb);
}
kern_return_t waitq_set_free(struct waitq_set *wqset)
{
waitq_set_deinit(wqset);
memset(wqset, 0, sizeof(*wqset));
zfree(waitq_set_zone, wqset);
return KERN_SUCCESS;
}
#if defined(DEVLEOPMENT) || defined(DEBUG)
#if CONFIG_WAITQ_DEBUG
uint64_t wqset_id(struct waitq_set *wqset)
{
if (!wqset)
return 0;
assert(waitqs_is_set(wqset));
return wqset->wqset_id;
}
struct waitq *wqset_waitq(struct waitq_set *wqset)
{
if (!wqset)
return NULL;
assert(waitqs_is_set(wqset));
return &wqset->wqset_q;
}
#endif
#endif
int waitq_clear_prepost_locked(struct waitq *waitq, spl_t *s)
{
struct wq_prepost *wqp;
int dropped_lock = 0;
if (waitq->waitq_prepost_id == 0)
return 0;
wqp = wq_prepost_get(waitq->waitq_prepost_id);
waitq->waitq_prepost_id = 0;
if (wqp) {
uint64_t wqp_id = wqp->wqp_prepostid.id;
wqdbg_v("invalidate prepost 0x%llx (refcnt:%d)",
wqp->wqp_prepostid.id, wqp_refcnt(wqp));
wq_prepost_invalidate(wqp);
while (wqp_refcnt(wqp) > 1) {
int do_spl = waitq_irq_safe(waitq);
disable_preemption();
waitq_unlock(waitq);
if (s && do_spl)
splx(*s);
dropped_lock = 1;
delay(1);
if (s && do_spl)
*s = splsched();
waitq_lock(waitq);
enable_preemption();
}
if (wqp_refcnt(wqp) > 0 && wqp->wqp_prepostid.id == wqp_id)
wq_prepost_put(wqp);
}
return dropped_lock;
}
void waitq_clear_prepost(struct waitq *waitq)
{
spl_t s;
int do_spl = waitq_irq_safe(waitq);
assert(waitq_valid(waitq));
if (do_spl)
s = splsched();
waitq_lock(waitq);
(void)waitq_clear_prepost_locked(waitq, &s);
waitq_unlock(waitq);
if (do_spl)
splx(s);
}
uint64_t waitq_get_prepost_id(struct waitq *waitq)
{
struct wq_prepost *wqp;
uint64_t wqp_id = 0;
spl_t s;
if (!waitq_valid(waitq))
return 0;
if (waitq_irq_safe(waitq))
s = splsched();
waitq_lock(waitq);
if (!waitq_valid(waitq))
goto out_unlock;
if (waitq->waitq_prepost_id) {
wqp_id = waitq->waitq_prepost_id;
goto out_unlock;
}
waitq_unlock(waitq);
if (waitq_irq_safe(waitq))
splx(s);
wqp = wq_prepost_alloc(WQP_WQ, 1);
if (!wqp)
return 0;
if (waitq_irq_safe(waitq))
s = splsched();
waitq_lock(waitq);
if (!waitq_valid(waitq)) {
wq_prepost_put(wqp);
wqp_id = 0;
goto out_unlock;
}
if (waitq->waitq_prepost_id) {
wq_prepost_put(wqp);
wqp_id = waitq->waitq_prepost_id;
goto out_unlock;
}
wqp->wqp_wq.wqp_wq_ptr = waitq;
wqp_set_valid(wqp);
wqp_id = wqp->wqp_prepostid.id;
waitq->waitq_prepost_id = wqp_id;
wq_prepost_put(wqp);
out_unlock:
waitq_unlock(waitq);
if (waitq_irq_safe(waitq))
splx(s);
return wqp_id;
}
static int waitq_inset_cb(struct waitq *waitq, void *ctx, struct setid_link *link)
{
uint64_t setid = *(uint64_t *)ctx;
int ltype = sl_type(link);
(void)waitq;
if (ltype == SLT_WQS && link->sl_set_id.id == setid) {
wqdbg_v(" waitq already in set 0x%llx", setid);
return WQ_ITERATE_FOUND;
} else if (ltype == SLT_LINK) {
wqdbg_v(" waitq already in set 0x%llx (SLT_LINK)", setid);
if (link->sl_link.sl_left_setid == setid ||
link->sl_link.sl_right_setid == setid)
return WQ_ITERATE_FOUND;
}
return WQ_ITERATE_CONTINUE;
}
boolean_t waitq_member(struct waitq *waitq, struct waitq_set *wqset)
{
kern_return_t kr = WQ_ITERATE_SUCCESS;
uint64_t setid;
spl_t s;
if (!waitq_valid(waitq))
panic("Invalid waitq: %p", waitq);
if (!waitqs_is_set(wqset))
return FALSE;
if (waitq_irq_safe(waitq))
s = splsched();
waitq_lock(waitq);
setid = wqset->wqset_id;
if (!setid)
goto out_unlock;
if (waitq->waitq_set_id == setid) {
waitq_unlock(waitq);
if (waitq_irq_safe(waitq))
splx(s);
return TRUE;
}
kr = walk_setid_links(LINK_WALK_ONE_LEVEL, waitq, waitq->waitq_set_id,
SLT_ALL, (void *)&setid, waitq_inset_cb);
out_unlock:
waitq_unlock(waitq);
if (waitq_irq_safe(waitq))
splx(s);
if (kr == WQ_ITERATE_FOUND)
return TRUE;
return FALSE;
}
boolean_t waitq_in_set(struct waitq *waitq)
{
struct setid_link *link;
boolean_t inset = FALSE;
spl_t s;
if (waitq_irq_safe(waitq))
s = splsched();
waitq_lock(waitq);
if (!waitq->waitq_set_id)
goto out_unlock;
link = lt_get_link(waitq->waitq_set_id);
if (link) {
inset = TRUE;
lt_put_link(link);
} else {
waitq->waitq_set_id = 0;
}
out_unlock:
waitq_unlock(waitq);
if (waitq_irq_safe(waitq))
splx(s);
return inset;
}
uint64_t waitq_link_reserve(struct waitq *waitq)
{
struct setid_link *link;
uint64_t reserved_id = 0;
assert(get_preemption_level() == 0 && waitq_wait_possible(current_thread()));
lt_ensure_free_space();
(void)waitq;
link = lt_alloc_link(WQT_RESERVED);
if (!link)
return 0;
reserved_id = link->sl_set_id.id;
return reserved_id;
}
void waitq_link_release(uint64_t id)
{
struct setid_link *link;
if (id == 0)
return;
link = lt_get_reserved(id, SLT_LINK);
if (!link)
return;
lt_put_link(link);
#if CONFIG_WAITQ_STATS
g_linktable.nreserved_releases += 1;
#endif
}
static kern_return_t waitq_link_internal(struct waitq *waitq,
uint64_t setid, struct setid_link *link)
{
struct setid_link *qlink;
kern_return_t kr;
assert(waitq_held(waitq));
if (!waitq->waitq_set_id) {
waitq->waitq_set_id = setid;
return KERN_SUCCESS;
}
qlink = lt_get_link(waitq->waitq_set_id);
if (!qlink) {
waitq->waitq_set_id = setid;
return KERN_SUCCESS;
}
lt_put_link(qlink);
kr = walk_setid_links(LINK_WALK_ONE_LEVEL, waitq, waitq->waitq_set_id,
SLT_ALL, (void *)&setid, waitq_inset_cb);
if (kr == WQ_ITERATE_FOUND)
return kr;
link->sl_link.sl_left_setid = setid;
link->sl_link.sl_right_setid = waitq->waitq_set_id;
sl_set_valid(link);
waitq->waitq_set_id = link->sl_set_id.id;
return KERN_SUCCESS;
}
kern_return_t waitq_link(struct waitq *waitq, struct waitq_set *wqset,
waitq_lock_state_t lock_state, uint64_t *reserved_link)
{
kern_return_t kr;
struct setid_link *link;
int should_lock = (lock_state == WAITQ_SHOULD_LOCK);
spl_t s;
if (!waitq_valid(waitq))
panic("Invalid waitq: %p", waitq);
if (!waitqs_is_set(wqset))
return KERN_INVALID_ARGUMENT;
wqdbg_v("Link waitq %p to wqset 0x%llx",
(void *)VM_KERNEL_UNSLIDE_OR_PERM(waitq), wqset->wqset_id);
if (waitq_irq_safe(waitq) && (!reserved_link || *reserved_link == 0)) {
panic("Global/IRQ-safe waitq %p cannot link to %p without"
"reserved object!", waitq, wqset);
}
if (reserved_link && *reserved_link != 0) {
link = lt_get_reserved(*reserved_link, SLT_LINK);
*reserved_link = 0;
} else {
link = lt_alloc_link(SLT_LINK);
}
if (!link)
return KERN_NO_SPACE;
if (should_lock) {
if (waitq_irq_safe(waitq))
s = splsched();
waitq_lock(waitq);
}
kr = waitq_link_internal(waitq, wqset->wqset_id, link);
if (should_lock) {
waitq_unlock(waitq);
if (waitq_irq_safe(waitq))
splx(s);
}
lt_put_link(link);
return kr;
}
static inline int waitq_maybe_remove_link(struct waitq *waitq,
uint64_t setid,
struct setid_link *parent,
struct setid_link *left,
struct setid_link *right)
{
uint64_t *wq_setid = &waitq->waitq_set_id;
if (*wq_setid == parent->sl_set_id.id) {
if (!left && !right) {
lt_invalidate(parent);
wqdbg_v("S1, L+R");
*wq_setid = 0;
return WQ_ITERATE_INVALID;
} else if (!left || left->sl_set_id.id == setid) {
*wq_setid = right ? right->sl_set_id.id : 0;
lt_invalidate(parent);
wqdbg_v("S1, L");
return left ? WQ_ITERATE_UNLINKED : WQ_ITERATE_INVALID;
} else if (!right || right->sl_set_id.id == setid) {
*wq_setid = left ? left->sl_set_id.id : 0;
lt_invalidate(parent);
wqdbg_v("S1, R");
return right ? WQ_ITERATE_UNLINKED : WQ_ITERATE_INVALID;
}
}
assert(left || right);
if (left && sl_type(left) == SLT_LINK) {
uint64_t Ll, Lr;
struct setid_link *linkLl, *linkLr;
assert(left->sl_set_id.id != setid);
Ll = left->sl_link.sl_left_setid;
Lr = left->sl_link.sl_right_setid;
linkLl = lt_get_link(Ll);
linkLr = lt_get_link(Lr);
if (!linkLl && !linkLr) {
lt_invalidate(left);
wqdbg_v("S2, Ll+Lr");
return WQ_ITERATE_INVALID;
} else if (!linkLl || Ll == setid) {
parent->sl_link.sl_left_setid = Lr;
lt_invalidate(left);
lt_put_link(linkLl);
lt_put_link(linkLr);
wqdbg_v("S2, Ll");
return linkLl ? WQ_ITERATE_UNLINKED : WQ_ITERATE_INVALID;
} else if (!linkLr || Lr == setid) {
parent->sl_link.sl_left_setid = Ll;
lt_invalidate(left);
lt_put_link(linkLr);
lt_put_link(linkLl);
wqdbg_v("S2, Lr");
return linkLr ? WQ_ITERATE_UNLINKED : WQ_ITERATE_INVALID;
}
lt_put_link(linkLl);
lt_put_link(linkLr);
}
if (right && sl_type(right) == SLT_LINK) {
uint64_t Rl, Rr;
struct setid_link *linkRl, *linkRr;
assert(right->sl_set_id.id != setid);
Rl = right->sl_link.sl_left_setid;
Rr = right->sl_link.sl_right_setid;
linkRl = lt_get_link(Rl);
linkRr = lt_get_link(Rr);
if (!linkRl && !linkRr) {
lt_invalidate(right);
wqdbg_v("S2, Rl+Rr");
return WQ_ITERATE_INVALID;
} else if (!linkRl || Rl == setid) {
parent->sl_link.sl_right_setid = Rr;
lt_invalidate(right);
lt_put_link(linkRl);
lt_put_link(linkRr);
wqdbg_v("S2, Rl");
return linkRl ? WQ_ITERATE_UNLINKED : WQ_ITERATE_INVALID;
} else if (!linkRr || Rr == setid) {
parent->sl_link.sl_right_setid = Rl;
lt_invalidate(right);
lt_put_link(linkRl);
lt_put_link(linkRr);
wqdbg_v("S2, Rr");
return linkRr ? WQ_ITERATE_UNLINKED : WQ_ITERATE_INVALID;
}
lt_put_link(linkRl);
lt_put_link(linkRr);
}
return WQ_ITERATE_CONTINUE;
}
static int waitq_unlink_cb(struct waitq *waitq, void *ctx,
struct setid_link *link)
{
uint64_t setid = *((uint64_t *)ctx);
struct setid_link *right, *left;
int ret = 0;
if (sl_type(link) != SLT_LINK)
return WQ_ITERATE_CONTINUE;
do {
left = lt_get_link(link->sl_link.sl_left_setid);
right = lt_get_link(link->sl_link.sl_right_setid);
ret = waitq_maybe_remove_link(waitq, setid, link, left, right);
lt_put_link(left);
lt_put_link(right);
if (!sl_is_valid(link))
return WQ_ITERATE_INVALID;
} while (ret == WQ_ITERATE_INVALID);
return ret;
}
static int waitq_unlink_prepost_cb(struct waitq_set __unused *wqset, void *ctx,
struct wq_prepost *wqp, struct waitq *waitq)
{
struct wq_unlink_ctx *ulctx = (struct wq_unlink_ctx *)ctx;
if (waitq != ulctx->unlink_wq)
return WQ_ITERATE_CONTINUE;
if (wqp_type(wqp) == WQP_WQ &&
wqp->wqp_prepostid.id == ulctx->unlink_wqset->wqset_prepost_id) {
wqdbg_v("unlink wqp (WQ) 0x%llx", wqp->wqp_prepostid.id);
ulctx->unlink_wqset->wqset_prepost_id = 0;
return WQ_ITERATE_BREAK;
}
assert(wqp_type(wqp) == WQP_POST);
wq_prepost_remove(ulctx->unlink_wqset, wqp);
return WQ_ITERATE_BREAK;
}
static kern_return_t waitq_unlink_locked(struct waitq *waitq,
struct waitq_set *wqset,
spl_t *s)
{
uint64_t setid;
kern_return_t kr;
setid = wqset->wqset_id;
if (waitq->waitq_set_id == 0) {
if (waitq->waitq_prepost_id != 0)
(void)waitq_clear_prepost_locked(waitq, s);
return KERN_NOT_IN_SET;
}
if (waitq->waitq_set_id == setid) {
waitq->waitq_set_id = 0;
(void)waitq_clear_prepost_locked(waitq, s);
return KERN_SUCCESS;
}
kr = walk_setid_links(LINK_WALK_ONE_LEVEL, waitq, waitq->waitq_set_id,
SLT_LINK, (void *)&setid, waitq_unlink_cb);
if (kr == WQ_ITERATE_UNLINKED) {
struct wq_unlink_ctx ulctx;
int do_spl = 0;
kr = KERN_SUCCESS;
if (!waitq_irq_safe(waitq) && waitq_irq_safe(&wqset->wqset_q)) {
*s = splsched();
do_spl = 1;
}
waitq_set_lock(wqset);
ulctx.unlink_wq = waitq;
ulctx.unlink_wqset = wqset;
(void)wq_prepost_iterate(wqset->wqset_prepost_id, (void *)&ulctx,
waitq_unlink_prepost_cb);
waitq_set_unlock(wqset);
if (do_spl)
splx(*s);
} else {
kr = KERN_NOT_IN_SET;
}
return kr;
}
kern_return_t waitq_unlink(struct waitq *waitq, struct waitq_set *wqset)
{
kern_return_t kr = KERN_SUCCESS;
spl_t s;
assert(waitqs_is_set(wqset));
if (!waitq_valid(waitq))
return KERN_INVALID_ARGUMENT;
wqdbg_v("unlink waitq %p from set 0x%llx",
(void *)VM_KERNEL_UNSLIDE_OR_PERM(waitq), wqset->wqset_id);
if (waitq_irq_safe(waitq))
s = splsched();
waitq_lock(waitq);
kr = waitq_unlink_locked(waitq, wqset, &s);
waitq_unlock(waitq);
if (waitq_irq_safe(waitq))
splx(s);
return kr;
}
void waitq_unlink_by_prepost_id(uint64_t wqp_id, struct waitq_set *wqset)
{
struct wq_prepost *wqp;
disable_preemption();
wqp = wq_prepost_get(wqp_id);
if (wqp) {
struct waitq *wq;
spl_t s;
wq = wqp->wqp_wq.wqp_wq_ptr;
if (waitq_irq_safe(wq))
s = splsched();
waitq_lock(wq);
wq_prepost_put(wqp);
if (!waitq_valid(wq)) {
waitq_unlock(wq);
if (waitq_irq_safe(wq))
splx(s);
enable_preemption();
return;
}
waitq_unlink_locked(wq, wqset, &s);
waitq_unlock(wq);
if (waitq_irq_safe(wq))
splx(s);
}
enable_preemption();
return;
}
kern_return_t waitq_unlink_all_locked(struct waitq *waitq, uint64_t *old_set_id,
spl_t *s, int *dropped_lock)
{
wqdbg_v("unlink waitq %p from all sets",
(void *)VM_KERNEL_UNSLIDE_OR_PERM(waitq));
*old_set_id = 0;
if (waitq->waitq_set_id == 0)
return KERN_SUCCESS;
*old_set_id = waitq->waitq_set_id;
waitq->waitq_set_id = 0;
int dropped = waitq_clear_prepost_locked(waitq, s);
if (dropped_lock)
*dropped_lock = dropped;
return KERN_SUCCESS;
}
kern_return_t waitq_unlink_all(struct waitq *waitq)
{
kern_return_t kr = KERN_SUCCESS;
uint64_t setid = 0;
spl_t s;
if (!waitq_valid(waitq))
panic("Invalid waitq: %p", waitq);
if (waitq_irq_safe(waitq))
s = splsched();
waitq_lock(waitq);
if (waitq_valid(waitq))
kr = waitq_unlink_all_locked(waitq, &setid, &s, NULL);
waitq_unlock(waitq);
if (waitq_irq_safe(waitq))
splx(s);
if (setid) {
(void)walk_setid_links(LINK_WALK_ONE_LEVEL, waitq, setid,
SLT_LINK, NULL, waitq_unlink_all_cb);
}
return kr;
}
kern_return_t waitq_set_unlink_all(struct waitq_set *wqset)
{
struct setid_link *link;
uint64_t prepost_id, set_links_id = 0;
spl_t spl;
assert(waitqs_is_set(wqset));
wqdbg_v("unlink all queues from set 0x%llx", wqset->wqset_id);
if (waitq_irq_safe(&wqset->wqset_q))
spl = splsched();
waitq_set_lock(wqset);
link = lt_get_link(wqset->wqset_id);
if (!link) {
waitq_set_unlock(wqset);
return KERN_SUCCESS;
}
lt_invalidate(link);
lt_realloc_link(link, SLT_WQS);
link->sl_wqs.sl_set = wqset;
wqset->wqset_id = link->sl_set_id.id;
sl_set_valid(link);
lt_put_link(link);
prepost_id = wqset->wqset_prepost_id;
wqset->wqset_prepost_id = 0;
waitq_unlink_all_locked(&wqset->wqset_q, &set_links_id, &spl, NULL);
waitq_set_unlock(wqset);
if (waitq_irq_safe(&wqset->wqset_q))
splx(spl);
if (set_links_id)
(void)walk_setid_links(LINK_WALK_ONE_LEVEL, &wqset->wqset_q,
set_links_id, SLT_LINK, NULL,
waitq_unlink_all_cb);
if (prepost_id)
(void)wq_prepost_iterate(prepost_id, NULL,
wqset_clear_prepost_chain_cb);
return KERN_SUCCESS;
}
static int waitq_prepost_reserve_cb(struct waitq *waitq, void *ctx,
struct setid_link *link)
{
uint32_t *num = (uint32_t *)ctx;
(void)waitq;
if (sl_type(link) == SLT_WQS) {
if (waitq_set_can_prepost(link->sl_wqs.sl_set))
*num += 2;
}
return WQ_ITERATE_CONTINUE;
}
static int waitq_alloc_prepost_reservation(int nalloc, struct waitq *waitq,
spl_t *s, int *did_unlock,
struct wq_prepost **wqp)
{
struct wq_prepost *tmp;
struct wqp_cache *cache;
*did_unlock = 0;
if (waitq) {
disable_preemption();
cache = &PROCESSOR_DATA(current_processor(), wqp_cache);
if (nalloc <= (int)cache->avail)
goto do_alloc;
enable_preemption();
*did_unlock = 1;
waitq_unlock(waitq);
if (waitq_irq_safe(waitq))
splx(*s);
}
do_alloc:
tmp = wq_prepost_alloc(WQT_RESERVED, nalloc);
if (!tmp)
panic("Couldn't reserve %d preposts for waitq @%p (wqp@%p)",
nalloc, waitq, *wqp);
if (*wqp) {
int __assert_only rc;
rc = wq_prepost_rlink(tmp, *wqp);
assert(rc == nalloc);
}
*wqp = tmp;
if (get_preemption_level() == 0)
wq_prepost_ensure_free_space();
if (waitq) {
if (*did_unlock == 0) {
enable_preemption();
} else {
if (waitq_irq_safe(waitq))
*s = splsched();
waitq_lock(waitq);
}
}
return nalloc;
}
static int waitq_count_prepost_reservation(struct waitq *waitq, int extra, int keep_locked)
{
int npreposts = 0;
if (waitq->waitq_set_id == 0) {
npreposts = 3;
} else {
if (waitq->waitq_prepost_id == 0)
npreposts = 3;
(void)walk_setid_links(LINK_WALK_FULL_DAG_UNLOCKED,
waitq, waitq->waitq_set_id,
SLT_WQS, (void *)&npreposts,
waitq_prepost_reserve_cb);
}
if (extra > 0)
npreposts += extra;
if (npreposts == 0 && !keep_locked) {
npreposts = 3;
}
return npreposts;
}
uint64_t waitq_prepost_reserve(struct waitq *waitq, int extra,
waitq_lock_state_t lock_state, spl_t *s)
{
uint64_t reserved = 0;
uint64_t prev_setid = 0, prev_prepostid = 0;
struct wq_prepost *wqp = NULL;
int nalloc = 0, npreposts = 0;
int keep_locked = (lock_state == WAITQ_KEEP_LOCKED);
int unlocked = 0;
if (s)
*s = 0;
wqdbg_v("Attempting to reserve prepost linkages for waitq %p (extra:%d)",
(void *)VM_KERNEL_UNSLIDE_OR_PERM(waitq), extra);
if (waitq == NULL && extra > 0) {
nalloc = waitq_alloc_prepost_reservation(extra + 2, NULL, NULL,
&unlocked, &wqp);
assert(nalloc == extra + 2);
return wqp->wqp_prepostid.id;
}
assert(lock_state == WAITQ_KEEP_LOCKED || lock_state == WAITQ_UNLOCK);
if (waitq_irq_safe(waitq))
*s = splsched();
waitq_lock(waitq);
if (waitq_is_global(waitq)) {
if (keep_locked)
goto out;
goto out_unlock;
}
prev_setid = waitq->waitq_set_id;
prev_prepostid = waitq->waitq_prepost_id;
if (prev_setid == 0 && keep_locked)
goto out;
npreposts = waitq_count_prepost_reservation(waitq, extra, keep_locked);
if (npreposts == 0) {
if (keep_locked)
goto out;
goto out_unlock;
}
try_alloc:
nalloc = waitq_alloc_prepost_reservation(npreposts, waitq, s,
&unlocked, &wqp);
if (!unlocked) {
if (keep_locked)
goto out;
goto out_unlock;
}
if ((waitq->waitq_set_id == 0) ||
(waitq->waitq_set_id == prev_setid &&
waitq->waitq_prepost_id == prev_prepostid)) {
if (keep_locked)
goto out;
goto out_unlock;
}
npreposts = waitq_count_prepost_reservation(waitq, extra, keep_locked);
if (npreposts > nalloc) {
prev_setid = waitq->waitq_set_id;
prev_prepostid = waitq->waitq_prepost_id;
npreposts = npreposts - nalloc;
goto try_alloc;
}
if (keep_locked)
goto out;
out_unlock:
waitq_unlock(waitq);
if (waitq_irq_safe(waitq))
splx(*s);
out:
if (wqp)
reserved = wqp->wqp_prepostid.id;
return reserved;
}
void waitq_prepost_release_reserve(uint64_t id)
{
struct wq_prepost *wqp;
wqdbg_v("releasing reserved preposts starting at: 0x%llx", id);
wqp = wq_prepost_rfirst(id);
if (!wqp)
return;
wq_prepost_release_rlist(wqp);
}
void waitq_set_clear_preposts(struct waitq_set *wqset)
{
uint64_t prepost_id;
spl_t spl;
assert(waitqs_is_set(wqset));
wqdbg_v("Clearing all preposted queues on waitq_set: 0x%llx",
wqset->wqset_id);
if (waitq_irq_safe(&wqset->wqset_q))
spl = splsched();
waitq_set_lock(wqset);
prepost_id = wqset->wqset_prepost_id;
wqset->wqset_prepost_id = 0;
waitq_set_unlock(wqset);
if (waitq_irq_safe(&wqset->wqset_q))
splx(spl);
if (prepost_id)
(void)wq_prepost_iterate(prepost_id, NULL,
wqset_clear_prepost_chain_cb);
}
struct wq_it_ctx {
void *input;
void *ctx;
waitq_iterator_t it;
spl_t *spl;
};
static int waitq_iterate_sets_cb(struct waitq *waitq, void *ctx,
struct setid_link *link)
{
struct wq_it_ctx *wctx = (struct wq_it_ctx *)(ctx);
struct waitq_set *wqset;
int ret;
spl_t spl;
(void)waitq;
assert(sl_type(link) == SLT_WQS);
wqset = link->sl_wqs.sl_set;
assert(wqset != NULL);
if (!waitq_irq_safe(waitq) && waitq_irq_safe(&wqset->wqset_q))
spl = splsched();
waitq_set_lock(wqset);
ret = wctx->it(wctx->ctx, (struct waitq *)wctx->input, wqset);
waitq_set_unlock(wqset);
if (!waitq_irq_safe(waitq) && waitq_irq_safe(&wqset->wqset_q))
splx(spl);
return ret;
}
static int wqset_iterate_prepost_cb(struct waitq_set *wqset, void *ctx,
struct wq_prepost *wqp, struct waitq *waitq)
{
struct wq_it_ctx *wctx = (struct wq_it_ctx *)(ctx);
uint64_t wqp_id;
int ret;
spl_t s;
(void)wqp;
if (waitq_irq_safe(waitq))
s = splsched();
if (waitq_lock_try(waitq))
goto call_iterator;
if (waitq_irq_safe(waitq))
splx(s);
if (!wqp_is_valid(wqp))
return WQ_ITERATE_RESTART;
wqp_id = wqp->wqp_prepostid.id;
wq_prepost_put(wqp);
waitq_set_unlock(wqset);
wqdbg_v("dropped set:%p lock waiting for wqp:%p (0x%llx -> wq:%p)",
wqset, wqp, wqp->wqp_prepostid.id, waitq);
delay(1);
waitq_set_lock(wqset);
wqp = wq_prepost_get(wqp_id);
if (!wqp)
return WQ_ITERATE_DROPPED;
return WQ_ITERATE_RESTART;
call_iterator:
if (!wqp_is_valid(wqp)) {
ret = WQ_ITERATE_RESTART;
goto out_unlock;
}
ret = wctx->it(wctx->ctx, waitq, wqset);
if (ret == WQ_ITERATE_BREAK_KEEP_LOCKED) {
ret = WQ_ITERATE_BREAK;
if (wctx->spl)
*(wctx->spl) = s;
goto out;
}
out_unlock:
waitq_unlock(waitq);
if (waitq_irq_safe(waitq))
splx(s);
out:
return ret;
}
int waitq_iterate_sets(struct waitq *waitq, void *ctx, waitq_iterator_t it)
{
int ret;
struct wq_it_ctx wctx = {
.input = (void *)waitq,
.ctx = ctx,
.it = it,
};
if (!it || !waitq)
return KERN_INVALID_ARGUMENT;
ret = walk_setid_links(LINK_WALK_ONE_LEVEL, waitq, waitq->waitq_set_id,
SLT_WQS, (void *)&wctx, waitq_iterate_sets_cb);
if (ret == WQ_ITERATE_CONTINUE)
ret = WQ_ITERATE_SUCCESS;
return ret;
}
int waitq_set_iterate_preposts(struct waitq_set *wqset,
void *ctx, waitq_iterator_t it, spl_t *s)
{
struct wq_it_ctx wctx = {
.input = (void *)wqset,
.ctx = ctx,
.it = it,
.spl = s,
};
if (!it || !wqset)
return WQ_ITERATE_INVALID;
assert(waitq_held(&wqset->wqset_q));
return wq_prepost_foreach_locked(wqset, (void *)&wctx,
wqset_iterate_prepost_cb);
}
wait_result_t waitq_assert_wait64(struct waitq *waitq,
event64_t wait_event,
wait_interrupt_t interruptible,
uint64_t deadline)
{
wait_result_t ret;
thread_t thread = current_thread();
spl_t s;
if (!waitq_valid(waitq))
panic("Invalid waitq: %p", waitq);
if (waitq_irq_safe(waitq))
s = splsched();
waitq_lock(waitq);
if (!waitq_irq_safe(waitq))
s = splsched();
thread_lock(thread);
ret = waitq_assert_wait64_locked(waitq, wait_event, interruptible,
TIMEOUT_URGENCY_SYS_NORMAL,
deadline, TIMEOUT_NO_LEEWAY, thread);
thread_unlock(thread);
waitq_unlock(waitq);
splx(s);
return ret;
}
wait_result_t waitq_assert_wait64_leeway(struct waitq *waitq,
event64_t wait_event,
wait_interrupt_t interruptible,
wait_timeout_urgency_t urgency,
uint64_t deadline,
uint64_t leeway)
{
wait_result_t ret;
thread_t thread = current_thread();
spl_t s;
if (!waitq_valid(waitq))
panic("Invalid waitq: %p", waitq);
if (waitq_irq_safe(waitq))
s = splsched();
waitq_lock(waitq);
if (!waitq_irq_safe(waitq))
s = splsched();
thread_lock(thread);
ret = waitq_assert_wait64_locked(waitq, wait_event, interruptible,
urgency, deadline, leeway, thread);
thread_unlock(thread);
waitq_unlock(waitq);
splx(s);
return ret;
}
kern_return_t waitq_wakeup64_one(struct waitq *waitq, event64_t wake_event,
wait_result_t result, int priority)
{
kern_return_t kr;
uint64_t reserved_preposts = 0;
spl_t spl;
if (!waitq_valid(waitq))
panic("Invalid waitq: %p", waitq);
reserved_preposts = waitq_prepost_reserve(waitq, 0,
WAITQ_KEEP_LOCKED, &spl);
kr = waitq_wakeup64_one_locked(waitq, wake_event, result,
&reserved_preposts, priority, WAITQ_UNLOCK);
if (waitq_irq_safe(waitq))
splx(spl);
waitq_prepost_release_reserve(reserved_preposts);
return kr;
}
kern_return_t waitq_wakeup64_all(struct waitq *waitq,
event64_t wake_event,
wait_result_t result,
int priority)
{
kern_return_t ret;
uint64_t reserved_preposts = 0;
spl_t s;
if (!waitq_valid(waitq))
panic("Invalid waitq: %p", waitq);
reserved_preposts = waitq_prepost_reserve(waitq, 0,
WAITQ_KEEP_LOCKED, &s);
ret = waitq_wakeup64_all_locked(waitq, wake_event, result,
&reserved_preposts, priority,
WAITQ_UNLOCK);
if (waitq_irq_safe(waitq))
splx(s);
waitq_prepost_release_reserve(reserved_preposts);
return ret;
}
kern_return_t waitq_wakeup64_thread(struct waitq *waitq,
event64_t wake_event,
thread_t thread,
wait_result_t result)
{
kern_return_t ret;
spl_t s, th_spl;
if (!waitq_valid(waitq))
panic("Invalid waitq: %p", waitq);
if (waitq_irq_safe(waitq))
s = splsched();
waitq_lock(waitq);
ret = waitq_select_thread_locked(waitq, wake_event, thread, &th_spl);
waitq_unlock(waitq);
if (ret == KERN_SUCCESS) {
ret = thread_go(thread, result);
assert(ret == KERN_SUCCESS);
thread_unlock(thread);
splx(th_spl);
waitq_stats_count_wakeup(waitq);
} else {
ret = KERN_NOT_WAITING;
waitq_stats_count_fail(waitq);
}
if (waitq_irq_safe(waitq))
splx(s);
return ret;
}