[scudo][standalone] Consolidate lists

[cryptoad]

Summary

I was going to introduce a couple more lists and realized that our
lists are currently a bit all over the place. While we have a singly
linked list type relatively well defined, we are using doubly linked
lists defined on the fly for the stats and for the secondary blocks.

This CL adds a doubly linked list object, reorganizing the singly list
one to extract as much of the common code as possible. We use this
new type in the stats and the secondary. We also reorganize the list
tests to benefit from this consolidation.

There are a few side effect changes such as using for iterator loops
that are, in my opinion, cleaner in a couple of places.

[cryptoad]

Ping!

[hctim]

Can we consider adding a fuzz target for the linked lists? I recently did a similar thing in android for a ringbuffer, which you can see here. If you get it checked in, I can help with getting it running on OSS-Fuzz.

lib/scudo/standalone/list.h

17

Why does the requirements to call clear() exist for non-zero-inited objects? For globally zero-init'ed instances of this object, we don't encounter a perf overhead of having Size, First, and Last be initialised to zero. For non-global instances, we have to call clear(), which seems easy to forget, and moving this initialisation into the c'tor doesn't cause any additional overhead (and I'd assume the call is elided, making it faster).

It also feels easy to forget to call clear(), and if any global objects are moved into static scopage, it may be incredibly hard to patch any instances where clear() isn't called.

95

Looks like this is test-only, can we move it out of the core header?

123

Shouldn't need this-> if you add using IntrusiveList<T>::empty;

(and similar elsewhere)

123

Why /s/DCHECK/CHECK here? This shouldn't fail in normal program execution, right?

176–182

DCHECK?

183

Isn't there an invariant held that if empty() == true, then First == nullptr? In which case, can't we hoist the X->Next = First; out from this conditional?

190

Would the specialisation:

if (Y == First)
  return push_front(X);

be more performant?

You should then be able to remove the if (Prev) check below, as assumedly there's an invariant that if Y isn't the first element, it has a Prev.

190

DCHECK?

191

DCHECK?

191

Same as push_front, isn't there an invariant that if empty() == true, Last == nullptr, and the X->Prev = Last can be hoisted out?

194

DCHECK?

203

DCHECK? (and throughout this function)

[cryptoad]

Mitch, thanks for the review! You made excellent points.

lib/scudo/standalone/list.h

17

Part of the issue, even with constexpr explicit constructors is that __thread can't seem to deal with them (as opposed to thread_local) and complains about it needing "dynamic initialization". It circles back to the choices made with init & initLinkerInitialized.
While your point makes sense, I don't think I can do it, unless I am missing something which is also very possible.

123

You are right. I initially thought that it would be important to ensure consistency, but extract is only called with X being Prev->Next, and while someone could attempt to TOCTOU it, I don't see that happening with a meaningful success chance.

183

Good point thank you!

190

Good point again, thanks!

191

Removed as part of the previously suggested change.

203

On this one I don't want to change the CHECKs to DCHECKs because doubly-lists unlinking is often the source of a mirrored write-4 primitive for exploitation.
Some examples can be found in http://xcon.xfocus.org/XCon2004/archives/14_Reliable%20Windows%20Heap%20Exploits_BY_SHOK.pdf.
Since it's being used in a large block header, I can't rule out that this could be targeted.
I can probably relax the nullptr CHECKs as they are probably less relevant to prevent further exploitation.

[cryptoad]

Addressing Mitch's comments:

• changing some CHECK to DCHECK where I felt it could be done "safely";
• reorganizing some code to make a clever use of the invariants;
• moving checkConsistency out of the main definition;

[hctim]

lib/scudo/standalone/list.h

17

So I think I remember the same problem from gwp_asan, but it was solved for us by marking the c'tor as constexpr.

https://godbolt.org/z/j1q8uR
^ works with constexpr c'tor with __thread and thread_local, fails for __thread if not constexpr c'tor. Sounds like this might be the same problem?

203

Sounds good to me, and the rationale sounds very reasonable. Is it possible to add a comment here to clarify this deliberate intent to future readers?

[cryptoad]

Adding comment to remove justifying the CHECKs.

[cryptoad]

lib/scudo/standalone/list.h

17

I gave a shot earlier to constexpr as well without success.
Using a constexpr explicit constructor for the lists, it bubbles up to the TSD:

.../compiler-rt/lib/scudo/standalone/tsd_exclusive.h:93:28: error: non-local variable ‘scudo::TSDRegistryExT<scudo::Allocator<scudo::DefaultConfig> >::ThreadTSD’ declared ‘__thread’ needs dynamic initialization
 THREADLOCAL TSD<Allocator> TSDRegistryExT<Allocator>::ThreadTSD;
                            ^~~~~~~~~~~~~~~~~~~~~~~~~
.../compiler-rt/lib/scudo/standalone/tsd_exclusive.h:93:28: note: C++11 ‘thread_local’ allows dynamic initialization and destruction

Part of the issue is probably that all of the TSD sub components as well as the TSD itself should all have constexpr constructors, but that's a rabbit hole I am not keen to look into at this moment.

[hctim]

LGTM with final comments.

lib/scudo/standalone/list.h

17

I see. Might be worth adding a strong TODO to go and sprinkle constexpr around where necessary to make this more bullet proof, but I don't want to block you on this.

101

if empty(), then First == nullptr as invariant, can hoist X->Next = First and this line out as well, right?

168

DCHECK?

[cryptoad]

lib/scudo/standalone/list.h

101

You are right, I missed those, thank you.
I changed that and also extracted the Size increment since it will be 0 when empty.

168

On this one, same as with the doubly linked lists, since we are writing Prev->Next I want to make sure that the list is consistent in the event of an intentional corruption of Y->Prev.
I added a comment.

[cryptoad]

Addressed Mitch's last comments:

• make use of invariants in lists to reorganize some code blocks
• added a comment to justify a hard CHECK in place of a DCHECK

[cryptoad]

This has landed.

lib/scudo/standalone/list.h

 //===-- list.h --------------------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef SCUDO_LIST_H_
 #define SCUDO_LIST_H_
 
 #include "internal_defs.h"
 
 namespace scudo {
 
-// Intrusive POD singly-linked list.
+// Intrusive POD singly and doubly linked list.
 // An object with all zero fields should represent a valid empty list. clear()
 // should be called on all non-zero-initialized objects before using.
-template <class Item> struct IntrusiveList {
-  friend class Iterator;
+
+template <class T> class IteratorBase {
+public:
+  explicit IteratorBase(T *CurrentT) : Current(CurrentT) {}
+  IteratorBase &operator++() {
+    Current = Current->Next;
+    return *this;
+  }
+  bool operator!=(IteratorBase Other) const { return Current != Other.Current; }
+  T &operator*() { return *Current; }
+
+private:
+  T *Current;
+};
+
+template <class T> struct IntrusiveList {
+  bool empty() const { return Size == 0; }
+  uptr size() const { return Size; }
+
+  T *front() { return First; }
+  const T *front() const { return First; }
+  T *back() { return Last; }
+  const T *back() const { return Last; }
 
   void clear() {
     First = Last = nullptr;
     Size = 0;
   }
 
-  bool empty() const { return Size == 0; }
-  uptr size() const { return Size; }
+  typedef IteratorBase<T> Iterator;
+  typedef IteratorBase<const T> ConstIterator;
 
-  void push_back(Item *X) {
-    if (empty()) {
-      X->Next = nullptr;
-      First = Last = X;
+  Iterator begin() { return Iterator(First); }
+  Iterator end() { return Iterator(nullptr); }
+
+  ConstIterator begin() const { return ConstIterator(First); }
+  ConstIterator end() const { return ConstIterator(nullptr); }
+
+  void checkConsistency() const;
+
+protected:
+  uptr Size;
+  T *First;
+  T *Last;
+};
+
+template <class T> void IntrusiveList<T>::checkConsistency() const {
+  if (Size == 0) {
+    CHECK_EQ(First, nullptr);
+    CHECK_EQ(Last, nullptr);
+  } else {
+    uptr Count = 0;
+    for (T *I = First;; I = I->Next) {
+      Count++;
+      if (I == Last)
+        break;
+    }
+    CHECK_EQ(this->size(), Count);
+    CHECK_EQ(Last->Next, nullptr);
+  }
+}
+
+template <class T> struct SinglyLinkedList : public IntrusiveList<T> {
+  using IntrusiveList<T>::First;
+  using IntrusiveList<T>::Last;
+  using IntrusiveList<T>::Size;
+  using IntrusiveList<T>::empty;
+
+  void push_back(T *X) {
+    if (empty()) {
+      First = X;
       Size = 1;
     } else {
-      X->Next = nullptr;
       Last->Next = X;
-      Last = X;
       Size++;
     }
+    Last = X;
   }
 
-  void push_front(Item *X) {
+  void push_front(T *X) {
     if (empty()) {
       X->Next = nullptr;
-      First = Last = X;
+      Last = X;
       Size = 1;
     } else {
       X->Next = First;
-      First = X;
       Size++;
     }
+    First = X;
   }
 
   void pop_front() {
     DCHECK(!empty());
     First = First->Next;
     if (!First)
       Last = nullptr;
     Size--;
   }
 
-  void extract(Item *Prev, Item *X) {
+  void extract(T *Prev, T *X) {
     DCHECK(!empty());
     DCHECK_NE(Prev, nullptr);
     DCHECK_NE(X, nullptr);
     DCHECK_EQ(Prev->Next, X);
     Prev->Next = X->Next;
     if (Last == X)
       Last = Prev;
     Size--;
   }
 
-  Item *front() { return First; }
-  const Item *front() const { return First; }
-  Item *back() { return Last; }
-  const Item *back() const { return Last; }
-
-  void append_front(IntrusiveList<Item> *L) {
-    DCHECK_NE(this, L);
-    if (L->empty())
-      return;
-    if (empty()) {
-      *this = *L;
-    } else if (!L->empty()) {
-      L->Last->Next = First;
-      First = L->First;
-      Size += L->size();
-    }
-    L->clear();
-  }
-
-  void append_back(IntrusiveList<Item> *L) {
+  void append_back(SinglyLinkedList<T> *L) {
     DCHECK_NE(this, L);
     if (L->empty())
       return;
     if (empty()) {
       *this = *L;
     } else {
       Last->Next = L->First;
       Last = L->Last;
       Size += L->size();
     }
     L->clear();
   }
+};
 
-  void checkConsistency() {
-    if (Size == 0) {
-      CHECK_EQ(First, nullptr);
-      CHECK_EQ(Last, nullptr);
+template <class T> struct DoublyLinkedList : IntrusiveList<T> {
+  using IntrusiveList<T>::First;
+  using IntrusiveList<T>::Last;
+  using IntrusiveList<T>::Size;
+  using IntrusiveList<T>::empty;
+
+  void push_front(T *X) {
+    X->Prev = nullptr;
+    if (empty()) {
+      Last = X;
     } else {
-      uptr Count = 0;
-      for (Item *I = First;; I = I->Next) {
-        Count++;
-        if (I == Last)
-          break;
-      }
-      CHECK_EQ(size(), Count);
-      CHECK_EQ(Last->Next, nullptr);
-    }
+      DCHECK_EQ(First->Prev, nullptr);
+    X->Next = First;
+    First = X;
+    Size++;
+
+  // Inserts X before Y.
+  void insert(T *X, T *Y) {
+    if (Y == First)
+      return push_front(X);
+    T *Prev = Y->Prev;
+    CHECK_EQ(Prev->Next, Y);
+    Prev->Next = X;
+    X->Prev = Prev;
+    X->Next = Y;
+    Y->Prev = X;
+    Size++;
   }
 
-  template <class ItemT> class IteratorBase {
-  public:
-    explicit IteratorBase(ItemT *CurrentItem) : Current(CurrentItem) {}
-    IteratorBase &operator++() {
-      Current = Current->Next;
-      return *this;
+  void push_back(T *X) {
+    X->Next = nullptr;
+    if (empty()) {
+      First = X;
+    } else {
+      DCHECK_EQ(Last->Next, nullptr);
+      Last->Next = X;
     }
-    bool operator!=(IteratorBase Other) const {
-      return Current != Other.Current;
-    }
-    ItemT &operator*() { return *Current; }
-
-  private:
-    ItemT *Current;
-  };
-
-  typedef IteratorBase<Item> Iterator;
-  typedef IteratorBase<const Item> ConstIterator;
-
-  Iterator begin() { return Iterator(First); }
-  Iterator end() { return Iterator(nullptr); }
+    X->Prev = Last;
+    Last = X;
+    Size++;
 
-  ConstIterator begin() const { return ConstIterator(First); }
-  ConstIterator end() const { return ConstIterator(nullptr); }
+  void pop_front() {
+    DCHECK(!empty());
+    First = First->Next;
+    if (!First)
+      Last = nullptr;
+    else
+      First->Prev = nullptr;
+    Size--;
+  }
 
-private:
-  uptr Size;
-  Item *First;
-  Item *Last;
+  void remove(T *X) {
+    T *Prev = X->Prev;
+    T *Next = X->Next;
+    if (Prev) {
+      CHECK_EQ(Prev->Next, X);
+      Prev->Next = Next;
+    }
+    if (Next) {
+      CHECK_EQ(Next->Prev, X);
+      Next->Prev = Prev;
+    }
+    if (First == X) {
+      DCHECK_EQ(Prev, nullptr);
+      First = Next;
+    } else {
+      DCHECK_NE(Prev, nullptr);
+    }
+    if (Last == X) {
+      DCHECK_EQ(Next, nullptr);
+      Last = Prev;
+    } else {
+      DCHECK_NE(Next, nullptr);
+    }
+    Size--;
+  }
 };
 
 } // namespace scudo
 
 #endif // SCUDO_LIST_H_

lib/scudo/standalone/primary32.h

struct ReleaseToOsInfo {
     uptr PushedBlocksAtLastRelease;
     uptr RangesReleased;
     uptr LastReleasedBytes;
     u64 LastReleaseAtNs;
   };
 
   struct ALIGNED(SCUDO_CACHE_LINE_SIZE) SizeClassInfo {
     HybridMutex Mutex;
-    IntrusiveList<TransferBatch> FreeList;
+    SinglyLinkedList<TransferBatch> FreeList;
     SizeClassStats Stats;
     bool CanRelease;
     u32 RandState;
     uptr AllocatedUser;
     ReleaseToOsInfo ReleaseInfo;
   };
   COMPILER_CHECK(sizeof(SizeClassInfo) % SCUDO_CACHE_LINE_SIZE == 0);
 
NOINLINE uptr releaseToOSMaybe(SizeClassInfo *Sci, uptr ClassId,
 
     // TODO(kostyak): currently not ideal as we loop over all regions and
     // iterate multiple times over the same freelist if a ClassId spans multiple
     // regions. But it will have to do for now.
     uptr TotalReleasedBytes = 0;
     for (uptr I = MinRegionIndex; I <= MaxRegionIndex; I++) {
       if (PossibleRegions[I] == ClassId) {
         ReleaseRecorder Recorder(I * RegionSize);
-        releaseFreeMemoryToOS(&Sci->FreeList, I * RegionSize,
+        releaseFreeMemoryToOS(Sci->FreeList, I * RegionSize,
                               RegionSize / PageSize, BlockSize, &Recorder);
         if (Recorder.getReleasedRangesCount() > 0) {
           Sci->ReleaseInfo.PushedBlocksAtLastRelease = Sci->Stats.PushedBlocks;
           Sci->ReleaseInfo.RangesReleased += Recorder.getReleasedRangesCount();
           Sci->ReleaseInfo.LastReleasedBytes = Recorder.getReleasedBytes();
           TotalReleasedBytes += Sci->ReleaseInfo.LastReleasedBytes;
         }
       }

lib/scudo/standalone/primary64.h

struct ReleaseToOsInfo {
     uptr PushedBlocksAtLastRelease;
     uptr RangesReleased;
     uptr LastReleasedBytes;
     u64 LastReleaseAtNs;
   };
 
   struct ALIGNED(SCUDO_CACHE_LINE_SIZE) RegionInfo {
     HybridMutex Mutex;
-    IntrusiveList<TransferBatch> FreeList;
+    SinglyLinkedList<TransferBatch> FreeList;
     RegionStats Stats;
     bool CanRelease;
     bool Exhausted;
     u32 RandState;
     uptr RegionBeg;
     uptr MappedUser;    // Bytes mapped for user memory.
     uptr AllocatedUser; // Bytes allocated for user memory.
     MapPlatformData Data;
if (!Force) {
       if (Region->ReleaseInfo.LastReleaseAtNs +
               static_cast<uptr>(IntervalMs) * 1000000ULL >
           getMonotonicTime()) {
         return 0; // Memory was returned recently.
       }
     }
 
     ReleaseRecorder Recorder(Region->RegionBeg, &Region->Data);
-    releaseFreeMemoryToOS(&Region->FreeList, Region->RegionBeg,
+    releaseFreeMemoryToOS(Region->FreeList, Region->RegionBeg,
                           roundUpTo(Region->AllocatedUser, PageSize) / PageSize,
                           BlockSize, &Recorder);
 
     if (Recorder.getReleasedRangesCount() > 0) {
       Region->ReleaseInfo.PushedBlocksAtLastRelease =
           Region->Stats.PushedBlocks;
       Region->ReleaseInfo.RangesReleased += Recorder.getReleasedRangesCount();
       Region->ReleaseInfo.LastReleasedBytes = Recorder.getReleasedBytes();

lib/scudo/standalone/quarantine.h

void getStats(ScopedString *Str) const {
     Str->append(
         "Stats: Quarantine: batches: %zu; bytes: %zu (user: %zu); chunks: %zu "
         "(capacity: %zu); %zu%% chunks used; %zu%% memory overhead\n",
         BatchCount, TotalBytes, TotalQuarantinedBytes, TotalQuarantineChunks,
         QuarantineChunksCapacity, ChunksUsagePercent, MemoryOverheadPercent);
   }
 
 private:
-  IntrusiveList<QuarantineBatch> List;
+  SinglyLinkedList<QuarantineBatch> List;
   atomic_uptr Size;
 
   void addToSize(uptr add) { atomic_store_relaxed(&Size, getSize() + add); }
   void subFromSize(uptr sub) { atomic_store_relaxed(&Size, getSize() - sub); }
 };
 
 // The callback interface is:
 // void Callback::recycle(Node *Ptr);

lib/scudo/standalone/release.h

private:
   const uptr PageSizeLog;
   bool InRange = false;
   uptr CurrentPage = 0;
   uptr CurrentRangeStatePage = 0;
 };
 
 template <class TransferBatchT, class ReleaseRecorderT>
 NOINLINE void
-releaseFreeMemoryToOS(const IntrusiveList<TransferBatchT> *FreeList, uptr Base,
+releaseFreeMemoryToOS(const IntrusiveList<TransferBatchT> &FreeList, uptr Base,
                       uptr AllocatedPagesCount, uptr BlockSize,
                       ReleaseRecorderT *Recorder) {
   const uptr PageSize = getPageSizeCached();
 
   // Figure out the number of chunks per page and whether we can take a fast
   // path (the number of chunks per page is the same for all pages).
   uptr FullPagesBlockCountMax;
   bool SameBlockCountPerPage;
releaseFreeMemoryToOS(const IntrusiveList<TransferBatchT> &FreeList, uptr Base,
 
   const uptr PageSizeLog = getLog2(PageSize);
   const uptr End = Base + AllocatedPagesCount * PageSize;
 
   // Iterate over free chunks and count how many free chunks affect each
   // allocated page.
   if (BlockSize <= PageSize && PageSize % BlockSize == 0) {
     // Each chunk affects one page only.
-    for (auto It = FreeList->begin(); It != FreeList->end(); ++It) {
-      for (u32 I = 0; I < (*It).getCount(); I++) {
-        const uptr P = reinterpret_cast<uptr>((*It).get(I));
+    for (const auto &It : FreeList) {
+      for (u32 I = 0; I < It.getCount(); I++) {
+        const uptr P = reinterpret_cast<uptr>(It.get(I));
         if (P >= Base && P < End)
           Counters.inc((P - Base) >> PageSizeLog);
       }
     }
   } else {
     // In all other cases chunks might affect more than one page.
-    for (auto It = FreeList->begin(); It != FreeList->end(); ++It) {
-      for (u32 I = 0; I < (*It).getCount(); I++) {
-        const uptr P = reinterpret_cast<uptr>((*It).get(I));
+    for (const auto &It : FreeList) {
+      for (u32 I = 0; I < It.getCount(); I++) {
+        const uptr P = reinterpret_cast<uptr>(It.get(I));
         if (P >= Base && P < End)
           Counters.incRange((P - Base) >> PageSizeLog,
                             (P - Base + BlockSize - 1) >> PageSizeLog);
       }
     }
   }
 
   // Iterate over pages detecting ranges of pages with chunk Counters equal

lib/scudo/standalone/secondary.h

 //===-- secondary.h ---------------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef SCUDO_SECONDARY_H_
 #define SCUDO_SECONDARY_H_
 
 #include "common.h"
+#include "list.h"
 #include "mutex.h"
 #include "stats.h"
 #include "string_utils.h"
 
 namespace scudo {
 
 // This allocator wraps the platform allocation primitives, and as such is on
 // the slower side and should preferably be used for larger sized allocations.
public:
 
   void getStats(ScopedString *Str) const;
 
   void disable() { Mutex.lock(); }
 
   void enable() { Mutex.unlock(); }
 
   template <typename F> void iterateOverBlocks(F Callback) const {
-    for (LargeBlock::Header *H = Tail; H != nullptr; H = H->Prev)
-      Callback(reinterpret_cast<uptr>(H) + LargeBlock::getHeaderSize());
+    for (const auto &H : InUseBlocks)
+      Callback(reinterpret_cast<uptr>(&H) + LargeBlock::getHeaderSize());
   }
 
 private:
   HybridMutex Mutex;
-  LargeBlock::Header *Tail;
+  DoublyLinkedList<LargeBlock::Header> InUseBlocks;
   uptr AllocatedBytes;
   uptr FreedBytes;
   uptr LargestSize;
   u32 NumberOfAllocs;
   u32 NumberOfFrees;
   LocalStats Stats;
 };
 
 } // namespace scudo
 
 #endif // SCUDO_SECONDARY_H_

lib/scudo/standalone/secondary.cpp

const uptr Ptr =
                                  CommitSize, "scudo:secondary", 0, &Data));
   LargeBlock::Header *H = reinterpret_cast<LargeBlock::Header *>(Ptr);
   H->MapBase = MapBase;
   H->MapSize = MapEnd - MapBase;
   H->BlockEnd = CommitBase + CommitSize;
   H->Data = Data;
   {
     ScopedLock L(Mutex);
-    if (LIKELY(Tail)) {
-      Tail->Next = H;
-      H->Prev = Tail;
-    }
-    Tail = H;
+    InUseBlocks.push_back(H);
     AllocatedBytes += CommitSize;
     if (LargestSize < CommitSize)
       LargestSize = CommitSize;
     NumberOfAllocs++;
     Stats.add(StatAllocated, CommitSize);
     Stats.add(StatMapped, H->MapSize);
   }
   if (BlockEnd)
     *BlockEnd = CommitBase + CommitSize;
   return reinterpret_cast<void *>(Ptr + LargeBlock::getHeaderSize());
 }
 
 void MapAllocator::deallocate(void *Ptr) {
   LargeBlock::Header *H = LargeBlock::getHeader(Ptr);
   {
     ScopedLock L(Mutex);
-    LargeBlock::Header *Prev = H->Prev;
-    LargeBlock::Header *Next = H->Next;
-    if (Prev) {
-      CHECK_EQ(Prev->Next, H);
-      Prev->Next = Next;
-    }
-    if (Next) {
-      CHECK_EQ(Next->Prev, H);
-      Next->Prev = Prev;
-    }
-    if (UNLIKELY(Tail == H)) {
-      CHECK(!Next);
-      Tail = Prev;
-    } else {
-      CHECK(Next);
-    }
+    InUseBlocks.remove(H);
     const uptr CommitSize = H->BlockEnd - reinterpret_cast<uptr>(H);
     FreedBytes += CommitSize;
     NumberOfFrees++;
     Stats.sub(StatAllocated, CommitSize);
     Stats.sub(StatMapped, H->MapSize);
   }
   void *Addr = reinterpret_cast<void *>(H->MapBase);
   const uptr Size = H->MapSize;

lib/scudo/standalone/stats.h

 //===-- stats.h -------------------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef SCUDO_STATS_H_
 #define SCUDO_STATS_H_
 
 #include "atomic_helpers.h"
+#include "list.h"
 #include "mutex.h"
 
 #include <string.h>
 
 namespace scudo {
 
 // Memory allocator statistics
 enum StatType { StatAllocated, StatFree, StatMapped, StatCount };
void sub(StatType I, uptr V) {
     V = atomic_load_relaxed(&StatsArray[I]) - V;
     atomic_store_relaxed(&StatsArray[I], V);
   }
 
   void set(StatType I, uptr V) { atomic_store_relaxed(&StatsArray[I], V); }
 
   uptr get(StatType I) const { return atomic_load_relaxed(&StatsArray[I]); }
 
-private:
-  friend class GlobalStats;
-  atomic_uptr StatsArray[StatCount];
   LocalStats *Next;
   LocalStats *Prev;
+
+private:
+  atomic_uptr StatsArray[StatCount];
 };
 
 // Global stats, used for aggregation and querying.
 class GlobalStats : public LocalStats {
 public:
-  void initLinkerInitialized() {
-    Next = this;
-    Prev = this;
-  }
+  void initLinkerInitialized() {}
   void init() {
     memset(this, 0, sizeof(*this));
     initLinkerInitialized();
   }
 
   void link(LocalStats *S) {
     ScopedLock L(Mutex);
-    S->Next = Next;
-    S->Prev = this;
-    Next->Prev = S;
-    Next = S;
+    StatsList.push_back(S);
   }
 
   void unlink(LocalStats *S) {
     ScopedLock L(Mutex);
-    S->Prev->Next = S->Next;
-    S->Next->Prev = S->Prev;
+    StatsList.remove(S);
     for (uptr I = 0; I < StatCount; I++)
       add(static_cast<StatType>(I), S->get(static_cast<StatType>(I)));
   }
 
   void get(uptr *S) const {
-    memset(S, 0, StatCount * sizeof(uptr));
     ScopedLock L(Mutex);
-    const LocalStats *Stats = this;
-    for (;;) {
-      for (uptr I = 0; I < StatCount; I++)
-        S[I] += Stats->get(static_cast<StatType>(I));
-      Stats = Stats->Next;
-      if (Stats == this)
-        break;
+      S[I] = LocalStats::get(static_cast<StatType>(I));
+    for (const auto &Stats : StatsList) {
+      for (uptr I = 0; I < StatCount; I++)
+        S[I] += Stats.get(static_cast<StatType>(I));
     }
     // All stats must be non-negative.
     for (uptr I = 0; I < StatCount; I++)
       S[I] = static_cast<sptr>(S[I]) >= 0 ? S[I] : 0;
   }
 
 private:
   mutable HybridMutex Mutex;
+  DoublyLinkedList<LocalStats> StatsList;
 };
 
 } // namespace scudo
 
 #endif // SCUDO_STATS_H_

lib/scudo/standalone/tests/list_test.cpp

 //===-- list_test.cpp -------------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "scudo/standalone/list.h"
 #include "gtest/gtest.h"
 
 struct ListItem {
   ListItem *Next;
+  ListItem *Prev;
 };
 
-typedef scudo::IntrusiveList<ListItem> List;
-
-static List StaticList;
-
-static void setList(List *L, ListItem *X = nullptr, ListItem *Y = nullptr,
-                    ListItem *Z = nullptr) {
+static ListItem Items[6];
+static ListItem *X = &Items[0];
+static ListItem *Y = &Items[1];
+static ListItem *Z = &Items[2];
+static ListItem *A = &Items[3];
+static ListItem *B = &Items[4];
+static ListItem *C = &Items[5];
+
+typedef scudo::SinglyLinkedList<ListItem> SLList;
+typedef scudo::DoublyLinkedList<ListItem> DLList;
+
+template <typename ListT>
+static void setList(ListT *L, ListItem *I1 = nullptr, ListItem *I2 = nullptr,
+                    ListItem *I3 = nullptr) {
   L->clear();
-  if (X)
-    L->push_back(X);
-  if (Y)
-    L->push_back(Y);
-  if (Z)
-    L->push_back(Z);
+  if (I1)
+    L->push_back(I1);
+  if (I2)
+    L->push_back(I2);
+  if (I3)
+    L->push_back(I3);
 }
 
-static void checkList(List *L, ListItem *I1, ListItem *I2 = nullptr,
+template <typename ListT>
+static void checkList(ListT *L, ListItem *I1, ListItem *I2 = nullptr,
                       ListItem *I3 = nullptr, ListItem *I4 = nullptr,
                       ListItem *I5 = nullptr, ListItem *I6 = nullptr) {
   if (I1) {
     EXPECT_EQ(L->front(), I1);
     L->pop_front();
   }
   if (I2) {
     EXPECT_EQ(L->front(), I2);
static void checkList(ListT *L, ListItem *I1, ListItem *I2 = nullptr,
   }
   if (I6) {
     EXPECT_EQ(L->front(), I6);
     L->pop_front();
   }
   EXPECT_TRUE(L->empty());
 }
 
-TEST(ScudoListTest, IntrusiveList) {
-  ListItem Items[6];
-  EXPECT_EQ(StaticList.size(), 0U);
-
-  List L;
+template <typename ListT> static void testListCommon(void) {
+  ListT L;
   L.clear();
 
-  ListItem *X = &Items[0];
-  ListItem *Y = &Items[1];
-  ListItem *Z = &Items[2];
-  ListItem *A = &Items[3];
-  ListItem *B = &Items[4];
-  ListItem *C = &Items[5];
-
   EXPECT_EQ(L.size(), 0U);
   L.push_back(X);
   EXPECT_EQ(L.size(), 1U);
   EXPECT_EQ(L.back(), X);
   EXPECT_EQ(L.front(), X);
   L.pop_front();
   EXPECT_TRUE(L.empty());
   L.checkConsistency();
template <typename ListT> static void testListCommon(void) {
   L.pop_front();
   EXPECT_EQ(L.size(), 2U);
   EXPECT_EQ(L.front(), Y);
   EXPECT_EQ(L.back(), Z);
   L.pop_front();
   L.pop_front();
   EXPECT_TRUE(L.empty());
   L.checkConsistency();
+}
+
+TEST(ScudoListTest, LinkedListCommon) {
+  testListCommon<SLList>();
+  testListCommon<DLList>();
+}
+
+TEST(ScudoListTest, SinglyLinkedList) {
+  SLList L;
+  L.clear();
 
   L.push_back(X);
   L.push_back(Y);
   L.push_back(Z);
   L.extract(X, Y);
   EXPECT_EQ(L.size(), 2U);
   EXPECT_EQ(L.front(), X);
   EXPECT_EQ(L.back(), Z);
   L.checkConsistency();
   L.extract(X, Z);
   EXPECT_EQ(L.size(), 1U);
   EXPECT_EQ(L.front(), X);
   EXPECT_EQ(L.back(), X);
   L.checkConsistency();
   L.pop_front();
   EXPECT_TRUE(L.empty());
 
-  List L1, L2;
+  SLList L1, L2;
   L1.clear();
   L2.clear();
 
-  L1.append_front(&L2);
-  EXPECT_TRUE(L1.empty());
-  EXPECT_TRUE(L2.empty());
-
   L1.append_back(&L2);
   EXPECT_TRUE(L1.empty());
   EXPECT_TRUE(L2.empty());
 
   setList(&L1, X);
   checkList(&L1, X);
 
   setList(&L1, X, Y, Z);
   setList(&L2, A, B, C);
   L1.append_back(&L2);
   checkList(&L1, X, Y, Z, A, B, C);
   EXPECT_TRUE(L2.empty());
 
-  setList(&L1, X, Y);
-  setList(&L2);
-  L1.append_front(&L2);
-  checkList(&L1, X, Y);
-  EXPECT_TRUE(L2.empty());
+  L1.clear();
+  L2.clear();
+  L1.push_back(X);
+  L1.append_back(&L2);
+  EXPECT_EQ(L1.back(), X);
+  EXPECT_EQ(L1.front(), X);
+  EXPECT_EQ(L1.size(), 1U);
 }
 
-TEST(ScudoListTest, IntrusiveListAppendEmpty) {
-  ListItem I;
-  List L;
+TEST(ScudoListTest, DoublyLinkedList) {
+  DLList L;
   L.clear();
-  L.push_back(&I);
-  List L2;
-  L2.clear();
-  L.append_back(&L2);
-  EXPECT_EQ(L.back(), &I);
-  EXPECT_EQ(L.front(), &I);
-  EXPECT_EQ(L.size(), 1U);
-  L.append_front(&L2);
-  EXPECT_EQ(L.back(), &I);
-  EXPECT_EQ(L.front(), &I);
+
+  L.push_back(X);
+  L.push_back(Y);
+  L.push_back(Z);
+  L.remove(Y);
+  EXPECT_EQ(L.size(), 2U);
+  EXPECT_EQ(L.front(), X);
+  EXPECT_EQ(L.back(), Z);
+  L.checkConsistency();
+  L.remove(Z);
   EXPECT_EQ(L.size(), 1U);
+  EXPECT_EQ(L.front(), X);
+  EXPECT_EQ(L.back(), X);
+  L.checkConsistency();
+  L.pop_front();
+  EXPECT_TRUE(L.empty());
 }

lib/scudo/standalone/tests/release_test.cpp

for (scudo::uptr I = 0; I < MaxBlocks; I++) {
         FreeArray.push_back(I * BlockSize);
     }
     if (FreeArray.empty())
       continue;
     // Shuffle the array to ensure that the order is irrelevant.
     std::shuffle(FreeArray.begin(), FreeArray.end(), R);
 
     // Build the FreeList from the FreeArray.
-    scudo::IntrusiveList<Batch> FreeList;
+    scudo::SinglyLinkedList<Batch> FreeList;
     FreeList.clear();
     Batch *CurrentBatch = nullptr;
     for (auto const &Block : FreeArray) {
       if (!CurrentBatch) {
         CurrentBatch = new Batch;
         CurrentBatch->clear();
         FreeList.push_back(CurrentBatch);
       }
       CurrentBatch->add(Block);
       if (CurrentBatch->getCount() == Batch::MaxCount)
         CurrentBatch = nullptr;
     }
 
     // Release the memory.
     ReleasedPagesRecorder Recorder;
-    releaseFreeMemoryToOS(&FreeList, 0, AllocatedPagesCount, BlockSize,
+    releaseFreeMemoryToOS(FreeList, 0, AllocatedPagesCount, BlockSize,
                           &Recorder);
 
     // Verify that there are no released pages touched by used chunks and all
     // ranges of free chunks big enough to contain the entire memory pages had
     // these pages released.
     scudo::uptr VerifiedReleasedPages = 0;
     std::set<scudo::uptr> FreeBlocks(FreeArray.begin(), FreeArray.end());