A system transaction to adopt foster twins into an intermediate page. More...

Detailed Description

A system transaction to adopt foster twins into an intermediate page.

See also: Physical-only, short-living system transactions.

This system transaction follows page-splits, which leave foster twins. The sysxct replaces an existing separator and pointer to the old-page with two new separators and pointers to the grandchildren. The parent-page thus need a room for one more separator/pointer, which might require page split.

There are following cases:

Case-A – Easies/fastest case. One of the grandchildren is an empty-range page. We simply discard such a page, thus we just replace the old pointer in parent page with a pointer to the non-empty grandchild.
Case-B – Normal cases. The grandchildren are not empty. When the pointer to old-page is the last entry of a non-full minipage in parent page, we can append at last of minipage. The same applies to the case where the pointer is the last entry of a full minipage that is the last minipage in a non-full parent page. Otherwise, we have to split the parent page (see below).

The caller of this sysxct reads and follows pointers without page-latch or fences because reads/traversals must be lock-free and as efficient as possible. This sysxct must make sure we are replacing the right pointer with adopted pointer(s).

This does nothing and returns kErrorCodeOk in the following cases:

The parent page turns out to be moved.
The old page turns out to be retired (already adopted).

Locks taken in this sysxct:

Page-lock of the parent page and old page (will be retied).

So far this sysxct adopts only one child at a time. TASK(Hideaki): Probably it helps by delaying and batching several adoptions.

See also: SplitIntermediate

Definition at line 67 of file masstree_adopt_impl.hpp.

#include <masstree_adopt_impl.hpp>

Inheritance diagram for foedus::storage::masstree::Adopt:

[legend]

Collaboration diagram for foedus::storage::masstree::Adopt:

[legend]

Public Member Functions
	Adopt (thread::Thread context, MasstreeIntermediatePage parent, MasstreePage *old)

virtual ErrorCode	run (xct::SysxctWorkspace *sysxct_workspace) override
	Execute the system transaction. More...

ErrorCode	adopt_case_a (uint16_t minipage_index, uint16_t pointer_index)

ErrorCode	adopt_case_b (uint16_t minipage_index, uint16_t pointer_index)

Public Attributes
thread::Thread *const	context_
	Thread context. More...

MasstreeIntermediatePage *const	parent_
	The parent page that currently points to the old page. More...

MasstreePage *const	old_
	The old page that was split, whose foster-twins are being adopted. More...

Constructor & Destructor Documentation

foedus::storage::masstree::Adopt::Adopt	(	thread::Thread *	context,
		MasstreeIntermediatePage *	parent,
		MasstreePage *	old
	)

inline

Definition at line 78 of file masstree_adopt_impl.hpp.

     : xct::SysxctFunctor(),
       context_(context),
       parent_(parent),
       old_(old) {
   }

Member Function Documentation

ErrorCode foedus::storage::masstree::Adopt::adopt_case_a	(	uint16_t	minipage_index,
		uint16_t	pointer_index
	)

Definition at line 73 of file masstree_adopt_impl.cpp.

Referenced by run().

                           {
   VLOG(0) << "Adopting from a child page that contains an empty-range page. This happens when"
     << " record compaction/expansion created a page without a record.";
 
   MasstreePage* grandchild_minor = context_->resolve_cast<MasstreePage>(old_->get_foster_minor());
   ASSERT_ND(grandchild_minor->get_low_fence() == old_->get_low_fence());
   ASSERT_ND(grandchild_minor->get_high_fence() == old_->get_foster_fence());
   MasstreePage* grandchild_major = context_->resolve_cast<MasstreePage>(old_->get_foster_major());
   ASSERT_ND(grandchild_major->get_low_fence() == old_->get_foster_fence());
   ASSERT_ND(grandchild_major->get_high_fence() == old_->get_high_fence());
   ASSERT_ND(!grandchild_minor->header().snapshot_);
   ASSERT_ND(!grandchild_major->header().snapshot_);
 
   ASSERT_ND(grandchild_minor->is_empty_range() != grandchild_major->is_empty_range());
 
   VolatilePagePointer nonempty_grandchild_pointer;
   MasstreePage* empty_grandchild = nullptr;
   MasstreePage* nonempty_grandchild = nullptr;
   if (grandchild_minor->is_empty_range()) {
     empty_grandchild = grandchild_minor;
     nonempty_grandchild = grandchild_major;
   } else {
     empty_grandchild = grandchild_major;
     nonempty_grandchild = grandchild_minor;
   }
 
   auto& minipage = parent_->get_minipage(minipage_index);
   ASSERT_ND(old_->get_volatile_page_id() == minipage.pointers_[pointer_index].volatile_pointer_);
   minipage.pointers_[pointer_index].snapshot_pointer_ = 0;
   minipage.pointers_[pointer_index].volatile_pointer_ = nonempty_grandchild->get_volatile_page_id();
 
   // The only thread that might be retiring this empty page must be in this function,
   // holding a page-lock in scope_child. Thus we don't need a lock in empty_grandchild.
   ASSERT_ND(!empty_grandchild->is_locked());  // none else holding lock on it
   // and we can safely retire the page. We do not use set_retired because is_moved() is false
   // It's a special retirement path.
   empty_grandchild->get_version_address()->status_.status_ |= PageVersionStatus::kRetiredBit;
   context_->collect_retired_volatile_page(empty_grandchild->get_volatile_page_id());
   old_->set_retired();
   context_->collect_retired_volatile_page(old_->get_volatile_page_id());
   return kErrorCodeOk;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ErrorCode foedus::storage::masstree::Adopt::adopt_case_b	(	uint16_t	minipage_index,
		uint16_t	pointer_index
	)

Definition at line 118 of file masstree_adopt_impl.cpp.

Referenced by run().

                           {
   const auto key_count = parent_->get_key_count();
   const KeySlice new_separator = old_->get_foster_fence();
   const VolatilePagePointer minor_pointer = old_->get_foster_minor();
   const VolatilePagePointer major_pointer = old_->get_foster_major();
   auto& minipage = parent_->get_minipage(minipage_index);
   ASSERT_ND(old_->get_volatile_page_id() == minipage.pointers_[pointer_index].volatile_pointer_);
 
   // Can we simply append the new pointer either as a new minipage at the end of this page
   // or as a new separator at the end of a minipage? Then we don't need major change.
   // We simply append without any change, which is easy to make right.
   if (minipage.key_count_ == pointer_index) {
     if (minipage.key_count_ < kMaxIntermediateMiniSeparators) {
       // We can append a new separator at the end of the minipage.
       ASSERT_ND(!minipage.pointers_[pointer_index].is_both_null());
       ASSERT_ND(pointer_index == 0 || minipage.separators_[pointer_index - 1] < new_separator);
       minipage.separators_[pointer_index] = new_separator;
       minipage.pointers_[pointer_index + 1].snapshot_pointer_ = 0;
       minipage.pointers_[pointer_index + 1].volatile_pointer_ = major_pointer;
 
       // we don't have to adopt the foster-minor because that's the child page itself,
       // but we have to switch the pointer
       minipage.pointers_[pointer_index].snapshot_pointer_ = 0;
       minipage.pointers_[pointer_index].volatile_pointer_ = minor_pointer;
 
       // we increase key count after above, with fence, so that concurrent transactions
       // never see an empty slot.
       assorted::memory_fence_release();
       ++minipage.key_count_;
       ASSERT_ND(minipage.key_count_ <= kMaxIntermediateMiniSeparators);
 
       old_->set_retired();
       context_->collect_retired_volatile_page(old_->get_volatile_page_id());
       return kErrorCodeOk;
     } else if (key_count == minipage_index && key_count < kMaxIntermediateSeparators) {
       // The minipage is full.. and the minipage is the last one!
       // We can add it as a new minipage
       auto& new_minipage = parent_->get_minipage(minipage_index + 1);
       new_minipage.key_count_ = 0;
 
 #ifndef NDEBUG
       // for ease of debugging zero-out the page first (only data part). only for debug build.
       for (uint8_t j = 0; j <= kMaxIntermediateMiniSeparators; ++j) {
         if (j < kMaxIntermediateMiniSeparators) {
           new_minipage.separators_[j] = 0;
         }
         new_minipage.pointers_[j].snapshot_pointer_ = 0;
         new_minipage.pointers_[j].volatile_pointer_.word = 0;
       }
 #endif  // NDEBUG
 
       ASSERT_ND(new_minipage.key_count_ == 0);
       new_minipage.pointers_[0].snapshot_pointer_ = 0;
       new_minipage.pointers_[0].volatile_pointer_ = major_pointer;
 
       // also handle foster-twin if it's border page
       DualPagePointer& old_pointer = minipage.pointers_[minipage.key_count_];
       old_pointer.snapshot_pointer_ = 0;
       old_pointer.volatile_pointer_ = minor_pointer;
 
       parent_->set_separator(minipage_index, new_separator);
 
       // increment key count after all with fence so that concurrent transactions never see
       // a minipage that is not ready for read
       assorted::memory_fence_release();
       parent_->increment_key_count();
       ASSERT_ND(parent_->get_key_count() == minipage_index + 1);
 
       old_->set_retired();
       context_->collect_retired_volatile_page(old_->get_volatile_page_id());
       return kErrorCodeOk;
     }
   }
 
   // In all other cases, we split this page.
   // We initially had more complex code to do in-page rebalance and
   // in-minipage "shifting", but got some bugs. Pulled out too many hairs.
   // Let's keep it simple. If we really observe bottleneck here, we can reconsider.
   // Splitting is way more robust because it changes nothing in this existing page.
   // It just places new foster-twin pointers.
 
   // Reuse SplitIntermediate. We are directly invoking the sysxct's internal logic
   // rather than nesting sysxct.
   memory::PagePoolOffset offsets[2];
   thread::GrabFreeVolatilePagesScope free_pages_scope(context_, offsets);
   CHECK_ERROR_CODE(free_pages_scope.grab(2));
   SplitIntermediate split(context_, parent_, old_);
   split.split_impl_no_error(&free_pages_scope);
   ASSERT_ND(old_->is_retired());  // the above internally retires old page
   return kErrorCodeOk;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ErrorCode foedus::storage::masstree::Adopt::run ( xct::SysxctWorkspace * sysxct_workspace )

overridevirtual

Execute the system transaction.

You should override this method.

Implements foedus::xct::SysxctFunctor.

Definition at line 32 of file masstree_adopt_impl.cpp.

                                                          {
   ASSERT_ND(!parent_->header().snapshot_);
   ASSERT_ND(!old_->header().snapshot_);
   ASSERT_ND(old_->is_moved());  // this is guaranteed because these flag are immutable once set.
 
   // Lock pages in one shot.
   Page* pages[2];
   pages[0] = reinterpret_cast<Page*>(parent_);
   pages[1] = reinterpret_cast<Page*>(old_);
   CHECK_ERROR_CODE(context_->sysxct_batch_page_locks(sysxct_workspace, 2, pages));
 
   // After the above lock, we check status of the pages
   if (parent_->is_moved()) {
     VLOG(0) << "Interesting. concurrent thread has already split this node?";
     return kErrorCodeOk;
   } else if (old_->is_retired()) {
     VLOG(0) << "Interesting. concurrent thread already adopted.";
     return kErrorCodeOk;
   }
 
   const KeySlice searching_slice = old_->get_low_fence();
   const auto minipage_index = parent_->find_minipage(searching_slice);
   auto& minipage = parent_->get_minipage(minipage_index);
   const auto pointer_index = minipage.find_pointer(searching_slice);
   ASSERT_ND(minipage.key_count_ <= kMaxIntermediateMiniSeparators);
   ASSERT_ND(old_->get_volatile_page_id() == minipage.pointers_[pointer_index].volatile_pointer_);
 
   // Now, how do we accommodate the new pointer?
   if (old_->get_foster_fence() == old_->get_low_fence()
     || old_->get_foster_fence() == old_->get_high_fence()) {
     // Case A. One of the grandchildrens is empty-range
     CHECK_ERROR_CODE(adopt_case_a(minipage_index, pointer_index));
   } else {
     // Case B. More complex, normal case
     CHECK_ERROR_CODE(adopt_case_b(minipage_index, pointer_index));
   }
 
   parent_->verify_separators();
   return kErrorCodeOk;
 }

Here is the call graph for this function:

Member Data Documentation

thread::Thread* const foedus::storage::masstree::Adopt::context_

Thread context.

Definition at line 69 of file masstree_adopt_impl.hpp.

Referenced by adopt_case_a(), adopt_case_b(), and run().

MasstreePage* const foedus::storage::masstree::Adopt::old_

The old page that was split, whose foster-twins are being adopted.

Precondition: old_->is_moved()

Definition at line 76 of file masstree_adopt_impl.hpp.

Referenced by adopt_case_a(), adopt_case_b(), and run().

MasstreeIntermediatePage* const foedus::storage::masstree::Adopt::parent_

The parent page that currently points to the old page.

Definition at line 71 of file masstree_adopt_impl.hpp.

Referenced by adopt_case_a(), adopt_case_b(), and run().

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

/home/shino/foedus_code/foedus-core/include/foedus/storage/masstree/masstree_adopt_impl.hpp
/home/shino/foedus_code/foedus-core/src/foedus/storage/masstree/masstree_adopt_impl.cpp

Detailed Description

Public Member Functions

Public Attributes

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation