1 //===-- list.h --------------------------------------------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 #ifndef SCUDO_LIST_H_
10 #define SCUDO_LIST_H_
11
12 #include "internal_defs.h"
13 #include "type_traits.h"
14
15 namespace scudo {
16
17 // Intrusive POD singly and doubly linked list.
18 // An object with all zero fields should represent a valid empty list. clear()
19 // should be called on all non-zero-initialized objects before using.
20 //
21 // The intrusive list requires the member `Next` (and `Prev` if doubly linked
22 // list)` defined in the node type. The type of `Next`/`Prev` can be a pointer
23 // or an index to an array. For example, if the storage of the nodes is an
24 // array, instead of using a pointer type, linking with an index type can save
25 // some space.
26 //
27 // There are two things to be noticed while using an index type,
28 // 1. Call init() to set up the base address of the array.
29 // 2. Define `EndOfListVal` as the nil of the list.
30
31 template <class T, bool LinkWithPtr = isPointer<decltype(T::Next)>::value>
32 class LinkOp {
33 public:
34 LinkOp() = default;
LinkOp(UNUSED T * BaseT,UNUSED uptr BaseSize)35 LinkOp(UNUSED T *BaseT, UNUSED uptr BaseSize) {}
init(UNUSED T * LinkBase,UNUSED uptr Size)36 void init(UNUSED T *LinkBase, UNUSED uptr Size) {}
getBase()37 T *getBase() const { return nullptr; }
getSize()38 uptr getSize() const { return 0; }
39
getNext(T * X)40 T *getNext(T *X) const { return X->Next; }
setNext(T * X,T * Next)41 void setNext(T *X, T *Next) const { X->Next = Next; }
42
getPrev(T * X)43 T *getPrev(T *X) const { return X->Prev; }
setPrev(T * X,T * Prev)44 void setPrev(T *X, T *Prev) const { X->Prev = Prev; }
45
getEndOfListVal()46 T *getEndOfListVal() const { return nullptr; }
47 };
48
49 template <class T> class LinkOp<T, /*LinkWithPtr=*/false> {
50 public:
51 using LinkTy = typename assertSameType<
52 typename removeConst<decltype(T::Next)>::type,
53 typename removeConst<decltype(T::EndOfListVal)>::type>::type;
54
55 LinkOp() = default;
LinkOp(T * BaseT,uptr BaseSize)56 LinkOp(T *BaseT, uptr BaseSize)
57 : Base(BaseT), Size(static_cast<LinkTy>(BaseSize)) {}
init(T * LinkBase,uptr BaseSize)58 void init(T *LinkBase, uptr BaseSize) {
59 Base = LinkBase;
60 Size = static_cast<LinkTy>(BaseSize);
61 }
getBase()62 T *getBase() const { return Base; }
getSize()63 LinkTy getSize() const { return Size; }
64
getNext(T * X)65 T *getNext(T *X) const {
66 DCHECK_NE(getBase(), nullptr);
67 if (X->Next == getEndOfListVal())
68 return nullptr;
69 DCHECK_LT(X->Next, Size);
70 return &Base[X->Next];
71 }
72 // Set `X->Next` to `Next`.
setNext(T * X,T * Next)73 void setNext(T *X, T *Next) const {
74 if (Next == nullptr) {
75 X->Next = getEndOfListVal();
76 } else {
77 assertElementInRange(Next);
78 X->Next = static_cast<LinkTy>(Next - Base);
79 }
80 }
81
getPrev(T * X)82 T *getPrev(T *X) const {
83 DCHECK_NE(getBase(), nullptr);
84 if (X->Prev == getEndOfListVal())
85 return nullptr;
86 DCHECK_LT(X->Prev, Size);
87 return &Base[X->Prev];
88 }
89 // Set `X->Prev` to `Prev`.
setPrev(T * X,T * Prev)90 void setPrev(T *X, T *Prev) const {
91 if (Prev == nullptr) {
92 X->Prev = getEndOfListVal();
93 } else {
94 assertElementInRange(Prev);
95 X->Prev = static_cast<LinkTy>(Prev - Base);
96 }
97 }
98
getEndOfListVal()99 LinkTy getEndOfListVal() const { return T::EndOfListVal; }
100
101 private:
assertElementInRange(T * X)102 void assertElementInRange(T *X) const {
103 DCHECK_GE(reinterpret_cast<uptr>(X), reinterpret_cast<uptr>(Base));
104 DCHECK_LE(static_cast<LinkTy>(X - Base), Size);
105 }
106
107 protected:
108 T *Base = nullptr;
109 LinkTy Size = 0;
110 };
111
112 template <class T> class IteratorBase : public LinkOp<T> {
113 public:
IteratorBase(const LinkOp<T> & Link,T * CurrentT)114 IteratorBase(const LinkOp<T> &Link, T *CurrentT)
115 : LinkOp<T>(Link), Current(CurrentT) {}
116
117 IteratorBase &operator++() {
118 Current = this->getNext(Current);
119 return *this;
120 }
121 bool operator!=(IteratorBase Other) const { return Current != Other.Current; }
122 T &operator*() { return *Current; }
123
124 private:
125 T *Current;
126 };
127
128 template <class T> struct IntrusiveList : public LinkOp<T> {
129 IntrusiveList() = default;
initIntrusiveList130 void init(T *Base, uptr BaseSize) { LinkOp<T>::init(Base, BaseSize); }
131
emptyIntrusiveList132 bool empty() const { return Size == 0; }
sizeIntrusiveList133 uptr size() const { return Size; }
134
frontIntrusiveList135 T *front() { return First; }
frontIntrusiveList136 const T *front() const { return First; }
backIntrusiveList137 T *back() { return Last; }
backIntrusiveList138 const T *back() const { return Last; }
139
clearIntrusiveList140 void clear() {
141 First = Last = nullptr;
142 Size = 0;
143 }
144
145 typedef IteratorBase<T> Iterator;
146 typedef IteratorBase<const T> ConstIterator;
147
beginIntrusiveList148 Iterator begin() {
149 return Iterator(LinkOp<T>(this->getBase(), this->getSize()), First);
150 }
endIntrusiveList151 Iterator end() {
152 return Iterator(LinkOp<T>(this->getBase(), this->getSize()), nullptr);
153 }
154
beginIntrusiveList155 ConstIterator begin() const {
156 return ConstIterator(LinkOp<const T>(this->getBase(), this->getSize()),
157 First);
158 }
endIntrusiveList159 ConstIterator end() const {
160 return ConstIterator(LinkOp<const T>(this->getBase(), this->getSize()),
161 nullptr);
162 }
163
164 void checkConsistency() const;
165
166 protected:
167 uptr Size = 0;
168 T *First = nullptr;
169 T *Last = nullptr;
170 };
171
checkConsistency()172 template <class T> void IntrusiveList<T>::checkConsistency() const {
173 if (Size == 0) {
174 CHECK_EQ(First, nullptr);
175 CHECK_EQ(Last, nullptr);
176 } else {
177 uptr Count = 0;
178 for (T *I = First;; I = this->getNext(I)) {
179 Count++;
180 if (I == Last)
181 break;
182 }
183 CHECK_EQ(this->size(), Count);
184 CHECK_EQ(this->getNext(Last), nullptr);
185 }
186 }
187
188 template <class T> struct SinglyLinkedList : public IntrusiveList<T> {
189 using IntrusiveList<T>::First;
190 using IntrusiveList<T>::Last;
191 using IntrusiveList<T>::Size;
192 using IntrusiveList<T>::empty;
193 using IntrusiveList<T>::setNext;
194 using IntrusiveList<T>::getNext;
195 using IntrusiveList<T>::getEndOfListVal;
196
push_backSinglyLinkedList197 void push_back(T *X) {
198 setNext(X, nullptr);
199 if (empty())
200 First = X;
201 else
202 setNext(Last, X);
203 Last = X;
204 Size++;
205 }
206
push_frontSinglyLinkedList207 void push_front(T *X) {
208 if (empty())
209 Last = X;
210 setNext(X, First);
211 First = X;
212 Size++;
213 }
214
pop_frontSinglyLinkedList215 void pop_front() {
216 DCHECK(!empty());
217 First = getNext(First);
218 if (!First)
219 Last = nullptr;
220 Size--;
221 }
222
223 // Insert X next to Prev
insertSinglyLinkedList224 void insert(T *Prev, T *X) {
225 DCHECK(!empty());
226 DCHECK_NE(Prev, nullptr);
227 DCHECK_NE(X, nullptr);
228 setNext(X, getNext(Prev));
229 setNext(Prev, X);
230 if (Last == Prev)
231 Last = X;
232 ++Size;
233 }
234
extractSinglyLinkedList235 void extract(T *Prev, T *X) {
236 DCHECK(!empty());
237 DCHECK_NE(Prev, nullptr);
238 DCHECK_NE(X, nullptr);
239 DCHECK_EQ(getNext(Prev), X);
240 setNext(Prev, getNext(X));
241 if (Last == X)
242 Last = Prev;
243 Size--;
244 }
245
append_backSinglyLinkedList246 void append_back(SinglyLinkedList<T> *L) {
247 DCHECK_NE(this, L);
248 if (L->empty())
249 return;
250 if (empty()) {
251 *this = *L;
252 } else {
253 setNext(Last, L->First);
254 Last = L->Last;
255 Size += L->size();
256 }
257 L->clear();
258 }
259 };
260
261 template <class T> struct DoublyLinkedList : IntrusiveList<T> {
262 using IntrusiveList<T>::First;
263 using IntrusiveList<T>::Last;
264 using IntrusiveList<T>::Size;
265 using IntrusiveList<T>::empty;
266 using IntrusiveList<T>::setNext;
267 using IntrusiveList<T>::getNext;
268 using IntrusiveList<T>::setPrev;
269 using IntrusiveList<T>::getPrev;
270 using IntrusiveList<T>::getEndOfListVal;
271
push_frontDoublyLinkedList272 void push_front(T *X) {
273 setPrev(X, nullptr);
274 if (empty()) {
275 Last = X;
276 } else {
277 DCHECK_EQ(getPrev(First), nullptr);
278 setPrev(First, X);
279 }
280 setNext(X, First);
281 First = X;
282 Size++;
283 }
284
285 // Inserts X before Y.
insertDoublyLinkedList286 void insert(T *X, T *Y) {
287 if (Y == First)
288 return push_front(X);
289 T *Prev = getPrev(Y);
290 // This is a hard CHECK to ensure consistency in the event of an intentional
291 // corruption of Y->Prev, to prevent a potential write-{4,8}.
292 CHECK_EQ(getNext(Prev), Y);
293 setNext(Prev, X);
294 setPrev(X, Prev);
295 setNext(X, Y);
296 setPrev(Y, X);
297 Size++;
298 }
299
push_backDoublyLinkedList300 void push_back(T *X) {
301 setNext(X, nullptr);
302 if (empty()) {
303 First = X;
304 } else {
305 DCHECK_EQ(getNext(Last), nullptr);
306 setNext(Last, X);
307 }
308 setPrev(X, Last);
309 Last = X;
310 Size++;
311 }
312
pop_frontDoublyLinkedList313 void pop_front() {
314 DCHECK(!empty());
315 First = getNext(First);
316 if (!First)
317 Last = nullptr;
318 else
319 setPrev(First, nullptr);
320 Size--;
321 }
322
323 // The consistency of the adjacent links is aggressively checked in order to
324 // catch potential corruption attempts, that could yield a mirrored
325 // write-{4,8} primitive. nullptr checks are deemed less vital.
removeDoublyLinkedList326 void remove(T *X) {
327 T *Prev = getPrev(X);
328 T *Next = getNext(X);
329 if (Prev) {
330 CHECK_EQ(getNext(Prev), X);
331 setNext(Prev, Next);
332 }
333 if (Next) {
334 CHECK_EQ(getPrev(Next), X);
335 setPrev(Next, Prev);
336 }
337 if (First == X) {
338 DCHECK_EQ(Prev, nullptr);
339 First = Next;
340 } else {
341 DCHECK_NE(Prev, nullptr);
342 }
343 if (Last == X) {
344 DCHECK_EQ(Next, nullptr);
345 Last = Prev;
346 } else {
347 DCHECK_NE(Next, nullptr);
348 }
349 Size--;
350 }
351 };
352
353 } // namespace scudo
354
355 #endif // SCUDO_LIST_H_
356