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

Detailed Description

Represents one border page in Masstree Storage.

Slots: One border page has at most kBorderPageMaxSlots slots. One slot is reserved for one physical record, which is never moved except snapshotting and split/compact. A thread first installs a new record by atomically modifying page_version, then set up the record with deletion flag on. Flipping the delete flag of the record is done by apply() of transaction, which might fail. If it fails, the record is left as deleted until snapshotting or split/compact.

Page Layout

Unused part
Headers, including common part and border-specific part
Record Data part, which grows forward
Slot part (32 bytes per record), which grows backward

Attention: Do NOT instantiate this object or derive from this class. A page is always reinterpret-ed from a pooled memory region. No meaningful RTTI.

Definition at line 444 of file masstree_page_impl.hpp.

#include <masstree_page_impl.hpp>

Inheritance diagram for foedus::storage::masstree::MasstreeBorderPage:

[legend]

Collaboration diagram for foedus::storage::masstree::MasstreeBorderPage:

[legend]

Classes
struct	FindKeyForReserveResult
	return value for find_key_for_reserve(). More...

struct	Slot
	Fix-sized slot for each record, which is placed at the end of data region. More...

struct	SlotLengthPart
	A piece of Slot object that must be read/written in one-shot, meaning no one reads half-written values whether it reads old values or new values. More...

union	SlotLengthUnion

Public Types
enum	MatchType { kNotFound = 0, kExactMatchLocalRecord = 1, kExactMatchLayerPointer = 2, kConflictingLocalRecord = 3 }
	Used in FindKeyForReserveResult. More...

Public Member Functions
	MasstreeBorderPage ()=delete

	MasstreeBorderPage (const MasstreeBorderPage &other)=delete

MasstreeBorderPage &	operator= (const MasstreeBorderPage &other)=delete

void	initialize_volatile_page (StorageId storage_id, VolatilePagePointer page_id, uint8_t layer, KeySlice low_fence, KeySlice high_fence)

void	initialize_snapshot_page (StorageId storage_id, SnapshotPagePointer page_id, uint8_t layer, KeySlice low_fence, KeySlice high_fence)

bool	is_consecutive_inserts () const
	Whether this page is receiving only sequential inserts. More...

DataOffset	get_next_offset () const

void	increase_next_offset (DataOffset length)

const Slot *	get_slot (SlotIndex index) const __attribute__((always_inline))

Slot *	get_slot (SlotIndex index) __attribute__((always_inline))

Slot *	get_new_slot (SlotIndex index) __attribute__((always_inline))

SlotIndex	to_slot_index (const Slot *slot) const __attribute__((always_inline))

DataOffset	available_space () const
	Returns usable data space in bytes. More...

SlotIndex	find_key (KeySlice slice, const void *suffix, KeyLength remainder) const __attribute__((always_inline))
	Navigates a searching key-slice to one of the record in this page. More...

SlotIndex	find_key_normalized (SlotIndex from_index, SlotIndex to_index, KeySlice slice) const __attribute__((always_inline))
	Specialized version for 8 byte native integer search. More...

FindKeyForReserveResult	find_key_for_reserve (SlotIndex from_index, SlotIndex to_index, KeySlice slice, const void *suffix, KeyLength remainder) const __attribute__((always_inline))
	This is for the case we are looking for either the matching slot or the slot we will modify. More...

FindKeyForReserveResult	find_key_for_snapshot (KeySlice slice, const void *suffix, KeyLength remainder) const __attribute__((always_inline))
	This one is used for snapshot pages. More...

char *	get_record (SlotIndex index) __attribute__((always_inline))

const char *	get_record (SlotIndex index) const __attribute__((always_inline))

char *	get_record_payload (SlotIndex index) __attribute__((always_inline))

const char *	get_record_payload (SlotIndex index) const __attribute__((always_inline))

DualPagePointer *	get_next_layer (SlotIndex index) __attribute__((always_inline))

const DualPagePointer *	get_next_layer (SlotIndex index) const __attribute__((always_inline))

char *	get_record_from_offset (DataOffset record_offset) __attribute__((always_inline))
	Offset versions. More...

const char *	get_record_from_offset (DataOffset record_offset) const __attribute__((always_inline))

const char *	get_record_payload_from_offsets (DataOffset record_offset, KeyLength remainder_length) const __attribute__((always_inline))

char *	get_record_payload_from_offsets (DataOffset record_offset, KeyLength remainder_length) __attribute__((always_inline))

DualPagePointer *	get_next_layer_from_offsets (DataOffset record_offset, KeyLength remainder_length) __attribute__((always_inline))

const DualPagePointer *	get_next_layer_from_offsets (DataOffset record_offset, KeyLength remainder_length) const __attribute__((always_inline))

bool	does_point_to_layer (SlotIndex index) const __attribute__((always_inline))

KeySlice	get_slice (SlotIndex index) const __attribute__((always_inline))

void	set_slice (SlotIndex index, KeySlice slice) __attribute__((always_inline))

DataOffset	get_offset_in_bytes (SlotIndex index) const __attribute__((always_inline))

xct::RwLockableXctId *	get_owner_id (SlotIndex index) __attribute__((always_inline))

const xct::RwLockableXctId *	get_owner_id (SlotIndex index) const __attribute__((always_inline))

KeyLength	get_remainder_length (SlotIndex index) const __attribute__((always_inline))

KeyLength	get_suffix_length (SlotIndex index) const __attribute__((always_inline))

KeyLength	get_suffix_length_aligned (SlotIndex index) const __attribute__((always_inline))

PayloadLength	get_payload_length (SlotIndex index) const __attribute__((always_inline))

PayloadLength	get_max_payload_length (SlotIndex index) const __attribute__((always_inline))

bool	can_accomodate (SlotIndex new_index, KeyLength remainder_length, PayloadLength payload_count) const __attribute__((always_inline))

bool	can_accomodate_snapshot (KeyLength remainder_length, PayloadLength payload_count) const __attribute__((always_inline))
	Slightly different from can_accomodate() as follows: More...

bool	compare_key (SlotIndex index, const void *be_key, KeyLength key_length) const __attribute__((always_inline))
	actually this method should be renamed to equal_key... More...

bool	equal_key (SlotIndex index, const void *be_key, KeyLength key_length) const __attribute__((always_inline))
	let's gradually migrate from compare_key() to this. More...

int	ltgt_key (SlotIndex index, const char *be_key, KeyLength key_length) const __attribute__((always_inline))
	compare the key. More...

int	ltgt_key (SlotIndex index, KeySlice slice, const char *suffix, KeyLength remainder) const __attribute__((always_inline))
	Overload to receive slice+suffix. More...

bool	will_conflict (SlotIndex index, const char *be_key, KeyLength key_length) const __attribute__((always_inline))
	Returns whether inserting the key will cause creation of a new next layer. More...

bool	will_conflict (SlotIndex index, KeySlice slice, KeyLength remainder) const __attribute__((always_inline))
	Overload to receive slice. More...

bool	will_contain_next_layer (SlotIndex index, const char *be_key, KeyLength key_length) const __attribute__((always_inline))
	Returns whether the record is a next-layer pointer that would contain the key. More...

bool	will_contain_next_layer (SlotIndex index, KeySlice slice, KeyLength remainder) const __attribute__((always_inline))

void	reserve_record_space (SlotIndex index, xct::XctId initial_owner_id, KeySlice slice, const void *suffix, KeyLength remainder_length, PayloadLength payload_count)
	Installs a new physical record that doesn't exist logically (delete bit on). More...

void	reserve_initially_next_layer (SlotIndex index, xct::XctId initial_owner_id, KeySlice slice, const DualPagePointer &pointer)
	For creating a record that is initially a next-layer. More...

void	append_next_layer_snapshot (xct::XctId initial_owner_id, KeySlice slice, SnapshotPagePointer pointer)
	Installs a next layer pointer. More...

void	replace_next_layer_snapshot (SnapshotPagePointer pointer)
	Same as above, except this is used to transform an existing record at end to a next layer pointer. More...

void	initialize_layer_root (const MasstreeBorderPage *copy_from, SlotIndex copy_index)
	Copy the initial record that will be the only record for a new root page. More...

void	release_pages_recursive (const memory::GlobalVolatilePageResolver &page_resolver, memory::PageReleaseBatch *batch)

void	prefetch () const __attribute__((always_inline))
	prefetch upto 256th bytes. More...

void	prefetch_additional_if_needed (SlotIndex key_count) const __attribute__((always_inline))

bool	try_expand_record_in_page_physical (PayloadLength payload_count, SlotIndex record_index)
	A physical-only method to expand a record within this page without any logical change. More...

void	initialize_as_layer_root_physical (VolatilePagePointer page_id, MasstreeBorderPage *parent, SlotIndex parent_index)
	A physical-only method to initialize this page as a volatile page of a layer-root pointed from the given parent record. More...

xct::TrackMovedRecordResult	track_moved_record (Engine engine, xct::RwLockableXctId old_address, xct::WriteXctAccess *write_set)

xct::TrackMovedRecordResult	track_moved_record_next_layer (Engine engine, xct::RwLockableXctId old_address)
	This one further tracks it to next layer. More...

bool	verify_slot_lengthes (SlotIndex index) const

void	assert_entries () __attribute__((always_inline))

void	assert_entries_impl () const
	defined in masstree_page_debug.cpp. More...

Public Member Functions inherited from foedus::storage::masstree::MasstreePage
	MasstreePage ()=delete

	MasstreePage (const MasstreePage &other)=delete

MasstreePage &	operator= (const MasstreePage &other)=delete

PageHeader &	header ()

const PageHeader &	header () const

VolatilePagePointer	get_volatile_page_id () const

SnapshotPagePointer	get_snapshot_page_id () const

bool	is_border () const __attribute__((always_inline))

bool	is_empty_range () const __attribute__((always_inline))
	An empty-range page, either intermediate or border, never has any entries. More...

KeySlice	get_low_fence () const __attribute__((always_inline))

KeySlice	get_high_fence () const __attribute__((always_inline))

bool	is_high_fence_supremum () const __attribute__((always_inline))

bool	is_low_fence_infimum () const __attribute__((always_inline))

bool	is_layer_root () const __attribute__((always_inline))

KeySlice	get_foster_fence () const __attribute__((always_inline))

bool	is_foster_minor_null () const __attribute__((always_inline))

bool	is_foster_major_null () const __attribute__((always_inline))

VolatilePagePointer	get_foster_minor () const __attribute__((always_inline))

VolatilePagePointer	get_foster_major () const __attribute__((always_inline))

void	set_foster_twin (VolatilePagePointer minor, VolatilePagePointer major)

void	install_foster_twin (VolatilePagePointer minor, VolatilePagePointer major, KeySlice foster_fence)

bool	within_fences (KeySlice slice) const __attribute__((always_inline))

bool	within_foster_minor (KeySlice slice) const __attribute__((always_inline))

bool	within_foster_major (KeySlice slice) const __attribute__((always_inline))

bool	has_foster_child () const __attribute__((always_inline))

uint8_t	get_layer () const __attribute__((always_inline))
	Layer-0 stores the first 8 byte slice, Layer-1 next 8 byte... More...

uint8_t	get_btree_level () const __attribute__((always_inline))
	used only in masstree. More...

SlotIndex	get_key_count () const __attribute__((always_inline))
	physical key count (those keys might be deleted) in this page. More...

void	set_key_count (SlotIndex count) __attribute__((always_inline))

void	increment_key_count () __attribute__((always_inline))

void	prefetch_general () const __attribute__((always_inline))
	prefetch upto keys/separators, whether this page is border or interior. More...

const PageVersion &	get_version () const __attribute__((always_inline))

PageVersion &	get_version () __attribute__((always_inline))

const PageVersion *	get_version_address () const __attribute__((always_inline))

PageVersion *	get_version_address () __attribute__((always_inline))

xct::McsWwLock *	get_lock_address () __attribute__((always_inline))

bool	is_locked () const __attribute__((always_inline))

bool	is_moved () const __attribute__((always_inline))

bool	is_retired () const __attribute__((always_inline))

void	set_moved () __attribute__((always_inline))

void	set_retired () __attribute__((always_inline))

void	release_pages_recursive_common (const memory::GlobalVolatilePageResolver &page_resolver, memory::PageReleaseBatch *batch)

void	set_foster_major_offset_unsafe (memory::PagePoolOffset offset) __attribute__((always_inline))
	As the name suggests, this should be used only by composer. More...

void	set_high_fence_unsafe (KeySlice high_fence) __attribute__((always_inline))
	As the name suggests, this should be used only by composer. More...

Static Public Member Functions
static DataOffset	to_record_length (KeyLength remainder_length, PayloadLength payload_length)
	returns minimal physical_record_length_ for the given remainder/payload length. More...

static DataOffset	required_data_space (KeyLength remainder_length, PayloadLength payload_length)
	returns the byte size of required contiguous space in data_ to insert a new record of the given remainder/payload length. More...

Friends
struct	SplitBorder

std::ostream &	operator<< (std::ostream &o, const MasstreeBorderPage &v)
	defined in masstree_page_debug.cpp. More...

Additional Inherited Members
Protected Member Functions inherited from foedus::storage::masstree::MasstreePage
void	initialize_volatile_common (StorageId storage_id, VolatilePagePointer page_id, PageType page_type, uint8_t layer, uint8_t level, KeySlice low_fence, KeySlice high_fence)

void	initialize_snapshot_common (StorageId storage_id, SnapshotPagePointer page_id, PageType page_type, uint8_t layer, uint8_t level, KeySlice low_fence, KeySlice high_fence)

Protected Attributes inherited from foedus::storage::masstree::MasstreePage
PageHeader	header_

KeySlice	low_fence_
	Inclusive low fence of this page. More...

KeySlice	high_fence_
	Inclusive high fence of this page. More...

KeySlice	foster_fence_
	Inclusive low_fence of foster child. More...

VolatilePagePointer	foster_twin_ [2]
	Points to foster children, or tentative child pages. More...

Member Enumeration Documentation

enum foedus::storage::masstree::MasstreeBorderPage::MatchType

Used in FindKeyForReserveResult.

Enumerator
kNotFound
kExactMatchLocalRecord
kExactMatchLayerPointer
kConflictingLocalRecord

Definition at line 585 of file masstree_page_impl.hpp.

                  {
     kNotFound = 0,
     kExactMatchLocalRecord = 1,
     kExactMatchLayerPointer = 2,
     kConflictingLocalRecord = 3,
   };

Constructor & Destructor Documentation

foedus::storage::masstree::MasstreeBorderPage::MasstreeBorderPage ( )

delete

foedus::storage::masstree::MasstreeBorderPage::MasstreeBorderPage ( const MasstreeBorderPage & other )

delete

Member Function Documentation

void foedus::storage::masstree::MasstreeBorderPage::append_next_layer_snapshot	(	xct::XctId	initial_owner_id,
		KeySlice	slice,
		SnapshotPagePointer	pointer
	)

inline

Installs a next layer pointer.

This is used only from snapshot composer, so no race.

Definition at line 1417 of file masstree_page_impl.hpp.

                                {
   ASSERT_ND(header().snapshot_);  // this is used only from snapshot composer
   const SlotIndex index = get_key_count();
   const KeyLength kRemainder = kInitiallyNextLayer;
   ASSERT_ND(can_accomodate(index, kRemainder, sizeof(DualPagePointer)));
   const DataOffset record_size = to_record_length(kRemainder, sizeof(DualPagePointer));
   const DataOffset offset = next_offset_;
   set_slice(index, slice);
   // This is in snapshot page, so no worry on race.
   Slot* slot = get_new_slot(index);
   slot->lengthes_.components.offset_ = offset;
   slot->lengthes_.components.unused_ = 0;
   slot->lengthes_.components.physical_record_length_ = record_size;
   slot->lengthes_.components.payload_length_ = sizeof(DualPagePointer);
   slot->original_physical_record_length_ = record_size;
   slot->remainder_length_ = kRemainder;
   slot->original_offset_ = offset;
   next_offset_ += record_size;
 
   slot->tid_.xct_id_ = initial_owner_id;
   slot->tid_.xct_id_.set_next_layer();
   DualPagePointer* dual_pointer = get_next_layer_from_offsets(offset, kRemainder);
   dual_pointer->volatile_pointer_.clear();
   dual_pointer->snapshot_pointer_ = pointer;
   set_key_count(index + 1U);
 }

Here is the call graph for this function:

void foedus::storage::masstree::MasstreeBorderPage::assert_entries ( )

inline

Definition at line 988 of file masstree_page_impl.hpp.

References assert_entries_impl().

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

                                       {
 #ifndef NDEBUG
     assert_entries_impl();
 #endif  // NDEBUG
   }

Here is the call graph for this function:

Here is the caller graph for this function:

void foedus::storage::masstree::MasstreeBorderPage::assert_entries_impl ( ) const

defined in masstree_page_debug.cpp.

Definition at line 114 of file masstree_page_debug.cpp.

References foedus::assorted::align8(), ASSERT_ND, does_point_to_layer(), foedus::storage::masstree::MasstreePage::get_key_count(), get_payload_length(), get_record(), get_remainder_length(), get_slice(), get_suffix_length(), get_suffix_length_aligned(), foedus::storage::masstree::MasstreePage::header_, foedus::storage::masstree::MasstreePage::is_locked(), foedus::storage::masstree::kBorderPageMaxSlots, and foedus::storage::PageHeader::snapshot_.

Referenced by assert_entries().

                                                    {
   // the following logic holds only when this page is locked
   ASSERT_ND(header_.snapshot_ || is_locked());
   struct Sorter {
     explicit Sorter(const MasstreeBorderPage* target) : target_(target) {}
     bool operator() (SlotIndex left, SlotIndex right) {
       KeySlice left_slice = target_->get_slice(left);
       KeySlice right_slice = target_->get_slice(right);
       if (left_slice < right_slice) {
         return true;
       } else if (left_slice == right_slice) {
         return target_->get_remainder_length(left) < target_->get_remainder_length(right);
       } else {
         return false;
       }
     }
     const MasstreeBorderPage* target_;
   };
   SlotIndex key_count = get_key_count();
   SlotIndex order[kBorderPageMaxSlots];
   for (SlotIndex i = 0; i < key_count; ++i) {
     order[i] = i;
   }
   std::sort(order, order + key_count, Sorter(this));
 
   if (header_.snapshot_) {
     // in snapshot page, all entries should be fully sorted
     for (SlotIndex i = 0; i < key_count; ++i) {
       ASSERT_ND(order[i] == i);
     }
   }
 
   for (SlotIndex i = 1; i < key_count; ++i) {
     SlotIndex pre = order[i - 1];
     SlotIndex cur = order[i];
     const KeySlice pre_slice = get_slice(pre);
     const KeySlice cur_slice = get_slice(cur);
     ASSERT_ND(pre_slice <= cur_slice);
     if (pre_slice == cur_slice) {
       const KeyLength pre_klen = get_remainder_length(pre);
       const KeyLength cur_klen = get_remainder_length(cur);
       ASSERT_ND(pre_klen < cur_klen);
       ASSERT_ND(pre_klen <= sizeof(KeySlice));
     }
   }
 
   // also check the padding between key suffix and payload
   if (header_.snapshot_) {  // this can't be checked in volatile pages that are being changed
     for (SlotIndex i = 0; i < key_count; ++i) {
       if (does_point_to_layer(i)) {
         continue;
       }
       KeyLength suffix_length = get_suffix_length(i);
       KeyLength suffix_length_aligned = get_suffix_length_aligned(i);
       if (suffix_length > 0 && suffix_length != suffix_length_aligned) {
         ASSERT_ND(suffix_length_aligned > suffix_length);
         for (KeyLength pos = suffix_length; pos < suffix_length_aligned; ++pos) {
           // must be zero-padded
           ASSERT_ND(get_record(i)[pos] == 0);
         }
       }
       PayloadLength payload_length = get_payload_length(i);
       PayloadLength payload_length_aligned = assorted::align8(payload_length);
       if (payload_length > 0 && payload_length != payload_length_aligned) {
         ASSERT_ND(payload_length_aligned > payload_length);
         for (PayloadLength pos = payload_length; pos < payload_length_aligned; ++pos) {
           // must be zero-padded
           ASSERT_ND(get_record(i)[suffix_length_aligned + pos] == 0);
         }
       }
     }
   }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

DataOffset foedus::storage::masstree::MasstreeBorderPage::available_space ( ) const

inline

Returns usable data space in bytes.

Definition at line 660 of file masstree_page_impl.hpp.

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

Referenced by can_accomodate(), can_accomodate_snapshot(), and try_expand_record_in_page_physical().

                                               {
     uint16_t consumed = next_offset_ + get_key_count() * sizeof(Slot);
     ASSERT_ND(consumed <= sizeof(data_));
     if (consumed > sizeof(data_)) {  // just to be conservative on release build
       return 0;
     }
     return sizeof(data_) - consumed;
   }

Here is the call graph for this function:

Here is the caller graph for this function:

bool foedus::storage::masstree::MasstreeBorderPage::can_accomodate	(	SlotIndex	new_index,
		KeyLength	remainder_length,
		PayloadLength	payload_count
	)		const

inline

Definition at line 1570 of file masstree_page_impl.hpp.

References ASSERT_ND, available_space(), foedus::storage::masstree::kBorderPageMaxSlots, foedus::storage::masstree::kInitiallyNextLayer, foedus::storage::masstree::kMaxKeyLength, foedus::storage::masstree::kMaxPayloadLength, and required_data_space().

Referenced by append_next_layer_snapshot(), reserve_initially_next_layer(), reserve_record_space(), and foedus::storage::masstree::ReserveRecords::run().

                                      {
   if (new_index == 0) {
     ASSERT_ND(remainder_length <= kMaxKeyLength || remainder_length == kInitiallyNextLayer);
     ASSERT_ND(payload_count <= kMaxPayloadLength);
     return true;
   } else if (new_index >= kBorderPageMaxSlots) {
     return false;
   }
   const DataOffset required = required_data_space(remainder_length, payload_count);
   const DataOffset available = available_space();
   return required <= available;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

bool foedus::storage::masstree::MasstreeBorderPage::can_accomodate_snapshot	(	KeyLength	remainder_length,
		PayloadLength	payload_count
	)		const

inline

Slightly different from can_accomodate() as follows:

No race, so no need to receive new_index. It just uses get_key_count().
Always guarantees that the payload can be later expanded to sizeof(DualPagePointer).
See also
replace_next_layer_snapshot()

MasstreeComposeContext::append_border()

Definition at line 1585 of file masstree_page_impl.hpp.

References ASSERT_ND, available_space(), foedus::storage::masstree::MasstreePage::get_key_count(), foedus::storage::masstree::MasstreePage::header_, foedus::storage::masstree::kBorderPageMaxSlots, required_data_space(), and foedus::storage::PageHeader::snapshot_.

                                      {
   ASSERT_ND(header_.snapshot_);
   SlotIndex new_index = get_key_count();
   if (new_index == 0) {
     return true;
   } else if (new_index >= kBorderPageMaxSlots) {
     return false;
   }
   PayloadLength adjusted_payload = std::max<PayloadLength>(payload_count, sizeof(DualPagePointer));
   const DataOffset required = required_data_space(remainder_length, adjusted_payload);
   const DataOffset available = available_space();
   return required <= available;
 }

Here is the call graph for this function:

bool foedus::storage::masstree::MasstreeBorderPage::compare_key	(	SlotIndex	index,
		const void *	be_key,
		KeyLength	key_length
	)		const

inline

actually this method should be renamed to equal_key...

Definition at line 1600 of file masstree_page_impl.hpp.

References ASSERT_ND, foedus::storage::masstree::MasstreePage::get_layer(), get_record(), get_remainder_length(), get_slice(), foedus::storage::masstree::kBorderPageMaxSlots, and foedus::storage::masstree::slice_layer().

Referenced by equal_key().

                               {
   ASSERT_ND(index < kBorderPageMaxSlots);
   KeyLength remainder = key_length - get_layer() * sizeof(KeySlice);
   const KeyLength klen = get_remainder_length(index);
   if (remainder != klen) {
     return false;
   }
   KeySlice slice = slice_layer(be_key, key_length, get_layer());
   const KeySlice rec_slice = get_slice(index);
   if (slice != rec_slice) {
     return false;
   }
   if (remainder > sizeof(KeySlice)) {
     return std::memcmp(
       reinterpret_cast<const char*>(be_key) + (get_layer() + 1) * sizeof(KeySlice),
       get_record(index),
       remainder - sizeof(KeySlice)) == 0;
   } else {
     return true;
   }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

bool foedus::storage::masstree::MasstreeBorderPage::does_point_to_layer ( SlotIndex index ) const

inline

Definition at line 796 of file masstree_page_impl.hpp.

References ASSERT_ND, get_slot(), foedus::xct::XctId::is_next_layer(), foedus::storage::masstree::kBorderPageMaxSlots, foedus::storage::masstree::MasstreeBorderPage::Slot::tid_, and foedus::xct::RwLockableXctId::xct_id_.

                                                                 {
     ASSERT_ND(index < kBorderPageMaxSlots);
     return get_slot(index)->tid_.xct_id_.is_next_layer();
   }

Here is the call graph for this function:

Here is the caller graph for this function:

bool foedus::storage::masstree::MasstreeBorderPage::equal_key	(	SlotIndex	index,
		const void *	be_key,
		KeyLength	key_length
	)		const

inline

let's gradually migrate from compare_key() to this.

Definition at line 1624 of file masstree_page_impl.hpp.

References compare_key().

                               {
   return compare_key(index, be_key, key_length);
 }

Here is the call graph for this function:

SlotIndex foedus::storage::masstree::MasstreeBorderPage::find_key	(	KeySlice	slice,
		const void *	suffix,
		KeyLength	remainder
	)		const

inline

Navigates a searching key-slice to one of the record in this page.

Returns: index of key found in this page, or kBorderPageMaxSlots if not found.

Definition at line 1120 of file masstree_page_impl.hpp.

References ASSERT_ND, does_point_to_layer(), foedus::storage::masstree::MasstreePage::get_key_count(), get_record(), get_remainder_length(), get_slice(), foedus::storage::masstree::kBorderPageMaxSlots, foedus::storage::masstree::kMaxKeyLength, LIKELY, and prefetch_additional_if_needed().

Referenced by foedus::storage::masstree::MasstreeStoragePimpl::locate_record(), track_moved_record(), and track_moved_record_next_layer().

                              {
   SlotIndex key_count = get_key_count();
   ASSERT_ND(remainder <= kMaxKeyLength);
   ASSERT_ND(key_count <= kBorderPageMaxSlots);
   prefetch_additional_if_needed(key_count);
 
   // one slice might be used for up to 10 keys, length 0 to 8 and pointer to next layer.
   if (remainder <= sizeof(KeySlice)) {
     // then we are looking for length 0-8 only.
     for (SlotIndex i = 0; i < key_count; ++i) {
       const KeySlice rec_slice = get_slice(i);
       if (LIKELY(slice != rec_slice)) {
         continue;
       }
       // no suffix nor next layer, so just compare length. if not match, continue
       const KeyLength klen = get_remainder_length(i);
       if (klen == remainder) {
         return i;
       }
     }
   } else {
     // then we are only looking for length>8.
     for (SlotIndex i = 0; i < key_count; ++i) {
       const KeySlice rec_slice = get_slice(i);
       if (LIKELY(slice != rec_slice)) {
         continue;
       }
 
       if (does_point_to_layer(i)) {
         // as it points to next layer, no need to check suffix. We are sure this is it.
         // so far we don't delete layers, so in this case the record is always valid.
         return i;
       }
 
       // now, our key is > 8 bytes and we found some local record.
       const KeyLength klen = get_remainder_length(i);
       if (klen <= sizeof(KeySlice)) {
         continue;  // length 0-8, surely not a match. skip.
       }
 
       if (klen == remainder) {
         // compare suffix.
         const char* record_suffix = get_record(i);
         if (std::memcmp(record_suffix, suffix, remainder - sizeof(KeySlice)) == 0) {
           return i;
         }
       }
 
       // The record has > 8 bytes key of the same slice. it must be the only such record in this
       // page because otherwise we must have created a next layer!
       break;  // no more check needed
     }
   }
   return kBorderPageMaxSlots;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

MasstreeBorderPage::FindKeyForReserveResult foedus::storage::masstree::MasstreeBorderPage::find_key_for_reserve	(	SlotIndex	from_index,
		SlotIndex	to_index,
		KeySlice	slice,
		const void *	suffix,
		KeyLength	remainder
	)		const

inline

This is for the case we are looking for either the matching slot or the slot we will modify.

Definition at line 1198 of file masstree_page_impl.hpp.

References ASSERT_ND, does_point_to_layer(), get_record(), get_remainder_length(), get_slice(), foedus::storage::masstree::kBorderPageMaxSlots, kConflictingLocalRecord, kExactMatchLayerPointer, kExactMatchLocalRecord, foedus::storage::masstree::kMaxKeyLength, kNotFound, LIKELY, and prefetch_additional_if_needed().

Referenced by foedus::storage::masstree::MasstreeStoragePimpl::reserve_record(), and foedus::storage::masstree::ReserveRecords::run().

                              {
   ASSERT_ND(to_index <= kBorderPageMaxSlots);
   ASSERT_ND(from_index <= to_index);
   ASSERT_ND(remainder <= kMaxKeyLength);
   if (from_index == 0) {
     prefetch_additional_if_needed(to_index);
   }
   if (remainder <= sizeof(KeySlice)) {
     for (SlotIndex i = from_index; i < to_index; ++i) {
       const KeySlice rec_slice = get_slice(i);
       if (LIKELY(slice != rec_slice)) {
         continue;
       }
       const KeyLength klen = get_remainder_length(i);
       if (klen == remainder) {
         ASSERT_ND(!does_point_to_layer(i));
         return FindKeyForReserveResult(i, kExactMatchLocalRecord);
       }
     }
   } else {
     for (SlotIndex i = from_index; i < to_index; ++i) {
       const KeySlice rec_slice = get_slice(i);
       if (LIKELY(slice != rec_slice)) {
         continue;
       }
 
       const bool next_layer = does_point_to_layer(i);
       const KeyLength klen = get_remainder_length(i);
 
       if (next_layer) {
         ASSERT_ND(klen > sizeof(KeySlice));
         return FindKeyForReserveResult(i, kExactMatchLayerPointer);
       } else if (klen <= sizeof(KeySlice)) {
         continue;
       }
 
       // now, both the searching key and this key are more than 8 bytes.
       // whether the key really matches or not, this IS the slot we are looking for.
       // Either 1) the keys really match, or 2) we will make this record point to next layer.
       const char* record_suffix = get_record(i);
       if (klen == remainder &&
         std::memcmp(record_suffix, suffix, remainder - sizeof(KeySlice)) == 0) {
         // case 1)
         return FindKeyForReserveResult(i, kExactMatchLocalRecord);
       } else {
         // case 2)
         return FindKeyForReserveResult(i, kConflictingLocalRecord);
       }
     }
   }
   return FindKeyForReserveResult(kBorderPageMaxSlots, kNotFound);
 }

Here is the call graph for this function:

Here is the caller graph for this function:

MasstreeBorderPage::FindKeyForReserveResult foedus::storage::masstree::MasstreeBorderPage::find_key_for_snapshot	(	KeySlice	slice,
		const void *	suffix,
		KeyLength	remainder
	)		const

inline

This one is used for snapshot pages.

Because keys are fully sorted in snapshot pages, this returns the index of the first record whose key is strictly larger than given key (key_count if not exists).

Precondition: header_.snapshot

Definition at line 1256 of file masstree_page_impl.hpp.

References ASSERT_ND, does_point_to_layer(), foedus::storage::masstree::MasstreePage::get_key_count(), get_record(), get_remainder_length(), get_slice(), foedus::storage::masstree::MasstreePage::header_, kConflictingLocalRecord, kExactMatchLayerPointer, kExactMatchLocalRecord, foedus::storage::masstree::kMaxKeyLength, kNotFound, and foedus::storage::PageHeader::snapshot_.

                              {
   ASSERT_ND(header_.snapshot_);
   ASSERT_ND(remainder <= kMaxKeyLength);
   // Remember, unlike other cases above, there are no worry on concurrency.
   const SlotIndex key_count = get_key_count();
   if (remainder <= sizeof(KeySlice)) {
     for (SlotIndex i = 0; i < key_count; ++i) {
       const KeySlice rec_slice = get_slice(i);
       if (rec_slice < slice) {
         continue;
       } else if (rec_slice > slice) {
         // as keys are sorted in snapshot page, "i" is the place the slice would be inserted.
         return FindKeyForReserveResult(i, kNotFound);
       }
       ASSERT_ND(rec_slice == slice);
       const KeyLength klen = get_remainder_length(i);
       if (klen == remainder) {
         ASSERT_ND(!does_point_to_layer(i));
         return FindKeyForReserveResult(i, kExactMatchLocalRecord);
       } else if (klen < remainder) {
         ASSERT_ND(!does_point_to_layer(i));
         continue;  // same as "rec_slice < slice" case
       } else {
         return FindKeyForReserveResult(i, kNotFound);  // same as "rec_slice > slice" case
       }
     }
   } else {
     for (SlotIndex i = 0; i < key_count; ++i) {
       const KeySlice rec_slice = get_slice(i);
       if (rec_slice < slice) {
         continue;
       } else if (rec_slice > slice) {
         // as keys are sorted in snapshot page, "i" is the place the slice would be inserted.
         return FindKeyForReserveResult(i, kNotFound);
       }
       ASSERT_ND(rec_slice == slice);
       const KeyLength klen = get_remainder_length(i);
 
       if (does_point_to_layer(i)) {
         return FindKeyForReserveResult(i, kExactMatchLayerPointer);
       }
 
       ASSERT_ND(!does_point_to_layer(i));
 
       if (klen <= sizeof(KeySlice)) {
         continue;  // same as "rec_slice < slice" case
       }
 
       // see the comment in MasstreeComposerContext::PathLevel.
       // Even if the record is larger than the current key, we consider it "matched" and cause
       // next layer creation, but keeping the larger record in a dummy original page in nexy layer.
       const char* record_suffix = get_record(i);
       if (klen == remainder &&
         std::memcmp(record_suffix, suffix, remainder - sizeof(KeySlice)) == 0) {
         return FindKeyForReserveResult(i, kExactMatchLocalRecord);
       } else {
         return FindKeyForReserveResult(i, kConflictingLocalRecord);
       }
     }
   }
   return FindKeyForReserveResult(key_count, kNotFound);
 }

Here is the call graph for this function:

SlotIndex foedus::storage::masstree::MasstreeBorderPage::find_key_normalized	(	SlotIndex	from_index,
		SlotIndex	to_index,
		KeySlice	slice
	)		const

inline

Specialized version for 8 byte native integer search.

Because such a key never goes to second layer, this is much simpler.

Definition at line 1179 of file masstree_page_impl.hpp.

References ASSERT_ND, get_remainder_length(), get_slice(), foedus::storage::masstree::kBorderPageMaxSlots, prefetch_additional_if_needed(), and UNLIKELY.

Referenced by foedus::storage::masstree::MasstreeStoragePimpl::locate_record_normalized(), and foedus::storage::masstree::MasstreeStoragePimpl::reserve_record_normalized().

                         {
   ASSERT_ND(to_index <= kBorderPageMaxSlots);
   ASSERT_ND(from_index <= to_index);
   if (from_index == 0) {  // we don't need prefetching in second time
     prefetch_additional_if_needed(to_index);
   }
   for (SlotIndex i = from_index; i < to_index; ++i) {
     const KeySlice rec_slice = get_slice(i);
     const KeyLength klen = get_remainder_length(i);
     if (UNLIKELY(slice == rec_slice && klen == sizeof(KeySlice))) {
       return i;
     }
   }
   return kBorderPageMaxSlots;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

PayloadLength foedus::storage::masstree::MasstreeBorderPage::get_max_payload_length ( SlotIndex index ) const

inline

Returns: the maximum payload length the physical record allows.

Definition at line 838 of file masstree_page_impl.hpp.

References foedus::storage::masstree::MasstreeBorderPage::Slot::get_max_payload_peek(), and get_slot().

Referenced by initialize_as_layer_root_physical(), foedus::storage::masstree::MasstreeStoragePimpl::insert_general(), foedus::storage::masstree::MasstreeStoragePimpl::reserve_record(), foedus::storage::masstree::MasstreeStoragePimpl::reserve_record_normalized(), foedus::storage::masstree::ReserveRecords::run(), try_expand_record_in_page_physical(), and foedus::storage::masstree::MasstreeStoragePimpl::upsert_general().

                                                                             {
     return get_slot(index)->get_max_payload_peek();
   }

Here is the call graph for this function:

Here is the caller graph for this function:

Slot* foedus::storage::masstree::MasstreeBorderPage::get_new_slot ( SlotIndex index )

inline

Definition at line 643 of file masstree_page_impl.hpp.

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

Referenced by append_next_layer_snapshot(), initialize_layer_root(), foedus::storage::masstree::SplitBorder::migrate_records(), reserve_initially_next_layer(), and reserve_record_space().

                                                            {
     ASSERT_ND(index == get_key_count());
     ASSERT_ND(index < kBorderPageMaxSlots);
     return reinterpret_cast<Slot*>(this + 1) - index - 1;
   }

Here is the call graph for this function:

Here is the caller graph for this function:

DualPagePointer* foedus::storage::masstree::MasstreeBorderPage::get_next_layer ( SlotIndex index )

inline

Definition at line 750 of file masstree_page_impl.hpp.

References get_record_payload().

Referenced by foedus::storage::masstree::MasstreeStoragePimpl::debugout_single_thread_recurse(), foedus::storage::masstree::MasstreeStoragePimpl::follow_layer(), foedus::storage::masstree::MasstreeStoragePimpl::hcc_reset_all_temperature_stat_recurse(), initialize_as_layer_root_physical(), foedus::storage::masstree::operator<<(), foedus::storage::masstree::MasstreeStoragePimpl::peek_volatile_page_boundaries_next_layer(), foedus::storage::masstree::MasstreeStoragePimpl::prefetch_pages_normalized_recurse(), release_pages_recursive(), replace_next_layer_snapshot(), foedus::storage::masstree::GrowNonFirstLayerRoot::run(), foedus::storage::masstree::ReserveRecords::run(), track_moved_record_next_layer(), and foedus::storage::masstree::MasstreeStoragePimpl::verify_single_thread_border().

                                                                  {
     return reinterpret_cast<DualPagePointer*>(get_record_payload(index));
   }

Here is the call graph for this function:

Here is the caller graph for this function:

const DualPagePointer* foedus::storage::masstree::MasstreeBorderPage::get_next_layer ( SlotIndex index ) const

inline

Definition at line 753 of file masstree_page_impl.hpp.

References get_record_payload().

                                                                              {
     return reinterpret_cast<const DualPagePointer*>(get_record_payload(index));
   }

Here is the call graph for this function:

DualPagePointer* foedus::storage::masstree::MasstreeBorderPage::get_next_layer_from_offsets	(	DataOffset	record_offset,
		KeyLength	remainder_length
	)

inline

Definition at line 782 of file masstree_page_impl.hpp.

References get_record_payload_from_offsets().

Referenced by append_next_layer_snapshot(), and reserve_initially_next_layer().

                                               {
     char* payload = get_record_payload_from_offsets(record_offset, remainder_length);
     return reinterpret_cast<DualPagePointer*>(payload);
   }

Here is the call graph for this function:

Here is the caller graph for this function:

const DualPagePointer* foedus::storage::masstree::MasstreeBorderPage::get_next_layer_from_offsets	(	DataOffset	record_offset,
		KeyLength	remainder_length
	)		const

inline

Definition at line 788 of file masstree_page_impl.hpp.

References get_record_payload_from_offsets().

                                                     {
     const char* payload = get_record_payload_from_offsets(record_offset, remainder_length);
     return reinterpret_cast<const DualPagePointer*>(payload);
   }

Here is the call graph for this function:

DataOffset foedus::storage::masstree::MasstreeBorderPage::get_next_offset ( ) const

inline

Definition at line 625 of file masstree_page_impl.hpp.

Referenced by foedus::storage::masstree::SplitBorder::run(), and try_expand_record_in_page_physical().

625 { return next_offset_; }

Here is the caller graph for this function:

DataOffset foedus::storage::masstree::MasstreeBorderPage::get_offset_in_bytes ( SlotIndex index ) const

inline

Definition at line 809 of file masstree_page_impl.hpp.

References foedus::storage::masstree::MasstreeBorderPage::SlotLengthUnion::components, get_slot(), foedus::storage::masstree::MasstreeBorderPage::Slot::lengthes_, and foedus::storage::masstree::MasstreeBorderPage::SlotLengthPart::offset_.

Referenced by get_record(), and foedus::storage::masstree::operator<<().

                                                                       {
     return get_slot(index)->lengthes_.components.offset_;
   }

Here is the call graph for this function:

Here is the caller graph for this function:

xct::RwLockableXctId* foedus::storage::masstree::MasstreeBorderPage::get_owner_id ( SlotIndex index )

inline

Definition at line 813 of file masstree_page_impl.hpp.

References get_slot(), and foedus::storage::masstree::MasstreeBorderPage::Slot::tid_.

                                                                   {
     return &get_slot(index)->tid_;
   }

Here is the call graph for this function:

Here is the caller graph for this function:

const xct::RwLockableXctId* foedus::storage::masstree::MasstreeBorderPage::get_owner_id ( SlotIndex index ) const

inline

Definition at line 816 of file masstree_page_impl.hpp.

References get_slot(), and foedus::storage::masstree::MasstreeBorderPage::Slot::tid_.

                                                                               {
     return &get_slot(index)->tid_;
   }

Here is the call graph for this function:

PayloadLength foedus::storage::masstree::MasstreeBorderPage::get_payload_length ( SlotIndex index ) const

inline

Returns: the current logical payload length, which might change later.

Definition at line 832 of file masstree_page_impl.hpp.

References foedus::storage::masstree::MasstreeBorderPage::SlotLengthUnion::components, get_slot(), foedus::storage::masstree::MasstreeBorderPage::Slot::lengthes_, and foedus::storage::masstree::MasstreeBorderPage::SlotLengthPart::payload_length_.

Referenced by assert_entries_impl(), foedus::storage::masstree::MasstreeStoragePimpl::increment_general(), foedus::storage::masstree::operator<<(), foedus::storage::masstree::MasstreeStoragePimpl::overwrite_general(), foedus::storage::masstree::MasstreeStoragePimpl::retrieve_general(), foedus::storage::masstree::MasstreeStoragePimpl::retrieve_part_general(), and foedus::storage::masstree::MasstreeStoragePimpl::upsert_general().

                                                                          {
     return get_slot(index)->lengthes_.components.payload_length_;
   }

Here is the call graph for this function:

Here is the caller graph for this function:

char* foedus::storage::masstree::MasstreeBorderPage::get_record ( SlotIndex index )

inline

Definition at line 732 of file masstree_page_impl.hpp.

References ASSERT_ND, get_offset_in_bytes(), get_record_from_offset(), and foedus::storage::masstree::kBorderPageMaxSlots.

Referenced by assert_entries_impl(), compare_key(), find_key(), find_key_for_reserve(), find_key_for_snapshot(), get_record_payload(), ltgt_key(), foedus::storage::masstree::operator<<(), foedus::storage::masstree::MasstreeStoragePimpl::register_record_write_log(), track_moved_record(), and track_moved_record_next_layer().

                                                   {
     ASSERT_ND(index < kBorderPageMaxSlots);
     return get_record_from_offset(get_offset_in_bytes(index));
   }

Here is the call graph for this function:

Here is the caller graph for this function:

const char* foedus::storage::masstree::MasstreeBorderPage::get_record ( SlotIndex index ) const

inline

Definition at line 736 of file masstree_page_impl.hpp.

References ASSERT_ND, get_offset_in_bytes(), get_record_from_offset(), and foedus::storage::masstree::kBorderPageMaxSlots.

                                                               {
     ASSERT_ND(index < kBorderPageMaxSlots);
     return get_record_from_offset(get_offset_in_bytes(index));
   }

Here is the call graph for this function:

char* foedus::storage::masstree::MasstreeBorderPage::get_record_from_offset ( DataOffset record_offset )

inline

Offset versions.

Definition at line 758 of file masstree_page_impl.hpp.

References ASSERT_ND.

Referenced by get_record(), get_record_payload_from_offsets(), initialize_layer_root(), foedus::storage::masstree::SplitBorder::migrate_records(), reserve_record_space(), and try_expand_record_in_page_physical().

                                                                        {
     ASSERT_ND(record_offset % 8 == 0);
     ASSERT_ND(record_offset < sizeof(data_));
     return data_ + record_offset;
   }

Here is the caller graph for this function:

const char* foedus::storage::masstree::MasstreeBorderPage::get_record_from_offset ( DataOffset record_offset ) const

inline

Definition at line 763 of file masstree_page_impl.hpp.

References ASSERT_ND.

                                                                                    {
     ASSERT_ND(record_offset % 8 == 0);
     ASSERT_ND(record_offset < sizeof(data_));
     return data_ + record_offset;
   }

char* foedus::storage::masstree::MasstreeBorderPage::get_record_payload ( SlotIndex index )

inline

Definition at line 740 of file masstree_page_impl.hpp.

References get_record(), and get_suffix_length_aligned().

Referenced by get_next_layer(), foedus::storage::masstree::MasstreeStoragePimpl::increment_general(), initialize_as_layer_root_physical(), initialize_layer_root(), foedus::storage::masstree::operator<<(), foedus::storage::masstree::MasstreeStoragePimpl::retrieve_general(), and foedus::storage::masstree::MasstreeStoragePimpl::retrieve_part_general().

                                                           {
     char* record = get_record(index);
     KeyLength skipped = get_suffix_length_aligned(index);
     return record + skipped;
   }

Here is the call graph for this function:

Here is the caller graph for this function:

const char* foedus::storage::masstree::MasstreeBorderPage::get_record_payload ( SlotIndex index ) const

inline

Definition at line 745 of file masstree_page_impl.hpp.

References get_record(), and get_suffix_length_aligned().

                                                                       {
     const char* record = get_record(index);
     KeyLength skipped = get_suffix_length_aligned(index);
     return record + skipped;
   }

Here is the call graph for this function:

const char* foedus::storage::masstree::MasstreeBorderPage::get_record_payload_from_offsets	(	DataOffset	record_offset,
		KeyLength	remainder_length
	)		const

inline

Definition at line 768 of file masstree_page_impl.hpp.

References foedus::storage::masstree::calculate_suffix_length_aligned(), and get_record_from_offset().

Referenced by get_next_layer_from_offsets(), and initialize_layer_root().

                                                     {
     const char* record = get_record_from_offset(record_offset);
     KeyLength skipped = calculate_suffix_length_aligned(remainder_length);
     return record + skipped;
   }

Here is the call graph for this function:

Here is the caller graph for this function:

char* foedus::storage::masstree::MasstreeBorderPage::get_record_payload_from_offsets	(	DataOffset	record_offset,
		KeyLength	remainder_length
	)

inline

Definition at line 775 of file masstree_page_impl.hpp.

References foedus::storage::masstree::calculate_suffix_length_aligned(), and get_record_from_offset().

                                               {
     char* record = get_record_from_offset(record_offset);
     KeyLength skipped = calculate_suffix_length_aligned(remainder_length);
     return record + skipped;
   }

Here is the call graph for this function:

KeyLength foedus::storage::masstree::MasstreeBorderPage::get_remainder_length ( SlotIndex index ) const

inline

Definition at line 820 of file masstree_page_impl.hpp.

References get_slot(), and foedus::storage::masstree::MasstreeBorderPage::Slot::remainder_length_.

Referenced by assert_entries_impl(), compare_key(), find_key(), find_key_for_reserve(), find_key_for_snapshot(), find_key_normalized(), get_suffix_length(), get_suffix_length_aligned(), ltgt_key(), foedus::storage::masstree::operator<<(), reserve_record_space(), foedus::storage::masstree::MasstreeStoragePimpl::verify_single_thread_border(), and will_conflict().

                                                                       {
     return get_slot(index)->remainder_length_;
   }

Here is the call graph for this function:

Here is the caller graph for this function:

KeySlice foedus::storage::masstree::MasstreeBorderPage::get_slice ( SlotIndex index ) const

inline

Definition at line 801 of file masstree_page_impl.hpp.

References ASSERT_ND, and foedus::storage::masstree::kBorderPageMaxSlots.

Referenced by assert_entries_impl(), compare_key(), foedus::storage::masstree::SplitBorder::decide_strategy(), find_key(), find_key_for_reserve(), find_key_for_snapshot(), find_key_normalized(), ltgt_key(), foedus::storage::masstree::operator<<(), foedus::storage::masstree::MasstreeStoragePimpl::peek_volatile_page_boundaries_next_layer(), foedus::storage::masstree::MasstreeStoragePimpl::prefetch_pages_normalized_recurse(), reserve_initially_next_layer(), reserve_record_space(), track_moved_record(), foedus::storage::masstree::MasstreeStoragePimpl::verify_single_thread_border(), will_conflict(), and will_contain_next_layer().

                                                           {
     ASSERT_ND(index < kBorderPageMaxSlots);
     return slices_[index];
   }

Here is the caller graph for this function:

const Slot* foedus::storage::masstree::MasstreeBorderPage::get_slot ( SlotIndex index ) const

inline

Definition at line 631 of file masstree_page_impl.hpp.

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

Referenced by does_point_to_layer(), get_max_payload_length(), get_offset_in_bytes(), get_owner_id(), get_payload_length(), get_remainder_length(), initialize_as_layer_root_physical(), initialize_layer_root(), foedus::storage::masstree::operator<<(), replace_next_layer_snapshot(), track_moved_record(), try_expand_record_in_page_physical(), and verify_slot_lengthes().

                                                                    {
     ASSERT_ND(index < get_key_count());
     ASSERT_ND(index < kBorderPageMaxSlots);
     return reinterpret_cast<const Slot*>(this + 1) - index - 1;
   }

Here is the call graph for this function:

Here is the caller graph for this function:

Slot* foedus::storage::masstree::MasstreeBorderPage::get_slot ( SlotIndex index )

inline

Definition at line 637 of file masstree_page_impl.hpp.

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

                                                        {
     ASSERT_ND(index < get_key_count());
     ASSERT_ND(index < kBorderPageMaxSlots);
     return reinterpret_cast<Slot*>(this + 1) - index - 1;
   }

Here is the call graph for this function:

KeyLength foedus::storage::masstree::MasstreeBorderPage::get_suffix_length ( SlotIndex index ) const

inline

Definition at line 823 of file masstree_page_impl.hpp.

References foedus::storage::masstree::calculate_suffix_length(), and get_remainder_length().

Referenced by assert_entries_impl(), and foedus::storage::masstree::operator<<().

                                                                    {
     const KeyLength remainder_length = get_remainder_length(index);
     return calculate_suffix_length(remainder_length);
   }

Here is the call graph for this function:

Here is the caller graph for this function:

KeyLength foedus::storage::masstree::MasstreeBorderPage::get_suffix_length_aligned ( SlotIndex index ) const

inline

Definition at line 827 of file masstree_page_impl.hpp.

References foedus::storage::masstree::calculate_suffix_length_aligned(), and get_remainder_length().

Referenced by assert_entries_impl(), and get_record_payload().

                                                                            {
     const KeyLength remainder_length = get_remainder_length(index);
     return calculate_suffix_length_aligned(remainder_length);
   }

Here is the call graph for this function:

Here is the caller graph for this function:

void foedus::storage::masstree::MasstreeBorderPage::increase_next_offset ( DataOffset length )

inline

Definition at line 626 of file masstree_page_impl.hpp.

References ASSERT_ND.

Referenced by try_expand_record_in_page_physical().

                                                       {
     next_offset_ += length;
     ASSERT_ND(next_offset_ <= sizeof(data_));
   }

Here is the caller graph for this function:

void foedus::storage::masstree::MasstreeBorderPage::initialize_as_layer_root_physical	(	VolatilePagePointer	page_id,
		MasstreeBorderPage *	parent,
		SlotIndex	parent_index
	)

A physical-only method to initialize this page as a volatile page of a layer-root pointed from the given parent record.

It merely migrates the parent record without any logical change.

Precondition: !parent->header_.snapshot_: only for volatile page; parent->is_locked() && !parent->is_moved(); parent->get_slot(parent_index)->is_locked(); !parent->get_slot(parent_index)->is_moved(); !parent->get_slot(parent_index)->does_point_to_layer()

Definition at line 431 of file masstree_page_impl.cpp.

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

                           {
   // This method assumes that the record's payload space is spacious enough.
   // The caller must make it sure as pre-condition.
   ASSERT_ND(parent->is_locked());
   ASSERT_ND(!parent->is_moved());
   Slot* parent_slot = parent->get_slot(parent_index);
   ASSERT_ND(parent_slot->tid_.is_keylocked());
   ASSERT_ND(!parent_slot->tid_.is_moved());
   ASSERT_ND(!parent_slot->does_point_to_layer());
   ASSERT_ND(parent->get_max_payload_length(parent_index) >= sizeof(DualPagePointer));
   DualPagePointer pointer;
   pointer.snapshot_pointer_ = 0;
   pointer.volatile_pointer_ = page_id;
 
   // initialize the root page by copying the record
   initialize_volatile_page(
     parent->header_.storage_id_,
     page_id,
     parent->get_layer() + 1,
     kInfimumSlice,    // infimum slice
     kSupremumSlice);   // high-fence is supremum
   ASSERT_ND(!is_locked());
   initialize_layer_root(parent, parent_index);
   ASSERT_ND(!is_moved());
   ASSERT_ND(!is_retired());
 
   SlotLengthPart new_lengthes = parent_slot->read_lengthes_oneshot();
   new_lengthes.payload_length_ = sizeof(DualPagePointer);
   char* parent_payload = parent->get_record_payload(parent_index);
 
   // point to the new page. Be careful on ordering.
   std::memcpy(parent_payload, &pointer, sizeof(pointer));
   assorted::memory_fence_release();
   parent_slot->write_lengthes_oneshot(new_lengthes);
   assorted::memory_fence_release();
   parent_slot->tid_.xct_id_.set_next_layer();  // which also turns off delete-bit
 
   ASSERT_ND(parent->get_next_layer(parent_index)->volatile_pointer_ == page_id);
   assorted::memory_fence_release();
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void foedus::storage::masstree::MasstreeBorderPage::initialize_layer_root	(	const MasstreeBorderPage *	copy_from,
		SlotIndex	copy_index
	)

Copy the initial record that will be the only record for a new root page.

This is called when a new layer is created, and done in a thread-private memory. So, no synchronization needed.

Definition at line 298 of file masstree_page_impl.cpp.

Referenced by initialize_as_layer_root_physical().

                         {
   ASSERT_ND(get_key_count() == 0);
   ASSERT_ND(!is_locked());  // we don't lock a new page
   ASSERT_ND(copy_from->get_owner_id(copy_index)->is_keylocked());
 
   // This is a new page, so no worry on race.
   const SlotIndex new_index = 0;
   Slot* slot = get_new_slot(new_index);
   const Slot* parent_slot = copy_from->get_slot(copy_index);
   const SlotLengthPart parent_lengthes = parent_slot->lengthes_.components;
   const char* parent_record = copy_from->get_record_from_offset(parent_lengthes.offset_);
 
   KeyLength parent_remainder = parent_slot->remainder_length_;
   ASSERT_ND(parent_remainder != kInitiallyNextLayer);
   ASSERT_ND(parent_remainder > sizeof(KeySlice));
   KeyLength remainder = parent_remainder - sizeof(KeySlice);
 
   // retrieve the first 8 byte (or less) as the new slice.
   const KeySlice new_slice = slice_key(parent_record, parent_remainder);
   const PayloadLength payload_length = parent_lengthes.payload_length_;
   const KeyLength suffix_length_aligned = calculate_suffix_length_aligned(remainder);
   const DataOffset record_size = to_record_length(remainder, payload_length);
   const DataOffset new_offset = next_offset_;
 
   set_slice(new_index, new_slice);
 
   ASSERT_ND(next_offset_ == 0);
   slot->lengthes_.components.offset_ = new_offset;
   slot->lengthes_.components.unused_ = 0;
   slot->lengthes_.components.physical_record_length_ = record_size;
   slot->lengthes_.components.payload_length_ = payload_length;
   slot->original_physical_record_length_ = record_size;
   slot->remainder_length_ = remainder;
   slot->original_offset_ = new_offset;
   next_offset_ += record_size;
   consecutive_inserts_ = true;
 
   // use the same xct ID. This means we also inherit deleted flag.
   slot->tid_.xct_id_ = parent_slot->tid_.xct_id_;
   ASSERT_ND(!slot->tid_.xct_id_.is_next_layer());
   // but we don't want to inherit locks
   slot->tid_.lock_.reset();
   if (suffix_length_aligned > 0) {
     // because suffix parts are 8-byte aligned with zero padding, we can memcpy in 8-bytes unit
     std::memcpy(
       get_record_from_offset(new_offset),
       parent_record + sizeof(KeySlice),
       suffix_length_aligned);
   }
   if (payload_length > 0) {
     std::memcpy(
       get_record_payload_from_offsets(new_offset, remainder),
       copy_from->get_record_payload(copy_index),
       assorted::align8(payload_length));  // payload is zero-padded to 8 bytes, too.
   }
 
   // as we don't lock this page, we directly increment it to avoid is_locked assertion
   ++header_.key_count_;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void foedus::storage::masstree::MasstreeBorderPage::initialize_snapshot_page	(	StorageId	storage_id,
		SnapshotPagePointer	page_id,
		uint8_t	layer,
		KeySlice	low_fence,
		KeySlice	high_fence
	)

Definition at line 146 of file masstree_page_impl.cpp.

References foedus::storage::masstree::MasstreePage::initialize_snapshot_common(), and foedus::storage::kMasstreeBorderPageType.

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

                                   {
   initialize_snapshot_common(
     storage_id,
     page_id,
     kMasstreeBorderPageType,
     layer,
     0,
     low_fence,
     high_fence);
   consecutive_inserts_ = true;  // snapshot pages are always completely sorted
   next_offset_ = 0;  // well, already implicitly zero-ed, but to be clear
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void foedus::storage::masstree::MasstreeBorderPage::initialize_volatile_page	(	StorageId	storage_id,
		VolatilePagePointer	page_id,
		uint8_t	layer,
		KeySlice	low_fence,
		KeySlice	high_fence
	)

Definition at line 128 of file masstree_page_impl.cpp.

References foedus::storage::masstree::MasstreePage::initialize_volatile_common(), and foedus::storage::kMasstreeBorderPageType.

Referenced by initialize_as_layer_root_physical(), foedus::storage::masstree::MasstreeStoragePimpl::load_empty(), and foedus::storage::masstree::ReserveRecords::run().

                                   {
   initialize_volatile_common(
     storage_id,
     page_id,
     kMasstreeBorderPageType,
     layer,
     0,
     low_fence,
     high_fence);
   consecutive_inserts_ = true;  // initially key_count = 0, so of course sorted
   next_offset_ = 0;  // well, already implicitly zero-ed, but to be clear
 }

Here is the call graph for this function:

Here is the caller graph for this function:

bool foedus::storage::masstree::MasstreeBorderPage::is_consecutive_inserts ( ) const

inline

Whether this page is receiving only sequential inserts.

If this is true, cursor can skip its sorting phase. If this is a snapshot page, this is always true.

Definition at line 623 of file masstree_page_impl.hpp.

Referenced by foedus::storage::masstree::SplitBorder::decide_strategy(), foedus::storage::masstree::SplitBorder::run(), and foedus::storage::masstree::MasstreeStoragePimpl::verify_single_thread_border().

623 { return consecutive_inserts_; }

Here is the caller graph for this function:

int foedus::storage::masstree::MasstreeBorderPage::ltgt_key	(	SlotIndex	index,
		const char *	be_key,
		KeyLength	key_length
	)		const

inline

compare the key.

returns negative, 0, positive when the given key is smaller,same,larger.

Definition at line 1631 of file masstree_page_impl.hpp.

References ASSERT_ND, foedus::storage::masstree::MasstreePage::get_layer(), foedus::storage::masstree::kSliceLen, and foedus::storage::masstree::slice_layer().

                               {
   ASSERT_ND(key_length > get_layer() * kSliceLen);
   KeyLength remainder = key_length - get_layer() * kSliceLen;
   KeySlice slice = slice_layer(be_key, key_length, get_layer());
   const char* suffix = be_key + (get_layer() + 1) * kSliceLen;
   return ltgt_key(index, slice, suffix, remainder);
 }

Here is the call graph for this function:

int foedus::storage::masstree::MasstreeBorderPage::ltgt_key	(	SlotIndex	index,
		KeySlice	slice,
		const char *	suffix,
		KeyLength	remainder
	)		const

inline

Overload to receive slice+suffix.

Definition at line 1641 of file masstree_page_impl.hpp.

References ASSERT_ND, does_point_to_layer(), get_record(), get_remainder_length(), get_slice(), foedus::storage::masstree::kBorderPageMaxSlots, foedus::storage::masstree::kMaxKeyLength, and foedus::storage::masstree::kSliceLen.

                              {
   ASSERT_ND(index < kBorderPageMaxSlots);
   ASSERT_ND(remainder > 0);
   ASSERT_ND(remainder <= kMaxKeyLength);
   KeyLength rec_remainder = get_remainder_length(index);
   KeySlice rec_slice = get_slice(index);
   if (slice < rec_slice) {
     return -1;
   } else if (slice > rec_slice) {
     return 1;
   }
 
   if (remainder <= kSliceLen) {
     if (remainder == rec_remainder) {
       return 0;
     } else if (remainder < rec_remainder) {
       return -1;
     } else {
       return 1;
     }
   }
 
   ASSERT_ND(remainder > kSliceLen);
   if (rec_remainder <= kSliceLen) {
     return 1;
   }
   if (does_point_to_layer(index)) {
     return 0;
   }
   ASSERT_ND(rec_remainder <= kMaxKeyLength);
   KeyLength min_remainder = std::min(remainder, rec_remainder);
   const char* rec_suffix = get_record(index);
   int cmp = std::memcmp(suffix, rec_suffix, min_remainder);
   if (cmp != 0) {
     return cmp;
   }
 
   if (remainder == rec_remainder) {
     return 0;
   } else if (remainder < rec_remainder) {
     return -1;
   } else {
     return 1;
   }
 }

Here is the call graph for this function:

MasstreeBorderPage& foedus::storage::masstree::MasstreeBorderPage::operator= ( const MasstreeBorderPage & other )

delete

void foedus::storage::masstree::MasstreeBorderPage::prefetch ( ) const

inline

prefetch upto 256th bytes.

Definition at line 934 of file masstree_page_impl.hpp.

References foedus::assorted::prefetch_cachelines().

                                       {
     assorted::prefetch_cachelines(this, 4);
   }

Here is the call graph for this function:

void foedus::storage::masstree::MasstreeBorderPage::prefetch_additional_if_needed ( SlotIndex key_count ) const

inline

Definition at line 937 of file masstree_page_impl.hpp.

References foedus::storage::masstree::kBorderPageAdditionalHeaderSize, foedus::assorted::kCachelineSize, foedus::storage::masstree::kCommonPageHeaderSize, and foedus::assorted::prefetch_cachelines().

Referenced by find_key(), find_key_for_reserve(), find_key_normalized(), and foedus::storage::masstree::MasstreeStoragePimpl::peek_volatile_page_boundaries_next_layer().

                                                                               {
     const uint32_t kInitialPrefetchBytes = 4U * assorted::kCachelineSize;  // 256 bytes
     const SlotIndex kInitiallyFetched
       = (kInitialPrefetchBytes - kCommonPageHeaderSize - kBorderPageAdditionalHeaderSize)
         / sizeof(KeySlice);
     if (key_count > kInitiallyFetched) {
       // we initially prefetched 64*4 = 256 bytes: header and 22 key slices.
       // if we have more, prefetch now while we are still searching.
       uint16_t cachelines = ((key_count - kInitiallyFetched) / sizeof(KeySlice)) + 1;
       assorted::prefetch_cachelines(
         reinterpret_cast<const char*>(this) + kInitialPrefetchBytes,
         cachelines);
     }
   }

Here is the call graph for this function:

Here is the caller graph for this function:

void foedus::storage::masstree::MasstreeBorderPage::release_pages_recursive	(	const memory::GlobalVolatilePageResolver &	page_resolver,
		memory::PageReleaseBatch *	batch
	)

Definition at line 266 of file masstree_page_impl.cpp.

References ASSERT_ND, does_point_to_layer(), foedus::storage::masstree::MasstreePage::foster_twin_, foedus::storage::masstree::MasstreePage::get_key_count(), get_next_layer(), foedus::storage::masstree::MasstreePage::header(), foedus::storage::masstree::MasstreePage::header_, foedus::storage::PageVersion::is_moved(), foedus::storage::VolatilePagePointer::is_null(), foedus::storage::masstree::kBorderPageMaxSlots, foedus::storage::PageHeader::page_id_, foedus::storage::PageHeader::page_version_, foedus::memory::PageReleaseBatch::release(), release_pages_recursive(), foedus::storage::masstree::MasstreePage::release_pages_recursive_common(), foedus::memory::GlobalVolatilePageResolver::resolve_offset(), foedus::storage::DualPagePointer::volatile_pointer_, and foedus::storage::VolatilePagePointer::word.

Referenced by release_pages_recursive(), and foedus::storage::masstree::MasstreePage::release_pages_recursive_common().

                                  {
   if (header_.page_version_.is_moved()) {
     for (int i = 0; i < 2; ++i) {
       ASSERT_ND(!foster_twin_[i].is_null());
       MasstreeBorderPage* p
         = reinterpret_cast<MasstreeBorderPage*>(page_resolver.resolve_offset(foster_twin_[i]));
       p->release_pages_recursive(page_resolver, batch);
       foster_twin_[i].word = 0;
     }
   } else {
     SlotIndex key_count = get_key_count();
     ASSERT_ND(key_count <= kBorderPageMaxSlots);
     for (SlotIndex i = 0; i < key_count; ++i) {
       if (does_point_to_layer(i)) {
         DualPagePointer* pointer = get_next_layer(i);
         if (!pointer->volatile_pointer_.is_null()) {
           MasstreePage* child = reinterpret_cast<MasstreePage*>(
             page_resolver.resolve_offset(pointer->volatile_pointer_));
           child->release_pages_recursive_common(page_resolver, batch);
         }
       }
     }
   }
 
   VolatilePagePointer volatile_id;
   volatile_id.word = header().page_id_;
   batch->release(volatile_id);
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void foedus::storage::masstree::MasstreeBorderPage::replace_next_layer_snapshot ( SnapshotPagePointer pointer )

inline

Same as above, except this is used to transform an existing record at end to a next layer pointer.

Unlike set_next_layer, this shrinks the payload part.

Definition at line 1447 of file masstree_page_impl.hpp.

                                                                                        {
   ASSERT_ND(header().snapshot_);  // this is used only from snapshot composer
   ASSERT_ND(get_key_count() > 0);
   const SlotIndex index = get_key_count() - 1U;
 
   ASSERT_ND(!does_point_to_layer(index));
   ASSERT_ND(!get_owner_id(index)->xct_id_.is_next_layer());
 
   // Overwriting an existing slot with kInitiallyNextLayer is not generally safe,
   // but this is in snapshot page, so no worry on race.
   const KeyLength kRemainder = kInitiallyNextLayer;
   const DataOffset new_record_size = sizeof(DualPagePointer);
   ASSERT_ND(new_record_size == to_record_length(kRemainder, sizeof(DualPagePointer)));
 
   // This is in snapshot page, so no worry on race.
   Slot* slot = get_slot(index);
 
   // This is the last record in this page, right?
   ASSERT_ND(next_offset_
     == slot->lengthes_.components.offset_ + slot->lengthes_.components.physical_record_length_);
 
   // Here, we assume the snapshot border page always leaves sizeof(DualPagePointer) whenever
   // it creates a record. Otherwise we might not have enough space!
   // For this reason, we use can_accomodate_snapshot() rather than can_accomodate().
   ASSERT_ND(slot->lengthes_.components.offset_ + new_record_size + sizeof(Slot) * get_key_count()
     <= sizeof(data_));
   slot->lengthes_.components.physical_record_length_ = new_record_size;
   slot->lengthes_.components.payload_length_ = sizeof(DualPagePointer);
   slot->original_physical_record_length_ = new_record_size;
   slot->remainder_length_ = kRemainder;
   next_offset_ = slot->lengthes_.components.offset_ + new_record_size;
 
   slot->tid_.xct_id_.set_next_layer();
   DualPagePointer* dual_pointer = get_next_layer(index);
   dual_pointer->volatile_pointer_.clear();
   dual_pointer->snapshot_pointer_ = pointer;
 
   ASSERT_ND(does_point_to_layer(index));
 }

Here is the call graph for this function:

static DataOffset foedus::storage::masstree::MasstreeBorderPage::required_data_space	(	KeyLength	remainder_length,
		PayloadLength	payload_length
	)

inlinestatic

returns the byte size of required contiguous space in data_ to insert a new record of the given remainder/payload length.

This includes Slot size. Slices are not included as they are anyway statically placed.

See also: to_record_length()

Definition at line 687 of file masstree_page_impl.hpp.

References to_record_length().

Referenced by can_accomodate(), and can_accomodate_snapshot().

                                   {
     return to_record_length(remainder_length, payload_length) + sizeof(Slot);
   }

Here is the call graph for this function:

Here is the caller graph for this function:

void foedus::storage::masstree::MasstreeBorderPage::reserve_initially_next_layer	(	SlotIndex	index,
		xct::XctId	initial_owner_id,
		KeySlice	slice,
		const DualPagePointer &	pointer
	)

inline

For creating a record that is initially a next-layer.

Definition at line 1375 of file masstree_page_impl.hpp.

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

                                   {
   ASSERT_ND(index < kBorderPageMaxSlots);
   ASSERT_ND(header().snapshot_ || is_locked());
   ASSERT_ND(get_key_count() == index);
   ASSERT_ND(can_accomodate(index, sizeof(KeySlice), sizeof(DualPagePointer)));
   ASSERT_ND(next_offset_ % 8 == 0);
   ASSERT_ND(initial_owner_id.is_next_layer());
   ASSERT_ND(!initial_owner_id.is_deleted());
   const KeyLength remainder = kInitiallyNextLayer;
   const DataOffset record_size = to_record_length(remainder, sizeof(DualPagePointer));
   ASSERT_ND(record_size % 8 == 0);
   const DataOffset new_offset = next_offset_;
   set_slice(index, slice);
   // This is a new slot, so no worry on race.
   Slot* slot = get_new_slot(index);
   slot->lengthes_.components.offset_ = new_offset;
   slot->lengthes_.components.unused_ = 0;
   slot->lengthes_.components.physical_record_length_ = record_size;
   slot->lengthes_.components.payload_length_ = sizeof(DualPagePointer);
   slot->original_physical_record_length_ = record_size;
   slot->remainder_length_ = remainder;
   slot->original_offset_ = new_offset;
   next_offset_ += record_size;
   if (index == 0) {
     consecutive_inserts_ = true;
   } else if (consecutive_inserts_) {
     // This record must be the only full-length slice, so the check is simpler
     const KeySlice prev_slice = get_slice(index - 1);
     if (prev_slice > slice) {
       consecutive_inserts_ = false;
     }
   }
   slot->tid_.lock_.reset();
   slot->tid_.xct_id_ = initial_owner_id;
   *get_next_layer_from_offsets(new_offset, remainder) = pointer;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void foedus::storage::masstree::MasstreeBorderPage::reserve_record_space	(	SlotIndex	index,
		xct::XctId	initial_owner_id,
		KeySlice	slice,
		const void *	suffix,
		KeyLength	remainder_length,
		PayloadLength	payload_count
	)

inline

Installs a new physical record that doesn't exist logically (delete bit on).

This sets 1) slot, 2) suffix key, and 3) XctId. Payload is not set yet. This is executed as a system transaction.

Definition at line 1322 of file masstree_page_impl.hpp.

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

                                {
   ASSERT_ND(header().snapshot_ || initial_owner_id.is_deleted());
   ASSERT_ND(index < kBorderPageMaxSlots);
   ASSERT_ND(remainder_length <= kMaxKeyLength || remainder_length == kInitiallyNextLayer);
   ASSERT_ND(remainder_length != kInitiallyNextLayer || payload_count == sizeof(DualPagePointer));
   ASSERT_ND(header().snapshot_ || is_locked());
   ASSERT_ND(get_key_count() == index);
   ASSERT_ND(can_accomodate(index, remainder_length, payload_count));
   ASSERT_ND(next_offset_ % 8 == 0);
   const KeyLength suffix_length = calculate_suffix_length(remainder_length);
   const DataOffset record_size = to_record_length(remainder_length, payload_count);
   ASSERT_ND(record_size % 8 == 0);
   const DataOffset new_offset = next_offset_;
   set_slice(index, slice);
   // This is a new slot, so no worry on race.
   Slot* slot = get_new_slot(index);
   slot->lengthes_.components.offset_ = new_offset;
   slot->lengthes_.components.unused_ = 0;
   slot->lengthes_.components.physical_record_length_ = record_size;
   slot->lengthes_.components.payload_length_ = payload_count;
   slot->original_physical_record_length_ = record_size;
   slot->remainder_length_ = remainder_length;
   slot->original_offset_ = new_offset;
   next_offset_ += record_size;
   if (index == 0) {
     consecutive_inserts_ = true;
   } else if (consecutive_inserts_) {
     // do we have to turn off consecutive_inserts_ now?
     const KeySlice prev_slice = get_slice(index - 1);
     const KeyLength prev_klen = get_remainder_length(index - 1);
     if (prev_slice > slice || (prev_slice == slice && prev_klen > remainder_length)) {
       consecutive_inserts_ = false;
     }
   }
   slot->tid_.lock_.reset();
   slot->tid_.xct_id_ = initial_owner_id;
   if (suffix_length > 0) {
     char* record = get_record_from_offset(new_offset);
     std::memcpy(record, suffix, suffix_length);
     KeyLength suffix_length_aligned = assorted::align8(suffix_length);
     // zero-padding
     if (suffix_length_aligned > suffix_length) {
       std::memset(record + suffix_length, 0, suffix_length_aligned - suffix_length);
     }
   }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void foedus::storage::masstree::MasstreeBorderPage::set_slice	(	SlotIndex	index,
		KeySlice	slice
	)

inline

Definition at line 805 of file masstree_page_impl.hpp.

References ASSERT_ND, and foedus::storage::masstree::kBorderPageMaxSlots.

Referenced by append_next_layer_snapshot(), initialize_layer_root(), foedus::storage::masstree::SplitBorder::migrate_records(), reserve_initially_next_layer(), and reserve_record_space().

                                                                     {
     ASSERT_ND(index < kBorderPageMaxSlots);
     slices_[index] = slice;
   }

Here is the caller graph for this function:

static DataOffset foedus::storage::masstree::MasstreeBorderPage::to_record_length	(	KeyLength	remainder_length,
		PayloadLength	payload_length
	)

inlinestatic

returns minimal physical_record_length_ for the given remainder/payload length.

Attention: this doesn't count the space for Slot nor slices.

See also: required_data_space()

Definition at line 674 of file masstree_page_impl.hpp.

References foedus::assorted::align8(), and foedus::storage::masstree::calculate_suffix_length_aligned().

Referenced by append_next_layer_snapshot(), initialize_layer_root(), foedus::storage::masstree::SplitBorder::migrate_records(), replace_next_layer_snapshot(), required_data_space(), reserve_initially_next_layer(), reserve_record_space(), and try_expand_record_in_page_physical().

                                   {
     KeyLength suffix_length_aligned = calculate_suffix_length_aligned(remainder_length);
     return suffix_length_aligned + assorted::align8(payload_length);
   }

Here is the call graph for this function:

Here is the caller graph for this function:

SlotIndex foedus::storage::masstree::MasstreeBorderPage::to_slot_index ( const Slot * slot ) const

inline

Definition at line 649 of file masstree_page_impl.hpp.

References ASSERT_ND.

Referenced by track_moved_record(), and track_moved_record_next_layer().

                                                                        {
     ASSERT_ND(slot);
     int64_t index = reinterpret_cast<const Slot*>(this + 1) - slot - 1;
     ASSERT_ND(index >= 0);
     ASSERT_ND(index < static_cast<int64_t>(sizeof(data_) / sizeof(Slot)));
     return static_cast<SlotIndex>(index);
   }

Here is the caller graph for this function:

xct::TrackMovedRecordResult foedus::storage::masstree::MasstreeBorderPage::track_moved_record	(	Engine *	engine,
		xct::RwLockableXctId *	old_address,
		xct::WriteXctAccess *	write_set
	)

See also: StorageManager::track_moved_record()

Definition at line 534 of file masstree_page_impl.cpp.

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

                         {
   ASSERT_ND(owner_address->is_moved() || owner_address->is_next_layer());
   ASSERT_ND(!header().snapshot_);
   ASSERT_ND(header().get_page_type() == kMasstreeBorderPageType);
 
   // Slot begins with TID, so it's also the slot address
   Slot* slot = reinterpret_cast<Slot*>(owner_address);
   ASSERT_ND(&slot->tid_ == owner_address);
   const SlotIndex original_index = to_slot_index(slot);
   ASSERT_ND(original_index < kBorderPageMaxSlots);
   ASSERT_ND(original_index < get_key_count());
 
   const KeyLength remainder = slot->remainder_length_;
   // If it's originally a next-layer record, why we took it as a record? This shouldn't happen.
   ASSERT_ND(remainder != kInitiallyNextLayer);
 
   if (does_point_to_layer(original_index)) {
     return track_moved_record_next_layer(engine, owner_address);
   }
 
   // otherwise, we can track without key information within this layer.
   // the slice and key length is enough to identify the record.
   ASSERT_ND(is_moved());
   ASSERT_ND(has_foster_child());
   ASSERT_ND(!is_foster_minor_null());
   ASSERT_ND(!is_foster_major_null());
   const char* suffix = get_record(original_index);
   KeySlice slice = get_slice(original_index);
 
   // if remainder <= 8 : this layer can have only one record that has this slice and this length.
   // if remainder > 8  : this layer has either the exact record, or it's now a next layer pointer.
 
   // recursively track. although probably it's only one level
   MasstreeBorderPage* cur_page = this;
   const memory::GlobalVolatilePageResolver& resolver
     = engine->get_memory_manager()->get_global_volatile_page_resolver();
   while (true) {
     cur_page = cur_page->track_foster_child(slice, resolver);
 
     // now cur_page must be the page that contains the record.
     // the only exception is
     // 1) again the record is being moved concurrently
     // 2) the record was moved to another layer
     SlotIndex index = cur_page->find_key(slice, suffix, remainder);
     if (index == kBorderPageMaxSlots) {
       // this can happen rarely because we are not doing the stable version trick here.
       // this is rare, so we just abort. no safety violation.
       VLOG(0) << "Very interesting. moved record not found due to concurrent updates";
       return xct::TrackMovedRecordResult();
     }
 
     Slot* cur_slot = cur_page->get_slot(index);
     xct::RwLockableXctId* new_owner_address = &cur_slot->tid_;
     char* new_record_address = cur_page->get_record(index);
     if (cur_page->does_point_to_layer(index)) {
       // another rare case. the record has been now moved to another layer.
       if (remainder <= sizeof(KeySlice)) {
         // the record we are looking for can't be stored in next layer..
         VLOG(0) << "Wtf 2. moved record in next layer not found. Probably due to concurrent thread";
         return xct::TrackMovedRecordResult();
       }
 
       VLOG(0) << "Interesting. moved record are now in another layer. further track.";
       return cur_page->track_moved_record_next_layer(engine, new_owner_address);
     }
 
     // Otherwise, this is it!
     // be careful, we give get_record() as "payload". the word "payload" is a bit overused here.
     return xct::TrackMovedRecordResult(new_owner_address, new_record_address);
   }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

xct::TrackMovedRecordResult foedus::storage::masstree::MasstreeBorderPage::track_moved_record_next_layer	(	Engine *	engine,
		xct::RwLockableXctId *	old_address
	)

This one further tracks it to next layer.

Instead it requires a non-null write_set.

Definition at line 609 of file masstree_page_impl.cpp.

Referenced by track_moved_record(), and track_moved_record_next_layer().

                                      {
   ASSERT_ND(!header().snapshot_);
   ASSERT_ND(header().get_page_type() == kMasstreeBorderPageType);
   ASSERT_ND(owner_address->xct_id_.is_next_layer());
 
   Slot* slot = reinterpret_cast<Slot*>(owner_address);
   ASSERT_ND(&slot->tid_ == owner_address);
   const SlotIndex original_index = to_slot_index(slot);
   ASSERT_ND(original_index < kBorderPageMaxSlots);
   ASSERT_ND(original_index < get_key_count());
   ASSERT_ND(does_point_to_layer(original_index));
 
   // The new masstree page layout leaves the original suffix untouched.
   // Thus, we can always retrieve the original key from it no matter whether
   // the record moved offset to expand. In case the record was expanded in-page,
   // we use original_xxx below.
   const KeyLength remainder = slot->remainder_length_;
   ASSERT_ND(remainder != kInitiallyNextLayer);
   if (UNLIKELY(remainder <= sizeof(KeySlice))) {
     LOG(ERROR) << "WTF. The original record was too short to get moved to next-layer, but it did?";
     return xct::TrackMovedRecordResult();
   }
 
   const char* original_suffix = get_record(original_index);
   const uint8_t cur_layer = get_layer();
   const uint8_t next_layer = cur_layer + 1U;
   const KeySlice next_slice = slice_key(original_suffix, remainder - sizeof(KeySlice));
   const KeyLength next_remainder = remainder - sizeof(KeySlice);
   const char* next_suffix = original_suffix + sizeof(KeySlice);
 
   VolatilePagePointer root_pointer = get_next_layer(original_index)->volatile_pointer_;
   if (root_pointer.is_null()) {
     VLOG(0) << "Wtf. moved record in next layer not found. Probably due to concurrent thread";
     return xct::TrackMovedRecordResult();
   }
 
   const memory::GlobalVolatilePageResolver& resolver
     = engine->get_memory_manager()->get_global_volatile_page_resolver();
   MasstreePage* cur_page
     = reinterpret_cast<MasstreeBorderPage*>(resolver.resolve_offset(root_pointer));
   ASSERT_ND(cur_page->get_low_fence() == kInfimumSlice && cur_page->is_high_fence_supremum());
   ASSERT_ND(cur_page->get_layer() == next_layer);
 
   while (true) {
     ASSERT_ND(cur_page->get_layer() == next_layer);
     ASSERT_ND(cur_page->within_fences(next_slice));
 
     if (!cur_page->is_border()) {
       MasstreeIntermediatePage* casted = reinterpret_cast<MasstreeIntermediatePage*>(cur_page);
       uint8_t index = casted->find_minipage(next_slice);
       MasstreeIntermediatePage::MiniPage& minipage = casted->get_minipage(index);
       uint8_t index_mini = minipage.find_pointer(next_slice);
       VolatilePagePointer pointer = minipage.pointers_[index_mini].volatile_pointer_;
       if (pointer.is_null()) {
         VLOG(0) << "Wtf 1. moved record in next layer not found. Probably due to concurrent thread";
         return xct::TrackMovedRecordResult();
       }
       cur_page = reinterpret_cast<MasstreePage*>(resolver.resolve_offset(pointer));
       ASSERT_ND(cur_page->get_layer() == next_layer);
       ASSERT_ND(cur_page->within_fences(next_slice));
       continue;
     }
 
     // now cur_page must be the page that contains the record.
     // the only exception is
     // 1) again the record is being moved concurrently
     // 2) the record was moved to another layer
     MasstreeBorderPage* casted = reinterpret_cast<MasstreeBorderPage*>(cur_page);
     // we track foster child in border pages only
     casted = casted->track_foster_child(next_slice, resolver);
     ASSERT_ND(casted != this);
     SlotIndex index = casted->find_key(next_slice, next_suffix, next_remainder);
     if (index == kBorderPageMaxSlots) {
       VLOG(0) << "Very interesting. moved record not found due to concurrent updates";
       return xct::TrackMovedRecordResult();
     }
 
     xct::RwLockableXctId* new_owner_address = casted->get_owner_id(index);
     ASSERT_ND(new_owner_address != owner_address);
     char* new_record_address = casted->get_record(index);
     if (casted->does_point_to_layer(index)) {
       // the record has been now moved to yet another layer.
       if (next_remainder <= sizeof(KeySlice)) {
         // the record we are looking for can't be stored in next layer..
         VLOG(0) << "Wtf 2. moved record in next layer not found. Probably due to concurrent thread";
         return xct::TrackMovedRecordResult();
       }
 
       VLOG(0) << "Interesting. moved record are now in another layer. further track.";
       return casted->track_moved_record_next_layer(engine, new_owner_address);
     }
 
     // be careful, we give get_record() as "payload". the word "payload" is a bit overused here.
     return xct::TrackMovedRecordResult(new_owner_address, new_record_address);
   }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

bool foedus::storage::masstree::MasstreeBorderPage::try_expand_record_in_page_physical	(	PayloadLength	payload_count,
		SlotIndex	record_index
	)

A physical-only method to expand a record within this page without any logical change.

Precondition: !header_.snapshot_: only for volatile page; is_locked() && !is_moved(); get_slot(record_index)->is_locked() && !get_slot(record_index)->is_moved()

Returns: This method might fail if there isn't enough space. In that case it returns false.

Definition at line 360 of file masstree_page_impl.cpp.

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

                           {
   ASSERT_ND(!header_.snapshot_);
   ASSERT_ND(is_locked());
   ASSERT_ND(!is_moved());
   ASSERT_ND(record_index < get_key_count());
   DVLOG(2) << "Expanding record.. current max=" << get_max_payload_length(record_index)
     << ", which must become " << payload_count;
 
   ASSERT_ND(verify_slot_lengthes(record_index));
   Slot* old_slot = get_slot(record_index);
   ASSERT_ND(!old_slot->tid_.is_moved());
   ASSERT_ND(old_slot->tid_.is_keylocked());
   ASSERT_ND(!old_slot->does_point_to_layer());
   const SlotLengthPart lengthes = old_slot->read_lengthes_oneshot();
   const KeyLength remainder_length = old_slot->remainder_length_;
   const DataOffset record_length = to_record_length(remainder_length, payload_count);
   const DataOffset available = available_space();
 
   // 1. Trivial expansion if the record is placed at last. Fastest.
   if (get_next_offset() == lengthes.offset_ + lengthes.physical_record_length_) {
     const DataOffset diff = record_length - lengthes.physical_record_length_;
     DVLOG(1) << "Lucky, expanding a record at last record region. diff=" << diff;
     if (available >= diff) {
       DVLOG(2) << "woo. yes, we can just increase the length";
       old_slot->lengthes_.components.physical_record_length_ = record_length;
       assorted::memory_fence_release();
       increase_next_offset(diff);
       assorted::memory_fence_release();
       return true;
     }
   }
 
   // 2. In-page expansion. Fast.
   if (available >= record_length) {
     DVLOG(2) << "Okay, in-page record expansion.";
     // We have to make sure all threads see a valid state, either new or old.
     SlotLengthPart new_lengthes = lengthes;
     new_lengthes.offset_ = get_next_offset();
     new_lengthes.physical_record_length_ = record_length;
     const char* old_record = get_record_from_offset(lengthes.offset_);
     char* new_record = get_record_from_offset(new_lengthes.offset_);
 
     // 2-a. Create the new record region.
     if (lengthes.physical_record_length_ > 0) {
       std::memcpy(new_record, old_record, lengthes.physical_record_length_);
       assorted::memory_fence_release();
     }
 
     // 2-b. announce the new location in one-shot.
     old_slot->write_lengthes_oneshot(new_lengthes);
     assorted::memory_fence_release();
     // We don't have to change TID here because we did nothing logically.
     // Reading transactions are safe to read either old or new record regions.
     // See comments in MasstreeCommonLogType::apply_record_prepare() for how we make it safe
     // for writing transactions.
 
     increase_next_offset(record_length);
     assorted::memory_fence_release();
     return true;
   }
 
   // 3. ouch. we need to split the page to complete it. beyond this method.
   DVLOG(1) << "Umm, we need to split this page for record expansion. available="
     << available << ", record_length=" << record_length
     << ", record_index=" << record_index
     << ", key_count=" << get_key_count();
   return false;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

bool foedus::storage::masstree::MasstreeBorderPage::verify_slot_lengthes ( SlotIndex index ) const

Returns: whether the length information seems okay. used only for assertions.

Definition at line 708 of file masstree_page_impl.cpp.

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

                                                                    {
   const Slot* slot = get_slot(index);
   SlotLengthPart lengthes = slot->lengthes_.components;
   if (lengthes.offset_ % 8 != 0) {
     ASSERT_ND(false);
     return false;
   }
   if (lengthes.physical_record_length_ % 8 != 0) {
     ASSERT_ND(false);
     return false;
   }
   if (lengthes.offset_ + lengthes.physical_record_length_ > sizeof(data_)) {
     ASSERT_ND(false);
     return false;
   }
 
   if (slot->remainder_length_ == kInitiallyNextLayer) {
     if (!slot->does_point_to_layer()) {
       ASSERT_ND(false);
       return false;
     }
   }
   // the only case we move the record in-page is to get a larger record size.
   if (lengthes.offset_ != slot->original_offset_) {
     if (lengthes.offset_ < slot->original_offset_) {
       ASSERT_ND(false);
       return false;
     }
     if (lengthes.physical_record_length_ <= slot->original_physical_record_length_) {
       ASSERT_ND(false);
       return false;
     }
   }
 
   if (slot->does_point_to_layer()) {
     if (slot->remainder_length_ <= sizeof(KeySlice)) {
       ASSERT_ND(false);
       return false;
     }
     if (lengthes.payload_length_ != sizeof(DualPagePointer)) {
       ASSERT_ND(false);
       return false;
     }
   } else {
     if (lengthes.payload_length_ > slot->get_max_payload_peek()) {
       ASSERT_ND(false);
       return false;
     }
   }
   return true;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

bool foedus::storage::masstree::MasstreeBorderPage::will_conflict	(	SlotIndex	index,
		const char *	be_key,
		KeyLength	key_length
	)		const

inline

Returns whether inserting the key will cause creation of a new next layer.

This is mainly used for assertions.

Definition at line 1690 of file masstree_page_impl.hpp.

References ASSERT_ND, foedus::storage::masstree::MasstreePage::get_layer(), foedus::storage::masstree::kSliceLen, and foedus::storage::masstree::slice_layer().

                               {
   ASSERT_ND(key_length > get_layer() * kSliceLen);
   KeyLength remainder = key_length - get_layer() * kSliceLen;
   KeySlice slice = slice_layer(be_key, key_length, get_layer());
   return will_conflict(index, slice, remainder);
 }

Here is the call graph for this function:

bool foedus::storage::masstree::MasstreeBorderPage::will_conflict	(	SlotIndex	index,
		KeySlice	slice,
		KeyLength	remainder
	)		const

inline

Overload to receive slice.

Definition at line 1699 of file masstree_page_impl.hpp.

References ASSERT_ND, get_remainder_length(), get_slice(), foedus::storage::masstree::kBorderPageMaxSlots, and foedus::storage::masstree::kSliceLen.

                              {
   ASSERT_ND(index < kBorderPageMaxSlots);
   ASSERT_ND(remainder > 0);
   if (slice != get_slice(index)) {
     return false;
   }
   KeyLength rec_remainder = get_remainder_length(index);
   if (remainder > kSliceLen && rec_remainder > kSliceLen) {
     return true;  // need to create next layer
   }
   return (remainder == rec_remainder);  // if same, it's exactly the same key
 }

Here is the call graph for this function:

bool foedus::storage::masstree::MasstreeBorderPage::will_contain_next_layer	(	SlotIndex	index,
		const char *	be_key,
		KeyLength	key_length
	)		const

inline

Returns whether the record is a next-layer pointer that would contain the key.

Definition at line 1714 of file masstree_page_impl.hpp.

References ASSERT_ND, foedus::storage::masstree::MasstreePage::get_layer(), foedus::storage::masstree::kSliceLen, and foedus::storage::masstree::slice_layer().

                               {
   ASSERT_ND(key_length > get_layer() * kSliceLen);
   KeyLength remainder = key_length - get_layer() * kSliceLen;
   KeySlice slice = slice_layer(be_key, key_length, get_layer());
   return will_contain_next_layer(index, slice, remainder);
 }

Here is the call graph for this function:

bool foedus::storage::masstree::MasstreeBorderPage::will_contain_next_layer	(	SlotIndex	index,
		KeySlice	slice,
		KeyLength	remainder
	)		const

inline

Definition at line 1723 of file masstree_page_impl.hpp.

References ASSERT_ND, does_point_to_layer(), get_slice(), foedus::storage::masstree::kBorderPageMaxSlots, and foedus::storage::masstree::kSliceLen.

                              {
   ASSERT_ND(index < kBorderPageMaxSlots);
   ASSERT_ND(remainder > 0);
   return slice == get_slice(index) && does_point_to_layer(index) && remainder > kSliceLen;
 }

Here is the call graph for this function:

Friends And Related Function Documentation

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

friend

defined in masstree_page_debug.cpp.

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;
 }

friend struct SplitBorder

friend

Definition at line 446 of file masstree_page_impl.hpp.

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

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

Detailed Description

Classes

Public Types

Public Member Functions

Static Public Member Functions

Friends

Additional Inherited Members

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation