Masstree Storage, 64-bit B-tries with internal B-trees. More...

Detailed Description

Masstree Storage, 64-bit B-tries with internal B-trees.

Although the package name says masstree [YANDONG12], we call our implementation Master-Tree. There are a few differences from the original Masstree.

Foster-Twin

See our paper (lame, yes).

Remainder vs Remaining Key

Througout our code, we always use the word remainder rather than remaining-key. In [YANDONG12] and [TU13], the word remaining-key meant the leftover of the entire key after removing the common prefixes in previous B-trie layers. For example, key "abcd" has remaining key "abcd" in layer-0. key "abcd12345678" has remaining keys "abcd12345678" in layer-0 and "5678" in layer-1. When the length of remaining-key is more than 8-bytes, the page also stores suffix, which is the key part after the slice in the layer. For example, "abcd12345678" stores "5678" as suffix in layer-0 while no suffix in layer-1.

Up to here, there is no difference between remainder and remaining-key. Actually, in most cases they are exactly the same.

They differ only when a record points to next layer. In the original papers/codes, the length of remaining-key is set to be 255 when the record now points to next layer, and they also overwrite the area to store suffix with next-page pointer.

In Master-Tree, we always keep the remainder even when now it points to the next layer. This simplifies many concurrency control issues, especially our foster-twin tracking algorithm. Therefore, we never change the length of remainder. It's an immutable property of the record. Instead, we have an additional mutable boolean flag "next_layer" in TID. Whether the next_layer flag is ON or OFF, all threads are safe to access the remainder. The commit protocol checks the flag and aborts if it's unexpectedly ON.

This is just a subtle difference, but allthemore subtle, it's confusing! Hence, we use a different word, remainder. Below we summarize the differences:

.	Remaining Key (Mass-Tree)	Remainder (Master-Tree)
Length	Full key length - layer*8 if not next-layer, 255 if it's now next-layer.	Full key length - layer*8 always. Keeps the original remainder length.
Suffix stored at	The beginning of data region if not next-layer, overwritten if it's now next-layer.	The beginning of data region always. Keeps the original remainder.
Length 0xFFFF means	The record is now next-layer, so the record has no suffix-region. HOWEVER, concurrent threads must be careful because it was not 0xFFFF before.	The record was initially next-layer as of creation, so the record has no suffix-region. Such a record is never moved. A record that later turned to be next-layer doesn't use this value.

References

[YANDONG12] Yandong Mao, Eddie Kohler, and Robert Tappan Morris. "Cache craftiness for fast multicore key-value storage.", EuroSys, 2012.

[TU13] Stephen Tu, Wenting Zheng, Eddie Kohler, Barbara Liskov, and Samuel Madden. "Speedy transactions in multicore in-memory databases.", SOSP, 2013.

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

struct	GrowFirstLayerRoot
	A system transaction to grow a first-layer root. More...

struct	GrowNonFirstLayerRoot
	A system transaction to grow a second- or depper-layer root. More...

struct	HighFence
	Used only for debugging as this is not space efficient. More...

class	MasstreeBorderPage
	Represents one border page in Masstree Storage. More...

struct	MasstreeCommonLogType
	A base class for MasstreeInsertLogType/MasstreeDeleteLogType/MasstreeOverwriteLogType. More...

class	MasstreeComposeContext
	MasstreeComposer's compose() implementation separated from the class itself. More...

class	MasstreeComposer
	Composer for an masstree storage. More...

struct	MasstreeCreateLogType
	Log type of CREATE MASSTREE STORAGE operation. More...

class	MasstreeCursor
	Represents a cursor object for Masstree storage. More...

struct	MasstreeDeleteLogType
	Log type of masstree-storage's delete operation. More...

struct	MasstreeInsertLogType
	Log type of masstree-storage's insert operation. More...

class	MasstreeIntermediatePage
	Represents one intermediate page in Masstree Storage. More...

struct	MasstreeIntermediatePointerIterator
	Handy iterator for MasstreeIntermediate. More...

struct	MasstreeMetadata
	Metadata of a masstree storage. More...

struct	MasstreeMetadataSerializer

struct	MasstreeOverwriteLogType
	Log type of masstree-storage's overwrite operation. More...

class	MasstreePage
	Common base of MasstreeIntermediatePage and MasstreeBorderPage. More...

class	MasstreePartitioner
	Partitioner for a masstree storage. More...

struct	MasstreePartitionerData
	Dynamic information of one partitioner. More...

class	MasstreeStorage
	Represents a Masstree storage. More...

struct	MasstreeStorageControlBlock
	Shared data of this storage type. More...

class	MasstreeStoragePimpl
	Pimpl object of MasstreeStorage. More...

struct	MasstreeUpdateLogType
	Log type of masstree-storage's update operation. More...

struct	OwnerSamples
	Number of vol pages in each node sampled per pointer in the root page. More...

struct	RecordLocation
	return value of MasstreeStoragePimpl::locate_record()/reserve_record(). More...

struct	ReserveRecords
	A system transaction to reserve a physical record(s) in a border page. More...

struct	SortEntry
	Unlike array's sort entry, we don't always use this because keys are arbitrary lengthes. More...

struct	SplitBorder
	A system transaction to split a border page in Master-Tree. More...

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

Typedefs
typedef uint8_t	Layer
	Represents the depth of a B-trie layer. More...

typedef uint8_t	InLayerLevel
	Represents the depth of a B-tree node in a B-trie layer. More...

typedef uint16_t	KeyLength
	Represents a byte-length of a key in this package. More...

typedef uint16_t	PayloadLength
	Represents a byte-length of a payload in this package. More...

typedef uint16_t	DataOffset
	Byte-offset in a page. More...

typedef uint16_t	SlotIndex
	Index of a record in a (border) page. More...

typedef uint64_t	KeySlice
	Each key slice is an 8-byte integer. More...

Functions
template<typename T >
KeySlice	normalize_primitive (T value)
	Order-preserving normalization for primitive key types. More...

template<typename T >
T	denormalize_primitive (KeySlice value)
	Opposite of normalize_primitive(). More...

KeySlice	normalize_be_bytes_full_aligned (const void *be_bytes)
	Convert an aligned big-endian byte array of at least 8-bytes-length to KeySlice. More...

KeySlice	normalize_be_bytes_full (const void *be_bytes)
	Convert a big-endian byte array of at least 8-bytes-length to KeySlice. More...

KeySlice	normalize_be_bytes_fragment (const void *be_bytes, uint32_t length)
	Convert a big-endian byte array of given length to KeySlice. More...

KeySlice	slice_key (const void *be_bytes, KeyLength slice_length)
	Extract a part of a big-endian byte array of given length as KeySlice. More...

KeySlice	slice_layer (const void *be_bytes, KeyLength key_length, Layer current_layer)
	Extract a part of a big-endian byte array of given length as KeySlice. More...

uint16_t	count_common_slices (const void left, const void right, uint16_t max_slices)
	Returns the number of 8-byte slices that the two strings share as prefix. More...

bool	is_key_aligned_and_zero_padded (const char *key, KeyLength key_length)
	Returns if the given key is 8-bytes aligned and also zero-padded to 8-bytes for easier slicing (which most of our code does). More...

uint8_t	extract_page_layer (const void *in_page_pointer)
	Retrieve masstree layer information from the header of the page that contains the pointer. More...

KeyLength	calculate_suffix_length (KeyLength remainder_length) __attribute__((always_inline))

KeyLength	calculate_suffix_length_aligned (KeyLength remainder_length) __attribute__((always_inline))

void	_dummy_static_size_check__COUNTER__ ()

int	compare_keys (const char left, uint16_t left_length, const char right, uint16_t right_length)
	Local utility functions. More...

const MasstreeCommonLogType *	resolve_log (const snapshot::LogBuffer &log_buffer, snapshot::BufferPosition pos)

void	fill_payload_padded (char destination, const char source, PayloadLength count)

MasstreeBorderPage *	as_border (MasstreePage *page)

MasstreeIntermediatePage *	as_intermediate (MasstreePage *page)

bool	from_this_snapshot (SnapshotPagePointer pointer, const Composer::ConstructRootArguments &args)

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

void	copy_input_key (const char input_key, KeyLength length, char buffer, KeySlice *slice_buffer)

void	grow_case_a_common (thread::Thread context, DualPagePointer pointer, MasstreePage *cur_root)

ErrorCode	grow_case_b_common (thread::Thread context, DualPagePointer pointer, MasstreePage *cur_root)

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

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

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

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

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

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

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

void	describe_masstree_page_common (std::ostream *o_ptr, const MasstreePage &v)

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

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

void	release_parallel (Engine *engine, VolatilePagePointer pointer)

void	design_partition_first_parallel_recurse (const memory::GlobalVolatilePageResolver &resolver, const MasstreePage page, uint32_t subtree_id, OwnerSamples result, assorted::UniformRandom *unirand)

void	design_partition_first_parallel (Engine engine, VolatilePagePointer subtree, uint32_t subtree_id, OwnerSamples result)

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

void	retrieve_positions (uint32_t logs_count, const SortEntry entries, snapshot::BufferPosition out)
	subroutine of sort_batch_8bytes More...

void	prepare_sort_entries (const Partitioner::SortBatchArguments &args, SortEntry *entries)
	subroutine of sort_batch_8bytes More...

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

xct::XctId	get_initial_xid ()

MasstreeBorderPage *	allocate_new_border_page (thread::Thread *context)

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

PayloadLength	adjust_payload_hint (PayloadLength payload_count, PayloadLength physical_payload_hint)

uint32_t	count_children_approximate (const MasstreeIntermediatePage *page)

ErrorStack	verify_page_basic (thread::Thread context, MasstreePage page, PageType page_type, KeySlice low_fence, HighFence high_fence)

Variables
const Layer	kMaxLayer = 63U
	Maximum value for Layer. More...

const InLayerLevel	kMaxSaneInLayerLevel = 15U
	If InLayerLevel exceeds this value, there must be something wrong. More...

const KeyLength	kMaxKeyLength = 1024U
	Max length of a key. More...

const KeyLength	kInitiallyNextLayer = 0xFFFFU
	A special key length value that denotes the record in a border page was initially a next-layer pointer, thus the record has no suffix region. More...

const PayloadLength	kMaxPayloadLength = 1024U
	Max length of a payload. More...

const uint64_t	kSliceLen = sizeof(KeySlice)
	Shorthand for sizeof(KeySlice). More...

const KeySlice	kInfimumSlice = 0

const KeySlice	kSupremumSlice = 0xFFFFFFFFFFFFFFFFULL

const uint32_t	kCommonPageHeaderSize = 80U
	Size of the base page class (MasstreePage), which is the common header for intermediate and border pages placed at the beginning. More...

const uint32_t	kBorderPageAdditionalHeaderSize = 8U
	Misc header attributes specific to MasstreeBorderPage placed after the common header. More...

const uint32_t	kBorderPageSlotSize = 32U
	Byte size of one slot in MasstreeBorderPage excluding slice information. More...

const SlotIndex	kBorderPageMaxSlots
	Maximum number of slots in one MasstreeBorderPage. More...

const uint32_t	kBorderPageDataPartSize
	Byte size of the record data part (data_) in MasstreeBorderPage. More...

const DataOffset	kBorderPageDataPartOffset
	Offset of data_ member in MasstreeBorderPage. More...

const uint16_t	kMaxIntermediateSeparators = 9U
	Max number of separators stored in the first level of intermediate pages. More...

const uint16_t	kMaxIntermediateMiniSeparators = 15U
	Max number of separators stored in the second level of intermediate pages. More...

const uint32_t	kMaxIntermediatePointers = (kMaxIntermediateSeparators + 1U) * (kMaxIntermediateMiniSeparators + 1U)
	Max number of pointers (if completely filled) stored in an intermediate pages. More...

constexpr uint32_t	kIntermediateAlmostFull = kMaxIntermediatePointers * 9U / 10U

Function Documentation

void foedus::storage::masstree::_dummy_static_size_check__COUNTER__ ( )

inline

Definition at line 1733 of file masstree_page_impl.hpp.

PayloadLength foedus::storage::masstree::adjust_payload_hint	(	PayloadLength	payload_count,
		PayloadLength	physical_payload_hint
	)

Definition at line 233 of file masstree_storage.cpp.

References foedus::assorted::align8(), ASSERT_ND, and kMaxPayloadLength.

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

                                        {
   ASSERT_ND(physical_payload_hint >= payload_count);  // if not, most likely misuse.
   if (physical_payload_hint < payload_count) {
     physical_payload_hint = payload_count;
   }
   if (physical_payload_hint > kMaxPayloadLength) {
     physical_payload_hint = kMaxPayloadLength;
   }
   physical_payload_hint = assorted::align8(physical_payload_hint);
   return physical_payload_hint;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

MasstreeBorderPage* foedus::storage::masstree::allocate_new_border_page ( thread::Thread * context )

inline

Definition at line 39 of file masstree_reserve_impl.cpp.

References foedus::thread::Thread::get_local_volatile_page_resolver(), foedus::thread::Thread::get_numa_node(), foedus::thread::Thread::get_thread_memory(), foedus::memory::NumaCoreMemory::grab_free_volatile_page(), foedus::storage::masstree::MasstreePage::header(), foedus::storage::PageHeader::page_id_, foedus::storage::VolatilePagePointer::set(), and foedus::storage::VolatilePagePointer::word.

Referenced by foedus::storage::masstree::ReserveRecords::run().

                                                                            {
   memory::NumaCoreMemory* memory = context->get_thread_memory();
   memory::PagePoolOffset offset = memory->grab_free_volatile_page();
   if (offset == 0) {
     return nullptr;
   }
 
   const auto &resolver = context->get_local_volatile_page_resolver();
   MasstreeBorderPage* new_page
     = reinterpret_cast<MasstreeBorderPage*>(resolver.resolve_offset_newpage(offset));
   VolatilePagePointer new_page_pointer;
   new_page_pointer.set(context->get_numa_node(), offset);
   new_page->header().page_id_ = new_page_pointer.word;
   return new_page;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

MasstreeBorderPage* foedus::storage::masstree::as_border ( MasstreePage * page )

inline

Definition at line 56 of file masstree_composer_impl.cpp.

References ASSERT_ND, and foedus::storage::masstree::MasstreePage::is_border().

                                                          {
   ASSERT_ND(page->is_border());
   return reinterpret_cast<MasstreeBorderPage*>(page);
 }

Here is the call graph for this function:

MasstreeIntermediatePage* foedus::storage::masstree::as_intermediate ( MasstreePage * page )

inline

Definition at line 61 of file masstree_composer_impl.cpp.

References ASSERT_ND, and foedus::storage::masstree::MasstreePage::is_border().

                                                                      {
   ASSERT_ND(!page->is_border());
   return reinterpret_cast<MasstreeIntermediatePage*>(page);
 }

Here is the call graph for this function:

KeyLength foedus::storage::masstree::calculate_suffix_length ( KeyLength remainder_length )

inline

Definition at line 1105 of file masstree_page_impl.hpp.

References ASSERT_ND, kInitiallyNextLayer, and kMaxKeyLength.

Referenced by calculate_suffix_length_aligned(), foedus::storage::masstree::MasstreeCursor::copy_combined_key(), foedus::storage::masstree::MasstreeCursor::copy_combined_key_part(), foedus::storage::masstree::MasstreeBorderPage::Slot::get_suffix_length(), foedus::storage::masstree::MasstreeBorderPage::get_suffix_length(), foedus::storage::masstree::SplitBorder::migrate_records(), and foedus::storage::masstree::MasstreeBorderPage::reserve_record_space().

                                                                      {
   if (remainder_length == kInitiallyNextLayer) {
     return 0;
   }
   ASSERT_ND(remainder_length <= kMaxKeyLength);
   if (remainder_length >= sizeof(KeySlice)) {
     return remainder_length - sizeof(KeySlice);
   } else {
     return 0;
   }
 }

Here is the caller graph for this function:

KeyLength foedus::storage::masstree::calculate_suffix_length_aligned ( KeyLength remainder_length )

inline

Definition at line 1116 of file masstree_page_impl.hpp.

References foedus::assorted::align8(), and calculate_suffix_length().

Referenced by foedus::storage::masstree::MasstreeBorderPage::Slot::get_aligned_suffix_length(), foedus::storage::masstree::MasstreeBorderPage::get_record_payload_from_offsets(), foedus::storage::masstree::MasstreeBorderPage::get_suffix_length_aligned(), foedus::storage::masstree::MasstreeBorderPage::initialize_layer_root(), and foedus::storage::masstree::MasstreeBorderPage::to_record_length().

                                                                              {
   return assorted::align8(calculate_suffix_length(remainder_length));
 }

Here is the call graph for this function:

Here is the caller graph for this function:

int foedus::storage::masstree::compare_keys	(	const char *	left,
		uint16_t	left_length,
		const char *	right,
		uint16_t	right_length
	)

inline

Local utility functions.

Used in partitioner and composer.Returns negative, 0, positive if left<right, left==right, left>right.

Definition at line 203 of file masstree_partitioner_impl.hpp.

                          {
   uint16_t cmp_length = std::min(left_length, right_length);
   int result = std::memcmp(left, right, cmp_length);
   if (result != 0) {
     return result;
   } else if (left_length < right_length) {
     return -1;
   } else if (left_length > right_length) {
     return 1;
   } else {
     return 0;
   }
 }

void foedus::storage::masstree::copy_input_key	(	const char *	input_key,
		KeyLength	length,
		char *	buffer,
		KeySlice *	slice_buffer
	)

Definition at line 925 of file masstree_cursor.cpp.

References ASSUME_ALIGNED, and slice_key().

Referenced by foedus::storage::masstree::MasstreeCursor::open().

                                                                                                    {
   std::memcpy(ASSUME_ALIGNED(buffer, 256), input_key, length);
   for (Layer i = 0; i * sizeof(KeySlice) < length; ++i) {
     slice_buffer[i] = slice_key(input_key + i * sizeof(KeySlice), length - i * sizeof(KeySlice));
   }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

uint32_t foedus::storage::masstree::count_children_approximate ( const MasstreeIntermediatePage * page )

Definition at line 32 of file masstree_storage_fatify.cpp.

References foedus::storage::masstree::MasstreePage::get_key_count(), foedus::storage::masstree::MasstreeIntermediatePage::get_minipage(), and foedus::storage::masstree::MasstreeIntermediatePage::MiniPage::key_count_.

Referenced by foedus::storage::masstree::MasstreeStoragePimpl::approximate_count_root_children(), and foedus::storage::masstree::MasstreeStoragePimpl::fatify_first_root_double().

                                                                           {
   // this method doesn't need page-lock, but instead it might be inaccurate
   const uint16_t key_count = page->get_key_count();
   uint32_t current_count = 0;
   for (uint16_t minipage_index = 0; minipage_index <= key_count; ++minipage_index) {
     const auto& minipage = page->get_minipage(minipage_index);
     current_count += minipage.key_count_ + 1;
   }
   return current_count;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void foedus::storage::masstree::describe_masstree_page_common	(	std::ostream *	o_ptr,
		const MasstreePage &	v
	)

Definition at line 39 of file masstree_page_debug.cpp.

References foedus::storage::describe_volatile_pointer(), foedus::storage::masstree::MasstreePage::get_foster_fence(), foedus::storage::masstree::MasstreePage::get_foster_major(), foedus::storage::masstree::MasstreePage::get_foster_minor(), foedus::storage::masstree::MasstreePage::get_high_fence(), foedus::storage::masstree::MasstreePage::get_low_fence(), and foedus::storage::masstree::MasstreePage::header().

Referenced by operator<<().

                                                                              {
   std::ostream& o = *o_ptr;
   o << std::endl << "<addr>" << assorted::Hex(reinterpret_cast<uintptr_t>(&v), 16) << "</addr>";
   o << std::endl << v.header();
   o << std::endl << "<low_fence_>" << assorted::Hex(v.get_low_fence(), 16) << "</low_fence_>";
   o << "<high_fence_>" << assorted::Hex(v.get_high_fence(), 16) << "</high_fence_>";
   o << "<foster_fence_>" << assorted::Hex(v.get_foster_fence(), 16) << "</foster_fence_>";
   o << std::endl << "<foster_minor>";
   describe_volatile_pointer(&o, v.get_foster_minor());
   o << "</foster_minor>";
   o << std::endl << "<foster_major>";
   describe_volatile_pointer(&o, v.get_foster_major());
   o << "</foster_major>";
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void foedus::storage::masstree::design_partition_first_parallel	(	Engine *	engine,
		VolatilePagePointer	subtree,
		uint32_t	subtree_id,
		OwnerSamples *	result
	)

Definition at line 155 of file masstree_partitioner_impl.cpp.

References ASSERT_ND, design_partition_first_parallel_recurse(), foedus::debugging::StopWatch::elapsed_us(), foedus::memory::EngineMemory::get_global_volatile_page_resolver(), foedus::Engine::get_memory_manager(), foedus::memory::GlobalVolatilePageResolver::resolve_offset(), and foedus::debugging::StopWatch::stop().

                         {
   const memory::GlobalVolatilePageResolver& resolver
     = engine->get_memory_manager()->get_global_volatile_page_resolver();
   ASSERT_ND(subtree_id < result->subtrees_);
   debugging::StopWatch watch;
   MasstreePage* page = reinterpret_cast<MasstreePage*>(resolver.resolve_offset(subtree));
   assorted::UniformRandom unirand(subtree_id);
   design_partition_first_parallel_recurse(resolver, page, subtree_id, result, &unirand);
   watch.stop();
   VLOG(0) << "Subtree-" << subtree_id << " done in " << watch.elapsed_us() << "us";
 }

Here is the call graph for this function:

void foedus::storage::masstree::design_partition_first_parallel_recurse	(	const memory::GlobalVolatilePageResolver &	resolver,
		const MasstreePage *	page,
		uint32_t	subtree_id,
		OwnerSamples *	result,
		assorted::UniformRandom *	unirand
	)

Definition at line 124 of file masstree_partitioner_impl.cpp.

References foedus::storage::masstree::MasstreePage::header(), foedus::storage::masstree::OwnerSamples::increment(), foedus::storage::masstree::MasstreePage::is_border(), foedus::storage::VolatilePagePointer::is_null(), foedus::storage::masstree::MasstreeIntermediatePage::MiniPage::key_count_, foedus::assorted::UniformRandom::next_uint32(), foedus::storage::masstree::MasstreeIntermediatePage::MiniPage::pointers_, foedus::memory::GlobalVolatilePageResolver::resolve_offset(), foedus::storage::PageHeader::stat_last_updater_node_, and foedus::storage::DualPagePointer::volatile_pointer_.

Referenced by design_partition_first_parallel().

                                   {
   uint32_t node = page->header().stat_last_updater_node_;
   result->increment(node, subtree_id);
   // we don't care foster twins. this is just for sampling.
   if (!page->is_border()) {
     const auto* casted = reinterpret_cast<const MasstreeIntermediatePage*>(page);
     const uint32_t kSamplingWidth = 3;  // follow this many pointers per page.
     for (uint32_t rep = 0; rep < kSamplingWidth; ++rep) {
       uint32_t index = unirand->next_uint32() % (casted->get_key_count() + 1U);
       const MasstreeIntermediatePage::MiniPage& minipage = casted->get_minipage(index);
       uint32_t index_mini = unirand->next_uint32() % (minipage.key_count_ + 1U);
       VolatilePagePointer pointer = minipage.pointers_[index_mini].volatile_pointer_;
       if (pointer.is_null()) {
         // because now this page might be changing, this is possible
         continue;
       }
       MasstreePage* child = reinterpret_cast<MasstreePage*>(resolver.resolve_offset(pointer));
       design_partition_first_parallel_recurse(resolver, child, subtree_id, result, unirand);
     }
   } else {
     // so far do not bother going down to next layer. the border page's owner probably
     // represents it well. it might not, but a worst case always exists (such as just 1 page
     // in the first layer.. in that case anyway no luck).
   }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

uint8_t foedus::storage::masstree::extract_page_layer ( const void * in_page_pointer )

inline

Retrieve masstree layer information from the header of the page that contains the pointer.

We initially stored layer information in the log, but that might be incorrect when someone moves the record to next layer between log creation and record locking, so we now extract it in apply_record().

Definition at line 72 of file masstree_log_types.hpp.

References foedus::storage::Page::get_header(), foedus::storage::PageHeader::masstree_layer_, and foedus::storage::to_page().

Referenced by foedus::storage::masstree::MasstreeCommonLogType::apply_record_prepare(), and foedus::storage::masstree::MasstreeCommonLogType::equal_record_and_log_suffixes().

                                                                {
   const Page* page = to_page(in_page_pointer);
   return page->get_header().masstree_layer_;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void foedus::storage::masstree::fill_payload_padded	(	char *	destination,
		const char *	source,
		PayloadLength	count
	)

inline

Definition at line 48 of file masstree_composer_impl.cpp.

References foedus::assorted::align8(), ASSERT_ND, and is_key_aligned_and_zero_padded().

                                                                                             {
   if (count > 0) {
     ASSERT_ND(is_key_aligned_and_zero_padded(source, count));
     std::memcpy(destination, source, assorted::align8(count));
   }
 }

Here is the call graph for this function:

bool foedus::storage::masstree::from_this_snapshot	(	SnapshotPagePointer	pointer,
		const Composer::ConstructRootArguments &	args
	)

Definition at line 102 of file masstree_composer_impl.cpp.

References ASSERT_ND, foedus::storage::extract_snapshot_id_from_snapshot_pointer(), foedus::snapshot::SnapshotWriter::get_snapshot_id(), foedus::snapshot::kNullSnapshotId, and foedus::storage::Composer::ConstructRootArguments::snapshot_writer_.

Referenced by foedus::storage::masstree::MasstreeComposer::construct_root().

                                                                                                  {
   if (pointer == 0) {
     return false;
   }
   snapshot::SnapshotId snapshot_id = extract_snapshot_id_from_snapshot_pointer(pointer);
   ASSERT_ND(snapshot_id != snapshot::kNullSnapshotId);
   return snapshot_id == args.snapshot_writer_->get_snapshot_id();
 }

Here is the call graph for this function:

Here is the caller graph for this function:

xct::XctId foedus::storage::masstree::get_initial_xid ( )

inline

Definition at line 31 of file masstree_reserve_impl.cpp.

References foedus::Epoch::kEpochInitialCurrent, and foedus::xct::XctId::set().

Referenced by foedus::storage::masstree::ReserveRecords::run().

                                   {
   xct::XctId initial_id;
   initial_id.set(
     Epoch::kEpochInitialCurrent,  // TODO(Hideaki) this should be something else
     0);
   return initial_id;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void foedus::storage::masstree::grow_case_a_common	(	thread::Thread *	context,
		DualPagePointer *	pointer,
		MasstreePage *	cur_root
	)

Definition at line 36 of file masstree_grow_impl.cpp.

Referenced by foedus::storage::masstree::GrowFirstLayerRoot::run(), and foedus::storage::masstree::GrowNonFirstLayerRoot::run().

                           {
   ASSERT_ND(cur_root->is_locked());
   const auto& resolver = context->get_global_volatile_page_resolver();
   MasstreePage* minor
     = reinterpret_cast<MasstreePage*>(resolver.resolve_offset(cur_root->get_foster_minor()));
   MasstreePage* major
     = reinterpret_cast<MasstreePage*>(resolver.resolve_offset(cur_root->get_foster_major()));
 
   ASSERT_ND(minor->get_low_fence() == cur_root->get_low_fence());
   ASSERT_ND(minor->get_high_fence() == cur_root->get_foster_fence());
   ASSERT_ND(major->get_low_fence() == cur_root->get_foster_fence());
   ASSERT_ND(major->get_high_fence() == cur_root->get_high_fence());
   ASSERT_ND(!minor->header().snapshot_);
   ASSERT_ND(!major->header().snapshot_);
   ASSERT_ND(minor->is_empty_range() != major->is_empty_range());
 
   VolatilePagePointer nonempty_pointer;
   MasstreePage* empty_child;
   if (minor->is_empty_range()) {
     empty_child = minor;
     nonempty_pointer = cur_root->get_foster_major();
   } else {
     empty_child = major;
     nonempty_pointer = cur_root->get_foster_minor();
   }
 
   // snapshot pointer does NOT have to be reset. This is still logically the same page.
   pointer->volatile_pointer_ = nonempty_pointer;
 
   // Same as Adopt::adopt_case_a()
   ASSERT_ND(!empty_child->is_locked());
   empty_child->get_version_address()->status_.status_ |= PageVersionStatus::kRetiredBit;
   context->collect_retired_volatile_page(empty_child->get_volatile_page_id());
   cur_root->set_retired();
   context->collect_retired_volatile_page(cur_root->get_volatile_page_id());
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ErrorCode foedus::storage::masstree::grow_case_b_common	(	thread::Thread *	context,
		DualPagePointer *	pointer,
		MasstreePage *	cur_root
	)

Definition at line 76 of file masstree_grow_impl.cpp.

Referenced by foedus::storage::masstree::GrowFirstLayerRoot::run(), and foedus::storage::masstree::GrowNonFirstLayerRoot::run().

                           {
   ASSERT_ND(cur_root->is_locked());
   const auto& resolver = context->get_global_volatile_page_resolver();
 
   // In this case, we create a new intermediate page.
   memory::NumaCoreMemory* memory = context->get_thread_memory();
   VolatilePagePointer new_pointer = memory->grab_free_volatile_page_pointer();
   if (new_pointer.is_null()) {
     return kErrorCodeMemoryNoFreePages;
   }
   MasstreeIntermediatePage* new_root = reinterpret_cast<MasstreeIntermediatePage*>(
     resolver.resolve_offset_newpage(new_pointer));
   new_root->initialize_volatile_page(
     cur_root->header().storage_id_,
     new_pointer,
     cur_root->get_layer(),
     cur_root->get_btree_level() + 1U,
     kInfimumSlice,    // infimum slice
     kSupremumSlice);   // high-fence is supremum
 
   new_root->header().key_count_ = 0;
   auto& mini_page = new_root->get_minipage(0);
   mini_page.key_count_ = 1;
   mini_page.pointers_[0].snapshot_pointer_ = 0;
   mini_page.pointers_[0].volatile_pointer_ = cur_root->get_foster_minor();
   mini_page.pointers_[1].snapshot_pointer_ = 0;
   mini_page.pointers_[1].volatile_pointer_ = cur_root->get_foster_major();
   mini_page.separators_[0] = cur_root->get_foster_fence();
 
   // Let's install a pointer to the new root page
   assorted::memory_fence_release();  // must be after populating the new_root.
   // snapshot pointer does NOT have to be reset. This is still logically the same page.
   pointer->volatile_pointer_ = new_pointer;
 
   // the old root page is now retired
   cur_root->set_retired();
   context->collect_retired_volatile_page(cur_root->get_volatile_page_id());
   return kErrorCodeOk;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

std::ostream& foedus::storage::masstree::operator<<	(	std::ostream &	o,
		const MasstreePage &	v
	)

Definition at line 30 of file masstree_page_debug.cpp.

References foedus::storage::masstree::MasstreePage::is_border().

                                                              {
   if (v.is_border()) {
     o << reinterpret_cast<const MasstreeBorderPage&>(v);
   } else {
     o << reinterpret_cast<const MasstreeIntermediatePage&>(v);
   }
   return o;
 }

Here is the call graph for this function:

std::ostream& foedus::storage::masstree::operator<<	(	std::ostream &	o,
		const MasstreeMetadata &	v
	)

Definition at line 34 of file masstree_metadata.cpp.

                                                                  {
   o << MasstreeMetadataSerializer(const_cast<MasstreeMetadata*>(&v));
   return o;
 }

std::ostream& foedus::storage::masstree::operator<<	(	std::ostream &	o,
		const MasstreeCreateLogType &	v
	)

Definition at line 50 of file masstree_log_types.cpp.

References foedus::storage::masstree::MasstreeCreateLogType::metadata_.

                                                                       {
   o << "<MasstreeCreateLog>" << v.metadata_ << "</MasstreeCreateLog>";
   return o;
 }

std::ostream& foedus::storage::masstree::operator<<	(	std::ostream &	o,
		const MasstreeIntermediatePage &	v
	)

Definition at line 54 of file masstree_page_debug.cpp.

References describe_masstree_page_common(), foedus::storage::masstree::MasstreePage::get_key_count(), foedus::storage::masstree::MasstreePage::get_low_fence(), foedus::storage::masstree::MasstreeIntermediatePage::get_minipage(), foedus::storage::masstree::MasstreeIntermediatePage::get_separator(), foedus::storage::masstree::MasstreePage::is_empty_range(), foedus::storage::masstree::MasstreeIntermediatePage::MiniPage::key_count_, foedus::storage::masstree::MasstreeIntermediatePage::MiniPage::pointers_, and foedus::storage::masstree::MasstreeIntermediatePage::MiniPage::separators_.

                                                                          {
   o << "<MasstreeIntermediatePage>";
   describe_masstree_page_common(&o, v);
   if (v.is_empty_range()) {
     o << "<EmptyRangePage />";
   } else {
     for (uint16_t i = 0; i <= v.get_key_count(); ++i) {
       const MasstreeIntermediatePage::MiniPage& minipage = v.get_minipage(i);
       KeySlice minipage_low = i == 0 ? v.get_low_fence() : v.get_separator(i - 1);
       o << std::endl << "  <Minipage index=\"" << static_cast<int>(i)
         << "\" low=\"" << assorted::Hex(minipage_low, 16)
         << "\" count=\"" << static_cast<int>(minipage.key_count_)
         << "\">";
       for (uint16_t j = 0; j <= minipage.key_count_; ++j) {
         o << std::endl << "    <Pointer index=\"" << static_cast<int>(j)
           << "\" low=\""
             << assorted::Hex(j == 0 ? minipage_low : minipage.separators_[j - 1], 16)
           << "\">" << minipage.pointers_[j] << "</Pointer>";
       }
       o << std::endl << "  </Minipage>";
     }
   }
   o << "</MasstreeIntermediatePage>";
   return o;
 }

Here is the call graph for this function:

std::ostream& foedus::storage::masstree::operator<<	(	std::ostream &	o,
		const MasstreeInsertLogType &	v
	)

Definition at line 55 of file masstree_log_types.cpp.

References foedus::storage::masstree::MasstreeCommonLogType::get_key(), foedus::storage::masstree::MasstreeCommonLogType::get_payload(), foedus::storage::masstree::MasstreeCommonLogType::key_length_, and foedus::storage::masstree::MasstreeCommonLogType::payload_count_.

                                                                       {
   o << "<MasstreeInsertLogType>"
     << "<key_length_>" << v.key_length_ << "</key_length_>"
     << "<key_>" << assorted::Top(v.get_key(), v.key_length_) << "</key_>"
     << "<payload_count_>" << v.payload_count_ << "</payload_count_>"
     << "<payload_>" << assorted::Top(v.get_payload(), v.payload_count_) << "</payload_>"
     << "</MasstreeInsertLogType>";
   return o;
 }

Here is the call graph for this function:

std::ostream& foedus::storage::masstree::operator<<	(	std::ostream &	o,
		const MasstreeDeleteLogType &	v
	)

Definition at line 65 of file masstree_log_types.cpp.

References foedus::storage::masstree::MasstreeCommonLogType::get_key(), and foedus::storage::masstree::MasstreeCommonLogType::key_length_.

                                                                       {
   o << "<MasstreeDeleteLogType>"
     << "<key_length_>" << v.key_length_ << "</key_length_>"
     << "<key_>" << assorted::Top(v.get_key(), v.key_length_) << "</key_>"
     << "</MasstreeDeleteLogType>";
   return o;
 }

Here is the call graph for this function:

std::ostream& foedus::storage::masstree::operator<<	(	std::ostream &	o,
		const MasstreeStorage &	v
	)

Definition at line 71 of file masstree_storage.cpp.

References foedus::storage::Storage< CONTROL_BLOCK >::get_id(), and foedus::storage::Storage< CONTROL_BLOCK >::get_name().

                                                                 {
   o << "<MasstreeStorage>"
     << "<id>" << v.get_id() << "</id>"
     << "<name>" << v.get_name() << "</name>"
     << "</MasstreeStorage>";
   return o;
 }

Here is the call graph for this function:

std::ostream& foedus::storage::masstree::operator<<	(	std::ostream &	o,
		const MasstreeUpdateLogType &	v
	)

Definition at line 73 of file masstree_log_types.cpp.

References foedus::storage::masstree::MasstreeCommonLogType::get_key(), foedus::storage::masstree::MasstreeCommonLogType::get_payload(), foedus::storage::masstree::MasstreeCommonLogType::key_length_, and foedus::storage::masstree::MasstreeCommonLogType::payload_count_.

                                                                       {
   o << "<MasstreeUpdateLogType>"
     << "<key_length_>" << v.key_length_ << "</key_length_>"
     << "<key_>" << assorted::Top(v.get_key(), v.key_length_) << "</key_>"
     << "<payload_count_>" << v.payload_count_ << "</payload_count_>"
     << "<payload_>" << assorted::Top(v.get_payload(), v.payload_count_) << "</payload_>"
     << "</MasstreeUpdateLogType>";
   return o;
 }

Here is the call graph for this function:

std::ostream& foedus::storage::masstree::operator<<	(	std::ostream &	o,
		const MasstreeBorderPage &	v
	)

Definition at line 80 of file masstree_page_debug.cpp.

                                                                    {
   o << "<MasstreeBorderPage>";
   describe_masstree_page_common(&o, v);
   o << "<consecutive_inserts_>" << v.consecutive_inserts_ << "</consecutive_inserts_>";
   o << std::endl << "<records>";
   for (uint16_t i = 0; i < v.get_key_count(); ++i) {
     o << std::endl << "  <record index=\"" << i
       << "\" slice=\"" << assorted::Hex(v.get_slice(i), 16)
       << "\" remainder_len=\"" << static_cast<int>(v.get_remainder_length(i))
       << "\" offset=\"" << v.get_offset_in_bytes(i)
       << "\" physical_record_len=\"" << v.get_slot(i)->lengthes_.components.physical_record_length_
       << "\" payload_len=\"" << v.get_payload_length(i)
       << "\">";
     if (v.does_point_to_layer(i)) {
       o << "<next_layer>" << *v.get_next_layer(i) << "</next_layer>";
     } else {
       if (v.get_remainder_length(i) > sizeof(KeySlice)) {
         std::string suffix(v.get_record(i), v.get_suffix_length(i));
         o << "<key_suffix>" << assorted::HexString(suffix) << "</key_suffix>";
       }
       if (v.get_payload_length(i) > 0) {
         std::string payload(v.get_record_payload(i), v.get_payload_length(i));
         o << "<payload>" << assorted::HexString(payload) << "</payload>";
       }
     }
     o << * v.get_owner_id(i);
     o << "</record>";
   }
   o << std::endl << "</records>";
   o << "</MasstreeBorderPage>";
   return o;
 }

Here is the call graph for this function:

std::ostream& foedus::storage::masstree::operator<<	(	std::ostream &	o,
		const MasstreeOverwriteLogType &	v
	)

Definition at line 83 of file masstree_log_types.cpp.

References foedus::storage::masstree::MasstreeCommonLogType::get_key(), foedus::storage::masstree::MasstreeCommonLogType::get_payload(), foedus::storage::masstree::MasstreeCommonLogType::key_length_, foedus::storage::masstree::MasstreeCommonLogType::payload_count_, and foedus::storage::masstree::MasstreeCommonLogType::payload_offset_.

                                                                          {
   o << "<MasstreeOverwriteLog>"
     << "<key_length_>" << v.key_length_ << "</key_length_>"
     << "<key_>" << assorted::Top(v.get_key(), v.key_length_) << "</key_>"
     << "<payload_offset_>" << v.payload_offset_ << "</payload_offset_>"
     << "<payload_count_>" << v.payload_count_ << "</payload_count_>"
     << "<payload_>" << assorted::Top(v.get_payload(), v.payload_count_) << "</payload_>"
     << "</MasstreeOverwriteLog>";
   return o;
 }

Here is the call graph for this function:

std::ostream& foedus::storage::masstree::operator<<	(	std::ostream &	o,
		const OwnerSamples &	v
	)

Definition at line 231 of file masstree_partitioner_impl.cpp.

References foedus::storage::masstree::OwnerSamples::at(), foedus::storage::masstree::OwnerSamples::get_assignment(), foedus::storage::masstree::OwnerSamples::nodes_, and foedus::storage::masstree::OwnerSamples::subtrees_.

                                                              {
   o << "<OwnerSamples nodes=\"" << v.nodes_
     << "\" subtrees=\"" << v.subtrees_ << "\">" << std::endl;
   o << "<!-- legend id=\"x\" assignment=\"x\">";
   for (uint32_t node = 0; node < v.nodes_; ++node) {
     o << "[Node-" << node << "] ";
   }
   o << " -->" << std::endl;
   for (uint32_t subtree_id = 0; subtree_id < v.subtrees_; ++subtree_id) {
     o << "  <subtree id=\"" << subtree_id
       << "\" assignment=\"" << v.get_assignment(subtree_id) << "\">";
     for (uint32_t node = 0; node < v.nodes_; ++node) {
       o << assorted::Hex(v.at(node, subtree_id), 6) << " ";
     }
     o << "</subtree>" << std::endl;
   }
   o << std::endl << "</OwnerSamples>";
   return o;
 }

Here is the call graph for this function:

std::ostream& foedus::storage::masstree::operator<<	(	std::ostream &	o,
		const MasstreePartitioner &	v
	)

Definition at line 503 of file masstree_partitioner_impl.cpp.

References foedus::storage::masstree::MasstreePartitionerData::low_keys_, foedus::storage::masstree::MasstreePartitionerData::partition_count_, and foedus::storage::masstree::MasstreePartitionerData::partitions_.

                                                                     {
   o << "<MasstreePartitioner>";
   if (v.data_) {
     o << "<partition_count_>" << v.data_->partition_count_ << "</partition_count_>"
       << "<partitions>";
     for (uint16_t i = 0; i < v.data_->partition_count_; ++i) {
       o << std::endl << "  <partition node=\"" << v.data_->partitions_[i] << "\">"
         << assorted::Hex(v.data_->low_keys_[i], 16)
         << "</partition>";
     }
     o << "</partitions>";
   } else {
     o << "Not yet designed";
   }
   o << "</MasstreePartitioner>";
   return o;
 }

std::ostream& foedus::storage::masstree::operator<<	(	std::ostream &	o,
		const MasstreeComposeContext::PathLevel &	v
	)

Definition at line 2851 of file masstree_composer_impl.cpp.

                                                                                 {
   o << "<PathLevel>"
     << "<layer_>" << static_cast<int>(v.layer_) << "</layer_>"
     << "<next_original_>" << static_cast<int>(v.next_original_) << "</next_original_>"
     << "<next_original_mini>" << static_cast<int>(v.next_original_mini_) << "</next_original_mini>"
     << "<head>" << v.head_ << "</head>"
     << "<tail_>" << v.tail_ << "</tail_>"
     << "<page_count_>" << v.page_count_ << "</page_count_>"
     << "<low_fence_>" << assorted::Hex(v.low_fence_, 16) << "</low_fence_>"
     << "<high_fence_>" << assorted::Hex(v.high_fence_, 16) << "</high_fence_>"
     << "<next_original_slice_>"
       << assorted::Hex(v.next_original_slice_, 16) << "</next_original_slice_>"
     << "</PathLevel>";
   return o;
 }

void foedus::storage::masstree::prepare_sort_entries	(	const Partitioner::SortBatchArguments &	args,
		SortEntry *	entries
	)

subroutine of sort_batch_8bytes

Definition at line 444 of file masstree_partitioner_impl.cpp.

References ASSERT_ND, foedus::storage::Partitioner::SortBatchArguments::base_epoch_, foedus::xct::XctId::get_epoch(), foedus::storage::masstree::MasstreeCommonLogType::get_key(), foedus::xct::XctId::get_ordinal(), foedus::log::BaseLogType::header_, foedus::storage::masstree::MasstreeCommonLogType::key_length_, foedus::log::kLogCodeMasstreeDelete, foedus::log::kLogCodeMasstreeInsert, foedus::log::kLogCodeMasstreeOverwrite, foedus::log::kLogCodeMasstreeUpdate, foedus::storage::Partitioner::SortBatchArguments::log_buffer_, foedus::storage::Partitioner::SortBatchArguments::log_positions_, foedus::log::LogHeader::log_type_code_, foedus::storage::Partitioner::SortBatchArguments::logs_count_, normalize_be_bytes_full_aligned(), foedus::snapshot::LogBuffer::resolve(), foedus::storage::masstree::SortEntry::set(), foedus::Epoch::subtract(), and foedus::log::LogHeader::xct_id_.

                                                                                          {
   const Epoch base_epoch = args.base_epoch_;
   // CPU profile of partition_masstree_perf: 9-10%.
   for (uint32_t i = 0; i < args.logs_count_; ++i) {
     const MasstreeCommonLogType* log_entry = reinterpret_cast<const MasstreeCommonLogType*>(
       args.log_buffer_.resolve(args.log_positions_[i]));
     ASSERT_ND(log_entry->header_.log_type_code_ == log::kLogCodeMasstreeInsert
       || log_entry->header_.log_type_code_ == log::kLogCodeMasstreeDelete
       || log_entry->header_.log_type_code_ == log::kLogCodeMasstreeUpdate
       || log_entry->header_.log_type_code_ == log::kLogCodeMasstreeOverwrite);
     ASSERT_ND(log_entry->key_length_ == sizeof(KeySlice));
     Epoch epoch = log_entry->header_.xct_id_.get_epoch();
     ASSERT_ND(epoch.subtract(base_epoch) < (1U << 16));
     uint16_t compressed_epoch = epoch.subtract(base_epoch);
     entries[i].set(
       normalize_be_bytes_full_aligned(log_entry->get_key()),
       compressed_epoch,
       log_entry->header_.xct_id_.get_ordinal(),
       args.log_positions_[i]);
   }
 }

Here is the call graph for this function:

void foedus::storage::masstree::release_parallel	(	Engine *	engine,
		VolatilePagePointer	pointer
	)

Definition at line 178 of file masstree_page_impl.cpp.

References foedus::memory::EngineMemory::get_global_volatile_page_resolver(), foedus::Engine::get_memory_manager(), foedus::memory::PageReleaseBatch::release_all(), foedus::storage::masstree::MasstreePage::release_pages_recursive_common(), and foedus::memory::GlobalVolatilePageResolver::resolve_offset().

Referenced by foedus::storage::masstree::MasstreeIntermediatePage::release_pages_recursive_parallel().

                                                                    {
   const memory::GlobalVolatilePageResolver& page_resolver
     = engine->get_memory_manager()->get_global_volatile_page_resolver();
   MasstreePage* p = reinterpret_cast<MasstreePage*>(page_resolver.resolve_offset(pointer));
   memory::PageReleaseBatch release_batch(engine);
   p->release_pages_recursive_common(page_resolver, &release_batch);
   release_batch.release_all();
 }

Here is the call graph for this function:

Here is the caller graph for this function:

const MasstreeCommonLogType* foedus::storage::masstree::resolve_log	(	const snapshot::LogBuffer &	log_buffer,
		snapshot::BufferPosition	pos
	)

inline

Definition at line 221 of file masstree_partitioner_impl.hpp.

References ASSERT_ND, foedus::log::LogHeader::get_type(), foedus::log::BaseLogType::header_, foedus::log::kLogCodeMasstreeDelete, foedus::log::kLogCodeMasstreeInsert, foedus::log::kLogCodeMasstreeOverwrite, foedus::log::kLogCodeMasstreeUpdate, and foedus::snapshot::LogBuffer::resolve().

Referenced by foedus::storage::masstree::MasstreePartitioner::partition_batch().

                               {
   const MasstreeCommonLogType* rec = reinterpret_cast<const MasstreeCommonLogType*>(
     log_buffer.resolve(pos));
   ASSERT_ND(rec->header_.get_type() == log::kLogCodeMasstreeInsert
     || rec->header_.get_type() == log::kLogCodeMasstreeDelete
     || rec->header_.get_type() == log::kLogCodeMasstreeUpdate
     || rec->header_.get_type() == log::kLogCodeMasstreeOverwrite);
   return rec;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void foedus::storage::masstree::retrieve_positions	(	uint32_t	logs_count,
		const SortEntry *	entries,
		snapshot::BufferPosition *	out
	)

subroutine of sort_batch_8bytes

Definition at line 432 of file masstree_partitioner_impl.cpp.

References foedus::storage::masstree::SortEntry::position_.

                                {
   // CPU profile of partition_masstree_perf: 2-3%. (10-15% if the "index" idea is used)
   for (uint32_t i = 0; i < logs_count; ++i) {
     out[i] = entries[i].position_;
   }
 }

ErrorStack foedus::storage::masstree::verify_page_basic	(	thread::Thread *	context,
		MasstreePage *	page,
		PageType	page_type,
		KeySlice	low_fence,
		HighFence	high_fence
	)

Definition at line 69 of file masstree_storage_verify.cpp.

Referenced by foedus::storage::masstree::MasstreeStoragePimpl::verify_single_thread_border(), and foedus::storage::masstree::MasstreeStoragePimpl::verify_single_thread_intermediate().

                         {
   CHECK_AND_ASSERT(!page->is_locked());
   CHECK_AND_ASSERT(page->header().get_page_type() == page_type);
   CHECK_AND_ASSERT(page->is_border() || page->get_btree_level() > 0);
   CHECK_AND_ASSERT(!page->is_border() || page->get_btree_level() == 0);
   CHECK_AND_ASSERT(page->get_low_fence() == low_fence);
   CHECK_AND_ASSERT(page->get_high_fence() == high_fence.slice_);
   CHECK_AND_ASSERT(page->is_high_fence_supremum() == high_fence.supremum_);
   CHECK_AND_ASSERT(
     (page->is_moved() && page->has_foster_child()
       && !page->is_foster_major_null() && !page->is_foster_minor_null()) ||
     (!page->is_moved() && !page->has_foster_child()
       && page->is_foster_major_null() && page->is_foster_minor_null()));
 
   if (!page->is_foster_major_null()) {
     CHECK_AND_ASSERT(!page->header().snapshot_);
     CHECK_AND_ASSERT(!context->resolve(page->get_foster_major())->get_header().snapshot_);
     CHECK_AND_ASSERT(context->resolve(page->get_foster_major())->get_header().get_page_type()
       == page_type);
   }
   if (!page->is_foster_minor_null()) {
     CHECK_AND_ASSERT(!page->header().snapshot_);
     CHECK_AND_ASSERT(!context->resolve(page->get_foster_minor())->get_header().snapshot_);
     CHECK_AND_ASSERT(context->resolve(page->get_foster_minor())->get_header().get_page_type()
       == page_type);
   }
   return kRetOk;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

const DataOffset foedus::storage::masstree::kBorderPageDataPartOffset

Initial value:

= kCommonPageHeaderSize
  + 8U  
  + kBorderPageMaxSlots * sizeof(KeySlice)

Offset of data_ member in MasstreeBorderPage.

Definition at line 178 of file masstree_id.hpp.

Referenced by foedus::storage::masstree::MasstreeCommonLogType::apply_record_prepare().

const KeySlice foedus::storage::masstree::kInfimumSlice = 0

Definition at line 132 of file masstree_id.hpp.

constexpr uint32_t foedus::storage::masstree::kIntermediateAlmostFull = kMaxIntermediatePointers * 9U / 10U

Definition at line 52 of file masstree_storage_fatify.cpp.

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

const uint64_t foedus::storage::masstree::kSliceLen = sizeof(KeySlice)

Shorthand for sizeof(KeySlice).

Not much shorter? you are right..

Definition at line 129 of file masstree_id.hpp.

Referenced by foedus::storage::masstree::MasstreeCommonLogType::compare_logs(), foedus::storage::masstree::MasstreeComposeContext::PathLevel::contains_key(), foedus::storage::masstree::MasstreeBorderPage::ltgt_key(), foedus::storage::masstree::MasstreeComposeContext::PathLevel::needs_to_consume_original(), foedus::storage::masstree::MasstreeBorderPage::will_conflict(), and foedus::storage::masstree::MasstreeBorderPage::will_contain_next_layer().

const KeySlice foedus::storage::masstree::kSupremumSlice = 0xFFFFFFFFFFFFFFFFULL

Definition at line 137 of file masstree_id.hpp.

Detailed Description

Foster-Twin

Remainder vs Remaining Key

References

Classes

Typedefs

Functions

Variables

Function Documentation

Variable Documentation