Provided by:
freebsd-manpages_7.1~beta1-1_all 
NAME
kse - kernel support for user threads
LIBRARY
Standard C Library (libc, -lc)
SYNOPSIS
#include <sys/types.h>
#include <sys/kse.h>
int
kse_create(struct kse_mailbox *mbx, int sys-scope);
int
kse_exit(void);
int
kse_release(struct timespec *timeout);
int
kse_switchin(struct kse_thr_mailbox *tmbx, int flags);
int
kse_thr_interrupt(struct kse_thr_mailbox *tmbx, int cmd, long data);
int
kse_wakeup(struct kse_mailbox *mbx);
DESCRIPTION
These system calls implement kernel support for multi-threaded processes.
Overview
Traditionally, user threading has been implemented in one of two ways:
either all threads are managed in user space and the kernel is unaware of
any threading (also known as “N to 1”), or else separate processes
sharing a common memory space are created for each thread (also known as
“N to N”). These approaches have advantages and disadvantages:
User threading Kernel threading
+ Lightweight - Heavyweight
+ User controls scheduling - Kernel controls scheduling
- Syscalls must be wrapped + No syscall wrapping required
- Cannot utilize multiple CPUs + Can utilize multiple CPUs
The KSE system is a hybrid approach that achieves the advantages of both
the user and kernel threading approaches. The underlying philosophy of
the KSE system is to give kernel support for user threading without
taking away any of the user threading library’s ability to make
scheduling decisions. A kernel-to-user upcall mechanism is used to pass
control to the user threading library whenever a scheduling decision
needs to be made. An arbitrarily number of user threads are multiplexed
onto a fixed number of virtual CPUs supplied by the kernel. This can be
thought of as an “N to M” threading scheme.
Some general implications of this approach include:
· The user process can run multiple threads simultaneously on multi-
processor machines. The kernel grants the process virtual CPUs to
schedule as it wishes; these may run concurrently on real CPUs.
· All operations that block in the kernel become asynchronous, allowing
the user process to schedule another thread when any thread blocks.
Definitions
KSE allows a user process to have multiple threads of execution in
existence at the same time, some of which may be blocked in the kernel
while others may be executing or blocked in user space. A kernel
scheduling entity (KSE) is a “virtual CPU” granted to the process for the
purpose of executing threads. A thread that is currently executing is
always associated with exactly one KSE, whether executing in user space
or in the kernel. The KSE is said to be assigned to the thread. KSEs (a
user abstraction) are implemented on top of kernel threads using an
’upcall’ entity.
The KSE becomes unassigned, and the associated thread is suspended, when
the KSE has an associated mailbox, (see below) the thread has an
associated thread mailbox, (also see below) and any of the following
occurs:
· The thread invokes a system call that blocks.
· The thread makes any other demand of the kernel that cannot be
immediately satisfied, e.g., touches a page of memory that needs to
be fetched from disk, causing a page fault.
· Another thread that was previously blocked in the kernel completes
its work in the kernel (or is interrupted) and becomes ready to
return to user space, and the current thread is returning to user
space.
· A signal is delivered to the process, and this KSE is chosen to
deliver it.
In other words, as soon as there is a scheduling decision to be made, the
KSE becomes unassigned, because the kernel does not presume to know how
the process’ other runnable threads should be scheduled. Unassigned KSEs
always return to user space as soon as possible via the upcall mechanism
(described below), allowing the user process to decide how that KSE
should be utilized next. KSEs always complete as much work as possible
in the kernel before becoming unassigned.
Individual KSEs within a process are effectively indistinguishable, and
any KSE in a process may be assigned by the kernel to any runnable (in
the kernel) thread associated with that process. In practice, the kernel
attempts to preserve the affinity between threads and actual CPUs to
optimize cache behavior, but this is invisible to the user process.
(Affinity is not yet fully implemented.)
Each KSE has a unique KSE mailbox supplied by the user process. A
mailbox consists of a control structure containing a pointer to an upcall
function and a user stack. The KSE invokes this function whenever it
becomes unassigned. The kernel updates this structure with information
about threads that have become runnable and signals that have been
delivered before each upcall. Upcalls may be temporarily blocked by the
user thread scheduling code during critical sections.
Each user thread has a unique thread mailbox as well. Threads are
referred to using pointers to these mailboxes when communicating between
the kernel and the user thread scheduler. Each KSE’s mailbox contains a
pointer to the mailbox of the user thread that the KSE is currently
executing. This pointer is saved when the thread blocks in the kernel.
Whenever a thread blocked in the kernel is ready to return to user space,
it is added to the process’s list of completed threads. This list is
presented to the user code at the next upcall as a linked list of thread
mailboxes.
There is a kernel-imposed limit on the number of threads in a process
that may be simultaneously blocked in the kernel (this number is not
currently visible to the user). When this limit is reached, upcalls are
blocked and no work is performed for the process until one of the threads
completes (or a signal is received).
Managing KSEs
To become multi-threaded, a process must first invoke kse_create(). The
kse_create() system call creates a new KSE (except for the very first
invocation; see below). The KSE will be associated with the mailbox
pointed to by mbx. If sys_scope is non-zero, then the new thread will be
counted as a system scope thread. Other things must be done as well to
make a system scope thread so this is not sufficient (yet). System scope
variables are not covered in detail in this manual page yet, but briefly,
they never perform upcalls and do not return to the user thread
scheduler. Once launched they run autonomously. The pthreads library
knows how to make system scope threads and users are encouraged to use
the library interface.
Each process initially has a single KSE executing a single user thread.
Since the KSE does not have an associated mailbox, it must remain
assigned to the thread and does not perform any upcalls. (It is by
definition a system scope thread). The result is the traditional,
unthreaded mode of operation. Therefore, as a special case, the first
call to kse_create() by this initial thread with sys_scope equal to zero
does not create a new KSE; instead, it simply associates the current KSE
with the supplied KSE mailbox, and no immediate upcall results. However,
an upcall will be triggered the next time the thread blocks and the
required conditions are met.
The kernel does not allow more KSEs to exist in a process than the number
of physical CPUs in the system (this number is available as the sysctl(3)
variable hw.ncpu). Having more KSEs than CPUs would not add any value to
the user process, as the additional KSEs would just compete with each
other for access to the real CPUs. Since the extra KSEs would always be
side-lined, the result to the application would be exactly the same as
having fewer KSEs. There may however be arbitrarily many user threads,
and it is up to the user thread scheduler to handle mapping the
application’s user threads onto the available KSEs.
The kse_exit() system call causes the KSE assigned to the currently
running thread to be destroyed. If this KSE is the last one in the
process, there must be no remaining threads associated with that process
blocked in the kernel. This system call does not return unless there is
an error. Calling kse_exit() from the last thread is the same as calling
exit().
The kse_release() system call is used to “park” the KSE assigned to the
currently running thread when it is not needed, e.g., when there are more
available KSEs than runnable user threads. The thread converts to an
upcall but does not get scheduled until there is a new reason to do so,
e.g., a previously blocked thread becomes runnable, or the timeout
expires. If successful, kse_release() does not return to the caller.
The kse_switchin() system call can be used by the UTS, when it has
selected a new thread, to switch to the context of that thread. The use
of kse_switchin() is machine dependent. Some platforms do not need a
system call to switch to a new context, while others require its use in
particular cases.
The kse_wakeup() system call is the opposite of kse_release(). It causes
the (parked) KSE associated with the mailbox pointed to by mbx to be
woken up, causing it to upcall. If the KSE has already woken up for
another reason, this system call has no effect. The mbx argument may be
NULL to specify “any KSE in the current process”.
The kse_thr_interrupt() system call is used to interrupt a currently
blocked thread. The thread must either be blocked in the kernel or
assigned to a KSE (i.e., executing). The thread is then marked as
interrupted. As soon as the thread invokes an interruptible system call
(or immediately for threads already blocked in one), the thread will be
made runnable again, even though the kernel operation may not have
completed. The effect on the interrupted system call is the same as if
it had been interrupted by a signal; typically this means an error is
returned with errno set to EINTR.
Signals
The current implementation creates a special signal thread. Kernel
threads (KSEs) in a process mask all signals, and only the signal thread
waits for signals to be delivered to the process, the signal thread is
responsible for dispatching signals to user threads.
A downside of this is that if a multiplexed thread calls the execve()
syscall, its signal mask and pending signals may not be available in the
kernel. They are stored in userland and the kernel does not know where
to get them, however POSIX requires them to be restored and passed them
to new process. Just setting the mask for the thread before calling
execve() is only a close approximation to the problem as it does not re-
deliver back to the kernel any pending signals that the old process may
have blocked, and it allows a window in which new signals may be
delivered to the process between the setting of the mask and the
execve().
For now this problem has been solved by adding a special combined
kse_thr_interrupt()/execve() mode to the kse_thr_interrupt() syscall.
The kse_thr_interrupt() syscall has a sub command KSE_INTR_EXECVE, that
allows it to accept a kse_execv_args structure, and allowing it to adjust
the signals and then atomically convert into an execve() call.
Additional pending signals and the correct signal mask can be passed to
the kernel in this way. The thread library overrides the execve()
syscall and translates it into kse_intr_interrupt() call, allowing a
multiplexed thread to restore pending signals and the correct signal mask
before doing the exec(). This solution to the problem may change.
KSE Mailboxes
Each KSE has a unique mailbox for user-kernel communication defined in
Some of the fields there are:
km_version describes the version of this structure and must be equal to
KSE_VER_0. km_udata is an opaque pointer ignored by the kernel.
km_func points to the KSE’s upcall function; it will be invoked using
km_stack, which must remain valid for the lifetime of the KSE.
km_curthread always points to the thread that is currently assigned to
this KSE if any, or NULL otherwise. This field is modified by both the
kernel and the user process as follows.
When km_curthread is not NULL, it is assumed to be pointing at the
mailbox for the currently executing thread, and the KSE may be
unassigned, e.g., if the thread blocks in the kernel. The kernel will
then save the contents of km_curthread with the blocked thread, set
km_curthread to NULL, and upcall to invoke km_func().
When km_curthread is NULL, the kernel will never perform any upcalls with
this KSE; in other words, the KSE remains assigned to the thread even if
it blocks. km_curthread must be NULL while the KSE is executing critical
user thread scheduler code that would be disrupted by an intervening
upcall; in particular, while km_func() itself is executing.
Before invoking km_func() in any upcall, the kernel always sets
km_curthread to NULL. Once the user thread scheduler has chosen a new
thread to run, it should point km_curthread at the thread’s mailbox, re-
enabling upcalls, and then resume the thread. Note: modification of
km_curthread by the user thread scheduler must be atomic with the loading
of the context of the new thread, to avoid the situation where the thread
context area may be modified by a blocking async operation, while there
is still valid information to be read out of it.
km_completed points to a linked list of user threads that have completed
their work in the kernel since the last upcall. The user thread
scheduler should put these threads back into its own runnable queue.
Each thread in a process that completes a kernel operation (synchronous
or asynchronous) that results in an upcall is guaranteed to be linked
into exactly one KSE’s km_completed list; which KSE in the group,
however, is indeterminate. Furthermore, the completion will be reported
in only one upcall.
km_sigscaught contains the list of signals caught by this process since
the previous upcall to any KSE in the process. As long as there exists
one or more KSEs with an associated mailbox in the user process, signals
are delivered this way rather than the traditional way. (This has not
been implemented and may change.)
km_timeofday is set by the kernel to the current system time before
performing each upcall.
km_flags may contain any of the following bits OR’ed together:
KMF_NOUPCALL
Block upcalls from happening. The thread is in some critical
section.
KMF_NOCOMPLETED, KMF_DONE, KMF_BOUND
This thread should be considered to be permanently bound to its
KSE, and treated much like a non-threaded process would be. It
is a “long term” version of KMF_NOUPCALL in some ways.
KMF_WAITSIGEVENT
Implement characteristics needed for the signal delivery thread.
Thread Mailboxes
Each user thread must have associated with it a unique struct
kse_thr_mailbox as defined in It includes the following fields.
tm_udata is an opaque pointer ignored by the kernel.
tm_context stores the context for the thread when the thread is blocked
in user space. This field is also updated by the kernel before a
completed thread is returned to the user thread scheduler via
km_completed.
tm_next links the km_completed threads together when returned by the
kernel with an upcall. The end of the list is marked with a NULL
pointer.
tm_uticks and tm_sticks are time counters for user mode and kernel mode
execution, respectively. These counters count ticks of the statistics
clock (see clocks(7)). While any thread is actively executing in the
kernel, the corresponding tm_sticks counter is incremented. While any
KSE is executing in user space and that KSE’s km_curthread pointer is not
equal to NULL, the corresponding tm_uticks counter is incremented.
tm_flags may contain any of the following bits OR’ed together:
TMF_NOUPCALL
Similar to KMF_NOUPCALL. This flag inhibits upcalling for
critical sections. Some architectures require this to be in one
place and some in the other.
RETURN VALUES
The kse_create(), kse_wakeup(), and kse_thr_interrupt() system calls
return zero if successful. The kse_exit() and kse_release() system calls
do not return if successful.
All of these system calls return a non-zero error code in case of an
error.
ERRORS
The kse_create() system call will fail if:
[ENXIO] There are already as many KSEs in the process as
hardware processors.
[EAGAIN] The user is not the super user, and the soft resource
limit corresponding to the resource argument
RLIMIT_NPROC would be exceeded (see getrlimit(2)).
[EFAULT] The mbx argument points to an address which is not a
valid part of the process address space.
The kse_exit() system call will fail if:
[EDEADLK] The current KSE is the last in its process and there
are still one or more threads associated with the
process blocked in the kernel.
[ESRCH] The current KSE has no associated mailbox, i.e., the
process is operating in traditional, unthreaded mode
(in this case use _exit(2) to exit the process).
The kse_release() system call will fail if:
[ESRCH] The current KSE has no associated mailbox, i.e., the
process is operating is traditional, unthreaded mode.
The kse_wakeup() system call will fail if:
[ESRCH] The mbx argument is not NULL and the mailbox pointed
to by mbx is not associated with any KSE in the
process.
[ESRCH] The mbx argument is NULL and the current KSE has no
associated mailbox, i.e., the process is operating in
traditional, unthreaded mode.
The kse_thr_interrupt() system call will fail if:
[ESRCH] The thread corresponding to tmbx is neither currently
assigned to any KSE in the process nor blocked in the
kernel.
SEE ALSO
rfork(2), pthread(3), ucontext(3)
Thomas E. Anderson, Brian N. Bershad, Edward D. Lazowska, and Henry M.
Levy, "Scheduler activations: effective kernel support for the user-level
management of parallelism", ACM Press, ACM Transactions on Computer
Systems, Issue 1, Volume 10, pp. 53-79, February 1992.
HISTORY
The KSE system calls first appeared in FreeBSD 5.0.
AUTHORS
KSE was originally implemented by Julian Elischer 〈julian@FreeBSD.org〉,
with additional contributions by Jonathan Mini 〈mini@FreeBSD.org〉, Daniel
Eischen 〈deischen@FreeBSD.org〉, and David Xu 〈davidxu@FreeBSD.org〉.
This manual page was written by Archie Cobbs 〈archie@FreeBSD.org〉.
BUGS
The KSE code is currently under development.