1 .\" Copyright (c) 2002 Packet Design, LLC.
2 .\" All rights reserved.
4 .\" Subject to the following obligations and disclaimer of warranty,
5 .\" use and redistribution of this software, in source or object code
6 .\" forms, with or without modifications are expressly permitted by
7 .\" Packet Design; provided, however, that:
9 .\" (i) Any and all reproductions of the source or object code
10 .\" must include the copyright notice above and the following
11 .\" disclaimer of warranties; and
12 .\" (ii) No rights are granted, in any manner or form, to use
13 .\" Packet Design trademarks, including the mark "PACKET DESIGN"
14 .\" on advertising, endorsements, or otherwise except as such
15 .\" appears in the above copyright notice or in the software.
17 .\" THIS SOFTWARE IS BEING PROVIDED BY PACKET DESIGN "AS IS", AND
18 .\" TO THE MAXIMUM EXTENT PERMITTED BY LAW, PACKET DESIGN MAKES NO
19 .\" REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED, REGARDING
20 .\" THIS SOFTWARE, INCLUDING WITHOUT LIMITATION, ANY AND ALL IMPLIED
21 .\" WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE,
22 .\" OR NON-INFRINGEMENT. PACKET DESIGN DOES NOT WARRANT, GUARANTEE,
23 .\" OR MAKE ANY REPRESENTATIONS REGARDING THE USE OF, OR THE RESULTS
24 .\" OF THE USE OF THIS SOFTWARE IN TERMS OF ITS CORRECTNESS, ACCURACY,
25 .\" RELIABILITY OR OTHERWISE. IN NO EVENT SHALL PACKET DESIGN BE
26 .\" LIABLE FOR ANY DAMAGES RESULTING FROM OR ARISING OUT OF ANY USE
27 .\" OF THIS SOFTWARE, INCLUDING WITHOUT LIMITATION, ANY DIRECT,
28 .\" INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, PUNITIVE, OR CONSEQUENTIAL
29 .\" DAMAGES, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES, LOSS OF
30 .\" USE, DATA OR PROFITS, HOWEVER CAUSED AND UNDER ANY THEORY OF
31 .\" LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
32 .\" (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
33 .\" THE USE OF THIS SOFTWARE, EVEN IF PACKET DESIGN IS ADVISED OF
34 .\" THE POSSIBILITY OF SUCH DAMAGE.
43 .Nd "kernel support for user threads"
50 .Fn kse_create "struct kse_mailbox *mbx" "int sys-scope"
54 .Fn kse_release "struct timespec *timeout"
56 .Fn kse_switchin "struct kse_thr_mailbox *tmbx" "int flags"
58 .Fn kse_thr_interrupt "struct kse_thr_mailbox *tmbx" "int cmd" "long data"
60 .Fn kse_wakeup "struct kse_mailbox *mbx"
62 These system calls implement kernel support for multi-threaded processes.
66 Traditionally, user threading has been implemented in one of two ways:
67 either all threads are managed in user space and the kernel is unaware
68 of any threading (also known as
70 or else separate processes sharing
71 a common memory space are created for each thread (also known as
73 These approaches have advantages and disadvantages:
74 .Bl -column "- Cannot utilize multiple CPUs" "+ Can utilize multiple CPUs"
75 .It Sy "User threading Kernel threading"
76 .It "+ Lightweight - Heavyweight"
77 .It "+ User controls scheduling - Kernel controls scheduling"
78 .It "- Syscalls must be wrapped + No syscall wrapping required"
79 .It "- Cannot utilize multiple CPUs + Can utilize multiple CPUs"
83 hybrid approach that achieves the advantages of both the user and kernel
85 The underlying philosophy of the KSE system is to give kernel support
86 for user threading without taking away any of the user threading library's
87 ability to make scheduling decisions.
88 A kernel-to-user upcall mechanism is used to pass control to the user
89 threading library whenever a scheduling decision needs to be made.
90 An arbitrarily number of user threads are multiplexed onto a fixed number of
91 virtual CPUs supplied by the kernel.
92 This can be thought of as an
96 Some general implications of this approach include:
99 The user process can run multiple threads simultaneously on multi-processor
101 The kernel grants the process virtual CPUs to schedule as it
102 wishes; these may run concurrently on real CPUs.
104 All operations that block in the kernel become asynchronous, allowing
105 the user process to schedule another thread when any thread blocks.
110 KSE allows a user process to have multiple
112 of execution in existence at the same time, some of which may be blocked
113 in the kernel while others may be executing or blocked in user space.
115 .Sy "kernel scheduling entity"
118 granted to the process for the purpose of executing threads.
119 A thread that is currently executing is always associated with
120 exactly one KSE, whether executing in user space or in the kernel.
121 The KSE is said to be
124 KSEs (a user abstraction) are implemented on top
125 of kernel threads using an 'upcall' entity.
129 and the associated thread is suspended, when the KSE has an associated
131 (see below) the thread has an associated
133 (also see below) and any of the following occurs:
136 The thread invokes a system call that blocks.
138 The thread makes any other demand of the kernel that cannot be immediately
139 satisfied, e.g., touches a page of memory that needs to be fetched from disk,
140 causing a page fault.
142 Another thread that was previously blocked in the kernel completes its
143 work in the kernel (or is
145 and becomes ready to return to user space, and the current thread is returning
148 A signal is delivered to the process, and this KSE is chosen to deliver it.
151 In other words, as soon as there is a scheduling decision to be made,
152 the KSE becomes unassigned, because the kernel does not presume to know
153 how the process' other runnable threads should be scheduled.
154 Unassigned KSEs always return to user space as soon as possible via
157 mechanism (described below), allowing the user process to decide how
158 that KSE should be utilized next.
159 KSEs always complete as much work as possible in the kernel before
162 Individual KSEs within a process are effectively indistinguishable,
163 and any KSE in a process may be assigned by the kernel to any runnable
164 (in the kernel) thread associated with that process.
165 In practice, the kernel attempts to preserve the affinity between threads
166 and actual CPUs to optimize cache behavior, but this is invisible to the
168 (Affinity is not yet fully implemented.)
170 Each KSE has a unique
172 supplied by the user process.
173 A mailbox consists of a control structure containing a pointer to an
174 .Sy "upcall function"
176 The KSE invokes this function whenever it becomes unassigned.
177 The kernel updates this structure with information about threads that have
178 become runnable and signals that have been delivered before each upcall.
179 Upcalls may be temporarily blocked by the user thread scheduling code
180 during critical sections.
182 Each user thread has a unique
185 Threads are referred to using pointers to these mailboxes when communicating
186 between the kernel and the user thread scheduler.
187 Each KSE's mailbox contains a pointer to the mailbox of the user thread
188 that the KSE is currently executing.
189 This pointer is saved when the thread blocks in the kernel.
191 Whenever a thread blocked in the kernel is ready to return to user space,
192 it is added to the process's list of
195 This list is presented to the user code at the next upcall as a linked list
198 There is a kernel-imposed limit on the number of threads in a process
199 that may be simultaneously blocked in the kernel (this number is not
200 currently visible to the user).
201 When this limit is reached, upcalls are blocked and no work is performed
202 for the process until one of the threads completes (or a signal is
207 To become multi-threaded, a process must first invoke
212 creates a new KSE (except for the very first invocation; see below).
213 The KSE will be associated with the mailbox pointed to by
217 is non-zero, then the new thread will be counted as a system scope
218 thread. Other things must be done as well to make a system scope thread
219 so this is not sufficient (yet).
220 System scope variables are not covered
221 in detail in this manual page yet, but briefly, they never perform
222 upcalls and do not return to the user thread scheduler.
223 Once launched they run autonomously.
224 The pthreads library knows how to make system
225 scope threads and users are encouraged to use the library interface.
227 Each process initially has a single KSE executing a single user thread.
228 Since the KSE does not have an associated mailbox, it must remain assigned
229 to the thread and does not perform any upcalls.
230 (It is by definition a system scope thread).
231 The result is the traditional, unthreaded mode of operation.
232 Therefore, as a special case, the first call to
234 by this initial thread with
236 equal to zero does not create a new KSE; instead, it simply associates the
237 current KSE with the supplied KSE mailbox, and no immediate upcall results.
238 However, an upcall will be triggered the next time the thread blocks and
239 the required conditions are met.
241 The kernel does not allow more KSEs to exist in a process than the
242 number of physical CPUs in the system (this number is available as the
246 Having more KSEs than CPUs would not add any value to the user process,
247 as the additional KSEs would just compete with each other for access to
249 Since the extra KSEs would always be side-lined, the result
250 to the application would be exactly the same as having fewer KSEs.
251 There may however be arbitrarily many user threads, and it is up to the
252 user thread scheduler to handle mapping the application's user threads
253 onto the available KSEs.
258 causes the KSE assigned to the currently running thread to be destroyed.
259 If this KSE is the last one in the process, there must be no remaining
260 threads associated with that process blocked in the kernel.
261 This system call does not return unless there is an error.
264 from the last thread is the same as calling
272 the KSE assigned to the currently running thread when it is not needed,
273 e.g., when there are more available KSEs than runnable user threads.
274 The thread converts to an upcall but does not get scheduled until
275 there is a new reason to do so, e.g., a previously
276 blocked thread becomes runnable, or the timeout expires.
279 does not return to the caller.
283 system call can be used by the UTS, when it has selected a new thread,
284 to switch to the context of that thread.
287 is machine dependent.
288 Some platforms do not need a system call to switch to a new context,
289 while others require its use in particular cases.
296 It causes the (parked) KSE associated with the mailbox pointed to by
298 to be woken up, causing it to upcall.
299 If the KSE has already woken up for another reason, this system call has no
307 .Dq "any KSE in the current process" .
310 .Fn kse_thr_interrupt
312 is used to interrupt a currently blocked thread.
313 The thread must either be blocked in the kernel or assigned to a KSE
315 The thread is then marked as interrupted.
316 As soon as the thread invokes an interruptible system call (or immediately
317 for threads already blocked in one), the thread will be made runnable again,
318 even though the kernel operation may not have completed.
319 The effect on the interrupted system call is the same as if it had been
320 interrupted by a signal; typically this means an error is returned with
327 The current implementation creates a special signal thread.
328 Kernel threads (KSEs) in a process mask all signals, and only the signal
329 thread waits for signals to be delivered to the process, the signal thread
331 for dispatching signals to user threads.
333 A downside of this is that if a multiplexed thread
336 syscall, its signal mask and pending signals may not be
337 available in the kernel.
339 in userland and the kernel does not know where to get them, however
341 requires them to be restored and passed them to new process.
342 Just setting the mask for the thread before calling
345 close approximation to the problem as it does not re-deliver back to the kernel
346 any pending signals that the old process may have blocked, and it allows a
347 window in which new signals may be delivered to the process between the setting
351 For now this problem has been solved by adding a special combined
352 .Fn kse_thr_interrupt Ns / Ns Fn execve
354 .Fn kse_thr_interrupt
357 .Fn kse_thr_interrupt
358 syscall has a sub command
359 .Dv KSE_INTR_EXECVE ,
360 that allows it to accept a
362 structure, and allowing it to adjust the signals and then atomically
366 Additional pending signals and the correct signal mask can be passed
367 to the kernel in this way.
368 The thread library overrides the
371 and translates it into
372 .Fn kse_intr_interrupt
373 call, allowing a multiplexed thread
374 to restore pending signals and the correct signal mask before doing the
376 This solution to the problem may change.
380 Each KSE has a unique mailbox for user-kernel communication defined in
382 Some of the fields there are:
385 describes the version of this structure and must be equal to
388 is an opaque pointer ignored by the kernel.
391 points to the KSE's upcall function;
392 it will be invoked using
394 which must remain valid for the lifetime of the KSE.
397 always points to the thread that is currently assigned to this KSE if any,
401 This field is modified by both the kernel and the user process as follows.
407 it is assumed to be pointing at the mailbox for the currently executing
408 thread, and the KSE may be unassigned, e.g., if the thread blocks in the
410 The kernel will then save the contents of
412 with the blocked thread, set
423 the kernel will never perform any upcalls with this KSE; in other words,
424 the KSE remains assigned to the thread even if it blocks.
428 while the KSE is executing critical user thread scheduler
429 code that would be disrupted by an intervening upcall;
436 in any upcall, the kernel always sets
440 Once the user thread scheduler has chosen a new thread to run,
443 at the thread's mailbox, re-enabling upcalls, and then resume the thread.
447 by the user thread scheduler must be atomic
448 with the loading of the context of the new thread, to avoid
449 the situation where the thread context area
450 may be modified by a blocking async operation, while there
451 is still valid information to be read out of it.
454 points to a linked list of user threads that have completed their work
455 in the kernel since the last upcall.
456 The user thread scheduler should put these threads back into its
458 Each thread in a process that completes a kernel operation
459 (synchronous or asynchronous) that results in an upcall is guaranteed to be
460 linked into exactly one KSE's
462 list; which KSE in the group, however, is indeterminate.
463 Furthermore, the completion will be reported in only one upcall.
466 contains the list of signals caught by this process since the previous
467 upcall to any KSE in the process.
468 As long as there exists one or more KSEs with an associated mailbox in
469 the user process, signals are delivered this way rather than the
471 (This has not been implemented and may change.)
474 is set by the kernel to the current system time before performing
478 may contain any of the following bits OR'ed together:
479 .Bl -tag -width indent
481 Block upcalls from happening.
482 The thread is in some critical section.
483 .It Dv KMF_NOCOMPLETED , KMF_DONE , KMF_BOUND
484 This thread should be considered to be permanently bound to
485 its KSE, and treated much like a non-threaded process would be.
491 .It Dv KMF_WAITSIGEVENT
492 Implement characteristics needed for the signal delivery thread.
497 Each user thread must have associated with it a unique
498 .Vt "struct kse_thr_mailbox"
501 It includes the following fields.
504 is an opaque pointer ignored by the kernel.
507 stores the context for the thread when the thread is blocked in user space.
508 This field is also updated by the kernel before a completed thread is returned
509 to the user thread scheduler via
515 threads together when returned by the kernel with an upcall.
516 The end of the list is marked with a
523 are time counters for user mode and kernel mode execution, respectively.
524 These counters count ticks of the statistics clock (see
526 While any thread is actively executing in the kernel, the corresponding
528 counter is incremented.
529 While any KSE is executing in user space and that KSE's
531 pointer is not equal to
535 counter is incremented.
538 may contain any of the following bits OR'ed together:
539 .Bl -tag -width indent
543 This flag inhibits upcalling for critical sections.
544 Some architectures require this to be in one place and some in the other.
551 .Fn kse_thr_interrupt
553 return zero if successful.
559 do not return if successful.
561 All of these system calls return a non-zero error code in case of an error.
569 There are already as many KSEs in the process as hardware processors.
571 The user is not the super user, and the soft resource limit corresponding
576 would be exceeded (see
582 points to an address which is not a valid part of the process address space.
591 The current KSE is the last in its process and there are still one or more
592 threads associated with the process blocked in the kernel.
594 The current KSE has no associated mailbox, i.e., the process is operating
595 in traditional, unthreaded mode (in this case use
597 to exit the process).
606 The current KSE has no associated mailbox, i.e., the process is operating is
607 traditional, unthreaded mode.
621 and the mailbox pointed to by
623 is not associated with any KSE in the process.
630 and the current KSE has no associated mailbox, i.e., the process is operating
631 in traditional, unthreaded mode.
635 .Fn kse_thr_interrupt
640 The thread corresponding to
642 is neither currently assigned to any KSE in the process nor blocked in the
650 .%A "Thomas E. Anderson"
651 .%A "Brian N. Bershad"
652 .%A "Edward D. Lazowska"
654 .%J "ACM Transactions on Computer Systems"
660 .%T "Scheduler activations: effective kernel support for the user-level management of parallelism"
663 The KSE system calls first appeared in
666 KSE was originally implemented by
668 .An "Julian Elischer" Aq julian@FreeBSD.org ,
669 with additional contributions by
670 .An "Jonathan Mini" Aq mini@FreeBSD.org ,
671 .An "Daniel Eischen" Aq deischen@FreeBSD.org ,
673 .An "David Xu" Aq davidxu@FreeBSD.org .
675 This manual page was written by
676 .An "Archie Cobbs" Aq archie@FreeBSD.org .