[kernel][wait_queue] extend wait queues to keep a sorted list of priority queues
Will now track blocked threads as a list of queues, sorted by priority.
Threads are added/removed in FIFO order within their queues.
Change-Id: I9ac10cc22cd2959b2731ab8559caf724c2dd5ffe
diff --git a/kernel/include/kernel/thread.h b/kernel/include/kernel/thread.h
index 38fa453..158c370 100644
--- a/kernel/include/kernel/thread.h
+++ b/kernel/include/kernel/thread.h
@@ -90,6 +90,11 @@
unsigned int flags;
unsigned int signals;
+ /* Total time in THREAD_RUNNING state. If the thread is currently in
+ * THREAD_RUNNING state, this excludes the time it has accrued since it
+ * left the scheduler. */
+ zx_duration_t runtime_ns;
+
int base_priority;
int priority_boost;
@@ -98,6 +103,18 @@
cpu_num_t last_cpu; /* last cpu the thread ran on, INVALID_CPU if it's never run */
cpu_mask_t cpu_affinity; /* mask of cpus that this thread can run on */
+ /* if blocked, a pointer to the wait queue */
+ struct wait_queue* blocking_wait_queue;
+
+ /* list of other wait queue heads if we're a head */
+ struct list_node wait_queue_heads_node;
+
+ /* return code if woken up abnormally from suspend, sleep, or block */
+ zx_status_t blocked_status;
+
+ /* are we allowed to be interrupted on the current thing we're blocked/sleeping on */
+ bool interruptable;
+
/* pointer to the kernel address space this thread is associated with */
struct vmm_aspace* aspace;
@@ -109,20 +126,6 @@
/* callback for user thread state changes */
thread_user_callback_t user_callback;
- /* Total time in THREAD_RUNNING state. If the thread is currently in
- * THREAD_RUNNING state, this excludes the time it has accrued since it
- * left the scheduler. */
- zx_duration_t runtime_ns;
-
- /* if blocked, a pointer to the wait queue */
- struct wait_queue* blocking_wait_queue;
-
- /* return code if woken up abnormally from suspend, sleep, or block */
- zx_status_t blocked_status;
-
- /* are we allowed to be interrupted on the current thing we're blocked/sleeping on */
- bool interruptable;
-
/* non-NULL if stopped in an exception */
const struct arch_exception_context* exception_context;
diff --git a/kernel/include/kernel/wait.h b/kernel/include/kernel/wait.h
index 490bf3e..48ffbfd 100644
--- a/kernel/include/kernel/wait.h
+++ b/kernel/include/kernel/wait.h
@@ -23,14 +23,14 @@
typedef struct wait_queue {
int magic;
int count;
- struct list_node list;
+ struct list_node heads;
} wait_queue_t;
-#define WAIT_QUEUE_INITIAL_VALUE(q) \
- { \
- .magic = WAIT_QUEUE_MAGIC, \
- .count = 0, \
- .list = LIST_INITIAL_VALUE((q).list) \
+#define WAIT_QUEUE_INITIAL_VALUE(q) \
+ { \
+ .magic = WAIT_QUEUE_MAGIC, \
+ .count = 0, \
+ .heads = LIST_INITIAL_VALUE((q).heads), \
}
/* wait queue primitive */
diff --git a/kernel/kernel/wait.c b/kernel/kernel/wait.c
index 39f6289..c8bda5b 100644
--- a/kernel/kernel/wait.c
+++ b/kernel/kernel/wait.c
@@ -41,6 +41,79 @@
return ret;
}
+// add a thread to the tail of a wait queue, sorted by priority
+static void wait_queue_insert(wait_queue_t* wait, thread_t* t) {
+ if (likely(list_is_empty(&wait->heads))) {
+ // we're the first thread
+ list_initialize(&t->queue_node);
+ list_add_head(&wait->heads, &t->wait_queue_heads_node);
+ } else {
+ int pri = t->base_priority; // TODO: get the effective priority from sched.c
+
+ // walk through the sorted list of wait queue heads
+ thread_t* temp;
+ list_for_every_entry(&wait->heads, temp, thread_t, wait_queue_heads_node) {
+ if (pri > temp->base_priority) {
+ // insert ourself here as a new queue head
+ list_initialize(&t->queue_node);
+ list_add_before(&temp->wait_queue_heads_node, &t->wait_queue_heads_node);
+ return;
+ } else if (temp->base_priority == pri) {
+ // same priority, add ourself to the tail of this queue
+ list_add_tail(&temp->queue_node, &t->queue_node);
+ list_clear_node(&t->wait_queue_heads_node);
+ return;
+ }
+ }
+
+ // we walked off the end, add ourself as a new queue head at the end
+ list_initialize(&t->queue_node);
+ list_add_tail(&wait->heads, &t->wait_queue_heads_node);
+ }
+}
+
+// remove a thread from whatever wait queue its in
+// thread must be the head of a queue
+static void remove_queue_head(thread_t* t) {
+ // are there any nodes in the queue for this priority?
+ if (list_is_empty(&t->queue_node)) {
+ // no, remove ourself from the the queue list
+ list_delete(&t->wait_queue_heads_node);
+ list_clear_node(&t->queue_node);
+ } else {
+ // there are other threads in this list, make the next thread in the queue the head
+ thread_t* newhead = list_peek_head_type(&t->queue_node, thread_t, queue_node);
+ list_delete(&t->queue_node);
+
+ // patch in the new head into the queue head list
+ list_replace_node(&t->wait_queue_heads_node, &newhead->wait_queue_heads_node);
+ }
+}
+
+// remove the head of the highest priority queue
+static thread_t* wait_queue_pop_head(wait_queue_t* wait) {
+ thread_t* t = NULL;
+
+ t = list_peek_head_type(&wait->heads, thread_t, wait_queue_heads_node);
+ if (!t)
+ return NULL;
+
+ remove_queue_head(t);
+
+ return t;
+}
+
+// remove the thread from whatever wait queue its in
+static void wait_queue_remove_thread(thread_t* t) {
+ if (!list_in_list(&t->wait_queue_heads_node)) {
+ // we're just in a queue, not a head
+ list_delete(&t->queue_node);
+ } else {
+ // we're the head of a queue
+ remove_queue_head(t);
+ }
+}
+
static zx_status_t wait_queue_block_worker(wait_queue_t* wait, zx_time_t deadline,
uint signal_mask) {
timer_t timer;
@@ -65,7 +138,7 @@
}
}
- list_add_tail(&wait->list, ¤t_thread->queue_node);
+ wait_queue_insert(wait, current_thread);
wait->count++;
current_thread->state = THREAD_BLOCKED;
current_thread->blocking_wait_queue = wait;
@@ -160,7 +233,7 @@
DEBUG_ASSERT(arch_ints_disabled());
DEBUG_ASSERT(spin_lock_held(&thread_lock));
- t = list_remove_head_type(&wait->list, thread_t, queue_node);
+ t = wait_queue_pop_head(wait);
if (t) {
wait->count--;
DEBUG_ASSERT(t->state == THREAD_BLOCKED);
@@ -188,7 +261,7 @@
DEBUG_ASSERT(arch_ints_disabled());
DEBUG_ASSERT(spin_lock_held(&thread_lock));
- t = list_remove_head_type(&wait->list, thread_t, queue_node);
+ t = wait_queue_pop_head(wait);
if (t) {
wait->count--;
DEBUG_ASSERT(t->state == THREAD_BLOCKED);
@@ -227,7 +300,8 @@
struct list_node list = LIST_INITIAL_VALUE(list);
/* pop all the threads off the wait queue into the run queue */
- while ((t = list_remove_head_type(&wait->list, thread_t, queue_node))) {
+ /* TODO: optimize with custom pop all routine */
+ while ((t = wait_queue_pop_head(wait))) {
wait->count--;
DEBUG_ASSERT(t->state == THREAD_BLOCKED);
@@ -258,7 +332,7 @@
DEBUG_ASSERT(arch_ints_disabled());
DEBUG_ASSERT(spin_lock_held(&thread_lock));
- return list_is_empty(&wait->list);
+ return wait->count == 0;
}
/**
@@ -273,7 +347,7 @@
void wait_queue_destroy(wait_queue_t* wait) {
DEBUG_ASSERT(wait->magic == WAIT_QUEUE_MAGIC);
- if (!list_is_empty(&wait->list)) {
+ if (wait->count != 0) {
panic("wait_queue_destroy() called on non-empty wait_queue_t\n");
}
@@ -304,7 +378,7 @@
DEBUG_ASSERT(t->blocking_wait_queue->magic == WAIT_QUEUE_MAGIC);
DEBUG_ASSERT(list_in_list(&t->queue_node));
- list_delete(&t->queue_node);
+ wait_queue_remove_thread(t);
t->blocking_wait_queue->count--;
t->blocking_wait_queue = NULL;
t->blocked_status = wait_queue_error;
diff --git a/system/public/zircon/listnode.h b/system/public/zircon/listnode.h
index db3e687..8d5118b 100644
--- a/system/public/zircon/listnode.h
+++ b/system/public/zircon/listnode.h
@@ -63,6 +63,17 @@
item->prev = item->next = 0;
}
+static inline void list_replace_node(list_node_t* old_node, list_node_t* new_node) {
+ // replace a spot in a list with a new node
+ // assumes old_node is part of a list and new_node is not
+ new_node->next = old_node->next;
+ new_node->prev = old_node->prev;
+ old_node->prev = old_node->next = 0;
+
+ new_node->next->prev = new_node;
+ new_node->prev->next = new_node;
+}
+
static inline list_node_t* list_remove_head(list_node_t* list) {
if (list->next != list) {
list_node_t* item = list->next;
