[scudo][standalone] Consolidate lists

Summary:
This is a clean patch using the last diff of D69265, but using git
instead of svn, since svn went ro and arc was making my life harded
than it needed to be.

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.

Reviewers: hctim, morehouse, pcc, cferris

Reviewed By: hctim

Subscribers: jfb, #sanitizers, llvm-commits

Tags: #sanitizers, #llvm

Differential Revision: https://reviews.llvm.org/D69516

1 files changed, 153 insertions, 82 deletions

diff --git a/compiler-rt/lib/scudo/standalone/list.h b/compiler-rt/lib/scudo/standalone/list.h
index 6a7b9bd747a..ca5b3167ab0 100644
--- a/compiler-rt/lib/scudo/standalone/list.h
+++ b/compiler-rt/lib/scudo/standalone/list.h
@@ -13,43 +13,93 @@
 
 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;
-      Size = 1;
-    } else {
-      X->Next = nullptr;
-      Last->Next = X;
-      Last = X;
-      Size++;
+  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);
   }
+}
 
-  void push_front(Item *X) {
-    if (empty()) {
-      X->Next = nullptr;
-      First = Last = X;
-      Size = 1;
-    } else {
-      X->Next = First;
+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) {
+    X->Next = nullptr;
+    if (empty())
       First = X;
-      Size++;
-    }
+    else
+      Last->Next = X;
+    Last = X;
+    Size++;
+  }
+
+  void push_front(T *X) {
+    if (empty())
+      Last = X;
+    X->Next = First;
+    First = X;
+    Size++;
   }
 
   void pop_front() {
@@ -60,7 +110,7 @@ template <class Item> struct IntrusiveList {
     Size--;
   }
 
-  void extract(Item *Prev, Item *X) {
+  void extract(T *Prev, T *X) {
     DCHECK(!empty());
     DCHECK_NE(Prev, nullptr);
     DCHECK_NE(X, nullptr);
@@ -71,84 +121,105 @@ template <class Item> struct IntrusiveList {
     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) {
+  void append_back(SinglyLinkedList<T> *L) {
     DCHECK_NE(this, L);
     if (L->empty())
       return;
     if (empty()) {
       *this = *L;
-    } else if (!L->empty()) {
-      L->Last->Next = First;
-      First = L->First;
+    } else {
+      Last->Next = L->First;
+      Last = L->Last;
       Size += L->size();
     }
     L->clear();
   }
+};
 
-  void append_back(IntrusiveList<Item> *L) {
-    DCHECK_NE(this, L);
-    if (L->empty())
-      return;
+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()) {
-      *this = *L;
+      Last = X;
     } else {
-      Last->Next = L->First;
-      Last = L->Last;
-      Size += L->size();
+      DCHECK_EQ(First->Prev, nullptr);
     }
-    L->clear();
+    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;
+    // This is a hard CHECK to ensure consistency in the event of an intentional
+    // corruption of Y->Prev, to prevent a potential write-{4,8}.
+    CHECK_EQ(Prev->Next, Y);
+    Prev->Next = X;
+    X->Prev = Prev;
+    X->Next = Y;
+    Y->Prev = X;
+    Size++;
   }
 
-  void checkConsistency() {
-    if (Size == 0) {
-      CHECK_EQ(First, nullptr);
-      CHECK_EQ(Last, nullptr);
+  void push_back(T *X) {
+    X->Next = nullptr;
+    if (empty()) {
+      First = 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(Last->Next, nullptr);
+      Last->Next = X;
     }
+    X->Prev = Last;
+    Last = X;
+    Size++;
   }
 
-  template <class ItemT> class IteratorBase {
-  public:
-    explicit IteratorBase(ItemT *CurrentItem) : Current(CurrentItem) {}
-    IteratorBase &operator++() {
-      Current = Current->Next;
-      return *this;
+  void pop_front() {
+    DCHECK(!empty());
+    First = First->Next;
+    if (!First)
+      Last = nullptr;
+    else
+      First->Prev = nullptr;
+    Size--;
+  }
+
+  // The consistency of the adjacent links is aggressively checked in order to
+  // catch potential corruption attempts, that could yield a mirrored
+  // write-{4,8} primitive. nullptr checks are deemed less vital.
+  void remove(T *X) {
+    T *Prev = X->Prev;
+    T *Next = X->Next;
+    if (Prev) {
+      CHECK_EQ(Prev->Next, X);
+      Prev->Next = Next;
     }
-    bool operator!=(IteratorBase Other) const {
-      return Current != Other.Current;
+    if (Next) {
+      CHECK_EQ(Next->Prev, X);
+      Next->Prev = Prev;
     }
-    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); }
-
-  ConstIterator begin() const { return ConstIterator(First); }
-  ConstIterator end() const { return ConstIterator(nullptr); }
-
-private:
-  uptr Size;
-  Item *First;
-  Item *Last;
+    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