\ _/\_/            _ _      _             __/\__
 )   (_           (_) |    | |           _) :  (
~~)   (_       ___ _| | ___| | __      _)  : __(
   )   (_     / _ \ | |/ __| |/ /    _)    _(
   )    (    |  __/ | | (__|   <    )     (
    `-.  (_   \___|_|_|\___|_|\_\   )     (~~
      /__/                          )__  _(
     /   \                         //  || \\_

This is a standalone implementation of a concept called

• ordered read-write locks (ORWL)

that had been introduced in

Example for iterative code, in a thread context

for (C∷size iter = 0; iter < 1000; ++iter) {
   mtx_lock(&writerLock);
   // do something there
   ...
   mtx_lock(&readerLock);
   // use writer and reader
   for (C∷size i = 0; i < maxLen; ++i)
       writerVector[i] += readerVector[i];
   // do something there
   mtx_unlock(&readerLock);
   // do something there
   ...
   mtx_unlock(&writerLock);
}

• EILck is implemented with Modular C.
• EILck is interfaced with plain C and C++.
• EILck uses C11's atomic and Linux' futex for an efficient lock implementation.
• EILck is an example of developing with the comfort of Modular C but remaining compatible with traditional programming interfaces.

• A lock object (eilck∷obj) associates data and a FIFO
• The FIFO regulates access to the data.
• The data is usually not manipulated directly, but through handles, here eilck∷ehdl and eilck∷ihdl.

Traditional locks have usually two major events: lock and unlock.

EILck handles have three major control events

• require appends a handle to the tail of the specified FIFO
• acquire blocks until the handle is at the head of the FIFO
• release removes the handle from the head of the FIFO

Other controlling events may occur, such as test or drop, but these should be much less frequent.

A handle is be typed for its access permissions:

• eilck∷ehdl: exclusive access, write permission to the data
• eilck∷ihdl: inclusive access, read-only permission to the data

An exclusive handle X at the head of the FIFO, is the only one.

• All other handles that try to acquire will block until X calls release.

Several consecutive inclusive require obtain a common position.

• The handles acquire the lock all at the same time.
• All consecutive inclusive require operations form a group until an exclusive require arrives.

• … is attributed to the handle(s) at the head of the FIFO
• Handles don't keep track which thread was used for require.

• One thread can (require) a whole bunch of handles.
• Other threads can then use these handles to synchronize (acquire).

Each lock object also represents an abstract data object that is usually only accessible through a handle that has successfully acquired its FIFO. Major manipulations of such data are:

• scale which is similar to C::lib::realloc and can be used to extend or shrink the data. The handle must be exclusive.
• map realizes the data in memory and returns a pointer in the address space of the calling thread.
  • For an exclusive lock the pointer type is void*.
  • For an inclusive lock it is void const*.

The object is only writable when an exclusive lock is acquired.

Many algorithms that use locks perform iterations.

For locks with handles, iterative lock access can easily be managed.

• Use two handles h[0] and h[1].
• Alternate their roles from iteration to iteration.
• When h[0] acquired the lock, require the lock for h[1].
• The access to the object becomes cyclic in a guaranteed order.

We have shown that this trick provides deadlock-free and fair access.

• EILck is written in Modular C.

• EILck is best used by programming with Modular C, directly.

  Easy programming in C with access to

  • modules
  • abbreviations,
  • type genericity,
  • code unrolling

  and other neat stuff that simplifies writing portable code.

If for some reason you don't want or cannot use Modular C yourself, you can also access it through plain C and C++

• ∷ (separator) or — (composer) become _ (underscore),
  • eilck∷ehdl \(\Longrightarrow\) eilck_ehdl,
  • eilck∷ehdl∷SECTION \(\Longrightarrow\) eilck_ehdl_SECTION.

Otherwise interfaces should work as expected.

• generic interfaces are implemented by using C11's _Generic

• An additional shallow wrapper eilck++.hpp.
• It mimics EILck's module hierarchy by using namespaces.
  • eilck∷ehdl∷SECTION \(\Longrightarrow\) eilck::ehdl::SECTION
• For compatibility, type names are as for C, e.g eilck_ehdl.

• EILck only works with threads inside a single process.
• Constraining locks to threads and not sharing them between processes has performance advantages.
• There is also no way to distribute EILck automatically over several hosts.

• C11's atomic data types and operations are used for user space access to lock primitives.
• There is no attempt to use architecture specific assembly for this.
• Native compiler support for atomics as defined by C11 is mandatory.

• The OS thread manipulation libraries (POSIX or C11) are sufficient.
• No other run-time support is needed.
• Iterative programs that use pairs of handles need no supplementary scheduling unit
• Threads synchronize via their access to the EILck handles and lock objects.
  • autonomous
  • without deadlocks

• EILck is only implemented for Linux.

The main reason:

• the use of Linux' futex for efficient locking.

It should be relatively straight forward to port EILck to other architectures by emulating this interface.

• EILck handles are allocated as one of the two modes, exclusive or inclusive.
• Later they may be accessed through mode generic interfaces in the eilck∷hdl module.

• A lock object and the handles that act on it can be typed.
• The data is then qualified as an array of objects of some base type T.
• Example: eilck∷unsigned
• In that case type safe interfaces for require and map are provided.
• Other programming languages:
  • C can use the type that is declared in Modular C, here eilck_unsigned_ehdl.
  • C++ has its own template wrappers.

• The data of a lock object can be equipped with different persistence.
• Interfaces different memory models on POSIX systems, heap, file, …

Is the default persistence.

• Unless told otherwise the data for an object is realized on the heap (similar to realloc)
• The data is lost at the end of program execution.

Ensures life of the data beyond the program execution and beyond machine reboot.

• For this to work, a name for the data must be provided as a third argument to scale.
• Otherwise the data remains anonymous and can not be retrieved after the program exits.
• It is possible to start with an unnamed file object and to expose it only by assigning a name once it is in a desired state.

This persistence comes with a cost:

• file systems have much less bandwidth than primary memory.

• The access is usually faster (as fast as heap)
• The data is scrapped after a reboot of the machine at latest.

Anonymous segment lock objects are probably the most efficient ones if the application has to scale the data often.

• point to a statically allocated memory area,
• take complete control of the data object with application defined functionality
• or to use a EILck without associating data to it.

eilck∷hdl has tools for pairs of handles, to be used for iteration:

eilck∷ehdl eh[2];
eilck∷ihdl ih[2];
...
for (C∷size iter = 0; iter < 1000; ++iter) {
   // do something here
   eilck∷hdl∷SECTION2(eh) {
      double* writer = eilck∷hdl∷map2(eh);
      eilck∷hdl∷SECTION2(ih) {
         double const* reader = eilck∷hdl∷map2(ih);
         // use writer and reader
         for (C∷size i = 0; i < maxLen; ++i)
            writer[i] += reader[i];
      }
   }
   // do something there
}

For other interfaces it suffices to use the first in the pair:

eilck∷ehdl eh0[2];
eilck∷ihdl ih1[2];
eilck∷ihdl ih2[2];

eilck∷hdl∷SEQUENCE(&object, &eh0[0], &ih1[0], &ih2[0]);

These pairs of handles can then be used by different threads:

• one producer that uses eh0
• two consumers that use ih1 and ih2.

An iteration will then alternate between

• a writer phase with exclusive access through eh0, and
• a reader phase with simultaneous access by ih1 and ih2.

eilck is managed within Modular C at

source can be downloaded within the whole cmod bundle (use git)

Documentation for eilck comes as a doxygen along side with the Modular C reference implementation.

to compile the EILck library you need Modular C:

• make -j 4

from the top cmod directory should do that in most cases

• Minimal language versions are C11 (with atomics) and C++11.

If your compilers don't have that per default use, ex. GCC 5

• CC='gcc-5 -std=c11' CXX='g++-5 -std==c++11' make

for examples of C and C++ executables go to cmod/eilck/C

• cd cmod/eilck/C
• make
• eilcktest++ 500

Needed

• libeilck.a
• libeilck.so (if linking dynamically)

how to use, look into

• cmod/eilck/Makefile
• cmod/eilck/eilcktest.X

Needed

• libeilck_noinit.a
• libeilck_noinit.so (if linking dynamically)
• the *.h header files in cmod/eilck/C/

how to use, look into

• cmod/eilck/C/Makefile
• cmod/eilck/C/eilcktest.c

Needed in addition to C

• libeilck++.a
• libeilck++.so (if linking dynamically)
• the *.hpp header files in cmod/eilck/C/

how to use, look into

• cmod/eilck/C/Makefile
• cmod/eilck/C/eilcktest++.cpp