\documentclass[twocolumn,a4paper]{article}      % -*- latex -*-

\author{
	Mark Probst\\
	{\tt http://www.unix.cslab.tuwien.ac.at/\char'176schani/}
	}
\title{Threads in Cacao}

\newcommand{\globvarslabel}[1]{\mbox{\texttt{#1}}\hfil}
\newenvironment{globvars}
    {\begin{list}{}%
           {\renewcommand{\makelabel}{\globvarslabel}%
           }%
    }%
    {\end{list}}

\newcommand{\structdesclabel}[1]{\mbox{\texttt{#1}}\hfil}
\newenvironment{structdesc}
    {\begin{list}{}%
           {\renewcommand{\makelabel}{\structdesclabel}%
           }%
    }%
    {\end{list}}

\begin{document}

\maketitle

\section{Overview}
\label{sec:overview}

To fulfill its role as a Java runtime environment, Cacao has to
provide support for threads. A thread in Java is what is generally
understood as a 'thread' in computer science: a context of execution
within a process that shares resources (virtual memory, file
descriptors, \dots ) with all other threads in the same process.

The Java Virtual Machine Specification does not specify how threads
should be implemented, so we had two alternatives to choose from:

\begin{enumerate}
\item Implementing Java threads using the corresponding thread implementation of the
underlying operating system.
\item Using just one operating system thread and implementing Java threads by doing
everything 'by hand'.
\end{enumerate}

A third alternative, namely using processes to emulate threads, is not
viable, because the sharing of all resources between processes (at
least UNIX processes) is almost impossible.

Both alternatives have their own advantages and drawbacks. Using
operating system threads avoids implementing all the gory details of
threads and gives scheduling control to the operating system, meaning
that it is not only preemptive but also multi-processor-aware.
Rolling it our own, on the other hand, does not waste operating system
resources (imagine a Java application that spawns over a hundred
threads!) and gives us much more control over thread-switching, which
makes it a lot easier to avoid synchronization problems. Furthermore,
it makes it possible to port Cacao to platforms which do not support
threads at the operating system level.

Since there already was a user-level thread implementation for a Java
virtual machine available as free software, we chose to build upon it,
thereby avoiding all the nasty coding details, without giving up the
advantages of user-level threads. We did, however, leave open the
possibility of replacing the user-level threads with an operating
system implementation.

As outlined in the previous paragraph, the threading code of Cacao is
based on the code of Tim Wilkinson's Kaffe (version 0.7), which has
been released under a BSD-style license.  We had to make a few
adjustments to the code, mainly making it '64-bit-aware'.

\section{Main Parts of the System}
\label{sec:mainparts}

The bulk of the threading system is located in the \texttt{threads/}
directory of the Cacao distribution. \texttt{threads/thread.c}
contains the thread management code (starting, suspending, killing,
\dots ), \texttt{threads/locks.c} contains the implementation of
synchronization primitives, which are discussed in more detail in
section~\ref{sec:synchronization}.
\texttt{threads/threadio.c} implements thread-aware I/O, which is detailed in
section~\ref{sec:io}.

The platform dependent parts of the system (which are pretty few) are
to be found in the files \texttt{sysdep/threads.h} and
\texttt{sysdep/asmpart.c}. They are discussed in
section~\ref{sec:threadswitching}.

There are a few other locations where changes had to be made for
threading support which are described in
sections~\ref{sec:criticalsections} and~\ref{sec:gc}.

\section{Data Structures}
\label{sec:datastructures}

The \texttt{java.lang.Thread} class, as defined in Sunsoft's Java
Runtime Library, provides a private instance variable
\texttt{PrivateInfo} of pointer type, which is reserved for the
purposes of the runtime system. Cacao uses the integer value of
\texttt{PrivateInfo} as an index into the array \texttt{contexts[]}
(see section~\ref{sec:globalvars}), which contains context information
(most notably priority and stack information) of all live threads:

\begin{verbatim}
typedef struct _ctx
{
    bool free;
    u1 status;
    u1 priority;
    u1* restorePoint;
    u1* stackMem;
    u1* stackBase;
    u1* stackEnd;
    u1* usedStackTop;
    s8 time;
    java_objectheader *exceptionptr;
    struct _thread *nextlive;
    u1 flags;
} ctx;
\end{verbatim}

\begin{structdesc}

\item[free] Is \texttt{true} if this \texttt{ctx} is associated with a thread.

\item[status] One of \texttt{THREAD\_SUSPENDED}, \texttt{THREAD\_RUNNING} and
    \texttt{THREAD\_DEAD}.

\item[priority] The priority of the thread. Must be in the range \texttt{MIN\_PRIORITY} (1) to
    \texttt{MAX\_PRIORITY} (10).

\item[restorePoint] Top of the stack of the corresponding thread.

\item[stackMem] Begin of the region of memory allocated for the stack, including the
    guarding pages.

\item[stackBase] Begin of the region of memory that can actually be used for the stack (i.e.
    the memory right after the guarding pages).

\item[stackEnd] Pointer to the first byte of memory after the region allocated for the stack.

\item[usedStackTop] Pointer to the actual top of the stack. Only valid if the corresponding
    thread is not running.

\item[time] Not used yet.

\item[exceptionptr] Saves the \texttt{exceptionptr} of the corresponding thread if it is
    not running.

\item[nextlive] Maintains a link to the next thread in the \texttt{livethreads} list
    (see section~\ref{sec:globalvars}).

\item[flags] Bitwise combination of several flags. If \texttt{THREAD\_FLAGS\_NOSTACKALLOC}
    is set, then the thread stack should not be dealloced upon thread death.
    \texttt{THREAD\_FLAGS\_USER\_SUSPEND} is set after the thread has been suspended by the user
    (i.e. the thread was not suspended by a blocking operation). \texttt{THREAD\_FLAGS\_KILLED}
    seems not to be used.

\end{structdesc}

\section{Scheduling}
\label{sec:scheduling}

Thread scheduling is performed by the routine
\texttt{reschedule()}. It checks the lists
\texttt{threadQhead[]}, beginning with the highest priority. If a thread is found, it is
immediately switched to. This means that higher-priority threads
always take precedence over lower-priority ones. A low-priority thread
will only run if all higher-priority ones are suspended (e.g. through
blocking).

\section{Thread-Switching}
\label{sec:threadswitching}

Thread-switching is the only platform-dependent part of the Cacao
threading system. Currently, only an Alpha implementation is
available.

The thread-switch is a function (written in assembly language), which
does nothing more than to push all callee-saved registers to the
stack, switch to the stack of the new thread, pop all callee-saved
registers (from the switched-to stack) and return. The only problem is
the setting up of a new thread stack, which needs to contain values
for the callee-saved registers and the address of the thread-entry
routine (\texttt{firstStartThread()}) as the return address of the
function call.  See the files \texttt{alpha/threads.h} and
\texttt{alpha/asmpart.c} for how this is managed in the Alpha
implementation.

\section{Critical Sections}
\label{sec:criticalsections}

Although the threading system is in its current implementation not
preemptive, this is planned.  It will be utilizing alarm timer signals
to preempt the running thread at certain points in time.

In order to write reliable code in a preemptive environment, it is
necessary to make it possible to prohibit preemption during certain
critical sections. For this purpose two macros (\texttt{intsDisable()}
and \texttt{intsRestore()}) are defined that can be used to enter and
to exit critical sections which are guaranteed not to be
preempted. Critical sections can be nested.

Apart from the code for mutexes and conditions (see
section~\ref{sec:synchronization}) the whole just-in-time compiler is
not to be preempted since it is not only not reentrant but does also
alter tables that may crash other threads if not in a consistent
state. This is one of the main problems that must be solved when
attempting to use operating-system threads in Cacao.

The other critical part outside of the threading system is the memory
management. Allocation on the heap is regarded as a critical section
as well as garbage collection which is further described in
section~\ref{sec:gc}.

\section{Thread Stacks}
\label{sec:threadstacks}

UNIX provides for each process one stack that dynamically grows when
its top is reached.  Since there can be more than one thread running
in a Cacao process, there must be a way of providing stacks for the
other threads. Cacao does this by simply allocating a region of memory
and using it as the stack for a thread. This stack has, unfortunately,
not the capability of growing dynamically. Worse yet, since it is
allocated on the heap, there is not even a way of checking the stack
for overflow (except from checking upon each entry to a subroutine,
which is too much a penalty). The solution to the latter problem is
the allocation of additional guarding pages above the top of the stack
(i.e. before the stack). These pages are then (by virtue of the
\texttt{mprotect(2)} system call) made inaccessible to the process,
resulting in a \texttt{SEGV} signal when the stack has over-flown.

The size of the thread stacks can be altered with the \texttt{-tss}
command line option. The default size is 32k. The number of guarding
pages is by default 1 and can be changed with the
\texttt{-ngp} command line option (not yet implemented).

\section{Mutexes and Conditions}
\label{sec:synchronization}

In Java, each and every object has a mutex (used for the
\texttt{synchronized} directive) and a condition variable (used by the
\texttt{wait()}, \texttt{notify()} and
\texttt{notifyAll()} methods) attached. Since we did not want to include
these two data structures in each object, as they take up rather a lot
of space on a 64-bit architecture, we decided to create them on demand
and keep them in a hash table that is indexed by the address of the
object the mutex/condition belongs to. This way, we are able to
allocate these structures on-demand: an object's mutex is allocated
not upon object creation but when the mutex is locked. When the mutex
is unlocked, it is freed again. For detailed information on this
topic, see the paper `Monitors and Exceptions: How to efficiently
implement Java'.

Following are the structures of mutexes and conditions:

\begin{verbatim}
typedef struct _iMux {
    struct _thread* holder;
    int count;
    struct _thread* muxWaiters;
} iMux;
\end{verbatim}

\begin{structdesc}

\item[holder] Points to the thread that has currently locked the mutex. If the mutex is not
    locked, \texttt{holder} is \texttt{0}.

\item[count] How often the mutex is locked by the current thread. It is incremented each time
    the mutex is locked and decremented when the mutex is
    unlocked. \texttt{0} if the mutex is unlocked.

\item[muxWaiters] List of threads that are waiting on the mutex to become unlocked.

\end{structdesc}

\begin{verbatim}
typedef struct _iCv {
    struct _thread* cvWaiters;
    struct _iMux* mux;
} iCv;
\end{verbatim}

\begin{structdesc}

\item[cvWaiters] List of threads waiting on the condition to be signalled.

\item[mux] Mutex which was used to wait on the condition.

\end{structdesc}

\section{I/O}
\label{sec:io}

UNIX I/O is by default blocking, which is suboptimal for user-level
threads, since a blocking I/O call would not only block its own thread
but the whole process. For this purpose Cacao makes all file
descriptors use non-blocking I/O and, whenever a thread wants to make
an I/O call that would block, suspends this thread and does not resume
it until the call would not require blocking. In order to check that
condition, Cacao does a \texttt{select()} with all pending file
descriptors (in function \texttt{checkEvents()}) whenever a thread
switch is requested and resumes all threads that can continue.

\section{Garbage Collection}
\label{sec:gc}

Garbage collection requires special attention in a threaded
environment and more so in Cacao.  Cacao uses a recursive
mark-and-sweep garbage collector, which means that it is not reentrant
and may use up a lot of stack. This means not only that it has to run
without been preempted but also that it needs to run in a thread with
a lot of stack available, which is not the case for a standard
thread. The best solution is obviously to run it on the stack of the
main thread which grows automatically. This is exactly what Cacao
does. Since the stack tops of all threads are known at any time, it is
a trivial task to switch over to another stack. This is handled by the
system dependent function \texttt{asm\_switchstackandcall} (defined in
\texttt{sysdep/asmpart.c}).

Another problem that needs to be taken care of is that all objects
that are referenced by any live thread need to be marked. Furthermore,
\texttt{Thread} objects that correspond to live threads must also be
marked, even if they are not referenced by any thread (which is
possible). To serve both purposes the list \texttt{liveThreads}
contains all live threads.

\section{Global Variables}
\label{sec:globalvars}

\begin{globvars}

\item[int blockInts] Indicates whether execution is within a critical section. \texttt{0} if
    not, otherwise \texttt{>0}, depending on the nesting level.

\item[bool needReschedule] Is \texttt{true} if a thread switch should occur upon exit of
    the currently executed critical section, otherwise \texttt{false}.

\item[thread *currentThread] The currently executed thread.

\item[ctx contexts[\texttt{]}] Array containing \texttt{MAXTHREADS} thread contexts.
    Elements with
    \texttt{free==false} are not occupied. The fact that this array has a fixed size means
    that there is maximum number of threads. This may change in the future.

\item[thread *liveThreads] List of all live threads. The list is linked through the
    \texttt{nextlive} member of the corresponding contexts of the threads.

\item[thread *threadQhead[\texttt{]}] Array of lists of not-suspended live threads. Indexed
    by thread priority.

\end{globvars}

\section{To Be Done}

\begin{itemize}

\item Cross-check threading code with newest release of Kaffe.

\item Preemptive multi-threading through alarm-timers.

\item Implement thread-table more efficiently (maintain free-list).

\item Implement some missing command-line switches (\texttt{getopt} would be cool).

\end{itemize}

\end{document}