Make thread list able to set node to 'delete'

arangodb · goedderz · Apr 28, 2025 · Mar 21, 2025 · Mar 24, 2025 · Mar 24, 2025
commit eca1c885ffc1706e1c50baf96aa24d93b1a0c9ce
diff --git a/lib/Containers/Concurrent/ThreadOwnedList.h b/lib/Containers/Concurrent/ThreadOwnedList.h
@@ -33,6 +33,10 @@
 
 namespace arangodb::containers {
 
+template<typename T>
+concept CanBeSetToDeleted = requires(T t) {
+  t.set_to_deleted();
+};
 /**
    This list is owned by one thread: nodes can only be added on this thread but
    other threads can read the list and mark nodes for deletion.
@@ -42,7 +46,8 @@ namespace arangodb::containers {
    shared_ptr to this list. Garbage collection can run either on the owning
    thread or on another thread (there are two distinct functions for gc).
  */
-template<HasSnapshot T>
+template<typename T>
+requires HasSnapshot<T> && CanBeSetToDeleted<T>
 struct ThreadOwnedList
     : public std::enable_shared_from_this<ThreadOwnedList<T>> {
   using Item = T;
@@ -51,11 +56,18 @@ struct ThreadOwnedList
   struct Node {
     T data;
     Node* next = nullptr;
-    std::atomic<Node*> previous =
-        nullptr;  // needs to be atomic for gc from different thread
+    // this needs to be an atomic because it is accessed during garbage
+    // collection which can happen in a different thread. This thread will
+    // load the value. Since there is only one transition, i.e. from nullptr
+    // to non-null ptr, any missed update will result in a pessimistic
+    // execution and not an error. More precise, the item might not be
+    // deleted, although it is not in head position and can be deleted. It
+    // will be deleted next round.
+    std::atomic<Node*> previous = nullptr;
     Node* next_to_free = nullptr;
-    std::shared_ptr<ThreadOwnedList<T>>
-        list;  // to be able to mark for deletion
+    // identifies the promise list it belongs to, to be able to mark for
+    // deletion
+    std::shared_ptr<ThreadOwnedList<T>> list;
   };
 
  private:
@@ -122,8 +134,7 @@ struct ThreadOwnedList
     // makes sure that promise is really in this list
     ADB_PROD_ASSERT(node->list.get() == this);
 
-    // TODO needs to be done in Promise::mark_for_deletion instead
-    // promise->state.store(State::Deleted);
+    node->data.set_to_deleted();
 
     // keep a local copy of the shared pointer. This promise might be the
     // last of the registry.

diff --git a/tests/Containers/Concurrent/ThreadOwnedListTest.cpp b/tests/Containers/Concurrent/ThreadOwnedListTest.cpp
@@ -50,6 +50,7 @@ std::size_t InstanceCounterValue::instanceCounter = 0;
 
 struct NodeData : InstanceCounterValue {
   int number;
+  bool isDeleted = false;
 
   NodeData(int number) : number{number} {}
 
@@ -58,6 +59,7 @@ struct NodeData : InstanceCounterValue {
     bool operator==(Snapshot const&) const = default;
   };
   auto snapshot() -> Snapshot { return Snapshot{.number = number}; }
+  auto set_to_deleted() -> void { isDeleted = true; };
 };
 
 using MyList = ThreadOwnedList<NodeData>;
@@ -145,6 +147,8 @@ TEST_F(ThreadOwnedListTest, marked_promises_are_deleted_in_garbage_collection) {
   EXPECT_EQ(nodes_in_registry(registry),
             (std::vector<NodeData::Snapshot>{another_node->data.snapshot(),
                                              node_to_delete->data.snapshot()}));
+  EXPECT_TRUE(node_to_delete->data.isDeleted);
+  EXPECT_FALSE(another_node->data.isDeleted);
 
   registry->garbage_collect();
   EXPECT_EQ(nodes_in_registry(registry),