Bug 1212624 - Tests for LinkedList, r=Waldo
authorSteve Fink <sfink@mozilla.com>
Wed, 07 Oct 2015 12:36:00 -0700
changeset 291357 5dfeaa81f035ded15afb705f249c9b4d54e349fc
parent 291356 8aba07c1a690d6e5e6e339a10f1ed13198931931
child 291358 0085266cdfd3c77dae0e2711bae9002246c65e36
push idunknown
push userunknown
push dateunknown
reviewersWaldo
bugs1212624
milestone44.0a1
Bug 1212624 - Tests for LinkedList, r=Waldo
js/src/gc/Marking.cpp
js/src/gc/Zone.cpp
js/src/gc/Zone.h
js/src/jsweakmap.cpp
js/src/jsweakmap.h
js/src/vm/WeakMapPtr.cpp
mfbt/tests/TestLinkedList.cpp
mfbt/tests/moz.build
--- a/js/src/gc/Marking.cpp
+++ b/js/src/gc/Marking.cpp
@@ -1770,17 +1770,17 @@ GCMarker::enterWeakMarkingMode()
         return;
 
     // During weak marking mode, we maintain a table mapping weak keys to
     // entries in known-live weakmaps.
     if (weakMapAction() == ExpandWeakMaps) {
         tag_ = TracerKindTag::WeakMarking;
 
         for (GCZoneGroupIter zone(runtime()); !zone.done(); zone.next()) {
-            for (WeakMapBase* m = zone->gcWeakMapList; m; m = m->next) {
+            for (WeakMapBase* m : zone->gcWeakMapList) {
                 if (m->marked)
                     m->markEphemeronEntries(this);
             }
         }
     }
 }
 
 void
--- a/js/src/gc/Zone.cpp
+++ b/js/src/gc/Zone.cpp
@@ -22,17 +22,16 @@ using namespace js::gc;
 
 Zone * const Zone::NotOnList = reinterpret_cast<Zone*>(1);
 
 JS::Zone::Zone(JSRuntime* rt)
   : JS::shadow::Zone(rt, &rt->gc.marker),
     debuggers(nullptr),
     arenas(rt),
     types(this),
-    gcWeakMapList(nullptr),
     compartments(),
     gcGrayRoots(),
     gcMallocBytes(0),
     gcMallocGCTriggered(false),
     usage(&rt->gc.usage),
     gcDelayBytes(0),
     data(nullptr),
     isSystem(false),
--- a/js/src/gc/Zone.h
+++ b/js/src/gc/Zone.h
@@ -278,18 +278,18 @@ struct Zone : public JS::shadow::Zone,
             oomUnsafe.crash("Zone::enqueueForPromotionToTenuredLogging");
     }
     void logPromotionsToTenured();
 
     js::gc::ArenaLists arenas;
 
     js::TypeZone types;
 
-    /* Linked list of live weakmaps in this zone. */
-    js::WeakMapBase* gcWeakMapList;
+    /* Live weakmaps in this zone. */
+    mozilla::LinkedList<js::WeakMapBase> gcWeakMapList;
 
     // The set of compartments in this zone.
     typedef js::Vector<JSCompartment*, 1, js::SystemAllocPolicy> CompartmentVector;
     CompartmentVector compartments;
 
     // This zone's gray roots.
     typedef js::Vector<js::gc::Cell*, 0, js::SystemAllocPolicy> GrayRootVector;
     GrayRootVector gcGrayRoots;
--- a/js/src/jsweakmap.cpp
+++ b/js/src/jsweakmap.cpp
@@ -20,28 +20,24 @@
 #include "jsobjinlines.h"
 
 using namespace js;
 using namespace js::gc;
 
 WeakMapBase::WeakMapBase(JSObject* memOf, Zone* zone)
   : memberOf(memOf),
     zone(zone),
-    next(WeakMapNotInList),
     marked(false)
 {
     MOZ_ASSERT_IF(memberOf, memberOf->compartment()->zone() == zone);
 }
 
 WeakMapBase::~WeakMapBase()
 {
     MOZ_ASSERT(CurrentThreadIsGCSweeping() || CurrentThreadIsHandlingInitFailure());
-    MOZ_ASSERT_IF(CurrentThreadIsGCSweeping(), !isInList());
-    if (isInList())
-        removeWeakMapFromList(this);
 }
 
 void
 WeakMapBase::trace(JSTracer* tracer)
 {
     MOZ_ASSERT(isInList());
     if (tracer->isMarkingTracer()) {
         marked = true;
@@ -66,94 +62,90 @@ WeakMapBase::trace(JSTracer* tracer)
         if (tracer->weakMapAction() == TraceWeakMapKeysValues)
             nonMarkingTraceKeys(tracer);
     }
 }
 
 void
 WeakMapBase::unmarkZone(JS::Zone* zone)
 {
-    for (WeakMapBase* m = zone->gcWeakMapList; m; m = m->next)
+    for (WeakMapBase* m : zone->gcWeakMapList)
         m->marked = false;
 }
 
 void
 WeakMapBase::markAll(JS::Zone* zone, JSTracer* tracer)
 {
     MOZ_ASSERT(tracer->weakMapAction() != DoNotTraceWeakMaps);
-    for (WeakMapBase* m = zone->gcWeakMapList; m; m = m->next) {
+    for (WeakMapBase* m : zone->gcWeakMapList) {
         m->trace(tracer);
         if (m->memberOf)
             TraceEdge(tracer, &m->memberOf, "memberOf");
     }
 }
 
 bool
 WeakMapBase::markZoneIteratively(JS::Zone* zone, JSTracer* tracer)
 {
     bool markedAny = false;
-    for (WeakMapBase* m = zone->gcWeakMapList; m; m = m->next) {
+    for (WeakMapBase* m : zone->gcWeakMapList) {
         if (m->marked && m->markIteratively(tracer))
             markedAny = true;
     }
     return markedAny;
 }
 
 bool
 WeakMapBase::findInterZoneEdges(JS::Zone* zone)
 {
-    for (WeakMapBase* m = zone->gcWeakMapList; m; m = m->next) {
+    for (WeakMapBase* m : zone->gcWeakMapList) {
         if (!m->findZoneEdges())
             return false;
     }
     return true;
 }
 
 void
 WeakMapBase::sweepZone(JS::Zone* zone)
 {
-    WeakMapBase** tailPtr = &zone->gcWeakMapList;
-    for (WeakMapBase* m = zone->gcWeakMapList; m; ) {
-        WeakMapBase* next = m->next;
+    for (WeakMapBase* m = zone->gcWeakMapList.getFirst(); m; ) {
+        WeakMapBase* next = m->getNext();
         if (m->marked) {
             m->sweep();
-            *tailPtr = m;
-            tailPtr = &m->next;
         } else {
             /* Destroy the hash map now to catch any use after this point. */
             m->finish();
-            m->next = WeakMapNotInList;
+            m->removeFrom(zone->gcWeakMapList);
         }
         m = next;
     }
-    *tailPtr = nullptr;
 
 #ifdef DEBUG
-    for (WeakMapBase* m = zone->gcWeakMapList; m; m = m->next)
+    for (WeakMapBase* m : zone->gcWeakMapList)
         MOZ_ASSERT(m->isInList() && m->marked);
 #endif
 }
 
 void
 WeakMapBase::traceAllMappings(WeakMapTracer* tracer)
 {
     JSRuntime* rt = tracer->runtime;
     for (ZonesIter zone(rt, SkipAtoms); !zone.done(); zone.next()) {
-        for (WeakMapBase* m = zone->gcWeakMapList; m; m = m->next) {
+        for (WeakMapBase* m : zone->gcWeakMapList) {
             // The WeakMapTracer callback is not allowed to GC.
             JS::AutoSuppressGCAnalysis nogc;
             m->traceMappings(tracer);
         }
     }
 }
 
 bool
 WeakMapBase::saveZoneMarkedWeakMaps(JS::Zone* zone, WeakMapSet& markedWeakMaps)
 {
-    for (WeakMapBase* m = zone->gcWeakMapList; m; m = m->next) {
+    for (WeakMapBase* m : zone->gcWeakMapList) {
         if (m->marked && !markedWeakMaps.put(m))
             return false;
     }
     return true;
 }
 
 void
 WeakMapBase::restoreMarkedWeakMaps(WeakMapSet& markedWeakMaps)
@@ -161,29 +153,16 @@ WeakMapBase::restoreMarkedWeakMaps(WeakM
     for (WeakMapSet::Range r = markedWeakMaps.all(); !r.empty(); r.popFront()) {
         WeakMapBase* map = r.front();
         MOZ_ASSERT(map->zone->isGCMarking());
         MOZ_ASSERT(!map->marked);
         map->marked = true;
     }
 }
 
-void
-WeakMapBase::removeWeakMapFromList(WeakMapBase* weakmap)
-{
-    JS::Zone* zone = weakmap->zone;
-    for (WeakMapBase** p = &zone->gcWeakMapList; *p; p = &(*p)->next) {
-        if (*p == weakmap) {
-            *p = (*p)->next;
-            weakmap->next = WeakMapNotInList;
-            break;
-        }
-    }
-}
-
 bool
 ObjectValueMap::findZoneEdges()
 {
     /*
      * For unmarked weakmap keys with delegates in a different zone, add a zone
      * edge to ensure that the delegate zone finishes marking before the key
      * zone.
      */
@@ -212,21 +191,16 @@ ObjectWeakMap::ObjectWeakMap(JSContext* 
 {}
 
 bool
 ObjectWeakMap::init()
 {
     return map.init();
 }
 
-ObjectWeakMap::~ObjectWeakMap()
-{
-    WeakMapBase::removeWeakMapFromList(&map);
-}
-
 JSObject*
 ObjectWeakMap::lookup(const JSObject* obj)
 {
     MOZ_ASSERT(map.initialized());
     if (ObjectValueMap::Ptr p = map.lookup(const_cast<JSObject*>(obj)))
         return &p->value().toObject();
     return nullptr;
 }
--- a/js/src/jsweakmap.h
+++ b/js/src/jsweakmap.h
@@ -2,16 +2,17 @@
  * vim: set ts=8 sts=4 et sw=4 tw=99:
  * This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #ifndef jsweakmap_h
 #define jsweakmap_h
 
+#include "mozilla/LinkedList.h"
 #include "mozilla/Move.h"
 
 #include "jscompartment.h"
 #include "jsfriendapi.h"
 #include "jsobj.h"
 
 #include "gc/Marking.h"
 #include "gc/StoreBuffer.h"
@@ -30,24 +31,22 @@ class WeakMapBase;
 //     is collected. If an entry is not collected, it remains in the WeakMap and it has a
 //     strong reference to the value.
 //
 // You must call this table's 'trace' method when the object of which it is a part is
 // reached by the garbage collection tracer. Once a table is known to be live, the
 // implementation takes care of the iterative marking needed for weak tables and removing
 // table entries when collection is complete.
 
-// The value for the next pointer for maps not in the map list.
-static WeakMapBase * const WeakMapNotInList = reinterpret_cast<WeakMapBase*>(1);
-
 typedef HashSet<WeakMapBase*, DefaultHasher<WeakMapBase*>, SystemAllocPolicy> WeakMapSet;
 
 // Common base class for all WeakMap specializations. The collector uses this to call
 // their markIteratively and sweep methods.
-class WeakMapBase {
+class WeakMapBase : public mozilla::LinkedListElement<WeakMapBase>
+{
     friend void js::GCMarker::enterWeakMarkingMode();
 
   public:
     WeakMapBase(JSObject* memOf, JS::Zone* zone);
     virtual ~WeakMapBase();
 
     void trace(JSTracer* tracer);
 
@@ -70,27 +69,22 @@ class WeakMapBase {
 
     // Sweep the weak maps in a zone, removing dead weak maps and removing
     // entries of live weak maps whose keys are dead.
     static void sweepZone(JS::Zone* zone);
 
     // Trace all delayed weak map bindings. Used by the cycle collector.
     static void traceAllMappings(WeakMapTracer* tracer);
 
-    bool isInList() { return next != WeakMapNotInList; }
-
     // Save information about which weak maps are marked for a zone.
     static bool saveZoneMarkedWeakMaps(JS::Zone* zone, WeakMapSet& markedWeakMaps);
 
     // Restore information about which weak maps are marked for many zones.
     static void restoreMarkedWeakMaps(WeakMapSet& markedWeakMaps);
 
-    // Remove a weakmap from its zone's weakmaps list.
-    static void removeWeakMapFromList(WeakMapBase* weakmap);
-
     // Any weakmap key types that want to participate in the non-iterative
     // ephemeron marking must override this method.
     virtual void maybeMarkEntry(JSTracer* trc, gc::Cell* markedCell, JS::GCCellPtr l) = 0;
 
     virtual void markEphemeronEntries(JSTracer* trc) = 0;
 
   protected:
     // Instance member functions called by the above. Instantiations of WeakMap override
@@ -104,21 +98,16 @@ class WeakMapBase {
     virtual void finish() = 0;
 
     // Object that this weak map is part of, if any.
     HeapPtrObject memberOf;
 
     // Zone containing this weak map.
     JS::Zone* zone;
 
-    // Link in a list of all WeakMaps in a Zone, headed by
-    // JS::Zone::gcWeakMapList. The last element of the list has nullptr as its
-    // next. Maps not in the list have WeakMapNotInList as their next.
-    WeakMapBase* next;
-
     // Whether this object has been traced during garbage collection.
     bool marked;
 };
 
 template <typename T>
 static T extractUnbarriered(WriteBarrieredBase<T> v)
 {
     return v.get();
@@ -142,18 +131,17 @@ class WeakMap : public HashMap<Key, Valu
     typedef typename Base::AddPtr AddPtr;
 
     explicit WeakMap(JSContext* cx, JSObject* memOf = nullptr)
         : Base(cx->runtime()), WeakMapBase(memOf, cx->compartment()->zone()) { }
 
     bool init(uint32_t len = 16) {
         if (!Base::init(len))
             return false;
-        next = zone->gcWeakMapList;
-        zone->gcWeakMapList = this;
+        zone->gcWeakMapList.insertFront(this);
         marked = JS::IsIncrementalGCInProgress(zone->runtimeFromMainThread());
         return true;
     }
 
     // Overwritten to add a read barrier to prevent an incorrectly gray value
     // from escaping the weak map. See the comment before UnmarkGrayChildren in
     // gc/Marking.cpp
     Ptr lookup(const Lookup& l) const {
@@ -172,16 +160,19 @@ class WeakMap : public HashMap<Key, Valu
 
     Ptr lookupWithDefault(const Key& k, const Value& defaultValue) {
         Ptr p = Base::lookupWithDefault(k, defaultValue);
         if (p)
             exposeGCThingToActiveJS(p->value());
         return p;
     }
 
+    // Resolve ambiguity with LinkedListElement<>::remove.
+    using Base::remove;
+
     // The WeakMap and some part of the key are marked. If the entry is marked
     // according to the exact semantics of this WeakMap, then mark the value.
     // (For a standard WeakMap, the entry is marked if either the key its
     // delegate is marked.)
     void maybeMarkEntry(JSTracer* trc, gc::Cell* markedCell, JS::GCCellPtr origKey) override
     {
         MOZ_ASSERT(marked);
 
@@ -413,17 +404,16 @@ class ObjectWeakMap
 {
   private:
     ObjectValueMap map;
     typedef gc::HashKeyRef<ObjectValueMap, JSObject*> StoreBufferRef;
 
   public:
     explicit ObjectWeakMap(JSContext* cx);
     bool init();
-    ~ObjectWeakMap();
 
     JSObject* lookup(const JSObject* obj);
     bool add(JSContext* cx, JSObject* obj, JSObject* target);
     void clear();
 
     void trace(JSTracer* trc);
     size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf);
     size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) {
--- a/js/src/vm/WeakMapPtr.cpp
+++ b/js/src/vm/WeakMapPtr.cpp
@@ -48,22 +48,17 @@ struct Utils
 
 } /* namespace */
 
 template <typename K, typename V>
 void
 JS::WeakMapPtr<K, V>::destroy()
 {
     MOZ_ASSERT(initialized());
-    auto map = Utils<K, V>::cast(ptr);
-    // If this destruction happens mid-GC, we might be in the compartment's list
-    // of known live weakmaps. If we are, remove ourselves before deleting.
-    if (map->isInList())
-        WeakMapBase::removeWeakMapFromList(map);
-    js_delete(map);
+    js_delete(Utils<K, V>::cast(ptr));
     ptr = nullptr;
 }
 
 template <typename K, typename V>
 bool
 JS::WeakMapPtr<K, V>::init(JSContext* cx)
 {
     MOZ_ASSERT(!initialized());
new file mode 100644
--- /dev/null
+++ b/mfbt/tests/TestLinkedList.cpp
@@ -0,0 +1,147 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=8 sts=2 et sw=2 tw=80: */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this file,
+ * You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "mozilla/Assertions.h"
+#include "mozilla/LinkedList.h"
+
+using mozilla::LinkedList;
+using mozilla::LinkedListElement;
+
+struct SomeClass : public LinkedListElement<SomeClass> {
+  unsigned int mValue;
+  explicit SomeClass(int aValue) : mValue(aValue) {}
+  void incr() { ++mValue; }
+};
+
+template <size_t N>
+static void
+CheckListValues(LinkedList<SomeClass>& list, unsigned int (&values)[N])
+{
+  size_t count = 0;
+  for (SomeClass* x : list) {
+    MOZ_RELEASE_ASSERT(x->mValue == values[count]);
+    ++count;
+  }
+  MOZ_RELEASE_ASSERT(count == N);
+}
+
+static void
+TestList()
+{
+  LinkedList<SomeClass> list;
+
+  SomeClass one(1), two(2), three(3);
+  
+  MOZ_RELEASE_ASSERT(list.isEmpty());
+  MOZ_RELEASE_ASSERT(!list.getFirst());
+  MOZ_RELEASE_ASSERT(!list.getLast());
+  MOZ_RELEASE_ASSERT(!list.popFirst());
+  MOZ_RELEASE_ASSERT(!list.popLast());
+
+  for (SomeClass* x : list) {
+    MOZ_RELEASE_ASSERT(x);
+    MOZ_RELEASE_ASSERT(false);
+  }
+
+  list.insertFront(&one);
+  { unsigned int check[] { 1 }; CheckListValues(list, check); }
+
+  MOZ_RELEASE_ASSERT(one.isInList());
+  MOZ_RELEASE_ASSERT(!two.isInList());
+  MOZ_RELEASE_ASSERT(!three.isInList());
+  
+  MOZ_RELEASE_ASSERT(!list.isEmpty());
+  MOZ_RELEASE_ASSERT(list.getFirst()->mValue == 1);
+  MOZ_RELEASE_ASSERT(list.getLast()->mValue == 1);
+
+  list.insertFront(&two);
+  { unsigned int check[] { 2, 1 }; CheckListValues(list, check); }
+
+  MOZ_RELEASE_ASSERT(list.getFirst()->mValue == 2);
+  MOZ_RELEASE_ASSERT(list.getLast()->mValue == 1);
+
+  list.insertBack(&three);
+  { unsigned int check[] { 2, 1, 3 }; CheckListValues(list, check); }
+
+  MOZ_RELEASE_ASSERT(list.getFirst()->mValue == 2);
+  MOZ_RELEASE_ASSERT(list.getLast()->mValue == 3);
+
+  one.removeFrom(list);
+  { unsigned int check[] { 2, 3 }; CheckListValues(list, check); }
+
+  three.setPrevious(&one);
+  { unsigned int check[] { 2, 1, 3 }; CheckListValues(list, check); }
+
+  three.removeFrom(list);
+  { unsigned int check[] { 2, 1 }; CheckListValues(list, check); }
+
+  two.setPrevious(&three);
+  { unsigned int check[] { 3, 2, 1 }; CheckListValues(list, check); }
+
+  three.removeFrom(list);
+  { unsigned int check[] { 2, 1 }; CheckListValues(list, check); }
+
+  two.setNext(&three);
+  { unsigned int check[] { 2, 3, 1 }; CheckListValues(list, check); }
+
+  one.remove();
+  { unsigned int check[] { 2, 3 }; CheckListValues(list, check); }
+
+  two.remove();
+  { unsigned int check[] { 3 }; CheckListValues(list, check); }
+
+  three.setPrevious(&two);
+  { unsigned int check[] { 2, 3 }; CheckListValues(list, check); }
+
+  three.remove();
+  { unsigned int check[] { 2 }; CheckListValues(list, check); }
+
+  two.remove();
+
+  list.insertBack(&three);
+  { unsigned int check[] { 3 }; CheckListValues(list, check); }
+
+  list.insertFront(&two);
+  { unsigned int check[] { 2, 3 }; CheckListValues(list, check); }
+
+  for (SomeClass* x : list) {
+    x->incr();
+  }
+
+  MOZ_RELEASE_ASSERT(list.getFirst() == &two);
+  MOZ_RELEASE_ASSERT(list.getLast() == &three);
+  MOZ_RELEASE_ASSERT(list.getFirst()->mValue == 3);
+  MOZ_RELEASE_ASSERT(list.getLast()->mValue == 4);
+}
+
+struct PrivateClass : private LinkedListElement<PrivateClass> {
+  friend class mozilla::LinkedList<PrivateClass>;
+  friend class mozilla::LinkedListElement<PrivateClass>;
+};
+
+static void
+TestPrivate()
+{
+  LinkedList<PrivateClass> list;
+  PrivateClass one, two;
+  list.insertBack(&one);
+  list.insertBack(&two);
+
+  size_t count = 0;
+  for (PrivateClass* p : list) {
+    MOZ_RELEASE_ASSERT(p, "cannot have null elements in list");
+    count++;
+  }
+  MOZ_RELEASE_ASSERT(count == 2);
+}
+
+int
+main()
+{
+  TestList();
+  TestPrivate();
+  return 0;
+}
--- a/mfbt/tests/moz.build
+++ b/mfbt/tests/moz.build
@@ -17,16 +17,17 @@ CppUnitTests([
     'TestEndian',
     'TestEnumSet',
     'TestFastBernoulliTrial',
     'TestFloatingPoint',
     'TestFunction',
     'TestIntegerPrintfMacros',
     'TestIntegerRange',
     'TestJSONWriter',
+    'TestLinkedList',
     'TestMacroArgs',
     'TestMacroForEach',
     'TestMathAlgorithms',
     'TestMaybe',
     'TestPair',
     'TestRefPtr',
     'TestRollingMean',
     'TestScopeExit',