libfoedus-core
FOEDUS Core Library
Public Member Functions | List of all members
foedus::xct::McsWwImpl< ADAPTOR > Class Template Reference
FOEDUS Components » Transaction Manager

A specialized/simplified implementation of an MCS-locking Algorithm for exclusive-only (WW) locks. More...

Detailed Description

template<typename ADAPTOR>
class foedus::xct::McsWwImpl< ADAPTOR >

A specialized/simplified implementation of an MCS-locking Algorithm for exclusive-only (WW) locks.

This is exactly same as MCSg. Most places in our codebase now use RW locks, but still there are a few WW-only places, such as page-lock (well, so far).

Definition at line 182 of file xct_mcs_impl.hpp.

#include <xct_mcs_impl.hpp>

Public Member Functions

 McsWwImpl (ADAPTOR adaptor)
 
McsBlockIndex acquire_unconditional (McsWwLock *lock)
 [WW] Unconditionally takes exclusive-only MCS lock on the given lock. More...
 
McsBlockIndex acquire_try (McsWwLock *lock)
 [WW] Try to take an exclusive lock. More...
 
McsBlockIndex initial (McsWwLock *lock)
 [WW] This doesn't use any atomic operation. More...
 
void release (McsWwLock *lock, McsBlockIndex block_index)
 [WW] Unlcok an MCS lock acquired by this thread. More...
 

Constructor & Destructor Documentation

template<typename ADAPTOR>
foedus::xct::McsWwImpl< ADAPTOR >::McsWwImpl ( ADAPTOR  adaptor)
inlineexplicit

Definition at line 184 of file xct_mcs_impl.hpp.

184 : adaptor_(adaptor) {}

Member Function Documentation

template<typename ADAPTOR >
McsBlockIndex foedus::xct::McsWwImpl< ADAPTOR >::acquire_try ( McsWwLock *  lock)

[WW] Try to take an exclusive lock.

Precondition
the lock must NOT be taken by this thread yet.
Returns
0 if failed, the block index if acquired.

Definition at line 137 of file xct_mcs_impl.cpp.

References foedus::xct::assert_mcs_aligned(), ASSERT_ND, foedus::xct::McsWwBlock::clear_successor_release(), foedus::xct::McsWwBlockData::get_thread_id_relaxed(), foedus::xct::McsWwBlockData::is_guest_relaxed(), foedus::xct::McsWwLock::is_locked(), foedus::xct::McsWwBlockData::is_valid_relaxed(), foedus::xct::McsWwLock::tail_, and foedus::xct::McsWwBlockData::word_.

137  {
138  assert_mcs_aligned(mcs_lock);
139  // In this function, we don't even need to modify me_waiting because
140  // we are not waiting whether we fail or succeed.
141  ASSERT_ND(!adaptor_.me_waiting()->load());
142  ASSERT_ND(adaptor_.get_cur_block() < 0xFFFFU);
143  McsBlockIndex block_index = adaptor_.issue_new_block();
144  ASSERT_ND(block_index > 0);
145  ASSERT_ND(block_index <= 0xFFFFU);
146  McsWwBlock* my_block = adaptor_.get_ww_my_block(block_index);
147  my_block->clear_successor_release();
148  const thread::ThreadId id = adaptor_.get_my_id();
149  McsWwBlockData desired(id, block_index); // purely local copy. okay to be always relaxed.
150  auto* address = &(mcs_lock->tail_); // be careful on this one!
151  assert_mcs_aligned(address);
152 
153  McsWwBlockData pred; // purely local copy. okay to be always relaxed.
154  ASSERT_ND(!pred.is_valid_relaxed());
155  // atomic op should imply full barrier, but make sure announcing the initialized new block.
156  ASSERT_ND(address->get_word_atomic() != desired.word_);
157  bool swapped = assorted::raw_atomic_compare_exchange_weak<uint64_t>(
158  &address->word_,
159  &pred.word_,
160  desired.word_);
161 
162  if (swapped) {
163  // this means it was not locked.
164  ASSERT_ND(mcs_lock->is_locked());
165  DVLOG(2) << "Okay, got a lock uncontended. me=" << id;
166  ASSERT_ND(address->is_valid_atomic());
167  ASSERT_ND(!address->is_guest_atomic());
168  ASSERT_ND(!pred.is_valid_relaxed());
169  ASSERT_ND(!adaptor_.me_waiting()->load());
170  return block_index; // we got it!
171  }
172 
173  // We couldn't get the lock. As we didn't even install the queue in this case,
174  // we don't need anything for cleanup either. Let's just do sanity check on pred
175 #ifndef NDEBUG
176  ASSERT_ND(pred.is_valid_relaxed());
177  ASSERT_ND(!adaptor_.me_waiting()->load());
178  if (!pred.is_guest_relaxed()) {
179  thread::ThreadId predecessor_id = pred.get_thread_id_relaxed();
180  ASSERT_ND(predecessor_id != id);
181  }
182 #endif // NDEBUG
183 
184  // In this case, we are 100% sure no one else observed the block, so let's decrement
185  // the counter to reuse the block index. Otherwise we'll quickly reach 2^16.
186  adaptor_.cancel_new_block(block_index);
187  return 0;
188 }
foedus::xct::McsBlockIndex
uint32_t McsBlockIndex
Index in thread-local MCS block.
Definition: xct_id.hpp:153
foedus::thread::ThreadId
uint16_t ThreadId
Typedef for a global ID of Thread (core), which is unique across NUMA nodes.
Definition: thread_id.hpp:80
foedus::xct::assert_mcs_aligned
void assert_mcs_aligned(const void *address)
Definition: xct_mcs_impl.cpp:34
ASSERT_ND
#define ASSERT_ND(x)
A warning-free wrapper macro of assert() that has no performance effect in release mode even when 'x'...
Definition: assert_nd.hpp:72

Here is the call graph for this function:

template<typename ADAPTOR >
McsBlockIndex foedus::xct::McsWwImpl< ADAPTOR >::acquire_unconditional ( McsWwLock *  mcs_lock)

[WW] Unconditionally takes exclusive-only MCS lock on the given lock.

WW-lock implementations (all simple versions) These do not depend on RW_BLOCK, so they are primary templates without partial specialization.

So we don't need any trick.

Definition at line 53 of file xct_mcs_impl.cpp.

References foedus::xct::assert_mcs_aligned(), ASSERT_ND, foedus::xct::McsWwBlock::clear_successor_release(), foedus::xct::McsWwBlockData::get_block_relaxed(), foedus::xct::McsWwBlockData::get_thread_id_relaxed(), foedus::xct::McsWwBlockData::is_guest_relaxed(), foedus::xct::McsWwLock::is_locked(), foedus::xct::McsWwBlockData::is_valid_relaxed(), foedus::xct::kMcsGuestId, foedus::xct::spin_until(), foedus::xct::McsWwLock::tail_, UNLIKELY, and foedus::xct::McsWwBlockData::word_.

53  {
54  // Basically _all_ writes in this function must come with some memory barrier. Be careful!
55  // Also, the performance of this method really matters, especially that of common path.
56  // Check objdump -d. Everything in common path should be inlined.
57  // Also, check minimal sufficient mfences (note, xchg implies lock prefix. not a compiler's bug!).
58  std::atomic<bool>* me_waiting = adaptor_.me_waiting();
59  ASSERT_ND(!me_waiting->load());
60  assert_mcs_aligned(mcs_lock);
61  // so far we allow only 2^16 MCS blocks per transaction. we might increase later.
62  ASSERT_ND(adaptor_.get_cur_block() < 0xFFFFU);
63  McsBlockIndex block_index = adaptor_.issue_new_block();
64  ASSERT_ND(block_index > 0);
65  ASSERT_ND(block_index <= 0xFFFFU);
66  McsWwBlock* my_block = adaptor_.get_ww_my_block(block_index);
67  my_block->clear_successor_release();
68  me_waiting->store(true, std::memory_order_release);
69  const thread::ThreadId id = adaptor_.get_my_id();
70  McsWwBlockData desired(id, block_index); // purely local copy. okay to be always relaxed.
71  McsWwBlockData group_tail = desired; // purely local copy. okay to be always relaxed.
72  auto* address = &(mcs_lock->tail_); // be careful on this one!
73  assert_mcs_aligned(address);
74 
75  McsWwBlockData pred; // purely local copy. okay to be always relaxed.
76  ASSERT_ND(!pred.is_valid_relaxed());
77  while (true) {
78  // if it's obviously locked by a guest, we should wait until it's released.
79  // so far this is busy-wait, we can do sth. to prevent priority inversion later.
80  if (UNLIKELY(address->is_guest_relaxed())) {
81  spin_until([address]{ return !address->is_guest_acquire(); });
82  }
83 
84  // atomic op should imply full barrier, but make sure announcing the initialized new block.
85  ASSERT_ND(!group_tail.is_guest_relaxed());
86  ASSERT_ND(group_tail.is_valid_relaxed());
87  ASSERT_ND(address->get_word_atomic() != group_tail.word_);
88  pred.word_ = assorted::raw_atomic_exchange<uint64_t>(&address->word_, group_tail.word_);
89  ASSERT_ND(pred != group_tail);
90  ASSERT_ND(pred != desired);
91 
92  if (!pred.is_valid_relaxed()) {
93  // this means it was not locked.
94  ASSERT_ND(mcs_lock->is_locked());
95  DVLOG(2) << "Okay, got a lock uncontended. me=" << id;
96  me_waiting->store(false, std::memory_order_release);
97  ASSERT_ND(address->is_valid_atomic());
98  return block_index;
99  } else if (UNLIKELY(pred.is_guest_relaxed())) {
100  // ouch, I don't want to keep the guest ID! return it back.
101  // This also determines the group_tail of this queue
102  group_tail.word_ = assorted::raw_atomic_exchange<uint64_t>(&address->word_, kMcsGuestId);
103  ASSERT_ND(group_tail.is_valid_relaxed() && !group_tail.is_guest_relaxed());
104  continue;
105  } else {
106  break;
107  }
108  }
109 
110  ASSERT_ND(pred.is_valid_relaxed() && !pred.is_guest_relaxed());
111  ASSERT_ND(address->is_valid_atomic());
112  ASSERT_ND(!address->is_guest_atomic());
113  ASSERT_ND(mcs_lock->is_locked());
114  thread::ThreadId predecessor_id = pred.get_thread_id_relaxed();
115  ASSERT_ND(predecessor_id != id);
116  McsBlockIndex predecessor_block = pred.get_block_relaxed();
117  DVLOG(0) << "mm, contended, we have to wait.. me=" << id << " pred=" << predecessor_id;
118 
119  ASSERT_ND(me_waiting->load());
120  McsWwBlock* pred_block = adaptor_.get_ww_other_block(predecessor_id, predecessor_block);
121  ASSERT_ND(!pred_block->has_successor_atomic());
122 
123  pred_block->set_successor_release(id, block_index);
124 
125  ASSERT_ND(address->is_valid_atomic());
126  ASSERT_ND(!address->is_guest_atomic());
127  spin_until([me_waiting]{ return !me_waiting->load(std::memory_order_acquire); });
128  DVLOG(1) << "Okay, now I hold the lock. me=" << id << ", ex-pred=" << predecessor_id;
129  ASSERT_ND(!me_waiting->load());
130  ASSERT_ND(mcs_lock->is_locked());
131  ASSERT_ND(address->is_valid_atomic());
132  ASSERT_ND(!address->is_guest_atomic());
133  return block_index;
134 }
foedus::xct::kMcsGuestId
const uint64_t kMcsGuestId
A special value meaning the lock is held by a non-regular guest that doesn't have a context...
Definition: xct_id.hpp:158
foedus::xct::spin_until
void spin_until(COND spin_until_cond)
Definition: xct_mcs_impl.cpp:41
foedus::xct::McsBlockIndex
uint32_t McsBlockIndex
Index in thread-local MCS block.
Definition: xct_id.hpp:153
foedus::thread::ThreadId
uint16_t ThreadId
Typedef for a global ID of Thread (core), which is unique across NUMA nodes.
Definition: thread_id.hpp:80
foedus::xct::assert_mcs_aligned
void assert_mcs_aligned(const void *address)
Definition: xct_mcs_impl.cpp:34
UNLIKELY
#define UNLIKELY(x)
Hints that x is highly likely false.
Definition: compiler.hpp:104
ASSERT_ND
#define ASSERT_ND(x)
A warning-free wrapper macro of assert() that has no performance effect in release mode even when 'x'...
Definition: assert_nd.hpp:72

Here is the call graph for this function:

template<typename ADAPTOR >
McsBlockIndex foedus::xct::McsWwImpl< ADAPTOR >::initial ( McsWwLock *  lock)

[WW] This doesn't use any atomic operation.

only allowed when there is no race TASK(Hideaki): This will be renamed to mcs_non_racy_lock(). "initial_lock" is ambiguous.

Definition at line 191 of file xct_mcs_impl.cpp.

References foedus::xct::assert_mcs_aligned(), ASSERT_ND, foedus::xct::McsWwBlock::clear_successor_release(), foedus::xct::McsWwLock::is_locked(), and foedus::xct::McsWwLock::reset_release().

191  {
192  // Basically _all_ writes in this function must come with release barrier.
193  // This method itself doesn't need barriers, but then we need to later take a seq_cst barrier
194  // in an appropriate place. That's hard to debug, so just take release barriers here.
195  // Also, everything should be inlined.
196  assert_mcs_aligned(mcs_lock);
197  ASSERT_ND(!adaptor_.me_waiting()->load());
198  ASSERT_ND(!mcs_lock->is_locked());
199  // so far we allow only 2^16 MCS blocks per transaction. we might increase later.
200  ASSERT_ND(adaptor_.get_cur_block() < 0xFFFFU);
201 
202  McsBlockIndex block_index = adaptor_.issue_new_block();
203  ASSERT_ND(block_index > 0 && block_index <= 0xFFFFU);
204  McsWwBlock* my_block = adaptor_.get_ww_my_block(block_index);
205  my_block->clear_successor_release();
206  const thread::ThreadId id = adaptor_.get_my_id();
207  mcs_lock->reset_release(id, block_index);
208  return block_index;
209 }
foedus::xct::McsBlockIndex
uint32_t McsBlockIndex
Index in thread-local MCS block.
Definition: xct_id.hpp:153
foedus::thread::ThreadId
uint16_t ThreadId
Typedef for a global ID of Thread (core), which is unique across NUMA nodes.
Definition: thread_id.hpp:80
foedus::xct::assert_mcs_aligned
void assert_mcs_aligned(const void *address)
Definition: xct_mcs_impl.cpp:34
ASSERT_ND
#define ASSERT_ND(x)
A warning-free wrapper macro of assert() that has no performance effect in release mode even when 'x'...
Definition: assert_nd.hpp:72

Here is the call graph for this function:

template<typename ADAPTOR >
void foedus::xct::McsWwImpl< ADAPTOR >::release ( McsWwLock *  lock,
McsBlockIndex  block_index 
)

[WW] Unlcok an MCS lock acquired by this thread.

Definition at line 212 of file xct_mcs_impl.cpp.

References foedus::xct::assert_mcs_aligned(), ASSERT_ND, foedus::xct::McsWwBlock::get_successor_thread_id_relaxed(), foedus::xct::McsWwLock::get_tail_waiter(), foedus::xct::McsWwBlock::has_successor_acquire(), foedus::xct::McsWwBlockData::is_guest_relaxed(), foedus::xct::McsWwLock::is_locked(), foedus::xct::McsWwBlockData::is_valid_relaxed(), foedus::xct::spin_until(), foedus::xct::McsWwLock::tail_, UNLIKELY, and foedus::xct::McsWwBlockData::word_.

Referenced by foedus::xct::SysxctLockList::release_all_locks().

212  {
213  // Basically _all_ writes in this function must come with some memory barrier. Be careful!
214  // Also, the performance of this method really matters, especially that of common path.
215  // Check objdump -d. Everything in common path should be inlined.
216  // Also, check minimal sufficient lock/mfences.
217  assert_mcs_aligned(mcs_lock);
218  ASSERT_ND(!adaptor_.me_waiting()->load());
219  ASSERT_ND(mcs_lock->is_locked());
220  ASSERT_ND(block_index > 0);
221  ASSERT_ND(adaptor_.get_cur_block() >= block_index);
222  const thread::ThreadId id = adaptor_.get_my_id();
223  const McsWwBlockData myself(id, block_index); // purely local copy. okay to be always relaxed.
224  auto* address = &(mcs_lock->tail_); // be careful on this one!
225  McsWwBlock* block = adaptor_.get_ww_my_block(block_index);
226  if (!block->has_successor_acquire()) {
227  // okay, successor "seems" nullptr (not contended), but we have to make it sure with atomic CAS
228  McsWwBlockData expected = myself; // purely local copy. okay to be always relaxed.
229  assert_mcs_aligned(address);
230  bool swapped
231  = assorted::raw_atomic_compare_exchange_strong<uint64_t>(
232  &address->word_,
233  &expected.word_,
234  0);
235  if (swapped) {
236  // we have just unset the locked flag, but someone else might have just acquired it,
237  // so we can't put assertion here.
238  ASSERT_ND(id == 0 || mcs_lock->get_tail_waiter() != id);
239  ASSERT_ND(expected == myself);
240  ASSERT_ND(address->copy_atomic() != myself);
241  DVLOG(2) << "Okay, release a lock uncontended. me=" << id;
242  return;
243  }
244  ASSERT_ND(expected.is_valid_relaxed());
245  ASSERT_ND(!expected.is_guest_relaxed());
246  DVLOG(0) << "Interesting contention on MCS release. I thought it's null, but someone has just "
247  " jumped in. me=" << id << ", mcs_lock=" << *mcs_lock;
248  // wait for someone else to set the successor
249  ASSERT_ND(mcs_lock->is_locked());
250  if (UNLIKELY(!block->has_successor_acquire())) {
251  spin_until([block]{ return block->has_successor_acquire(); });
252  }
253  }
254  // Relax: In either case above, we confirmed that block->has_successor with fences.
255  // We thus can just read in relaxed mode here.
256  thread::ThreadId successor_id = block->get_successor_thread_id_relaxed();
257  DVLOG(1) << "Okay, I have a successor. me=" << id << ", succ=" << successor_id;
258  ASSERT_ND(successor_id != id);
259  ASSERT_ND(address->copy_atomic() != myself);
260 
261  ASSERT_ND(adaptor_.other_waiting(successor_id)->load());
262  ASSERT_ND(mcs_lock->is_locked());
263 
264  ASSERT_ND(address->copy_atomic() != myself);
265  adaptor_.other_waiting(successor_id)->store(false, std::memory_order_release);
266  ASSERT_ND(address->copy_atomic() != myself);
267 }
foedus::xct::spin_until
void spin_until(COND spin_until_cond)
Definition: xct_mcs_impl.cpp:41
foedus::thread::ThreadId
uint16_t ThreadId
Typedef for a global ID of Thread (core), which is unique across NUMA nodes.
Definition: thread_id.hpp:80
foedus::xct::assert_mcs_aligned
void assert_mcs_aligned(const void *address)
Definition: xct_mcs_impl.cpp:34
UNLIKELY
#define UNLIKELY(x)
Hints that x is highly likely false.
Definition: compiler.hpp:104
ASSERT_ND
#define ASSERT_ND(x)
A warning-free wrapper macro of assert() that has no performance effect in release mode even when 'x'...
Definition: assert_nd.hpp:72

Here is the call graph for this function:

Here is the caller graph for this function:

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