|
Tervel
1.0.0
A collection of wait-free containers and algorithms.
|
|
Tervel
1.0.0
A collection of wait-free containers and algorithms.
|
This is a non-blocking FIFO ring buffer design that was made wait-free by applying a progress assurance framework to it. More...
#include <ring_buffer.h>
Classes | |
| class | BufferOp |
| class | DequeueOp |
| class | EnqueueOp |
| class | Helper |
| class | Value |
| RingBuffer value class, values stored in the class must extend it. More... | |
Public Member Functions | |
| RingBuffer (size_t capacity) | |
| Ring Buffer constructor. More... | |
| bool | isFull () |
| Returns whether or not the ring buffer is full. More... | |
| bool | isFull (int64_t tail, int64_t head) |
| Returns whether or not the ring buffer is full. More... | |
| bool | isEmpty () |
| Returns whether or not the ring buffer is empty. More... | |
| bool | isEmpty (int64_t tail, int64_t head) |
| Returns whether or not the ring buffer is empty. More... | |
| bool | enqueue (T value) |
| Enqueues the passed value into the buffer. More... | |
| bool | dequeue (T &value) |
| Dequeues a value from the buffer. More... | |
| std::string | debug_string () |
| This function returns a string debugging information. More... | |
Private Member Functions | |
| bool | readValue (int64_t pos, uintptr_t &val) |
| This function attempts to load a value from the buffer. More... | |
| void | getInfo (uintptr_t val, int64_t &val_seqid, bool &val_isValueType, bool &val_isMarked) |
| This function is used to get information from a value read from the ring buffer. More... | |
| int64_t | nextHead () |
| performs a fetch-and-add on the head counter More... | |
| int64_t | getHead () |
| performs an atomic load on the head counter More... | |
| int64_t | casHead (int64_t &expected, int64_t new_val) |
| int64_t | nextTail () |
| performs a fetch-and-add on the tail counter More... | |
| int64_t | getTail () |
| performs an atomic load on the tail counter More... | |
| int64_t | casTail (int64_t &expected, int64_t new_val) |
| int64_t | nextSeqId (int64_t seqid) |
| Returns the next seqid. More... | |
| int64_t | getPos (int64_t seqid) |
| Returns the position a seqid belongs at. More... | |
| bool | backoff (int64_t pos, uintptr_t val) |
| A backoff routine in the event of thread delay. More... | |
| void | atomic_delay_mark (int64_t pos) |
| This function places a bitmark on the value held at address. More... | |
| std::string | debug_string (uintptr_t val) |
| This prints out debugging information. More... | |
Static Private Member Functions | |
| static uintptr_t | EmptyType (int64_t seqid) |
| Creates a uintptr_t that represents an EmptyType. More... | |
| static int64_t | getEmptyTypeSeqId (uintptr_t val) |
| Returns the seqid encoded in the passed value. More... | |
| static uintptr_t | ValueType (T value, int64_t seqid) |
| Creates a uintptr_t that represents an ValueType. More... | |
| static T | getValueType (uintptr_t val) |
| Returns the value type from a uintptr. More... | |
| static int64_t | getValueTypeSeqId (uintptr_t val) |
| Returns the seqid of the passed value. More... | |
| static uintptr_t | DelayMarkValue (uintptr_t val) |
| Takes a uintptr_t and places a bitmark on the delayMark_lsb. More... | |
| static bool | isEmptyType (uintptr_t p) |
| returns whether or not p represents an EmptyType More... | |
| static bool | isValueType (uintptr_t p) |
| returns whether or not p represents an ValueType More... | |
| static bool | isDelayedMarked (uintptr_t p) |
| returns whether or not p has a delay mark More... | |
| static int64_t | counterAction (std::atomic< int64_t > &counter, int64_t val) |
| utility function for incrementing counter More... | |
Private Attributes | |
| const int64_t | capacity_ |
| std::atomic< int64_t > | head_ {0} |
| std::atomic< int64_t > | tail_ {0} |
| std::unique_ptr< std::atomic< uintptr_t >[]> | array_ |
Static Private Attributes | |
| static const uintptr_t | num_lsb = 3 |
| static const uintptr_t | delayMark_lsb = 0x1 |
| static const uintptr_t | emptytype_lsb = 0x2 |
| static const uintptr_t | oprec_lsb = 0x4 |
| static const uintptr_t | clear_lsb = 7 |
This is a non-blocking FIFO ring buffer design that was made wait-free by applying a progress assurance framework to it.
If isDelayed never returns true then it will not use additional memory. However, if it does, then it will allocate some objects which are protected by hazard pointer protection.
This ring buffer is implemented on a statically sized array. It can only store pointer sized objects that extend the Value class. Further it reserves the 3 LSB for type identification, which makes it compatible only with 64 bit systems
It supports enqueue, dequeue, isFull, and isEmpty operations
| T | The type of information stored, must be a pointer and the class must extend RingBuffer::Value. |
| tervel::containers::wf::RingBuffer< T >::RingBuffer | ( | size_t | capacity | ) |
Ring Buffer constructor.
This constructs and initializes the ring buffer object
| capacity | the length of the internal array to allocate. |
|
private |
This function places a bitmark on the value held at address.
This function places a bitmark on the value held at address by calling address->fetch_or(delayMark_lsb) and then it loads the new current value and assigns it to val.
| pos | The position to perform the blind bitmark. |
|
private |
A backoff routine in the event of thread delay.
This function is called in the event the value at position on the ringbuffer is lagging behind as a result of a delayed thread.
It calls tervel::util::backoff() and upon its return checks whether or the value at address has changed. If it has, it returns true, Else it returns false. If the value has changed the new value is assigned to val
| pos | The pos val was read from |
| val | The last read value from address. |
|
private |
|
private |
|
inlinestaticprivate |
utility function for incrementing counter
contains internal checks on the returned value
| counter | counter to increment |
| val | value by which to increment the counter |
| std::string tervel::containers::wf::RingBuffer< T >::debug_string | ( | ) |
This function returns a string debugging information.
This information includes Value at each potion, head, tail, capacity, and someother stuff.
|
private |
This prints out debugging information.
This prints out debugging information.
| val | a value loaded from a position on the buffer |
|
inlinestaticprivate |
Takes a uintptr_t and places a bitmark on the delayMark_lsb.
Takes a uintptr_t and places a bitmark on the delayMark_lsb
| val | The value to mark |
| bool tervel::containers::wf::RingBuffer< T >::dequeue | ( | T & | value | ) |
Dequeues a value from the buffer.
This function attempts to dequeue a value. It returns false in the event the ring buffer is empty.
| value | A variable to store the dequeued value. |
|
inlinestaticprivate |
Creates a uintptr_t that represents an EmptyType.
the uintptr_t is composed by seqid << num_lsb | emptytype_lsb
| seqid | the seqid for this EmptyType |
| bool tervel::containers::wf::RingBuffer< T >::enqueue | ( | T | value | ) |
Enqueues the passed value into the buffer.
This function attempts to enqueue the passed value. It returns false in the event the ring buffer is full. Internally it assigned a sequence number to the value.
| value | The value to enqueue. |
|
inlinestaticprivate |
Returns the seqid encoded in the passed value.
Returns the seqid encoded in the passed value
seqid = val >> num_lsb
| val | a unitptr_t loaded from the buffer |
|
private |
performs an atomic load on the head counter
performs an atomic load on the head counter
|
private |
This function is used to get information from a value read from the ring buffer.
This function is used to get information from a value read from the ring buffer. This information is then assigned to the arguments.
| val | a value read from a position on the ring buffer |
| val_seqid | The seqid associated with val |
| val_isValueType | Whether or not val is a ValueType |
| val_isMarked | Whether or not val has a delay mark. |
|
private |
Returns the position a seqid belongs at.
Returns the position a seqid belongs at, determined by seqid % capacity_
| seqid | the seqid |
|
private |
performs an atomic load on the tail counter
performs an atomic load on the tail counter
|
inlinestaticprivate |
Returns the value type from a uintptr.
clears any delayed marks then casts it to type T.
| val | The value to cast |
|
inlinestaticprivate |
Returns the seqid of the passed value.
Returns the seqid of the passed value, first it casts val to type T by calling getValyeType then it calls val->func_seqid();
| val | a value read from the ring buffer that has been determined to be a ValueType |
|
inlinestaticprivate |
returns whether or not p has a delay mark
returns whether or not p has a delay mark by examining the delayMark_lsb. If it is 1 then it is delayed
| p | the value to examine |
| bool tervel::containers::wf::RingBuffer< T >::isEmpty | ( | ) |
Returns whether or not the ring buffer is empty.
Returns whether or not the ring buffer is empty.
| bool tervel::containers::wf::RingBuffer< T >::isEmpty | ( | int64_t | tail, |
| int64_t | head | ||
| ) |
Returns whether or not the ring buffer is empty.
Returns whether or not the ring buffer is empty.
| tail | |
| head |
|
inlinestaticprivate |
returns whether or not p represents an EmptyType
returns whether or not p represents an EmptyType by examining the emptytype_lsb. If it is 1 then it is an EmptyType type.
| p | the value to examine |
| bool tervel::containers::wf::RingBuffer< T >::isFull | ( | ) |
Returns whether or not the ring buffer is full.
Returns whether or not the ring buffer is full.
| bool tervel::containers::wf::RingBuffer< T >::isFull | ( | int64_t | tail, |
| int64_t | head | ||
| ) |
Returns whether or not the ring buffer is full.
Returns whether or not the ring buffer is full.
| tail | [description] |
| head | [description] |
|
inlinestaticprivate |
returns whether or not p represents an ValueType
returns whether or not p represents an ValueType by examining the emptytype_lsb. If it is 0 then it is an ValueType type.
| p | the value to examine |
|
private |
performs a fetch-and-add on the head counter
atomically increments the head
|
private |
Returns the next seqid.
Returns the next seqid, which is seqid+capacity_
| seqid | The current seqid |
|
private |
performs a fetch-and-add on the tail counter
atomically increments the tail
|
private |
This function attempts to load a value from the buffer.
This function encapsulates logic related to achieving hazard pointer protection on objects read from the buffer. Currently it does not protected type T objects, only Helper objects used in the progress assurance framework. If a Helper object is read it will return false, otherwise it will return a successful read.
| pos | the position to load from |
| val | the variable to store the loaded value. |
|
inlinestaticprivate |
Creates a uintptr_t that represents an ValueType.
the uintptr_t is composed by casting value to a uintptr_t.
Internally it calls value->func_seqid(seqid) to set the seqid.
| value | a pointer type to enqueue |
| seqid | the sequence id assigned to this value |
|
private |
|
private |
|
staticprivate |
|
staticprivate |
|
staticprivate |
|
private |
|
staticprivate |
|
staticprivate |
|
private |
1.8.9.1
