stmhal: Implement a proper thread scheduler.

This patch changes the threading implementation from simple round-robin
with busy waits on mutexs, to proper scheduling whereby threads that are
waiting on a mutex are only scheduled when the mutex becomes available.

1 files changed, 157 insertions, 22 deletions

diff --git a/stmhal/pybthread.c b/stmhal/pybthread.c
index 9f9f82a45..51e9a738d 100644
--- a/stmhal/pybthread.c
+++ b/stmhal/pybthread.c
@@ -34,29 +34,80 @@
 
 #if MICROPY_PY_THREAD
 
-int pyb_thread_enabled;
-pyb_thread_t *pyb_thread_cur;
+#define PYB_MUTEX_UNLOCKED ((void*)0)
+#define PYB_MUTEX_LOCKED ((void*)1)
+
+extern void __fatal_error(const char*);
+
+volatile int pyb_thread_enabled;
+pyb_thread_t *volatile pyb_thread_all;
+pyb_thread_t *volatile pyb_thread_cur;
+
+static inline void pyb_thread_add_to_runable(pyb_thread_t *thread) {
+    thread->run_prev = pyb_thread_cur->run_prev;
+    thread->run_next = pyb_thread_cur;
+    pyb_thread_cur->run_prev->run_next = thread;
+    pyb_thread_cur->run_prev = thread;
+}
+
+static inline void pyb_thread_remove_from_runable(pyb_thread_t *thread) {
+    if (thread->run_next == thread) {
+        __fatal_error("deadlock");
+    }
+    thread->run_prev->run_next = thread->run_next;
+    thread->run_next->run_prev = thread->run_prev;
+}
 
 void pyb_thread_init(pyb_thread_t *thread) {
+    pyb_thread_enabled = 0;
+    pyb_thread_all = thread;
     pyb_thread_cur = thread;
-    pyb_thread_cur->sp = NULL; // will be set when this thread switches out
-    pyb_thread_cur->local_state = 0; // will be set by mp_thread_init
-    pyb_thread_cur->arg = NULL;
-    pyb_thread_cur->stack = &_heap_end;
-    pyb_thread_cur->stack_len = ((uint32_t)&_estack - (uint32_t)&_heap_end) / sizeof(uint32_t);
-    pyb_thread_cur->prev = thread;
-    pyb_thread_cur->next = thread;
+    thread->sp = NULL; // will be set when this thread switches out
+    thread->local_state = 0; // will be set by mp_thread_init
+    thread->arg = NULL;
+    thread->stack = &_heap_end;
+    thread->stack_len = ((uint32_t)&_estack - (uint32_t)&_heap_end) / sizeof(uint32_t);
+    thread->all_next = NULL;
+    thread->run_prev = thread;
+    thread->run_next = thread;
+    thread->queue_next = NULL;
+}
+
+void pyb_thread_deinit() {
+    uint32_t irq_state = disable_irq();
+    pyb_thread_enabled = 0;
+    pyb_thread_all = pyb_thread_cur;
+    pyb_thread_cur->all_next = NULL;
+    pyb_thread_cur->run_prev = pyb_thread_cur;
+    pyb_thread_cur->run_next = pyb_thread_cur;
+    enable_irq(irq_state);
 }
 
 STATIC void pyb_thread_terminate(void) {
-    uint32_t irq_state = raise_irq_pri(IRQ_PRI_PENDSV);
-    pyb_thread_cur->prev->next = pyb_thread_cur->next;
-    pyb_thread_cur->next->prev = pyb_thread_cur->prev;
-    if (pyb_thread_cur->next == pyb_thread_cur->prev) {
+    uint32_t irq_state = disable_irq();
+    pyb_thread_t *thread = pyb_thread_cur;
+    // take current thread off the run list
+    pyb_thread_remove_from_runable(thread);
+    // take current thread off the list of all threads
+    for (pyb_thread_t **n = (pyb_thread_t**)&pyb_thread_all;; n = &(*n)->all_next) {
+        if (*n == thread) {
+            *n = thread->all_next;
+            break;
+        }
+    }
+    // clean pointers as much as possible to help GC
+    thread->all_next = NULL;
+    thread->queue_next = NULL;
+    thread->stack = NULL;
+    if (pyb_thread_all->all_next == NULL) {
+        // only 1 thread left
         pyb_thread_enabled = 0;
     }
-    restore_irq_pri(irq_state);
-    pyb_thread_yield(); // should not return
+    // thread switch will occur after we enable irqs
+    SCB->ICSR = SCB_ICSR_PENDSVSET_Msk;
+    enable_irq(irq_state);
+    // should not return
+    __fatal_error("could not terminate");
 }
 
 uint32_t pyb_thread_new(pyb_thread_t *thread, void *stack, size_t stack_len, void *entry, void *arg) {
@@ -77,21 +128,105 @@ uint32_t pyb_thread_new(pyb_thread_t *thread, void *stack, size_t stack_len, voi
     thread->arg = arg;
     thread->stack = stack;
     thread->stack_len = stack_len;
-    uint32_t irq_state = raise_irq_pri(IRQ_PRI_PENDSV);
+    thread->queue_next = NULL;
+    uint32_t irq_state = disable_irq();
     pyb_thread_enabled = 1;
-    thread->next = pyb_thread_cur->next;
-    thread->prev = pyb_thread_cur;
-    pyb_thread_cur->next->prev = thread;
-    pyb_thread_cur->next = thread;
-    restore_irq_pri(irq_state);
+    thread->all_next = pyb_thread_all;
+    pyb_thread_all = thread;
+    pyb_thread_add_to_runable(thread);
+    enable_irq(irq_state);
     return (uint32_t)thread; // success
 }
 
+void pyb_thread_dump(void) {
+    if (!pyb_thread_enabled) {
+        printf("THREAD: only main thread\n");
+    } else {
+        printf("THREAD:\n");
+        for (pyb_thread_t *th = pyb_thread_all; th != NULL; th = th->all_next) {
+            bool runable = false;
+            for (pyb_thread_t *th2 = pyb_thread_cur;; th2 = th2->run_next) {
+                if (th == th2) {
+                    runable = true;
+                    break;
+                }
+                if (th2->run_next == pyb_thread_cur) {
+                    break;
+                }
+            }
+            printf("    id=%p sp=%p sz=%u", th, th->stack, th->stack_len);
+            if (runable) {
+                printf(" (runable)");
+            }
+            printf("\n");
+        }
+    }
+}
+
 // should only be called from pendsv_isr_handler
 void *pyb_thread_next(void *sp) {
     pyb_thread_cur->sp = sp;
-    pyb_thread_cur = pyb_thread_cur->next;
+    pyb_thread_cur = pyb_thread_cur->run_next;
+    pyb_thread_cur->timeslice = 4; // in milliseconds
     return pyb_thread_cur->sp;
 }
 
+void pyb_mutex_init(pyb_mutex_t *m) {
+    *m = PYB_MUTEX_UNLOCKED;
+}
+
+int pyb_mutex_lock(pyb_mutex_t *m, int wait) {
+    uint32_t irq_state = disable_irq();
+    if (*m == PYB_MUTEX_UNLOCKED) {
+        // mutex is available
+        *m = PYB_MUTEX_LOCKED;
+        enable_irq(irq_state);
+    } else {
+        // mutex is locked
+        if (!wait) {
+            enable_irq(irq_state);
+            return 0; // failed to lock mutex
+        }
+        if (*m == PYB_MUTEX_LOCKED) {
+            *m = pyb_thread_cur;
+        } else {
+            for (pyb_thread_t *n = *m;; n = n->queue_next) {
+                if (n->queue_next == NULL) {
+                    n->queue_next = pyb_thread_cur;
+                    break;
+                }
+            }
+        }
+        pyb_thread_cur->queue_next = NULL;
+        // take current thread off the run list
+        pyb_thread_remove_from_runable(pyb_thread_cur);
+        // thread switch will occur after we enable irqs
+        SCB->ICSR = SCB_ICSR_PENDSVSET_Msk;
+        enable_irq(irq_state);
+        // when we come back we have the mutex
+    }
+    return 1; // have mutex
+}
+
+void pyb_mutex_unlock(pyb_mutex_t *m) {
+    uint32_t irq_state = disable_irq();
+    if (*m == PYB_MUTEX_LOCKED) {
+        // no threads are blocked on the mutex
+        *m = PYB_MUTEX_UNLOCKED;
+    } else {
+        // at least one thread is blocked on this mutex
+        pyb_thread_t *th = *m;
+        if (th->queue_next == NULL) {
+            // no other threads are blocked
+            *m = PYB_MUTEX_LOCKED;
+        } else {
+            // at least one other thread is still blocked
+            *m = th->queue_next;
+        }
+        // put unblocked thread on runable list
+        pyb_thread_add_to_runable(th);
+    }
+    enable_irq(irq_state);
+}
+
 #endif // MICROPY_PY_THREAD