Pimpl object of MasstreeStorage. More...

Detailed Description

A private pimpl object for MasstreeStorage. Do not include this header from a client program unless you know what you are doing.

Definition at line 98 of file masstree_storage_pimpl.hpp.

#include <masstree_storage_pimpl.hpp>

Inheritance diagram for foedus::storage::masstree::MasstreeStoragePimpl:

[legend]

Collaboration diagram for foedus::storage::masstree::MasstreeStoragePimpl:

[legend]

Public Member Functions
	MasstreeStoragePimpl ()

	MasstreeStoragePimpl (MasstreeStorage *storage)

ErrorStack	create (const MasstreeMetadata &metadata)

ErrorStack	load (const StorageControlBlock &snapshot_block)

ErrorStack	load_empty ()

ErrorStack	drop ()
	Storage-wide operations, such as drop, create, etc. More...

bool	exists () const

StorageId	get_id () const

const StorageName &	get_name () const

const MasstreeMetadata &	get_meta () const

const DualPagePointer &	get_first_root_pointer () const

DualPagePointer *	get_first_root_pointer_address ()

ErrorCode	get_first_root (thread::Thread context, bool for_write, MasstreeIntermediatePage *root)
	Root-node related, such as a method to retrieve 1st-root, to grow, etc. More...

ErrorCode	find_border_physical (thread::Thread context, MasstreePage layer_root, uint8_t current_layer, bool for_writes, KeySlice slice, MasstreeBorderPage **border) __attribute__((always_inline))
	Find a border node in the layer that corresponds to the given key slice. More...

ErrorCode	locate_record (thread::Thread context, const void key, KeyLength key_length, bool for_writes, RecordLocation *result)
	Identifies page and record for the key. More...

ErrorCode	locate_record_normalized (thread::Thread context, KeySlice key, bool for_writes, RecordLocation result)
	Identifies page and record for the normalized key. More...

ErrorCode	reserve_record (thread::Thread context, const void key, KeyLength key_length, PayloadLength payload_count, PayloadLength physical_payload_hint, RecordLocation *result)
	Like locate_record(), this is also a logical operation. More...

ErrorCode	reserve_record_normalized (thread::Thread context, KeySlice key, PayloadLength payload_count, PayloadLength physical_payload_hint, RecordLocation result)

ErrorCode	retrieve_general (thread::Thread context, const RecordLocation &location, void payload, PayloadLength *payload_capacity)
	implementation of get_record family. More...

ErrorCode	retrieve_part_general (thread::Thread context, const RecordLocation &location, void payload, PayloadLength payload_offset, PayloadLength payload_count)

ErrorCode	register_record_write_log (thread::Thread context, const RecordLocation &location, log::RecordLogType log_entry)
	Used in the following methods. More...

ErrorCode	insert_general (thread::Thread context, const RecordLocation &location, const void be_key, KeyLength key_length, const void *payload, PayloadLength payload_count)
	implementation of insert_record family. More...

ErrorCode	delete_general (thread::Thread context, const RecordLocation &location, const void be_key, KeyLength key_length)
	implementation of delete_record family. More...

ErrorCode	upsert_general (thread::Thread context, const RecordLocation &location, const void be_key, KeyLength key_length, const void *payload, PayloadLength payload_count)
	implementation of upsert_record family. More...

ErrorCode	overwrite_general (thread::Thread context, const RecordLocation &location, const void be_key, KeyLength key_length, const void *payload, PayloadLength payload_offset, PayloadLength payload_count)
	implementation of overwrite_record family. More...

template<typename PAYLOAD >
ErrorCode	increment_general (thread::Thread context, const RecordLocation &location, const void be_key, KeyLength key_length, PAYLOAD *value, PayloadLength payload_offset)
	implementation of increment_record family. More...

ErrorStack	verify_single_thread (thread::Thread *context)
	These are defined in masstree_storage_verify.cpp. More...

ErrorStack	verify_single_thread_layer (thread::Thread context, uint8_t layer, MasstreePage layer_root)

ErrorStack	verify_single_thread_intermediate (thread::Thread context, KeySlice low_fence, HighFence high_fence, MasstreeIntermediatePage page)

ErrorStack	verify_single_thread_border (thread::Thread context, KeySlice low_fence, HighFence high_fence, MasstreeBorderPage page)

ErrorStack	debugout_single_thread (Engine *engine, bool volatile_only, uint32_t max_pages)
	These are defined in masstree_storage_debug.cpp. More...

ErrorStack	debugout_single_thread_recurse (Engine engine, cache::SnapshotFileSet fileset, MasstreePage parent, bool follow_volatile, uint32_t remaining_pages)

ErrorStack	debugout_single_thread_follow (Engine engine, cache::SnapshotFileSet fileset, const DualPagePointer &pointer, bool follow_volatile, uint32_t *remaining_pages)

ErrorStack	hcc_reset_all_temperature_stat ()
	For stupid reasons (I'm lazy!) these are defined in _debug.cpp. More...

ErrorStack	hcc_reset_all_temperature_stat_recurse (MasstreePage *parent)

ErrorStack	hcc_reset_all_temperature_stat_follow (VolatilePagePointer page_id)

ErrorCode	follow_page (thread::Thread context, bool for_writes, storage::DualPagePointer pointer, MasstreePage **page)
	Thread::follow_page_pointer() for masstree. More...

ErrorCode	follow_layer (thread::Thread context, bool for_writes, MasstreeBorderPage parent, SlotIndex record_index, MasstreePage **page) __attribute__((always_inline))
	Follows to next layer's root page. More...

ErrorCode	prefetch_pages_normalized (thread::Thread *context, bool install_volatile, bool cache_snapshot, KeySlice from, KeySlice to)
	defined in masstree_storage_prefetch.cpp More...

ErrorCode	prefetch_pages_normalized_recurse (thread::Thread context, bool install_volatile, bool cache_snapshot, KeySlice from, KeySlice to, MasstreePage page)

ErrorCode	prefetch_pages_follow (thread::Thread context, DualPagePointer pointer, bool vol_on, bool snp_on, KeySlice from, KeySlice to)

xct::TrackMovedRecordResult	track_moved_record (xct::RwLockableXctId old_address, xct::WriteXctAccess write_set) __attribute__((always_inline))

ErrorCode	peek_volatile_page_boundaries (Engine *engine, const MasstreeStorage::PeekBoundariesArguments &args)
	Defined in masstree_storage_peek.cpp. More...

ErrorCode	peek_volatile_page_boundaries_next_layer (const MasstreePage *layer_root, const memory::GlobalVolatilePageResolver &resolver, const MasstreeStorage::PeekBoundariesArguments &args)

ErrorCode	peek_volatile_page_boundaries_this_layer (const MasstreePage *layer_root, const memory::GlobalVolatilePageResolver &resolver, const MasstreeStorage::PeekBoundariesArguments &args)

ErrorCode	peek_volatile_page_boundaries_this_layer_recurse (const MasstreeIntermediatePage *cur, const memory::GlobalVolatilePageResolver &resolver, const MasstreeStorage::PeekBoundariesArguments &args)

ErrorStack	fatify_first_root (thread::Thread *context, uint32_t desired_count, bool disable_no_record_split)
	Defined in masstree_storage_fatify.cpp. More...

ErrorStack	fatify_first_root_double (thread::Thread *context, bool disable_no_record_split)

ErrorCode	approximate_count_root_children (thread::Thread context, uint32_t out)
	Returns the count of direct children in the first-root node. More...

Public Member Functions inherited from foedus::Attachable< MasstreeStorageControlBlock >
	Attachable ()

	Attachable (Engine *engine)

	Attachable (Engine engine, MasstreeStorageControlBlock control_block)

	Attachable (MasstreeStorageControlBlock *control_block)

	Attachable (const Attachable &other)

virtual	~Attachable ()

Attachable &	operator= (const Attachable &other)

virtual void	attach (MasstreeStorageControlBlock *control_block)
	Attaches to the given shared memory. More...

bool	is_attached () const
	Returns whether the object has been already attached to some shared memory. More...

MasstreeStorageControlBlock *	get_control_block () const

Engine *	get_engine () const

void	set_engine (Engine *engine)

Static Public Member Functions
static ErrorCode	check_next_layer_bit (xct::XctId observed) __attribute__((always_inline))

Additional Inherited Members
Protected Attributes inherited from foedus::Attachable< MasstreeStorageControlBlock >
Engine *	engine_
	Most attachable object stores an engine pointer (local engine), so we define it here. More...

MasstreeStorageControlBlock *	control_block_
	The shared data on shared memory that has been initialized in some SOC or master engine. More...

Constructor & Destructor Documentation

foedus::storage::masstree::MasstreeStoragePimpl::MasstreeStoragePimpl ( )

inline

Definition at line 100 of file masstree_storage_pimpl.hpp.

100 : Attachable<MasstreeStorageControlBlock>() {}

foedus::storage::masstree::MasstreeStoragePimpl::MasstreeStoragePimpl ( MasstreeStorage * storage )

inlineexplicit

Definition at line 101 of file masstree_storage_pimpl.hpp.

     : Attachable<MasstreeStorageControlBlock>(
       storage->get_engine(),
       storage->get_control_block()) {}

Member Function Documentation

ErrorCode foedus::storage::masstree::MasstreeStoragePimpl::approximate_count_root_children	(	thread::Thread *	context,
		uint32_t *	out
	)

Returns the count of direct children in the first-root node.

This is without lock, so it might not be accurate.

Definition at line 42 of file masstree_storage_fatify.cpp.

References CHECK_ERROR_CODE, foedus::storage::masstree::count_children_approximate(), get_first_root(), and foedus::kErrorCodeOk.

Referenced by fatify_first_root(), and fatify_first_root_double().

                  {
   *out = 0;
   MasstreeIntermediatePage* root;
   CHECK_ERROR_CODE(get_first_root(context, true, &root));
   *out = count_children_approximate(root);
   return kErrorCodeOk;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ErrorCode foedus::storage::masstree::MasstreeStoragePimpl::check_next_layer_bit ( xct::XctId observed )

inlinestatic

Definition at line 589 of file masstree_storage_pimpl.cpp.

References foedus::xct::XctId::is_next_layer(), foedus::kErrorCodeOk, foedus::kErrorCodeXctRaceAbort, and UNLIKELY.

Referenced by delete_general(), increment_general(), insert_general(), overwrite_general(), retrieve_general(), retrieve_part_general(), and upsert_general().

                                                                              {
   if (UNLIKELY(observed.is_next_layer())) {
     // this should have been checked before this method and resolved as abort or retry,
     // but if it reaches here for some reason, we treat it as usual contention abort.
     DLOG(INFO) << "Probably this should be caught beforehand. next_layer bit is on";
     return kErrorCodeXctRaceAbort;
   }
   return kErrorCodeOk;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ErrorStack foedus::storage::masstree::MasstreeStoragePimpl::create ( const MasstreeMetadata & metadata )

Definition at line 164 of file masstree_storage_pimpl.cpp.

References CHECK_ERROR, foedus::Attachable< MasstreeStorageControlBlock >::control_block_, ERROR_STACK, exists(), get_name(), foedus::kErrorCodeStrAlreadyExists, foedus::storage::kExists, foedus::kRetOk, and load_empty().

Referenced by foedus::storage::masstree::MasstreeStorage::create().

                                                                         {
   if (exists()) {
     LOG(ERROR) << "This masstree-storage already exists: " << get_name();
     return ERROR_STACK(kErrorCodeStrAlreadyExists);
   }
 
   control_block_->meta_ = metadata;
   CHECK_ERROR(load_empty());
   control_block_->status_ = kExists;
   LOG(INFO) << "Newly created an masstree-storage " << get_name();
   return kRetOk;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ErrorStack foedus::storage::masstree::MasstreeStoragePimpl::debugout_single_thread	(	Engine *	engine,
		bool	volatile_only,
		uint32_t	max_pages
	)

These are defined in masstree_storage_debug.cpp.

Definition at line 36 of file masstree_storage_debug.cpp.

References CHECK_ERROR, foedus::Attachable< MasstreeStorageControlBlock >::control_block_, debugout_single_thread_follow(), foedus::Attachable< MasstreeStorageControlBlock >::engine_, foedus::DefaultInitializable::initialize(), foedus::storage::VolatilePagePointer::is_null(), foedus::kRetOk, foedus::UninitializeGuard::kWarnIfUninitializeError, foedus::storage::DualPagePointer::snapshot_pointer_, foedus::DefaultInitializable::uninitialize(), and foedus::storage::DualPagePointer::volatile_pointer_.

Referenced by foedus::storage::masstree::MasstreeStorage::debugout_single_thread().

                       {
   LOG(INFO) << "**"
     << std::endl << "***************************************************************"
     << std::endl << "***   Dumping " << MasstreeStorage(engine_, control_block_) << " in details. "
     << std::endl << "*** volatile_only=" << volatile_only << ", max_pages=" << max_pages
     << std::endl << "***************************************************************";
 
   cache::SnapshotFileSet files(engine);
   CHECK_ERROR(files.initialize());
   UninitializeGuard files_guard(&files, UninitializeGuard::kWarnIfUninitializeError);
 
   LOG(INFO) << "First, dumping volatile pages...";
   DualPagePointer pointer = control_block_->root_page_pointer_;
   if (pointer.volatile_pointer_.is_null()) {
     LOG(INFO) << "No volatile pages.";
   } else {
     uint32_t remaining = max_pages;
     CHECK_ERROR(debugout_single_thread_follow(engine, &files, pointer, true, &remaining));
   }
   LOG(INFO) << "Dumped volatile pages.";
   if (!volatile_only) {
     LOG(INFO) << "Now dumping snapshot pages...";
     if (pointer.snapshot_pointer_ == 0) {
       LOG(INFO) << "No snapshot pages.";
     } else {
       uint32_t remaining = max_pages;
       CHECK_ERROR(debugout_single_thread_follow(engine, &files, pointer, false, &remaining));
     }
     LOG(INFO) << "Dumped snapshot pages.";
   }
 
   CHECK_ERROR(files.uninitialize());
   return kRetOk;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ErrorStack foedus::storage::masstree::MasstreeStoragePimpl::debugout_single_thread_follow	(	Engine *	engine,
		cache::SnapshotFileSet *	fileset,
		const DualPagePointer &	pointer,
		bool	follow_volatile,
		uint32_t *	remaining_pages
	)

Definition at line 122 of file masstree_storage_debug.cpp.

References foedus::memory::AlignedMemory::alloc(), CHECK_ERROR, debugout_single_thread_recurse(), foedus::memory::AlignedMemory::get_block(), foedus::memory::EngineMemory::get_global_volatile_page_resolver(), foedus::Engine::get_memory_manager(), foedus::storage::VolatilePagePointer::is_null(), foedus::memory::AlignedMemory::kNumaAllocOnnode, foedus::kRetOk, foedus::cache::SnapshotFileSet::read_page(), foedus::memory::GlobalVolatilePageResolver::resolve_offset(), foedus::storage::DualPagePointer::snapshot_pointer_, foedus::storage::DualPagePointer::volatile_pointer_, and WRAP_ERROR_CODE.

Referenced by debugout_single_thread(), and debugout_single_thread_recurse().

                              {
   if ((*remaining_pages) == 0) {
     return kRetOk;
   }
   if (follow_volatile) {
     if (!pointer.volatile_pointer_.is_null()) {
      MasstreePage* page = reinterpret_cast<MasstreePage*>(
        engine->get_memory_manager()->get_global_volatile_page_resolver().resolve_offset(
         pointer.volatile_pointer_));
       CHECK_ERROR(debugout_single_thread_recurse(engine, files, page, true, remaining_pages));
     }
   } else {
     if (pointer.snapshot_pointer_ != 0) {
       memory::AlignedMemory buf;
       buf.alloc(1 << 12U, 1 << 12U, memory::AlignedMemory::kNumaAllocOnnode, 0);
       MasstreePage* page = reinterpret_cast<MasstreePage*>(buf.get_block());
       WRAP_ERROR_CODE(files->read_page(pointer.snapshot_pointer_, page));
       CHECK_ERROR(debugout_single_thread_recurse(engine, files, page, false, remaining_pages));
     }
   }
   return kRetOk;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ErrorStack foedus::storage::masstree::MasstreeStoragePimpl::debugout_single_thread_recurse	(	Engine *	engine,
		cache::SnapshotFileSet *	fileset,
		MasstreePage *	parent,
		bool	follow_volatile,
		uint32_t *	remaining_pages
	)

Definition at line 75 of file masstree_storage_debug.cpp.

References CHECK_ERROR, debugout_single_thread_follow(), foedus::storage::masstree::MasstreeBorderPage::does_point_to_layer(), foedus::storage::masstree::MasstreePage::get_key_count(), foedus::storage::masstree::MasstreeBorderPage::get_next_layer(), foedus::storage::masstree::MasstreePage::is_border(), foedus::storage::masstree::MasstreeIntermediatePointerIterator::is_valid(), and foedus::kRetOk.

Referenced by debugout_single_thread_follow().

                              {
   if (((*remaining_pages) == 0) || --(*remaining_pages) == 0) {
     LOG(INFO) << "Reached write-out max. skip the following";
     return kRetOk;
   }
   // Implementation note:
   // So far we don't follow foster-twins in debugout_xxx, so this is irrelevant.
   // However, if we change it later to follow foster-twins,
   // do not forget about empty-range intermediate pages that only appear as foster twins.
   // Empty-range border pages are fine. We just see zero records.
   // Foster-twins are sooner or later adopted, and Master-Tree invariant for intermediate page
   // guarantees that we can just read the old page. no need to follow foster-twins.
 
   LOG(INFO) << *parent;
   uint16_t key_count = parent->get_key_count();
   if (parent->is_border()) {
     MasstreeBorderPage* casted = reinterpret_cast<MasstreeBorderPage*>(parent);
     for (uint16_t i = 0; i < key_count; ++i) {
       if (casted->does_point_to_layer(i)) {
         CHECK_ERROR(debugout_single_thread_follow(
           engine,
           files,
           *casted->get_next_layer(i),
           follow_volatile,
           remaining_pages));
       }
     }
   } else {
     MasstreeIntermediatePage* casted = reinterpret_cast<MasstreeIntermediatePage*>(parent);
     for (MasstreeIntermediatePointerIterator it(casted); it.is_valid(); it.next()) {
       CHECK_ERROR(debugout_single_thread_follow(
         engine,
         files,
         it.get_pointer(),
         follow_volatile,
         remaining_pages));
     }
   }
 
   return kRetOk;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ErrorCode foedus::storage::masstree::MasstreeStoragePimpl::delete_general	(	thread::Thread *	context,
		const RecordLocation &	location,
		const void *	be_key,
		KeyLength	key_length
	)

implementation of delete_record family.

use with locate_record()

Definition at line 691 of file masstree_storage_pimpl.cpp.

References foedus::storage::masstree::MasstreeDeleteLogType::calculate_log_length(), CHECK_ERROR_CODE, check_next_layer_bit(), get_id(), foedus::thread::Thread::get_numa_node(), foedus::thread::Thread::get_thread_log_buffer(), foedus::storage::masstree::MasstreePage::header(), foedus::xct::XctId::is_deleted(), foedus::kErrorCodeStrKeyNotFound, foedus::storage::masstree::RecordLocation::observed_, foedus::storage::masstree::RecordLocation::page_, foedus::storage::masstree::MasstreeDeleteLogType::populate(), register_record_write_log(), foedus::log::ThreadLogBuffer::reserve_new_log(), and foedus::storage::PageHeader::stat_last_updater_node_.

Referenced by foedus::storage::masstree::MasstreeCursor::delete_record(), foedus::storage::masstree::MasstreeStorage::delete_record(), and foedus::storage::masstree::MasstreeStorage::delete_record_normalized().

                         {
   if (location.observed_.is_deleted()) {
     // in this case, we don't need a page-version set. the physical record is surely there.
     return kErrorCodeStrKeyNotFound;
   }
   CHECK_ERROR_CODE(check_next_layer_bit(location.observed_));
 
   MasstreeBorderPage* border = location.page_;
   uint16_t log_length = MasstreeDeleteLogType::calculate_log_length(key_length);
   MasstreeDeleteLogType* log_entry = reinterpret_cast<MasstreeDeleteLogType*>(
     context->get_thread_log_buffer().reserve_new_log(log_length));
   log_entry->populate(get_id(), be_key, key_length);
   border->header().stat_last_updater_node_ = context->get_numa_node();
   return register_record_write_log(context, location, log_entry);
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ErrorStack foedus::storage::masstree::MasstreeStoragePimpl::drop ( )

Storage-wide operations, such as drop, create, etc.

Definition at line 105 of file masstree_storage_pimpl.cpp.

References foedus::Attachable< MasstreeStorageControlBlock >::control_block_, foedus::Attachable< MasstreeStorageControlBlock >::engine_, foedus::memory::EngineMemory::get_global_volatile_page_resolver(), foedus::Engine::get_memory_manager(), get_name(), foedus::kRetOk, foedus::storage::masstree::MasstreeIntermediatePage::release_pages_recursive_parallel(), and foedus::memory::GlobalVolatilePageResolver::resolve_offset().

Referenced by foedus::storage::masstree::MasstreeStorage::drop().

                                       {
   LOG(INFO) << "Uninitializing a masstree-storage " << get_name();
 
   if (!control_block_->root_page_pointer_.volatile_pointer_.is_null()) {
     // release volatile pages
     const memory::GlobalVolatilePageResolver& page_resolver
       = engine_->get_memory_manager()->get_global_volatile_page_resolver();
     // first root is guaranteed to be an intermediate page
     MasstreeIntermediatePage* first_root = reinterpret_cast<MasstreeIntermediatePage*>(
       page_resolver.resolve_offset(control_block_->root_page_pointer_.volatile_pointer_));
     first_root->release_pages_recursive_parallel(engine_);
     control_block_->root_page_pointer_.volatile_pointer_.word = 0;
   }
 
   return kRetOk;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

bool foedus::storage::masstree::MasstreeStoragePimpl::exists ( ) const

inline

Definition at line 111 of file masstree_storage_pimpl.hpp.

References foedus::Attachable< MasstreeStorageControlBlock >::control_block_.

Referenced by create().

111 { return control_block_->exists(); }

foedus::Attachable< MasstreeStorageControlBlock >::control_block_

MasstreeStorageControlBlock * control_block_

The shared data on shared memory that has been initialized in some SOC or master engine.

Definition: attachable.hpp:111

Here is the caller graph for this function:

ErrorStack foedus::storage::masstree::MasstreeStoragePimpl::fatify_first_root	(	thread::Thread *	context,
		uint32_t	desired_count,
		bool	disable_no_record_split
	)

Defined in masstree_storage_fatify.cpp.

Definition at line 54 of file masstree_storage_fatify.cpp.

References approximate_count_root_children(), CHECK_ERROR, foedus::debugging::StopWatch::elapsed_us(), fatify_first_root_double(), get_name(), foedus::storage::masstree::kIntermediateAlmostFull, foedus::kRetOk, foedus::debugging::StopWatch::start(), foedus::debugging::StopWatch::stop(), and WRAP_ERROR_CODE.

Referenced by foedus::storage::masstree::MasstreeStorage::fatify_first_root().

                                 {
   LOG(INFO) << "Masstree-" << get_name() << " being fatified for " << desired_count
     << ", disable_no_record_split=" << disable_no_record_split;
 
   if (desired_count > kIntermediateAlmostFull) {
     LOG(INFO) << "desired_count too large. adjusted to the max";
     desired_count = kIntermediateAlmostFull;
   }
   uint32_t initial_children;
   WRAP_ERROR_CODE(approximate_count_root_children(context, &initial_children));
   LOG(INFO) << "initial_children=" << initial_children;
 
   // We keep doubling the direct root-children
   debugging::StopWatch watch;
   watch.start();
   uint16_t iterations = 0;
   for (uint32_t count = initial_children; count < desired_count && iterations < 10U; ++iterations) {
     CHECK_ERROR(fatify_first_root_double(context, disable_no_record_split));
     uint32_t new_count;
     WRAP_ERROR_CODE(approximate_count_root_children(context, &new_count));
     if (count == new_count) {
       LOG(WARNING) << "Not enough descendants for further fatification. Stopped here";
       break;
     }
     count = new_count;
   }
 
   uint32_t after_children;
   WRAP_ERROR_CODE(approximate_count_root_children(context, &after_children));
   watch.stop();
   LOG(INFO) << "fatify done: Iterations=" << iterations
     << ", took " << watch.elapsed_us() << "us in total."
     << " child count: " << initial_children << "->" << after_children;
 
   return kRetOk;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ErrorStack foedus::storage::masstree::MasstreeStoragePimpl::fatify_first_root_double	(	thread::Thread *	context,
		bool	disable_no_record_split
	)

Definition at line 94 of file masstree_storage_fatify.cpp.

Referenced by fatify_first_root().

                                 {
   // We invoke split sysxct and adopt sysxct many times.
   debugging::StopWatch watch;
   watch.start();
   uint16_t root_retries = 0;
   KeySlice cur_slice = kInfimumSlice;
   uint16_t skipped_children = 0;
   uint16_t adopted_children = 0;
   uint32_t initial_children;
   WRAP_ERROR_CODE(approximate_count_root_children(context, &initial_children));
   while (cur_slice != kSupremumSlice) {
     if (initial_children + adopted_children >= kIntermediateAlmostFull) {
       LOG(INFO) << "Root page nearing full. Stopped fatification";
       break;
     }
 
     // Get a non-moved root. This might trigger grow-root.
     // grow-root is a non-mandatory operation, so we might keep seeing a moved root.
     MasstreeIntermediatePage* root;
     WRAP_ERROR_CODE(get_first_root(context, true, &root));
     ASSERT_ND(root->get_low_fence() == kInfimumSlice);
     ASSERT_ND(root->get_high_fence() == kSupremumSlice);
     if (root->is_moved()) {
       ++root_retries;
       if (root_retries > 50U) {
         LOG(WARNING) << "Hm? there might be some contention to prevent grow-root. Gave up";
         break;
       }
       continue;
     }
 
     root_retries = 0;
     const auto minipage_index = root->find_minipage(cur_slice);
     auto& minipage = root->get_minipage(minipage_index);
     auto pointer_index = minipage.find_pointer(cur_slice);
 
     MasstreePage* child;
     WRAP_ERROR_CODE(follow_page(
       context,
       true,
       minipage.pointers_ + pointer_index,
       &child));
     ASSERT_ND(!child->header().snapshot_);
     cur_slice = child->get_high_fence();  // go on to next
 
     if (!child->is_moved()) {
       // Split the child so that we can adopt it to the root
       if (child->is_border()) {
         if (child->get_key_count() >= 2U) {
           MasstreeBorderPage* casted = reinterpret_cast<MasstreeBorderPage*>(child);
           auto low_slice = child->get_low_fence();
           auto high_slice = child->get_high_fence();
           auto mid_slice = low_slice + (high_slice - low_slice) / 2U;
           SplitBorder split(context, casted, mid_slice, disable_no_record_split);
           WRAP_ERROR_CODE(context->run_nested_sysxct(&split, 2U));
         } else {
           ++skipped_children;
           continue;  // not worth splitting
         }
       } else {
         MasstreeIntermediatePage* casted = reinterpret_cast<MasstreeIntermediatePage*>(child);
         uint32_t grandchild_count = count_children_approximate(casted);
         if (grandchild_count >= 2U) {
           SplitIntermediate split(context, casted);
           WRAP_ERROR_CODE(context->run_nested_sysxct(&split, 2U));
         } else {
           ++skipped_children;
           continue;  // not worth splitting
         }
       }
     }
 
     Adopt adopt(context, root, child);
     WRAP_ERROR_CODE(context->run_nested_sysxct(&adopt, 2U));
     ++adopted_children;
   }
 
   uint32_t after_children;
   WRAP_ERROR_CODE(approximate_count_root_children(context, &after_children));
   watch.stop();
   LOG(INFO) << "fatify_double: adopted " << adopted_children << " root-children and skipped "
     << skipped_children << " that are already too sparse in " << watch.elapsed_us() << "us."
     << " child count: " << initial_children << "->" << after_children;
 
   return kRetOk;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ErrorCode foedus::storage::masstree::MasstreeStoragePimpl::find_border_physical	(	thread::Thread *	context,
		MasstreePage *	layer_root,
		uint8_t	current_layer,
		bool	for_writes,
		KeySlice	slice,
		MasstreeBorderPage **	border
	)

inline

Find a border node in the layer that corresponds to the given key slice.

Record-wise or page-wise operations.

Note: this method is physical-only. It doesn't take any long-term lock or readset.

Definition at line 213 of file masstree_storage_pimpl.cpp.

Referenced by locate_record(), locate_record_normalized(), reserve_record(), and reserve_record_normalized().

                                {
   assert_aligned_page(layer_root);
   ASSERT_ND(layer_root->is_high_fence_supremum());
   ASSERT_ND(layer_root->get_low_fence() == kInfimumSlice);
   MasstreePage* cur = layer_root;
   cur->prefetch_general();
   while (true) {
     assert_aligned_page(cur);
     ASSERT_ND(cur->get_layer() == current_layer);
     ASSERT_ND(cur->within_fences(slice));
     if (cur->is_border()) {
       // We follow foster-twins only in border pages.
       // In intermediate pages, Master-Tree invariant tells us that we don't have to.
       // Furthermore, if we do, we need to handle the case of empty-range intermediate pages.
       // Rather we just do this only in border pages.
       if (UNLIKELY(cur->has_foster_child())) {
         // follow one of foster-twin.
         if (cur->within_foster_minor(slice)) {
           cur = reinterpret_cast<MasstreePage*>(context->resolve(cur->get_foster_minor()));
         } else {
           cur = reinterpret_cast<MasstreePage*>(context->resolve(cur->get_foster_major()));
         }
         ASSERT_ND(cur->within_fences(slice));
         continue;
       }
       *border = reinterpret_cast<MasstreeBorderPage*>(cur);
       return kErrorCodeOk;
     } else {
       MasstreeIntermediatePage* page = reinterpret_cast<MasstreeIntermediatePage*>(cur);
       uint8_t minipage_index = page->find_minipage(slice);
       MasstreeIntermediatePage::MiniPage& minipage = page->get_minipage(minipage_index);
 
       minipage.prefetch();
       uint8_t pointer_index = minipage.find_pointer(slice);
       DualPagePointer& pointer = minipage.pointers_[pointer_index];
       MasstreePage* next;
       CHECK_ERROR_CODE(follow_page(context, for_writes, &pointer, &next));
       next->prefetch_general();
       if (LIKELY(next->within_fences(slice))) {
         if (next->has_foster_child() && !cur->is_moved()) {
           // oh, the page has foster child, so we should adopt it.
           // Whether Adopt actually adopted it or not,
           // we follow the "old" next page. Master-Tree invariant guarantees that it's safe.
           // This is beneficial when we lazily give up adoption in the method, eg other threads
           // holding locks in the intermediate page.
           if (!next->is_locked() && !cur->is_locked()) {
             // Let's try adopting. No need to try many times. Adopt can be delayed
             Adopt functor(context, page, next);
             CHECK_ERROR_CODE(context->run_nested_sysxct(&functor, 2));
           } else {
             // We don't have to adopt it right away. Do it when it's not contended
             DVLOG(1) << "Someone else seems doing something there.. already adopting? skip it";
           }
         }
         cur = next;
       } else {
         // even in this case, local retry suffices thanks to foster-twin
         DVLOG(0) << "Interesting. concurrent thread affected the search. local retry";
         assorted::memory_fence_acquire();
       }
     }
   }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ErrorCode foedus::storage::masstree::MasstreeStoragePimpl::follow_layer	(	thread::Thread *	context,
		bool	for_writes,
		MasstreeBorderPage *	parent,
		SlotIndex	record_index,
		MasstreePage **	page
	)

inline

Follows to next layer's root page.

Definition at line 384 of file masstree_storage_pimpl.cpp.

References ASSERT_ND, CHECK_ERROR_CODE, foedus::storage::masstree::MasstreeBorderPage::does_point_to_layer(), follow_page(), foedus::storage::masstree::MasstreeBorderPage::get_next_layer(), foedus::storage::masstree::MasstreeBorderPage::get_owner_id(), foedus::xct::XctId::is_moved(), foedus::xct::XctId::is_next_layer(), foedus::storage::masstree::kBorderPageMaxSlots, foedus::kErrorCodeOk, foedus::thread::Thread::run_nested_sysxct(), UNLIKELY, and foedus::xct::RwLockableXctId::xct_id_.

Referenced by locate_record(), and reserve_record().

                        {
   ASSERT_ND(record_index < kBorderPageMaxSlots);
   ASSERT_ND(parent->does_point_to_layer(record_index));
   DualPagePointer* pointer = parent->get_next_layer(record_index);
   xct::RwLockableXctId* owner = parent->get_owner_id(record_index);
   ASSERT_ND(owner->xct_id_.is_next_layer() || owner->xct_id_.is_moved());
   ASSERT_ND(!pointer->is_both_null());
   MasstreePage* next_root;
   CHECK_ERROR_CODE(follow_page(context, for_writes, pointer, &next_root));
 
   // root page has a foster child... time for tree growth!
   if (UNLIKELY(next_root->has_foster_child())) {
     ASSERT_ND(next_root->get_layer() > 0);
     // Either case, we follow the old page. Master-Tree invariant guarantees it's safe
     GrowNonFirstLayerRoot functor(context, parent, record_index);
     CHECK_ERROR_CODE(context->run_nested_sysxct(&functor, 2U));
   }
 
   ASSERT_ND(next_root);
   *page = next_root;
   return kErrorCodeOk;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ErrorCode foedus::storage::masstree::MasstreeStoragePimpl::follow_page	(	thread::Thread *	context,
		bool	for_writes,
		storage::DualPagePointer *	pointer,
		MasstreePage **	page
	)

Thread::follow_page_pointer() for masstree.

Because of how masstree works, this method never creates a completely new page. In other words, always !pointer->is_both_null(). It either reads an existing volatile/snapshot page or creates a volatile page from existing snapshot page.

Definition at line 367 of file masstree_storage_pimpl.cpp.

References ASSERT_ND, foedus::thread::Thread::follow_page_pointer(), and foedus::storage::DualPagePointer::is_both_null().

Referenced by fatify_first_root_double(), find_border_physical(), follow_layer(), verify_single_thread_border(), and verify_single_thread_intermediate().

                        {
   ASSERT_ND(!pointer->is_both_null());
   return context->follow_page_pointer(
     nullptr,  // masstree doesn't create a new page except splits.
     false,  // so, there is no null page possible
     for_writes,  // always get volatile pages for writes
     true,
     pointer,
     reinterpret_cast<Page**>(page),
     nullptr,  // only used for new page creation, so nothing to pass
     -1);  // same as above
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ErrorCode foedus::storage::masstree::MasstreeStoragePimpl::get_first_root	(	thread::Thread *	context,
		bool	for_write,
		MasstreeIntermediatePage **	root
	)

Root-node related, such as a method to retrieve 1st-root, to grow, etc.

Definition at line 58 of file masstree_storage_pimpl.cpp.

References foedus::storage::assert_aligned_page(), ASSERT_ND, CHECK_ERROR_CODE, foedus::Attachable< MasstreeStorageControlBlock >::control_block_, foedus::thread::Thread::follow_page_pointer(), get_first_root_pointer_address(), foedus::storage::masstree::MasstreePage::get_high_fence(), get_id(), foedus::storage::masstree::MasstreePage::get_layer(), foedus::storage::masstree::MasstreePage::get_low_fence(), foedus::storage::masstree::MasstreePage::has_foster_child(), foedus::storage::masstree::MasstreePage::header(), foedus::kErrorCodeOk, foedus::storage::masstree::kInfimumSlice, foedus::storage::masstree::kSupremumSlice, foedus::thread::Thread::run_nested_sysxct(), foedus::storage::PageHeader::snapshot_, and UNLIKELY.

Referenced by approximate_count_root_children(), fatify_first_root_double(), locate_record(), locate_record_normalized(), foedus::storage::masstree::MasstreeCursor::open(), prefetch_pages_normalized(), reserve_record(), reserve_record_normalized(), and verify_single_thread().

                                    {
   DualPagePointer* root_pointer = get_first_root_pointer_address();
   MasstreeIntermediatePage* page = nullptr;
   CHECK_ERROR_CODE(context->follow_page_pointer(
     nullptr,
     false,
     for_write,
     true,
     root_pointer,
     reinterpret_cast<Page**>(&page),
     nullptr,
     0));
 
   assert_aligned_page(page);
   ASSERT_ND(page->get_layer() == 0);
   ASSERT_ND(page->get_low_fence() == kInfimumSlice);
   ASSERT_ND(page->get_high_fence() == kSupremumSlice);
   ASSERT_ND(!for_write || !page->header().snapshot_);
 
   if (UNLIKELY(page->has_foster_child())) {
     ASSERT_ND(!page->header().snapshot_);
     // root page has a foster child... time for tree growth!
     // either case, we just follow the moved page. Master-Tree invariant guarantees it's safe.
     if (control_block_->first_root_locked_) {
       // To avoid contention, we begin it only when the lock seems uncontended.
       DVLOG(0) << "Other thread seems growing the first-layer. let him do that";
     } else {
       GrowFirstLayerRoot functor(context, get_id());
       CHECK_ERROR_CODE(context->run_nested_sysxct(&functor, 2));
     }
   }
 
   ASSERT_ND(page->get_layer() == 0);
   ASSERT_ND(page->get_low_fence() == kInfimumSlice);
   ASSERT_ND(page->get_high_fence() == kSupremumSlice);
   *root = page;
   return kErrorCodeOk;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

const DualPagePointer& foedus::storage::masstree::MasstreeStoragePimpl::get_first_root_pointer ( ) const

inline

Definition at line 115 of file masstree_storage_pimpl.hpp.

References foedus::Attachable< MasstreeStorageControlBlock >::control_block_.

Referenced by peek_volatile_page_boundaries().

                                                         {
     return control_block_->root_page_pointer_;
   }

Here is the caller graph for this function:

DualPagePointer* foedus::storage::masstree::MasstreeStoragePimpl::get_first_root_pointer_address ( )

inline

Definition at line 118 of file masstree_storage_pimpl.hpp.

References foedus::Attachable< MasstreeStorageControlBlock >::control_block_.

Referenced by get_first_root().

118 { return &control_block_->root_page_pointer_; }

foedus::Attachable< MasstreeStorageControlBlock >::control_block_

MasstreeStorageControlBlock * control_block_

The shared data on shared memory that has been initialized in some SOC or master engine.

Definition: attachable.hpp:111

Here is the caller graph for this function:

StorageId foedus::storage::masstree::MasstreeStoragePimpl::get_id ( ) const

inline

Definition at line 112 of file masstree_storage_pimpl.hpp.

References foedus::Attachable< MasstreeStorageControlBlock >::control_block_.

Referenced by delete_general(), get_first_root(), increment_general(), insert_general(), load_empty(), overwrite_general(), register_record_write_log(), and upsert_general().

112 { return control_block_->meta_.id_; }

foedus::Attachable< MasstreeStorageControlBlock >::control_block_

MasstreeStorageControlBlock * control_block_

The shared data on shared memory that has been initialized in some SOC or master engine.

Definition: attachable.hpp:111

Here is the caller graph for this function:

const MasstreeMetadata& foedus::storage::masstree::MasstreeStoragePimpl::get_meta ( ) const

inline

Definition at line 114 of file masstree_storage_pimpl.hpp.

References foedus::Attachable< MasstreeStorageControlBlock >::control_block_.

Referenced by load(), and reserve_record().

114 { return control_block_->meta_; }

foedus::Attachable< MasstreeStorageControlBlock >::control_block_

MasstreeStorageControlBlock * control_block_

The shared data on shared memory that has been initialized in some SOC or master engine.

Definition: attachable.hpp:111

Here is the caller graph for this function:

const StorageName& foedus::storage::masstree::MasstreeStoragePimpl::get_name ( ) const

inline

Definition at line 113 of file masstree_storage_pimpl.hpp.

References foedus::Attachable< MasstreeStorageControlBlock >::control_block_.

Referenced by create(), drop(), fatify_first_root(), and prefetch_pages_normalized().

113 { return control_block_->meta_.name_; }

foedus::Attachable< MasstreeStorageControlBlock >::control_block_

MasstreeStorageControlBlock * control_block_

The shared data on shared memory that has been initialized in some SOC or master engine.

Definition: attachable.hpp:111

Here is the caller graph for this function:

ErrorStack foedus::storage::masstree::MasstreeStoragePimpl::hcc_reset_all_temperature_stat ( )

For stupid reasons (I'm lazy!) these are defined in _debug.cpp.

Definition at line 151 of file masstree_storage_debug.cpp.

References CHECK_ERROR, foedus::Attachable< MasstreeStorageControlBlock >::control_block_, foedus::Attachable< MasstreeStorageControlBlock >::engine_, hcc_reset_all_temperature_stat_follow(), foedus::storage::VolatilePagePointer::is_null(), foedus::kRetOk, and foedus::storage::DualPagePointer::volatile_pointer_.

Referenced by foedus::storage::masstree::MasstreeStorage::hcc_reset_all_temperature_stat().

                                                                 {
   LOG(INFO) << "**"
     << std::endl << "***************************************************************"
     << std::endl << "***   Reseting " << MasstreeStorage(engine_, control_block_) << "'s "
     << std::endl << "*** temperature stat for HCC"
     << std::endl << "***************************************************************";
 
   DualPagePointer pointer = control_block_->root_page_pointer_;
   if (pointer.volatile_pointer_.is_null()) {
     LOG(INFO) << "No volatile pages.";
   } else {
     CHECK_ERROR(hcc_reset_all_temperature_stat_follow(pointer.volatile_pointer_));
   }
 
   LOG(INFO) << "Done resettting";
   return kRetOk;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ErrorStack foedus::storage::masstree::MasstreeStoragePimpl::hcc_reset_all_temperature_stat_follow ( VolatilePagePointer page_id )

Definition at line 192 of file masstree_storage_debug.cpp.

References CHECK_ERROR, foedus::Attachable< MasstreeStorageControlBlock >::engine_, foedus::memory::EngineMemory::get_global_volatile_page_resolver(), foedus::Engine::get_memory_manager(), hcc_reset_all_temperature_stat_recurse(), foedus::storage::VolatilePagePointer::is_null(), foedus::kRetOk, and foedus::memory::GlobalVolatilePageResolver::resolve_offset().

Referenced by hcc_reset_all_temperature_stat(), and hcc_reset_all_temperature_stat_recurse().

                                {
   if (page_id.is_null()) {
     MasstreePage* page = reinterpret_cast<MasstreePage*>(
       engine_->get_memory_manager()->get_global_volatile_page_resolver().resolve_offset(page_id));
     CHECK_ERROR(hcc_reset_all_temperature_stat_recurse(page));
   }
   return kRetOk;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ErrorStack foedus::storage::masstree::MasstreeStoragePimpl::hcc_reset_all_temperature_stat_recurse ( MasstreePage * parent )

Definition at line 170 of file masstree_storage_debug.cpp.

References CHECK_ERROR, foedus::storage::masstree::MasstreeBorderPage::does_point_to_layer(), foedus::storage::masstree::MasstreePage::get_key_count(), foedus::storage::masstree::MasstreeBorderPage::get_next_layer(), hcc_reset_all_temperature_stat_follow(), foedus::storage::masstree::MasstreePage::header(), foedus::storage::PageHeader::hotness_, foedus::storage::masstree::MasstreePage::is_border(), foedus::storage::masstree::MasstreeIntermediatePointerIterator::is_valid(), foedus::kRetOk, foedus::assorted::ProbCounter::reset(), and foedus::storage::DualPagePointer::volatile_pointer_.

Referenced by hcc_reset_all_temperature_stat_follow().

                                                                                             {
   uint16_t key_count = parent->get_key_count();
   if (parent->is_border()) {
     MasstreeBorderPage* casted = reinterpret_cast<MasstreeBorderPage*>(parent);
     casted->header().hotness_.reset();
     for (uint16_t i = 0; i < key_count; ++i) {
       if (casted->does_point_to_layer(i)) {
         CHECK_ERROR(hcc_reset_all_temperature_stat_follow(
           casted->get_next_layer(i)->volatile_pointer_));
       }
     }
   } else {
     MasstreeIntermediatePage* casted = reinterpret_cast<MasstreeIntermediatePage*>(parent);
     for (MasstreeIntermediatePointerIterator it(casted); it.is_valid(); it.next()) {
       CHECK_ERROR(hcc_reset_all_temperature_stat_follow(
         it.get_pointer().volatile_pointer_));
     }
   }
 
   return kRetOk;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename PAYLOAD >

ErrorCode foedus::storage::masstree::MasstreeStoragePimpl::increment_general	(	thread::Thread *	context,
		const RecordLocation &	location,
		const void *	be_key,
		KeyLength	key_length,
		PAYLOAD *	value,
		PayloadLength	payload_offset
	)

implementation of increment_record family.

use with locate_record()

Definition at line 806 of file masstree_storage_pimpl.cpp.

References foedus::storage::masstree::MasstreeCommonLogType::calculate_log_length(), CHECK_ERROR_CODE, check_next_layer_bit(), get_id(), foedus::thread::Thread::get_numa_node(), foedus::storage::masstree::MasstreeBorderPage::get_payload_length(), foedus::storage::masstree::MasstreeBorderPage::get_record_payload(), foedus::thread::Thread::get_thread_log_buffer(), foedus::storage::masstree::MasstreePage::header(), foedus::storage::masstree::RecordLocation::index_, foedus::xct::XctId::is_deleted(), foedus::kErrorCodeStrKeyNotFound, foedus::kErrorCodeStrTooShortPayload, foedus::storage::masstree::RecordLocation::observed_, foedus::storage::masstree::RecordLocation::page_, foedus::storage::masstree::MasstreeOverwriteLogType::populate(), register_record_write_log(), foedus::log::ThreadLogBuffer::reserve_new_log(), and foedus::storage::PageHeader::stat_last_updater_node_.

Referenced by foedus::storage::masstree::MasstreeCursor::increment_record(), foedus::storage::masstree::MasstreeStorage::increment_record(), and foedus::storage::masstree::MasstreeStorage::increment_record_normalized().

                                 {
   if (location.observed_.is_deleted()) {
     // in this case, we don't need a page-version set. the physical record is surely there.
     return kErrorCodeStrKeyNotFound;
   }
   CHECK_ERROR_CODE(check_next_layer_bit(location.observed_));
   MasstreeBorderPage* border = location.page_;
   if (border->get_payload_length(location.index_) < payload_offset + sizeof(PAYLOAD)) {
     LOG(WARNING) << "short record ";  // probably this is a rare error. so warn.
     return kErrorCodeStrTooShortPayload;
   }
 
   char* ptr = border->get_record_payload(location.index_) + payload_offset;
   *value += *reinterpret_cast<const PAYLOAD*>(ptr);
 
   uint16_t log_length = MasstreeOverwriteLogType::calculate_log_length(key_length, sizeof(PAYLOAD));
   MasstreeOverwriteLogType* log_entry = reinterpret_cast<MasstreeOverwriteLogType*>(
     context->get_thread_log_buffer().reserve_new_log(log_length));
   log_entry->populate(
     get_id(),
     be_key,
     key_length,
     value,
     payload_offset,
     sizeof(PAYLOAD));
   border->header().stat_last_updater_node_ = context->get_numa_node();
   return register_record_write_log(context, location, log_entry);
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ErrorCode foedus::storage::masstree::MasstreeStoragePimpl::insert_general	(	thread::Thread *	context,
		const RecordLocation &	location,
		const void *	be_key,
		KeyLength	key_length,
		const void *	payload,
		PayloadLength	payload_count
	)

implementation of insert_record family.

use with reserve_record()

Definition at line 661 of file masstree_storage_pimpl.cpp.

References ASSERT_ND, foedus::storage::masstree::MasstreeCommonLogType::calculate_log_length(), CHECK_ERROR_CODE, check_next_layer_bit(), get_id(), foedus::storage::masstree::MasstreeBorderPage::get_max_payload_length(), foedus::thread::Thread::get_numa_node(), foedus::thread::Thread::get_thread_log_buffer(), foedus::storage::masstree::MasstreePage::header(), foedus::storage::masstree::RecordLocation::index_, foedus::xct::XctId::is_deleted(), foedus::kErrorCodeStrKeyAlreadyExists, foedus::storage::masstree::RecordLocation::observed_, foedus::storage::masstree::RecordLocation::page_, foedus::storage::masstree::MasstreeInsertLogType::populate(), register_record_write_log(), foedus::log::ThreadLogBuffer::reserve_new_log(), and foedus::storage::PageHeader::stat_last_updater_node_.

Referenced by foedus::storage::masstree::MasstreeStorage::insert_record(), and foedus::storage::masstree::MasstreeStorage::insert_record_normalized().

                                 {
   if (!location.observed_.is_deleted()) {
     return kErrorCodeStrKeyAlreadyExists;
   }
   CHECK_ERROR_CODE(check_next_layer_bit(location.observed_));
 
   // as of reserve_record() it was spacious enough, and this length is
   // either immutable or only increases, so this must hold.
   MasstreeBorderPage* border = location.page_;
   ASSERT_ND(border->get_max_payload_length(location.index_) >= payload_count);
 
   uint16_t log_length = MasstreeInsertLogType::calculate_log_length(key_length, payload_count);
   MasstreeInsertLogType* log_entry = reinterpret_cast<MasstreeInsertLogType*>(
     context->get_thread_log_buffer().reserve_new_log(log_length));
   log_entry->populate(
     get_id(),
     be_key,
     key_length,
     payload,
     payload_count);
   border->header().stat_last_updater_node_ = context->get_numa_node();
   return register_record_write_log(context, location, log_entry);
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ErrorStack foedus::storage::masstree::MasstreeStoragePimpl::load ( const StorageControlBlock & snapshot_block )

Definition at line 176 of file masstree_storage_pimpl.cpp.

References CHECK_ERROR, foedus::Attachable< MasstreeStorageControlBlock >::control_block_, foedus::Attachable< MasstreeStorageControlBlock >::engine_, foedus::Engine::get_memory_manager(), get_meta(), foedus::DefaultInitializable::initialize(), foedus::storage::kExists, foedus::kRetOk, foedus::UninitializeGuard::kWarnIfUninitializeError, load_empty(), foedus::memory::EngineMemory::load_one_volatile_page(), foedus::storage::StorageControlBlock::meta_, foedus::storage::Metadata::root_snapshot_page_id_, and foedus::DefaultInitializable::uninitialize().

Referenced by foedus::storage::masstree::MasstreeStorage::load().

                                                                                {
   control_block_->meta_ = static_cast<const MasstreeMetadata&>(snapshot_block.meta_);
   const MasstreeMetadata& meta = control_block_->meta_;
   control_block_->root_page_pointer_.snapshot_pointer_ = meta.root_snapshot_page_id_;
   control_block_->root_page_pointer_.volatile_pointer_.word = 0;
   control_block_->first_root_locked_ = false;
 
   // So far we assume the root page always has a volatile version.
   // Create it now.
   if (meta.root_snapshot_page_id_ != 0) {
     cache::SnapshotFileSet fileset(engine_);
     CHECK_ERROR(fileset.initialize());
     UninitializeGuard fileset_guard(&fileset, UninitializeGuard::kWarnIfUninitializeError);
     VolatilePagePointer volatile_pointer;
     MasstreeIntermediatePage* volatile_root;
     CHECK_ERROR(engine_->get_memory_manager()->load_one_volatile_page(
       &fileset,
       meta.root_snapshot_page_id_,
       &volatile_pointer,
       reinterpret_cast<Page**>(&volatile_root)));
     CHECK_ERROR(fileset.uninitialize());
     control_block_->root_page_pointer_.volatile_pointer_ = volatile_pointer;
   } else {
     LOG(INFO) << "This is an empty masstree: " << get_meta();
     CHECK_ERROR(load_empty());
   }
 
   control_block_->status_ = kExists;
   LOG(INFO) << "Loaded a masstree-storage " << get_meta();
   return kRetOk;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ErrorStack foedus::storage::masstree::MasstreeStoragePimpl::load_empty ( )

Definition at line 122 of file masstree_storage_pimpl.cpp.

References ASSERT_ND, foedus::Attachable< MasstreeStorageControlBlock >::control_block_, foedus::Attachable< MasstreeStorageControlBlock >::engine_, get_id(), foedus::Engine::get_memory_manager(), foedus::storage::masstree::MasstreeIntermediatePage::get_minipage(), foedus::memory::EngineMemory::get_node_memory(), foedus::memory::PagePool::get_resolver(), foedus::memory::NumaNodeMemoryRef::get_volatile_pool(), foedus::memory::PagePool::grab_one(), foedus::storage::masstree::MasstreeIntermediatePage::initialize_volatile_page(), foedus::storage::masstree::MasstreeBorderPage::initialize_volatile_page(), foedus::storage::masstree::kInfimumSlice, foedus::kRetOk, foedus::storage::masstree::kSupremumSlice, foedus::storage::masstree::MasstreeIntermediatePage::MiniPage::pointers_, foedus::memory::LocalPageResolver::resolve_offset_newpage(), foedus::storage::VolatilePagePointer::set(), foedus::storage::DualPagePointer::snapshot_pointer_, foedus::storage::DualPagePointer::volatile_pointer_, and WRAP_ERROR_CODE.

Referenced by create(), and load().

                                             {
   control_block_->root_page_pointer_.snapshot_pointer_ = 0;
   control_block_->root_page_pointer_.volatile_pointer_.word = 0;
   control_block_->meta_.root_snapshot_page_id_ = 0;
 
   const uint16_t kDummyNode = 0;  // whatever. just pick from the first node
   memory::PagePool* pool
     = engine_->get_memory_manager()->get_node_memory(kDummyNode)->get_volatile_pool();
   const memory::LocalPageResolver &local_resolver = pool->get_resolver();
 
   // The root of first layer is always an intermediate page.
   // This is a special rule only for first layer to simplify partitioning and composer.
   memory::PagePoolOffset root_offset;
   WRAP_ERROR_CODE(pool->grab_one(&root_offset));
   ASSERT_ND(root_offset);
   MasstreeIntermediatePage* root_page = reinterpret_cast<MasstreeIntermediatePage*>(
     local_resolver.resolve_offset_newpage(root_offset));
   control_block_->first_root_locked_ = false;
   control_block_->root_page_pointer_.snapshot_pointer_ = 0;
   control_block_->root_page_pointer_.volatile_pointer_.set(kDummyNode, root_offset);
   root_page->initialize_volatile_page(
     get_id(),
     control_block_->root_page_pointer_.volatile_pointer_,
     0,
     1,
     kInfimumSlice,
     kSupremumSlice);
 
   // Also allocate the only child.
   memory::PagePoolOffset child_offset;
   WRAP_ERROR_CODE(pool->grab_one(&child_offset));
   ASSERT_ND(child_offset);
   MasstreeBorderPage* child_page = reinterpret_cast<MasstreeBorderPage*>(
     local_resolver.resolve_offset_newpage(child_offset));
   VolatilePagePointer child_pointer;
   child_pointer.set(kDummyNode, child_offset);
   child_page->initialize_volatile_page(get_id(), child_pointer, 0, kInfimumSlice, kSupremumSlice);
   root_page->get_minipage(0).pointers_[0].snapshot_pointer_ = 0;
   root_page->get_minipage(0).pointers_[0].volatile_pointer_ = child_pointer;
   return kRetOk;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ErrorCode foedus::storage::masstree::MasstreeStoragePimpl::locate_record	(	thread::Thread *	context,
		const void *	key,
		KeyLength	key_length,
		bool	for_writes,
		RecordLocation *	result
	)

Identifies page and record for the key.

Definition at line 283 of file masstree_storage_pimpl.cpp.

Referenced by foedus::storage::masstree::MasstreeStorage::delete_record(), foedus::storage::masstree::MasstreeStorage::get_record(), foedus::storage::masstree::MasstreeStorage::get_record_part(), foedus::storage::masstree::MasstreeStorage::get_record_primitive(), foedus::storage::masstree::MasstreeStorage::increment_record(), foedus::storage::masstree::MasstreeStorage::overwrite_record(), and foedus::storage::masstree::MasstreeStorage::overwrite_record_primitive().

                           {
   ASSERT_ND(result);
   ASSERT_ND(key_length <= kMaxKeyLength);
   result->clear();
   xct::Xct* cur_xct = &context->get_current_xct();
   MasstreePage* layer_root;
   CHECK_ERROR_CODE(get_first_root(
     context,
     for_writes,
     reinterpret_cast<MasstreeIntermediatePage**>(&layer_root)));
   for (uint16_t current_layer = 0;; ++current_layer) {
     KeyLength remainder_length = key_length - current_layer * 8;
     KeySlice slice = slice_layer(key, key_length, current_layer);
     const void* suffix = reinterpret_cast<const char*>(key) + (current_layer + 1) * 8;
     MasstreeBorderPage* border;
     CHECK_ERROR_CODE(find_border_physical(
       context,
       layer_root,
       current_layer,
       for_writes,
       slice,
       &border));
     PageVersionStatus border_version = border->get_version().status_;
     assorted::memory_fence_consume();
     SlotIndex index = border->find_key(slice, suffix, remainder_length);
 
     if (index == kBorderPageMaxSlots) {
       // this means not found. add it to page version set to protect the lack of record
       if (!border->header().snapshot_) {
         CHECK_ERROR_CODE(cur_xct->add_to_page_version_set(
           border->get_version_address(),
           border_version));
       }
       // So far we just use page-version set to protect this non-existence.
       // TASK(Hideaki) range lock rather than page-set to improve concurrency?
       result->clear();
       return kErrorCodeStrKeyNotFound;
     }
     if (border->does_point_to_layer(index)) {
       CHECK_ERROR_CODE(follow_layer(context, for_writes, border, index, &layer_root));
       continue;
     } else {
       CHECK_ERROR_CODE(result->populate_logical(cur_xct, border, index, for_writes));
       return kErrorCodeOk;
     }
   }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ErrorCode foedus::storage::masstree::MasstreeStoragePimpl::locate_record_normalized	(	thread::Thread *	context,
		KeySlice	key,
		bool	for_writes,
		RecordLocation *	result
	)

Identifies page and record for the normalized key.

Definition at line 336 of file masstree_storage_pimpl.cpp.

Referenced by foedus::storage::masstree::MasstreeStorage::delete_record_normalized(), foedus::storage::masstree::MasstreeStorage::get_record_normalized(), foedus::storage::masstree::MasstreeStorage::get_record_part_normalized(), foedus::storage::masstree::MasstreeStorage::get_record_primitive_normalized(), foedus::storage::masstree::MasstreeStorage::increment_record_normalized(), foedus::storage::masstree::MasstreeStorage::overwrite_record_normalized(), and foedus::storage::masstree::MasstreeStorage::overwrite_record_primitive_normalized().

                           {
   ASSERT_ND(result);
   result->clear();
   xct::Xct* cur_xct = &context->get_current_xct();
   MasstreeBorderPage* border;
   MasstreeIntermediatePage* layer_root;
   CHECK_ERROR_CODE(get_first_root(context, for_writes, &layer_root));
   CHECK_ERROR_CODE(find_border_physical(context, layer_root, 0, for_writes, key, &border));
   SlotIndex index = border->find_key_normalized(0, border->get_key_count(), key);
   PageVersionStatus border_version = border->get_version().status_;
   if (index == kBorderPageMaxSlots) {
     // this means not found
     if (!border->header().snapshot_) {
       CHECK_ERROR_CODE(cur_xct->add_to_page_version_set(
         border->get_version_address(),
         border_version));
     }
     // TASK(Hideaki) range lock
     result->clear();
     return kErrorCodeStrKeyNotFound;
   }
   // because this is just one slice, we never go to second layer
   ASSERT_ND(!border->does_point_to_layer(index));
   CHECK_ERROR_CODE(result->populate_logical(cur_xct, border, index, for_writes));
   return kErrorCodeOk;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ErrorCode foedus::storage::masstree::MasstreeStoragePimpl::overwrite_general	(	thread::Thread *	context,
		const RecordLocation &	location,
		const void *	be_key,
		KeyLength	key_length,
		const void *	payload,
		PayloadLength	payload_offset,
		PayloadLength	payload_count
	)

implementation of overwrite_record family.

use with locate_record()

Definition at line 772 of file masstree_storage_pimpl.cpp.

References foedus::storage::masstree::MasstreeCommonLogType::calculate_log_length(), CHECK_ERROR_CODE, check_next_layer_bit(), get_id(), foedus::thread::Thread::get_numa_node(), foedus::storage::masstree::MasstreeBorderPage::get_payload_length(), foedus::thread::Thread::get_thread_log_buffer(), foedus::storage::masstree::MasstreePage::header(), foedus::storage::masstree::RecordLocation::index_, foedus::xct::XctId::is_deleted(), foedus::kErrorCodeStrKeyNotFound, foedus::kErrorCodeStrTooShortPayload, foedus::storage::masstree::RecordLocation::observed_, foedus::storage::masstree::RecordLocation::page_, foedus::storage::masstree::MasstreeOverwriteLogType::populate(), register_record_write_log(), foedus::log::ThreadLogBuffer::reserve_new_log(), and foedus::storage::PageHeader::stat_last_updater_node_.

Referenced by foedus::storage::masstree::MasstreeCursor::overwrite_record(), foedus::storage::masstree::MasstreeStorage::overwrite_record(), foedus::storage::masstree::MasstreeStorage::overwrite_record_normalized(), foedus::storage::masstree::MasstreeCursor::overwrite_record_primitive(), foedus::storage::masstree::MasstreeStorage::overwrite_record_primitive(), and foedus::storage::masstree::MasstreeStorage::overwrite_record_primitive_normalized().

                                 {
   if (location.observed_.is_deleted()) {
     // in this case, we don't need a page-version set. the physical record is surely there.
     return kErrorCodeStrKeyNotFound;
   }
   CHECK_ERROR_CODE(check_next_layer_bit(location.observed_));
   MasstreeBorderPage* border = location.page_;
   if (border->get_payload_length(location.index_) < payload_offset + payload_count) {
     LOG(WARNING) << "short record ";  // probably this is a rare error. so warn.
     return kErrorCodeStrTooShortPayload;
   }
 
   uint16_t log_length = MasstreeOverwriteLogType::calculate_log_length(key_length, payload_count);
   MasstreeOverwriteLogType* log_entry = reinterpret_cast<MasstreeOverwriteLogType*>(
     context->get_thread_log_buffer().reserve_new_log(log_length));
   log_entry->populate(
     get_id(),
     be_key,
     key_length,
     payload,
     payload_offset,
     payload_count);
   border->header().stat_last_updater_node_ = context->get_numa_node();
   return register_record_write_log(context, location, log_entry);
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ErrorCode foedus::storage::masstree::MasstreeStoragePimpl::peek_volatile_page_boundaries	(	Engine *	engine,
		const MasstreeStorage::PeekBoundariesArguments &	args
	)

Defined in masstree_storage_peek.cpp.

Definition at line 37 of file masstree_storage_peek.cpp.

References foedus::storage::masstree::MasstreeStorage::PeekBoundariesArguments::found_boundary_count_, get_first_root_pointer(), foedus::memory::EngineMemory::get_global_volatile_page_resolver(), foedus::Engine::get_memory_manager(), foedus::storage::VolatilePagePointer::is_null(), foedus::kErrorCodeOk, peek_volatile_page_boundaries_next_layer(), peek_volatile_page_boundaries_this_layer(), foedus::storage::masstree::MasstreeStorage::PeekBoundariesArguments::prefix_slice_count_, foedus::memory::GlobalVolatilePageResolver::resolve_offset(), and foedus::storage::DualPagePointer::volatile_pointer_.

Referenced by foedus::storage::masstree::MasstreeStorage::peek_volatile_page_boundaries().

                                                       {
   *args.found_boundary_count_ = 0;
 
   VolatilePagePointer root_pointer = get_first_root_pointer().volatile_pointer_;
   if (root_pointer.is_null()) {
     VLOG(0) << "This masstree has no volatile pages. Maybe the composer is executed as part of"
       << " restart?";
     return kErrorCodeOk;
   }
 
   const memory::GlobalVolatilePageResolver& resolver
     = engine->get_memory_manager()->get_global_volatile_page_resolver();
   const MasstreePage* root
     = reinterpret_cast<const MasstreePage*>(resolver.resolve_offset(root_pointer));
 
   if (args.prefix_slice_count_ == 0) {
     return peek_volatile_page_boundaries_this_layer(root, resolver, args);
   } else {
     return peek_volatile_page_boundaries_next_layer(root, resolver, args);
   }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ErrorCode foedus::storage::masstree::MasstreeStoragePimpl::peek_volatile_page_boundaries_next_layer	(	const MasstreePage *	layer_root,
		const memory::GlobalVolatilePageResolver &	resolver,
		const MasstreeStorage::PeekBoundariesArguments &	args
	)

Definition at line 61 of file masstree_storage_peek.cpp.

Referenced by peek_volatile_page_boundaries().

                                                       {
   ASSERT_ND(!layer_root->header().snapshot_);
   uint8_t this_layer = layer_root->get_layer();
   ASSERT_ND(this_layer < args.prefix_slice_count_);
   ASSERT_ND(layer_root->get_low_fence() == kInfimumSlice && layer_root->is_high_fence_supremum());
   KeySlice slice = args.prefix_slices_[layer_root->get_layer()];
 
   // look for this slice in this layer. If we can't find it (which is unlikely), no results.
   // compared to tree-traversal code in the transactional methods, we can give up whenever
   // something rare happens.
   const MasstreePage* cur = layer_root;
   cur->prefetch_general();
   while (!cur->is_border()) {
     ASSERT_ND(cur->within_fences(slice));
     // We do NOT follow foster-twins here.
     // Foster-twins are sooner or later adopted, and Master-Tree invariant for intermediate page
     // guarantees that we can just read the old page. no need to follow foster-twins.
     const MasstreeIntermediatePage* page = reinterpret_cast<const MasstreeIntermediatePage*>(cur);
     uint8_t minipage_index = page->find_minipage(slice);
     const MasstreeIntermediatePage::MiniPage& minipage = page->get_minipage(minipage_index);
 
     minipage.prefetch();
     uint8_t pointer_index = minipage.find_pointer(slice);
     VolatilePagePointer pointer = minipage.pointers_[pointer_index].volatile_pointer_;
     const MasstreePage* next
       = reinterpret_cast<const MasstreePage*>(resolver.resolve_offset(pointer));
     next->prefetch_general();
     if (LIKELY(next->within_fences(slice))) {
       cur = next;
     } else {
       // even in this case, local retry suffices thanks to foster-twin
       VLOG(0) << "Interesting. concurrent thread affected the search. local retry";
       assorted::memory_fence_acquire();
     }
   }
   const MasstreeBorderPage* border = reinterpret_cast<const MasstreeBorderPage*>(cur);
 
   // following code are not transactional at all, but it's fine because these are just hints.
   // however, make sure we don't hit something like segfault. check nulls etc.
   ASSERT_ND(border->within_fences(slice));
   uint8_t key_count = border->get_key_count();
   SlotIndex rec = kBorderPageMaxSlots;
   border->prefetch_additional_if_needed(key_count);
   for (SlotIndex i = 0; i < key_count; ++i) {
     KeySlice cur_slice = border->get_slice(i);
     if (LIKELY(cur_slice < slice)) {
       continue;
     }
     if (cur_slice > slice) {
       break;
     }
     // one slice might be used for up to 10 keys, length 0 to 8 and pointer to next layer.
     if (border->does_point_to_layer(i)) {
       rec = i;
       break;
     }
   }
 
   if (UNLIKELY(rec >= key_count || !border->does_point_to_layer(rec))) {
     LOG(INFO) << "Slice not found during peeking. Gives up finding a page boundary hint";
     return kErrorCodeOk;
   }
 
   VolatilePagePointer pointer = border->get_next_layer(rec)->volatile_pointer_;
   if (UNLIKELY(pointer.is_null()
     || pointer.get_numa_node() >= resolver.numa_node_count_
     || pointer.get_offset() < resolver.begin_
     || pointer.get_offset() >= resolver.end_)) {
     LOG(INFO) << "Encountered invalid page during peeking. Gives up finding a page boundary hint";
     return kErrorCodeOk;
   }
   const MasstreePage* next_root
     = reinterpret_cast<const MasstreePage*>(resolver.resolve_offset(pointer));
   if (this_layer + 1U == args.prefix_slice_count_) {
     return peek_volatile_page_boundaries_this_layer(next_root, resolver, args);
   } else {
     return peek_volatile_page_boundaries_next_layer(next_root, resolver, args);
   }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ErrorCode foedus::storage::masstree::MasstreeStoragePimpl::peek_volatile_page_boundaries_this_layer	(	const MasstreePage *	layer_root,
		const memory::GlobalVolatilePageResolver &	resolver,
		const MasstreeStorage::PeekBoundariesArguments &	args
	)

Definition at line 144 of file masstree_storage_peek.cpp.

References ASSERT_ND, foedus::storage::masstree::MasstreePage::get_layer(), foedus::storage::masstree::MasstreePage::get_low_fence(), foedus::storage::masstree::MasstreePage::header(), foedus::storage::masstree::MasstreePage::is_border(), foedus::storage::masstree::MasstreePage::is_high_fence_supremum(), foedus::kErrorCodeOk, foedus::storage::masstree::kInfimumSlice, peek_volatile_page_boundaries_this_layer_recurse(), foedus::storage::masstree::MasstreeStorage::PeekBoundariesArguments::prefix_slice_count_, and foedus::storage::PageHeader::snapshot_.

Referenced by peek_volatile_page_boundaries(), and peek_volatile_page_boundaries_next_layer().

                                                       {
   ASSERT_ND(!layer_root->header().snapshot_);
   ASSERT_ND(layer_root->get_layer() == args.prefix_slice_count_);
   ASSERT_ND(layer_root->get_low_fence() == kInfimumSlice && layer_root->is_high_fence_supremum());
   if (layer_root->is_border()) {
     ASSERT_ND(layer_root->get_layer() > 0);  // first layer's root page is always intermediate
     // the root page of the layer of interest is a border page, hence no boundaries.
     return kErrorCodeOk;
   }
   const MasstreeIntermediatePage* cur
     = reinterpret_cast<const MasstreeIntermediatePage*>(layer_root);
   return peek_volatile_page_boundaries_this_layer_recurse(cur, resolver, args);
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ErrorCode foedus::storage::masstree::MasstreeStoragePimpl::peek_volatile_page_boundaries_this_layer_recurse	(	const MasstreeIntermediatePage *	cur,
		const memory::GlobalVolatilePageResolver &	resolver,
		const MasstreeStorage::PeekBoundariesArguments &	args
	)

Definition at line 161 of file masstree_storage_peek.cpp.

Referenced by peek_volatile_page_boundaries_this_layer().

                                                       {
   ASSERT_ND(!cur->header().snapshot_);
   ASSERT_ND(!cur->is_border());
   ASSERT_ND(cur->get_layer() == args.prefix_slice_count_);
   // because of concurrent modifications, this is possible. we just give up finding hints.
   if (UNLIKELY(cur->get_low_fence() >= args.to_ || cur->get_high_fence() <= args.from_)) {
     return kErrorCodeOk;
   }
 
   uint8_t begin_index = 0;
   uint8_t begin_mini_index = 0;
   if (cur->within_fences(args.from_)) {
     begin_index = cur->find_minipage(args.from_);
     const MasstreeIntermediatePage::MiniPage& minipage = cur->get_minipage(begin_index);
     minipage.prefetch();
     begin_mini_index = minipage.find_pointer(args.from_);
   }
 
   // if children of this page are intermediate pages (this level>=2), we further recurse.
   // if children of this page are border pages, just append the page boundaries stored in this page.
   const bool needs_recurse = (cur->get_btree_level() >= 2U);
   // we don't care wherther the child has foster twins. it's rare, and most keys are already
   // pushed up to this page. again, this method is opportunistic.
   // this guarantees that the cost of peeking is cheap. we just read intermediate pages.
   // again, this code is not protected from concurrent transactions at all.
   // we just make sure it doesn't hit segfault etc.
   MasstreeIntermediatePointerIterator it(cur);
   it.index_ = begin_index;
   it.index_mini_ = begin_mini_index;
   for (; it.is_valid(); it.next()) {
     VolatilePagePointer pointer = it.get_pointer().volatile_pointer_;
     KeySlice boundary = it.get_low_key();
     if (boundary >= args.to_) {  // all pages under the pointer are >= boundary.
       break;
     }
     if (boundary > args.from_) {
       // at least guarantee that the resulting found_boundaries_ is ordered.
       if ((*args.found_boundary_count_) == 0
         || args.found_boundaries_[(*args.found_boundary_count_) - 1U] < boundary) {
         ASSERT_ND((*args.found_boundary_count_) < args.found_boundary_capacity_);
         args.found_boundaries_[*args.found_boundary_count_] = boundary;
         ++(*args.found_boundary_count_);
         if ((*args.found_boundary_count_) >= args.found_boundary_capacity_) {
           VLOG(0) << "Found too many boundaries while peeking. stops here.";
           return kErrorCodeOk;
         }
       }
     }
     // recurse to find more. note that it might contain pages of interest
     // even if boundary < args.from_ because it's a *low*-fence.
     if (needs_recurse && !pointer.is_null()) {
       if (LIKELY(pointer.get_numa_node() < resolver.numa_node_count_
         && pointer.get_offset() >= resolver.begin_
         && pointer.get_offset() < resolver.end_)) {
         const MasstreeIntermediatePage* next
           = reinterpret_cast<const MasstreeIntermediatePage*>(resolver.resolve_offset(pointer));
         if (next->is_border()) {
           // this is possible because our masstree might be unbalanced.
           ASSERT_ND(cur->get_layer() == 0);  // but it can happen only at first layer's root
           ASSERT_ND(cur->get_low_fence() == kInfimumSlice && cur->is_high_fence_supremum());
           continue;
         }
         ASSERT_ND(next->header().get_page_type() == kMasstreeIntermediatePageType);
         CHECK_ERROR_CODE(peek_volatile_page_boundaries_this_layer_recurse(next, resolver, args));
         ASSERT_ND((*args.found_boundary_count_) <= args.found_boundary_capacity_);
         if ((*args.found_boundary_count_) >= args.found_boundary_capacity_) {
           return kErrorCodeOk;
         }
       }
     }
   }
 
   return kErrorCodeOk;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ErrorCode foedus::storage::masstree::MasstreeStoragePimpl::prefetch_pages_follow	(	thread::Thread *	context,
		DualPagePointer *	pointer,
		bool	vol_on,
		bool	snp_on,
		KeySlice	from,
		KeySlice	to
	)

Definition at line 112 of file masstree_storage_prefetch.cpp.

References ASSERT_ND, CHECK_ERROR_CODE, foedus::thread::Thread::find_or_read_a_snapshot_page(), foedus::thread::Thread::install_a_volatile_page(), foedus::storage::VolatilePagePointer::is_null(), foedus::kErrorCodeOk, foedus::storage::prefetch_page_l2(), prefetch_pages_normalized_recurse(), foedus::thread::Thread::resolve_cast(), foedus::storage::DualPagePointer::snapshot_pointer_, foedus::storage::to_page(), and foedus::storage::DualPagePointer::volatile_pointer_.

Referenced by prefetch_pages_normalized_recurse().

                {
   // first, do we have to cache snapshot page?
   if (pointer->snapshot_pointer_ != 0) {
     if (snp_on) {
       MasstreePage* child;
       CHECK_ERROR_CODE(context->find_or_read_a_snapshot_page(
         pointer->snapshot_pointer_,
         reinterpret_cast<Page**>(&child)));
       prefetch_page_l2(child);
       CHECK_ERROR_CODE(prefetch_pages_normalized_recurse(
         context,
         false,
         snp_on,
         from,
         to,
         child));
     }
     // do we have to install volatile page based on it?
     if (pointer->volatile_pointer_.is_null() && vol_on) {
       ASSERT_ND(!to_page(pointer)->get_header().snapshot_);
       Page* child;
       CHECK_ERROR_CODE(context->install_a_volatile_page(pointer, &child));
     }
   }
 
   // then go down
   if (!pointer->volatile_pointer_.is_null() && vol_on) {
     ASSERT_ND(!to_page(pointer)->get_header().snapshot_);
     MasstreePage* child = context->resolve_cast<MasstreePage>(pointer->volatile_pointer_);
     prefetch_page_l2(child);
     CHECK_ERROR_CODE(prefetch_pages_normalized_recurse(
       context,
       vol_on,
       snp_on,
       from,
       to,
       child));
   }
   return kErrorCodeOk;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ErrorCode foedus::storage::masstree::MasstreeStoragePimpl::prefetch_pages_normalized	(	thread::Thread *	context,
		bool	install_volatile,
		bool	cache_snapshot,
		KeySlice	from,
		KeySlice	to
	)

defined in masstree_storage_prefetch.cpp

Definition at line 30 of file masstree_storage_prefetch.cpp.

References CHECK_ERROR_CODE, foedus::debugging::StopWatch::elapsed_us(), get_first_root(), get_name(), foedus::thread::Thread::get_thread_id(), foedus::kErrorCodeOk, foedus::storage::prefetch_page_l2(), prefetch_pages_normalized_recurse(), and foedus::debugging::StopWatch::stop().

Referenced by foedus::storage::masstree::MasstreeStorage::prefetch_pages_normalized().

                {
   debugging::StopWatch watch;
   VLOG(0) << "Thread-" << context->get_thread_id()
     << " prefetching " << get_name() << " from=" << from << ", to=" << to;
 
   MasstreeIntermediatePage* root_page;
   CHECK_ERROR_CODE(get_first_root(context, false, &root_page));
   prefetch_page_l2(root_page);
   CHECK_ERROR_CODE(prefetch_pages_normalized_recurse(context, vol_on, snp_on, from, to, root_page));
 
   watch.stop();
   VLOG(0) << "Thread-" << context->get_thread_id()
     << " prefetched " << get_name() << " in " << watch.elapsed_us() << "us";
   return kErrorCodeOk;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ErrorCode foedus::storage::masstree::MasstreeStoragePimpl::prefetch_pages_normalized_recurse	(	thread::Thread *	context,
		bool	install_volatile,
		bool	cache_snapshot,
		KeySlice	from,
		KeySlice	to,
		MasstreePage *	page
	)

Definition at line 51 of file masstree_storage_prefetch.cpp.

Referenced by prefetch_pages_follow(), and prefetch_pages_normalized().

                    {
   if (p->is_empty_range()) {
     return kErrorCodeOk;
   }
 
   if (p->has_foster_child()) {
     MasstreePage* minor = context->resolve_cast<MasstreePage>(p->get_foster_minor());
     MasstreePage* major = context->resolve_cast<MasstreePage>(p->get_foster_major());
     CHECK_ERROR_CODE(prefetch_pages_normalized_recurse(context, vol_on, snp_on, from, to, minor));
     CHECK_ERROR_CODE(prefetch_pages_normalized_recurse(context, vol_on, snp_on, from, to, major));
     return kErrorCodeOk;
   }
 
   uint8_t count = p->get_key_count();
   if (p->is_border()) {
     MasstreeBorderPage* page = reinterpret_cast<MasstreeBorderPage*>(p);
     for (uint8_t i = 0; i < count; ++i) {
       if (page->does_point_to_layer(i) && page->get_slice(i) >= from && page->get_slice(i) <= to) {
         DualPagePointer* pointer = page->get_next_layer(i);
         // next layer. exhaustively read
         CHECK_ERROR_CODE(prefetch_pages_follow(
           context,
           pointer,
           vol_on,
           snp_on,
           kInfimumSlice,
           kSupremumSlice));
       }
     }
   } else {
     MasstreeIntermediatePage* page = reinterpret_cast<MasstreeIntermediatePage*>(p);
     for (uint8_t i = 0; i <= count; ++i) {
       if (i < count && page->get_separator(i) >= from) {
         continue;
       }
       if (i > 0 && page->get_separator(i - 1) > to) {
         break;
       }
       MasstreeIntermediatePage::MiniPage& minipage = page->get_minipage(i);
       for (uint8_t j = 0; j <= minipage.key_count_; ++j) {
         if (j < minipage.key_count_ && minipage.separators_[j] >= from) {
           continue;
         }
         if (j > 0 && minipage.separators_[j - 1] > to) {
           break;
         }
         DualPagePointer* pointer = &minipage.pointers_[j];
         // next layer. exhaustively read
         CHECK_ERROR_CODE(prefetch_pages_follow(context, pointer, vol_on, snp_on, from, to));
       }
     }
   }
   return kErrorCodeOk;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ErrorCode foedus::storage::masstree::MasstreeStoragePimpl::register_record_write_log	(	thread::Thread *	context,
		const RecordLocation &	location,
		log::RecordLogType *	log_entry
	)

Used in the following methods.

Definition at line 645 of file masstree_storage_pimpl.cpp.

References foedus::xct::Xct::add_related_write_set(), foedus::xct::Xct::add_to_write_set(), foedus::thread::Thread::get_current_xct(), get_id(), foedus::storage::masstree::MasstreeBorderPage::get_owner_id(), foedus::storage::masstree::MasstreeBorderPage::get_record(), foedus::storage::masstree::RecordLocation::index_, foedus::storage::masstree::RecordLocation::page_, and foedus::storage::masstree::RecordLocation::readset_.

Referenced by delete_general(), increment_general(), insert_general(), overwrite_general(), and upsert_general().

                                {
   // If we have taken readset in locate_record, add as a related write set
   MasstreeBorderPage* border = location.page_;
   auto* tid = border->get_owner_id(location.index_);
   char* record = border->get_record(location.index_);
   xct::Xct* cur_xct = &context->get_current_xct();
   if (location.readset_) {
     return cur_xct->add_related_write_set(location.readset_, tid, record, log_entry);
   } else {
     return cur_xct->add_to_write_set(get_id(), tid, record, log_entry);
   }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ErrorCode foedus::storage::masstree::MasstreeStoragePimpl::reserve_record	(	thread::Thread *	context,
		const void *	key,
		KeyLength	key_length,
		PayloadLength	payload_count,
		PayloadLength	physical_payload_hint,
		RecordLocation *	result
	)

Like locate_record(), this is also a logical operation.

Definition at line 412 of file masstree_storage_pimpl.cpp.

Referenced by foedus::storage::masstree::MasstreeStorage::insert_record(), and foedus::storage::masstree::MasstreeStorage::upsert_record().

                           {
   ASSERT_ND(key_length <= kMaxKeyLength);
   ASSERT_ND(physical_payload_hint >= payload_count);
   ASSERT_ND(result);
   result->clear();
   xct::Xct* cur_xct = &context->get_current_xct();
 
   MasstreePage* layer_root;
   CHECK_ERROR_CODE(get_first_root(
     context,
     true,
     reinterpret_cast<MasstreeIntermediatePage**>(&layer_root)));
   for (uint16_t layer = 0;; ++layer) {
     const KeyLength remainder = key_length - layer * sizeof(KeySlice);
     const KeySlice slice = slice_layer(key, key_length, layer);
     const void* const suffix = reinterpret_cast<const char*>(key) + (layer + 1) * sizeof(KeySlice);
     MasstreeBorderPage* border;
     CHECK_ERROR_CODE(find_border_physical(context, layer_root, layer, true, slice, &border));
     while (true) {  // retry loop for following foster child and temporary failure
       // if we found out that the page was split and we should follow foster child, do it.
       while (border->has_foster_child()) {
         if (border->within_foster_minor(slice)) {
           border = context->resolve_cast<MasstreeBorderPage>(border->get_foster_minor());
         } else {
           border = context->resolve_cast<MasstreeBorderPage>(border->get_foster_major());
         }
       }
       ASSERT_ND(border->within_fences(slice));
 
       const SlotIndex count = border->get_key_count();
       // ReserveRecords, we need a fence on BOTH sides.
       // observe key count first, then verify the keys.
       assorted::memory_fence_acquire();
       MasstreeBorderPage::FindKeyForReserveResult match = border->find_key_for_reserve(
         0,
         count,
         slice,
         suffix,
         remainder);
 
       if (match.match_type_ == MasstreeBorderPage::kExactMatchLayerPointer) {
         ASSERT_ND(match.index_ < kBorderPageMaxSlots);
         CHECK_ERROR_CODE(follow_layer(context, true, border, match.index_, &layer_root));
         break;  // next layer
       } else if (match.match_type_ == MasstreeBorderPage::kExactMatchLocalRecord) {
         // Even in this case, if the record space is too small, we must migrate it first.
         if (border->get_max_payload_length(match.index_) >= payload_count) {
           // Ok, this seems to already satisfy our need. but...
           // Up until now, all the searches/expands were physical-only.
           // Now we finalize the XID in the search result so that precommit will
           // catch any change since now. This also means we need to re-check
           // the status again, and retry if pointing to next layer or moved.
           CHECK_ERROR_CODE(result->populate_logical(cur_xct, border, match.index_, true));
           if (result->observed_.is_next_layer() || result->observed_.is_moved()) {
             // because the search is optimistic, we might now see a XctId with next-layer bit on.
             // in this case, we retry.
             VLOG(0) << "Interesting. Next-layer-retry due to concurrent transaction";
             assorted::memory_fence_acquire();
             continue;
           }
           return kErrorCodeOk;
         }
       }
 
       // In all other cases, we (probably) need to do something complex.
       // ReserveRecords sysxct does it.
       ReserveRecords reserve(
         context,
         border,
         slice,
         remainder,
         suffix,
         physical_payload_hint,  // let's allocate conservatively
         get_meta().should_aggresively_create_next_layer(layer, remainder),
         match.match_type_ == MasstreeBorderPage::kNotFound ? count : match.index_);
       CHECK_ERROR_CODE(context->run_nested_sysxct(&reserve, 2U));
 
       // We might need to split the page
       if (reserve.out_split_needed_) {
         SplitBorder split(
           context,
           border,
           slice,
           false,
           true,
           remainder,
           physical_payload_hint,
           suffix);
         CHECK_ERROR_CODE(context->run_nested_sysxct(&split, 2U));
       }
 
       // In either case, we should resume the search.
       continue;
     }
   }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ErrorCode foedus::storage::masstree::MasstreeStoragePimpl::reserve_record_normalized	(	thread::Thread *	context,
		KeySlice	key,
		PayloadLength	payload_count,
		PayloadLength	physical_payload_hint,
		RecordLocation *	result
	)

Definition at line 515 of file masstree_storage_pimpl.cpp.

Referenced by foedus::storage::masstree::MasstreeStorage::insert_record_normalized(), and foedus::storage::masstree::MasstreeStorage::upsert_record_normalized().

                           {
   ASSERT_ND(result);
   result->clear();
   xct::Xct* cur_xct = &context->get_current_xct();
   MasstreeBorderPage* border;
 
   MasstreeIntermediatePage* layer_root;
   CHECK_ERROR_CODE(get_first_root(context, true, &layer_root));
   CHECK_ERROR_CODE(find_border_physical(context, layer_root, 0, true, key, &border));
   while (true) {  // retry loop for following foster child
     // if we found out that the page was split and we should follow foster child, do it.
     while (border->has_foster_child()) {
       if (border->within_foster_minor(key)) {
         border = context->resolve_cast<MasstreeBorderPage>(border->get_foster_minor());
       } else {
         border = context->resolve_cast<MasstreeBorderPage>(border->get_foster_major());
       }
     }
 
     ASSERT_ND(border->within_fences(key));
 
     // because we never go on to second layer in this case, it's either a full match or not-found
     const SlotIndex count = border->get_key_count();
     assorted::memory_fence_acquire();
     const SlotIndex index = border->find_key_normalized(0, count, key);
 
     if (index != kBorderPageMaxSlots) {
       // If the record space is too small, we can't insert.
       if (border->get_max_payload_length(index) >= payload_count) {
         CHECK_ERROR_CODE(result->populate_logical(cur_xct, border, index, true));
         if (result->observed_.is_moved()) {
           // because the search is optimistic, we might now see a XctId with next-layer bit on.
           // in this case, we retry.
           VLOG(0) << "Interesting. Moved by concurrent transaction";
           assorted::memory_fence_acquire();
           continue;
         }
         return kErrorCodeOk;
       }
     }
 
     // Same as the general case.
     ReserveRecords reserve(
       context,
       border,
       key,
       sizeof(KeySlice),
       nullptr,
       physical_payload_hint,
       false,
       index == kBorderPageMaxSlots ? count : index);
     CHECK_ERROR_CODE(context->run_nested_sysxct(&reserve, 2U));
 
     if (reserve.out_split_needed_) {
       SplitBorder split(
         context,
         border,
         key,
         false,
         true,
         sizeof(KeySlice),
         physical_payload_hint,
         nullptr);
       CHECK_ERROR_CODE(context->run_nested_sysxct(&split, 2U));
     }
     continue;
   }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ErrorCode foedus::storage::masstree::MasstreeStoragePimpl::retrieve_general	(	thread::Thread *	context,
		const RecordLocation &	location,
		void *	payload,
		PayloadLength *	payload_capacity
	)

implementation of get_record family.

use with locate_record()

Definition at line 599 of file masstree_storage_pimpl.cpp.

References CHECK_ERROR_CODE, check_next_layer_bit(), foedus::storage::masstree::MasstreeBorderPage::get_payload_length(), foedus::storage::masstree::MasstreeBorderPage::get_record_payload(), foedus::storage::masstree::RecordLocation::index_, foedus::xct::XctId::is_deleted(), foedus::kErrorCodeOk, foedus::kErrorCodeStrKeyNotFound, foedus::kErrorCodeStrTooSmallPayloadBuffer, foedus::storage::masstree::RecordLocation::observed_, and foedus::storage::masstree::RecordLocation::page_.

Referenced by foedus::storage::masstree::MasstreeStorage::get_record(), and foedus::storage::masstree::MasstreeStorage::get_record_normalized().

                                    {
   if (location.observed_.is_deleted()) {
     // This result is protected by readset
     return kErrorCodeStrKeyNotFound;
   }
   CHECK_ERROR_CODE(check_next_layer_bit(location.observed_));
 
   // here, we do NOT have to do another optimistic-read protocol because we already took
   // the owner_id into read-set. If this read is corrupted, we will be aware of it at commit time.
   MasstreeBorderPage* border = location.page_;
   PayloadLength payload_length = border->get_payload_length(location.index_);
   if (payload_length > *payload_capacity) {
     // buffer too small
     DVLOG(0) << "buffer too small??" << payload_length << ":" << *payload_capacity;
     *payload_capacity = payload_length;
     return kErrorCodeStrTooSmallPayloadBuffer;
   }
   *payload_capacity = payload_length;
   std::memcpy(payload, border->get_record_payload(location.index_), payload_length);
   return kErrorCodeOk;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ErrorCode foedus::storage::masstree::MasstreeStoragePimpl::retrieve_part_general	(	thread::Thread *	context,
		const RecordLocation &	location,
		void *	payload,
		PayloadLength	payload_offset,
		PayloadLength	payload_count
	)

Definition at line 625 of file masstree_storage_pimpl.cpp.

References CHECK_ERROR_CODE, check_next_layer_bit(), foedus::storage::masstree::MasstreeBorderPage::get_payload_length(), foedus::storage::masstree::MasstreeBorderPage::get_record_payload(), foedus::storage::masstree::RecordLocation::index_, foedus::xct::XctId::is_deleted(), foedus::kErrorCodeOk, foedus::kErrorCodeStrKeyNotFound, foedus::kErrorCodeStrTooShortPayload, foedus::storage::masstree::RecordLocation::observed_, and foedus::storage::masstree::RecordLocation::page_.

Referenced by foedus::storage::masstree::MasstreeStorage::get_record_part(), foedus::storage::masstree::MasstreeStorage::get_record_part_normalized(), foedus::storage::masstree::MasstreeStorage::get_record_primitive(), and foedus::storage::masstree::MasstreeStorage::get_record_primitive_normalized().

                                 {
   if (location.observed_.is_deleted()) {
     // This result is protected by readset
     return kErrorCodeStrKeyNotFound;
   }
   CHECK_ERROR_CODE(check_next_layer_bit(location.observed_));
   MasstreeBorderPage* border = location.page_;
   if (border->get_payload_length(location.index_) < payload_offset + payload_count) {
     LOG(WARNING) << "short record";  // probably this is a rare error. so warn.
     return kErrorCodeStrTooShortPayload;
   }
   std::memcpy(payload, border->get_record_payload(location.index_) + payload_offset, payload_count);
   return kErrorCodeOk;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

xct::TrackMovedRecordResult foedus::storage::masstree::MasstreeStoragePimpl::track_moved_record	(	xct::RwLockableXctId *	old_address,
		xct::WriteXctAccess *	write_set
	)

inline

Definition at line 848 of file masstree_storage_pimpl.cpp.

References ASSERT_ND, foedus::Attachable< MasstreeStorageControlBlock >::engine_, foedus::storage::masstree::MasstreePage::is_border(), foedus::storage::masstree::MasstreePage::is_moved(), foedus::xct::RwLockableXctId::is_next_layer(), foedus::storage::to_page(), and foedus::storage::masstree::MasstreeBorderPage::track_moved_record().

Referenced by foedus::storage::masstree::MasstreeStorage::track_moved_record().

                                 {
   ASSERT_ND(old_address);
   // We use moved bit only for volatile border pages
   MasstreeBorderPage* page = reinterpret_cast<MasstreeBorderPage*>(to_page(old_address));
   ASSERT_ND(page->is_border());
   ASSERT_ND(page->is_moved() || old_address->is_next_layer());
   return page->track_moved_record(engine_, old_address, write_set);
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ErrorCode foedus::storage::masstree::MasstreeStoragePimpl::upsert_general	(	thread::Thread *	context,
		const RecordLocation &	location,
		const void *	be_key,
		KeyLength	key_length,
		const void *	payload,
		PayloadLength	payload_count
	)

implementation of upsert_record family.

use with reserve_record()

Definition at line 711 of file masstree_storage_pimpl.cpp.

Referenced by foedus::storage::masstree::MasstreeStorage::upsert_record(), and foedus::storage::masstree::MasstreeStorage::upsert_record_normalized().

                                 {
   // Upsert is a combination of what insert does and what delete does.
   // If there isn't an existing physical record, it's exactly same as insert.
   // If there is, it's _basically_ a delete followed by an insert.
   // There are a few complications, depending on the status of the record.
   CHECK_ERROR_CODE(check_next_layer_bit(location.observed_));
 
   // as of reserve_record() it was spacious enough, and this length is
   // either immutable or only increases, so this must hold.
   MasstreeBorderPage* border = location.page_;
   ASSERT_ND(border->get_max_payload_length(location.index_) >= payload_count);
 
   MasstreeCommonLogType* common_log;
   if (location.observed_.is_deleted()) {
     // If it's a deleted record, this turns to be a plain insert.
     uint16_t log_length = MasstreeInsertLogType::calculate_log_length(key_length, payload_count);
     MasstreeInsertLogType* log_entry = reinterpret_cast<MasstreeInsertLogType*>(
       context->get_thread_log_buffer().reserve_new_log(log_length));
     log_entry->populate(
       get_id(),
       be_key,
       key_length,
       payload,
       payload_count);
     common_log = log_entry;
   } else if (payload_count == border->get_payload_length(location.index_)) {
     // If it's not changing payload size of existing record, we can conver it to an overwrite,
     // which is more efficient
     uint16_t log_length = MasstreeOverwriteLogType::calculate_log_length(key_length, payload_count);
     MasstreeOverwriteLogType* log_entry = reinterpret_cast<MasstreeOverwriteLogType*>(
       context->get_thread_log_buffer().reserve_new_log(log_length));
     log_entry->populate(
       get_id(),
       be_key,
       key_length,
       payload,
       0,
       payload_count);
     common_log = log_entry;
   } else {
     // If not, this is an update operation.
     uint16_t log_length = MasstreeUpdateLogType::calculate_log_length(key_length, payload_count);
     MasstreeUpdateLogType* log_entry = reinterpret_cast<MasstreeUpdateLogType*>(
       context->get_thread_log_buffer().reserve_new_log(log_length));
     log_entry->populate(
       get_id(),
       be_key,
       key_length,
       payload,
       payload_count);
     common_log = log_entry;
   }
   border->header().stat_last_updater_node_ = context->get_numa_node();
   return register_record_write_log(context, location, common_log);
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ErrorStack foedus::storage::masstree::MasstreeStoragePimpl::verify_single_thread ( thread::Thread * context )

These are defined in masstree_storage_verify.cpp.

Definition at line 39 of file masstree_storage_verify.cpp.

References CHECK_AND_ASSERT, CHECK_ERROR, get_first_root(), foedus::storage::masstree::MasstreePage::is_border(), foedus::kRetOk, verify_single_thread_layer(), and WRAP_ERROR_CODE.

Referenced by foedus::storage::masstree::MasstreeStorage::verify_single_thread().

                                                                            {
   MasstreeIntermediatePage* layer_root;
   WRAP_ERROR_CODE(get_first_root(context, false, &layer_root));
   CHECK_AND_ASSERT(!layer_root->is_border());  // root of first layer is always intermediate page
   CHECK_ERROR(verify_single_thread_layer(context, 0, layer_root));
   return kRetOk;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ErrorStack foedus::storage::masstree::MasstreeStoragePimpl::verify_single_thread_border	(	thread::Thread *	context,
		KeySlice	low_fence,
		HighFence	high_fence,
		MasstreeBorderPage *	page
	)

Definition at line 201 of file masstree_storage_verify.cpp.

Referenced by verify_single_thread_intermediate(), and verify_single_thread_layer().

                             {
   CHECK_ERROR(verify_page_basic(context, page, kMasstreeBorderPageType, low_fence, high_fence));
   // check consecutive_inserts_. this should be consistent whether it's moved or not.
   bool sorted = true;
   for (SlotIndex i = 1; i < page->get_key_count(); ++i) {
     KeySlice prev = page->get_slice(i - 1);
     KeySlice slice = page->get_slice(i);
     KeyLength prev_len = page->get_remainder_length(i - 1);
     KeyLength len = page->get_remainder_length(i);
     if (prev > slice || (prev == slice && prev_len > len)) {
       sorted = false;
       break;
     }
   }
   CHECK_AND_ASSERT(page->is_consecutive_inserts() == sorted);
 
   if (page->is_moved()) {
     auto* minor = context->resolve_cast<MasstreeBorderPage>(page->get_foster_minor());
     auto* major = context->resolve_cast<MasstreeBorderPage>(page->get_foster_major());
     // If major is empty-range, the minor might be supremum
     bool is_minor_supremum = high_fence.supremum_ && page->get_foster_fence() == kSupremumSlice;
     CHECK_ERROR(verify_single_thread_border(
       context,
       low_fence,
       HighFence(page->get_foster_fence(), is_minor_supremum),
       minor));
     CHECK_ERROR(verify_single_thread_border(
       context,
       page->get_foster_fence(),
       high_fence,
       major));
     return kRetOk;
   }
 
   CHECK_AND_ASSERT(!page->is_moved());
   CHECK_AND_ASSERT(page->get_key_count() <= kBorderPageMaxSlots);
   for (SlotIndex i = 0; i < page->get_key_count(); ++i) {
     CHECK_AND_ASSERT(!page->get_owner_id(i)->lock_.is_locked());
     CHECK_AND_ASSERT(!page->get_owner_id(i)->xct_id_.is_being_written());
     CHECK_AND_ASSERT(page->get_owner_id(i)->xct_id_.get_epoch().is_valid());
     CHECK_AND_ASSERT(page->verify_slot_lengthes(i));
     KeySlice slice = page->get_slice(i);
     CHECK_AND_ASSERT(slice >= low_fence);
     CHECK_AND_ASSERT(slice < high_fence.slice_ || page->is_high_fence_supremum());
     if (page->does_point_to_layer(i)) {
       CHECK_AND_ASSERT(page->get_owner_id(i)->xct_id_.is_next_layer());
       CHECK_AND_ASSERT(!page->get_next_layer(i)->is_both_null());
       MasstreePage* next;
       // TASK(Hideaki) probably two versions: always follow volatile vs snapshot
       // so far check volatile only
       WRAP_ERROR_CODE(follow_page(context, true, page->get_next_layer(i), &next));
       CHECK_ERROR(verify_single_thread_layer(context, page->get_layer() + 1, next));
     } else {
       CHECK_AND_ASSERT(!page->get_owner_id(i)->xct_id_.is_next_layer());
     }
   }
 
   return kRetOk;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ErrorStack foedus::storage::masstree::MasstreeStoragePimpl::verify_single_thread_intermediate	(	thread::Thread *	context,
		KeySlice	low_fence,
		HighFence	high_fence,
		MasstreeIntermediatePage *	page
	)

Definition at line 103 of file masstree_storage_verify.cpp.

Referenced by verify_single_thread_layer().

                                   {
   CHECK_ERROR(
     verify_page_basic(context, page, kMasstreeIntermediatePageType, low_fence, high_fence));
 
   if (page->is_empty_range()) {
     CHECK_AND_ASSERT(page->get_key_count() == 0);
     CHECK_AND_ASSERT(!page->is_moved());
     return kRetOk;
   }
 
   if (page->is_moved()) {
     auto* minor = context->resolve_cast<MasstreeIntermediatePage>(page->get_foster_minor());
     auto* major = context->resolve_cast<MasstreeIntermediatePage>(page->get_foster_major());
     // If major is empty-range, the minor might be supremum
     bool is_minor_supremum = high_fence.supremum_ && page->get_foster_fence() == kSupremumSlice;
     CHECK_ERROR(verify_single_thread_intermediate(
       context,
       low_fence,
       HighFence(page->get_foster_fence(), is_minor_supremum),
       minor));
     CHECK_ERROR(verify_single_thread_intermediate(
       context,
       page->get_foster_fence(),
       high_fence,
       major));
     return kRetOk;
   }
 
   uint8_t key_count = page->get_key_count();
   CHECK_AND_ASSERT(key_count <= kMaxIntermediateSeparators);
   KeySlice previous_low = low_fence;
   for (uint8_t i = 0; i <= key_count; ++i) {
     HighFence mini_high(0, false);
     if (i < key_count) {
       mini_high.slice_ = page->get_separator(i);
       mini_high.supremum_ = false;
       CHECK_AND_ASSERT(high_fence.supremum_ || mini_high.slice_ < high_fence.slice_);
       if (i == 0) {
         CHECK_AND_ASSERT(mini_high.slice_ > low_fence);
       } else {
         CHECK_AND_ASSERT(mini_high.slice_ > page->get_separator(i - 1));
       }
     } else {
       mini_high = high_fence;
     }
 
     MasstreeIntermediatePage::MiniPage& minipage = page->get_minipage(i);
     uint8_t mini_count = minipage.key_count_;
     CHECK_AND_ASSERT(mini_count <= kMaxIntermediateMiniSeparators);
     KeySlice page_low = previous_low;
     for (uint8_t j = 0; j <= mini_count; ++j) {
       HighFence page_high(0, false);
       if (j < mini_count) {
         page_high.slice_ = minipage.separators_[j];
         page_high.supremum_ = false;
         CHECK_AND_ASSERT(page_high.slice_ < mini_high.slice_ || mini_high.supremum_);
         if (j == 0) {
           CHECK_AND_ASSERT(page_high.slice_ > previous_low);
         } else {
           CHECK_AND_ASSERT(page_high.slice_ > minipage.separators_[j - 1]);
         }
       } else {
         page_high = mini_high;
       }
       CHECK_AND_ASSERT(!minipage.pointers_[j].is_both_null());
       MasstreePage* next;
       // TASK(Hideaki) probably two versions: always follow volatile vs snapshot
       // so far check volatile only
       WRAP_ERROR_CODE(follow_page(context, true, &minipage.pointers_[j], &next));
       CHECK_AND_ASSERT(next->get_layer() == page->get_layer());
       CHECK_AND_ASSERT(next->get_btree_level() + 1U == page->get_btree_level());
       if (next->is_border()) {
         CHECK_ERROR(verify_single_thread_border(
           context,
           page_low,
           page_high,
           reinterpret_cast<MasstreeBorderPage*>(next)));
       } else {
         CHECK_ERROR(verify_single_thread_intermediate(
           context,
           page_low,
           page_high,
           reinterpret_cast<MasstreeIntermediatePage*>(next)));
       }
 
       page_low = page_high.slice_;
     }
 
     previous_low = mini_high.slice_;
   }
 
   return kRetOk;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ErrorStack foedus::storage::masstree::MasstreeStoragePimpl::verify_single_thread_layer	(	thread::Thread *	context,
		uint8_t	layer,
		MasstreePage *	layer_root
	)

Definition at line 47 of file masstree_storage_verify.cpp.

References CHECK_AND_ASSERT, CHECK_ERROR, foedus::storage::masstree::MasstreePage::get_layer(), foedus::storage::masstree::MasstreePage::is_border(), foedus::storage::masstree::kInfimumSlice, foedus::kRetOk, foedus::storage::masstree::kSupremumSlice, verify_single_thread_border(), and verify_single_thread_intermediate().

Referenced by verify_single_thread(), and verify_single_thread_border().

                             {
   CHECK_AND_ASSERT(layer_root->get_layer() == layer);
   HighFence high_fence(kSupremumSlice, true);
   if (layer_root->is_border()) {
     CHECK_ERROR(verify_single_thread_border(
       context,
       kInfimumSlice,
       high_fence,
       reinterpret_cast<MasstreeBorderPage*>(layer_root)));
   } else {
     CHECK_ERROR(verify_single_thread_intermediate(
       context,
       kInfimumSlice,
       high_fence,
       reinterpret_cast<MasstreeIntermediatePage*>(layer_root)));
   }
   return kRetOk;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

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

/home/shino/foedus_code/foedus-core/include/foedus/storage/masstree/masstree_storage_pimpl.hpp
/home/shino/foedus_code/foedus-core/src/foedus/storage/masstree/masstree_storage_debug.cpp
/home/shino/foedus_code/foedus-core/src/foedus/storage/masstree/masstree_storage_fatify.cpp
/home/shino/foedus_code/foedus-core/src/foedus/storage/masstree/masstree_storage_peek.cpp
/home/shino/foedus_code/foedus-core/src/foedus/storage/masstree/masstree_storage_pimpl.cpp
/home/shino/foedus_code/foedus-core/src/foedus/storage/masstree/masstree_storage_prefetch.cpp
/home/shino/foedus_code/foedus-core/src/foedus/storage/masstree/masstree_storage_verify.cpp

Detailed Description

Public Member Functions

Static Public Member Functions

Additional Inherited Members

Constructor & Destructor Documentation

Member Function Documentation