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