An MCS reader-writer lock data structure. More...

Detailed Description

An MCS reader-writer lock data structure.

This implements a fair reader-writer lock by the original authors of MCS lock [PPoPP 1991]. The version implemented here includes a bug fix due to Keir Fraser (University of Cambridge). See https://www.cs.rochester.edu/research/synchronization/pseudocode/rw.html#s_f for the original pseudocode with the fix.

The major use case so far is row-level locking for 2PL.

The assumption is that a thread at any instant can be waiting for only one MCS lock, so knowing the thread ID suffices to locate the block index as well.

TODO(tzwang): add the ownerless variant.

Definition at line 795 of file xct_id.hpp.

#include <xct_id.hpp>

Public Member Functions
	McsRwLock ()

	McsRwLock (const McsRwLock &other)=delete

McsRwLock &	operator= (const McsRwLock &other)=delete

void	reset ()

void	increment_nreaders ()

uint16_t	decrement_nreaders ()

uint16_t	nreaders ()

McsBlockIndex	get_tail_waiter_block () const

thread::ThreadId	get_tail_waiter () const

bool	has_next_writer () const

void	set_next_writer (thread::ThreadId thread_id)

thread::ThreadId	get_next_writer ()

thread::ThreadId	xchg_next_writer (thread::ThreadId id)

bool	cas_next_writer_weak (thread::ThreadId expected, thread::ThreadId desired)

bool	cas_next_writer_strong (thread::ThreadId expected, thread::ThreadId desired)

uint32_t	xchg_tail (uint32_t new_tail)

bool	cas_tail_strong (uint32_t expected, uint32_t desired)

bool	cas_tail_weak (uint32_t expected, uint32_t desired)

uint32_t	get_tail_int ()

bool	is_locked () const

Static Public Member Functions
static uint32_t	to_tail_int (thread::ThreadId tail_waiter, McsBlockIndex tail_waiter_block)

Public Attributes
uint32_t	tail_

thread::ThreadId	next_writer_

uint16_t	nreaders_

Static Public Attributes
static const thread::ThreadId	kNextWriterNone = 0xFFFFU

Friends
std::ostream &	operator<< (std::ostream &o, const McsRwLock &v)

Constructor & Destructor Documentation

foedus::xct::McsRwLock::McsRwLock ( )

inline

Definition at line 798 of file xct_id.hpp.

References reset().

798 { reset(); }

foedus::xct::McsRwLock::reset

void reset()

Definition: xct_id.hpp:803

Here is the call graph for this function:

foedus::xct::McsRwLock::McsRwLock ( const McsRwLock & other )

delete

Member Function Documentation

bool foedus::xct::McsRwLock::cas_next_writer_strong	(	thread::ThreadId	expected,
		thread::ThreadId	desired
	)

inline

Definition at line 835 of file xct_id.hpp.

References next_writer_.

                                                                                {
     return assorted::raw_atomic_compare_exchange_strong<thread::ThreadId>(
       &next_writer_, &expected, desired);
   }

bool foedus::xct::McsRwLock::cas_next_writer_weak	(	thread::ThreadId	expected,
		thread::ThreadId	desired
	)

inline

Definition at line 831 of file xct_id.hpp.

References next_writer_.

                                                                              {
     return assorted::raw_atomic_compare_exchange_weak<thread::ThreadId>(
       &next_writer_, &expected, desired);
   }

bool foedus::xct::McsRwLock::cas_tail_strong	(	uint32_t	expected,
		uint32_t	desired
	)

inline

Definition at line 842 of file xct_id.hpp.

References tail_.

                                                                    {
     return assorted::raw_atomic_compare_exchange_strong<uint32_t>(&tail_, &expected, desired);
   }

bool foedus::xct::McsRwLock::cas_tail_weak	(	uint32_t	expected,
		uint32_t	desired
	)

inline

Definition at line 845 of file xct_id.hpp.

References tail_.

                                                                  {
     return assorted::raw_atomic_compare_exchange_weak<uint32_t>(&tail_, &expected, desired);
   }

uint16_t foedus::xct::McsRwLock::decrement_nreaders ( )

inline

Definition at line 811 of file xct_id.hpp.

References nreaders_.

Referenced by foedus::xct::McsImpl< ADAPTOR, McsRwSimpleBlock >::release_rw_reader().

                                        {
     return assorted::raw_atomic_fetch_add<uint16_t>(&nreaders_, -1);
   }

Here is the caller graph for this function:

thread::ThreadId foedus::xct::McsRwLock::get_next_writer ( )

inline

Definition at line 825 of file xct_id.hpp.

References next_writer_.

Referenced by foedus::xct::McsImpl< ADAPTOR, McsRwSimpleBlock >::acquire_unconditional_rw_writer().

                                           {
     return assorted::atomic_load_acquire<thread::ThreadId>(&next_writer_);
   }

Here is the caller graph for this function:

uint32_t foedus::xct::McsRwLock::get_tail_int ( )

inline

Definition at line 854 of file xct_id.hpp.

References tail_.

                                  {
     return assorted::atomic_load_acquire<uint32_t>(&tail_);
   }

thread::ThreadId foedus::xct::McsRwLock::get_tail_waiter ( ) const

inline

Definition at line 818 of file xct_id.hpp.

References tail_.

Referenced by foedus::xct::McsMockAdaptor< RW_BLOCK >::dereference_rw_tail_block(), foedus::thread::ThreadPimplMcsAdaptor< RW_BLOCK >::dereference_rw_tail_block(), foedus::xct::operator<<(), and foedus::storage::array::ArrayStoragePimpl::verify_single_thread().

818 { return tail_ >> 16U; }

foedus::xct::McsRwLock::tail_

uint32_t tail_

Definition: xct_id.hpp:861

Here is the caller graph for this function:

McsBlockIndex foedus::xct::McsRwLock::get_tail_waiter_block ( ) const

inline

Definition at line 817 of file xct_id.hpp.

References tail_.

Referenced by foedus::xct::McsMockAdaptor< RW_BLOCK >::dereference_rw_tail_block(), foedus::thread::ThreadPimplMcsAdaptor< RW_BLOCK >::dereference_rw_tail_block(), foedus::xct::operator<<(), and foedus::storage::array::ArrayStoragePimpl::verify_single_thread().

817 { return tail_ & 0xFFFFU; }

foedus::xct::McsRwLock::tail_

uint32_t tail_

Definition: xct_id.hpp:861

Here is the caller graph for this function:

bool foedus::xct::McsRwLock::has_next_writer ( ) const

inline

Definition at line 819 of file xct_id.hpp.

References next_writer_.

                                       {
     return assorted::atomic_load_acquire<thread::ThreadId>(&next_writer_) != kNextWriterNone;
   }

void foedus::xct::McsRwLock::increment_nreaders ( )

inline

Definition at line 808 of file xct_id.hpp.

References nreaders_.

Referenced by foedus::xct::McsImpl< ADAPTOR, McsRwSimpleBlock >::acquire_unconditional_rw_reader(), foedus::xct::McsImpl< ADAPTOR, McsRwSimpleBlock >::release_rw_writer(), and foedus::xct::McsImpl< ADAPTOR, McsRwSimpleBlock >::retry_async_rw_reader().

                                    {
     assorted::raw_atomic_fetch_add<uint16_t>(&nreaders_, 1);
   }

Here is the caller graph for this function:

bool foedus::xct::McsRwLock::is_locked ( ) const

inline

Definition at line 857 of file xct_id.hpp.

References nreaders_, and tail_.

Referenced by foedus::xct::RwLockableXctId::is_keylocked(), foedus::xct::operator<<(), and foedus::storage::masstree::MasstreeStoragePimpl::verify_single_thread_border().

                          {
     return (tail_ & 0xFFFFU) != 0 || nreaders_ > 0;
   }

Here is the caller graph for this function:

uint16_t foedus::xct::McsRwLock::nreaders ( )

inline

Definition at line 814 of file xct_id.hpp.

References nreaders_.

Referenced by foedus::xct::McsImpl< ADAPTOR, McsRwSimpleBlock >::acquire_unconditional_rw_writer(), and foedus::xct::McsImpl< ADAPTOR, McsRwSimpleBlock >::release_rw_reader().

                              {
     return assorted::atomic_load_acquire<uint16_t>(&nreaders_);
   }

Here is the caller graph for this function:

McsRwLock& foedus::xct::McsRwLock::operator= ( const McsRwLock & other )

delete

void foedus::xct::McsRwLock::reset ( )

inline

Definition at line 803 of file xct_id.hpp.

References foedus::assorted::memory_fence_release(), nreaders_, set_next_writer(), and tail_.

Referenced by foedus::storage::sequential::SequentialPage::append_record_nosync(), foedus::storage::masstree::MasstreeBorderPage::initialize_layer_root(), McsRwLock(), foedus::storage::masstree::MasstreeBorderPage::reserve_initially_next_layer(), foedus::storage::masstree::MasstreeBorderPage::reserve_record_space(), foedus::xct::RwLockableXctId::reset(), and foedus::storage::masstree::SplitBorder::run().

                       {
     tail_ = nreaders_ = 0;
     set_next_writer(kNextWriterNone);
     assorted::memory_fence_release();
   }

Here is the call graph for this function:

Here is the caller graph for this function:

void foedus::xct::McsRwLock::set_next_writer ( thread::ThreadId thread_id )

inline

Definition at line 822 of file xct_id.hpp.

References xchg_next_writer().

Referenced by reset().

                                                         {
     xchg_next_writer(thread_id);  // sub-word access...
   }

Here is the call graph for this function:

Here is the caller graph for this function:

static uint32_t foedus::xct::McsRwLock::to_tail_int	(	thread::ThreadId	tail_waiter,
		McsBlockIndex	tail_waiter_block
	)

inlinestatic

Definition at line 848 of file xct_id.hpp.

References ASSERT_ND.

                                      {
     ASSERT_ND(tail_waiter_block <= 0xFFFFU);
     return static_cast<uint32_t>(tail_waiter) << 16 | (tail_waiter_block & 0xFFFFU);
   }

Here is the caller graph for this function:

thread::ThreadId foedus::xct::McsRwLock::xchg_next_writer ( thread::ThreadId id )

inline

Definition at line 828 of file xct_id.hpp.

References next_writer_.

Referenced by set_next_writer().

                                                             {
     return assorted::raw_atomic_exchange<thread::ThreadId>(&next_writer_, id);
   }

Here is the caller graph for this function:

uint32_t foedus::xct::McsRwLock::xchg_tail ( uint32_t new_tail )

inline

Definition at line 839 of file xct_id.hpp.

References tail_.

                                                {
     return assorted::raw_atomic_exchange<uint32_t>(&tail_, new_tail);
   }

Friends And Related Function Documentation

std::ostream& operator<<	(	std::ostream &	o,
		const McsRwLock &	v
	)

friend

Definition at line 195 of file xct_id.cpp.

                                                           {
   o << "<McsRwLock><locked>" << v.is_locked() << "</locked><tail_waiter>"
     << v.get_tail_waiter() << "</tail_waiter><tail_block>" << v.get_tail_waiter_block()
     << "</tail_block></McsRwLock>";
   return o;
 }