Overview

libshelter
Author: Zachary Anderson (zanderso@gmail.com)

Overview:
This is the runtime library for Shelters:

Zachary Anderson, David Gay
Composable, Nestable, Pessimistic Atomic Statements
OOPSLA 2011

This code is GPL'd. See the LICENSE file for details.
--------------------------------------------------------------------------------

Dependencies:

Verified on Ubuntu 10.04 and 11.10 [Probably also works on more recent versions]
running on Intel Q6700 processor.

Makefile generated with cmake. With Ubuntu, just install the Ubuntu package.

The implementation uses some of the atomic built-in functions that are offered
by gcc, so a gcc version that includes those would be best.

Porting to a different ISA is probably just a matter of rewriting the inline
assembly if your gcc version doesn't support the atomic builtins, though
using Hans Boehm's libatomic is probably a better choice. Porting to an
architecture with a different memory model is probably difficult since it is
unlikely that I have memory barriers, etc. in all the right places.

Building:

$ cmake .
$ make
$ sudo make install

Usage:

#include <shelter.h>

shelter_t s;
data_t d;
shelter_init(&s, 0, NULL);

shelter_register1(SHELTER_WRITE, 0, &s);

shelter_wait(SHELTER_WRITE, &s);
d = ...;
...
shelter_release_all();

Link with -lshelter

Shelters make sure that thread-shared data is accessed safely. Before accessing
thread-shared data, you must "register" the shelter to indicate the beginning
of the critical section for that data. Then within the critical section, you
must "wait" on the shelter before accessing the data. At the end of the
critical section you "release" the shelters.

The API:

void shelter_system_init() 

Call before any other shelters calls are made, and before any threads are
spawned to initialize the shelters library



void shelter_thread_init() 

Call in a spawned thread before any other shelters calls are made to initialize
thread private shelters data structures



void shelter_thread_destroy()

Call before a thread exits, and at program exit to deallocate thread private
structures



void shelter_init(shelter_t *s, int shadow, shelter_t *parent)

Call to initialize a shelter s. If shadow is non-zero, then the shelter is
treated as a shadow shelter. parent indicates the parent of the shelter s in the
shelter hierarchy. parent should be NULL if the shelter has no parent.



void shelter_reparent(shelter_t *s, int num, shelter_t *parent)

Set the parent of the array of num shelters based at s to parent. Bad things
will happen if any threads are registered for the shelters in s while this
function is called.



void shelter_register1(shelter_access_t at, int later, shelter_t *s)

Causes a thread to register for access to a shelter s. The access type at
indicates whether the thread will read (SHELTER_READ) or write (SHELTER_WRITE)
the data protected by the shelter. A non-zero value of later indicates that
there may be a shelter_register call on the same shelter, or one of its
descendants, with a value of 0 for later before a call to shelter_release_all().

***A shelter or one of its ancestors must be passed to shelter_register with a
non-zero value of later if it will be passed to shelter_register with a zero
value of later before an intervening call to shelter_release_all().***

***Strange, undefined, or incorrect behavior (including a program crash with a
mysterious unhelpful error message) may result if shelter_wait() is called on a
shelter when it or one of its ancestors is not currently registered with a later
value of 0.***

It is safe to register for a shelter with a zero value of later after having
already done so without an intervening call to shelter_release_all().

The functions shelter_register[2-5]() are the same as shelter_register1, but
taking arguments for 2 - 5 shelters. shelter_register(int n, ...) takes
arguments for an arbitrary number of shelters indicated by the first argument.



void shelter_wait(shelter_access_t at, shelter_t *s)

This call must be made before accessing data protected by the shelter s. s or
one of its ancestors, must already have been registered with a later value of 0.
The argument at indicates the access type, as in shelter_register.

***Incorrect behavior will result if shelter_wait is not called before the first
access to data protected by a shelter within a critical section where that
shelter or one of its ancestors has been registered.***

Corollary: Since shelter_wait can only be called on a shelter after it (or
an ancestor) has been registered with a later value of 0, and before the
matching call to shelter_release_all(), incorrect behavior will result if
data protected by a shelter is accessed outside of a critical section
delimited by shelter registration and release.



void shelter_release_all()

This function is deceptively named. It does not release all shelters, but only
those from the most recent shelter_register call that hasn't already been
matched by a call to shelter_release_all().



void shelter_cond_init(shelter_cond_t *scv)
void shelter_cond_signal(shelter_cond_t *scv)
void shelter_cond_broadcast(shelter_cond_t *scv)
void shelter_ll_release_and_wait(shelter_cond_t *scv)

These functions act as condition variables for shelters. The first three
functions behave as pthread condition variables. shelter_ll_release_and_wait()
is a bit different. It has the effect of calling shelter_release_all() before
blocking to wait for a signal. So, you would do something like:

shelter_register1(SHELTER_WRITE, 0, s);
while(!cond) {
  shelter_ll_release_and_wait(scv);
  shelter_register1(SHELTER_WRITE, 0, s);
}
// do whatever with things sheltered by s
shelter_release_all();
shelter_cond_signal(scv);




Example:
See the code in tests/liveness_test.c for a simple example of correct use.

Warnings:
I have not tested with hierarchies taller than 3 levels. Since calls to this API
were intended to be generated by a compiler such that misuses were compiler
bugs, there isn't much in the way of communication from the library when it
isn't used correctly. You might get an assertion failure. Then again, maybe not.

TODO:
Document shadow shelters. Add an example/test for open-nesting.