libfoedus-core
FOEDUS Core Library
foedus::xct::XctId Struct Reference

Persistent status part of Transaction ID. More...

Detailed Description

Persistent status part of Transaction ID.

Unlike what [TU13] Sec 4.2 defines, FOEDUS's TID is 128 bit to contain more information. XctId represents a half (64bit) of TID that is used to represent persistent status of the record, such as record versions. The locking-mechanism part is separated to another half; McsWwLock.

Bit Assignments
BitsNameDescription
1Psuedo-delete bitWhether te key is logically non-existent.
2Moved bitThis is used for the Master-tree foster-twin protocol. when a record is moved from one page to another during split.
3BeingWrittenBefore we start applying modifications to a record, we set true to this so that optimistic-read can easily check for half-updated value. After the modification, we set false to this. Of course with appropriate fences.
4NextLayerThis is used only in Masstree. This bit indicates whether the record represents a pointer to next layer. False if it is a tuple itself. We put this information as part of XctId because we sometimes have to transactionally know whether the record is a next-layer pointer or not. There is something wrong if a read-set or write-set contains an XctId whose NextLayer bit is ON, because then the record is not a logical tuple. In other words, a reading transaction can efficiently protect their reads on a record that might become a next-layer pointer with a simple check after the usual read protocol.
5..32EpochThe recent owning transaction was in this Epoch. We don't consume full 32 bits for epoch. Assuming 20ms per epoch, 28bit still represents 1 year. All epochs will be refreshed by then or we can have some periodic mantainance job to make it sure.
33..64OrdinalThe recent owning transaction had this ordinal in the epoch. We assign 32 bits. Thus we no longer have the case where we have to increment current epoch even when there are many dependencies between transactions. We still have the machanism to do so, but in reality it won't be triggered.
Greater than/Less than as 64-bit integer
The last 60 bits represent the serialization order of the transaction. Sometimes not exactly the chronological order, but enough to assure serializability, see discussion in Sec 4.2 of [TU13]. This class thus provides before() method to check strict order of two instantances. Be aware of the following things, though:
  • Epoch might be invalid/uninitialized (zero). An invalid epoch is before everything else.
  • Epoch might wrap-around. We use the same wrap-around handling as foedus::Epoch.
  • Ordinal is not a strict ordinal unless there is a dependency between transactions in different cores. In that case, commit protocol adjusts the ordinal for serializability. See [TU13] or their code (gen_commit_tid() in proto2_impl.h).
  • We can NOT provide "equals" semantics via simple integer comparison. 61th- bits are status bits, thus we have to mask it. equals_serial_order() does it.
No Thread-ID
This is one difference from SILO. FOEDUS's XctID does not store thread-ID of last commit. We don't use it for any purpose.
POD
This is a POD struct. Default destructor/copy-constructor/assignment operator work fine.

Definition at line 955 of file xct_id.hpp.

#include <xct_id.hpp>

Public Member Functions

 XctId ()
 
void set (Epoch::EpochInteger epoch_int, uint32_t ordinal)
 
Epoch get_epoch () const __attribute__((always_inline))
 
void set_epoch (Epoch epoch) __attribute__((always_inline))
 
Epoch::EpochInteger get_epoch_int () const __attribute__((always_inline))
 
void set_epoch_int (Epoch::EpochInteger epoch_int) __attribute__((always_inline))
 
bool is_valid () const __attribute__((always_inline))
 
uint32_t get_ordinal () const __attribute__((always_inline))
 
void set_ordinal (uint32_t ordinal) __attribute__((always_inline))
 
void increment_ordinal () __attribute__((always_inline))
 
int compare_epoch_and_orginal (const XctId &other) const __attribute__((always_inline))
 Returns -1, 0, 1 when this is less than, same, larger than other in terms of epoch/ordinal. More...
 
void set_being_written () __attribute__((always_inline))
 
void set_write_complete () __attribute__((always_inline))
 
XctId spin_while_being_written () const __attribute__((always_inline))
 Returns a version of this Xid whose being_written flag is off. More...
 
void set_deleted () __attribute__((always_inline))
 
void set_notdeleted () __attribute__((always_inline))
 
void set_moved () __attribute__((always_inline))
 
void set_next_layer () __attribute__((always_inline))
 
bool is_being_written () const __attribute__((always_inline))
 
bool is_deleted () const __attribute__((always_inline))
 
bool is_moved () const __attribute__((always_inline))
 
bool is_next_layer () const __attribute__((always_inline))
 
bool needs_track_moved () const __attribute__((always_inline))
 is_moved() || is_next_layer() More...
 
bool operator== (const XctId &other) const __attribute__((always_inline))
 
bool operator!= (const XctId &other) const __attribute__((always_inline))
 
void store_max (const XctId &other) __attribute__((always_inline))
 Kind of std::max(this, other). More...
 
bool before (const XctId &other) const __attribute__((always_inline))
 Returns if this XctId is before other in serialization order, meaning this is either an invalid (unused) epoch or strictly less than the other. More...
 
void clear_status_bits ()
 

Public Attributes

uint64_t data_
 

Friends

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

Constructor & Destructor Documentation

foedus::xct::XctId::XctId ( )
inline

Definition at line 956 of file xct_id.hpp.

956 : data_(0) {}

Member Function Documentation

bool foedus::xct::XctId::before ( const XctId other) const
inline

Returns if this XctId is before other in serialization order, meaning this is either an invalid (unused) epoch or strictly less than the other.

Precondition
other.is_valid()

Definition at line 1074 of file xct_id.hpp.

References ASSERT_ND, foedus::Epoch::before(), get_epoch(), get_epoch_int(), and get_ordinal().

Referenced by foedus::xct::XctManagerPimpl::precommit_xct_apply(), foedus::xct::Xct::remember_previous_xct_id(), and store_max().

1074  {
1075  ASSERT_ND(other.is_valid());
1076  // compare epoch, then ordinal
1077  if (get_epoch_int() != other.get_epoch_int()) {
1078  return get_epoch().before(other.get_epoch());
1079  }
1080  return get_ordinal() < other.get_ordinal();
1081  }
Epoch::EpochInteger get_epoch_int() const __attribute__((always_inline))
Definition: xct_id.hpp:966
uint32_t get_ordinal() const __attribute__((always_inline))
Definition: xct_id.hpp:976
Epoch get_epoch() const __attribute__((always_inline))
Definition: xct_id.hpp:964
#define ASSERT_ND(x)
A warning-free wrapper macro of assert() that has no performance effect in release mode even when 'x'...
Definition: assert_nd.hpp:72
bool before(const Epoch &other) const
Returns if this epoch is before the given epoch in the sense of distance defined in RFC 1982...
Definition: epoch.hpp:176

Here is the call graph for this function:

Here is the caller graph for this function:

void foedus::xct::XctId::clear_status_bits ( )
inline

Definition at line 1083 of file xct_id.hpp.

References data_, and foedus::xct::kXctIdMaskSerializer.

Referenced by foedus::xct::XctManagerPimpl::precommit_xct_apply().

const uint64_t kXctIdMaskSerializer
Definition: xct_id.hpp:887

Here is the caller graph for this function:

int foedus::xct::XctId::compare_epoch_and_orginal ( const XctId other) const
inline

Returns -1, 0, 1 when this is less than, same, larger than other in terms of epoch/ordinal.

Precondition
this->is_valid(), other.is_valid()
this->get_ordinal() != 0, other.get_ordinal() != 0

Definition at line 993 of file xct_id.hpp.

References ASSERT_ND, get_epoch(), get_epoch_int(), get_ordinal(), and foedus::Epoch::is_valid().

Referenced by foedus::storage::hash::HashTmpBin::delete_record(), foedus::storage::hash::HashTmpBin::insert_record(), foedus::storage::hash::HashTmpBin::overwrite_record(), and foedus::storage::hash::HashTmpBin::update_record().

993  {
994  // compare epoch
995  if (get_epoch_int() != other.get_epoch_int()) {
996  Epoch this_epoch = get_epoch();
997  Epoch other_epoch = other.get_epoch();
998  ASSERT_ND(this_epoch.is_valid());
999  ASSERT_ND(other_epoch.is_valid());
1000  if (this_epoch < other_epoch) {
1001  return -1;
1002  } else {
1003  ASSERT_ND(this_epoch > other_epoch);
1004  return 1;
1005  }
1006  }
1007 
1008  // if the epoch is the same, compare in_epoch_ordinal_.
1009  ASSERT_ND(get_epoch() == other.get_epoch());
1010  if (get_ordinal() < other.get_ordinal()) {
1011  return -1;
1012  } else if (get_ordinal() > other.get_ordinal()) {
1013  return 1;
1014  } else {
1015  return 0;
1016  }
1017  }
Epoch::EpochInteger get_epoch_int() const __attribute__((always_inline))
Definition: xct_id.hpp:966
uint32_t get_ordinal() const __attribute__((always_inline))
Definition: xct_id.hpp:976
Epoch get_epoch() const __attribute__((always_inline))
Definition: xct_id.hpp:964
#define ASSERT_ND(x)
A warning-free wrapper macro of assert() that has no performance effect in release mode even when 'x'...
Definition: assert_nd.hpp:72

Here is the call graph for this function:

Here is the caller graph for this function:

Epoch::EpochInteger foedus::xct::XctId::get_epoch_int ( ) const
inline

Definition at line 966 of file xct_id.hpp.

References data_.

Referenced by before(), compare_epoch_and_orginal(), get_epoch(), is_valid(), and foedus::log::on_non_durable_meta_log_found().

966  {
967  return (data_ & kXctIdMaskEpoch) >> 32;
968  }
const uint64_t kXctIdMaskEpoch
Definition: xct_id.hpp:888

Here is the caller graph for this function:

uint32_t foedus::xct::XctId::get_ordinal ( ) const
inline

Definition at line 976 of file xct_id.hpp.

References ASSERT_ND, and data_.

Referenced by foedus::snapshot::MergeSort::assert_sorted(), before(), compare_epoch_and_orginal(), increment_ordinal(), foedus::xct::Xct::issue_next_id(), foedus::log::on_non_durable_meta_log_found(), foedus::xct::operator<<(), foedus::xct::XctManagerPimpl::precommit_xct_apply(), foedus::storage::array::prepare_sort_entries(), foedus::storage::hash::prepare_sort_entries(), foedus::storage::masstree::prepare_sort_entries(), and foedus::snapshot::LogReducerRef::verify_log_chunk().

976  {
977  ASSERT_ND(static_cast<uint32_t>(data_) <= kMaxXctOrdinal);
978  return static_cast<uint32_t>(data_);
979  }
const uint64_t kMaxXctOrdinal
Maximum value of in-epoch ordinal.
Definition: xct_id.hpp:898
#define ASSERT_ND(x)
A warning-free wrapper macro of assert() that has no performance effect in release mode even when 'x'...
Definition: assert_nd.hpp:72

Here is the caller graph for this function:

void foedus::xct::XctId::increment_ordinal ( )
inline

Definition at line 984 of file xct_id.hpp.

References get_ordinal(), and set_ordinal().

984  {
985  uint32_t ordinal = get_ordinal();
986  set_ordinal(ordinal + 1U);
987  }
uint32_t get_ordinal() const __attribute__((always_inline))
Definition: xct_id.hpp:976
void set_ordinal(uint32_t ordinal) __attribute__((always_inline))
Definition: xct_id.hpp:980

Here is the call graph for this function:

bool foedus::xct::XctId::is_deleted ( ) const
inline

Definition at line 1040 of file xct_id.hpp.

References data_.

Referenced by foedus::storage::masstree::MasstreeStoragePimpl::delete_general(), foedus::storage::hash::HashStoragePimpl::delete_record(), foedus::storage::hash::HashTmpBin::delete_record(), foedus::storage::masstree::MasstreeStoragePimpl::increment_general(), foedus::storage::hash::HashStoragePimpl::increment_record(), foedus::storage::masstree::MasstreeStoragePimpl::insert_general(), foedus::storage::hash::HashStoragePimpl::insert_record(), foedus::storage::hash::HashTmpBin::insert_record(), foedus::xct::LockableXctId::is_deleted(), foedus::xct::RwLockableXctId::is_deleted(), foedus::storage::masstree::MasstreeCursor::next(), foedus::storage::masstree::MasstreeCursor::open(), foedus::xct::operator<<(), foedus::storage::masstree::MasstreeStoragePimpl::overwrite_general(), foedus::storage::hash::HashStoragePimpl::overwrite_record(), foedus::storage::hash::HashTmpBin::overwrite_record(), foedus::xct::XctManagerPimpl::precommit_xct_apply(), foedus::storage::masstree::MasstreeBorderPage::reserve_initially_next_layer(), foedus::storage::masstree::MasstreeBorderPage::reserve_record_space(), foedus::storage::masstree::MasstreeStoragePimpl::retrieve_general(), foedus::storage::masstree::MasstreeStoragePimpl::retrieve_part_general(), foedus::storage::hash::HashTmpBin::update_record(), foedus::storage::masstree::MasstreeStoragePimpl::upsert_general(), and foedus::storage::hash::HashStoragePimpl::upsert_record().

1040 { return (data_ & kXctIdDeletedBit) != 0; }
const uint64_t kXctIdDeletedBit
Definition: xct_id.hpp:883

Here is the caller graph for this function:

bool foedus::xct::XctId::is_next_layer ( ) const
inline
bool foedus::xct::XctId::needs_track_moved ( ) const
inline

is_moved() || is_next_layer()

Definition at line 1044 of file xct_id.hpp.

References data_.

Referenced by foedus::xct::LockableXctId::needs_track_moved(), and foedus::xct::RwLockableXctId::needs_track_moved().

1044  {
1045  return (data_ & (kXctIdMovedBit | kXctIdNextLayerBit)) != 0;
1046  }
const uint64_t kXctIdMovedBit
Definition: xct_id.hpp:884
const uint64_t kXctIdNextLayerBit
Definition: xct_id.hpp:886

Here is the caller graph for this function:

bool foedus::xct::XctId::operator!= ( const XctId other) const
inline

Definition at line 1050 of file xct_id.hpp.

References data_.

1050 { return data_ != other.data_; }
bool foedus::xct::XctId::operator== ( const XctId other) const
inline

Definition at line 1049 of file xct_id.hpp.

References data_.

1049 { return data_ == other.data_; }
void foedus::xct::XctId::set ( Epoch::EpochInteger  epoch_int,
uint32_t  ordinal 
)
inline

Definition at line 958 of file xct_id.hpp.

References ASSERT_ND, data_, and foedus::Epoch::kEpochIntOverflow.

Referenced by foedus::storage::hash::ReserveRecords::create_new_record_in_tail_page(), foedus::storage::masstree::get_initial_xid(), foedus::xct::XctManagerPimpl::precommit_xct_readwrite(), foedus::storage::hash::HashDataPage::reserve_record(), and foedus::storage::sequential::SequentialStoragePimpl::truncate().

958  {
959  ASSERT_ND(epoch_int < Epoch::kEpochIntOverflow);
960  ASSERT_ND(ordinal <= kMaxXctOrdinal);
961  data_ = static_cast<uint64_t>(epoch_int) << 32 | ordinal;
962  }
Epoch values wrap around at this value.
Definition: epoch.hpp:81
const uint64_t kMaxXctOrdinal
Maximum value of in-epoch ordinal.
Definition: xct_id.hpp:898
#define ASSERT_ND(x)
A warning-free wrapper macro of assert() that has no performance effect in release mode even when 'x'...
Definition: assert_nd.hpp:72

Here is the caller graph for this function:

void foedus::xct::XctId::set_being_written ( )
inline

Definition at line 1019 of file xct_id.hpp.

References data_, and foedus::xct::kXctIdBeingWrittenBit.

Referenced by foedus::xct::XctManagerPimpl::precommit_xct_apply().

const uint64_t kXctIdBeingWrittenBit
Definition: xct_id.hpp:885

Here is the caller graph for this function:

void foedus::xct::XctId::set_deleted ( )
inline
void foedus::xct::XctId::set_epoch ( Epoch  epoch)
inline

Definition at line 965 of file xct_id.hpp.

References set_epoch_int().

Referenced by foedus::log::MetaLogBuffer::commit(), foedus::xct::Xct::initialize(), and foedus::xct::Xct::issue_next_id().

965 { set_epoch_int(epoch.value()); }
void set_epoch_int(Epoch::EpochInteger epoch_int) __attribute__((always_inline))
Definition: xct_id.hpp:969

Here is the call graph for this function:

Here is the caller graph for this function:

void foedus::xct::XctId::set_epoch_int ( Epoch::EpochInteger  epoch_int)
inline

Definition at line 969 of file xct_id.hpp.

References ASSERT_ND, data_, and foedus::Epoch::kEpochIntOverflow.

Referenced by set_epoch().

969  {
970  ASSERT_ND(epoch_int < Epoch::kEpochIntOverflow);
971  data_ = (data_ & ~kXctIdMaskEpoch) | (static_cast<uint64_t>(epoch_int) << 32);
972  }
Epoch values wrap around at this value.
Definition: epoch.hpp:81
const uint64_t kXctIdMaskEpoch
Definition: xct_id.hpp:888
#define ASSERT_ND(x)
A warning-free wrapper macro of assert() that has no performance effect in release mode even when 'x'...
Definition: assert_nd.hpp:72

Here is the caller graph for this function:

void foedus::xct::XctId::set_moved ( )
inline

Definition at line 1029 of file xct_id.hpp.

References data_, and foedus::xct::kXctIdMovedBit.

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

1029 { data_ |= kXctIdMovedBit; }
const uint64_t kXctIdMovedBit
Definition: xct_id.hpp:884

Here is the caller graph for this function:

void foedus::xct::XctId::set_next_layer ( )
inline

Definition at line 1030 of file xct_id.hpp.

References data_, and foedus::xct::kXctIdNextLayerBit.

Referenced by foedus::storage::masstree::MasstreeBorderPage::append_next_layer_snapshot(), and foedus::storage::masstree::MasstreeBorderPage::replace_next_layer_snapshot().

1030  {
1031  // Delete-bit has no meaning for a next-layer record. To avoid confusion, turn it off.
1033  }
const uint64_t kXctIdDeletedBit
Definition: xct_id.hpp:883
const uint64_t kXctIdNextLayerBit
Definition: xct_id.hpp:886

Here is the caller graph for this function:

void foedus::xct::XctId::set_notdeleted ( )
inline

Definition at line 1028 of file xct_id.hpp.

References data_.

1028 { data_ &= (~kXctIdDeletedBit); }
const uint64_t kXctIdDeletedBit
Definition: xct_id.hpp:883
void foedus::xct::XctId::set_ordinal ( uint32_t  ordinal)
inline

Definition at line 980 of file xct_id.hpp.

References ASSERT_ND, and data_.

Referenced by increment_ordinal(), foedus::xct::Xct::initialize(), and foedus::xct::Xct::issue_next_id().

980  {
981  ASSERT_ND(ordinal <= kMaxXctOrdinal);
982  data_ = (data_ & (~kXctIdMaskOrdinal)) | ordinal;
983  }
const uint64_t kMaxXctOrdinal
Maximum value of in-epoch ordinal.
Definition: xct_id.hpp:898
const uint64_t kXctIdMaskOrdinal
Definition: xct_id.hpp:889
#define ASSERT_ND(x)
A warning-free wrapper macro of assert() that has no performance effect in release mode even when 'x'...
Definition: assert_nd.hpp:72

Here is the caller graph for this function:

void foedus::xct::XctId::set_write_complete ( )
inline

Definition at line 1020 of file xct_id.hpp.

References data_.

1020 { data_ &= (~kXctIdBeingWrittenBit); }
const uint64_t kXctIdBeingWrittenBit
Definition: xct_id.hpp:885
XctId foedus::xct::XctId::spin_while_being_written ( ) const
inline

Returns a version of this Xid whose being_written flag is off.

This internally spins until the bit becomes false, so use it only where deadlock is not possible.

Definition at line 1190 of file xct_id.hpp.

References data_, and UNLIKELY.

Referenced by foedus::xct::Xct::on_record_read(), and foedus::storage::hash::RecordLocation::populate_physical().

1190  {
1191  uint64_t copied_data = assorted::atomic_load_acquire<uint64_t>(&data_);
1192  if (UNLIKELY(copied_data & kXctIdBeingWrittenBit)) {
1193  while (copied_data & kXctIdBeingWrittenBit) {
1194  copied_data = assorted::atomic_load_acquire<uint64_t>(&data_);
1195  }
1196  }
1197  XctId ret;
1198  ret.data_ = copied_data;
1199  return ret;
1200 }
const uint64_t kXctIdBeingWrittenBit
Definition: xct_id.hpp:885
#define UNLIKELY(x)
Hints that x is highly likely false.
Definition: compiler.hpp:104

Here is the caller graph for this function:

void foedus::xct::XctId::store_max ( const XctId other)
inline

Kind of std::max(this, other).

This relies on the semantics of before(). Thus, this can't differentiate two XctId that differ only in status bits. This method is only used for XctId generation at commit time, so that's fine.

Definition at line 1059 of file xct_id.hpp.

References before().

Referenced by foedus::xct::Xct::issue_next_id(), foedus::xct::XctManagerPimpl::precommit_xct_lock(), and foedus::xct::XctManagerPimpl::precommit_xct_verify_readwrite().

1059  {
1060  if (!other.is_valid()) {
1061  return;
1062  }
1063 
1064  if (before(other)) {
1065  operator=(other);
1066  }
1067  }
bool before(const XctId &other) const __attribute__((always_inline))
Returns if this XctId is before other in serialization order, meaning this is either an invalid (unus...
Definition: xct_id.hpp:1074

Here is the call graph for this function:

Here is the caller graph for this function:

Friends And Related Function Documentation

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

Definition at line 178 of file xct_id.cpp.

178  {
179  o << "<XctId epoch=\"" << v.get_epoch()
180  << "\" ordinal=\"" << v.get_ordinal()
181  << "\" status=\""
182  << (v.is_deleted() ? "D" : " ")
183  << (v.is_moved() ? "M" : " ")
184  << (v.is_being_written() ? "W" : " ")
185  << (v.is_next_layer() ? "N" : " ")
186  << "\" />";
187  return o;
188 }

Member Data Documentation


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