in src/mwcas/mwcas.h [99:401]
class alignas(kCacheLineSize) Descriptor {
template<typename T> friend class MwcTargetField;
public:
/// Signifies a dirty word requiring cache line write back
static const uint64_t kDirtyFlag = (uint64_t)1 << 61;
/// Garbage list recycle policy: only free [new_value] upon restart
static const uint32_t kRecycleOnRecovery = 0x1;
/// Garbage list recycle policy: leave the memory alone
static const uint32_t kRecycleNever = 0x2;
/// Garbage list recycle policy: free [old/new_value] if succeeded/failed
static const uint32_t kRecycleAlways = 0x3;
/// Garbage list recycle policy: free only [old value] if succeeded
static const uint32_t kRecycleOldOnSuccess = 0x4;
/// Garbage list recycle policy: free only [new value] if succeeded
static const uint32_t kRecycleNewOnFailure = 0x5;
/// Recycle and installation policy: neither install nor recycle
/// only used for allocation purpose
static const uint32_t kAllocNullAddress = 0x0;
/// Signaure for garbage free callback (see free_callback_ below)
typedef void (*FreeCallback)(void* context, void* word);
/// Signature for NVM allocation callback (see allocate_callback_ below)
typedef void* (*AllocateCallback)(size_t size);
/// The default NVM allocate callback used if no callback is specified by the user
static void* DefaultAllocateCallback(size_t size);
/// The default free callback used if no callback is specified by the user
static void DefaultFreeCallback(void* context, void* p);
/// Specifies what word to update in the mwcas, storing before/after images so
/// others may help along. This also servers as the descriptor for conditional
/// CAS(RDCSS in the Harris paper). status_address_ points to the parent
/// Descriptor's status_ field which determines whether a CAS that wishes to
/// make address_ point to WordDescriptor can happen.
struct WordDescriptor {
/// The target address
uint64_t* address_;
/// The original old value stored at /a Address
uint64_t old_value_;
/// The new value to be stored at /a Address
uint64_t new_value_;
/// The parent Descriptor's status
uint32_t* status_address_;
/// Whether to invoke the user-provided memory free callback to free the
/// memory when recycling this descriptor. This must be per-word - the
/// application could mix pointer and non-pointer changes in a single mwcas,
/// e.g., in the bwtree we might use a single mwcas to change both the root
/// lpid and other memory page pointers along the way.
uint32_t recycle_policy_;
/// Returns the parent descriptor for this particular word
inline Descriptor* GetDescriptor() {
return (Descriptor*)((uint64_t)status_address_ -
offsetof(Descriptor, status_));
}
#ifdef PMEM
/// Persist the content of address_
inline void PersistAddress() {
NVRAM::Flush(sizeof(uint64_t*), (void*)&address_);
}
#endif
};
/// Default constructor
Descriptor() = delete;
Descriptor(DescriptorPartition* partition);
/// Function for initializing a newly allocated Descriptor.
void Initialize();
/// Executes the multi-word compare and swap operation.
bool MwCAS() {
RAW_CHECK(status_ == kStatusFinished,
"status of descriptor is not kStatusFinished");
status_ = kStatusUndecided;
#ifdef PMEM
return PersistentMwCAS(0);
#else
return VolatileMwCAS(0);
#endif
}
/// Retrieves the new value for the given word index in the PMwCAS
inline uint64_t GetNewValue(uint32_t index) {
return words_[index].new_value_;
}
/// Retrieves the pointer to the new value slot for a given word in the PMwCAS
inline uint64_t* GetNewValuePtr(uint32_t index) {
return &words_[index].new_value_;
}
/// Adds information about a new word to be modifiec by the MwCAS operator.
/// Word descriptors are stored sorted on the word address to prevent
/// livelocks. Return value is negative if the descriptor is full.
/// @free_on_recycle: use the user-provided callback to free the address
/// stored in [oldval] (if mwcas succeeded) or [newval] (if mwcas failed).
/// Pre-requisite: the application is using mwcas to change memory pointers,
/// although technically the application can abuse this mechanism to do
/// anything.
uint32_t AddEntry(uint64_t* addr, uint64_t oldval, uint64_t newval,
uint32_t recycle_policy = kRecycleNever);
/// Allocate [size] bytes of memory and store the address in [newval]. Assume
/// the allocator features an interface similar to posix_memalign's which
/// accepts a reference to the location that will store the address of
/// allocated memory. In our case it's [newval]. Note: applies only if the
/// MwCAS is intended to change pointer values.
uint32_t AllocateAndAddEntry(uint64_t* addr, uint64_t oldval, size_t size,
uint32_t recycle_policy = kRecycleNever);
/// Reserve a slot in the words array, but don't know what the new value is
/// yet. The application should use GetNewValue[Ptr] to fill in later.
inline uint32_t ReserveAndAddEntry(uint64_t* addr, uint64_t oldval,
uint32_t recycle_policy = kRecycleNever) {
return AddEntry(addr, oldval, kNewValueReserved, recycle_policy);
}
/// Abort the MwCAS operation, can be used only before the operation starts.
Status Abort();
private:
#if defined(GOOGLE_FRAMEWORK) && defined(APPS)
/// Allow tests to access privates for failure injection purposes.
FRIEND_TEST(PMwCASTest, SingleThreadedRecovery);
#endif
friend class DescriptorPool;
/// Value signifying an internal reserved value for a new entry
static const uint64_t kNewValueReserved = ~0ull;
/// Internal helper function to conduct a double-compare, single-swap
/// operation on an target field depending on the value of the status_ field
/// in Descriptor. The conditional CAS tries to install a pointer to the MwCAS
/// descriptor derived from one of words_, expecting the status_ field
/// indicates Undecided. [dirty_flag] will be applied on the MwCAS descriptor
/// address if specified.
uint64_t CondCAS(uint32_t word_index, uint64_t dirty_flag = 0);
/// A version of the MwCAS function that will fail/abort during execution.
/// This is a private function that should only be used for testing failure
/// modes and recovery.
bool MwCASWithFailure(uint32_t calldepth = 0,
bool complete_descriptor_install = false) {
RAW_CHECK(status_ == kStatusFinished,
"status of descriptor is not kStatusFinished");
status_ = kStatusUndecided;
#ifdef PMEM
return PersistentMwCASWithFailure(calldepth, complete_descriptor_install);
#else
return VolatileMwCASWithFailure(calldepth, complete_descriptor_install);
#endif
}
#ifdef RTM
bool RTMInstallDescriptors(uint64_t dirty_flag = 0);
#endif
/// Retrieve the index position in the descriptor of the given address.
int GetInsertPosition(uint64_t* addr);
#ifndef PMEM
/// Execute the multi-word compare and swap operation.
bool VolatileMwCAS(uint32_t calldepth = 0);
/// Volatile version of the multi-word CAS with failure injection.
bool VolatileMwCASWithFailure(uint32_t calldepth = 0,
bool complete_descriptor_install = false);
#endif
#ifdef PMEM
/// Execute the multi-word compare and swap operation on persistent memory.
bool PersistentMwCAS(uint32_t calldepth = 0);
/// Persistent version of the multi-word CAS with failure injection.
bool PersistentMwCASWithFailure(uint32_t calldepth = 0,
bool complete_descriptor_install = false);
/// Flush only the Status field to persistent memory.
inline void PersistStatus() { NVRAM::Flush(sizeof(status_), &status_); }
// Read and persist the status field (if its dirty bit is set).
// The caller must ensure that the descriptor is already persistent.
// The returned value is guaranteed to be persistent in PM.
uint32_t ReadPersistStatus();
#endif
/// Flag signifying an multi-word CAS is underway for the target word.
static const uint64_t kMwCASFlag = (uint64_t)1 << 63;
/// Flag signifying a conditional CAS is underway for the target word.
static const uint64_t kCondCASFlag = (uint64_t)1 << 62;
/// Returns whether the value given is an MwCAS descriptor or not.
inline static bool IsMwCASDescriptorPtr(uint64_t value) {
return value & kMwCASFlag;
}
/// Returns whether the value given is a CondCAS descriptor or not.
inline static bool IsCondCASDescriptorPtr(uint64_t value) {
return value & kCondCASFlag;
}
/// Returns whether the underlying word is dirty (not surely persisted).
inline static bool IsDirtyPtr(uint64_t value) {
return value & kDirtyFlag;
}
/// Returns true if the target word has no pmwcas management flags set.
inline static bool IsCleanPtr(uint64_t value) {
return (value & (kCondCASFlag | kMwCASFlag | kDirtyFlag)) == 0;
}
/// Clear the descriptor flag for the provided /a ptr
static inline uint64_t CleanPtr(uint64_t ptr) {
return ptr & ~(kMwCASFlag | kCondCASFlag | kDirtyFlag);
}
/// Bitwise-or the given flags to the given value
inline static uint64_t SetFlags(uint64_t value, uint64_t flags) {
RAW_CHECK((flags & ~(kMwCASFlag | kCondCASFlag | kDirtyFlag)) == 0,
"invalid flags");
return value | flags;
}
/// Set the given flags for a target descriptor word.
inline static uint64_t SetFlags(Descriptor* desc, uint64_t flags) {
return SetFlags((uint64_t)desc, flags);
}
/// Mask to indicate the status field is dirty, any reader should first flush
/// it before use.
static const uint32_t kStatusDirtyFlag = 1ULL << 31;
/// Cleanup steps of MWCAS common to both persistent and volatile versions.
bool Cleanup();
/// Deallocate the memory associated with the MwCAS if needed.
void DeallocateMemory();
/// Places a descriptor back on the descriptor free pool (partitioned). This
/// can be used as the callback function for the epoch manager/garbage list to
/// reclaim this descriptor for reuse after we are sure no one is using or
/// could possibly access this descriptor.
static void FreeDescriptor(void* context, void* desc);
/// Descriptor states. Valid transitions are as follows:
/// kStatusUndecided->kStatusSucceeded->kStatusFinished->kStatusUndecided
/// \-->kStatusFailed-->kStatusFinished->kStatusUndecided
static const uint32_t kStatusInvalid = 0U;
static const uint32_t kStatusFinished = 1U;
static const uint32_t kStatusSucceeded = 2U;
static const uint32_t kStatusFailed = 3U;
static const uint32_t kStatusUndecided = 4U;
inline void assert_valid_status() {
auto s = status_ & ~kStatusDirtyFlag;
RAW_CHECK(s == kStatusFinished || s == kStatusFailed ||
s == kStatusSucceeded || s == kStatusUndecided, "invalid status");
}
/// Free list pointer for managing free pre-allocated descriptor pools
Descriptor* next_ptr_;
/// Back pointer to owning partition so the descriptor can be returned to its
/// howm partition when it is freed.
DescriptorPartition* owner_partition_;
/// Tracks the current status of the descriptor.
uint32_t status_;
/// Count of actual descriptors held in #WordDesc
uint32_t count_;
/// A callback for freeing the words listed in [words_] when recycling the
/// descriptor. Optional: only for applications that use it.
FreeCallback free_callback_;
/// A callback for allocating memory in AllocateAndAddEntry; the address of
/// the allocated memory will be store in [new_value].
AllocateCallback allocate_callback_;
/// Array of word descriptors bounded DESC_CAP
WordDescriptor words_[DESC_CAP];
};