[v3,06/14] uthread: add cooperative multi-tasking interface

Add a new internal API called uthread (Kconfig symbol: UTHREAD) which
provides cooperative multi-tasking. The goal is to be able to improve
the performance of some parts of U-Boot by overlapping lengthy
operations, and also implement background jobs in the U-Boot shell.
Each uthread has its own stack allocated on the heap. The default stack
size is defined by the UTHREAD_STACK_SIZE symbol and is used when
uthread_create() receives zero for the stack_sz argument.

The implementation is based on context-switching via initjmp()/setjmp()/
longjmp() and is inspired from barebox threads [1]. A notion of thread
group helps with dependencies, such as when a thread needs to block
until a number of other threads have returned.

The name "uthread" comes from "user-space threads" because the
scheduling happens with no help from a higher privileged mode, contrary
to more complex models where kernel threads are defined. But the 'u'
may as well stand for 'U-Boot' since the bootloader may actually be
running at any privilege level and the notion of user vs. kernel may
not make much sense in this context.

[1] https://github.com/barebox/barebox/blob/master/common/bthread.c

Signed-off-by: Jerome Forissier <jerome.forissier@linaro.org>
---
 doc/api/index.rst   |   1 +
 doc/api/uthread.rst |   7 +++
 include/uthread.h   | 123 +++++++++++++++++++++++++++++++++++++++
 lib/Kconfig         |  21 +++++++
 lib/Makefile        |   2 +
 lib/uthread.c       | 139 ++++++++++++++++++++++++++++++++++++++++++++
 6 files changed, 293 insertions(+)
 create mode 100644 doc/api/uthread.rst
 create mode 100644 include/uthread.h
 create mode 100644 lib/uthread.c

On Tue, 4 Mar 2025 at 17:31, Jerome Forissier
<jerome.forissier@linaro.org> wrote:
>
> Add a new internal API called uthread (Kconfig symbol: UTHREAD) which
> provides cooperative multi-tasking. The goal is to be able to improve
> the performance of some parts of U-Boot by overlapping lengthy
> operations, and also implement background jobs in the U-Boot shell.
> Each uthread has its own stack allocated on the heap. The default stack
> size is defined by the UTHREAD_STACK_SIZE symbol and is used when
> uthread_create() receives zero for the stack_sz argument.
>
> The implementation is based on context-switching via initjmp()/setjmp()/
> longjmp() and is inspired from barebox threads [1]. A notion of thread
> group helps with dependencies, such as when a thread needs to block
> until a number of other threads have returned.
>
> The name "uthread" comes from "user-space threads" because the
> scheduling happens with no help from a higher privileged mode, contrary
> to more complex models where kernel threads are defined. But the 'u'
> may as well stand for 'U-Boot' since the bootloader may actually be
> running at any privilege level and the notion of user vs. kernel may
> not make much sense in this context.
>
> [1] https://github.com/barebox/barebox/blob/master/common/bthread.c
>
> Signed-off-by: Jerome Forissier <jerome.forissier@linaro.org>
> ---
>  doc/api/index.rst   |   1 +
>  doc/api/uthread.rst |   7 +++
>  include/uthread.h   | 123 +++++++++++++++++++++++++++++++++++++++
>  lib/Kconfig         |  21 +++++++
>  lib/Makefile        |   2 +
>  lib/uthread.c       | 139 ++++++++++++++++++++++++++++++++++++++++++++
>  6 files changed, 293 insertions(+)
>  create mode 100644 doc/api/uthread.rst
>  create mode 100644 include/uthread.h
>  create mode 100644 lib/uthread.c
>
> diff --git a/doc/api/index.rst b/doc/api/index.rst
> index 0dc9ad45d41..506843ed74a 100644
> --- a/doc/api/index.rst
> +++ b/doc/api/index.rst
> @@ -29,3 +29,4 @@ U-Boot API documentation
>     sysreset
>     timer
>     unicode
> +   uthread
> diff --git a/doc/api/uthread.rst b/doc/api/uthread.rst
> new file mode 100644
> index 00000000000..21233ff6b22
> --- /dev/null
> +++ b/doc/api/uthread.rst
> @@ -0,0 +1,7 @@
> +.. SPDX-License-Identifier: GPL-2.0-or-later
> +
> +Uthread API
> +===========
> +
> +.. kernel-doc:: include/uthread.h
> +   :internal:
> diff --git a/include/uthread.h b/include/uthread.h
> new file mode 100644
> index 00000000000..ec3034c097a
> --- /dev/null
> +++ b/include/uthread.h
> @@ -0,0 +1,123 @@
> +/* SPDX-License-Identifier: GPL-2.0+ */
> +/*
> + * Copyright 2025 Linaro Limited
> + */
> +
> +#include <linux/list.h>
> +#include <linux/types.h>
> +#include <setjmp.h>
> +
> +#ifndef _UTHREAD_H_
> +#define _UTHREAD_H_
> +
> +/**
> + * DOC: Overview
> + *
> + * The uthread framework is a basic task scheduler that allows to run functions
> + * "in parallel" on a single CPU core. The scheduling is cooperative, not
> + * preemptive -- meaning that context switches from one task to another task is
> + * voluntary, via a call to uthread_schedule(). This characteristic makes thread
> + * synchronization much easier, because a thread cannot be interrupted in the
> + * middle of a critical section (reading from or writing to shared state, for
> + * instance).
> + *
> + * CONFIG_UTHREAD in lib/Kconfig enables the uthread framework. When disabled,
> + * the uthread_create()  and uthread_schedule() functions may still be used so
> + * that code differences between uthreads enabled and disabled can be reduced to
> + * a minimum.
> + */
> +
> +/**
> + * struct uthread - a thread object
> + *
> + * @fn: thread entry point
> + * @arg: argument passed to the entry point when the thread is started
> + * @ctx: context to resume execution of this thread (via longjmp())
> + * @stack: initial stack pointer for the thread
> + * @done: true once @fn has returned, false otherwise
> + * @grp_id: user-supplied identifier for this thread and possibly others. A
> + * thread can belong to zero or one group (not more), and a group may contain
> + * any number of threads.
> + * @list: link in the global scheduler list
> + */
> +struct uthread {
> +       void (*fn)(void *);
> +       void *arg;
> +       jmp_buf ctx;
> +       void *stack;
> +       bool done;
> +       unsigned int grp_id;
> +       struct list_head list;
> +};
> +
> +#ifdef CONFIG_UTHREAD
> +
> +/**
> + * uthread_create() - Create a uthread object and make it ready for execution
> + *
> + * Threads are automatically deleted when they return from their entry point.
> + *
> + * @uthr: a pointer to a user-allocated uthread structure to store information
> + * about the new thread, or NULL to let the framework allocate and manage its
> + * own structure.
> + * @fn: the thread's entry point
> + * @arg: argument passed to the thread's entry point
> + * @stack_sz: stack size for the new thread (in bytes). The stack is allocated
> + * on the heap.
> + * @grp_id: an optional thread group ID that the new thread should belong to
> + * (zero for no group)
> + */
> +int uthread_create(struct uthread *uthr, void (*fn)(void *), void *arg,
> +                  size_t stack_sz, unsigned int grp_id);
> +/**
> + * uthread_schedule() - yield the CPU to the next runnable thread
> + *
> + * This function is called either by the main thread or any secondary thread
> + * (that is, any thread created via uthread_create()) to switch execution to
> + * the next runnable thread.
> + *
> + * Return: true if a thread was scheduled, false if no runnable thread was found
> + */
> +bool uthread_schedule(void);
> +/**
> + * uthread_grp_new_id() - return a new ID for a thread group
> + *
> + * Return: the new thread group ID
> + */
> +unsigned int uthread_grp_new_id(void);
> +/**
> + * uthread_grp_done() - test if all threads in a group are done
> + *
> + * @grp_id: the ID of the thread group that should be considered
> + * Return: false if the group contains at least one runnable thread (i.e., one
> + * thread which entry point has not returned yet), true otherwise
> + */
> +bool uthread_grp_done(unsigned int grp_id);
> +
> +#else
> +
> +static inline int uthread_create(struct uthread *uthr, void (*fn)(void *),
> +                                void *arg, size_t stack_sz,
> +                                unsigned int grp_id)
> +{
> +       fn(arg);
> +       return 0;
> +}
> +
> +static inline bool uthread_schedule(void)
> +{
> +       return false;
> +}
> +
> +static inline unsigned int uthread_grp_new_id(void)
> +{
> +       return 0;
> +}
> +
> +static inline bool uthread_grp_done(unsigned int grp_id)
> +{
> +       return true;
> +}
> +
> +#endif /* CONFIG_UTHREAD */
> +#endif /* _UTHREAD_H_ */
> diff --git a/lib/Kconfig b/lib/Kconfig
> index 1a683dea670..8321f20e154 100644
> --- a/lib/Kconfig
> +++ b/lib/Kconfig
> @@ -1255,6 +1255,27 @@ config PHANDLE_CHECK_SEQ
>           enable this config option to distinguish them using
>           phandles in fdtdec_get_alias_seq() function.
>
> +config UTHREAD
> +       bool "Enable thread support"
> +       depends on HAVE_INITJMP
> +       help
> +         Implement a simple form of cooperative multi-tasking based on
> +         context-switching via initjmp(), setjmp() and longjmp(). The
> +         uthread_ interface enables the main thread of execution to create
> +         one or more secondary threads and schedule them until they all have
> +         returned. At any point a thread may suspend its execution and
> +         schedule another thread, which allows for the efficient multiplexing
> +         of leghthy operations.
> +
> +config UTHREAD_STACK_SIZE
> +       int "Default uthread stack size"
> +       depends on UTHREAD
> +       default 32768
> +       help
> +         The default stack size for uthreads. Each uthread has its own stack.
> +         When the stack_sz argument to uthread_create() is zero then this
> +         value is used.
> +
>  endmenu
>
>  source "lib/fwu_updates/Kconfig"
> diff --git a/lib/Makefile b/lib/Makefile
> index a7bc2f3134a..3610694de7a 100644
> --- a/lib/Makefile
> +++ b/lib/Makefile
> @@ -164,6 +164,8 @@ obj-$(CONFIG_LIB_ELF) += elf.o
>
>  obj-$(CONFIG_$(PHASE_)SEMIHOSTING) += semihosting.o
>
> +obj-$(CONFIG_UTHREAD) += uthread.o
> +
>  #
>  # Build a fast OID lookup registry from include/linux/oid_registry.h
>  #
> diff --git a/lib/uthread.c b/lib/uthread.c
> new file mode 100644
> index 00000000000..3cb25784556
> --- /dev/null
> +++ b/lib/uthread.c
> @@ -0,0 +1,139 @@
> +// SPDX-License-Identifier: GPL-2.0-only
> +/*
> + * Copyright (C) 2021 Ahmad Fatoum, Pengutronix
> + * Copyright (C) 2025 Linaro Limited
> + *
> + * An implementation of cooperative multi-tasking inspired from barebox threads
> + * https://github.com/barebox/barebox/blob/master/common/bthread.c
> + */
> +
> +#include <compiler.h>
> +#include <linux/kernel.h>
> +#include <linux/list.h>
> +#include <malloc.h>
> +#include <setjmp.h>
> +#include <stdint.h>
> +#include <uthread.h>
> +
> +static struct uthread main_thread = {
> +       .list = LIST_HEAD_INIT(main_thread.list),
> +};
> +
> +static struct uthread *current = &main_thread;
> +
> +/**
> + * uthread_trampoline() - Call the current thread's entry point then resume the
> + * main thread.
> + *
> + * This is a helper function which is used as the @func argument to the
> + * initjmp() function, and ultimately invoked via setjmp(). It does not return
> + * but instead longjmp()'s back to the main thread.
> + */
> +static void __noreturn uthread_trampoline(void)
> +{
> +       struct uthread *curr = current;
> +
> +       curr->fn(curr->arg);
> +       curr->done = true;
> +       current = &main_thread;
> +       longjmp(current->ctx, 1);
> +       /* Not reached */
> +       while (true)
> +               ;
> +}
> +
> +/**
> + * uthread_free() - Free memory used by a uthread object.
> + */
> +static void uthread_free(struct uthread *uthread)
> +{
> +       if (!uthread)
> +               return;
> +       free(uthread->stack);
> +       free(uthread);
> +}
> +
> +int uthread_create(struct uthread *uthr, void (*fn)(void *), void *arg,
> +                  size_t stack_sz, unsigned int grp_id)
> +{
> +       bool user_allocated = false;
> +
> +       if (!stack_sz)
> +               stack_sz = CONFIG_UTHREAD_STACK_SIZE;
> +
> +       if (uthr) {
> +               user_allocated = true;
> +       } else {
> +               uthr = calloc(1, sizeof(*uthr));
> +               if (!uthr)
> +                       return -1;
> +       }
> +
> +       uthr->stack = memalign(16, stack_sz);
> +       if (!uthr->stack)
> +               goto err;
> +
> +       uthr->fn = fn;
> +       uthr->arg = arg;
> +       uthr->grp_id = grp_id;
> +
> +       list_add_tail(&uthr->list, &current->list);
> +
> +       initjmp(uthr->ctx, uthread_trampoline, uthr->stack + stack_sz);
> +
> +       return 0;
> +err:
> +       if (!user_allocated)
> +               free(uthr);
> +       return -1;
> +}
> +
> +/**
> + * uthread_resume() - switch execution to a given thread
> + *
> + * @uthread: the thread object that should be resumed
> + */
> +static void uthread_resume(struct uthread *uthread)
> +{
> +       if (!setjmp(current->ctx)) {
> +               current = uthread;
> +               longjmp(uthread->ctx, 1);
> +       }
> +}
> +
> +bool uthread_schedule(void)
> +{
> +       struct uthread *next;
> +       struct uthread *tmp;
> +
> +       list_for_each_entry_safe(next, tmp, &current->list, list) {
> +               if (!next->done) {
> +                       uthread_resume(next);
> +                       return true;
> +               } else {
> +                       /* Found a 'done' thread, free its resources */
> +                       list_del(&next->list);
> +                       uthread_free(next);
> +               }
> +       }
> +       return false;
> +}
> +
> +unsigned int uthread_grp_new_id(void)
> +{
> +       static unsigned int id = 0;
> +
> +       return ++id;
> +}
> +
> +bool uthread_grp_done(unsigned int grp_id)
> +{
> +       struct uthread *next;
> +
> +       list_for_each_entry(next, &main_thread.list, list) {
> +               if (next->grp_id == grp_id && !next->done)
> +                       return false;
> +       }
> +
> +       return true;
> +}
> --
> 2.43.0
>

Reviewed-by: Ilias Apalodimas <ilias.apalodimas@linaro.org>