[coreboot-gerrit] New patch to review for coreboot: dfdfae8 x86: implement cooperative multi-tasking
Aaron Durbin (adurbin@google.com)
gerrit at coreboot.org
Fri May 3 23:27:07 CEST 2013
Aaron Durbin (adurbin at google.com) just uploaded a new patch set to gerrit, which you can find at http://review.coreboot.org/3192
-gerrit
commit dfdfae88ec05b81c9c43185e3b0ec22a0f8948a9
Author: Aaron Durbin <adurbin at chromium.org>
Date: Fri May 3 16:03:20 2013 -0500
x86: implement cooperative multi-tasking
The cooperative multitasking support allows for callbacks
and the boostate machine to be ran cooperatively. There is
a concept of threads, but they aren't threads in the traditional
sense. They are really a container for execution context by way
of the stack. A configurable number of threads are available to the
system. The cooperative scheduling works by using udelay() as an exit
point to start resume another thread of execution. The "main thread"
never yields unless running timers or new threads. The main thread
is the initial thread running on the boot cpu. In this manner it is
possible to still write serialized code sequences without having to
hand-write a state machine using the existing callbacks.
Change-Id: I9e73495a1814a0b8a8dfc9f265cd83c29a305f13
Signed-off-by: Aaron Durbin <adurbin at chromium.org>
---
src/Kconfig | 16 ++
src/arch/x86/include/arch/cpu.h | 5 +
src/arch/x86/lib/Makefile.inc | 2 +
src/arch/x86/lib/c_start.S | 9 +
src/arch/x86/lib/thread.c | 330 +++++++++++++++++++++++++++++++++++++
src/arch/x86/lib/thread_switch.S | 58 +++++++
src/cpu/intel/haswell/mp_init.c | 2 +
src/cpu/x86/lapic/apic_timer.c | 4 +
src/cpu/x86/lapic/lapic_cpu_init.c | 2 +
src/cpu/x86/tsc/delay_tsc.c | 4 +
src/include/thread.h | 60 +++++++
src/lib/hardwaremain.c | 14 +-
src/lib/timer_queue.c | 10 +-
13 files changed, 512 insertions(+), 4 deletions(-)
diff --git a/src/Kconfig b/src/Kconfig
index ce7f400..9fde0e4 100644
--- a/src/Kconfig
+++ b/src/Kconfig
@@ -324,6 +324,22 @@ config TIMER_QUEUE
help
Provide a timer queue for performing time-based callbacks.
+config COOP_MULTITASKING
+ def_bool n
+ depends on TIMER_QUEUE && ARCH_X86
+ help
+ Cooperative multitasking allows callbacks to be multiplexed on the
+ main thread of ramstage. With this enabled it allows for multiple
+ execution paths to take place when they have udelay() calls within
+ their code.
+
+config NUM_THREADS
+ int
+ default 4
+ depends on COOP_MULTITASKING
+ help
+ How many execution threads to cooperatively multitask with.
+
config HIGH_SCRATCH_MEMORY_SIZE
hex
default 0x0
diff --git a/src/arch/x86/include/arch/cpu.h b/src/arch/x86/include/arch/cpu.h
index a3555d8..4a31088 100644
--- a/src/arch/x86/include/arch/cpu.h
+++ b/src/arch/x86/include/arch/cpu.h
@@ -164,9 +164,14 @@ struct cpu_driver *find_cpu_driver(struct device *cpu);
#include <arch/io.h>
#endif
+struct thread;
+
struct cpu_info {
device_t cpu;
unsigned int index;
+#if CONFIG_COOP_MULTITASKING
+ struct thread *thread;
+#endif
};
static inline struct cpu_info *cpu_info(void)
diff --git a/src/arch/x86/lib/Makefile.inc b/src/arch/x86/lib/Makefile.inc
index 82f4e62..7cdd3c6 100644
--- a/src/arch/x86/lib/Makefile.inc
+++ b/src/arch/x86/lib/Makefile.inc
@@ -9,6 +9,8 @@ ramstage-y += memset.c
ramstage-y += memcpy.c
ramstage-y += ebda.c
ramstage-y += rom_media.c
+ramstage-$(CONFIG_COOP_MULTITASKING) += thread.c
+ramstage-$(CONFIG_COOP_MULTITASKING) += thread_switch.S
romstage-$(CONFIG_EARLY_CONSOLE) += romstage_console.c
romstage-y += cbfs_and_run.c
diff --git a/src/arch/x86/lib/c_start.S b/src/arch/x86/lib/c_start.S
index 32af0cc..e9d072f 100644
--- a/src/arch/x86/lib/c_start.S
+++ b/src/arch/x86/lib/c_start.S
@@ -10,6 +10,11 @@
_stack:
.space CONFIG_MAX_CPUS*CONFIG_STACK_SIZE
_estack:
+#if CONFIG_COOP_MULTITASKING
+.global thread_stacks
+thread_stacks:
+.space CONFIG_STACK_SIZE*CONFIG_NUM_THREADS
+#endif
.section ".textfirst", "ax", @progbits
.code32
@@ -45,6 +50,10 @@ _start:
/* set new stack */
movl $_estack, %esp
+#if CONFIG_COOP_MULTITASKING
+ /* Push the thread pointer. */
+ pushl $0
+#endif
/* Push the cpu index and struct cpu */
pushl $0
pushl $0
diff --git a/src/arch/x86/lib/thread.c b/src/arch/x86/lib/thread.c
new file mode 100644
index 0000000..bcc297c
--- /dev/null
+++ b/src/arch/x86/lib/thread.c
@@ -0,0 +1,330 @@
+/*
+ * This file is part of the coreboot project.
+ *
+ * Copyright (C) 2013 Google, Inc.
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; version 2 of the License.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+#include <stddef.h>
+#include <stdint.h>
+#include <arch/cpu.h>
+#include <console/console.h>
+#include <thread.h>
+
+#define TOTAL_NUM_THREADS (CONFIG_NUM_THREADS + 1)
+extern void asmlinkage switch_to_thread(uintptr_t new_stack,
+ uintptr_t *saved_stack);
+extern char thread_stacks[CONFIG_NUM_THREADS*CONFIG_STACK_SIZE];
+
+struct thread {
+ int id;
+ uintptr_t saved_stack;
+ char *stack_top;
+ struct thread *next;
+ struct timeout_callback tocb;
+ void (*entry)(void *);
+ void *entry_arg;
+ int can_yield;
+};
+
+struct pushad_regs {
+ uint32_t edi;
+ uint32_t esi;
+ uint32_t ebp;
+ uint32_t esp;
+ uint32_t ebx;
+ uint32_t edx;
+ uint32_t ecx;
+ uint32_t eax;
+};
+
+static struct thread *runnable_threads;
+static struct thread *free_threads;
+static struct thread all_threads[TOTAL_NUM_THREADS];
+
+static inline struct cpu_info *thread_cpu_info(const struct thread *t)
+{
+ return (void *)(t->stack_top - sizeof(struct cpu_info));
+}
+
+static inline int cpu_info_can_switch(const struct cpu_info *ci)
+{
+ return (ci->thread != NULL);
+}
+
+static inline int thread_is_main(const struct thread *t)
+{
+ return t->id == 0;
+}
+
+/* Assumes current cpu info can switch. */
+static struct thread *cpu_info_to_thread(const struct cpu_info *ci)
+{
+ return ci->thread;
+}
+
+static inline struct thread *get_main_thread(void)
+{
+ return &all_threads[0];
+}
+
+static inline struct thread *current_thread(void)
+{
+ return cpu_info_to_thread(cpu_info());
+}
+
+static inline int thread_list_empty(struct thread **list)
+{
+ return *list == NULL;
+}
+
+static inline struct thread *pop_thread(struct thread **list)
+{
+ struct thread *t;
+
+ t = *list;
+ *list = t->next;
+ t->next = NULL;
+ return t;
+}
+
+static inline void push_thread(struct thread **list, struct thread *t)
+{
+ t->next = *list;
+ *list = t;
+}
+
+static inline struct thread *get_free_thread(void)
+{
+ struct thread *t;
+ struct cpu_info *ci;
+ struct cpu_info *new_ci;
+
+ if (thread_list_empty(&free_threads))
+ return NULL;
+
+ t = pop_thread(&free_threads);
+
+ ci = cpu_info();
+
+ /* The BSP is the only one that can switch threads. Therefore, only
+ * initialize the device_t and thread pointer. */
+ new_ci = thread_cpu_info(t);
+ new_ci->cpu = ci->cpu;
+ new_ci->thread = t;
+
+ return t;
+}
+
+static inline void free_thread(struct thread *t)
+{
+ push_thread(&free_threads, t);
+}
+
+void threads_initialize(void)
+{
+ int i;
+ struct thread *t;
+ char *stack_top;
+ struct cpu_info *ci;
+
+ /* Initialize the BSP thread first. */
+ t = &all_threads[0];
+ ci = cpu_info();
+ ci->thread = t;
+ t->stack_top = (void *)&ci[1];
+ t->id = 0;
+
+ stack_top = &thread_stacks[CONFIG_STACK_SIZE];
+ for (i = 1; i < TOTAL_NUM_THREADS; i++) {
+ t = &all_threads[i];
+ t->stack_top = stack_top;
+ t->id = i;
+ stack_top += CONFIG_STACK_SIZE;
+ free_thread(t);
+ }
+}
+
+#if 0
+static void debug_thread_dump(const char *str, const struct thread *t,
+ uintptr_t stack_start)
+{
+ printk(BIOS_DEBUG, "%s: thread[%d] stack @%x -> %p\n", str, t->id,
+ stack_start, t->stack_top);
+
+ int i;
+ uint32_t *slot;
+ uint32_t *end;
+
+ slot = (void *)t->stack_top;
+ slot--;
+ end = (void *)stack_start;
+ end--;
+ i = (uintptr_t)t->stack_top - stack_start;
+ i -= sizeof(slot);
+
+ while (slot != end) {
+ printk(BIOS_DEBUG, "%04x: %08x\n", i, *slot);
+ slot--;
+ i -= sizeof(*slot);
+ }
+}
+#endif
+
+static void schedule(struct thread *t)
+{
+ struct thread *current;
+
+ current = current_thread();
+
+ /* If t is NULL need to find new runnable thread. */
+ if (t == NULL) {
+ if (thread_list_empty(&runnable_threads))
+ die("Runnable thread list is empty!\n");
+ t = pop_thread(&runnable_threads);
+ switch_to_thread(t->saved_stack, ¤t->saved_stack);
+ } else {
+ push_thread(&runnable_threads, current);
+ switch_to_thread(t->saved_stack, ¤t->saved_stack);
+ }
+}
+
+static void terminate_thread(struct thread *t)
+{
+ free_thread(t);
+ schedule(NULL);
+}
+
+static void asmlinkage call_wrapper(struct thread *t)
+{
+ t->entry(t->entry_arg);
+ terminate_thread(t);
+}
+
+static inline uintptr_t push_stack(uintptr_t cur_stack, uintptr_t value)
+{
+ uintptr_t *addr;
+
+ cur_stack -= sizeof(value);
+ addr = (uintptr_t *)cur_stack;
+ *addr = value;
+ return cur_stack;
+}
+
+static uintptr_t prepare_thread(struct thread *t, void *func, void *arg)
+{
+ uintptr_t stack;
+
+ stack = (uintptr_t)thread_cpu_info(t);
+
+ /* Stash the function and argument to run. */
+ t->entry = func;
+ t->entry_arg = arg;
+
+ /* All new threads can yield by default. */
+ t->can_yield = 1;
+
+ /* Imitate call_wrapper(t) with return address of 0. call_wrapper()
+ * will never return through the stack as it will call
+ * terminate_thread().*/
+ stack = push_stack(stack, (uintptr_t)t);
+ stack = push_stack(stack, (uintptr_t)0);
+ stack = push_stack(stack, (uintptr_t)call_wrapper);
+ /* Make room for the registers. Ignore intial values. */
+ stack -= sizeof(struct pushad_regs);
+
+ return stack;
+}
+
+int thread_run(void (*func)(void *), void *arg)
+{
+ struct thread *current;
+ struct cpu_info *ci;
+ struct thread *t;
+
+ ci = cpu_info();
+
+ if (!cpu_info_can_switch(ci)) {
+ printk(BIOS_ERR, "thread_run(): non-switchable cpu: %d\n",
+ ci->index);
+ return -1;
+ }
+
+ current = cpu_info_to_thread(ci);
+ t = get_free_thread();
+
+ if (t == NULL) {
+ printk(BIOS_ERR, "thread_run() No more threads!\n");
+ return -1;
+ }
+
+ t->saved_stack = prepare_thread(t, func, arg);
+ schedule(t);
+
+ return 0;
+}
+
+void thread_resume(struct timeout_callback *tocb)
+{
+ struct thread *to;
+ struct thread *current;
+
+ current = current_thread();
+ to = tocb->priv;
+ schedule(to);
+}
+
+int thread_yield_for(unsigned microsecs)
+{
+ struct thread *current;
+ struct cpu_info *ci;
+
+ ci = cpu_info();
+
+ if (!cpu_info_can_switch(ci))
+ return -1;
+ current = cpu_info_to_thread(ci);
+
+ /* By default thread_yield_for() will not yield the main thread. */
+ if (thread_is_main(current) || !current->can_yield)
+ return -1;
+
+ current->tocb.priv = current;
+ current->tocb.callback = thread_resume;
+
+ if (timer_sched_callback(¤t->tocb, microsecs))
+ return -1;
+
+ schedule(NULL);
+
+ return 0;
+}
+
+void thread_cooperate(void)
+{
+ struct thread *current;
+
+ current = current_thread();
+
+ current->can_yield = 1;
+}
+
+void thread_prevent_coop(void)
+{
+ struct thread *current;
+
+ current = current_thread();
+
+ current->can_yield = 0;
+}
diff --git a/src/arch/x86/lib/thread_switch.S b/src/arch/x86/lib/thread_switch.S
new file mode 100644
index 0000000..8de1948
--- /dev/null
+++ b/src/arch/x86/lib/thread_switch.S
@@ -0,0 +1,58 @@
+/*
+ * This file is part of the coreboot project.
+ *
+ * Copyright (C) 2013 Google, Inc.
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; version 2 of the License.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+.code32
+.text
+
+/*
+ * stack layout after pushad:
+ * +------------+
+ * | save stack | <-- esp + 0x28
+ * +------------+
+ * | new stack | <-- esp + 0x24
+ * +------------+
+ * | ret addr | <-- esp + 0x20
+ * +------------+
+ * | eax | <-- esp + 0x1c
+ * +------------+
+ * | ecx | <-- esp + 0x18
+ * +------------+
+ * | edx | <-- esp + 0x14
+ * +------------+
+ * | ebx | <-- esp + 0x10
+ * +------------+
+ * | orig esp | <-- esp + 0x0c
+ * +------------+
+ * | ebp | <-- esp + 0x08
+ * +------------+
+ * | esi | <-- esp + 0x04
+ * +------------+
+ * | edi | <-- esp + 0x00
+ * +------------+
+ */
+.globl switch_to_thread
+switch_to_thread:
+ pusha
+ /* Save the current stack */
+ movl 0x28(%esp), %ebx
+ movl %esp, (%ebx)
+ /* Switch to the new stack. */
+ movl 0x24(%esp), %eax
+ movl %eax, %esp
+ popa
+ ret
diff --git a/src/cpu/intel/haswell/mp_init.c b/src/cpu/intel/haswell/mp_init.c
index ddcff6c..f7623db 100644
--- a/src/cpu/intel/haswell/mp_init.c
+++ b/src/cpu/intel/haswell/mp_init.c
@@ -36,6 +36,7 @@
#include <lib.h>
#include <smp/atomic.h>
#include <smp/spinlock.h>
+#include <thread.h>
#include "haswell.h"
/* This needs to match the layout in the .module_parametrs section. */
@@ -164,6 +165,7 @@ ap_init(unsigned int cpu, void *microcode_ptr)
info = cpu_info();
info->index = cpu;
info->cpu = cpu_devs[cpu];
+ thread_init_cpu_info_non_bsp(info);
apic_id_table[info->index] = lapicid();
info->cpu->path.apic.apic_id = apic_id_table[info->index];
diff --git a/src/cpu/x86/lapic/apic_timer.c b/src/cpu/x86/lapic/apic_timer.c
index 749fef0..954e324 100644
--- a/src/cpu/x86/lapic/apic_timer.c
+++ b/src/cpu/x86/lapic/apic_timer.c
@@ -21,6 +21,7 @@
#include <stdint.h>
#include <console/console.h>
#include <delay.h>
+#include <thread.h>
#include <arch/io.h>
#include <arch/cpu.h>
#include <cpu/x86/car.h>
@@ -95,6 +96,9 @@ void udelay(u32 usecs)
{
u32 start, value, ticks;
+ if (!thread_yield_for(usecs))
+ return;
+
if (!timer_fsb || (lapic_read(LAPIC_LVTT) &
(LAPIC_LVT_TIMER_PERIODIC | LAPIC_LVT_MASKED)) !=
(LAPIC_LVT_TIMER_PERIODIC | LAPIC_LVT_MASKED))
diff --git a/src/cpu/x86/lapic/lapic_cpu_init.c b/src/cpu/x86/lapic/lapic_cpu_init.c
index 69430d5..fbc8aa4 100644
--- a/src/cpu/x86/lapic/lapic_cpu_init.c
+++ b/src/cpu/x86/lapic/lapic_cpu_init.c
@@ -32,6 +32,7 @@
#include <smp/spinlock.h>
#include <cpu/cpu.h>
#include <cpu/intel/speedstep.h>
+#include <thread.h>
#if CONFIG_SMP && CONFIG_MAX_CPUS > 1
/* This is a lot more paranoid now, since Linux can NOT handle
@@ -292,6 +293,7 @@ int start_cpu(device_t cpu)
info = (struct cpu_info *)stack_end;
info->index = index;
info->cpu = cpu;
+ thread_init_cpu_info_non_bsp(info);
/* Advertise the new stack and index to start_cpu */
secondary_stack = stack_end;
diff --git a/src/cpu/x86/tsc/delay_tsc.c b/src/cpu/x86/tsc/delay_tsc.c
index 0e2a9c0..c648119 100644
--- a/src/cpu/x86/tsc/delay_tsc.c
+++ b/src/cpu/x86/tsc/delay_tsc.c
@@ -4,6 +4,7 @@
#include <cpu/x86/tsc.h>
#include <smp/spinlock.h>
#include <delay.h>
+#include <thread.h>
#if !defined(__PRE_RAM__)
@@ -176,6 +177,9 @@ void udelay(unsigned us)
unsigned long long current;
unsigned long long clocks;
+ if (!thread_yield_for(us))
+ return;
+
start = rdtscll();
clocks = us;
clocks *= get_clocks_per_usec();
diff --git a/src/include/thread.h b/src/include/thread.h
new file mode 100644
index 0000000..7dfe4e7
--- /dev/null
+++ b/src/include/thread.h
@@ -0,0 +1,60 @@
+/*
+ * This file is part of the coreboot project.
+ *
+ * Copyright (C) 2013 Google, Inc.
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; version 2 of the License.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+#ifndef THREAD_H_
+#define THREAD_H_
+
+#include <stddef.h>
+#include <timer.h>
+#include <arch/cpu.h>
+
+#if CONFIG_COOP_MULTITASKING && !defined(__SMM__) && !defined(__PRE_RAM__)
+void threads_initialize(void);
+/* Return 0 on success, < 0 on failure. */
+int thread_run(void (*func)(void *), void *arg);
+/* Return 0 on success, < 0 on failure. */
+int thread_yield_for(unsigned microsecs);
+/* thread_resume() is exposed only to be used by the timer code. */
+void thread_resume(struct timeout_callback *tocb);
+
+static inline int tocb_is_resume(const struct timeout_callback *tocb)
+{
+ return tocb->callback == thread_resume;
+}
+
+void thread_cooperate(void);
+void thread_prevent_coop(void);
+
+static inline void thread_init_cpu_info_non_bsp(struct cpu_info *ci)
+{
+ ci->thread = NULL;
+}
+#else
+static inline void threads_initialize(void) {}
+static inline int thread_run(void (*func)(void *), void *arg) { return -1; }
+static inline int thread_yield_for(unsigned microsecs) { return -1; }
+static inline int tocb_is_resume(const struct timeout_callback *tocb)
+{
+ return 0;
+}
+static inline void thread_cooperate(void) {}
+static inline void thread_prevent_coop(void) {}
+static inline void thread_init_cpu_info_non_bsp(struct cpu_info *ci) { }
+#endif
+
+#endif /* THREAD_H_ */
diff --git a/src/lib/hardwaremain.c b/src/lib/hardwaremain.c
index a4d2fc9..9f16e06 100644
--- a/src/lib/hardwaremain.c
+++ b/src/lib/hardwaremain.c
@@ -39,6 +39,7 @@
#endif
#include <timer.h>
#include <timestamp.h>
+#include <thread.h>
#if BOOT_STATE_DEBUG
#define BS_DEBUG_LVL BIOS_DEBUG
@@ -327,7 +328,8 @@ static void bs_call_callbacks(struct boot_state *state,
printk(BS_DEBUG_LVL, "BS: callback (%p) @ %s.\n",
bscb, bscb->location);
#endif
- bs_call_callback(bscb);
+ if (thread_run((void *)bs_call_callback, bscb))
+ bs_call_callback(bscb);
continue;
}
@@ -476,13 +478,21 @@ void hardwaremain(int boot_complete)
hard_reset();
}
+ threads_initialize();
+
/* Schedule the static boot state entries. */
boot_state_schedule_static_entries();
/* FIXME: Is there a better way to handle this? */
init_timer();
- bs_walk_state_machine(BS_PRE_DEVICE);
+ if (thread_run((void *)bs_walk_state_machine, (void *)BS_PRE_DEVICE))
+ bs_walk_state_machine(BS_PRE_DEVICE);
+
+ while (1) {
+ bs_run_timers(1);
+ }
+
die("Boot state machine failure.\n");
}
diff --git a/src/lib/timer_queue.c b/src/lib/timer_queue.c
index 8d11f10..7426c3c 100644
--- a/src/lib/timer_queue.c
+++ b/src/lib/timer_queue.c
@@ -18,6 +18,7 @@
*/
#include <stddef.h>
#include <timer.h>
+#include <thread.h>
#define MAX_TIMER_QUEUE_ENTRIES 64
@@ -191,8 +192,13 @@ int timers_run(void)
timer_monotonic_get(¤t_time);
tocb = timer_queue_expired(&global_timer_queue, ¤t_time);
- if (tocb != NULL)
- tocb->callback(tocb);
+ if (tocb != NULL) {
+ /* If we are resuming a thread or cannot schedule a new
+ * thread run the callback in this execution context. */
+ if (tocb_is_resume(tocb) ||
+ thread_run((void *)tocb->callback, tocb) < 0)
+ tocb->callback(tocb);
+ }
return !timer_queue_empty(&global_timer_queue);
}
More information about the coreboot-gerrit
mailing list