FreeBSD Man Pages

kse_exit(2)

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 newgroup);

     int
     kse_exit(void);

     int
     kse_release(struct timespec *timeout);

     int
     kse_switchin(mcontext_t *mcp, long val, long *loc);

     int
     kse_thr_interrupt(struct kse_thr_mailbox *tmbx);

     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 tak-
     ing 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:

     o	 The user process can run multiple threads simultaneously on multi-

   Definitions
     KSE allows a user process to have multiple threads of execution in exis-
     tence 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.

     The KSE becomes unassigned, and the associated thread is suspended, when
     the KSE has an associated mailbox, (see below) the thread has an associ-
     ated thread mailbox, (also see below) and any of the following occurs:

     o	 The thread invokes a system call that blocks.

     o	 The thread makes any other demand of the kernel that cannot be imme-
	 diately satisfied, e.g., touches a page of memory that needs to be
	 fetched from disk, causing a page fault.

     o	 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.

     o	 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.

     A KSE group is a collection of KSEs that are scheduled uniformly and
     which share access to the same pool of threads, which are associated with
     the KSE group.  A KSE group is the smallest entity to which a kernel
     scheduling priority may be assigned.  For the purposes of process sched-
     uling and accounting, each KSE group counts similarly to a traditional
     unthreaded process.  Individual KSEs within a KSE group are effectively
     indistinguishable, and any KSE in a KSE group may be assigned by the ker-
     nel to any runnable (in the kernel) thread associated with that KSE
     group.  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 implemented.)

     Each KSE has a unique KSE mailbox supplied by the user process.  A mail-
     box 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 deliv-
     ered 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

     There is a kernel-imposed limit on the number of threads in a KSE group
     that may be simultaneously blocked in the kernel (this number is not cur-
     rently visible to the user).  When this limit is reached, upcalls are
     blocked and no work is performed for the KSE group 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 newgroup is non-zero, a new KSE group is also cre-
     ated containing the KSE.  Otherwise, the new KSE is added to the current
     KSE group.  Newly created KSEs are initially unassigned; therefore, they
     will upcall immediately.

     Each process initially has a single KSE in a single KSE group 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.
     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 newgroup equal to zero does not create a new KSE; instead, it simply
     associates the current KSE with the supplied KSE mailbox, and no immedi-
     ate 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 KSE group than the num-
     ber 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 run-
     ning thread to be destroyed.  If this KSE is the last one in the KSE
     group, there must be no remaining threads associated with the KSE group
     blocked in the kernel.  This system call does not return unless there is
     an error.

     As a special case, if the last remaining KSE in the last remaining KSE
     group invokes this system call, then the KSE is not destroyed; instead,
     the KSE just looses the association with its mailbox and kse_exit()
     returns normally.	This returns the process to its original, unthreaded
     state.

     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

     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 inter-
     rupted.  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 deliv-
     ered 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.  Addi-
     tional 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
     <sys/kse.h>.  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 mail-
     box 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().

     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 sched-
     uler should put these threads back into its own runnable queue.  Each
     thread in a KSE group 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 per-
     forming 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 considerred 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 charactersitics 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 <sys/kse.h>.  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 com-
     pleted thread is returned to the user thread scheduler via km_completed.

     tm_next links the km_completed threads together when returned by the ker-
     nel 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

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 KSE group as
			hardware processors.

     [EAGAIN]		The system-imposed limit on the total number of KSE
			groups under execution would be exceeded.  The limit
			is given by the sysctl(3) MIB variable KERN_MAXPROC.
			(The limit is actually ten less than this except for
			the super user.)

     [EAGAIN]		The user is not the super user, and the system-imposed
			limit on the total number of KSE groups under execu-
			tion by a single user would be exceeded.  The limit is
			given by the sysctl(3) MIB variable
			KERN_MAXPROCPERUID.

     [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 KSE group and there
			are still one or more threads associated with the KSE
			group 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.
     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.

FreeBSD 5.4		      September 10, 2002		   FreeBSD 5.4

SPONSORED LINKS