bmalloc: free up a bit in BoundaryTag
authorggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 26 Feb 2015 19:30:11 +0000 (19:30 +0000)
committerggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 26 Feb 2015 19:30:11 +0000 (19:30 +0000)
https://bugs.webkit.org/show_bug.cgi?id=142048

Reviewed by Brady Eidson.

We were wasting a bit by accident, and I need one now.

* bmalloc/Algorithm.h:
(bmalloc::rightShift): Deleted. Not needed, now that I've simplified
the math.

* bmalloc/BoundaryTag.h: Since each boundary tag bucket is 1024 bytes
long, the maximum offset into a bucket is 1023.

You need 5 bits to count up to 1024, but only 4 to count up to 1023.

Math is hard.

(bmalloc::BoundaryTag::compactBegin): Switched to division because it
is simpler, and easier to match up with our ASSERT. The compiler will
turn division by constant power of two into a shift for us.

(bmalloc::BoundaryTag::setRange): Added an ASSERT for compactBegin
because we do encode it, so we should ASSERT that encoding did not
lose information.

* bmalloc/Sizes.h: Shifting is no longer used since we use division
instead.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@180688 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/bmalloc/ChangeLog
Source/bmalloc/bmalloc/Algorithm.h
Source/bmalloc/bmalloc/BoundaryTag.h
Source/bmalloc/bmalloc/Sizes.h

index 4fb2e73..1c75721 100644 (file)
@@ -1,3 +1,34 @@
+2015-02-26  Geoffrey Garen  <ggaren@apple.com>
+
+        bmalloc: free up a bit in BoundaryTag
+        https://bugs.webkit.org/show_bug.cgi?id=142048
+
+        Reviewed by Brady Eidson.
+
+        We were wasting a bit by accident, and I need one now.
+
+        * bmalloc/Algorithm.h:
+        (bmalloc::rightShift): Deleted. Not needed, now that I've simplified
+        the math.
+
+        * bmalloc/BoundaryTag.h: Since each boundary tag bucket is 1024 bytes
+        long, the maximum offset into a bucket is 1023.
+
+        You need 5 bits to count up to 1024, but only 4 to count up to 1023.
+        
+        Math is hard.
+
+        (bmalloc::BoundaryTag::compactBegin): Switched to division because it
+        is simpler, and easier to match up with our ASSERT. The compiler will
+        turn division by constant power of two into a shift for us.
+
+        (bmalloc::BoundaryTag::setRange): Added an ASSERT for compactBegin
+        because we do encode it, so we should ASSERT that encoding did not
+        lose information.
+
+        * bmalloc/Sizes.h: Shifting is no longer used since we use division
+        instead.
+
 2015-02-24  Stephanie Lewis  <slewis@apple.com>
 
         Rolling out http://trac.webkit.org/changeset/180430 as it causes the PLT to crash.
index fdf31b0..269866c 100644 (file)
@@ -53,11 +53,6 @@ template<typename T> inline constexpr T mask(T value, uintptr_t mask)
     return reinterpret_cast<T>(reinterpret_cast<uintptr_t>(value) & mask);
 }
 
-template<typename T> inline constexpr T rightShift(T value, uintptr_t shift)
-{
-    return reinterpret_cast<T>(reinterpret_cast<uintptr_t>(value) >> shift);
-}
-
 template<typename T> inline constexpr bool test(T value, uintptr_t mask)
 {
     return !!(reinterpret_cast<uintptr_t>(value) & mask);
index 9cc11c3..c51c956 100644 (file)
@@ -68,11 +68,16 @@ public:
 
 private:
     static const size_t flagBits = 3;
-    static const size_t compactBeginBits = 5;
+    static const size_t compactBeginBits = 4;
     static const size_t sizeBits = bitCount<unsigned>() - flagBits - compactBeginBits;
 
-    static_assert((1 << compactBeginBits) - 1 >= largeMin / largeAlignment, "compactBegin must be encodable in a BoundaryTag.");
-    static_assert((1 << sizeBits) - 1 >= largeMax, "largeMax must be encodable in a BoundaryTag.");
+    static_assert(
+        (1 << compactBeginBits) - 1 >= (largeMin - 1) / largeAlignment,
+        "compactBegin must be encodable in a BoundaryTag.");
+
+    static_assert(
+        (1 << sizeBits) - 1 >= largeMax,
+        "largeMax must be encodable in a BoundaryTag.");
 
     bool m_isFree: 1;
     bool m_isEnd: 1;
@@ -84,14 +89,14 @@ private:
 inline unsigned BoundaryTag::compactBegin(void* object)
 {
     return static_cast<unsigned>(
-        reinterpret_cast<uintptr_t>(
-            rightShift(
-                mask(object, largeMin - 1), largeAlignmentShift)));
+        reinterpret_cast<uintptr_t>(mask(object, largeMin - 1)) / largeAlignment);
 }
 
 inline void BoundaryTag::setRange(const Range& range)
 {
     m_compactBegin = compactBegin(range.begin());
+    BASSERT(this->compactBegin() == compactBegin(range.begin()));
+
     m_size = static_cast<unsigned>(range.size());
     BASSERT(this->size() == range.size());
 }
index 9bc59b3..fadca77 100644 (file)
@@ -76,8 +76,6 @@ namespace Sizes {
     static const size_t largeChunkMask = ~(largeChunkSize - 1ul);
 
     static const size_t largeAlignment = 64;
-    static const size_t largeAlignmentShift = 6;
-    static_assert(1 << largeAlignmentShift == largeAlignment, "largeAlignmentShift be log2(largeAlignment).");
     static const size_t largeMax = largeChunkSize * 99 / 100; // Plenty of room for metadata.
     static const size_t largeMin = mediumMax;