foedus::xct::CurrentLockList Class Reference

Sorted list of all locks, either read-lock or write-lock, taken in the current run. More...

Detailed Description

Sorted list of all locks, either read-lock or write-lock, taken in the current run.

This is NOT a POD because we need dynamic memory for the list. This holds all locks in address order to help our commit protocol.

We so far maintain this object in addition to read-set/write-set. We can merge these objects in to one, which will allow us to add some functionality and optimizations. For example, "read my own write" semantics would be practically implemented with such an integrated list. We can reduce the number of sorting and tracking, too. But, let's do them later.

Note

This object itself is thread-private. No concurrency control needed.

Definition at line 309 of file retrospective_lock_list.hpp.

#include <retrospective_lock_list.hpp>

Public Member Functions
	CurrentLockList ()
	~CurrentLockList ()
void	init (LockEntry *array, uint32_t capacity, const memory::GlobalVolatilePageResolver &resolver)
void	uninit ()
void	clear_entries ()
LockListPosition	binary_search (UniversalLockId lock) const
	Analogous to std::binary_search() for the given lock. More...
LockListPosition	get_or_add_entry (UniversalLockId lock_id, RwLockableXctId *lock, LockMode preferred_mode)
	Adds an entry to this list, re-sorting part of the list if necessary to keep the sortedness. More...
LockListPosition	lower_bound (UniversalLockId lock) const
	Analogous to std::lower_bound() for the given lock. More...
const LockEntry *	get_array () const
LockEntry *	get_array ()
LockEntry *	get_entry (LockListPosition pos)
const LockEntry *	get_entry (LockListPosition pos) const
uint32_t	get_capacity () const
LockListPosition	get_last_active_entry () const
bool	is_valid_entry (LockListPosition pos) const
bool	is_empty () const
void	assert_sorted () const __attribute__((always_inline))
void	assert_sorted_impl () const
LockEntry *	begin ()
LockEntry *	end ()
const LockEntry *	cbegin () const
const LockEntry *	cend () const
const memory::GlobalVolatilePageResolver &	get_volatile_page_resolver () const
LockListPosition	get_last_locked_entry () const
UniversalLockId	get_max_locked_id () const
LockListPosition	calculate_last_locked_entry () const
	Calculate last_locked_entry_ by really checking the whole list. More...
LockListPosition	calculate_last_locked_entry_from (LockListPosition from) const
	Only searches among entries at or before "from". More...
void	assert_last_locked_entry () const
void	batch_insert_write_placeholders (const WriteXctAccess *write_set, uint32_t write_set_size)
	Create entries for all write-sets in one-shot. More...
void	prepopulate_for_retrospective_lock_list (const RetrospectiveLockList &rll)
	Another batch-insert method used at the beginning of a transaction. More...
template<typename MCS_RW_IMPL >
ErrorCode	try_or_acquire_single_lock (LockListPosition pos, MCS_RW_IMPL *mcs_rw_impl)
	Methods below take or release locks, so they receive MCS_RW_IMPL, a template param. More...
template<typename MCS_RW_IMPL >
ErrorCode	try_or_acquire_multiple_locks (LockListPosition upto_pos, MCS_RW_IMPL *mcs_rw_impl)
	Acquire multiple locks up to the given position in canonical order. More...
template<typename MCS_RW_IMPL >
void	try_async_single_lock (LockListPosition pos, MCS_RW_IMPL *mcs_rw_impl)
template<typename MCS_RW_IMPL >
bool	retry_async_single_lock (LockListPosition pos, MCS_RW_IMPL *mcs_rw_impl)
template<typename MCS_RW_IMPL >
void	cancel_async_single_lock (LockListPosition pos, MCS_RW_IMPL *mcs_rw_impl)
template<typename MCS_RW_IMPL >
void	try_async_multiple_locks (LockListPosition upto_pos, MCS_RW_IMPL *mcs_rw_impl)
template<typename MCS_RW_IMPL >
void	release_all_locks (MCS_RW_IMPL *mcs_rw_impl)
template<typename MCS_RW_IMPL >
void	release_all_after (UniversalLockId address, MCS_RW_IMPL *mcs_rw_impl)
	Release all locks in CLL whose addresses are canonically ordered before the parameter. More...
template<typename MCS_RW_IMPL >
void	release_all_at_and_after (UniversalLockId address, MCS_RW_IMPL *mcs_rw_impl)
	same as release_all_after(address - 1) More...
template<typename MCS_RW_IMPL >
void	giveup_all_after (UniversalLockId address, MCS_RW_IMPL *mcs_rw_impl)
	This gives-up locks in CLL that are not yet taken. More...
template<typename MCS_RW_IMPL >
void	giveup_all_at_and_after (UniversalLockId address, MCS_RW_IMPL *mcs_rw_impl)

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

Constructor & Destructor Documentation

foedus::xct::CurrentLockList::CurrentLockList

(

)

Definition at line 76 of file retrospective_lock_list.cpp.

References clear_entries().

                                 {
  array_ = nullptr;
  capacity_ = 0;
  clear_entries();
}

Here is the call graph for this function:

foedus::xct::CurrentLockList::~CurrentLockList

(

)

Definition at line 82 of file retrospective_lock_list.cpp.

References uninit().

                                  {
  uninit();
}

Here is the call graph for this function:

Member Function Documentation

void foedus::xct::CurrentLockList::assert_last_locked_entry ( ) const

inline

Definition at line 405 of file retrospective_lock_list.hpp.

References ASSERT_ND, and calculate_last_locked_entry().

Referenced by assert_sorted_impl(), binary_search(), get_or_add_entry(), lower_bound(), release_all_after(), retry_async_single_lock(), try_async_single_lock(), and try_or_acquire_single_lock().

                                        {
#ifndef NDEBUG
    LockListPosition correct = calculate_last_locked_entry();
    ASSERT_ND(correct == last_locked_entry_);
#endif  // NDEBUG
  }

Here is the call graph for this function:

Here is the caller graph for this function:

void foedus::xct::CurrentLockList::assert_sorted ( ) const

inline

Definition at line 555 of file retrospective_lock_list.hpp.

References assert_sorted_impl().

Referenced by batch_insert_write_placeholders(), foedus::xct::CurrentLockListIteratorForWriteSet::CurrentLockListIteratorForWriteSet(), get_or_add_entry(), giveup_all_after(), prepopulate_for_retrospective_lock_list(), and release_all_after().

                                                 {
#ifndef  NDEBUG
  assert_sorted_impl();
#endif  // NDEBUG
}

Here is the call graph for this function:

Here is the caller graph for this function:

void foedus::xct::CurrentLockList::assert_sorted_impl

(

)

const

Definition at line 178 of file retrospective_lock_list.cpp.

References assert_last_locked_entry(), and foedus::xct::lock_assert_sorted().

Referenced by assert_sorted().

                                               {
  assert_last_locked_entry();
  lock_assert_sorted(*this);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void foedus::xct::CurrentLockList::batch_insert_write_placeholders	(	const WriteXctAccess *	write_set,
		uint32_t	write_set_size
	)

Create entries for all write-sets in one-shot.

Parameters

[in]	write_set	write-sets to create placeholders for. Must be canonically sorted.
[in]	write_set_size	count of entries in write_set

During precommit, we must create an entry for every write-set. Rather than doing it one by one, this method creates placeholder entries for all of them. The placeholders are not locked yet (taken_mode_ == kNoLock).

Definition at line 329 of file retrospective_lock_list.cpp.

References ASSERT_ND, assert_sorted(), binary_search(), calculate_last_locked_entry(), foedus::xct::kLockListPositionInvalid, foedus::xct::kNoLock, foedus::xct::kWriteLock, foedus::xct::RecordXctAccess::ordinal_, foedus::xct::RecordXctAccess::owner_id_address_, foedus::xct::RecordXctAccess::owner_lock_id_, foedus::xct::LockEntry::preferred_mode_, foedus::xct::LockEntry::set(), and foedus::xct::LockEntry::universal_lock_id_.

Referenced by foedus::xct::XctManagerPimpl::precommit_xct_lock().

                           {
  // We want to avoid full-sorting and minimize the number of copies/shifts.
  // Luckily, write_set is already sorted, so is our array_. Just merge them in order.
  if (write_set_size == 0) {
    return;
  }
#ifndef NDEBUG
  for (uint32_t i = 1; i < write_set_size; ++i) {
    ASSERT_ND(write_set[i - 1].ordinal_ != write_set[i].ordinal_);
    if (write_set[i].owner_lock_id_ == write_set[i - 1].owner_lock_id_) {
      ASSERT_ND(write_set[i - 1].ordinal_ < write_set[i].ordinal_);
    } else {
      ASSERT_ND(write_set[i - 1].owner_lock_id_ < write_set[i].owner_lock_id_);
    }
  }
  assert_sorted();
#endif  // NDEBUG

  // Implementation note: I considered a few approaches to efficiently do the merge.
  //  1) insertion-sort: that sounds expensive... we might be inserting several
  //  2) a bit complex. first path to identify the number of new entries, then second path to
  //   merge from the end, not the beginning, to copy/shift only what we need to.
  //  3) insert all write-sets at the end then invoke std::sort once.
  // For now I picked 3) for simplicity. Revisit laster if CPU profile tells something.
  if (last_active_entry_ == kLockListPositionInvalid) {
    // If CLL is now empty, it's even easier. Just add all write-sets
    uint32_t added = 0;
    for (uint32_t write_pos = 0; write_pos < write_set_size; ++write_pos) {
      const WriteXctAccess* write = write_set + write_pos;
      if (write_pos > 0) {
        const WriteXctAccess* prev = write_set + write_pos - 1;
        ASSERT_ND(write->ordinal_ != prev->ordinal_);
        ASSERT_ND(write->owner_lock_id_ >= prev->owner_lock_id_);
        if (write->owner_lock_id_ == prev->owner_lock_id_) {
          ASSERT_ND(write->ordinal_ > prev->ordinal_);
          continue;
        }
      }
      ++added;
      LockEntry* new_entry = array_ + added;
      new_entry->set(write->owner_lock_id_, write->owner_id_address_, kWriteLock, kNoLock);
    }
    last_active_entry_ = added;
  } else {
    uint32_t write_pos = 0;
    uint32_t added = 0;
    for (LockListPosition pos = 1U; pos <= last_active_entry_ && write_pos < write_set_size;) {
      LockEntry* existing = array_ + pos;
      const WriteXctAccess* write = write_set + write_pos;
      UniversalLockId write_lock_id = write->owner_lock_id_;
      if (existing->universal_lock_id_ < write_lock_id) {
        ++pos;
      } else if (existing->universal_lock_id_ == write_lock_id) {
        if (existing->preferred_mode_ != kWriteLock) {
          existing->preferred_mode_ = kWriteLock;
        }
        ++write_pos;
      } else {
        // yuppy, new entry.
        ASSERT_ND(existing->universal_lock_id_ > write_lock_id);
        ++added;
        LockEntry* new_entry = array_ + last_active_entry_ + added;
        new_entry->set(write_lock_id, write->owner_id_address_, kWriteLock, kNoLock);
        // be careful on duplicate in write-set.
        // It might contain multiple writes to one record.
        for (++write_pos; write_pos < write_set_size; ++write_pos) {
          const WriteXctAccess* next_write = write_set + write_pos;
          UniversalLockId next_write_id = next_write->owner_lock_id_;
          ASSERT_ND(next_write_id >= write_lock_id);
          if (next_write_id > write_lock_id) {
            break;
          }
        }
      }
    }

    while (write_pos < write_set_size) {
      // After iterating over all existing entries, still some write-set entry remains.
      // Hence they are all after the existing entries.
      const WriteXctAccess* write = write_set + write_pos;
      UniversalLockId write_lock_id = write->owner_lock_id_;
      ASSERT_ND(last_active_entry_ == kLockListPositionInvalid
        || array_[last_active_entry_].universal_lock_id_ < write_lock_id);

      // Again, be careful on duplicate in write set.
      ++added;
      LockEntry* new_entry = array_ + last_active_entry_ + added;
      new_entry->set(write_lock_id, write->owner_id_address_, kWriteLock, kNoLock);
      for (++write_pos; write_pos < write_set_size; ++write_pos) {
        const WriteXctAccess* next_write = write_set + write_pos;
        UniversalLockId next_write_id = next_write->owner_lock_id_;
        ASSERT_ND(next_write_id >= write_lock_id);
        if (next_write_id > write_lock_id) {
          break;
        }
      }
    }

    if (added > 0) {
      last_active_entry_ += added;
      std::sort(array_ + 1U, array_ + 1U + last_active_entry_);
    }
  }

  // Adjusting last_locked_entry_ is not impossible.. but let's just recalculate. Not too often.
  last_locked_entry_ = calculate_last_locked_entry();
  assert_sorted();
#ifndef NDEBUG
  for (uint32_t i = 0; i < write_set_size; ++i) {
    ASSERT_ND(binary_search(write_set[i].owner_lock_id_) != kLockListPositionInvalid);
  }
#endif  // NDEBUG
}

Here is the call graph for this function:

Here is the caller graph for this function:

LockEntry* foedus::xct::CurrentLockList::begin ( )

inline

Definition at line 371 of file retrospective_lock_list.hpp.

Referenced by giveup_all_after(), and release_all_after().

{ return array_ + 1U; }

Here is the caller graph for this function:

LockListPosition foedus::xct::CurrentLockList::binary_search

(

UniversalLockId

lock

)

const

Analogous to std::binary_search() for the given lock.

Data manipulation (search/add/etc)

Returns

Index of an entry whose lock_ == lock. kLockListPositionInvalid if not found.

Definition at line 189 of file retrospective_lock_list.cpp.

References assert_last_locked_entry().

Referenced by batch_insert_write_placeholders().

                                                                          {
  assert_last_locked_entry();
  return lock_binary_search<CurrentLockList, LockEntry>(*this, lock);
}

Here is the call graph for this function:

Here is the caller graph for this function:

LockListPosition foedus::xct::CurrentLockList::calculate_last_locked_entry ( ) const

inline

Calculate last_locked_entry_ by really checking the whole list.

Usually for sanity checks

Definition at line 393 of file retrospective_lock_list.hpp.

References calculate_last_locked_entry_from().

Referenced by assert_last_locked_entry(), and batch_insert_write_placeholders().

                                                       {
    return calculate_last_locked_entry_from(last_active_entry_);
  }

Here is the call graph for this function:

Here is the caller graph for this function:

LockListPosition foedus::xct::CurrentLockList::calculate_last_locked_entry_from ( LockListPosition  from ) const

inline

Only searches among entries at or before "from".

Definition at line 397 of file retrospective_lock_list.hpp.

References foedus::xct::kLockListPositionInvalid.

Referenced by calculate_last_locked_entry(), try_async_single_lock(), and try_or_acquire_single_lock().

                                                                                 {
    for (LockListPosition pos = from; pos > kLockListPositionInvalid; --pos) {
      if (array_[pos].is_locked()) {
        return pos;
      }
    }
    return kLockListPositionInvalid;
  }

Here is the caller graph for this function:

template<typename MCS_RW_IMPL >

void foedus::xct::CurrentLockList::cancel_async_single_lock ( LockListPosition  pos, MCS_RW_IMPL *  mcs_rw_impl  )

inline

Definition at line 724 of file retrospective_lock_list.hpp.

References ASSERT_ND, get_entry(), foedus::xct::RwLockableXctId::get_key_lock(), foedus::xct::LockEntry::is_enough(), foedus::xct::kNoLock, foedus::xct::kReadLock, foedus::xct::LockEntry::lock_, foedus::xct::LockEntry::mcs_block_, foedus::xct::LockEntry::preferred_mode_, and foedus::xct::LockEntry::taken_mode_.

                            {
  LockEntry* lock_entry = get_entry(pos);
  ASSERT_ND(!lock_entry->is_enough());
  ASSERT_ND(lock_entry->taken_mode_ == kNoLock);
  ASSERT_ND(lock_entry->mcs_block_);
  McsRwLock* lock_addr = lock_entry->lock_->get_key_lock();
  if (lock_entry->preferred_mode_ == kReadLock) {
    mcs_rw_impl->cancel_async_rw_reader(lock_addr, lock_entry->mcs_block_);
  } else {
    ASSERT_ND(lock_entry->preferred_mode_ == kReadLock);
    mcs_rw_impl->cancel_async_rw_writer(lock_addr, lock_entry->mcs_block_);
  }
  lock_entry->mcs_block_ = 0;
}

Here is the call graph for this function:

const LockEntry* foedus::xct::CurrentLockList::cbegin ( ) const

inline

Definition at line 373 of file retrospective_lock_list.hpp.

{ return array_ + 1U; }

const LockEntry* foedus::xct::CurrentLockList::cend ( ) const

inline

Definition at line 374 of file retrospective_lock_list.hpp.

{ return array_ + 1U + last_active_entry_; }

void foedus::xct::CurrentLockList::clear_entries

(

)

Definition at line 96 of file retrospective_lock_list.cpp.

References foedus::xct::kLockListPositionInvalid, foedus::xct::kNoLock, foedus::xct::LockEntry::lock_, foedus::xct::LockEntry::preferred_mode_, foedus::xct::LockEntry::taken_mode_, and foedus::xct::LockEntry::universal_lock_id_.

Referenced by foedus::xct::Xct::activate(), CurrentLockList(), init(), foedus::xct::XctManagerPimpl::release_and_clear_all_current_locks(), and uninit().

                                    {
  last_active_entry_ = kLockListPositionInvalid;
  last_locked_entry_ = kLockListPositionInvalid;
  if (array_) {
    // Dummy entry
    array_[kLockListPositionInvalid].universal_lock_id_ = 0;
    array_[kLockListPositionInvalid].lock_ = nullptr;
    array_[kLockListPositionInvalid].preferred_mode_ = kNoLock;
    array_[kLockListPositionInvalid].taken_mode_ = kNoLock;
  }
}

Here is the caller graph for this function:

LockEntry* foedus::xct::CurrentLockList::end ( )

inline

Definition at line 372 of file retrospective_lock_list.hpp.

Referenced by giveup_all_after(), and release_all_after().

{ return array_ + 1U + last_active_entry_; }

Here is the caller graph for this function:

const LockEntry* foedus::xct::CurrentLockList::get_array ( ) const

inline

Definition at line 350 of file retrospective_lock_list.hpp.

Referenced by foedus::xct::XctManagerPimpl::precommit_xct_lock().

{ return array_; }

Here is the caller graph for this function:

LockEntry* foedus::xct::CurrentLockList::get_array ( )

inline

Definition at line 351 of file retrospective_lock_list.hpp.

{ return array_; }

uint32_t foedus::xct::CurrentLockList::get_capacity ( ) const

inline

Definition at line 360 of file retrospective_lock_list.hpp.

{ return capacity_; }

LockEntry* foedus::xct::CurrentLockList::get_entry ( LockListPosition  pos )

inline

Definition at line 352 of file retrospective_lock_list.hpp.

References ASSERT_ND, and is_valid_entry().

Referenced by cancel_async_single_lock(), get_max_locked_id(), foedus::xct::CurrentLockListIteratorForWriteSet::next_writes(), foedus::xct::Xct::on_record_read_take_locks_if_needed(), retry_async_single_lock(), try_async_single_lock(), and try_or_acquire_single_lock().

                                             {
    ASSERT_ND(is_valid_entry(pos));
    return array_ + pos;
  }

Here is the call graph for this function:

Here is the caller graph for this function:

const LockEntry* foedus::xct::CurrentLockList::get_entry ( LockListPosition  pos ) const

inline

Definition at line 356 of file retrospective_lock_list.hpp.

References ASSERT_ND, and is_valid_entry().

                                                         {
    ASSERT_ND(is_valid_entry(pos));
    return array_ + pos;
  }

Here is the call graph for this function:

LockListPosition foedus::xct::CurrentLockList::get_last_active_entry ( ) const

inline

Definition at line 361 of file retrospective_lock_list.hpp.

{ return last_active_entry_; }

LockListPosition foedus::xct::CurrentLockList::get_last_locked_entry ( ) const

inline

Returns

largest index of entries that are already locked. kLockListPositionInvalid if no entry is locked.

Definition at line 383 of file retrospective_lock_list.hpp.

Referenced by foedus::xct::XctManagerPimpl::precommit_xct_lock().

{ return last_locked_entry_; }

Here is the caller graph for this function:

UniversalLockId foedus::xct::CurrentLockList::get_max_locked_id ( ) const

inline

Returns

the biggest Id of locks actually locked. If none, kNullUniversalLockId.

Definition at line 385 of file retrospective_lock_list.hpp.

References get_entry(), foedus::xct::kLockListPositionInvalid, foedus::xct::kNullUniversalLockId, and foedus::xct::LockEntry::universal_lock_id_.

Referenced by foedus::thread::ThreadPimpl::cll_get_max_locked_id().

                                            {
    if (last_locked_entry_ == kLockListPositionInvalid) {
      return kNullUniversalLockId;
    } else {
      return get_entry(last_locked_entry_)->universal_lock_id_;
    }
  }

Here is the call graph for this function:

Here is the caller graph for this function:

LockListPosition foedus::xct::CurrentLockList::get_or_add_entry	(	UniversalLockId	lock_id,
		RwLockableXctId *	lock,
		LockMode	preferred_mode
	)

Adds an entry to this list, re-sorting part of the list if necessary to keep the sortedness.

If there is an existing entry for the lock, it just returns its position. If not, this method creates a new entry with taken_mode=kNoLock.

Returns

the position of the newly added entry. kLockListPositionInvalid means the list was full and couldn't add (which is very unlikely, tho).

Note

Do not frequently use this method. You should batch your insert when you can. This method is used when we couldn't batch/expect the new entry.

See also

batch_insert_write_placeholders()

Definition at line 204 of file retrospective_lock_list.cpp.

References assert_last_locked_entry(), ASSERT_ND, assert_sorted(), foedus::xct::kLockListPositionInvalid, foedus::xct::kNoLock, lower_bound(), foedus::xct::LockEntry::preferred_mode_, foedus::xct::LockEntry::set(), and foedus::xct::xct_id_to_universal_lock_id().

Referenced by foedus::xct::Xct::on_record_read_take_locks_if_needed().

                           {
  assert_last_locked_entry();
  ASSERT_ND(id == xct_id_to_universal_lock_id(volatile_page_resolver_, lock));
  // Easy case? (lock >= the last entry)
  LockListPosition insert_pos = lower_bound(id);
  ASSERT_ND(insert_pos != kLockListPositionInvalid);

  // Larger than all existing entries? Append to the last!
  if (insert_pos > last_active_entry_) {
    ASSERT_ND(insert_pos == last_active_entry_ + 1U);
    LockListPosition new_pos = issue_new_position();
    array_[new_pos].set(id, lock, preferred_mode, kNoLock);
    ASSERT_ND(new_pos == insert_pos);
    return new_pos;
  }

  // lower_bound returns the first entry that is NOT less than. is it equal?
  ASSERT_ND(array_[insert_pos].universal_lock_id_ >= id);
  if (array_[insert_pos].universal_lock_id_ == id) {
    // Found existing!
    if (array_[insert_pos].preferred_mode_ < preferred_mode) {
      array_[insert_pos].preferred_mode_ = preferred_mode;
    }
    return insert_pos;
  }

  DVLOG(1) << "not an easy case. We need to adjust the order. This is costly!";
  ASSERT_ND(insert_pos <= last_active_entry_);  // otherwise we went into the 1st branch
  ASSERT_ND(array_[insert_pos].universal_lock_id_ > id);  // if ==, we went into the 2nd branch
  ASSERT_ND(insert_pos == 1U || array_[insert_pos - 1U].universal_lock_id_ < id);

  LockListPosition new_last_pos = issue_new_position();
  ASSERT_ND(new_last_pos > insert_pos);
  uint64_t moved_bytes = sizeof(LockEntry) * (new_last_pos - insert_pos);
  std::memmove(array_ + insert_pos + 1U, array_ + insert_pos, moved_bytes);
  DVLOG(1) << "Re-sorted. hope this won't happen often";
  array_[insert_pos].set(id, lock, preferred_mode, kNoLock);
  if (last_locked_entry_ >= insert_pos) {
    ++last_locked_entry_;
  }

  assert_sorted();
  return insert_pos;
}

Here is the call graph for this function:

Here is the caller graph for this function:

const memory::GlobalVolatilePageResolver& foedus::xct::CurrentLockList::get_volatile_page_resolver ( ) const

inline

Definition at line 375 of file retrospective_lock_list.hpp.

                                                                             {
    return volatile_page_resolver_;
  }

template<typename MCS_RW_IMPL >

void foedus::xct::CurrentLockList::giveup_all_after ( UniversalLockId  address, MCS_RW_IMPL *  mcs_rw_impl  )

inline

This gives-up locks in CLL that are not yet taken.

preferred mode will be set to either NoLock or same as taken_mode, and all incomplete async locks will be cancelled. Unlike clear_entries(), this leaves the entries.

Definition at line 826 of file retrospective_lock_list.hpp.

References ASSERT_ND, assert_sorted(), begin(), end(), foedus::xct::kNoLock, foedus::xct::kReadLock, and foedus::xct::kWriteLock.

Referenced by foedus::thread::ThreadPimpl::cll_giveup_all_locks_after().

                                                                                               {
  assert_sorted();
  uint32_t givenup_read_locks = 0;
  uint32_t givenup_write_locks = 0;
  uint32_t givenup_upgrades = 0;
  uint32_t already_enough_locks = 0;
  uint32_t canceled_async_read_locks = 0;
  uint32_t canceled_async_write_locks = 0;

  for (LockEntry* entry = begin(); entry != end(); ++entry) {
    if (entry->universal_lock_id_ <= address) {
      continue;
    }
    if (entry->preferred_mode_ == kNoLock) {
      continue;
    }
    if (entry->is_enough()) {
      ++already_enough_locks;
      continue;
    }

    if (entry->is_locked()) {
      ASSERT_ND(entry->taken_mode_ == kReadLock);
      ASSERT_ND(entry->preferred_mode_ == kWriteLock);
      ++givenup_upgrades;
      entry->preferred_mode_ = entry->taken_mode_;
    } else if (entry->mcs_block_) {
      if (entry->preferred_mode_ == kReadLock) {
        mcs_rw_impl->cancel_async_rw_reader(entry->lock_->get_key_lock(), entry->mcs_block_);
        ++canceled_async_read_locks;
      } else {
        ASSERT_ND(entry->preferred_mode_ == kWriteLock);
        mcs_rw_impl->cancel_async_rw_writer(entry->lock_->get_key_lock(), entry->mcs_block_);
        ++canceled_async_write_locks;
      }
      entry->mcs_block_ = 0;
      entry->preferred_mode_ = kNoLock;
    } else {
      ASSERT_ND(entry->taken_mode_ == kNoLock);
      if (entry->preferred_mode_ == kReadLock) {
        ++givenup_read_locks;
      } else {
        ASSERT_ND(entry->preferred_mode_ == kWriteLock);
        ++givenup_write_locks;
      }
      entry->preferred_mode_ = kNoLock;
    }
  }

#ifndef NDEBUG
  giveup_all_after_debuglog(
    givenup_read_locks,
    givenup_write_locks,
    givenup_upgrades,
    already_enough_locks,
    canceled_async_read_locks,
    canceled_async_write_locks);
#endif  // NDEBUG
}

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename MCS_RW_IMPL >

void foedus::xct::CurrentLockList::giveup_all_at_and_after ( UniversalLockId  address, MCS_RW_IMPL *  mcs_rw_impl  )

inline

Definition at line 886 of file retrospective_lock_list.hpp.

References foedus::xct::kNullUniversalLockId.

                            {
  if (address == kNullUniversalLockId) {
    giveup_all_after<MCS_RW_IMPL>(kNullUniversalLockId, mcs_rw_impl);
  } else {
    giveup_all_after<MCS_RW_IMPL>(address - 1U, mcs_rw_impl);
  }
}

void foedus::xct::CurrentLockList::init	(	LockEntry *	array,
		uint32_t	capacity,
		const memory::GlobalVolatilePageResolver &	resolver
	)

Definition at line 86 of file retrospective_lock_list.cpp.

References clear_entries().

Referenced by foedus::xct::Xct::initialize().

                                                    {
  array_ = array;
  capacity_ = capacity;
  volatile_page_resolver_ = resolver;
  clear_entries();
}

Here is the call graph for this function:

Here is the caller graph for this function:

bool foedus::xct::CurrentLockList::is_empty ( ) const

inline

Definition at line 365 of file retrospective_lock_list.hpp.

References foedus::xct::kLockListPositionInvalid.

Referenced by foedus::xct::Xct::deactivate(), foedus::xct::XctManagerPimpl::precommit_xct(), and prepopulate_for_retrospective_lock_list().

{ return last_active_entry_ == kLockListPositionInvalid; }

Here is the caller graph for this function:

bool foedus::xct::CurrentLockList::is_valid_entry ( LockListPosition  pos ) const

inline

Definition at line 362 of file retrospective_lock_list.hpp.

References foedus::xct::kLockListPositionInvalid.

Referenced by get_entry().

                                                  {
    return pos != kLockListPositionInvalid && pos <= last_active_entry_;
  }

Here is the caller graph for this function:

LockListPosition foedus::xct::CurrentLockList::lower_bound

(

UniversalLockId

lock

)

const

Analogous to std::lower_bound() for the given lock.

Returns

Index of the fist entry whose lock_ is not less than lock. If no such entry, last_active_entry_ + 1U, whether last_active_entry_ is 0 or not. Thus the return value is always >0. This is to immitate std::lower_bound's behavior.

Definition at line 196 of file retrospective_lock_list.cpp.

References assert_last_locked_entry().

Referenced by get_or_add_entry().

                                                                        {
  assert_last_locked_entry();
  return lock_lower_bound<CurrentLockList, LockEntry>(*this, lock);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void foedus::xct::CurrentLockList::prepopulate_for_retrospective_lock_list

(

const RetrospectiveLockList &

rll

)

Another batch-insert method used at the beginning of a transaction.

When an Xct has RLL, it will highly likely lock all of them. So, it pre-populates CLL entries for all of them at the beginning. This is both for simplicity and performance.

Precondition

is_empty() : call this at the beginning of xct.

!rll.is_empty() : then why the heck are you calling.

Definition at line 445 of file retrospective_lock_list.cpp.

References ASSERT_ND, foedus::xct::RetrospectiveLockList::assert_sorted(), assert_sorted(), foedus::xct::RetrospectiveLockList::get_array(), foedus::xct::RetrospectiveLockList::get_last_active_entry(), foedus::xct::RetrospectiveLockList::is_empty(), is_empty(), and foedus::xct::kLockListPositionInvalid.

Referenced by foedus::xct::Xct::activate().

                                                                                              {
  ASSERT_ND(is_empty());
  ASSERT_ND(!rll.is_empty());
  rll.assert_sorted();
  // Because now we use LockEntry for both RLL and CLL, we can do just one memcpy
  std::memcpy(array_ + 1U, rll.get_array() + 1U, sizeof(LockEntry) * rll.get_last_active_entry());
  last_active_entry_ = rll.get_last_active_entry();
  last_locked_entry_ = kLockListPositionInvalid;
  assert_sorted();
}

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename MCS_RW_IMPL >

void foedus::xct::CurrentLockList::release_all_after ( UniversalLockId  address, MCS_RW_IMPL *  mcs_rw_impl  )

inline

Release all locks in CLL whose addresses are canonically ordered before the parameter.

This is used where we need to rule out the risk of deadlock. Unlike clear_entries(), this leaves the entries.

Definition at line 753 of file retrospective_lock_list.hpp.

References assert_last_locked_entry(), ASSERT_ND, assert_sorted(), begin(), end(), foedus::xct::kLockListPositionInvalid, foedus::xct::kNoLock, foedus::xct::kReadLock, and foedus::xct::kWriteLock.

Referenced by foedus::thread::ThreadPimpl::cll_release_all_locks_after(), and release_all_locks().

                                                                                                {
  // Only this and below logics are implemented here because this needs to know about CLL.
  // This is not quite about the lock algorithm itself. It's something on higher level.
  assert_sorted();
  uint32_t released_read_locks = 0;
  uint32_t released_write_locks = 0;
  uint32_t already_released_locks = 0;
  uint32_t canceled_async_read_locks = 0;
  uint32_t canceled_async_write_locks = 0;

  LockListPosition new_last_locked_entry = kLockListPositionInvalid;
  for (LockEntry* entry = begin(); entry != end(); ++entry) {
    if (entry->universal_lock_id_ <= address) {
      if (entry->is_locked()) {
        new_last_locked_entry = entry - array_;
      }
      continue;
    }
    if (entry->is_locked()) {
      if (entry->taken_mode_ == kReadLock) {
        mcs_rw_impl->release_rw_reader(entry->lock_->get_key_lock(), entry->mcs_block_);
        ++released_read_locks;
      } else {
        ASSERT_ND(entry->taken_mode_ == kWriteLock);
        mcs_rw_impl->release_rw_writer(entry->lock_->get_key_lock(), entry->mcs_block_);
        ++released_write_locks;
      }
      entry->mcs_block_ = 0;
      entry->taken_mode_ = kNoLock;
    } else if (entry->mcs_block_) {
      // Not locked yet, but we have mcs_block_ set, this means we tried it in
      // async mode, then still waiting or at least haven't confirmed that we acquired it.
      // Cancel these "retrieable" locks to which we already pushed our qnode.
      ASSERT_ND(entry->taken_mode_ == kNoLock);
      if (entry->preferred_mode_ == kReadLock) {
        mcs_rw_impl->cancel_async_rw_reader(entry->lock_->get_key_lock(), entry->mcs_block_);
        ++canceled_async_read_locks;
      } else {
        ASSERT_ND(entry->preferred_mode_ == kWriteLock);
        mcs_rw_impl->cancel_async_rw_writer(entry->lock_->get_key_lock(), entry->mcs_block_);
        ++canceled_async_write_locks;
      }
      entry->mcs_block_ = 0;
    } else {
      ASSERT_ND(entry->taken_mode_ == kNoLock);
      ++already_released_locks;
    }
  }

  last_locked_entry_ = new_last_locked_entry;
  assert_last_locked_entry();

#ifndef NDEBUG
  release_all_after_debuglog(
    released_read_locks,
    released_write_locks,
    already_released_locks,
    canceled_async_read_locks,
    canceled_async_write_locks);
#endif  // NDEBUG
}

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename MCS_RW_IMPL >

void foedus::xct::CurrentLockList::release_all_at_and_after ( UniversalLockId  address, MCS_RW_IMPL *  mcs_rw_impl  )

inline

same as release_all_after(address - 1)

Definition at line 815 of file retrospective_lock_list.hpp.

References foedus::xct::kNullUniversalLockId.

                            {
  if (address == kNullUniversalLockId) {
    release_all_after<MCS_RW_IMPL>(kNullUniversalLockId, mcs_rw_impl);
  } else {
    release_all_after<MCS_RW_IMPL>(address - 1U, mcs_rw_impl);
  }
}

template<typename MCS_RW_IMPL >

void foedus::xct::CurrentLockList::release_all_locks ( MCS_RW_IMPL *  mcs_rw_impl )

inline

• Release all locks in CLL

Definition at line 473 of file retrospective_lock_list.hpp.

References foedus::xct::kNullUniversalLockId, and release_all_after().

Referenced by foedus::thread::ThreadPimpl::cll_release_all_locks().

                                                          {
    release_all_after(kNullUniversalLockId, mcs_rw_impl);
  }

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename MCS_RW_IMPL >

bool foedus::xct::CurrentLockList::retry_async_single_lock ( LockListPosition  pos, MCS_RW_IMPL *  mcs_rw_impl  )

inline

Definition at line 696 of file retrospective_lock_list.hpp.

References assert_last_locked_entry(), ASSERT_ND, get_entry(), foedus::xct::RwLockableXctId::get_key_lock(), foedus::xct::LockEntry::is_enough(), foedus::xct::LockEntry::is_locked(), foedus::xct::kNoLock, foedus::xct::kReadLock, foedus::xct::kWriteLock, foedus::xct::LockEntry::lock_, foedus::xct::LockEntry::mcs_block_, foedus::xct::LockEntry::preferred_mode_, and foedus::xct::LockEntry::taken_mode_.

                            {
  LockEntry* lock_entry = get_entry(pos);
  // Must be not taken yet, and must have pushed a qnode to the lock queue
  ASSERT_ND(!lock_entry->is_enough());
  ASSERT_ND(lock_entry->taken_mode_ == kNoLock);
  ASSERT_ND(lock_entry->mcs_block_);
  ASSERT_ND(!lock_entry->is_locked());

  McsRwLock* lock_addr = lock_entry->lock_->get_key_lock();
  bool acquired = false;
  if (lock_entry->preferred_mode_ == kWriteLock) {
    acquired = mcs_rw_impl->retry_async_rw_writer(lock_addr, lock_entry->mcs_block_);
  } else {
    ASSERT_ND(lock_entry->preferred_mode_ == kReadLock);
    acquired = mcs_rw_impl->retry_async_rw_reader(lock_addr, lock_entry->mcs_block_);
  }
  if (acquired) {
    lock_entry->taken_mode_ = lock_entry->preferred_mode_;
    ASSERT_ND(lock_entry->is_locked());
    last_locked_entry_ = std::max(last_locked_entry_, pos);
    assert_last_locked_entry();
  }
  return acquired;
}

Here is the call graph for this function:

template<typename MCS_RW_IMPL >

void foedus::xct::CurrentLockList::try_async_multiple_locks ( LockListPosition  upto_pos, MCS_RW_IMPL *  mcs_rw_impl  )

inline

Definition at line 742 of file retrospective_lock_list.hpp.

References ASSERT_ND, foedus::xct::kLockListPositionInvalid, and try_async_single_lock().

                            {
  ASSERT_ND(upto_pos != kLockListPositionInvalid);
  ASSERT_ND(upto_pos <= last_active_entry_);
  for (LockListPosition pos = 1U; pos <= upto_pos; ++pos) {
    try_async_single_lock(pos, mcs_rw_impl);
  }
}

Here is the call graph for this function:

template<typename MCS_RW_IMPL >

void foedus::xct::CurrentLockList::try_async_single_lock ( LockListPosition  pos, MCS_RW_IMPL *  mcs_rw_impl  )

inline

Definition at line 649 of file retrospective_lock_list.hpp.

References foedus::xct::AcquireAsyncRet::acquired_, assert_last_locked_entry(), ASSERT_ND, foedus::xct::AcquireAsyncRet::block_index_, calculate_last_locked_entry_from(), get_entry(), foedus::xct::RwLockableXctId::get_key_lock(), foedus::xct::LockEntry::is_enough(), foedus::xct::kNoLock, foedus::xct::kReadLock, foedus::xct::kWriteLock, foedus::xct::LockEntry::lock_, foedus::xct::LockEntry::mcs_block_, foedus::xct::LockEntry::preferred_mode_, and foedus::xct::LockEntry::taken_mode_.

Referenced by try_async_multiple_locks().

                            {
  LockEntry* lock_entry = get_entry(pos);
  if (lock_entry->is_enough()) {
    return;
  }
  ASSERT_ND(lock_entry->taken_mode_ != kWriteLock);

  McsRwLock* lock_addr = lock_entry->lock_->get_key_lock();
  if (lock_entry->taken_mode_ != kNoLock) {
    ASSERT_ND(lock_entry->preferred_mode_ == kWriteLock);
    ASSERT_ND(lock_entry->taken_mode_ == kReadLock);
    ASSERT_ND(lock_entry->mcs_block_);
    // This is reader->writer upgrade.
    // We simply release read-lock first then take write-lock in this case.
    // In traditional 2PL, such an unlock-then-lock violates serializability,
    // but we guarantee serializability by read-verification anyways.
    // We can release any lock anytime.. great flexibility!
    mcs_rw_impl->release_rw_reader(lock_addr, lock_entry->mcs_block_);
    lock_entry->taken_mode_ = kNoLock;
    last_locked_entry_ = calculate_last_locked_entry_from(pos - 1U);
    assert_last_locked_entry();
  } else {
    // This function is for pushing the queue node in the extended rwlock.
    // Doomed if we already have a queue node.
    ASSERT_ND(lock_entry->mcs_block_ == 0);
  }

  // Don't really care canonical order here, just send out the request.
  AcquireAsyncRet async_ret;
  if (lock_entry->preferred_mode_ == kWriteLock) {
    async_ret = mcs_rw_impl->acquire_async_rw_writer(lock_addr);
  } else {
    ASSERT_ND(lock_entry->preferred_mode_ == kReadLock);
    async_ret = mcs_rw_impl->acquire_async_rw_reader(lock_addr);
  }
  ASSERT_ND(async_ret.block_index_);
  lock_entry->mcs_block_ = async_ret.block_index_;
  if (async_ret.acquired_) {
    lock_entry->taken_mode_ = lock_entry->preferred_mode_;
    ASSERT_ND(lock_entry->is_enough());
  }
  ASSERT_ND(lock_entry->mcs_block_);
}

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename MCS_RW_IMPL >

ErrorCode foedus::xct::CurrentLockList::try_or_acquire_multiple_locks ( LockListPosition  upto_pos, MCS_RW_IMPL *  mcs_rw_impl  )

inline

Acquire multiple locks up to the given position in canonical order.

This is invoked by the thread to keep itself in canonical mode. This method is unconditional, meaning waits forever until we acquire the locks. Hence, this method must be invoked when the thread is still in canonical mode. Otherwise, it risks deadlock.

Definition at line 636 of file retrospective_lock_list.hpp.

References ASSERT_ND, CHECK_ERROR_CODE, foedus::kErrorCodeOk, foedus::xct::kLockListPositionInvalid, and try_or_acquire_single_lock().

Referenced by foedus::thread::ThreadPimpl::cll_try_or_acquire_multiple_locks().

                            {
  ASSERT_ND(upto_pos != kLockListPositionInvalid);
  ASSERT_ND(upto_pos <= last_active_entry_);
  // Especially in this case, we probably should release locks after upto_pos first.
  for (LockListPosition pos = 1U; pos <= upto_pos; ++pos) {
    CHECK_ERROR_CODE(try_or_acquire_single_lock(pos, mcs_rw_impl));
  }
  return kErrorCodeOk;
}

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename MCS_RW_IMPL >

ErrorCode foedus::xct::CurrentLockList::try_or_acquire_single_lock ( LockListPosition  pos, MCS_RW_IMPL *  mcs_rw_impl  )

inline

Methods below take or release locks, so they receive MCS_RW_IMPL, a template param.

Inline definitions of CurrentLockList methods below.

To avoid vtable and allow inlining, we define them at the bottom of this file. Acquire one lock in this CLL.

This method automatically checks if we are following canonical mode, and acquire the lock unconditionally when in canonical mode (never returns until acquire), and try the lock instanteneously when not in canonical mode (returns RaceAbort immediately).

These are inlined primarily because they receive a template param, not because we want to inline for performance. We could do explicit instantiations, but not that lengthy, either. Just inlining them is easier in this case.

Definition at line 569 of file retrospective_lock_list.hpp.

References assert_last_locked_entry(), ASSERT_ND, calculate_last_locked_entry_from(), get_entry(), foedus::xct::RwLockableXctId::get_key_lock(), foedus::xct::LockEntry::is_enough(), foedus::xct::LockEntry::is_locked(), foedus::kErrorCodeOk, foedus::kErrorCodeXctLockAbort, foedus::xct::kLockListPositionInvalid, foedus::xct::kNoLock, foedus::xct::kReadLock, foedus::xct::kWriteLock, foedus::xct::LockEntry::lock_, foedus::xct::LockEntry::mcs_block_, foedus::xct::LockEntry::preferred_mode_, and foedus::xct::LockEntry::taken_mode_.

Referenced by foedus::thread::ThreadPimpl::cll_try_or_acquire_single_lock(), and try_or_acquire_multiple_locks().

                            {
  LockEntry* lock_entry = get_entry(pos);
  if (lock_entry->is_enough()) {
    return kErrorCodeOk;
  }
  ASSERT_ND(lock_entry->taken_mode_ != kWriteLock);

  McsRwLock* lock_addr = lock_entry->lock_->get_key_lock();
  if (lock_entry->taken_mode_ != kNoLock) {
    ASSERT_ND(lock_entry->preferred_mode_ == kWriteLock);
    ASSERT_ND(lock_entry->taken_mode_ == kReadLock);
    ASSERT_ND(lock_entry->mcs_block_);
    // This is reader->writer upgrade.
    // We simply release read-lock first then take write-lock in this case.
    // In traditional 2PL, such an unlock-then-lock violates serializability,
    // but we guarantee serializability by read-verification anyways.
    // We can release any lock anytime.. great flexibility!
    mcs_rw_impl->release_rw_reader(lock_addr, lock_entry->mcs_block_);
    lock_entry->taken_mode_ = kNoLock;
    last_locked_entry_ = calculate_last_locked_entry_from(pos - 1U);
    assert_last_locked_entry();
  } else {
    // This method is for unconditional acquire and try, not aync/retry.
    // If we have a queue node already, something was misused.
    ASSERT_ND(lock_entry->mcs_block_ == 0);
  }

  // Now we need to take the lock. Are we in canonical mode?
  if (last_locked_entry_ == kLockListPositionInvalid || last_locked_entry_ < pos) {
    // yay, we are in canonical mode. we can unconditionally get the lock
    ASSERT_ND(lock_entry->taken_mode_ == kNoLock);  // not a lock upgrade, either
    if (lock_entry->preferred_mode_ == kWriteLock) {
      lock_entry->mcs_block_ = mcs_rw_impl->acquire_unconditional_rw_writer(lock_addr);
    } else {
      ASSERT_ND(lock_entry->preferred_mode_ == kReadLock);
      lock_entry->mcs_block_ = mcs_rw_impl->acquire_unconditional_rw_reader(lock_addr);
    }
    lock_entry->taken_mode_ = lock_entry->preferred_mode_;
    last_locked_entry_ = pos;
  } else {
    // hmm, we violated canonical mode. has a risk of deadlock.
    // Let's just try acquire the lock and immediately give up if it fails.
    // The RLL will take care of the next run.
    // TODO(Hideaki) release some of the lock we have taken to restore canonical mode.
    // We haven't imlpemented this optimization yet.
    ASSERT_ND(lock_entry->mcs_block_ == 0);
    ASSERT_ND(lock_entry->taken_mode_ == kNoLock);
    if (lock_entry->preferred_mode_ == kWriteLock) {
      lock_entry->mcs_block_ = mcs_rw_impl->acquire_try_rw_writer(lock_addr);
    } else {
      ASSERT_ND(lock_entry->preferred_mode_ == kReadLock);
      lock_entry->mcs_block_ = mcs_rw_impl->acquire_try_rw_reader(lock_addr);
    }
    if (lock_entry->mcs_block_ == 0) {
      return kErrorCodeXctLockAbort;
    }
    lock_entry->taken_mode_ = lock_entry->preferred_mode_;
  }
  ASSERT_ND(lock_entry->mcs_block_);
  ASSERT_ND(lock_entry->is_locked());
  assert_last_locked_entry();
  return kErrorCodeOk;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void foedus::xct::CurrentLockList::uninit

(

)

Definition at line 109 of file retrospective_lock_list.cpp.

References clear_entries().

Referenced by ~CurrentLockList().

                             {
  array_ = nullptr;
  capacity_ = 0;
  clear_entries();
}

Here is the call graph for this function:

Here is the caller graph for this function:

Friends And Related Function Documentation

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

friend

Definition at line 132 of file retrospective_lock_list.cpp.

                                                                {
  o << "<CurrentLockList>"
    << "<Capacity>" << v.capacity_ << "</Capacity>"
    << "<LastActiveEntry>" << v.last_active_entry_ << "</LastActiveEntry>"
    << "<LastLockedEntry>" << v.last_locked_entry_ << "</LastLockedEntry>";
  const uint32_t kMaxShown = 32U;
  for (auto i = 1U; i <= std::min(v.last_active_entry_, kMaxShown); ++i) {
    o << v.array_[i];
  }
  o << "</CurrentLockList>";
  return o;
}

---

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

• /home/shino/foedus_code/foedus-core/include/foedus/xct/retrospective_lock_list.hpp
• /home/shino/foedus_code/foedus-core/src/foedus/xct/retrospective_lock_list.cpp