LURC: Light ULM/Reactive library for C

Latest news

We are now at version 0.5 with mutexes, which you can read about below.

What is LURC ?

LURC is a small lightweight version of ULM (only the reactive part) in a C library intended for substitution with PThreads or GNU Pth.

LURC supports the creation of synchronous cooperative threads, synchronising and communicating with eachother using signals in a deterministic scheduler.

What features does LURC have ?

  • Synchronous cooperative threads

    Threads are executed in their order of creation, one at a time, each cooperating with the others to let them execute too. Execution time is divided in abstract time slices called instants. Each instant ends when all threads are blocked.

    Threads can cooperate (and let the other threads run) by waiting for the next instant. This will block the thread until the scheduler declares the start of the next instant, when it will be allowed to resume execution. Cooperation can also be achieved by waiting for a signal (see below).

    // the thread's function
    void thread_func(void *arg){
      while(1){
        // print our message
        printf("%s\n", (char*)arg);
        // then cooperate
        lurc_pause();
      }
    }
    int main(int argc, char **argv){
      // create two threads
      lurc_thread_create(NULL, NULL, &thread_func, "A");
      lurc_thread_create(NULL, NULL, &thread_func, "B");
      // and schedule them now
      lurc_main();
      return 0;
    }
  • Deterministic scheduler

    LURC has a deterministic scheduler: this means that the scheduling of a given program will be the same at every execution. This helps a lot in figuring out what your program does, and at reproducing bugs related to thread synchronisation.

  • Multiple flavours of threads

    LURC has four types of threads, all of them with different properties but all operating under the same deterministic semantics when cooperative. All types of threads can run next to the other under the same scheduler. Here are the main differences between them:

    • Synchronous Copy: this is the default type of thread, it is purely cooperative and they all share a common stack, which is saved and restored when cooperating. Memory usage for each thread is minimal, this is recommended for threads with a small stack usage.
    • Synchronous Jump: another purely cooperative thread, but they each have their own separate stack. Memory usage depends on the initial stack size, but is usually higher, while cooperation time is fastest. This type is recommended for threads with a high stack usage.
    • Asynchronous Lock: cooperative threads which can become asynchronous and free from the scheduler at run-time, and of course they can become synchronous again later on. This is based on PThreads, where each thread uses PThread locks when cooperative in order to cooperate. This type of thread is recommended for threads which are mainly asynchronous.
    • Asynchronous Jump: another thread which can become asynchronous, but when it is cooperative, its underlying PThread is sleeping, thus yielding the same performance as the Synchronous Jump type when cooperating. This is recommended for threads which are mainly synchronous.

    As you can see, each thread has its own distinct implementation and advantages, and they can all run next to one another, so it's up to the programmer to find the thread type most suited to each thread.

  • Synchronisation and communication via signals

    Signals are the main communication means in LURC. They are objects that can have two states: unemitted and emitted. Every signal starts each instant in its unemitted state, until a thread emits it, which changes its state to emitted until the next instant.

    Threads can wait for signals, in which case the waiting thread will resume when the signal becomes emitted (or not wait at all if it was already). More than one thread can wait for a given signal, and emitting that signal will wake up all the threads waiting for it (emission is broadcast to every thread).

    void hello_func(void *_sig){
      // get the signal parameter
      lurc_signal_t sig = (lurc_signal_t)_sig;
      while(1){
        // print the first part
        printf("Hello ");
        // awaken the second thread
        lurc_signal_emit(sig);
        // and cooperate to it
        lurc_pause();
      }
    }

    void world_func(void *_sig){
      // get the signal parameter
      lurc_signal_t sig = (lurc_signal_t)_sig;
      while(1){
        // await the signal from the first thread
        lurc_signal_await(sig);
        // print the second part
        printf("World\n");
        // and cooperate
        lurc_pause();
      }
    }

    int main(int argc, char **argv){
      // create a new signal
      lurc_signal_t relay = lurc_signal("my signal");
      // and two threads
      lurc_thread_create(NULL, NULL, &hello_func, sig);
      lurc_thread_create(NULL, NULL, &world_func, sig);
      // and schedule them now
      lurc_main();
      // free the signal now
      lurc_signal_destroy(&relay);
      return 0;
    }
  • Synchronisation via mutexes

    There are two cases where you want to use Mutexes in a cooperative world like LURC. The first is when you want to cooperate (or you want to wait for a signal) in the middle of a critical section. The second is when you're not a cooperative thread! This happens of course if a thread is detached and becomes asynchronous.

    Well rest assured, whether a thread is cooperative or synchronous, it can rely on the mutex locking and unlocking functions to save your critical sections.

  • Integrated syntax for callbacks with 0+ parameter

    Using GCC macros it is possible to declare callbacks with more than just a single void* parameter. This macro declares convenience functions for thread creation using the correct types and number of parameters, before packing and unpacking them for the callback.

    // Declare a callback function with no parameter:
    // This is equivalent to:
    // void printer(void *p){ ... }
    lurc_cb(printer){
      while(1){
        printf("Hello World\n");
        // cooperate
        lurc_pause();
      }
    }

    // Declare a callback function with two parameters:
    // This is equivalent to:
    // void printer(void *p){ /* do some unpacking of p */ ... }
    lurc_cb2(param_printer, int, fd, char*, mesg){
      // in this callback, the arguments fd and mesg are declared with the
      // correct in and char* types
      while(1){
        fprintf(fd, "%s\n", mesg);
        // cooperate
        lurc_pause();
      }
    }

    int main(int argc, char **argv){
      // start the printer thread with the macro-generated function
      printer_thread(NULL, NULL);
      // and the one with parameters
      param_printer_thread(NULL, NULL, 0, "Hello World");
      // and schedule them
      lurc_main();
      return 0;
    }
  • Suspension blocks

    Threads can enter special control blocks called suspension blocks, which will suspend the execution of the block whenever a given signal is not emitted. This means the block will start every instant suspended, waiting for the signal to be emitted, which will then allow the block to resume execution until at most the end of the instant.

    lurc_cb(pair_printer){
      // this function is allowed to be executed at every
      // instant when the pair signal is emitted
      while(1){
        printf("Pair emitted\n");
        // and cooperate
        lurc_pause();
        // we won't get to the next instant until pair
        // is emitted again
      }
    }

    lurc_cb1(tpair, lurc_signal_t, pair){
      // now enter the pair_func block when the pair signal is emitted
      // this function is macro-generated by lurc_cb
      pair_printer_when(&pair, NULL);
    }

    lurc_cb1(emitter, lurc_signal_t, pair){
      int i=0;
      while(++i){
        // if this is an even iteration, emit the signal
        if((i % 2) == 0)
          lurc_signal_emit(&pair);
        printf("Iteration %d\n", i);
        // and cooperate
        lurc_pause();
      }
    }

    int main(int argc, char **argv){
      // create a signal
      lurc_signal_t pair = lurc_signal("pair signal");
      // create the thread emitting the signal
      emitter_thread(NULL, NULL, pair);
      // and the one waiting for it
      tpair_thread(NULL, NULL,  pair);
      // and schedule them now
      lurc_main();
      // free the signal now
      lurc_signal_destroy(&pair);
      return 0;
    }
  • Preemption blocks

    Threads can enter special control blocks called preemption blocks, which will execute the block normally, but will terminate it at the end of the first instant where a given signal is emitted. This serves as a try/catch block in which exceptions are signals and can thus be emitted by any thread.

    // this thread emits a signal after n instants
    lurc_cb2(timer, int, n, lurc_signal_t, sig){
      // wait for n instants
      while(n-- > 0){
        lurc_pause();
      }
      // then emit the signal
      lurc_signal_emit(&sig);
    }

    // this function executes the given callback for
    // up to n instants maximum
    void exec_up_to(int n, lurc_cb_t cb){
      // create a signal for the preemption
      lurc_signal_t kill = lurc_signal("killer signal");
      // create the thread that will emit it in n instants
      timer_thread(NULL, NULL, n, kill);
      // now enter a preemption context for at most n instants
      lurc_watch(&kill, cb, NULL);
      // we can free the signal now
      lurc_signal_destroy(&kill);
    }

    // this function prints forever
    lurc_cb(printer){
      while(1){
        printf("Hello\n");
        lurc_pause();
      }
    }

    // this function waits forever
    lurc_cb(waiter){
      // create a signal
      lurc_signal_t sig = lurc_signal("never emitted");
      // and await it forever
      lurc_signal_await(&sig);
      // ooops this signal is never freed... see below for protection blocks
    }

    // this is the main thread
    lurc_cb(lmain){
      // wait for an absent signal for at most 2+1 instants
      exec_up_to(2, &waiter);
      // print Hello for at most 3+1 instants
      exec_up_tp(3, &printer);
    }

    int main(int argc, char **argv){
      // create the main thread
      lmain_thread(NULL, NULL);
      // and schedule it now
      lurc_main();
      return 0;
    }
  • Protection blocks

    Threads can enter special control blocks called protection blocks, composed of two parts: the protected block and the protector block. The principle is that the protected block will be executed normally, and when that block either terminates, or is preempted, the protector block will be executed. When the protector block has terminated, if the protected block terminated normally, the protection block terminates, and if the protector block was preempted, preemption is resumed upwards.

    Note that since preemption is decided at the end of instant, it is executed at the next instant. Therefore when the protected block is preempted, the protector block is executed at the next instant.

    // this function prints forever on the given file
    lurc_cb1(printer, int, fd){
      char *buf = "Hello\n";
      while(1){
        // print to the file
        write(fd, buf, 6);
        // and cooperate
        lurc_pause();
      }
    }

    // this function closes the file descriptor
    lurc_cb1(closer, int, fd){
      // close it
      close(fd);
    }

    // do the printing while protecting the file
    lurc_cb(protected_printer){
      // open the file
      int fd = open("log.txt", O_WRONLY | O_APPEND);
      // print while making sure preemption won't prevent
      // us from closing the file
      lurc_protect_with(&printer_func, fd, &closer_func, fd);
    }

    void lmain(void *p){
      // let's print the logs for at most 10 instants
      // (see preemption above for exec_up_to())
      exec_up_to(10, &protected_printer);
    }

    int main(int argc, char **argv){
      // create the main thread
      lmain_thread(NULL, NULL);
      // and schedule it now
      lurc_main();
      return 0;
    }
  • Integrated syntax for control blocks

    The three control block features can be used either as a library function, by passing pointers to the function blocks as parameters, or can be used inline, using GCC macros to generate nested functions in order to call those library functions and still capture the local environment.

    The syntax integrates seamlessly with other C control blocks like for, while or case.

    // let's do the Protector block example again with the new syntax:

    // this function prints until preempted on the given file, and
    // then closes it
    lurc_cb(protected_printer){
      int fd = open("log.txt", O_WRONLY | O_APPEND);
      LURC_PROTECT{
        char *buf = "Hello\n";
        while(1){
          // print to the file
          write(fd, buf, 6);
          // and cooperate
          lurc_pause();
        }
      }LURC_WITH{
        // close it
        close(fd);
      }LURC_PROTECT_END;
    }

    void lmain(void *p){
      // let's print the logs for at most 10 instants
      // (see preemption above for exec_up_to())
      exec_up_to(10, &protected_printer);
    }

    int main(int argc, char **argv){
      // create the main thread
      lmain_thread(NULL, NULL);
      // and schedule it now
      lurc_main();
      return 0;
    }
  • Integration of the REL (Reactive Event Loop) model

    LURC integrates the cooperative reactive scheduling of threads with an Event Loop model, thus creating a Reactive Event Loop where Events are represented by signals and emitted by the scheduler automatically. Integration of threading and Event Loop based programming has never been easier.

    LURC features two types of REL signals: Input/Output and timeout signals. The first will be emitted whenever a certain event happens on a given file descriptor, while the second will be emitted after a certain ammount of time.

    // this thread ticks when the given timeout is reached
    lurc_cb1(ticker, struct timeval, timeout){
      // make a timeout signal
      lurc_signal_t s = lurc_timeout_signal("timeout", timeout);
      // the macro form for inline suspension blocks: execute when timeout
      // has been reached
      LURC_WHEN(&s){
        while(1){
          printf("Tick\n");
          // cooperate
          lurc_pause();
        }
      }
    }

    // this thread reads stdin whenever ready
    lurc_cb(reader){
      // create a signal for stdin
      lurc_signal_t s = lurc_io_signal("stdin", 0, LURC_EVT_READ);
      // the macro form for inline suspension blocks: execute when data
      // available on stdin
      LURC_WHEN(&s){
        while(1){
          int n;
          char buf[1024];
          if((n = read(0, buf, 1023)) > 0){
            // we have data
            buf[n] = 0;
            printf("Data: %s", buf);
            // cooperate
            lurc_pause();
          }else{
            // end of file
            break;
          }
        }
      }
      // we can now free that signal
      lurc_signal_destroy(&s);
    }

    int main(int argc, char **argv){
      // create the ticker for every 2.0 seconds
      ticker_thread(NULL, NULL, {2,0});
      // and the stdin reader
      reader_thread(NULL, NULL);
      // and schedule them
      lurc_main();
      return 0;
    }
  • Asynchronisation of threads

    LURC threads always start in a cooperative state, but it is possible to create LURC threads which can become asynchronous when needed, and return to synchronous cooperative scheduling whenever they want.

    lurc_cb(sync_async){
      int i = 0;
      // we start synchronous
      int async = 0;
      while(++i){
        // switch state every 100 iterations
        if((i % 100) == 0){
          if(async){
            // become synchronous
            lurc_attach();
            async = 0;
          }else{
            // become asynchronous
            lurc_detach();
            async = 1;
          }
        }
        // print something
        printf("A[%d]: %s\n", i, async ? "async" : "sync");
        // and cooperate (noop if we're async)
        lurc_pause();
      }
    }

    lurc_cb(sync){
      int i=0;
      while(++i){
        // print the current iteration
        printf("A[%d]\n", i);
        // cooperate
        lurc_pause();
      }
    }

    int main(int argc, char **argv){
      // start the asynchronous thread
      lurc_thread_attr_t attr;
      lurc_thread_attr_init(&attr);
      lurc_thread_attr_settype(&attr, LURC_THREAD_ASYNC_LOCK_TYPE);
      sync_async_thread(NULL, &attr);
      lurc_thread_attr_destroy(&attr);
      // and the sync one
      sync_thread(NULL, NULL);
      // now schedule them
      lurc_main();
      return 0;
    }
  • TSD (Thread-Specific Data) storage

    Preliminary for Thread-Specific Data is included in LURC, which allows each thread to have a pointer to a data area that is specific to this thread alone. An example of how to extend it to have PThread-like TSD is included here, but is not the default, since doing TSD with Hash Tables can be preferred in some situations, which LURC lets you do.

  • GC (Garbage-Collector) integration

    LURC provides an API for GCs to use when they want to garbage-collect an application using LURC threads. Some patches are available to make the Boehm-Demers-Weiser GC work with LURC, but this should be sufficient for most GCs out there.

On what hardware/OS does LURC run?

LURC has been tested on i386, amd_64 and powerpc architectures, on Linux and Mac OSX, but is written in portable GCC C and thus should work on most architectures and OSes on which modern GCC runs.

 
As far as I'm concerned, style is something that happens to other people...