hyrise · nikriek · Nov 2, 2023 · Oct 12, 2023 · Oct 12, 2023 · Oct 12, 2023
diff --git a/README.md b/README.md
@@ -207,6 +207,7 @@ Contact: firstname.lastname@hpi.de
 -   Leander   Neiß
 -   Vincent   Rahn
 -   Hendrik   Rätz
+-   Niklas    Riekenbrauck
 -   Alexander Riese
 -   Marc      Rosenau
 -   Johannes  Schneider

diff --git a/src/lib/CMakeLists.txt b/src/lib/CMakeLists.txt
@@ -439,6 +439,9 @@ set(
     storage/base_segment_accessor.hpp
     storage/base_segment_encoder.hpp
     storage/base_value_segment.hpp
+    storage/buffer/frame.cpp
+    storage/buffer/frame.hpp
+    storage/buffer/page_id.hpp
     storage/chunk.cpp
     storage/chunk.hpp
     storage/chunk_encoder.cpp

diff --git a/src/lib/storage/buffer/frame.cpp b/src/lib/storage/buffer/frame.cpp
@@ -0,0 +1,180 @@
+#include "frame.hpp"
+
+#include <bitset>
+
+namespace hyrise {
+
+Frame::Frame() {
+  // The frame should have an initial state of EVICTED and version 0.
+  _state_and_version.store(_update_state_with_same_version(0, EVICTED), std::memory_order_release);
+}
+
+void Frame::set_node_id(const NodeID node_id) {
+  DebugAssert(node_id <= (_node_id_mask >> _node_id_shift), "NUMA node must be smaller than 128.");
+  DebugAssert(node_id != INVALID_NODE_ID, "Cannot set empty NUMA node");
+  DebugAssert(state(_state_and_version.load()) == LOCKED, "Frame must be locked to set NUMA node.");
+  auto old_state_and_version = _state_and_version.load();
+
+  // Execute a compare-and-swap loop to set the NUMA node.
+  while (true) {
+    auto new_state_and_version =
+        old_state_and_version ^
+        ((old_state_and_version ^ static_cast<Frame::StateVersionType>(node_id) << _node_id_shift) & _node_id_mask);
+    if (_state_and_version.compare_exchange_strong(old_state_and_version, new_state_and_version)) {
+      DebugAssert((old_state_and_version & ~_node_id_mask) == (new_state_and_version & ~_node_id_mask),
+                  "Settings the NUMA node failed.");
+      break;
+    }
+  }
+
+  DebugAssert(Frame::node_id(_state_and_version.load()) == node_id,
+              "Setting NUMA node didnt work: " + std::to_string(Frame::node_id(_state_and_version.load())));
+}
+
+void Frame::mark_dirty() {
+  DebugAssert(state(_state_and_version.load()) == LOCKED, "Frame must be locked to set dirty flag.");
+  _state_and_version |= _dirty_mask;
+}
+
+void Frame::reset_dirty() {
+  _state_and_version &= ~_dirty_mask;
+}
+
+void Frame::unlock_exclusive_and_set_evicted() {
+  DebugAssert(state(_state_and_version.load()) == LOCKED, "Frame must be marked to set evicted flag.");
+  _state_and_version.store(_update_state_with_incremented_version(_state_and_version.load(), EVICTED),
+                           std::memory_order_release);
+}
+
+bool Frame::try_mark(const Frame::StateVersionType old_state_and_version) {
+  DebugAssert(
+      state(_state_and_version.load()) == UNLOCKED,
+      "Frame must be UNLOCKED to transition to MARKED, instead: " + std::to_string(state(_state_and_version.load())));
+  auto state_and_version = old_state_and_version;
+  return _state_and_version.compare_exchange_strong(state_and_version,
+                                                    _update_state_with_same_version(old_state_and_version, MARKED));
+}
+
+bool Frame::is_dirty() const {
+  return (_state_and_version.load() & _dirty_mask) >> _dirty_shift;
+}
+
+Frame::StateVersionType Frame::state(const Frame::StateVersionType state_and_version) {
+  return (state_and_version & _state_mask) >> _state_shift;
+}
+
+Frame::StateVersionType Frame::version(const Frame::StateVersionType state_and_version) {
+  return state_and_version & _version_mask;
+}
+
+Frame::StateVersionType Frame::state_and_version() const {
+  return _state_and_version.load();
+}
+
+NodeID Frame::node_id() const {
+  return node_id(_state_and_version.load());
+}
+
+NodeID Frame::node_id(const Frame::StateVersionType state_and_version) {
+  return static_cast<NodeID>((state_and_version & _node_id_mask) >> _node_id_shift);
+}
+
+bool Frame::try_lock_shared(const Frame::StateVersionType old_state_and_version) {
+  auto old_state = state(old_state_and_version);
+  auto state_and_version = old_state_and_version;
+
+  // Multiple threads can try to lock shared concurrently until the state reaches MAX_LOCKED_SHARED.
+  if (old_state < MAX_LOCKED_SHARED) {
+    // Increment the state by 1 to add a new concurrent reader
+    return _state_and_version.compare_exchange_strong(
+        state_and_version, _update_state_with_same_version(old_state_and_version, old_state + 1));
+  }
+
+  // If the state is MARKED, we just set the frame to 1 reader.
+  if (old_state == MARKED) {
+    return _state_and_version.compare_exchange_strong(
+        state_and_version, _update_state_with_same_version(old_state_and_version, SINGLE_LOCKED_SHARED));
+  }
+  return false;
+}
+
+bool Frame::try_lock_exclusive(const Frame::StateVersionType old_state_and_version) {
+  DebugAssert(state(old_state_and_version) == UNLOCKED || state(old_state_and_version) == MARKED ||
+                  state(old_state_and_version) == EVICTED,
+              "Frame must be unlocked, marked or evicted to lock exclusive, instead: " +
+                  std::to_string(state(old_state_and_version)));
+  auto state_and_version = old_state_and_version;
+  return _state_and_version.compare_exchange_strong(state_and_version,
+                                                    _update_state_with_same_version(old_state_and_version, LOCKED));
+}
+
+bool Frame::unlock_shared() {
+  while (true) {
+    auto old_state_and_version = _state_and_version.load();
+    const auto old_state = state(old_state_and_version);
+    DebugAssert(old_state > 0 && old_state <= MAX_LOCKED_SHARED, "Frame must be locked shared to unlock shared.");
+    // Decrement the state by 1 to remove a concurrent reader, the version stays the same for shared unlocks.
+    const auto new_state = old_state - 1;
+    if (_state_and_version.compare_exchange_strong(old_state_and_version,
+                                                   _update_state_with_same_version(old_state_and_version, new_state))) {
+      // Return true if last shared latch has been released.
+      return new_state == Frame::UNLOCKED;
+    }
+  }
+}
+
+void Frame::unlock_exclusive() {
+  DebugAssert(state(_state_and_version.load()) == LOCKED,
+              "Frame must be locked to unlock exclusive. " + std::to_string(state(_state_and_version.load())));
+  _state_and_version.store(_update_state_with_incremented_version(_state_and_version.load(), UNLOCKED),
+                           std::memory_order_release);
+}
+
+Frame::StateVersionType Frame::_update_state_with_same_version(const Frame::StateVersionType old_version_and_state,
+                                                               const Frame::StateVersionType new_state) {
+  constexpr auto SHIFT = _bit_width - _state_shift;
+  return ((old_version_and_state << SHIFT) >> SHIFT) | (new_state << _state_shift);
+}
+
+Frame::StateVersionType Frame::_update_state_with_incremented_version(
+    const Frame::StateVersionType old_version_and_state, const Frame::StateVersionType new_state) {
+  constexpr auto SHIFT = _bit_width - _state_shift;
+  return (((old_version_and_state << SHIFT) >> SHIFT) + 1) | (new_state << _state_shift);
+}
+
+bool Frame::is_unlocked() const {
+  return state(_state_and_version.load()) == UNLOCKED;
+}
+
+std::ostream& operator<<(std::ostream& os, const Frame& frame) {
+  const auto state_and_version = frame.state_and_version();
+  const auto state = Frame::state(state_and_version);
+  const auto version = Frame::version(state_and_version);
+  const auto node_id = frame.node_id();
+  const auto dirty = frame.is_dirty();
+
+  os << "Frame(state = ";
+
+  switch (state) {
+    case Frame::UNLOCKED:
+      os << "UNLOCKED";
+      break;
+    case Frame::LOCKED:
+      os << "LOCKED";
+      break;
+    case Frame::MARKED:
+      os << "MARKED";
+      break;
+    case Frame::EVICTED:
+      os << "EVICTED";
+      break;
+    default:
+      os << "LOCKED_SHARED (" << state << ")";
+      break;
+  }
+
+  os << ", node_id = " << node_id << ", dirty = " << dirty << ", version = " << version << ")";
+
+  return os;
+}
+}  // namespace hyrise
diff --git a/src/lib/storage/buffer/frame.hpp b/src/lib/storage/buffer/frame.hpp
@@ -0,0 +1,177 @@
+#pragma once
+
+#include <atomic>
+
+#include <bit>
+
+#include "types.hpp"
+
+namespace hyrise {
+
+/**
+ * Frames are the metadata objects for each page. We use a 64-bit atomic integer to store the (latching) state, NUMA node, dirty flag, and the frame version.
+ * All operations are atomic. The basic idea and most of the code is based on the SIGMOD'23 paper "Virtual-Memory Assisted Buffer Management" by Leis et al.
+ * 
+ * The frame's upper 16 bits encode the (latching) state (see below). 1 bit is used for the dirty flag. 7 bits are used for the NUMA node. The lower 40 bits are used for the version. 
+ * The version is used to tract concurrent changes to the state of the frame. The version is incremented after exclusively unlocking the frame. It is not incremented when unlocking in shared mode.
+ * 
+ *  +-----------+-------+-----------+----------------+
+ *  | State     | Dirty | NUMA node | Version        |
+ *  +-----------+-------+-----------+----------------+
+ * 64          48      47          40                0          
+ * 
+ * The (latching) state is encoded as EVICTED (65535), LOCKED (65533), UNLOCKED (0), MARKED (65534) and LOCK_SHARED (1-65532). Initially, the frame is in state EVICTED. 
+ * Then, the frame gets LOCKED for reading from disk. After that, the frame is UNLOCKED and can be used. It can be LOCKED again for write access. For multiple current readers,
+ * the state is incremented by 1 until MAX_LOCKED_SHARED is reached. When locking in shared mode, we also need to perform the same amount of unlocked to move the state to UNLOCKED again.  
+ * The state MARKED is used for Second-Chance marking a frame for eviction. Only frames that were previously MARKED after the UNLOCKED state are eligible for eviction. This approximates an LRU policy. 
+ * Later, the state is changed to EVICTED after the page has been written to disk. After unlocking a frame, the version counter is updated. The version is used to detect concurrent changes to the 
+ * state of the frame. The version is primarily used for the Second-Chance eviction mechanism. We use it to verify if an enqueued frame has been modified in the meantime and thereby is outdated. If so,
+ * we know that a newer version of the frame has been enqueued or that the frame is currently locked. Thus, we can skip the frame for now. The version can also be used to implementet an optimistic latching 
+ * mechanism.
+ * 
+ * The reference implementation can be found in https://github.com/viktorleis/vmcache/blob/master/vmcache.cpp.
+ * 
+ *                                                            try_lock_exclusive
+ *                                                   +----------------------------------------------------------------------+
+ *                                                   v                                                                      |
+ * +---------+  try_lock_exclusive                 +--------+  unlock_exclusive     +----------------+  try_mark          +---------------------+
+ * | EVICTED | ----------------------------------> |        | --------------------> |                | -----------------> |       MARKED        |
+ * +---------+                                     |        |                       |                |                    +---------------------+
+ *   ^         unlock_exclusive_and_set_evicted    |        |  try_lock_exclusive   |                |                        try_lock_shared
+ *   +-------------------------------------------- | LOCKED | <-------------------- |    UNLOCKED    |                      +-----------------+
+ *                                                 |        |                       |                |                      v                 |
+ *                                                 |        |                       |                |  try_lock_shared   +---------------------+
+ *                                                 |        |                       |                | -----------------> |    LOCKED_SHARED    | -+
+ *                                                 +--------+                       +----------------+                    +---------------------+  |
+ *                                                                                    ^                                     ^ unlock_shared   |    |
+ *                                                                                    | unlock_shared                       +-----------------+    |
+ *                                                                                    |                                                            |
+ *                                                                                    | (only if no other latches are present)                     |
+ *                                                                                    +------------------------------------------------------------+
+ */
+class Frame final : private Noncopyable {
+ public:
+  // Type of state and version
+  using StateVersionType = uint64_t;
+
+  // Signifes no reader or writer
+  static constexpr StateVersionType UNLOCKED = 0;
+
+  // Signifies that the frame has a single reader. It has a value of 1. Used for convenience.
+  static constexpr StateVersionType SINGLE_LOCKED_SHARED = 1;
+
+  // Maxium amount of shared readers. It has a value of 65532.
+  static constexpr StateVersionType MAX_LOCKED_SHARED = 0xFFFF - 3;
+
+  // Signifies that the frame is locked exclusively. It has a value of 65533.
+  static constexpr StateVersionType LOCKED = 0xFFFF - 2;
+
+  // Signifies that the frame is marked for eviction. It has a value of 65534.
+  static constexpr StateVersionType MARKED = 0xFFFF - 1;
+
+  // Signies and evicted page with a value of 65535 and is the initial state of the frame.
+  static constexpr StateVersionType EVICTED = 0xFFFF;
+
+  // Constructs the frame in state EVICTED and version 0.
+  Frame();
+
+  // Set the NUMA node of the frame.
+  void set_node_id(const NodeID node_id);
+
+  // Set the dirty flag of the frame. Fails if the frame is not locked exclusively.
+  void mark_dirty();
+
+  // Check if the frame is dirty.
+  bool is_dirty() const;
+
+  // Reset the dirty flag. Fails if the frame is not locked exclusively.
+  void reset_dirty();
+
+  // Get the NUMA node of the frame.
+  NodeID node_id() const;
+
+  /**
+   * Try to latch in frame in shared node by incrementing the state. Fails if the frame is 
+   * not in state UNLOCKED, MARKED or reaches MAX_LOCKED_SHARED.
+   */
+  bool try_lock_shared(const StateVersionType old_state_and_version);
+
+  /**
+   * Try to latch in frame in exclusive node. Fails if the frame is not in state UNLOCKED or MARKED. 
+   * Returns true on success.
+   */
+  bool try_lock_exclusive(const StateVersionType old_state_and_version);
+
+  // Try to mark the frame. Fails if the frame is not in state UNLOCKED. Returns true on success.
+  bool try_mark(const StateVersionType old_state_and_version);
+
+  // Decrement the shared latch. Returns true if the last shared latch has been released (state is UNLOCKED).
+  bool unlock_shared();
+
+  // Unlocks the frame after an exclusive lock and sets the state to EVICTED.
+  void unlock_exclusive_and_set_evicted();
+
+  // Unlocks the frame and increments the version.
+  void unlock_exclusive();
+
+  // Check if the frame is in state UNLOCKED.
+  bool is_unlocked() const;
+
+  // Load the complete state and version atomically.
+  StateVersionType state_and_version() const;
+
+  // Extract the state from the atomic integer. The state is encoded in 16 bits.
+  static StateVersionType state(const StateVersionType state_and_version);
+
+  // Extract the version from the atomic integer. The version is encoded in 40 bits.
+  static StateVersionType version(const StateVersionType state_and_version);
+
+  // Extract the node id from the atomic integer. The node id is encoded in 7 bits.
+  static NodeID node_id(const StateVersionType state_and_version);
+
+ private:
+  // clang-format off
+
+  // The dirty flag is encoded in at bit 41.
+  static constexpr uint64_t _dirty_mask       = 0x0000800000000000;
+
+  // The NUMA is encoded 7 bits between the state an the the dirty mask.
+  static constexpr uint64_t _node_id_mask     = 0x00007F0000000000;
+
+  // The state is encoded in the upper 16 bits.
+  static constexpr uint64_t _state_mask       = 0xFFFF000000000000;
+
+  // The version is encoded in the lower 40 bits.
+  static constexpr uint64_t _version_mask     = 0x000000FFFFFFFFFF;
+
+  // clang-format on
+
+  static_assert((_node_id_mask ^ _dirty_mask ^ _state_mask ^ _version_mask) ==
+                    std::numeric_limits<StateVersionType>::max(),
+                "The given masks either overlap or do not cover the whole StateVersionType.");
+
+  // The number of bits for the state and version. It should be 64.
+  static constexpr uint64_t _bit_width = std::numeric_limits<StateVersionType>::digits;
+
+  // The number of bits to shift to the right to get the node id.
+  static constexpr uint64_t _node_id_shift = std::countr_zero(_node_id_mask);
+
+  // The number of bits to shift to the right to get the dirty flag.
+  static constexpr uint64_t _dirty_shift = std::countr_zero(_dirty_mask);
+
+  // The number of bits to shift to the right to get the state.
+  static constexpr uint64_t _state_shift = std::countr_zero(_state_mask);
+
+  // Update the state and keep the same version. The new state is encoded in the lower 16 bits without the version.
+  static StateVersionType _update_state_with_same_version(const StateVersionType old_version_and_state,
+                                                          const StateVersionType new_state);
+
+  // Update the state and incremente the version. The new state is encoded in the lower 16 bits without the version.
+  static StateVersionType _update_state_with_incremented_version(const StateVersionType old_version_and_state,
+                                                                 const StateVersionType new_state);
+
+  std::atomic<StateVersionType> _state_and_version;
+};
+
+std::ostream& operator<<(std::ostream& os, const Frame& frame);
+}  // namespace hyrise