folly::LockFreeRingBuffer< T, Atom > Class Template Reference

#include <LockFreeRingBuffer.h>

Inheritance diagram for folly::LockFreeRingBuffer< T, Atom >:

Classes
struct	Cursor

Public Member Functions
	LockFreeRingBuffer (uint32_t capacity) noexcept
void	write (T &value) noexcept
Cursor	writeAndGetCursor (T &value) noexcept
bool	tryRead (T &dest, const Cursor &cursor) noexcept
bool	waitAndTryRead (T &dest, const Cursor &cursor) noexcept
Cursor	currentHead () noexcept
	Returns a Cursor pointing to the first write that has not occurred yet. More...
Cursor	currentTail (double skipFraction=0.0) noexcept
	~LockFreeRingBuffer ()

Private Member Functions
uint32_t	idx (uint64_t ticket) noexcept
uint32_t	turn (uint64_t ticket) noexcept

Private Attributes
const uint32_t	capacity_
const std::unique_ptr< detail::RingBufferSlot< T, Atom >[]>	slots_
Atom< uint64_t >	ticket_

Detailed Description

template<typename T, template< typename > class Atom = std::atomic>
class folly::LockFreeRingBuffer< T, Atom >

LockFreeRingBuffer<T> is a fixed-size, concurrent ring buffer with the following semantics:

1. Writers cannot block on other writers UNLESS they are <capacity> writes apart from each other (writing to the same slot after a wrap-around)
2. Writers cannot block on readers
3. Readers can wait for writes that haven't occurred yet
4. Readers can detect if they are lagging behind

In this sense, reads from this buffer are best-effort but writes are guaranteed.

Another way to think about this is as an unbounded stream of writes. The buffer contains the last <capacity> writes but readers can attempt to read any part of the stream, even outside this window. The read API takes a Cursor that can point anywhere in this stream of writes. Reads from the "future" can optionally block but reads from the "past" will always fail.

Definition at line 59 of file LockFreeRingBuffer.h.

Constructor & Destructor Documentation

template<typename T, template< typename > class Atom = std::atomic>

folly::LockFreeRingBuffer< T, Atom >::LockFreeRingBuffer ( uint32_t  capacity )

inlineexplicitnoexcept

Definition at line 99 of file LockFreeRingBuffer.h.

      : capacity_(capacity),
        slots_(new detail::RingBufferSlot<T, Atom>[capacity]),
        ticket_(0) {}

template<typename T, template< typename > class Atom = std::atomic>

folly::LockFreeRingBuffer< T, Atom >::~LockFreeRingBuffer ( )

inline

Definition at line 162 of file LockFreeRingBuffer.h.

{}

Member Function Documentation

template<typename T, template< typename > class Atom = std::atomic>

Cursor folly::LockFreeRingBuffer< T, Atom >::currentHead ( )

inlinenoexcept

Returns a Cursor pointing to the first write that has not occurred yet.

Definition at line 139 of file LockFreeRingBuffer.h.

Referenced by folly::runWritesNeverFail(), and folly::TEST().

                                {
    return Cursor(ticket_.load());
  }

template<typename T, template< typename > class Atom = std::atomic>

Cursor folly::LockFreeRingBuffer< T, Atom >::currentTail ( double  skipFraction = 0.0 )

inlinenoexcept

Returns a Cursor pointing to a currently readable write. skipFraction is a value in the [0, 1] range indicating how far into the currently readable window to place the cursor. 0 means the earliest readable write, 1 means the latest readable write (if any).

Definition at line 147 of file LockFreeRingBuffer.h.

References min, ticket, and uint64_t.

Referenced by folly::TEST().

                                                         {
    assert(skipFraction >= 0.0 && skipFraction <= 1.0);
    uint64_t ticket = ticket_.load();

    uint64_t backStep = llround((1.0 - skipFraction) * capacity_);

    // always try to move at least one step backward to something readable
    backStep = std::max<uint64_t>(1, backStep);

    // can't go back more steps than we've taken
    backStep = std::min(ticket, backStep);

    return Cursor(ticket - backStep);
  }

template<typename T, template< typename > class Atom = std::atomic>

uint32_t folly::LockFreeRingBuffer< T, Atom >::idx ( uint64_t  ticket )

inlineprivatenoexcept

Definition at line 171 of file LockFreeRingBuffer.h.

References ticket.

                                         {
    return ticket % capacity_;
  }

template<typename T, template< typename > class Atom = std::atomic>

bool folly::LockFreeRingBuffer< T, Atom >::tryRead ( T &  dest, const Cursor &  cursor  )

inlinenoexcept

Read the value at the cursor. Returns true if the read succeeded, false otherwise. If the return value is false, dest is to be considered partially read and in an inconsistent state. Readers are advised to discard it.

Definition at line 126 of file LockFreeRingBuffer.h.

References upload::dest.

Referenced by folly::TEST().

                                                       {
    return slots_[idx(cursor.ticket)].tryRead(dest, turn(cursor.ticket));
  }

template<typename T, template< typename > class Atom = std::atomic>

uint32_t folly::LockFreeRingBuffer< T, Atom >::turn ( uint64_t  ticket )

inlineprivatenoexcept

Definition at line 175 of file LockFreeRingBuffer.h.

References Atom, ticket, and uint32_t.

                                          {
    return (uint32_t)(ticket / capacity_);
  }

template<typename T, template< typename > class Atom = std::atomic>

bool folly::LockFreeRingBuffer< T, Atom >::waitAndTryRead ( T &  dest, const Cursor &  cursor  )

inlinenoexcept

Read the value at the cursor or block if the write has not occurred yet. Returns true if the read succeeded, false otherwise. If the return value is false, dest is to be considered partially read and in an inconsistent state. Readers are advised to discard it.

Definition at line 134 of file LockFreeRingBuffer.h.

References upload::dest.

Referenced by folly::TEST().

                                                              {
    return slots_[idx(cursor.ticket)].waitAndTryRead(dest, turn(cursor.ticket));
  }

template<typename T, template< typename > class Atom = std::atomic>

void folly::LockFreeRingBuffer< T, Atom >::write ( T &  value )

inlinenoexcept

Perform a single write of an object of type T. Writes can block iff a previous writer has not yet completed a write for the same slot (before the most recent wrap-around).

Definition at line 107 of file LockFreeRingBuffer.h.

References ticket, uint64_t, and folly::value().

Referenced by folly::runReader(), and folly::TEST().

                                {
    uint64_t ticket = ticket_.fetch_add(1);
    slots_[idx(ticket)].write(turn(ticket), value);
  }

template<typename T, template< typename > class Atom = std::atomic>

Cursor folly::LockFreeRingBuffer< T, Atom >::writeAndGetCursor ( T &  value )

inlinenoexcept

Perform a single write of an object of type T. Writes can block iff a previous writer has not yet completed a write for the same slot (before the most recent wrap-around). Returns a Cursor pointing to the just-written T.

Definition at line 116 of file LockFreeRingBuffer.h.

References ticket, uint64_t, and folly::value().

Referenced by folly::TEST().

                                              {
    uint64_t ticket = ticket_.fetch_add(1);
    slots_[idx(ticket)].write(turn(ticket), value);
    return Cursor(ticket);
  }

Member Data Documentation

template<typename T, template< typename > class Atom = std::atomic>

const uint32_t folly::LockFreeRingBuffer< T, Atom >::capacity_

private

Definition at line 165 of file LockFreeRingBuffer.h.

template<typename T, template< typename > class Atom = std::atomic>

const std::unique_ptr<detail::RingBufferSlot<T, Atom>[]> folly::LockFreeRingBuffer< T, Atom >::slots_

private

Definition at line 167 of file LockFreeRingBuffer.h.

template<typename T, template< typename > class Atom = std::atomic>

Atom<uint64_t> folly::LockFreeRingBuffer< T, Atom >::ticket_

private

Definition at line 169 of file LockFreeRingBuffer.h.

---

The documentation for this class was generated from the following file:

• proxygen/folly/folly/experimental/LockFreeRingBuffer.h