1 files changed, 167 insertions, 204 deletions

diff --git a/firmware/export/thread.h b/firmware/export/thread.h
index dd97ab1e83..bb1cb7cd17 100644
--- a/firmware/export/thread.h
+++ b/firmware/export/thread.h
@@ -26,21 +26,35 @@
 
 /* Priority scheduling (when enabled with HAVE_PRIORITY_SCHEDULING) works
  * by giving high priority threads more CPU time than less priority threads
- * when they need it.
- * 
+ * when they need it. Priority is differential such that the priority
+ * difference between a lower priority runnable thread and the highest priority
+ * runnable thread determines the amount of aging nescessary for the lower
+ * priority thread to be scheduled in order to prevent starvation.
+ *
  * If software playback codec pcm buffer is going down to critical, codec
- * can change it own priority to REALTIME to override user interface and
+ * can gradually raise its own priority to override user interface and
  * prevent playback skipping.
  */
+#define PRIORITY_RESERVED_HIGH   0   /* Reserved */
+#define PRIORITY_RESERVED_LOW    32  /* Reserved */
 #define HIGHEST_PRIORITY         1   /* The highest possible thread priority */
-#define LOWEST_PRIORITY          100 /* The lowest possible thread priority */
-#define PRIORITY_REALTIME        1
-#define PRIORITY_USER_INTERFACE  4   /* The main thread */
-#define PRIORITY_RECORDING       4   /* Recording thread */
-#define PRIORITY_PLAYBACK        4   /* or REALTIME when needed */
-#define PRIORITY_BUFFERING       4   /* Codec buffering thread */
-#define PRIORITY_SYSTEM          6   /* All other firmware threads */
-#define PRIORITY_BACKGROUND      8   /* Normal application threads */
+#define LOWEST_PRIORITY          31  /* The lowest possible thread priority */
+/* Realtime range reserved for threads that will not allow threads of lower
+ * priority to age and run (future expansion) */
+#define PRIORITY_REALTIME_1      1
+#define PRIORITY_REALTIME_2      2
+#define PRIORITY_REALTIME_3      3
+#define PRIORITY_REALTIME_4      4
+#define PRIORITY_REALTIME        4   /* Lowest realtime range */
+#define PRIORITY_USER_INTERFACE  16  /* The main thread */
+#define PRIORITY_RECORDING       16  /* Recording thread */
+#define PRIORITY_PLAYBACK        16  /* Variable between this and MAX */
+#define PRIORITY_PLAYBACK_MAX    5   /* Maximum allowable playback priority */
+#define PRIORITY_BUFFERING       16  /* Codec buffering thread */
+#define PRIORITY_SYSTEM          18  /* All other firmware threads */
+#define PRIORITY_BACKGROUND      20  /* Normal application threads */
+#define NUM_PRIORITIES           32
+#define PRIORITY_IDLE            32  /* Priority representative of no tasks */
 
 /* TODO: Only a minor tweak to create_thread would be needed to let
  * thread slots be caller allocated - no essential threading functionality
@@ -59,80 +73,40 @@
 
 #define DEFAULT_STACK_SIZE 0x400 /* Bytes */
 
-/**
- * "Busy" values that can be swapped into a variable to indicate
- * that the variable or object pointed to is in use by another processor
- * core. When accessed, the busy value is swapped-in while the current
- * value is atomically returned. If the swap returns the busy value,
- * the processor should retry the operation until some other value is
- * returned. When modification is finished, the new value should be
- * written which unlocks it and updates it atomically.
- *
- * Procedure:
- * while ((curr_value = swap(&variable, BUSY_VALUE)) == BUSY_VALUE);
- *
- * Modify/examine object at mem location or variable. Create "new_value"
- * as suitable.
- *
- * variable = new_value or curr_value;
- *
- * To check a value for busy and perform an operation if not:
- * curr_value = swap(&variable, BUSY_VALUE);
- *
- * if (curr_value != BUSY_VALUE)
- * {
- *     Modify/examine object at mem location or variable. Create "new_value"
- *     as suitable.
- *     variable = new_value or curr_value;
- * }
- * else
- * {
- *     Do nothing - already busy
- * }
- *
- * Only ever restore when an actual value is returned or else it could leave
- * the variable locked permanently if another processor unlocked in the
- * meantime. The next access attempt would deadlock for all processors since
- * an abandoned busy status would be left behind.
- */
-#define STATE_BUSYuptr    ((void*)UINTPTR_MAX)
-#define STATE_BUSYu8      UINT8_MAX
-#define STATE_BUSYi       INT_MIN
-
 #ifndef SIMULATOR
 /* Need to keep structures inside the header file because debug_menu
  * needs them. */
 #ifdef CPU_COLDFIRE
 struct regs
 {
-    unsigned int macsr;  /*     0 - EMAC status register */
-    unsigned int d[6];   /*  4-24 - d2-d7 */
-    unsigned int a[5];   /* 28-44 - a2-a6 */
-    void         *sp;    /*    48 - Stack pointer (a7) */
-    void         *start; /*    52 - Thread start address, or NULL when started */
+    uint32_t macsr; /*     0 - EMAC status register */
+    uint32_t d[6];  /*  4-24 - d2-d7 */
+    uint32_t a[5];  /* 28-44 - a2-a6 */
+    uint32_t sp;    /*    48 - Stack pointer (a7) */
+    uint32_t start; /*    52 - Thread start address, or NULL when started */
 };
 #elif CONFIG_CPU == SH7034
 struct regs
 {
-    unsigned int r[7];   /*  0-24 - Registers r8 thru r14 */
-    void         *sp;    /*    28 - Stack pointer (r15) */
-    void         *pr;    /*    32 - Procedure register */
-    void         *start; /*    36 - Thread start address, or NULL when started */
+    uint32_t r[7];  /*  0-24 - Registers r8 thru r14 */
+    uint32_t sp;    /*    28 - Stack pointer (r15) */
+    uint32_t pr;    /*    32 - Procedure register */
+    uint32_t start; /*    36 - Thread start address, or NULL when started */
 };
 #elif defined(CPU_ARM)
 struct regs
 {
-    unsigned int r[8];   /*  0-28 - Registers r4-r11 */
-    void         *sp;    /*    32 - Stack pointer (r13) */
-    unsigned int lr;     /*    36 - r14 (lr) */
-    void         *start; /*    40 - Thread start address, or NULL when started */
+    uint32_t r[8];  /*  0-28 - Registers r4-r11 */
+    uint32_t sp;    /*    32 - Stack pointer (r13) */
+    uint32_t lr;    /*    36 - r14 (lr) */
+    uint32_t start; /*    40 - Thread start address, or NULL when started */
 };
 #endif /* CONFIG_CPU */
 #else
 struct regs
 {
     void *t;             /* Simulator OS thread */
-    void *c;             /* Condition for blocking and sync */
+    void *s;             /* Semaphore for blocking and wakeup */
     void (*start)(void); /* Start function */
 };
 #endif /* !SIMULATOR */
@@ -154,13 +128,13 @@ enum
                             thread_thaw is called with its ID */
     THREAD_NUM_STATES,
     TIMEOUT_STATE_FIRST = STATE_SLEEPING,
-#if NUM_CORES > 1
-    STATE_BUSY = STATE_BUSYu8, /* Thread slot is being examined */
-#endif
 };
 
 #if NUM_CORES > 1
-#define THREAD_DESTRUCT ((const char *)0x84905617)
+/* Pointer value for name field to indicate thread is being killed. Using
+ * an alternate STATE_* won't work since that would interfere with operation
+ * while the thread is still running. */
+#define THREAD_DESTRUCT ((const char *)~(intptr_t)0)
 #endif
 
 /* Link information for lists thread is in */
@@ -188,7 +162,7 @@ void corelock_unlock(struct corelock *cl);
 /* Use native atomic swap/exchange instruction */
 struct corelock
 {
-    unsigned char locked;
+    volatile unsigned char locked;
 } __attribute__((packed));
 
 #define corelock_init(cl) \
@@ -207,15 +181,36 @@ struct corelock
 #define corelock_unlock(cl)
 #endif /* core locking selection */
 
-struct thread_queue
+#ifdef HAVE_PRIORITY_SCHEDULING
+struct blocker
 {
-    struct thread_entry *queue; /* list of threads waiting -
-                                   _must_ be first member */
-#if CONFIG_CORELOCK == SW_CORELOCK
-    struct corelock cl;         /* lock for atomic list operations */
-#endif
+    struct thread_entry *thread;   /* thread blocking other threads
+                                      (aka. object owner) */
+    int priority;                  /* highest priority waiter */
+    struct thread_entry * (*wakeup_protocol)(struct thread_entry *thread);
+};
+
+/* Choices of wakeup protocol */
+
+/* For transfer of object ownership by one thread to another thread by
+ * the owning thread itself (mutexes) */
+struct thread_entry *
+    wakeup_priority_protocol_transfer(struct thread_entry *thread);
+
+/* For release by owner where ownership doesn't change - other threads,
+ * interrupts, timeouts, etc. (mutex timeout, queues) */
+struct thread_entry *
+    wakeup_priority_protocol_release(struct thread_entry *thread);
+
+
+struct priority_distribution
+{
+    uint8_t  hist[NUM_PRIORITIES]; /* Histogram: Frequency for each priority */
+    uint32_t mask;                 /* Bitmask of hist entries that are not zero */
 };
 
+#endif /* HAVE_PRIORITY_SCHEDULING */
+
 /* Information kept in each thread slot
  * members are arranged according to size - largest first - in order
  * to ensure both alignment and packing at the same time.
@@ -224,88 +219,83 @@ struct thread_entry
 {
     struct regs context;       /* Register context at switch -
                                   _must_ be first member */
-    void *stack;               /* Pointer to top of stack */
+    uintptr_t *stack;          /* Pointer to top of stack */
     const char *name;          /* Thread name */
     long tmo_tick;             /* Tick when thread should be woken from
-                                  timeout */
+                                  timeout -
+                                  states: STATE_SLEEPING/STATE_BLOCKED_W_TMO */
     struct thread_list l;      /* Links for blocked/waking/running -
                                   circular linkage in both directions */
     struct thread_list tmo;    /* Links for timeout list -
-                                  Self-pointer-terminated in reverse direction,
-                                  NULL-terminated in forward direction */
-    struct thread_queue *bqp;  /* Pointer to list variable in kernel
+                                  Circular in reverse direction, NULL-terminated in
+                                  forward direction -
+                                  states: STATE_SLEEPING/STATE_BLOCKED_W_TMO */
+    struct thread_entry **bqp; /* Pointer to list variable in kernel
                                   object where thread is blocked - used
-                                  for implicit unblock and explicit wake */
-#if CONFIG_CORELOCK == SW_CORELOCK
-    struct thread_entry **bqnlp; /* Pointer to list variable in kernel
-                                    object where thread is blocked - non-locked
-                                    operations will be used */
+                                  for implicit unblock and explicit wake
+                                  states: STATE_BLOCKED/STATE_BLOCKED_W_TMO  */
+#if NUM_CORES > 1
+    struct corelock *obj_cl;   /* Object corelock where thead is blocked -
+                                  states: STATE_BLOCKED/STATE_BLOCKED_W_TMO */
 #endif
     struct thread_entry *queue; /* List of threads waiting for thread to be
                                   removed */
 #ifdef HAVE_EXTENDED_MESSAGING_AND_NAME
-    intptr_t retval;           /* Return value from a blocked operation */
+    #define HAVE_WAKEUP_EXT_CB
+    void (*wakeup_ext_cb)(struct thread_entry *thread); /* Callback that
+                                  performs special steps needed when being
+                                  forced off of an object's wait queue that
+                                  go beyond the standard wait queue removal
+                                  and priority disinheritance */
+    /* Only enabled when using queue_send for now */
+#endif
+#if defined(HAVE_EXTENDED_MESSAGING_AND_NAME) || NUM_CORES > 1
+    intptr_t retval;           /* Return value from a blocked operation/
+                                  misc. use */
 #endif
 #ifdef HAVE_PRIORITY_SCHEDULING
-    long last_run;             /* Last tick when started */
+    /* Priority summary of owned objects that support inheritance */
+    struct blocker *blocker;   /* Pointer to blocker when this thread is blocked
+                                  on an object that supports PIP -
+                                  states: STATE_BLOCKED/STATE_BLOCKED_W_TMO  */
+    struct priority_distribution pdist; /* Priority summary of owned objects
+                                  that have blocked threads and thread's own
+                                  base priority */
+    int skip_count;            /* Number of times skipped if higher priority
+                                  thread was running */
 #endif
     unsigned short stack_size; /* Size of stack in bytes */
 #ifdef HAVE_PRIORITY_SCHEDULING
-    unsigned char priority;    /* Current priority */
-    unsigned char priority_x;  /* Inherited priority - right now just a
-                                  runtime guarantee flag */
+    unsigned char base_priority; /* Base priority (set explicitly during
+                                  creation or thread_set_priority) */
+    unsigned char priority;    /* Scheduled priority (higher of base or
+                                  all threads blocked by this one) */
 #endif
     unsigned char state;       /* Thread slot state (STATE_*) */
-#if NUM_CORES > 1
-    unsigned char core;        /* The core to which thread belongs */
-#endif
 #ifdef HAVE_SCHEDULER_BOOSTCTRL
-    unsigned char boosted;     /* CPU frequency boost flag */
+    unsigned char cpu_boost;   /* CPU frequency boost flag */
 #endif
-#if CONFIG_CORELOCK == SW_CORELOCK
-    struct corelock cl;        /* Corelock to lock thread slot */
+#if NUM_CORES > 1
+    unsigned char core;        /* The core to which thread belongs */
+    struct corelock waiter_cl; /* Corelock for thread_wait */
+    struct corelock slot_cl;   /* Corelock to lock thread slot */
 #endif
 };
 
 #if NUM_CORES > 1
 /* Operations to be performed just before stopping a thread and starting
    a new one if specified before calling switch_thread */
-#define TBOP_UNLOCK_LIST     0x01 /* Set a pointer variable address var_ptrp */
-#if CONFIG_CORELOCK == CORELOCK_SWAP
-#define TBOP_SET_VARi        0x02 /* Set an int at address var_ip */
-#define TBOP_SET_VARu8       0x03 /* Set an unsigned char at address var_u8p */
-#define TBOP_VAR_TYPE_MASK   0x03 /* Mask for variable type*/
-#endif /* CONFIG_CORELOCK */
-#define TBOP_UNLOCK_CORELOCK 0x04
-#define TBOP_UNLOCK_THREAD   0x08 /* Unlock a thread's slot */
-#define TBOP_UNLOCK_CURRENT  0x10 /* Unlock the current thread's slot */
-#define TBOP_SWITCH_CORE     0x20 /* Call the core switch preparation routine */
+enum
+{
+    TBOP_CLEAR = 0,       /* No operation to do */
+    TBOP_UNLOCK_CORELOCK, /* Unlock a corelock variable */
+    TBOP_SWITCH_CORE,     /* Call the core switch preparation routine */
+};
 
 struct thread_blk_ops
 {
-#if CONFIG_CORELOCK != SW_CORELOCK
-    union
-    {
-        int var_iv;                   /* int variable value to set */
-        uint8_t var_u8v;              /* unsigned char valur to set */
-        struct thread_entry *list_v;  /* list pointer queue value to set */
-    };
-#endif
-    union
-    {
-#if CONFIG_CORELOCK != SW_CORELOCK
-        int *var_ip;                  /* pointer to int variable */
-        uint8_t *var_u8p;             /* pointer to unsigned char varuable */
-#endif
-        struct thread_queue *list_p;  /* pointer to list variable */
-    };
-#if CONFIG_CORELOCK == SW_CORELOCK
-    struct corelock *cl_p;            /* corelock to unlock */
-    struct thread_entry *thread;      /* thread to unlock */
-#elif CONFIG_CORELOCK == CORELOCK_SWAP
-    unsigned char state;              /* new thread state (performs unlock) */
-#endif /* SOFTWARE_CORELOCK */
-    unsigned char flags;    /* TBOP_* flags */
+    struct corelock *cl_p;    /* pointer to corelock */
+    unsigned char    flags;   /* TBOP_* flags */
 };
 #endif /* NUM_CORES > 1 */
 
@@ -316,28 +306,30 @@ struct core_entry
 {
     /* "Active" lists - core is constantly active on these and are never
        locked and interrupts do not access them */
-    struct thread_entry *running;  /* threads that are running */
+    struct thread_entry *running;  /* threads that are running (RTR) */
     struct thread_entry *timeout;  /* threads that are on a timeout before
                                       running again */
-    /* "Shared" lists - cores interact in a synchronized manner - access
-       is locked between cores and interrupts */
-    struct thread_queue  waking;   /* intermediate locked list that
-                                      hold threads other core should wake up
-                                      on next task switch */
+    struct thread_entry *block_task; /* Task going off running list */
+#ifdef HAVE_PRIORITY_SCHEDULING
+    struct priority_distribution rtr; /* Summary of running and ready-to-run
+                                         threads */
+#endif
     long next_tmo_check;           /* soonest time to check tmo threads */
 #if NUM_CORES > 1
     struct thread_blk_ops blk_ops; /* operations to perform when
                                       blocking a thread */
-#endif /* NUM_CORES */
 #ifdef HAVE_PRIORITY_SCHEDULING
-    unsigned char highest_priority;
+    struct corelock rtr_cl;        /* Lock for rtr list */
 #endif
+#endif /* NUM_CORES */
 };
 
 #ifdef HAVE_PRIORITY_SCHEDULING
 #define IF_PRIO(...)    __VA_ARGS__
+#define IFN_PRIO(...)
 #else
 #define IF_PRIO(...)
+#define IFN_PRIO(...)   __VA_ARGS__
 #endif
 
 /* Macros generate better code than an inline function is this case */
@@ -464,13 +456,18 @@ struct core_entry
 void core_idle(void);
 void core_wake(IF_COP_VOID(unsigned int core));
 
+/* Initialize the scheduler */
+void init_threads(void);
+
+/* Allocate a thread in the scheduler */
 #define CREATE_THREAD_FROZEN   0x00000001 /* Thread is frozen at create time */
 struct thread_entry*
-    create_thread(void (*function)(void), void* stack, int stack_size,
+    create_thread(void (*function)(void), void* stack, size_t stack_size,
                   unsigned flags, const char *name
                   IF_PRIO(, int priority)
                           IF_COP(, unsigned int core));
 
+/* Set and clear the CPU frequency boost flag for the calling thread */
 #ifdef HAVE_SCHEDULER_BOOSTCTRL
 void trigger_cpu_boost(void);
 void cancel_cpu_boost(void);
@@ -478,86 +475,52 @@ void cancel_cpu_boost(void);
 #define trigger_cpu_boost()
 #define cancel_cpu_boost()
 #endif
+/* Make a frozed thread runnable (when started with CREATE_THREAD_FROZEN).
+ * Has no effect on a thread not frozen. */
 void thread_thaw(struct thread_entry *thread);
+/* Wait for a thread to exit */
 void thread_wait(struct thread_entry *thread);
+/* Exit the current thread */
+void thread_exit(void);
+#if defined(DEBUG) || defined(ROCKBOX_HAS_LOGF)
+#define ALLOW_REMOVE_THREAD
+/* Remove a thread from the scheduler */
 void remove_thread(struct thread_entry *thread);
-void switch_thread(struct thread_entry *old);
-void sleep_thread(int ticks);
+#endif
 
-/**
- * Setup to allow using thread queues as locked or non-locked without speed
- * sacrifices in both core locking types.
- *
- * The blocking/waking function inline two different version of the real
- * function into the stubs when a software or other separate core locking
- * mechanism is employed.
- *
- * When a simple test-and-set or similar instruction is available, locking
- * has no cost and so one version is used and the internal worker is called
- * directly.
- *
- * CORELOCK_NONE is treated the same as when an atomic instruction can be
- * used.
- */
+/* Switch to next runnable thread */
+void switch_thread(void);
+/* Blocks a thread for at least the specified number of ticks (0 = wait until
+ * next tick) */
+void sleep_thread(int ticks);
+/* Indefinitely blocks the current thread on a thread queue */
+void block_thread(struct thread_entry *current);
+/* Blocks the current thread on a thread queue until explicitely woken or
+ * the timeout is reached */
+void block_thread_w_tmo(struct thread_entry *current, int timeout);
+
+/* Return bit flags for thread wakeup */
+#define THREAD_NONE     0x0 /* No thread woken up (exclusive) */
+#define THREAD_OK       0x1 /* A thread was woken up */
+#define THREAD_SWITCH   0x2 /* Task switch recommended (one or more of
+                               higher priority than current were woken) */
 
-/* Blocks the current thread on a thread queue */
-#if CONFIG_CORELOCK == SW_CORELOCK
-void block_thread(struct thread_queue *tq);
-void block_thread_no_listlock(struct thread_entry **list);
-#else
-void _block_thread(struct thread_queue *tq);
-static inline void block_thread(struct thread_queue *tq)
-    { _block_thread(tq); }
-static inline void block_thread_no_listlock(struct thread_entry **list)
-    { _block_thread((struct thread_queue *)list); }
-#endif /* CONFIG_CORELOCK */
-
-/* Blocks the current thread on a thread queue for a max amount of time
- * There is no "_no_listlock" version because timeout blocks without sync on
- * the blocking queues is not permitted since either core could access the
- * list at any time to do an implicit wake. In other words, objects with
- * timeout support require lockable queues. */
-void block_thread_w_tmo(struct thread_queue *tq, int timeout);
-
-/* Wakes up the thread at the head of the queue */
-#define THREAD_WAKEUP_NONE    ((struct thread_entry *)NULL)
-#define THREAD_WAKEUP_MISSING ((struct thread_entry *)(NULL+1))
-#if CONFIG_CORELOCK == SW_CORELOCK
-struct thread_entry * wakeup_thread(struct thread_queue *tq);
-struct thread_entry * wakeup_thread_no_listlock(struct thread_entry **list);
-#else
-struct thread_entry * _wakeup_thread(struct thread_queue *list);
-static inline struct thread_entry * wakeup_thread(struct thread_queue *tq)
-    { return _wakeup_thread(tq); }
-static inline struct thread_entry * wakeup_thread_no_listlock(struct thread_entry **list)
-    { return _wakeup_thread((struct thread_queue *)list); }
-#endif /* CONFIG_CORELOCK */
-
-/* Initialize a thread_queue object. */
-static inline void thread_queue_init(struct thread_queue *tq)
-    { tq->queue = NULL; IF_SWCL(corelock_init(&tq->cl);) }
 /* A convenience function for waking an entire queue of threads. */
-static inline void thread_queue_wake(struct thread_queue *tq)
-    { while (wakeup_thread(tq) != NULL); }
-/* The no-listlock version of thread_queue_wake() */
-static inline void thread_queue_wake_no_listlock(struct thread_entry **list)
-    { while (wakeup_thread_no_listlock(list) != NULL); }
+unsigned int thread_queue_wake(struct thread_entry **list);
+
+/* Wakeup a thread at the head of a list */
+unsigned int wakeup_thread(struct thread_entry **list);
 
 #ifdef HAVE_PRIORITY_SCHEDULING
 int thread_set_priority(struct thread_entry *thread, int priority);
 int thread_get_priority(struct thread_entry *thread);
-/* Yield that guarantees thread execution once per round regardless of
-   thread's scheduler priority - basically a transient realtime boost
-   without altering the scheduler's thread precedence. */
-void priority_yield(void);
-#else
-#define priority_yield  yield
 #endif /* HAVE_PRIORITY_SCHEDULING */
 #if NUM_CORES > 1
 unsigned int switch_core(unsigned int new_core);
 #endif
 struct thread_entry * thread_get_current(void);
-void init_threads(void);
+
+/* Debugging info - only! */
 int thread_stack_usage(const struct thread_entry *thread);
 #if NUM_CORES > 1
 int idle_stack_usage(unsigned int core);