foedus::xct::RetrospectiveLockList Class Reference

Retrospective lock list. More...

Detailed Description

Retrospective lock list.

This is NOT a POD because we need dynamic memory for the list.

Note

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

Definition at line 189 of file retrospective_lock_list.hpp.

#include <retrospective_lock_list.hpp>

Public Member Functions
	RetrospectiveLockList ()
	Init/Uninit. More...
	~RetrospectiveLockList ()
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	lower_bound (UniversalLockId lock) const
	Analogous to std::lower_bound() for the given lock. More...
void	construct (thread::Thread *context, uint32_t read_lock_threshold)
	Fill out this retrospetive lock list for the next run of the given transaction. More...
const LockEntry *	get_array () const
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

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

Constructor & Destructor Documentation

foedus::xct::RetrospectiveLockList::RetrospectiveLockList

(

)

Init/Uninit.

Definition at line 39 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::RetrospectiveLockList::~RetrospectiveLockList

(

)

Definition at line 45 of file retrospective_lock_list.cpp.

References uninit().

                                              {
  uninit();
}

Here is the call graph for this function:

Member Function Documentation

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

inline

Definition at line 548 of file retrospective_lock_list.hpp.

References assert_sorted_impl().

Referenced by construct(), and foedus::xct::CurrentLockList::prepopulate_for_retrospective_lock_list().

                                                       {
  // In release mode, this code must be completely erased by compiler
#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::RetrospectiveLockList::assert_sorted_impl

(

)

const

Definition at line 182 of file retrospective_lock_list.cpp.

References foedus::xct::lock_assert_sorted().

Referenced by assert_sorted().

                                                     {
  lock_assert_sorted(*this);
}

Here is the call graph for this function:

Here is the caller graph for this function:

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

inline

Definition at line 254 of file retrospective_lock_list.hpp.

{ return array_ + 1U; }

LockListPosition foedus::xct::RetrospectiveLockList::binary_search

(

UniversalLockId

lock

)

const

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

Returns

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

Definition at line 193 of file retrospective_lock_list.cpp.

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

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

Here is the caller graph for this function:

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

inline

Definition at line 256 of file retrospective_lock_list.hpp.

{ return array_ + 1U; }

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

inline

Definition at line 257 of file retrospective_lock_list.hpp.

{ return array_ + 1U + last_active_entry_; }

void foedus::xct::RetrospectiveLockList::clear_entries

(

)

Definition at line 59 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::XctManagerPimpl::abort_xct(), init(), foedus::xct::Xct::on_record_read_take_locks_if_needed(), foedus::xct::XctManagerPimpl::precommit_xct(), RetrospectiveLockList(), and uninit().

                                          {
  last_active_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:

void foedus::xct::RetrospectiveLockList::construct	(	thread::Thread *	context,
		uint32_t	read_lock_threshold
	)

Fill out this retrospetive lock list for the next run of the given transaction.

Parameters

[in]	context	the thread conveying the transaction. must be currently running a xct
[in]	read_lock_threshold	we "recommend" a read lock in RLL for records whose page have this value or more in the temperature-stat. This value should be a bit lower than the threshold we trigger read-locks without RLL. Otherwise, the next run might often take a read-lock the RLL discarded due to a concurrent abort, which might violate canonical order.

This method is invoked when a transaction aborts at precommit due to some conflict. Based on the current transaction's read/write-sets, this builds an RLL that contains locks we probably should take next time in a canonical order.

Note

we should keep an eye on the CPU cost of this method. Hopefully negligible. We can speed up this method by merging RLL/CLL to read/write-set in xct so that we don't need another sorting.

Definition at line 252 of file retrospective_lock_list.cpp.

References ASSERT_ND, assert_sorted(), foedus::thread::Thread::get_current_xct(), foedus::storage::Page::get_header(), foedus::xct::Xct::get_read_set(), foedus::xct::Xct::get_read_set_size(), foedus::xct::Xct::get_write_set(), foedus::xct::Xct::get_write_set_size(), foedus::storage::PageHeader::hotness_, foedus::xct::Xct::is_active(), foedus::xct::kLockListPositionInvalid, foedus::xct::kNoLock, foedus::xct::kReadLock, foedus::xct::kWriteLock, foedus::xct::LockEntry::preferred_mode_, foedus::xct::LockEntry::set(), foedus::storage::to_page(), foedus::assorted::ProbCounter::value_, foedus::xct::RwLockableXctId::xct_id_, and foedus::xct::xct_id_to_universal_lock_id().

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

                                                                                         {
  Xct* xct = &context->get_current_xct();
  ASSERT_ND(xct->is_active());
  // We currently hold read/write-set separately. So, we need to sort and merge them.
  ReadXctAccess* read_set = xct->get_read_set();
  const uint32_t read_set_size = xct->get_read_set_size();
  WriteXctAccess* write_set = xct->get_write_set();
  const uint32_t write_set_size = xct->get_write_set_size();
  ASSERT_ND(capacity_ >= read_set_size + write_set_size);

  last_active_entry_ = kLockListPositionInvalid;
  if (read_set_size == 0 && write_set_size == 0) {
    return;
  }

  for (uint32_t i = 0; i < read_set_size; ++i) {
    RwLockableXctId* lock = read_set[i].owner_id_address_;
    storage::Page* page = storage::to_page(lock);
    if (page->get_header().hotness_.value_ < read_lock_threshold
      && lock->xct_id_ == read_set[i].observed_owner_id_) {
      // We also add it to RLL whenever we observed a verification error.
      continue;
    }

    auto pos = issue_new_position();
    ASSERT_ND(
      read_set[i].owner_lock_id_ ==
      xct_id_to_universal_lock_id(volatile_page_resolver_, lock));
    array_[pos].set(read_set[i].owner_lock_id_, lock, kReadLock, kNoLock);
  }
  DVLOG(1) << "Added " << last_active_entry_ << " to RLL for read-locks";

  // Writes are always added to RLL.
  for (uint32_t i = 0; i < write_set_size; ++i) {
    auto pos = issue_new_position();
    ASSERT_ND(
      write_set[i].owner_lock_id_ ==
      xct_id_to_universal_lock_id(volatile_page_resolver_, write_set[i].owner_id_address_));
    array_[pos].set(
      write_set[i].owner_lock_id_,
      write_set[i].owner_id_address_,
      kWriteLock,
      kNoLock);
  }

  // Now, the entries are not sorted and we might have duplicates.
  // Sort them, and merge entries for the same record.
  // std::set? no joke. we can't afford heap allocation here.
  ASSERT_ND(last_active_entry_ != kLockListPositionInvalid);
  std::sort(array_ + 1U, array_ + last_active_entry_ + 1U);
  LockListPosition prev_pos = 1U;
  uint32_t merged_count = 0U;
  for (LockListPosition pos = 2U; pos <= last_active_entry_; ++pos) {
    ASSERT_ND(prev_pos < pos);
    ASSERT_ND(array_[prev_pos].universal_lock_id_ <= array_[pos].universal_lock_id_);
    if (array_[prev_pos].universal_lock_id_ == array_[pos].universal_lock_id_) {
      // Merge!
      if (array_[pos].preferred_mode_ == kWriteLock) {
        array_[prev_pos].preferred_mode_ = kWriteLock;
      }
      ++merged_count;
    } else {
      // No merge.
      if (prev_pos + 1U < pos) {
        std::memcpy(array_ + prev_pos + 1U, array_ + pos, sizeof(LockEntry));
      }
      ++prev_pos;
    }
  }

  // For example, last_active_entry_ was 3 (0=Dummy, 1=A, 2=A, 3=B),
  // prev_pos becomes 2 while merged count is 1.
  ASSERT_ND(prev_pos + merged_count == last_active_entry_);
  last_active_entry_ = prev_pos;
  assert_sorted();
}

Here is the call graph for this function:

Here is the caller graph for this function:

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

inline

Definition at line 255 of file retrospective_lock_list.hpp.

{ return array_ + 1U + last_active_entry_; }

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

inline

Definition at line 234 of file retrospective_lock_list.hpp.

Referenced by foedus::xct::Xct::on_record_read_take_locks_if_needed(), and foedus::xct::CurrentLockList::prepopulate_for_retrospective_lock_list().

{ return array_; }

Here is the caller graph for this function:

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

inline

Definition at line 243 of file retrospective_lock_list.hpp.

{ return capacity_; }

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

inline

Definition at line 235 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:

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

inline

Definition at line 239 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::RetrospectiveLockList::get_last_active_entry ( ) const

inline

Definition at line 244 of file retrospective_lock_list.hpp.

Referenced by foedus::xct::XctManagerPimpl::begin_xct(), and foedus::xct::CurrentLockList::prepopulate_for_retrospective_lock_list().

{ return last_active_entry_; }

Here is the caller graph for this function:

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

inline

Definition at line 258 of file retrospective_lock_list.hpp.

Referenced by foedus::xct::Xct::add_to_read_set(), and foedus::xct::Xct::add_to_write_set().

                                                                             {
    return volatile_page_resolver_;
  }

Here is the caller graph for this function:

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

Definition at line 49 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::RetrospectiveLockList::is_empty ( ) const

inline

Definition at line 248 of file retrospective_lock_list.hpp.

References foedus::xct::kLockListPositionInvalid.

Referenced by foedus::xct::Xct::activate(), foedus::xct::Xct::on_record_read_take_locks_if_needed(), and foedus::xct::CurrentLockList::prepopulate_for_retrospective_lock_list().

{ return last_active_entry_ == kLockListPositionInvalid; }

Here is the caller graph for this function:

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

inline

Definition at line 245 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::RetrospectiveLockList::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 200 of file retrospective_lock_list.cpp.

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

void foedus::xct::RetrospectiveLockList::uninit

(

)

Definition at line 70 of file retrospective_lock_list.cpp.

References clear_entries().

Referenced by ~RetrospectiveLockList().

                                   {
  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 RetrospectiveLockList &  v  )

friend

Definition at line 145 of file retrospective_lock_list.cpp.

                                                                      {
  o << "<RetrospectiveLockList>"
    << "<Capacity>" << v.capacity_ << "</Capacity>"
    << "<LastActiveEntry>" << v.last_active_entry_ << "</LastActiveEntry>";
  const uint32_t kMaxShown = 32U;
  for (auto i = 1U; i <= std::min(v.last_active_entry_, kMaxShown); ++i) {
    o << v.array_[i];
  }
  o << "</RetrospectiveLockList>";
  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