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; 35 LinkOp(UNUSED T *BaseT, UNUSED uptr BaseSize) {} 36 void init(UNUSED T *LinkBase, UNUSED uptr Size) {} 37 T *getBase() const { return nullptr; } 38 uptr getSize() const { return 0; } 39 40 T *getNext(T *X) const { return X->Next; } 41 void setNext(T *X, T *Next) const { X->Next = Next; } 42 43 T *getPrev(T *X) const { return X->Prev; } 44 void setPrev(T *X, T *Prev) const { X->Prev = Prev; } 45 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; 56 LinkOp(T *BaseT, uptr BaseSize) 57 : Base(BaseT), Size(static_cast<LinkTy>(BaseSize)) {} 58 void init(T *LinkBase, uptr BaseSize) { 59 Base = LinkBase; 60 Size = static_cast<LinkTy>(BaseSize); 61 } 62 T *getBase() const { return Base; } 63 LinkTy getSize() const { return Size; } 64 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`. 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 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`. 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 99 LinkTy getEndOfListVal() const { return T::EndOfListVal; } 100 101 private: 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: 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; 130 void init(T *Base, uptr BaseSize) { LinkOp<T>::init(Base, BaseSize); } 131 132 bool empty() const { return Size == 0; } 133 uptr size() const { return Size; } 134 135 T *front() { return First; } 136 const T *front() const { return First; } 137 T *back() { return Last; } 138 const T *back() const { return Last; } 139 140 void clear() { 141 First = Last = nullptr; 142 Size = 0; 143 } 144 145 typedef IteratorBase<T> Iterator; 146 typedef IteratorBase<const T> ConstIterator; 147 148 Iterator begin() { 149 return Iterator(LinkOp<T>(this->getBase(), this->getSize()), First); 150 } 151 Iterator end() { 152 return Iterator(LinkOp<T>(this->getBase(), this->getSize()), nullptr); 153 } 154 155 ConstIterator begin() const { 156 return ConstIterator(LinkOp<const T>(this->getBase(), this->getSize()), 157 First); 158 } 159 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 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 197 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 207 void push_front(T *X) { 208 if (empty()) 209 Last = X; 210 setNext(X, First); 211 First = X; 212 Size++; 213 } 214 215 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 224 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 235 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 246 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 272 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. 286 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 300 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 313 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. 326 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