Base scheduler queues off linked lists and do cleanup/consolidation

Abstracts threading from itself a bit, changes the way its queues are
handled and does type hiding for that as well.

Do alot here due to already required major brain surgery.

Threads may now be on a run queue and a wait queue simultaneously so
that the expired timer only has to wake the thread but not remove it
from the wait queue which simplifies the implicit wake handling.

List formats change for wait queues-- doubly-linked, not circular.
Timeout queue is now singly-linked. The run queue is still circular
as before.

Adds a better thread slot allocator that may keep the slot marked as
used regardless of the thread state. Assists in dumping special tasks
that switch_thread was tasked to perform (blocking tasks).

Deletes alot of code yet surprisingly, gets larger than expected.
Well, I'm not not minding that for the time being-- omlettes and break
a few eggs and all that.

Change-Id: I0834d7bb16b2aecb2f63b58886eeda6ae4f29d59

5 files changed, 32 insertions, 17 deletions

diff --git a/firmware/kernel/include/mrsw_lock.h b/firmware/kernel/include/mrsw_lock.h
index d919f7be26..7511f87e93 100644
--- a/firmware/kernel/include/mrsw_lock.h
+++ b/firmware/kernel/include/mrsw_lock.h
@@ -39,10 +39,9 @@
  */
 struct mrsw_lock
 {
-    int volatile count; /* rd/wr counter; >0 = reader(s), <0 = writer */
-    struct thread_entry *queue;
-    struct blocker_splay splay; /* priority inheritance info
-                                   for waiters */
+    int volatile         count; /* counter; >0 = reader(s), <0 = writer */
+    struct __wait_queue  queue; /* waiter list */
+    struct blocker_splay splay; /* priority inheritance/owner info  */
     uint8_t rdrecursion[MAXTHREADS]; /* per-thread reader recursion counts */
     IF_COP( struct corelock cl; )
 };
diff --git a/firmware/kernel/include/mutex.h b/firmware/kernel/include/mutex.h
index 72736ec8fd..b74bfe23f5 100644
--- a/firmware/kernel/include/mutex.h
+++ b/firmware/kernel/include/mutex.h
@@ -26,13 +26,13 @@
 
 struct mutex
 {
-    struct thread_entry *queue;   /* waiter list */
-    int recursion;                /* lock owner recursion count */
-    struct blocker blocker;       /* priority inheritance info
-                                     for waiters and owner*/
-    IF_COP( struct corelock cl; ) /* multiprocessor sync */
+    struct __wait_queue queue;     /* waiter list */
+    int                 recursion; /* lock owner recursion count */
+    struct blocker      blocker;   /* priority inheritance info
+                                      for waiters and owner*/
+    IF_COP( struct corelock cl; )  /* multiprocessor sync */
 #ifdef HAVE_PRIORITY_SCHEDULING
-    bool no_preempt;
+    bool                no_preempt;
 #endif
 };
 
diff --git a/firmware/kernel/include/queue.h b/firmware/kernel/include/queue.h
index 3f24598d5b..afee4c90ff 100644
--- a/firmware/kernel/include/queue.h
+++ b/firmware/kernel/include/queue.h
@@ -88,7 +88,7 @@ struct queue_sender_list
     /* If non-NULL, there is a thread waiting for the corresponding event */
     /* Must be statically allocated to put in non-cached ram. */
     struct thread_entry *senders[QUEUE_LENGTH]; /* message->thread map */
-    struct thread_entry *list;                  /* list of senders in map */
+    struct __wait_queue list;                   /* list of senders in map */
     /* Send info for last message dequeued or NULL if replied or not sent */
     struct thread_entry * volatile curr_sender;
 #ifdef HAVE_PRIORITY_SCHEDULING
@@ -108,7 +108,7 @@ struct queue_sender_list
 
 struct event_queue
 {
-    struct thread_entry *queue;         /* waiter list */
+    struct __wait_queue queue;          /* waiter list */
     struct queue_event events[QUEUE_LENGTH]; /* list of events */
     unsigned int volatile read;         /* head of queue */
     unsigned int volatile write;        /* tail of queue */
diff --git a/firmware/kernel/include/semaphore.h b/firmware/kernel/include/semaphore.h
index 16095d9c2d..1d604a4e76 100644
--- a/firmware/kernel/include/semaphore.h
+++ b/firmware/kernel/include/semaphore.h
@@ -26,10 +26,10 @@
 
 struct semaphore
 {
-    struct thread_entry *queue;         /* Waiter list */
-    int volatile count;                 /* # of waits remaining before unsignaled */
-    int max;                            /* maximum # of waits to remain signaled */
-    IF_COP( struct corelock cl; )       /* multiprocessor sync */
+    struct __wait_queue queue;    /* Waiter list */
+    int volatile        count;    /* # of waits remaining before unsignaled */
+    int                 max;      /* maximum # of waits to remain signaled */
+    IF_COP( struct corelock cl; ) /* multiprocessor sync */
 };
 
 extern void semaphore_init(struct semaphore *s, int max, int start);
diff --git a/firmware/kernel/include/thread.h b/firmware/kernel/include/thread.h
index 5a8bff0107..dfb632785e 100644
--- a/firmware/kernel/include/thread.h
+++ b/firmware/kernel/include/thread.h
@@ -26,6 +26,7 @@
 #include <stdbool.h>
 #include "config.h"
 #include "gcc_extensions.h"
+#include "linked_list.h"
 #include "bitarray.h"
 #include "corelock.h"
 
@@ -52,7 +53,7 @@
 #define PRIORITY_REALTIME_4      4
 #define PRIORITY_REALTIME        4   /* Lowest realtime range */
 #define PRIORITY_BUFFERING       15  /* Codec buffering thread */
-#define PRIORITY_USER_INTERFACE  16  /* The main thread */
+#define PRIORITY_USER_INTERFACE  16  /* For most UI thrads */
 #define PRIORITY_RECORDING       16  /* Recording thread */
 #define PRIORITY_PLAYBACK        16  /* Variable between this and MAX */
 #define PRIORITY_PLAYBACK_MAX    5   /* Maximum allowable playback priority */
@@ -61,6 +62,7 @@
 #define NUM_PRIORITIES           32
 #define PRIORITY_IDLE            32  /* Priority representative of no tasks */
 
+#define PRIORITY_MAIN_THREAD     PRIORITY_USER_INTERFACE
 #define IO_PRIORITY_IMMEDIATE    0
 #define IO_PRIORITY_BACKGROUND   32
 
@@ -108,6 +110,9 @@ extern unsigned sleep(unsigned ticks);
 #define IFN_PRIO(...)   __VA_ARGS__
 #endif
 
+#define __wait_queue      lld_head
+#define __wait_queue_node lld_node
+
 /* Basic structure describing the owner of an object */
 struct blocker
 {
@@ -168,6 +173,7 @@ int thread_get_priority(unsigned int thread_id);
 void thread_set_io_priority(unsigned int thread_id, int io_priority);
 int thread_get_io_priority(unsigned int thread_id);
 #endif /* HAVE_IO_PRIORITY */
+
 #if NUM_CORES > 1
 unsigned int switch_core(unsigned int new_core);
 #endif
@@ -186,11 +192,21 @@ int core_get_debug_info(unsigned int core, struct core_debug_info *infop);
 
 #endif /* NUM_CORES */
 
+#ifdef HAVE_SDL_THREADS
+#define IF_SDL(x...) x
+#define IFN_SDL(x...)
+#else
+#define IF_SDL(x...)
+#define IFN_SDL(x...) x
+#endif
+
 struct thread_debug_info
 {
     char         statusstr[4];
     char         name[32];
+#ifndef HAVE_SDL_THREADS
     unsigned int stack_usage;
+#endif
 #if NUM_CORES > 1
     unsigned int core;
 #endif