libpthread

[Neal H. Walfield]

I am extremely pleased to announce the first release of RMGPT, the
"Rubbish, I asked for mine with Minced Garlic, Please Take this back"
release [1].  RMGPT is (or rather, aspires to one day be) a complete,
portable implementation of IEEE Std 1003.1-2001 threads as known as
POSIX threads.

A project of this sort does not write and test itself.  First, I would
like to thank Roland: without his encouragement this past July to
complete and port my minimal pthread implementation to Mach, RMGPT
would never have become a reality.  I am also thankful for the
feedback I have received since the first alpha release: it has been
nothing but positive and encouraging.


Overview
========

This library can happily coexist with cthreads.  It provides all of
the call backs that glibc expects from the current implementation of
cthreads, including the initialization code, mutexes, stream locking
and thread specific data in an ABI compatible way.  This library
requires *no* changes to glibc.  This should make the migration path
from cthreads to pthread fairly painless and permit users to start to
take advantage of libpthread in the very near future.

All functions--both optional and required by POSIX threads--are
present in at least stub form.  Nearly all are implemented and tested.
This does not mean that they are bug free: we still need testers and
more test cases.  If you are looking to help, this is an excellent way
to get started.

There are several deficiencies that I hope to correct in the near
future.  The following list details all of the problems that I am
aware of; I am certain that there are more.


Interfaces
----------

All of the definitions are either in <pthread.h> or the appropriate
"bits" file.  There are two definitions which are present in
<pthread.h> which do not belong there: pthread_kill and
pthread_sigmask.  POSIX states that these function definitions shall
be made available by including <signal.h>.  Without actually changing
the installed <signal.h>, this is difficult.  This should not pose a
real problem for general usage--at best there may be a warning or two.


pthread_atfork
--------------

This is currently unimplemented.  It either requires hooks in glibc
(c.f. libc/sysdeps/mach/hurd/fork.c) or a custom fork implementation
that wraps the fork in the underlying libc using dlopen et al.  The
latter is clearly less intrusive and more portable, however, I am not
sure of its affects on static linking.  I will implement this later
once I understand the problem a bit better.  As the stub for
pthread_atfork is already present, a future implementation should have
no impact on the ABI.


Static Linking
--------------

Because most functions are implemented in individual files, there must
be an explicit dependency to pull a given function in.  Since
`-lpthread' normally appears before `-lc' on the link line, the
initialization routines and cthread compatibility are not added to the
final executable.  To get around this, `-u_cthread_init_routine' et
al. can be added, however, there must be a more elegant way to do this
perhaps using a linker script that undefines the appropriate symbols
and then pulls in libpthread.


Versioning
----------

I have not yet written a versioning script.  I feel that using
HURD_CTHREADS_0.3 is wrong.  Additionally, the symbol we choose may
depend on where libpthread will be included.


Scheduling and Thread Priorities
--------------------------------

There is no support for any of this.  All of the following functions
are stubs:

     pthread_attr_getinheritsched
     pthread_attr_setinheritsched
     pthread_attr_getschedparam
     pthread_attr_setschedparam
     pthread_attr_getschedpolicy
     pthread_attr_setschedpolicy
     pthread_attr_getscope
     pthread_attr_setscope

     pthread_mutexattr_getprioceiling
     pthread_mutexattr_setprioceiling
     pthread_mutexattr_getprotocol
     pthread_mutexattr_setprotocol
     pthread_mutex_getprioceiling
     pthread_mutex_setprioceiling

     pthread_setschedprio
     pthread_getschedparam
     pthread_setschedparam

I really need some hints on how to proceed with the implementation of
these functions.  At the moment, it seems that we either have to
maintain the wait queues in priority order (which means a lot of
possible shuffling if the priorities change) or multiple queues.  Can
the kernel help in any way here?  This is further complicated as we do
not implement most scheduling functions at the process level, for
instance, sched_setscheduler, sched_setparam and sched_getparam are
stubs which return ENOSYS.


Stacks
------

Stacks default to two megabytes; we may want to reduce this to 64k
which is what cthreads currently uses.  This value cannot be changed
as we use the Hurd TSD implementation which requires fixed sized
stacks to function correctly.  To move away from this model would
require reorganization in glibc (c.f. <hurd/threadvar.h>).  Despite
this, user stacks can be used (by calling pthread_attr_getstackaddr,
pthread_attr_setstackaddr, pthread_attr_getstack,
pthread_attr_setstack, pthread_attr_getstacksize and
pthread_attr_setstacksize) as long as the supplied stack is of the
correct size and has the appropriate alignment.

Stack guards are also supported.  They are tested and appear to work.


Process Shared Attribute
------------------------

Currently, there is no real support for the process shared attribute.
Spin locks should, however, work as we just use a test and set, yield
loop.  On the other hand, barriers, conditions, mutexes and rwlocks
signal wakeups by queuing messages on ports whose names are process
local.

One solution I have consider in passing is to hash to local data using
the address of the shared data structure as the key.  The first thread
that blocks per process would spin on the shared memory area; all
others would block as normal.  When the resource became available, the
first thread would signal the other local threads as necessary.
Alternatively, there could be an external server.  This may, however,
open a large security whole; I need to consider it more.


Cancelation
-----------

The only cancelation points are in pthread_join, pthread_cond_wait,
pthead_cond_timedwait and pthread_testcancel.  I need to do some more
research to determine if attaching a function to
hurd_sigstate->cancel_hook (c.f. <hurd/signal.h>) will provide the
desired semantics.  If not, we must either wrap some functions using
dlopen or integrate with glibc.

The implementation of asynchronous cancelation injects a new IP into
the canceled thread which runs the cancelation handlers in its
context (c.f. sysdeps/mach/hurd/pt-docancel.c) and then calls
pthread_exit.  The handlers need to have access to the stack as they
may use local variables.  I think that the current method may leave
the frame pointer in a corrupted state if the thread was in, for
instance, the middle of a function call.  I would like third party
confirmation that the implementation is in fact robust.


Waking Up
---------

When a thread blocks, it adds itself to a queue attached to the
particular resource it is interested in.  It then waits for a message
on a thread local port.  To wake it up, a thread queues a message on
the waiter's port.  If the wakeup is a broadcast wakeup
(e.g. pthread_cond_broadcast, pthread_barrier_wait and
pthread_rdlock_unlock), the waker thread must send N messages where N
is the number of waiting threads on the queue.  If all the threads
instead receive on a lock local (i.e. as opposed to thread local) port
then the thread which eventually does the wakeup needs to do just one
operation, mach_port_destroy, to wakeup all of the waiting threads
(they would get MACH_RCV_PORT_DIED back from mach_msg).  Note that
there is a trade off: the port must be recreated.  This needs to be
implemented, tested and benchmarked.

This approach sounds nice until we consider scheduling priorities:
there may be a preference for certain threads to wakeup before others
(especially if we are not doing a broadcast, for instance,
pthread_mutex_unlock and pthread_cond_signal).  If the outlined
approach is taken, the kernel chooses which threads are awakened.  If
we find that the kernel makes the wrong choices, we can still beat it
by merging the two algorithms and having a list of ports sorted in
priority order.  The waker could then mach_port_destroy or queue a
message on a port as appropriate.


Barriers
--------

Barriers may be slow as the contention can be very high.  The waiting
algorithm presented above may offer substantial gains.  The
improvement may be further augmented with an initial number of spins
and yields: it is expected that all of the threads reach the barrier
within close succession, thus just queuing a message may turn out to
be more expensive.  This needs to be implemented and benchmarked.


Clocks
------

pthread_condattr_setclock permits a process to specify a clock for use
with pthread_cond_timedwait.  What is the correct default for this?
Right now, it uses CLOCK_REALTIME, however, the underlying
implementation is really using the system clock (gettimeofday) which,
if I understand correctly, is completely different.

An important question I have is: can we even use other clocks?
mach_msg uses a relative time against the system clock.  I am not
aware of a way to override this.

pthread_getcpuclockid just returns CLOCK_THREAD_CPUTIME_ID if defined.
Is this the correct behavior?


Timed Waiting
-------------

pthread_cond_timedwait, pthead_mutex_timedlock,
pthread_rwlock_timedrdlock and pthread_rwlock_timedwrlock all take
absolute times.  We need to convert them to relative times for
mach_msg.  Is there a way around this?  How will clock skew affect us?


Weak Aliases à la glibc
-----------------------

Mark used them in a way which seems to be a bit inconsistent with what
Roland describes in[2].  In the near future, I hope to take another
careful look at the code and try to pick up these type of nits.



The Souce
=========

I have uploaded a tarball to:

  ftp://alpha.gnu.org/gnu/hurd/contrib/neal/libpthread/

Compiling is easy, there is even a README included in the base
directory.  First you will need to download this tarball and the Hurd
source code from CVS (the Debian package is also okay).  Assuming that
the tarball is in your home directory, the Hurd source is in
$HOME/src/hurd and you build in $HOME/build/hurd, you would do the
following:

  # cd ~/src/hurd
  # sudo apt-get install autoconf2.13
  # tar xfvz ~/libpthread-20020928.tar.gz
  # mv libpthread-20020928 libpthread
  # patch -p0 < libpthread/hurd.diff
  # autconf2.13
  # cd ~/build/hurd
  # ../../src/hurd/configure --disable-profile
  # make libpthread
  # sudo make install
  # cd ~/src/hurd/libpthread/tests
  # make check

The test suite is not integrated with the Hurd build system: it would
take a lot of work which, if all goes well would be for naught, as it
will hopefully be replaced by automake in the near future.  Until
then, we will all have to deal with this hack.

If any tests fail, please report it to me with the corresponding
output file.  For instance, if test-1 fails, send me
$HOME/src/hurd/libpthread/test/test-1.out preferably with a back trace
from gdb and if possible a patch in unidiff format with GNU style
change log entries.  But failing that, just report the error.

If you have gotten this far then you are ready to start downloading
packages and compiling them.  I have tested a few, however, as more
are compiled, more bugs will surely be found.  Again, please report
them.

For those that are too lazy, I have also provided binaries at:

  http://people.debian.org/~neal

Just download the Debian package and install it using `dpkg -i'.

Of course a library by itself is relatively useless and not so
impressive, as such, I have compiled dillo, a small browser.  You can
also find that on my Debian homepage.


Conclusion
==========

In conclusion, thanks for listening.  I would love to get feedback,
bug reports, criticism, etc, send them all to neal@cs.uml.edu.

Thanks,
Neal



[1] Most new program names are a bunch of letters stuck together.
Only later does it become an acronym and the words become bound.  This
is boring; each new release of RMGPT will offer a fresh, new and
exciting expansion of the "acronym."

[2] http://sources.redhat.com/ml/libc-alpha/2002-08/msg00278.html