A system transaction to split an intermediate page in Master-Tree. More...

Detailed Description

A system transaction to split an intermediate page in Master-Tree.

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

Same as border page split.

This does nothing and returns kErrorCodeOk in the following cases:

The page turns out to be already split.
piggyback_adopt_child_ turns out to be already retired (meaning already adopted)

Locks taken in this sysxct (in order of taking):

Page-lock of the target page, and piggyback_adopt_child_ if piggyback_adopt_child_ is non-null. We lock target/piggyback_adopt_child_ in canonical order.

Obviously no chance of deadlocks or even any conditional locks after releasing enclosing user transaction's locks. max_retries=2 should be enough in run_nested_sysxct().

Definition at line 158 of file masstree_split_impl.hpp.

#include <masstree_split_impl.hpp>

Inheritance diagram for foedus::storage::masstree::SplitIntermediate:

[legend]

Collaboration diagram for foedus::storage::masstree::SplitIntermediate:

[legend]

Classes
struct	SplitStrategy
	Constructed by hierarchically reading all separators and pointers in old page. More...

Public Member Functions
	SplitIntermediate (thread::Thread context, MasstreeIntermediatePage target, MasstreePage *piggyback_adopt_child=nullptr)

virtual ErrorCode	run (xct::SysxctWorkspace *sysxct_workspace) override
	Interior node's Split. More...

void	split_impl_no_error (thread::GrabFreeVolatilePagesScope *free_pages)
	The core implementation after locking relevant pages and acquiring free page resource. More...

void	decide_strategy (SplitStrategy *out) const
	Subroutine to decide how we will split this page. More...

void	migrate_pointers (const SplitStrategy &strategy, uint16_t from, uint16_t to, KeySlice expected_last_separator, MasstreeIntermediatePage *dest) const
	Subroutine to construct a new page. More...

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

MasstreeIntermediatePage *const	target_
	The page to split. More...

MasstreePage *const	piggyback_adopt_child_
	An optimization for the common case: splitting the parent page to adopt foster twins of a child page. More...

Constructor & Destructor Documentation

foedus::storage::masstree::SplitIntermediate::SplitIntermediate	(	thread::Thread *	context,
		MasstreeIntermediatePage *	target,
		MasstreePage *	piggyback_adopt_child = `nullptr`
	)

inline

Definition at line 179 of file masstree_split_impl.hpp.

     : xct::SysxctFunctor(),
       context_(context),
       target_(target),
       piggyback_adopt_child_(piggyback_adopt_child) {
   }

Member Function Documentation

void foedus::storage::masstree::SplitIntermediate::decide_strategy ( SplitIntermediate::SplitStrategy * out ) const

Subroutine to decide how we will split this page.

Definition at line 552 of file masstree_split_impl.cpp.

Referenced by split_impl_no_error().

                                                                                  {
   ASSERT_ND(target_->is_locked());
   out->compact_adopt_ = false;
   out->total_separator_count_ = 0;
 
   // While collecting pointers from the old page, we look for the piggyback_adopt_child_
   // and replace it with new pointers (so, this increases the total # of separators).
   KeySlice old_separator = 0;
   KeySlice new_separator = 0;
   VolatilePagePointer old_pointer;
   if (piggyback_adopt_child_) {
     ASSERT_ND(piggyback_adopt_child_->is_moved());
     old_separator = piggyback_adopt_child_->get_low_fence();
     new_separator = piggyback_adopt_child_->get_foster_fence();
     old_pointer = VolatilePagePointer(piggyback_adopt_child_->header().page_id_);
   }
 
   bool found_old = false;
   for (MasstreeIntermediatePointerIterator iter(target_); iter.is_valid(); iter.next()) {
     const KeySlice low = iter.get_low_key();
     const KeySlice high = iter.get_high_key();
     const DualPagePointer& pointer = iter.get_pointer();
     if (piggyback_adopt_child_ && low == old_separator) {
       // Found the existing pointer to replace with foster-minor
       ASSERT_ND(pointer.volatile_pointer_.is_equivalent(old_pointer));
       ASSERT_ND(high == piggyback_adopt_child_->get_high_fence());
       out->separators_[out->total_separator_count_] = new_separator;
       out->pointers_[out->total_separator_count_].volatile_pointer_
         = piggyback_adopt_child_->get_foster_minor();
       out->pointers_[out->total_separator_count_].snapshot_pointer_ = 0;
       ++(out->total_separator_count_);
 
       // Also add foster-major as a new entry
       out->separators_[out->total_separator_count_] = high;
       out->pointers_[out->total_separator_count_].volatile_pointer_
         = piggyback_adopt_child_->get_foster_major();
       out->pointers_[out->total_separator_count_].snapshot_pointer_ = 0;
       ++(out->total_separator_count_);
       found_old = true;
     } else {
       out->separators_[out->total_separator_count_] = high;
       out->pointers_[out->total_separator_count_] = pointer;
       ++(out->total_separator_count_);
     }
     ASSERT_ND(piggyback_adopt_child_ == nullptr || low < old_separator || found_old);
   }
 
   ASSERT_ND(piggyback_adopt_child_ == nullptr || found_old);
   ASSERT_ND(out->total_separator_count_ >= 2U);
   ASSERT_ND(out->total_separator_count_ <= kMaxIntermediatePointers + 1U);
 
   if (out->total_separator_count_ <= kMaxIntermediatePointers) {
     // Then, compact_adopt:
     // we create a dummy foster with empty
     // range on right side, and just re-structures target page onto left foster twin.
     // In other words, this is compaction/restructure that is done in another page in RCU fashion.
     out->compact_adopt_ = true;
     out->mid_index_ = out->total_separator_count_ - 1U;
     out->mid_separator_ = target_->get_high_fence();
   } else if (piggyback_adopt_child_
     && piggyback_adopt_child_->get_foster_major()
         == out->pointers_[out->total_separator_count_ - 1].volatile_pointer_) {
     DVLOG(0) << "Seems like a sequential insert. let's do no-record split";
     out->mid_index_ = out->total_separator_count_ - 2U;
     out->mid_separator_ = out->separators_[out->mid_index_];
   } else {
     // Usual: otherwise, we split them into 50-50 distribution.
     out->mid_index_ = (out->total_separator_count_ - 1U) / 2;
     out->mid_separator_ = out->separators_[out->mid_index_];
   }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void foedus::storage::masstree::SplitIntermediate::migrate_pointers	(	const SplitStrategy &	strategy,
		uint16_t	from,
		uint16_t	to,
		KeySlice	expected_last_separator,
		MasstreeIntermediatePage *	dest
	)		const

Subroutine to construct a new page.

Definition at line 624 of file masstree_split_impl.cpp.

Referenced by split_impl_no_error().

                                         {
   // construct dest page. copy the separators and pointers.
   // we distribute them as much as possible in first level. if mini pages have little
   // entries to start with, following adoption would be only local.
   float entries_per_mini = static_cast<float>(to - from) / (kMaxIntermediateSeparators + 1);
   ASSERT_ND(to > from);
   const uint16_t move_count = to - from;
 
   // it looks a bit complicated because each separator is "one-off" due to first-level separator.
   // so we buffer one separator.
   float next_mini_threshold = entries_per_mini;
   uint8_t cur_mini = 0;
   uint8_t cur_mini_separators = 0;
   auto* cur_mini_page = &dest->get_minipage(0);
   cur_mini_page->pointers_[0] = strategy.pointers_[from];
   ASSERT_ND(!strategy.pointers_[from].is_both_null());
   KeySlice next_separator = strategy.separators_[from];
 
   for (uint16_t i = 1; i < move_count; ++i) {
     uint16_t original_index = i + from;
     ASSERT_ND(!strategy.pointers_[original_index].is_both_null());
     if (i >= next_mini_threshold && cur_mini < kMaxIntermediateSeparators) {
       // switch to next mini page. so, the separator goes to the first level
       assorted::memory_fence_release();  // set key count after all
       cur_mini_page->key_count_ = cur_mini_separators;  // close the current
       ASSERT_ND(cur_mini_page->key_count_ <= kMaxIntermediateMiniSeparators);
 
       dest->separators_[cur_mini] = next_separator;
 
       next_mini_threshold += entries_per_mini;
       cur_mini_separators = 0;
       ++cur_mini;
       cur_mini_page = &dest->get_minipage(cur_mini);
       cur_mini_page->pointers_[0] = strategy.pointers_[original_index];
     } else {
       // still the same mini page. so, the separator goes to the second level
       cur_mini_page->separators_[cur_mini_separators] = next_separator;
       ++cur_mini_separators;
       ASSERT_ND(cur_mini_separators <= kMaxIntermediateMiniSeparators);
 
       cur_mini_page->pointers_[cur_mini_separators] = strategy.pointers_[original_index];
     }
     next_separator = strategy.separators_[original_index];
   }
   cur_mini_page->key_count_ = cur_mini_separators;  // close the last one
   ASSERT_ND(cur_mini_page->key_count_ <= kMaxIntermediateMiniSeparators);
   assorted::memory_fence_release();
   dest->header_.set_key_count(cur_mini);  // set key count after all
   ASSERT_ND(dest->get_key_count() <= kMaxIntermediateSeparators);
 
   // the last separator is ignored because it's foster-fence/high-fence.
   ASSERT_ND(next_separator == expected_last_separator);
 
   dest->verify_separators();
 }

Here is the call graph for this function:

Here is the caller graph for this function:

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

overridevirtual

Interior node's Split.

Implements foedus::xct::SysxctFunctor.

Definition at line 443 of file masstree_split_impl.cpp.

References CHECK_ERROR_CODE, context_, foedus::thread::GrabFreeVolatilePagesScope::grab(), foedus::storage::masstree::MasstreePage::has_foster_child(), foedus::storage::masstree::MasstreePage::is_retired(), foedus::kErrorCodeOk, piggyback_adopt_child_, split_impl_no_error(), foedus::thread::Thread::sysxct_batch_page_locks(), foedus::thread::Thread::sysxct_page_lock(), and target_.

                                                                      {
   DVLOG(1) << "Preparing to split an intermediate page... ";
 
   // First, lock the page(s)
   Page* target_page = reinterpret_cast<Page*>(target_);
   if (piggyback_adopt_child_) {
     Page* pages[2];
     pages[0] = target_page;
     pages[1] = reinterpret_cast<Page*>(piggyback_adopt_child_);
     // lock target_ and piggyback_adopt_child_ in batched mode to avoid deadlock.
     CHECK_ERROR_CODE(context_->sysxct_batch_page_locks(sysxct_workspace, 2, pages));
   } else {
     CHECK_ERROR_CODE(context_->sysxct_page_lock(sysxct_workspace, target_page));
   }
 
   // The lock involves atomic operation, so now all we see are finalized.
   if (target_->has_foster_child()) {
     DVLOG(0) << "Interesting. the page has been already split";
     return kErrorCodeOk;
   }
   if (piggyback_adopt_child_ && piggyback_adopt_child_->is_retired()) {
     VLOG(0) << "Interesting. this child is now retired, so someone else has already adopted.";
     return kErrorCodeOk;  // fine. the goal is already achieved
   }
 
   // 3 free volatile pages needed.
   // foster-minor/major (will be placed in successful case), and SplitStrategy (will be discarded)
   memory::PagePoolOffset offsets[2];
   thread::GrabFreeVolatilePagesScope free_pages_scope(context_, offsets);
   CHECK_ERROR_CODE(free_pages_scope.grab(2));
   split_impl_no_error(&free_pages_scope);
   return kErrorCodeOk;
 }

Here is the call graph for this function:

void foedus::storage::masstree::SplitIntermediate::split_impl_no_error ( thread::GrabFreeVolatilePagesScope * free_pages )

The core implementation after locking relevant pages and acquiring free page resource.

This method never fails because all lock/resource are already taken.

Precondition: target_->is_locked(); free_pages->get_count() >= 2; piggyback_adopt_child_ == nullptr || piggyback_adopt_child_->is_locked(); target_->has_foster_child()) : should be checked after locking before calling; piggyback_adopt_child_ == nullptr || !piggyback_adopt_child_->is_retired(): same above

Definition at line 476 of file masstree_split_impl.cpp.

Referenced by run().

                                                                                         {
   // similar to border page's split, but simpler in a few places because
   // 1) intermediate page doesn't have owner_id for each pointer (no lock concerns).
   // 2) intermediate page is already completely sorted.
   // thus, this is just a physical operation without any transactional behavior.
   // even not a system transaction
   ASSERT_ND(!target_->header().snapshot_);
   ASSERT_ND(!target_->is_empty_range());
 
   debugging::RdtscWatch watch;
   DVLOG(1) << "Splitting an intermediate page... ";
 
   const uint8_t key_count = target_->get_key_count();
   target_->verify_separators();
 
   // 2 free volatile pages needed.
   // foster-minor/major (will be placed in successful case)
   const auto& resolver = context_->get_local_volatile_page_resolver();
 
   // SplitStrategy on heap. 4kb is not too large on heap
   SplitStrategy strategy;
   decide_strategy(&strategy);
   const KeySlice new_foster_fence = strategy.mid_separator_;
 
   MasstreeIntermediatePage* twin[2];
   VolatilePagePointer new_pointers[2];
   for (int i = 0; i < 2; ++i) {
     twin[i]
       = reinterpret_cast<MasstreeIntermediatePage*>(
           resolver.resolve_offset_newpage(free_pages->get(i)));
     new_pointers[i].set(context_->get_numa_node(), free_pages->get(i));
 
     twin[i]->initialize_volatile_page(
       target_->header().storage_id_,
       new_pointers[i],
       target_->get_layer(),
       target_->get_btree_level(),  // foster child has the same level as foster-parent
       i == 0 ? target_->low_fence_ : new_foster_fence,
       i == 0 ? new_foster_fence : target_->high_fence_);
   }
 
   migrate_pointers(strategy, 0, strategy.mid_index_ + 1, new_foster_fence, twin[0]);
   if (strategy.compact_adopt_) {
     twin[1]->set_key_count(0);  // right is empty-range
   } else {
     migrate_pointers(
       strategy,
       strategy.mid_index_ + 1,
       strategy.total_separator_count_,
       target_->high_fence_,
       twin[1]);
   }
 
   // Now we will install the new pages. **From now on no error-return allowed**
   assorted::memory_fence_release();
   // We install pointers to the pages AFTER we initialize the pages.
   target_->install_foster_twin(new_pointers[0], new_pointers[1], new_foster_fence);
   free_pages->dispatch(0);
   free_pages->dispatch(1);
   assorted::memory_fence_release();
   // invoking set_moved is the point we announce all of these changes. take fence to make it right
   target_->set_moved();
 
   if (piggyback_adopt_child_) {
     // piggyback_adopt_child_ is adopted and retired.
     piggyback_adopt_child_->set_retired();
     context_->collect_retired_volatile_page(piggyback_adopt_child_->get_volatile_page_id());
   }
 
   watch.stop();
   DVLOG(1) << "Costed " << watch.elapsed() << " cycles to split a node. original node"
     << " key count: " << static_cast<int>(key_count);
 
   target_->verify_separators();
 }

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

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

Thread context.

Definition at line 160 of file masstree_split_impl.hpp.

Referenced by run(), and split_impl_no_error().

MasstreePage* const foedus::storage::masstree::SplitIntermediate::piggyback_adopt_child_

An optimization for the common case: splitting the parent page to adopt foster twins of a child page.

The child page whose foster-twins will be adopted in the course of this split. Without this optimization, we need two Sysxct invocation, split and adopt. This also gives a hint whether it might be no-record-split (NRS). null if no such piggy-back adoption (in that case ignores the possibility of NRS).

Precondition: piggyback_adopt_child_ == nullptr || piggyback_adopt_child_->has_foster_child()

Definition at line 177 of file masstree_split_impl.hpp.

Referenced by decide_strategy(), run(), and split_impl_no_error().

MasstreeIntermediatePage* const foedus::storage::masstree::SplitIntermediate::target_

The page to split.

Precondition: !target_->header_.snapshot_ (split happens to only volatile pages)

Definition at line 165 of file masstree_split_impl.hpp.

Referenced by decide_strategy(), run(), and split_impl_no_error().

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

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

Detailed Description

Classes

Public Member Functions

Public Attributes

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation