/*
- * Copyright (c) 2017 Apple Inc. All rights reserved.
+ * Copyright (c) 2017-2020 Apple Inc. All rights reserved.
*
* @APPLE_OSREFERENCE_LICENSE_HEADER_START@
*
#include <os/hash.h>
#include <libkern/section_keywords.h>
-static zone_t turnstiles_zone;
-static int turnstile_max_hop;
+static TUNABLE(int, turnstile_max_hop, "turnstile_max_hop", TURNSTILE_MAX_HOP_DEFAULT);
+static ZONE_DECLARE(turnstiles_zone, "turnstiles", sizeof(struct turnstile), ZC_NONE);
+
static struct mpsc_daemon_queue turnstile_deallocate_queue;
-#define MAX_TURNSTILES (thread_max)
#define TURNSTILES_CHUNK (THREAD_CHUNK)
/* Global table for turnstile promote policy for all type of turnstiles */
#if DEVELOPMENT || DEBUG
static queue_head_t turnstiles_list;
-static lck_spin_t global_turnstile_lock;
-lck_grp_t turnstiles_dev_lock_grp;
-lck_attr_t turnstiles_dev_lock_attr;
-lck_grp_attr_t turnstiles_dev_lock_grp_attr;
+static LCK_GRP_DECLARE(turnstiles_dev_lock_grp, "turnstile_dev_lock");
+static LCK_SPIN_DECLARE(global_turnstile_lock, &turnstiles_dev_lock_grp);
-#define global_turnstiles_lock_init() \
- lck_spin_init(&global_turnstile_lock, &turnstiles_dev_lock_grp, &turnstiles_dev_lock_attr)
-#define global_turnstiles_lock_destroy() \
- lck_spin_destroy(&global_turnstile_lock, &turnstiles_dev_lock_grp)
#define global_turnstiles_lock() \
lck_spin_lock_grp(&global_turnstile_lock, &turnstiles_dev_lock_grp)
#define global_turnstiles_lock_try() \
/* Static function declarations */
static turnstile_type_t
turnstile_get_type(struct turnstile *turnstile);
+static bool
+turnstile_is_send_turnstile(struct turnstile *turnstile);
static uint32_t
turnstile_get_gencount(struct turnstile *turnstile);
static void
return (turnstile_type_t) type_and_gencount.ts_type;
}
+/* Only safe to be called from stackshot context */
+static bool
+turnstile_is_send_turnstile(struct turnstile *turnstile)
+{
+ if (not_in_kdp) {
+ panic("turnstile_is_send_turnstile() called outside of kernel debugger context");
+ }
+
+ if (turnstile_get_type(turnstile) == TURNSTILE_SYNC_IPC) {
+ ipc_port_t port = (ipc_port_t) turnstile->ts_proprietor;
+
+ return port_send_turnstile(port) == turnstile;
+ }
+
+ return false;
+}
+
+/* Only safe to be called from stackshot context */
+static bool
+turnstile_is_receive_turnstile(struct turnstile *turnstile)
+{
+ if (not_in_kdp) {
+ panic("turnstile_is_receive_turnstile() called outside of kernel debugger context");
+ }
+
+ if (turnstile_get_type(turnstile) == TURNSTILE_SYNC_IPC) {
+ ipc_port_t port = (ipc_port_t) turnstile->ts_proprietor;
+
+ return *port_rcv_turnstile_address(port) == turnstile;
+ }
+
+ return false;
+}
+
static uint32_t
turnstile_get_gencount(struct turnstile *turnstile)
{
/* Bucket locks for turnstile hashtable */
-lck_grp_t turnstiles_htable_lock_grp;
-lck_attr_t turnstiles_htable_lock_attr;
-lck_grp_attr_t turnstiles_htable_lock_grp_attr;
+LCK_GRP_DECLARE(turnstiles_htable_lock_grp, "turnstiles_htable_locks");
#define turnstile_bucket_lock_init(bucket) \
- lck_spin_init(&bucket->ts_ht_bucket_lock, &turnstiles_htable_lock_grp, &turnstiles_htable_lock_attr)
+ lck_spin_init(&bucket->ts_ht_bucket_lock, &turnstiles_htable_lock_grp, LCK_ATTR_NULL)
#define turnstile_bucket_lock(bucket) \
lck_spin_lock_grp(&bucket->ts_ht_bucket_lock, &turnstiles_htable_lock_grp)
#define turnstile_bucket_unlock(bucket) \
assert(ts_htable_buckets <= TURNSTILE_HTABLE_BUCKETS_MAX);
uint32_t ts_htable_size = ts_htable_buckets * sizeof(struct turnstile_htable_bucket);
- turnstile_htable_irq_safe = (struct turnstile_htable_bucket *)kalloc(ts_htable_size);
+ turnstile_htable_irq_safe = zalloc_permanent(ts_htable_size, ZALIGN_PTR);
if (turnstile_htable_irq_safe == NULL) {
panic("Turnstiles hash table memory allocation failed!");
}
- turnstile_htable = (struct turnstile_htable_bucket *)kalloc(ts_htable_size);
+ turnstile_htable = zalloc_permanent(ts_htable_size, ZALIGN_PTR);
if (turnstile_htable == NULL) {
panic("Turnstiles hash table memory allocation failed!");
}
- lck_grp_attr_setdefault(&turnstiles_htable_lock_grp_attr);
- lck_grp_init(&turnstiles_htable_lock_grp, "turnstiles_htable_locks", &turnstiles_htable_lock_grp_attr);
- lck_attr_setdefault(&turnstiles_htable_lock_attr);
/* Initialize all the buckets of the hashtables */
for (uint32_t i = 0; i < ts_htable_buckets; i++) {
void
turnstiles_init(void)
{
- turnstiles_zone = zinit(sizeof(struct turnstile),
- MAX_TURNSTILES * sizeof(struct turnstile),
- TURNSTILES_CHUNK * sizeof(struct turnstile),
- "turnstiles");
-
- if (!PE_parse_boot_argn("turnstile_max_hop", &turnstile_max_hop, sizeof(turnstile_max_hop))) {
- turnstile_max_hop = TURNSTILE_MAX_HOP_DEFAULT;
- }
-
turnstiles_hashtable_init();
thread_deallocate_daemon_register_queue(&turnstile_deallocate_queue,
turnstile_deallocate_queue_invoke);
#if DEVELOPMENT || DEBUG
- /* Initialize the global turnstile locks and lock group */
-
- lck_grp_attr_setdefault(&turnstiles_dev_lock_grp_attr);
- lck_grp_init(&turnstiles_dev_lock_grp, "turnstiles_dev_lock", &turnstiles_dev_lock_grp_attr);
- lck_attr_setdefault(&turnstiles_dev_lock_attr);
- global_turnstiles_lock_init();
-
queue_init(&turnstiles_list);
/* Initialize turnstile test primitive */
tstile_test_prim_init(&test_prim_global_ts_kernel);
tstile_test_prim_init(&test_prim_global_ts_kernel_hash);
#endif
- return;
}
/*
turnstile->ts_priority = 0;
turnstile->ts_inheritor_flags = TURNSTILE_UPDATE_FLAGS_NONE;
turnstile->ts_port_ref = 0;
- priority_queue_init(&turnstile->ts_inheritor_queue,
- PRIORITY_QUEUE_BUILTIN_MAX_HEAP);
+ priority_queue_init(&turnstile->ts_inheritor_queue);
#if DEVELOPMENT || DEBUG
turnstile->ts_thread = current_thread();
int thread_link_priority;
boolean_t needs_update = FALSE;
- thread_link_priority = priority_queue_entry_key(&(dst_turnstile->ts_waitq.waitq_prio_queue),
- &(thread->wait_prioq_links));
+ thread_link_priority = priority_queue_entry_sched_pri(
+ &dst_turnstile->ts_waitq.waitq_prio_queue,
+ &thread->wait_prioq_links);
int priority = turnstile_compute_thread_push(dst_turnstile, thread);
* Returns: whether the maximum priority of the queue changed.
*/
static boolean_t
-turnstile_priority_queue_update_entry_key(struct priority_queue *q,
- priority_queue_entry_t elt, priority_queue_key_t pri)
+turnstile_priority_queue_update_entry_key(struct priority_queue_sched_max *q,
+ priority_queue_entry_sched_t elt, priority_queue_key_t pri)
{
- priority_queue_key_t old_key = priority_queue_max_key(q);
+ priority_queue_key_t old_key = priority_queue_max_sched_pri(q);
- if (priority_queue_entry_key(q, elt) < pri) {
- if (priority_queue_entry_increase(q, elt, pri,
- PRIORITY_QUEUE_SCHED_PRI_MAX_HEAP_COMPARE)) {
- return old_key != priority_queue_max_key(q);
+ if (priority_queue_entry_sched_pri(q, elt) < pri) {
+ priority_queue_entry_set_sched_pri(q, elt, pri, false);
+ if (priority_queue_entry_increased(q, elt)) {
+ return old_key != priority_queue_max_sched_pri(q);
}
- } else if (priority_queue_entry_key(q, elt) > pri) {
- if (priority_queue_entry_decrease(q, elt, pri,
- PRIORITY_QUEUE_SCHED_PRI_MAX_HEAP_COMPARE)) {
- return old_key != priority_queue_max_key(q);
+ } else if (priority_queue_entry_sched_pri(q, elt) > pri) {
+ priority_queue_entry_set_sched_pri(q, elt, pri, false);
+ if (priority_queue_entry_decreased(q, elt)) {
+ return old_key != priority_queue_max_sched_pri(q);
}
}
int priority = turnstile_compute_thread_push(dst_turnstile, thread);
- thread_link_priority = priority_queue_entry_key(&(dst_turnstile->ts_waitq.waitq_prio_queue),
- &(thread->wait_prioq_links));
+ thread_link_priority = priority_queue_entry_sched_pri(
+ &dst_turnstile->ts_waitq.waitq_prio_queue,
+ &thread->wait_prioq_links);
if (priority != thread_link_priority) {
KERNEL_DEBUG_CONSTANT_IST(KDEBUG_TRACE,
if (!turnstile_priority_queue_update_entry_key(
&dst_turnstile->ts_waitq.waitq_prio_queue,
- &thread->wait_prioq_links, priority)) {
+ &thread->wait_prioq_links, (priority_queue_key_t)priority)) {
return FALSE;
}
case TURNSTILE_USER_PROMOTE:
case TURNSTILE_USER_IPC_PROMOTE:
- if (priority_queue_insert(&(thread->base_inheritor_queue),
- &turnstile->ts_inheritor_links, turnstile->ts_priority,
- PRIORITY_QUEUE_SCHED_PRI_MAX_HEAP_COMPARE)) {
+ priority_queue_entry_set_sched_pri(&thread->base_inheritor_queue,
+ &turnstile->ts_inheritor_links, turnstile->ts_priority, false);
+ if (priority_queue_insert(&thread->base_inheritor_queue,
+ &turnstile->ts_inheritor_links)) {
needs_update = thread_recompute_user_promotion_locked(thread);
}
break;
case TURNSTILE_KERNEL_PROMOTE:
- if (priority_queue_insert(&(thread->sched_inheritor_queue),
- &turnstile->ts_inheritor_links, turnstile->ts_priority,
- PRIORITY_QUEUE_SCHED_PRI_MAX_HEAP_COMPARE)) {
+ priority_queue_entry_set_sched_pri(&thread->sched_inheritor_queue,
+ &turnstile->ts_inheritor_links, turnstile->ts_priority, false);
+ if (priority_queue_insert(&thread->sched_inheritor_queue,
+ &turnstile->ts_inheritor_links)) {
needs_update = thread_recompute_kernel_promotion_locked(thread);
}
switch (turnstile_promote_policy[turnstile_get_type(turnstile)]) {
case TURNSTILE_USER_PROMOTE:
case TURNSTILE_USER_IPC_PROMOTE:
- if (priority_queue_remove(&(thread->base_inheritor_queue),
- &turnstile->ts_inheritor_links,
- PRIORITY_QUEUE_SCHED_PRI_MAX_HEAP_COMPARE)) {
+ if (priority_queue_remove(&thread->base_inheritor_queue,
+ &turnstile->ts_inheritor_links)) {
needs_update = thread_recompute_user_promotion_locked(thread);
}
break;
case TURNSTILE_KERNEL_PROMOTE:
- if (priority_queue_remove(&(thread->sched_inheritor_queue),
- &turnstile->ts_inheritor_links,
- PRIORITY_QUEUE_SCHED_PRI_MAX_HEAP_COMPARE)) {
+ if (priority_queue_remove(&thread->sched_inheritor_queue,
+ &turnstile->ts_inheritor_links)) {
needs_update = thread_recompute_kernel_promotion_locked(thread);
}
break;
switch (turnstile_promote_policy[turnstile_get_type(turnstile)]) {
case TURNSTILE_USER_PROMOTE:
case TURNSTILE_USER_IPC_PROMOTE:
- turnstile_link_priority = priority_queue_entry_key(&(thread->base_inheritor_queue),
- &(turnstile->ts_inheritor_links));
+ turnstile_link_priority = priority_queue_entry_sched_pri(
+ &thread->base_inheritor_queue,
+ &turnstile->ts_inheritor_links);
break;
case TURNSTILE_KERNEL_PROMOTE:
- turnstile_link_priority = priority_queue_entry_key(&(thread->sched_inheritor_queue),
- &(turnstile->ts_inheritor_links));
+ turnstile_link_priority = priority_queue_entry_sched_pri(
+ &thread->sched_inheritor_queue,
+ &turnstile->ts_inheritor_links);
break;
default:
panic("turnstile promotion for type %d not yet implemented", turnstile_get_type(turnstile));
switch (turnstile_promote_policy[turnstile_get_type(turnstile)]) {
case TURNSTILE_USER_PROMOTE:
case TURNSTILE_USER_IPC_PROMOTE:
- turnstile_link_priority = priority_queue_entry_key(&(thread->base_inheritor_queue), &turnstile->ts_inheritor_links);
+ turnstile_link_priority = priority_queue_entry_sched_pri(
+ &thread->base_inheritor_queue,
+ &turnstile->ts_inheritor_links);
if (turnstile_priority_queue_update_entry_key(&(thread->base_inheritor_queue),
&turnstile->ts_inheritor_links, turnstile->ts_priority)) {
}
break;
case TURNSTILE_KERNEL_PROMOTE:
- turnstile_link_priority = priority_queue_entry_key(&(thread->sched_inheritor_queue), &turnstile->ts_inheritor_links);
+ turnstile_link_priority = priority_queue_entry_sched_pri(
+ &thread->sched_inheritor_queue,
+ &turnstile->ts_inheritor_links);
if (turnstile_priority_queue_update_entry_key(&(thread->sched_inheritor_queue),
&turnstile->ts_inheritor_links, turnstile->ts_priority)) {
struct turnstile, ts_inheritor_links);
if (max_turnstile) {
- return priority_queue_entry_key(&thread->sched_inheritor_queue,
- &max_turnstile->ts_inheritor_links);
+ return priority_queue_entry_sched_pri(
+ &thread->sched_inheritor_queue,
+ &max_turnstile->ts_inheritor_links);
}
return 0;
struct turnstile, ts_inheritor_links);
if (max_turnstile) {
- return priority_queue_entry_key(&thread->base_inheritor_queue,
- &max_turnstile->ts_inheritor_links);
+ return priority_queue_entry_sched_pri(
+ &thread->base_inheritor_queue,
+ &max_turnstile->ts_inheritor_links);
}
return 0;
return turnstile;
}
- /* Get the safeq if the waitq is a port queue */
- if (waitq_is_port_queue(waitq)) {
- waitq = waitq_get_safeq(waitq);
+ if (waitq_is_turnstile_proxy(waitq)) {
+ return waitq->waitq_ts;
}
/* Check if the waitq is a turnstile queue */
}
/* Get the safeq if the waitq is a port queue */
- if (waitq_is_port_queue(waitq)) {
- waitq = waitq_get_safeq(waitq);
+ if (waitq_is_turnstile_proxy(waitq)) {
+ if (waitq->waitq_ts) {
+ return TSU_NO_PRI_CHANGE_NEEDED;
+ }
+ return TSU_NO_TURNSTILE;
}
/* Check if the waitq is a turnstile queue */
int src_turnstile_link_priority;
boolean_t needs_update = FALSE;
- src_turnstile_link_priority = priority_queue_entry_key(&(dst_turnstile->ts_inheritor_queue),
- &(src_turnstile->ts_inheritor_links));
+ src_turnstile_link_priority = priority_queue_entry_sched_pri(
+ &dst_turnstile->ts_inheritor_queue,
+ &src_turnstile->ts_inheritor_links);
needs_update = (src_turnstile_link_priority == src_turnstile->ts_priority) ? FALSE : TRUE;
return needs_update;
struct turnstile *src_turnstile)
{
int src_turnstile_link_priority;
- src_turnstile_link_priority = priority_queue_entry_key(&(dst_turnstile->ts_inheritor_queue),
- &(src_turnstile->ts_inheritor_links));
+ src_turnstile_link_priority = priority_queue_entry_sched_pri(
+ &dst_turnstile->ts_inheritor_queue,
+ &src_turnstile->ts_inheritor_links);
if (src_turnstile->ts_priority != src_turnstile_link_priority) {
KERNEL_DEBUG_CONSTANT_IST(KDEBUG_TRACE,
VM_KERNEL_UNSLIDE_OR_PERM(src_turnstile),
src_turnstile->ts_priority, 0, 0);
- priority_queue_entry_init(&(src_turnstile->ts_inheritor_links));
+ priority_queue_entry_init(&src_turnstile->ts_inheritor_links);
+ priority_queue_entry_set_sched_pri(&dst_turnstile->ts_inheritor_queue,
+ &src_turnstile->ts_inheritor_links, src_turnstile->ts_priority, false);
if (priority_queue_insert(&dst_turnstile->ts_inheritor_queue,
- &src_turnstile->ts_inheritor_links, src_turnstile->ts_priority,
- PRIORITY_QUEUE_SCHED_PRI_MAX_HEAP_COMPARE)) {
+ &src_turnstile->ts_inheritor_links)) {
/* Update dst turnstile priority */
needs_update = turnstile_recompute_priority_locked(dst_turnstile);
}
0, 0, 0);
if (priority_queue_remove(&dst_turnstile->ts_inheritor_queue,
- &src_turnstile->ts_inheritor_links,
- PRIORITY_QUEUE_SCHED_PRI_MAX_HEAP_COMPARE)) {
+ &src_turnstile->ts_inheritor_links)) {
/* Update dst turnstile priority */
needs_update = turnstile_recompute_priority_locked(dst_turnstile);
}
* queue by calling priority queue increase/decrease
* operations.
*/
- priority_queue_entry_init(&(thread->wait_prioq_links));
+ priority_queue_entry_init(&thread->wait_prioq_links);
+ priority_queue_entry_set_sched_pri(&wq->waitq_prio_queue,
+ &thread->wait_prioq_links, priority, false);
priority_queue_insert(&wq->waitq_prio_queue,
- &thread->wait_prioq_links, priority,
- PRIORITY_QUEUE_SCHED_PRI_MAX_HEAP_COMPARE);
+ &thread->wait_prioq_links);
}
/*
struct thread, wait_prioq_links);
if (max_thread) {
- thread_max_pri = priority_queue_entry_key(&turnstile->ts_waitq.waitq_prio_queue,
- &max_thread->wait_prioq_links);
+ thread_max_pri = priority_queue_entry_sched_pri(
+ &turnstile->ts_waitq.waitq_prio_queue,
+ &max_thread->wait_prioq_links);
}
max_turnstile = priority_queue_max(&turnstile->ts_inheritor_queue,
if (max_turnstile) {
assert(turnstile_promote_policy[turnstile_get_type(turnstile)] != TURNSTILE_KERNEL_PROMOTE);
- turnstile_max_pri = priority_queue_entry_key(&turnstile->ts_inheritor_queue,
- &max_turnstile->ts_inheritor_links);
+ turnstile_max_pri = priority_queue_entry_sched_pri(
+ &turnstile->ts_inheritor_queue,
+ &max_turnstile->ts_inheritor_links);
}
new_priority = max(thread_max_pri, turnstile_max_pri);
- turnstile->ts_priority = new_priority;
+ turnstile->ts_priority = (uint8_t)new_priority;
if (old_priority != new_priority) {
KERNEL_DEBUG_CONSTANT_IST(KDEBUG_TRACE,
max_turnstile = priority_queue_max(&turnstile->ts_inheritor_queue,
struct turnstile, ts_inheritor_links);
if (max_turnstile) {
- max_priority = priority_queue_entry_key(&turnstile->ts_inheritor_queue,
- &max_turnstile->ts_inheritor_links);
+ max_priority = priority_queue_entry_sched_pri(
+ &turnstile->ts_inheritor_queue,
+ &max_turnstile->ts_inheritor_links);
proprietor = max_turnstile->ts_proprietor;
}
max_thread = priority_queue_max(&turnstile->ts_waitq.waitq_prio_queue,
struct thread, wait_prioq_links);
if (max_thread) {
- max_thread_pri = priority_queue_entry_key(
+ max_thread_pri = priority_queue_entry_sched_pri(
&turnstile->ts_waitq.waitq_prio_queue,
&max_thread->wait_prioq_links);
}
max_ts = priority_queue_max(&turnstile->ts_inheritor_queue,
struct turnstile, ts_inheritor_links);
if (max_ts) {
- max_ts_pri = priority_queue_entry_key(&turnstile->ts_inheritor_queue,
- &max_ts->ts_inheritor_links);
+ max_ts_pri = priority_queue_entry_sched_pri(
+ &turnstile->ts_inheritor_queue,
+ &max_ts->ts_inheritor_links);
}
/*
*hops = *hops + 1;
+ /*
+ * If we found a send turnstile, try to get the task that the turnstile's
+ * port is in the ipc space of
+ */
+ if (turnstile_is_send_turnstile(ts)) {
+ task_t dest_task = TASK_NULL;
+ ipc_port_t port = (ipc_port_t)ts->ts_proprietor;
+
+ if (port && ip_active(port)) {
+ if (ip_lock_held_kdp(port)) {
+ *flags |= STACKSHOT_TURNSTILE_STATUS_HELD_IPLOCK;
+
+ return 0;
+ } else {
+ if (port->ip_receiver_name != 0) {
+ if (port->ip_receiver) {
+ ipc_space_t space = (ipc_space_t) port->ip_receiver;
+
+ dest_task = space->is_task;
+ } else {
+ return 0;
+ }
+ }
+ }
+ }
+
+ if (dest_task != TASK_NULL) {
+ *flags |= STACKSHOT_TURNSTILE_STATUS_BLOCKED_ON_TASK;
+ return pid_from_task(dest_task);
+ }
+ }
+
if (ts->ts_inheritor_flags & TURNSTILE_INHERITOR_TURNSTILE) {
return kdp_turnstile_traverse_inheritor_chain(ts->ts_inheritor, flags, hops);
}
return VM_KERNEL_UNSLIDE_OR_PERM(ts->ts_inheritor);
}
+ if (turnstile_is_receive_turnstile(ts)) {
+ ipc_port_t port = (ipc_port_t)ts->ts_proprietor;
+ if (port && ip_active(port)) {
+ if (ip_lock_held_kdp(port)) {
+ *flags |= STACKSHOT_TURNSTILE_STATUS_HELD_IPLOCK;
+ return 0;
+ }
+ if (port->ip_specialreply) {
+ /* try getting the pid stored in the port */
+ uint64_t pid_candidate = ipc_special_reply_get_pid_locked(port);
+
+ if (pid_candidate) {
+ *flags |= STACKSHOT_TURNSTILE_STATUS_BLOCKED_ON_TASK;
+ return pid_candidate;
+ }
+ }
+ }
+ }
+
*flags |= STACKSHOT_TURNSTILE_STATUS_UNKNOWN;
return 0;
}
test_prim->ttprim_turnstile = TURNSTILE_NULL;
test_prim->ttprim_owner = NULL;
- lck_spin_init(&test_prim->ttprim_interlock, &turnstiles_dev_lock_grp, &turnstiles_dev_lock_attr);
+ lck_spin_init(&test_prim->ttprim_interlock, &turnstiles_dev_lock_grp, LCK_ATTR_NULL);
test_prim->tt_prim_waiters = 0;
*test_prim_ptr = test_prim;
projects / apple / xnu.git / blobdiff