1/**************************************************************************/
2/* safe_list.h */
3/**************************************************************************/
4/* This file is part of: */
5/* GODOT ENGINE */
6/* https://godotengine.org */
7/**************************************************************************/
8/* Copyright (c) 2014-present Godot Engine contributors (see AUTHORS.md). */
9/* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur. */
10/* */
11/* Permission is hereby granted, free of charge, to any person obtaining */
12/* a copy of this software and associated documentation files (the */
13/* "Software"), to deal in the Software without restriction, including */
14/* without limitation the rights to use, copy, modify, merge, publish, */
15/* distribute, sublicense, and/or sell copies of the Software, and to */
16/* permit persons to whom the Software is furnished to do so, subject to */
17/* the following conditions: */
18/* */
19/* The above copyright notice and this permission notice shall be */
20/* included in all copies or substantial portions of the Software. */
21/* */
22/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */
23/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */
24/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. */
25/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */
26/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */
27/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */
28/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
29/**************************************************************************/
30
31#ifndef SAFE_LIST_H
32#define SAFE_LIST_H
33
34#include "core/os/memory.h"
35#include "core/typedefs.h"
36
37#include <atomic>
38#include <functional>
39#include <type_traits>
40
41// Design goals for these classes:
42// - Accessing this list with an iterator will never result in a use-after free,
43// even if the element being accessed has been logically removed from the list on
44// another thread.
45// - Logical deletion from the list will not result in deallocation at that time,
46// instead the node will be deallocated at a later time when it is safe to do so.
47// - No blocking synchronization primitives will be used.
48
49// This is used in very specific areas of the engine where it's critical that these guarantees are held.
50
51template <class T, class A = DefaultAllocator>
52class SafeList {
53 struct SafeListNode {
54 std::atomic<SafeListNode *> next = nullptr;
55
56 // If the node is logically deleted, this pointer will typically point
57 // to the previous list item in time that was also logically deleted.
58 std::atomic<SafeListNode *> graveyard_next = nullptr;
59
60 std::function<void(T)> deletion_fn = [](T t) { return; };
61
62 T val;
63 };
64
65 static_assert(std::atomic<T>::is_always_lock_free);
66
67 std::atomic<SafeListNode *> head = nullptr;
68 std::atomic<SafeListNode *> graveyard_head = nullptr;
69
70 std::atomic_uint active_iterator_count = 0;
71
72public:
73 class Iterator {
74 friend class SafeList;
75
76 SafeListNode *cursor = nullptr;
77 SafeList *list = nullptr;
78
79 Iterator(SafeListNode *p_cursor, SafeList *p_list) :
80 cursor(p_cursor), list(p_list) {
81 list->active_iterator_count++;
82 }
83
84 public:
85 Iterator(const Iterator &p_other) :
86 cursor(p_other.cursor), list(p_other.list) {
87 list->active_iterator_count++;
88 }
89
90 ~Iterator() {
91 list->active_iterator_count--;
92 }
93
94 public:
95 T &operator*() {
96 return cursor->val;
97 }
98
99 Iterator &operator++() {
100 cursor = cursor->next;
101 return *this;
102 }
103
104 // These two operators are mostly useful for comparisons to nullptr.
105 bool operator==(const void *p_other) const {
106 return cursor == p_other;
107 }
108
109 bool operator!=(const void *p_other) const {
110 return cursor != p_other;
111 }
112
113 // These two allow easy range-based for loops.
114 bool operator==(const Iterator &p_other) const {
115 return cursor == p_other.cursor;
116 }
117
118 bool operator!=(const Iterator &p_other) const {
119 return cursor != p_other.cursor;
120 }
121 };
122
123public:
124 // Calling this will cause an allocation.
125 void insert(T p_value) {
126 SafeListNode *new_node = memnew_allocator(SafeListNode, A);
127 new_node->val = p_value;
128 SafeListNode *expected_head = nullptr;
129 do {
130 expected_head = head.load();
131 new_node->next.store(expected_head);
132 } while (!head.compare_exchange_strong(/* expected= */ expected_head, /* new= */ new_node));
133 }
134
135 Iterator find(T p_value) {
136 for (Iterator it = begin(); it != end(); ++it) {
137 if (*it == p_value) {
138 return it;
139 }
140 }
141 return end();
142 }
143
144 void erase(T p_value, std::function<void(T)> p_deletion_fn) {
145 Iterator tmp = find(p_value);
146 erase(tmp, p_deletion_fn);
147 }
148
149 void erase(T p_value) {
150 Iterator tmp = find(p_value);
151 erase(tmp, [](T t) { return; });
152 }
153
154 void erase(Iterator &p_iterator, std::function<void(T)> p_deletion_fn) {
155 p_iterator.cursor->deletion_fn = p_deletion_fn;
156 erase(p_iterator);
157 }
158
159 void erase(Iterator &p_iterator) {
160 if (find(p_iterator.cursor->val) == nullptr) {
161 // Not in the list, nothing to do.
162 return;
163 }
164 // First, remove the node from the list.
165 while (true) {
166 Iterator prev = begin();
167 SafeListNode *expected_head = prev.cursor;
168 for (; prev != end(); ++prev) {
169 if (prev.cursor && prev.cursor->next == p_iterator.cursor) {
170 break;
171 }
172 }
173 if (prev != end()) {
174 // There exists a node before this.
175 prev.cursor->next.store(p_iterator.cursor->next.load());
176 // Done.
177 break;
178 } else {
179 if (head.compare_exchange_strong(/* expected= */ expected_head, /* new= */ p_iterator.cursor->next.load())) {
180 // Successfully reassigned the head pointer before another thread changed it to something else.
181 break;
182 }
183 // Fall through upon failure, try again.
184 }
185 }
186 // Then queue it for deletion by putting it in the node graveyard.
187 // Don't touch `next` because an iterator might still be pointing at this node.
188 SafeListNode *expected_head = nullptr;
189 do {
190 expected_head = graveyard_head.load();
191 p_iterator.cursor->graveyard_next.store(expected_head);
192 } while (!graveyard_head.compare_exchange_strong(/* expected= */ expected_head, /* new= */ p_iterator.cursor));
193 }
194
195 Iterator begin() {
196 return Iterator(head.load(), this);
197 }
198
199 Iterator end() {
200 return Iterator(nullptr, this);
201 }
202
203 // Calling this will cause zero to many deallocations.
204 bool maybe_cleanup() {
205 SafeListNode *cursor = nullptr;
206 SafeListNode *new_graveyard_head = nullptr;
207 do {
208 // The access order here is theoretically important.
209 cursor = graveyard_head.load();
210 if (active_iterator_count.load() != 0) {
211 // It's not safe to clean up with an active iterator, because that iterator
212 // could be pointing to an element that we want to delete.
213 return false;
214 }
215 // Any iterator created after this point will never point to a deleted node.
216 // Swap it out with the current graveyard head.
217 } while (!graveyard_head.compare_exchange_strong(/* expected= */ cursor, /* new= */ new_graveyard_head));
218 // Our graveyard list is now unreachable by any active iterators,
219 // detached from the main graveyard head and ready for deletion.
220 while (cursor) {
221 SafeListNode *tmp = cursor;
222 cursor = cursor->graveyard_next;
223 tmp->deletion_fn(tmp->val);
224 memdelete_allocator<SafeListNode, A>(tmp);
225 }
226 return true;
227 }
228
229 ~SafeList() {
230#ifdef DEBUG_ENABLED
231 if (!maybe_cleanup()) {
232 ERR_PRINT("There are still iterators around when destructing a SafeList. Memory will be leaked. This is a bug.");
233 }
234#else
235 maybe_cleanup();
236#endif
237 }
238};
239
240#endif // SAFE_LIST_H
241