.. default-domain:: chpl

.. module:: LockFreeQueue
   :synopsis: A lock-free queue using the Michael and Scott algorithm.

LockFreeQueue
=============
**Usage**

.. code-block:: chapel

   use LockFreeQueue;


or

.. code-block:: chapel

   import LockFreeQueue;

A lock-free queue using the Michael and Scott algorithm.

.. warning::

  This module relies on the :mod:`AtomicObjects` package module, which
  has several platform restrictions in its current state:

    - It relies on Chapel ``extern`` code blocks and so requires that
      the Chapel compiler is built with LLVM enabled.
    - Currently only ``CHPL_TARGET_ARCH=x86_64`` is supported as it uses
      the x86-64 instruction: CMPXCHG16B_.
    - The implementation relies on ``GCC`` style inline assembly, and so
      is restricted to a ``CHPL_TARGET_COMPILER`` value of ``gnu``,
      ``clang``, or ``llvm``.

  .. _CMPXCHG16B: https://www.felixcloutier.com/x86/cmpxchg8b:cmpxchg16b

An implementation of the Michael & Scott [#]_, a lock-free queue. Concurrent safe
memory reclamation is handled by an internal :record:`EpochManager`. Usage of the
queue can be seen below.

.. code-block:: chpl

  var lfq = new LockFreeQueue(int);
  forall i in 1..N do lfq.enqueue(i);
  var total : int;
  coforall tid in 1..here.maxTaskPar with (+ reduce total) {
    var (hasElt, elt) = lfq.dequeue();
    while hasElt {
      total += elt;
      (hasElt, elt) = lfq.dequeue();
    }
  }

As an optimization, the user can register to receive a :class:`~EpochManager.TokenWrapper`, and pass this
to the stack. This can provide significant improvement in performance by up to an order of magnitude
by avoiding the overhead of registering and unregistering for each operation.

.. code-block:: chpl

  var lfq = new LockFreeQueue(int);
  forall i in 1..N with (var tok = lfq.getToken()) do lfq.enqueue(i,tok);
  var total : int;
  coforall tid in 1..here.maxTaskPar with (+ reduce total) {
    var tok = lfq.getToken();
    var (hasElt, elt) = lfq.dequeue(tok);
    while hasElt {
      total += elt;
      (hasElt, elt) = lfq.dequeue(tok);
    }
  }

Lastly, to safely reclaim memory, the user must explicitly invoke ``tryReclaim``, or else
there will be a memory leak. This must be explicitly invoked so that the user may tune how often
reclamation will be attempted. Reclamation is concurrent-safe, but if called too frequently,
it can add unnecessary overhead. A complete example of what would be considered 'optimal'
usage of this lock-free stack.

.. code-block:: chpl

  var lfq = new LockFreeQueue(int);
  forall i in 1..N with (var tok = lfq.getToken()) do lfq.push(i,tok);
  var total : int;
  coforall tid in 1..here.maxTaskPar with (+ reduce total) {
    var tok = lfq.getToken();
    var (hasElt, elt) = lfq.dequeue(tok);
    var n : int;
    while hasElt {
      total += elt;
      (hasElt, elt) = lfq.dequeue(tok);
      n += 1;
      if n % GC_THRESHOLD == 0 then lfq.tryReclaim();
    }
  }

Also provided, is a utility method for draining the stack of all elements,
called ``drain``. This iterator will implicitly call ``tryReclaim`` at the
end and will optimally create one token per task.

.. code-block:: chpl

  var lfq = new LockFreeQueue(int);
  forall i in 1..N with (var tok = lfq.getToken()) do lfq.enqueue(i,tok);
  var total = + reduce lfq.drain();

.. [#] Michael, Maged M., and Michael L. Scott.
    Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms.
    No. TR-600. ROCHESTER UNIV NY DEPT OF COMPUTER SCIENCE, 1995.

.. class:: Node

   .. attribute:: type eltType

   .. attribute:: var val: toNilableIfClassType(eltType)

   .. attribute:: var next: AtomicObject(unmanaged Node(eltType)?, hasGlobalSupport = true, hasABASupport = false)

   .. method:: proc init(val: ?eltType)

   .. method:: proc init(type eltType)

.. class:: LockFreeQueue

   .. attribute:: type objType

   .. attribute:: var _head: AtomicObject(unmanaged Node(objType), hasGlobalSupport = true, hasABASupport = false)

   .. attribute:: var _tail: AtomicObject(unmanaged Node(objType), hasGlobalSupport = true, hasABASupport = false)

   .. attribute:: var _manager = new owned LocalEpochManager()

   .. method:: proc objTypeOpt type

   .. method:: proc init(type objType)

   .. method:: proc getToken(): owned TokenWrapper

   .. method:: proc enqueue(newObj: objType, tok: owned TokenWrapper = getToken())

   .. method:: proc dequeue(tok: owned TokenWrapper = getToken()): (bool, objTypeOpt)

   .. itermethod:: iter drain(): objTypeOpt

   .. itermethod:: iter drain(param tag: iterKind): objTypeOpt where tag == iterKind.standalone

   .. method:: proc tryReclaim()