Guards and locks
================

Apart from ``spawn`` and ``parallel`` Nim also provides all the common low level
concurrency mechanisms like locks, atomic intristics or condition variables.

Nim significantly improves on the safety of these features via additional
pragmas:

1) A `guard`:idx: annotation is introduced to prevent data races.
2) Every access of a guarded memory location needs to happen in an
   appropriate `locks`:idx: statement.
3) Locks and routines can be annotated with `lock levels`:idx: to prevent
   deadlocks at compile time.


Guards and the locks section
----------------------------

Protecting global variables
~~~~~~~~~~~~~~~~~~~~~~~~~~~

Object fields and global variables can be annotated via a ``guard`` pragma:

.. code-block:: nim
  var glock: TLock
  var gdata {.guard: glock.}: int

The compiler then ensures that every access of ``gdata`` is within a ``locks``
section:

.. code-block:: nim
  proc invalid =
    # invalid: unguarded access:
    echo gdata

  proc valid =
    # valid access:
    {.locks: [glock].}:
      echo gdata

Top level accesses to ``gdata`` are always allowed so that it can be initialized
conveniently. It is *assumed* (but not enforced) that every top level statement
is executed before any concurrent action happens.

The ``locks`` section deliberately looks ugly because it has no runtime
semantics and should not be used directly! It should only be used in templates
that also implement some form of locking at runtime:

.. code-block:: nim
  template lock(a: TLock; body: untyped) =
    pthread_mutex_lock(a)
    {.locks: [a].}:
      try:
        body
      finally:
        pthread_mutex_unlock(a)


The guard does not need to be of any particular type. It is flexible enough to
model low level lockfree mechanisms:

.. code-block:: nim
  var dummyLock {.compileTime.}: int
  var atomicCounter {.guard: dummyLock.}: int

  template atomicRead(x): untyped =
    {.locks: [dummyLock].}:
      memoryReadBarrier()
      x

  echo atomicRead(atomicCounter)


The ``locks`` pragma takes a list of lock expressions ``locks: [a, b, ...]``
in order to support *multi lock* statements. Why these are essential is
explained in the `lock levels`_ section.


Protecting general locations
~~~~~~~~~~~~~~~~~~~~~~~~~~~~

The ``guard`` annotation can also be used to protect fields within an object.
The guard then needs to be another field within the same object or a
global variable.

Since objects can reside on the heap or on the stack this greatly enhances the
expressivity of the language:

.. code-block:: nim
  type
    ProtectedCounter = object
      v {.guard: L.}: int
      L: TLock

  proc incCounters(counters: var openArray[ProtectedCounter]) =
    for i in 0..counters.high:
      lock counters[i].L:
        inc counters[i].v

The access to field ``x.v`` is allowed since its guard ``x.L``  is active.
After template expansion, this amounts to:

.. code-block:: nim
  proc incCounters(counters: var openArray[ProtectedCounter]) =
    for i in 0..counters.high:
      pthread_mutex_lock(counters[i].L)
      {.locks: [counters[i].L].}:
        try:
          inc counters[i].v
        finally:
          pthread_mutex_unlock(counters[i].L)

There is an analysis that checks that ``counters[i].L`` is the lock that
corresponds to the protected location ``counters[i].v``. This analysis is called
`path analysis`:idx: because it deals with paths to locations
like ``obj.field[i].fieldB[j]``.

The path analysis is **currently unsound**, but that doesn't make it useless.
Two paths are considered equivalent if they are syntactically the same.

This means the following compiles (for now) even though it really should not:

.. code-block:: nim
  {.locks: [a[i].L].}:
    inc i
    access a[i].v



Lock levels
-----------

Lock levels are used to enforce a global locking order in order to prevent
deadlocks at compile-time. A lock level is an constant integer in the range
0..1_000. Lock level 0 means that no lock is acquired at all.

If a section of code holds a lock of level ``M`` than it can also acquire any
lock of level ``N < M``. Another lock of level ``M`` cannot be acquired. Locks
of the same level can only be acquired *at the same time* within a
single ``locks`` section:

.. code-block:: nim
  var a, b: TLock[2]
  var x: TLock[1]
  # invalid locking order: TLock[1] cannot be acquired before TLock[2]:
  {.locks: [x].}:
    {.locks: [a].}:
      ...
  # valid locking order: TLock[2] acquired before TLock[1]:
  {.locks: [a].}:
    {.locks: [x].}:
      ...

  # invalid locking order: TLock[2] acquired before TLock[2]:
  {.locks: [a].}:
    {.locks: [b].}:
      ...

  # valid locking order, locks of the same level acquired at the same time:
  {.locks: [a, b].}:
    ...


Here is how a typical multilock statement can be implemented in Nim. Note how
the runtime check is required to ensure a global ordering for two locks ``a``
and ``b`` of the same lock level:

.. code-block:: nim
  template multilock(a, b: ptr TLock; body: untyped) =
    if cast[ByteAddress](a) < cast[ByteAddress](b):
      pthread_mutex_lock(a)
      pthread_mutex_lock(b)
    else:
      pthread_mutex_lock(b)
      pthread_mutex_lock(a)
    {.locks: [a, b].}:
      try:
        body
      finally:
        pthread_mutex_unlock(a)
        pthread_mutex_unlock(b)


Whole routines can also be annotated with a ``locks`` pragma that takes a lock
level. This then means that the routine may acquire locks of up to this level.
This is essential so that procs can be called within a ``locks`` section:

.. code-block:: nim
  proc p() {.locks: 3.} = discard

  var a: TLock[4]
  {.locks: [a].}:
    # p's locklevel (3) is strictly less than a's (4) so the call is allowed:
    p()


As usual ``locks`` is an inferred effect and there is a subtype
relation: ``proc () {.locks: N.}`` is a subtype of ``proc () {.locks: M.}``
iff (M <= N).