Bug 1011355 (part 2) - Add a CompactFreeSpan class. r=billm.
authorNicholas Nethercote <nnethercote@mozilla.com>
Thu, 15 May 2014 22:16:25 -0700
changeset 183430 6a3df055066a6c942c20b1e600be06c3eacadd29
parent 183429 734a94168769bc4beedaa7e5011796f9ed2ab404
child 183431 5385817bdae605fab0c8415e12fe6b1965d79df3
push idunknown
push userunknown
push dateunknown
reviewersbillm
bugs1011355
milestone32.0a1
Bug 1011355 (part 2) - Add a CompactFreeSpan class. r=billm.
js/src/gc/Heap.h
js/src/jsgc.cpp
--- a/js/src/gc/Heap.h
+++ b/js/src/gc/Heap.h
@@ -143,18 +143,19 @@ const size_t ArenaBitmapWords = ArenaBit
  * - In a non-empty span, |first| is the address of the first free thing in the
  *   span, and |last| is the address of the last free thing in the span.
  *   Furthermore, the memory pointed to by |last| holds a FreeSpan structure
  *   that points to the next span (which may be empty); this works because
  *   sizeof(FreeSpan) is less than the smallest thingSize.
  */
 class FreeSpan
 {
+    friend class ArenaCellIterImpl;
+    friend class CompactFreeSpan;
     friend class FreeList;
-    friend class ArenaCellIterImpl;
 
     uintptr_t   first;
     uintptr_t   last;
 
   public:
     FreeSpan() {}
 
     // This inits just |first| and |last|; if the span is non-empty it doesn't
@@ -183,47 +184,16 @@ class FreeSpan
         last = lastArg;
         FreeSpan *lastSpan = reinterpret_cast<FreeSpan*>(last);
         lastSpan->first = 0;
         lastSpan->last = 0;
         JS_ASSERT(!isEmpty());
         checkSpan(thingSize);
     }
 
-    /*
-     * To minimize the size of the arena header the first span is encoded
-     * there as offsets from the arena start.
-     */
-    static size_t encodeOffsets(size_t firstOffset, size_t lastOffset) {
-        static_assert(ArenaShift < 16, "Check that we can pack offsets into uint16_t.");
-        JS_ASSERT(firstOffset <= lastOffset);
-        JS_ASSERT(lastOffset < ArenaSize);
-        return firstOffset | (lastOffset << 16);
-    }
-
-    /*
-     * Encoded offsets for a full arena, i.e. one with an empty FreeSpan.
-     */
-    static const size_t FullArenaOffsets = 0;
-
-    static FreeSpan decodeOffsets(uintptr_t arenaAddr, size_t offsets) {
-        JS_ASSERT(!(arenaAddr & ArenaMask));
-        FreeSpan decodedSpan;
-        if (offsets == FullArenaOffsets) {
-            decodedSpan.initAsEmpty();
-        } else {
-            size_t firstOffset = offsets & 0xFFFF;
-            size_t lastOffset = offsets >> 16;
-            JS_ASSERT(firstOffset <= lastOffset);
-            JS_ASSERT(lastOffset < ArenaSize);
-            decodedSpan.initBounds(arenaAddr + firstOffset, arenaAddr + lastOffset);
-        }
-        return decodedSpan;
-    }
-
     bool isEmpty() const {
         checkSpan();
         return !first;
     }
 
     // Like nextSpan(), but no checking of the following span is done.
     FreeSpan *nextSpanUnchecked() const {
         return reinterpret_cast<FreeSpan *>(last);
@@ -242,20 +212,16 @@ class FreeSpan
 #ifdef DEBUG
     bool isWithinArena(uintptr_t arenaAddr) const {
         JS_ASSERT(!(arenaAddr & ArenaMask));
         JS_ASSERT(!isEmpty());
         return arenaAddress() == arenaAddr;
     }
 #endif
 
-    size_t encodeAsOffsets() const {
-        return encodeOffsets(first & ArenaMask, last & ArenaMask);
-    }
-
     size_t length(size_t thingSize) const {
         checkSpan();
         JS_ASSERT((last - first) % thingSize == 0);
         return (last - first) / thingSize + 1;
     }
 
     bool inFreeList(uintptr_t thing) {
         for (const FreeSpan *span = this; !span->isEmpty(); span = span->nextSpan()) {
@@ -295,16 +261,67 @@ class FreeSpan
             JS_ASSERT(thingSize
                       ? last + 2 * thingSize <= next->first
                       : last < next->first);
         }
 #endif
     }
 };
 
+class CompactFreeSpan
+{
+    uint16_t firstOffset_;
+    uint16_t lastOffset_;
+
+  public:
+    CompactFreeSpan(size_t firstOffset, size_t lastOffset)
+      : firstOffset_(firstOffset)
+      , lastOffset_(lastOffset)
+    {}
+
+    void initAsEmpty() {
+        firstOffset_ = 0;
+        lastOffset_ = 0;
+    }
+
+    bool operator==(const CompactFreeSpan &other) const {
+        return firstOffset_ == other.firstOffset_ &&
+               lastOffset_  == other.lastOffset_;
+    }
+
+    void compact(FreeSpan span) {
+        if (span.isEmpty()) {
+            initAsEmpty();
+        } else {
+            static_assert(ArenaShift < 16, "Check that we can pack offsets into uint16_t.");
+            uintptr_t arenaAddr = span.arenaAddress();
+            firstOffset_ = span.first - arenaAddr;
+            lastOffset_  = span.last  - arenaAddr;
+        }
+    }
+
+    bool isEmpty() const {
+        JS_ASSERT(!!firstOffset_ == !!lastOffset_);
+        return !firstOffset_;
+    }
+
+    FreeSpan decompact(uintptr_t arenaAddr) const {
+        JS_ASSERT(!(arenaAddr & ArenaMask));
+        FreeSpan decodedSpan;
+        if (isEmpty()) {
+            decodedSpan.initAsEmpty();
+        } else {
+            JS_ASSERT(firstOffset_ <= lastOffset_);
+            JS_ASSERT(lastOffset_ < ArenaSize);
+            decodedSpan.initBounds(arenaAddr + firstOffset_, arenaAddr + lastOffset_);
+        }
+        return decodedSpan;
+    }
+};
+
 class FreeList
 {
     // Although |head| is private, it is exposed to the JITs via the
     // offsetOf{First,Last}() and addressOfFirstLast() methods below.
     // Therefore, any change in the representation of |head| will require
     // updating the relevant JIT code.
     FreeSpan head;
 
@@ -390,21 +407,20 @@ struct ArenaHeader : public JS::shadow::
      * ArenaHeader::next has two purposes: when unallocated, it points to the
      * next available Arena's header. When allocated, it points to the next
      * arena of the same size class and compartment.
      */
     ArenaHeader     *next;
 
   private:
     /*
-     * The first span of free things in the arena. We encode it as the start
-     * and end offsets within the arena, not as FreeSpan structure, to
-     * minimize the header size.
+     * The first span of free things in the arena. We encode it as a
+     * CompactFreeSpan rather than a FreeSpan to minimize the header size.
      */
-    size_t          firstFreeSpanOffsets;
+    CompactFreeSpan firstFreeSpan;
 
     /*
      * One of AllocKind constants or FINALIZE_LIMIT when the arena does not
      * contain any GC things and is on the list of empty arenas in the GC
      * chunk. The latter allows to quickly check if the arena is allocated
      * during the conservative GC scanning without searching the arena in the
      * list.
      *
@@ -458,18 +474,21 @@ struct ArenaHeader : public JS::shadow::
         JS_ASSERT(!markOverflow);
         JS_ASSERT(!allocatedDuringIncremental);
         JS_ASSERT(!hasDelayedMarking);
         zone = zoneArg;
 
         static_assert(FINALIZE_LIMIT <= 255, "We must be able to fit the allockind into uint8_t.");
         allocKind = size_t(kind);
 
-        /* The arena is initially marked as full; see allocateFromArenaInline(). */
-        firstFreeSpanOffsets = FreeSpan::FullArenaOffsets;
+        /*
+         * The firstFreeSpan is initially marked as empty (and thus the arena
+         * is marked as full). See allocateFromArenaInline().
+         */
+        firstFreeSpan.initAsEmpty();
     }
 
     void setAsNotAllocated() {
         allocKind = size_t(FINALIZE_LIMIT);
         markOverflow = 0;
         allocatedDuringIncremental = 0;
         hasDelayedMarking = 0;
         auxNextLink = 0;
@@ -481,23 +500,23 @@ struct ArenaHeader : public JS::shadow::
     AllocKind getAllocKind() const {
         JS_ASSERT(allocated());
         return AllocKind(allocKind);
     }
 
     inline size_t getThingSize() const;
 
     bool hasFreeThings() const {
-        return firstFreeSpanOffsets != FreeSpan::FullArenaOffsets;
+        return !firstFreeSpan.isEmpty();
     }
 
     inline bool isEmpty() const;
 
     void setAsFullyUsed() {
-        firstFreeSpanOffsets = FreeSpan::FullArenaOffsets;
+        firstFreeSpan.initAsEmpty();
     }
 
     inline FreeSpan getFirstFreeSpan() const;
     inline void setFirstFreeSpan(const FreeSpan *span);
 
 #ifdef DEBUG
     void checkSynchronizedWithFreeList() const;
 #endif
@@ -895,33 +914,34 @@ ArenaHeader::getArena()
 
 inline bool
 ArenaHeader::isEmpty() const
 {
     /* Arena is empty if its first span covers the whole arena. */
     JS_ASSERT(allocated());
     size_t firstThingOffset = Arena::firstThingOffset(getAllocKind());
     size_t lastThingOffset = ArenaSize - getThingSize();
-    return firstFreeSpanOffsets == FreeSpan::encodeOffsets(firstThingOffset, lastThingOffset);
+    const CompactFreeSpan emptyCompactSpan(firstThingOffset, lastThingOffset);
+    return firstFreeSpan == emptyCompactSpan;
 }
 
 FreeSpan
 ArenaHeader::getFirstFreeSpan() const
 {
 #ifdef DEBUG
     checkSynchronizedWithFreeList();
 #endif
-    return FreeSpan::decodeOffsets(arenaAddress(), firstFreeSpanOffsets);
+    return firstFreeSpan.decompact(arenaAddress());
 }
 
 void
 ArenaHeader::setFirstFreeSpan(const FreeSpan *span)
 {
     JS_ASSERT_IF(!span->isEmpty(), span->isWithinArena(arenaAddress()));
-    firstFreeSpanOffsets = span->encodeAsOffsets();
+    firstFreeSpan.compact(*span);
 }
 
 inline ArenaHeader *
 ArenaHeader::getNextDelayedMarking() const
 {
     JS_ASSERT(hasDelayedMarking);
     return &reinterpret_cast<Arena *>(auxNextLink << ArenaShift)->aheader;
 }
--- a/js/src/jsgc.cpp
+++ b/js/src/jsgc.cpp
@@ -407,17 +407,17 @@ ArenaHeader::checkSynchronizedWithFreeLi
     /*
      * We can be called from the background finalization thread when the free
      * list in the zone can mutate at any moment. We cannot do any
      * checks in this case.
      */
     if (IsBackgroundFinalized(getAllocKind()) && zone->runtimeFromAnyThread()->gc.helperThread.onBackgroundThread())
         return;
 
-    FreeSpan firstSpan = FreeSpan::decodeOffsets(arenaAddress(), firstFreeSpanOffsets);
+    FreeSpan firstSpan = firstFreeSpan.decompact(arenaAddress());
     if (firstSpan.isEmpty())
         return;
     const FreeList *freeList = zone->allocator.arenas.getFreeList(getAllocKind());
     if (freeList->isEmpty() || firstSpan.arenaAddress() != freeList->arenaAddress())
         return;
 
     /*
      * Here this arena has free things, FreeList::lists[thingKind] is not