EILck: Exclusive–Inclusive Linear Locks

Table of Contents

Jens Gustedt

1 Introduction

1.1 Overview

1.1.1 What

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

This is a standalone implementation of a concept called

  • ordered read-write locks (ORWL)

that had been introduced in

1.1.2 Why (example)

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);
}

1.1.3 Why (semantic)

  1. Program semantic:
    • readerLock \(\Longleftrightarrow\) readerVector is implicit
    • syntax does not reflect logic
  2. Algorithm semantic:
    • no control for order of access
    • missing numerical guarantees

1.1.4 Why (execution)

  1. Runtime behavior:
    • risk of deadlocks
    • risk of starvation or unfairness
  2. Efficiency:

    maybe there are several readers

1.1.5 How

  • 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.

1.2 Ordered read-write locks

1.2.1 Lock objects

  • 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.

1.2.2 Lock events

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.

1.2.3 Lock mode

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.

1.2.4 Lock acquisition

  • … 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).

1.2.5 Lock data

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.

1.2.6 Lock iteration

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.

2 Specificities of EILck

2.1 Programming language(s)

2.1.1 Modular C

  • 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++

2.1.2 C (minimal version C11)

  • (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

2.1.3 C++ (minimal version C++11)

  • 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.

2.2 System

2.2.1 Threads

  • 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.

2.2.2 Atomics

  • 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.

2.2.3 Runtime

  • 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

2.2.4 Linux

  • EILck is only implemented for Linux.

The main reason:

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

2.3 Genericity

2.3.1 mode genericity

  • 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.
  1. SEQUENCE

    … can be used to place a bunch of require operations:

    eilck∷hdl∷SEQUENCE(&object, &h0, &h1, &h2);
    

    Inserts the three handles h0, h1, h2 in the given order into the FIFO of object, regardless whether they are eilck∷ehdl or eilck∷ihdl.

    Nevertheless, in most of the cases h0 will be exclusive: we first have to write contents to the data before we can use it.

  2. SECTION

    … condenses acquire and release operations into one convenience macro that marks a critical section:

    eilck∷hdl∷SECTION(&h0) {
      // do something with handle h0
    }
    

    This acquires h0 before entering in the dependent block and releases it aftewards.

  3. map

    … maps its handle argument, regardless if it is an exclusive or inclusive handle:

    eilck∷ehdl eh;
    eilck∷ihdl ih;
    ...
    eilck∷hdl∷SECTION(&eh) {
       double* writer = eilck∷hdl∷map(&eh);
       eilck∷hdl∷SECTION(&ih) {
          double const* reader = eilck∷hdl∷map(&ih);
          // use writer and reader
          writer[0] += reader[0];
       }
    }
    

    Here, the target pointer for reader must be const qualified, otherwise this produces a compiler error.

2.3.2 Type genericity

  • 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.

2.4 Data persistence

2.4.1 Persistence models

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

2.4.2 heap

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.

2.4.3 file

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.

2.4.4 segment

  • 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.

2.4.5 fixed

  • 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.

2.5 Iteration

2.5.1 SECTION2 and map2

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
}

2.5.2 queue insertions

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.

3 More

3.1 how to get it

3.1.1 documentation and download

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 processed web site within the documentation of our Modular C reference implementation.

3.1.2 Install

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

3.1.3 Test

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

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

3.2 how to use it

3.2.1 Modular C

Needed

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

how to use, look into

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

3.2.2 C

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

3.2.3 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

Author: Jens Gustedt

Created: 2017-10-14 Sa 10:41

Validate