From: ken@cs.cornell.edu (Ken Birman)
Newsgroups: comp.sys.isis
Subject: Some thoughts on Isis threads
Date: 28 Sep 92 00:43:33 GMT
Organization: Cornell Univ. CS Dept, Ithaca NY 14853

\documentstyle[11pt,fullpage]{article}
%%% Make _ be itself except in math mode.
%%% Bug: _ in filenames is \input statements don't work!
\newcommand{\sub}{_} % Define a subscript command while _ still means subscript
\newcommand{\uscore}{\_\,} % An OK looking underscore. Could be better.
\catcode`_=\active   % Make _ an active character for the following defns.
\newcommand{_}{\ifmmode\sub\else\uscore\fi}


\begin{document}
\begin{center} {\bf SOME NOTES ON THREADS IN ISIS } \end{center}

\section{Overview}
Lightweight threads are generally recognized as necessary in 
systems that support RPC or communication, but have not yet become
widely standard on UNIX platforms.  For these reasons, Isis
employs a lighthweight threads model of its own, but maps it to
the prevailing package when one is available.

This short document is intended to provide an overview of the
approach, warn readers about some limitations, and describe some of the
more advanced features of the package.  

In Isis, a lightweight thread is represented by an area of memory
containing a {\em task table structure}, which Isis uses to represent
per-task information, and a {\em stack region}, within which the
lightweight stack is maintained.  On systems with their own 
threads package, the Isis stack region is empty; otherwise it is of
fixed size.  The default size is 16KB, chosen to be {\em small enough}
to force users to think about stack overflow and to explicitly 
work around it.  After all, any fixed size would have some risk of
overflow, and there is no way to support multiple threads with
private, dynamically extended stacks under UNIX.  Fixed size stack
regions are also a feature of the POSIX threads package.

Isis does check for stack overflow, but not in a systematic way.
The problem is that although Isis has a check routine, called
t_scheck(), it has no way to arrange for this routine to be
invoked when user code is running -- except, of course, if the
user happens to call into the Isis tasking package.  So, the
check is often skipped and code may experience undetected overflows.

Various strategies come to mind for detecting overflows; none works
very well.  It has been suggested that we should put some sort of
magic number at the top end of the stack and watch for corruption --
but this would detect problems ``late'', and might not detect them
at all: any procedure that allocates a local variable but doesn't
always assign it a value could ``skip over'' the region containing
the magic number, and indeed the type of casual allocation of large
objects on the stack that is most likely to provoke an overflow is also
least likely to be detected.

Using mmap(2), we could also map out the top page of each stack.
Unfortunately, mmap does not work on many platforms where Isis is
used.  (Isis users are welcome to do this themselves, at the start
of their top-level functions called from Isis.  We explain how, below).
Anyhow, even mapping out a page might not cause a stack problem to
be detected.

As a result, Isis users are urged to control their use of local
storage carefully, except when on the system-assigned ``main'' stack.
A primitive for requesting that Isis invoke a specified function on
the main stack (t_on_sys_stack) is also provided by the system.
Finally, {\em prior to calling isis_remote_init}, users can
override the default Isis stack size, either on a per-entry basis or
system-wide.  However, be aware that when calling into code you
didn't write, such as X-windows or database routines, there is no
safe way to anticipate the amount of stack space that could be 
consumed.  Our experience is that X-windows actually uses very little
stack space but that many commercial database products use huge
amounts of stack space and cannot be called safely from static
size stacks regardless of their size.

{\em WARNING: if you try and change a stack size AFTER calling
isis_remote_init, Isis may get confused about the size of
tasks that are already active and may segment fault
a little later.  Future releases of the system will
notice that you tried to do this and complain, but for now, be careful not to
call this routine after Isis is running.}

The 16K Isis limit was picked to avoid excessive memory utilization
on machines with 4MB memories.

\section{Preemption issues}
The Isis tasking system can be used with preemptive tasks, but
while in Isis, scheduling is non-preemptive.  That is, tasks
managed by Isis are always in one of two states: waiting for
some event, or runnable, and Isis itself makes sure that even if
the user thinks multiple tasks are runnable, in fact only one
task is ever runnable at a time.

Nonetheless, reentrancy can easily occur in Isis.  For example,
a procedure might call an Isis primitive that does IO or blocks
for some other reason, and could do this while searching a table or
otherwise ``sensitive'' to global variables and their values.
In such a situation, it is entirely possible that Isis will schedule
another task or accept an incoming message, and that such a task
could modify data structures shared with the blocked task, or
reenter a procedure that the blocked task was running.
To protect against this, we urge Isis users to use a notion of
critical sections within which globally visible data structures
are manipulated.  Here are procedures for entering and
exiting a critical section.  We assume that for each
critical section there is an integer variable ``inside'' and
a condition variable ``cond'', allocated by the application
developer, and initialized to zero.

\begin{verbatim}
int inside = 0;
condition cond = 0;

    ..... ready to touch a shared structure ....
    CsEnter(&inside,&cond);
       ... touch shared object ...
    CsExit(&inside,&cond);

CsEnter(int *inside_p, condition *cond_p)
  {
	if(*inside_p)
	    (void)t_wait_l(cond_p, "CsEnter");
	else
	    *inside_p = 1;
  }

CsExit(int *inside_p, condition *cond_p)
  {
	if(t_waiting(cond_p))
	    t_sig(cond_p, 0);
	else
	    *inside_p = 0;
  }
\end{verbatim}

These procedures are very inexpensive, and it is generally better
to do something like this much too often and in this way err on the side of
safety, than to call them too infrequently, and have an error result.
Notice that the specific code above can be changed but that
it is also easy to code this type of entry/exit procedure
incorrectly.  The code above will certainly work.

Notice that reentrancy can only occur when you invoke
an Isis procedure of some sort and it blocks using the Isis t_wait
primitive.  There is no risk of preemption during, say, execution of
X11 code or a database procedure provided by a vendor, since
such code would not make calls into Isis.  Thus, unless the vendor
code does some form of upcall into your code and your code enters
Isis, reentrancy is not a concern when combing Isis with software from
other vendors.

\section{Runtime information available in the task subsystem}
When in a task, Isis sets a global variable isis_ctp to the
task base.  isis_ctp->task_stack is the start of the
tasks stack region, and isis_ctp->task_end is the end of
the region (both are zero if the system is running over some
other package).  If Isis implements stacks itself, and tp
is the task base of a task that is blocked, then tp->task_env
is a jmp_buf initialized by setjmp and giving the registers
associated with the state of the task at the time that it blocked.

This information is printed in the client dump, and can be obtained
by a call to cl_dump(-1, "some sort of title");  The TASK entries
show some information derived from a loop that iterates over the
task structure, much as in the code below:

An example of a
loop that will iterate over the task structure is as follows:
\begin{verbatim}
{
	struct task *tp;
	struct qnode *qp;
	for(qp = isis_tasks->qu_next; qp != isis_tasks; qp = qp->qu_next)
	{
	    tp = qp->qu_task;
	    printf("task with tp %x has jmp_buf at %x\n", tp, &tp->task_env);
	}
}
\end{verbatim}

When using the obscured releases of Isis, include the following
defines before compiling this code:

\begin{verbatim}
#define qu_task A1
#define qnode   A2
#define qu_next P49d7b01a
#define isis_tasks V7d9df7ce
#define task_env T14f8f8a6
#define task_end R4a0efdce
\end{verbatim}

In general, the contents of a jmp_buf are defined somewhere in the
vendor documentation for the UNIX system on which you are running.
However, be aware that on some UNIX systems Isis has its own
version of setjmp/longjmp, and in these cases the jmp_buf may have
non-standard contents (on VMS, for example, this is the case).
To know if Isis is using the standard setjmp/longjmp on a
particular platform, look at clib/cl_tasks.c and see if setjmp/longjmp
are renamed isis_setjmp/isis_longjmp in that file.  If so, calls
YOUR code makes to setjmp/longjmp will work as expected, but Isis
will be using hand-coded versions of these routines, with the
code in clib/cl_setjmp.s

\section{Mapping the top page of the stack out}
This can be done using the mmap routine.  The top of the stack
starts at task_stack.  Note that since task_stack is not page-aligned
and that the page at the very top of the stack may be partially
filled with the Isis task structure itself, the page to map out
is the first full page starting at an address greater than or equal to
the value of tp->task_stack.

When using this approach, we recommend that the default stack size be
increased {\em prior to calling isis_init}.

\section{Allowing preemption}
When using a native threads package underneath Isis, it
is safe to call into Isis from a thread that Isis did not
create.  On entry, Isis arranges for such a thread to call
THREAD_ENTER_ISIS(), and this procedure acquires the Isis
mutex lock and sets up a task table entry for the caller.
On exit, THREAD_LEAVE_ISIS() deallocates the entry.

In a preemptive threads environment, a thread running within
Isis (and hence non-preemptively) can do the reverse sequence
to allow preemption to occur, or to allow itself to run in parallel
with the rest of Isis.
The sequence for this would be a call to THREAD_LEAVE_ISIS()
before running the preemptive code segment, followed by a call
to THREAD_ENTER_ISIS() when done.
If it is desired to call CsEnter(), do so {\em before} calling
THREAD_LEAVE_ISIS().  In this case, call CsExit() {\em after}
calling THREAD_ENTER_ISIS().

\section{Need to call isis_accept_events}
Isis uses a procedure called isis_accept_events to schedule
a number of important actions, such as accepting incoming messages,
retransmitting outgoing messages, and performing timed actions.
Needless to say, the performance of the system will be poor if
these actions are not taken within, say, a few seconds of when 
they are expected.  As a result, Isis users are encouraged to
call isis_accept_events periodically, even as often as 2 or 3 times
per second, to give Isis a chance to perform these critical
functions.

After a delay of 45 to 60 seconds beyond when isis_accept_events
was last called, an Isis application may be considered dead and
disconnected from the system.  Such an application can intercept
the disconnect event using isis_failed and reconnect, but this
is obviously not the most graceful way to write software for
a cooperative setting.

Isis imposes these annoying rules for a reason: they allow us to
use protocols that involve active participation by all members of
a group, or a set of groups.  In such protocols, large numbers of
processes can get stuck waiting for a message and it is important
that messages be sent in a timely manner.  Applications that don't
cooperate with Isis in this respect simply interfere with all the
applications that DO cooperate.

But, there is a down-side.  Any time that isis_accept_events
is called, there is a risk that Isis will spawn new user tasks
and these tasks could run and change data structures
that the application might be sensitive to.  So, be careful to
use the CsEnter and CsExit approach to guard such data structures
if there is any risk at all of unfortunate suprises.  Crude
locking is usually adequate for safe and problem-free programming,
while fine-grained locking is hard to design and tends to
expose the user to reentrancy bugs while not speeding things up
very much, anyhow.

\section{ITIMER and SIGIO interrupts}
Normally, Isis is not driven by interrupts.  However, using 
the ISIS_USEITIMER flag to isis_remote_init, you can enable
an interrupt-based mechanism that will call isis_accept_events
from SIGIO interrupts and itimer interrupts, which Isis will
schedule to keep itself reactive.  

This can introduce some reentrancy bugs if, say, an X11
procedure is running at the time that a SIGIO event occurs,
and the isis_accept_events invocation causes delivery of a
message that is handled by a procedure that calls back into X11.
X11 (for example) may not be designed to protect itself 
against reentrancy, and this raises all the concerns cited
in the introduction.

The only system procedures that Isis itself uses, and that could
cause problems of this sort, are malloc() and gethostbyname().
Calls to malloc() are handled by introducing a version of malloc()/free()
that we modified to set a flag, isis_in_critical, and to clear the
flag on exiting the routine.  When this flag is set, Isis will
not call isis_accept_events at interrupt time.  You can set
the flag yourself: ++isis_in_critical; ... --isis_in_critical; to
protect small regions of code from interrupt-driven calls into
isis_accept_events().

In general, even if interrupts are enabled, Isis will not
call isis_accept_events unless the following conditions hold.
Either the task that is running must be a child of a
top-level procedure that was declared to Isis via isis_may_preempt,
or the task must have used THREAD_LEAVE_ISIS() to leave
the Isis tasking system.  

The reader may wonder why we introduced the isis_in_critical flag:
it would seem that by calling THREAD_ENTER_ISIS(), malloc could
also have protected itself.  However, this might not be the case:
malloc() could be called within a task running a top-level
procedure declared via isis_may_preempt(), and in this case
extra calls to THREAD_ENTER_ISIS() wouldn't provide any additional
protection at all.
Thus, the extra flag.

\section{Debugging support}
Debugging code that uses light-weight threads can be tricky,
for several reasons.  Stack overflow is often suspected by
programmers, but in fact this is very uncommon in applications
designed with some care, and in any case it is easy to
detect by sugaring the user's code with calls to t_scheck().

However, the mere fact that stacks are allocated via malloc()
and that the task_env data structure contains critical register
values makes it especially easy to ``smash'' data structures used
in the Isis tasking subsystem (or other subsystems) by
overrunning a dynamically allocated object from application code.
This will cause a crash in some part of Isis, some time later,
and can be very confusing.

Reentrancy bugs can also come as a surprise to users who expect
the Isis tasking model, because it is non-preemptive, to be safe
from reentrancy.  We have even made this mistake ourselves in Isis
on several ocassions.  One learns from experience: code like the
CsEnter/CsExit sequence is common in Isis.

Finally, it is annoying to find that few (if any) debuggers have
mechanisms to deal with multithreaded applications -- even when
Isis is run on a platform with native threads.  In a pinch,
the loop given above can be used to iterate over the jmp_buf
structures for each inactive task, and from the sp/fp
values saved therein, the stack can be unwound with knowledge of
the C calling convention for the architecture being used.
Although somewhat painful, we have coded mechanisms of this sort
and used them to print stack traces for the tasks active in
our Isis applications.  However, it is far easier to modify
a debugger for which source is available to have a command
capable of printing the stack trace associated with a jmp_buf
structure, and then to invoke this command for each of the
stacks enumerated by the for-loop above.

As a general rule, though, we find it much easier to fix
reentrancy bugs by either avoiding them entirely using
coarse-grained barrier schemes, or by staring at the
place where a program died and waiting for insight to strike.
Isis is not in the business of doing threads packages or 
debuggers, and until the vendors start taking both of these
seriously, the situation is not likely to improve very much.
\end{document}
-- 
Kenneth P. Birman                              E-mail:  ken@cs.cornell.edu
4105 Upson Hall, Dept. of Computer Science     TEL:     607 255-9199 (office)
Cornell University Ithaca, NY 14853 (USA)      FAX:     607 255-4428