wtf/BitVector.h has a variety of bugs which manifest when the
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 24 Sep 2011 02:07:58 +0000 (02:07 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 24 Sep 2011 02:07:58 +0000 (02:07 +0000)
vector grows beyond 63 bits
https://bugs.webkit.org/show_bug.cgi?id=68746

Reviewed by Oliver Hunt.

Out-of-lined slow path code in BitVector so that not every user
of CodeBlock ends up having to compile it. Fixed a variety of
index computation and size computation bugs.

I have not seen these issues manifest themselves, but they are
blocking a patch that uses BitVector more aggressively.

* GNUmakefile.list.am:
* JavaScriptCore.vcproj/WTF/WTF.vcproj:
* JavaScriptCore.xcodeproj/project.pbxproj:
* wtf/BitVector.cpp: Added.
(BitVector::BitVector):
(BitVector::operator=):
(BitVector::resize):
(BitVector::clearAll):
(BitVector::OutOfLineBits::create):
(BitVector::OutOfLineBits::destroy):
(BitVector::resizeOutOfLine):
* wtf/BitVector.h:
(WTF::BitVector::ensureSize):
(WTF::BitVector::get):
(WTF::BitVector::set):
(WTF::BitVector::clear):
(WTF::BitVector::byteCount):
(WTF::BitVector::OutOfLineBits::numWords):
(WTF::BitVector::OutOfLineBits::bits):
(WTF::BitVector::outOfLineBits):
* wtf/CMakeLists.txt:
* wtf/wtf.pri:

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

Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/GNUmakefile.list.am
Source/JavaScriptCore/JavaScriptCore.vcproj/WTF/WTF.vcproj
Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
Source/JavaScriptCore/wtf/BitVector.cpp [new file with mode: 0644]
Source/JavaScriptCore/wtf/BitVector.h
Source/JavaScriptCore/wtf/CMakeLists.txt
Source/JavaScriptCore/wtf/wtf.pri

index a94ae7f..10b531d 100644 (file)
@@ -1,3 +1,41 @@
+2011-09-23  Filip Pizlo  <fpizlo@apple.com>
+
+        wtf/BitVector.h has a variety of bugs which manifest when the
+        vector grows beyond 63 bits
+        https://bugs.webkit.org/show_bug.cgi?id=68746
+
+        Reviewed by Oliver Hunt.
+        
+        Out-of-lined slow path code in BitVector so that not every user
+        of CodeBlock ends up having to compile it. Fixed a variety of
+        index computation and size computation bugs.
+        
+        I have not seen these issues manifest themselves, but they are
+        blocking a patch that uses BitVector more aggressively.
+
+        * GNUmakefile.list.am:
+        * JavaScriptCore.vcproj/WTF/WTF.vcproj:
+        * JavaScriptCore.xcodeproj/project.pbxproj:
+        * wtf/BitVector.cpp: Added.
+        (BitVector::BitVector):
+        (BitVector::operator=):
+        (BitVector::resize):
+        (BitVector::clearAll):
+        (BitVector::OutOfLineBits::create):
+        (BitVector::OutOfLineBits::destroy):
+        (BitVector::resizeOutOfLine):
+        * wtf/BitVector.h:
+        (WTF::BitVector::ensureSize):
+        (WTF::BitVector::get):
+        (WTF::BitVector::set):
+        (WTF::BitVector::clear):
+        (WTF::BitVector::byteCount):
+        (WTF::BitVector::OutOfLineBits::numWords):
+        (WTF::BitVector::OutOfLineBits::bits):
+        (WTF::BitVector::outOfLineBits):
+        * wtf/CMakeLists.txt:
+        * wtf/wtf.pri:
+
 2011-09-23  Adam Klein  <adamk@chromium.org>
 
         Add ENABLE_MUTATION_OBSERVERS feature flag
index fe2f150..1a4497a 100644 (file)
@@ -468,6 +468,7 @@ javascriptcore_sources += \
        Source/JavaScriptCore/wtf/Assertions.h \
        Source/JavaScriptCore/wtf/Atomics.h \
        Source/JavaScriptCore/wtf/AVLTree.h \
+       Source/JavaScriptCore/wtf/BitVector.cpp \
        Source/JavaScriptCore/wtf/BitVector.h \
        Source/JavaScriptCore/wtf/Bitmap.h \
        Source/JavaScriptCore/wtf/BlockStack.h \
index a1b1d57..650eade 100644 (file)
                        >
                </File>
                <File
+                       RelativePath="..\..\wtf\BitVector.cpp"
+                       >
+               </File>
+               <File
                        RelativePath="..\..\wtf\BitVector.h"
                        >
                </File>
index 2e739cf..c165753 100644 (file)
@@ -50,6 +50,7 @@
                0BDFFAE10FC6193100D69EF4 /* OwnFastMallocPtr.h in Headers */ = {isa = PBXBuildFile; fileRef = 0BDFFAD10FC616EC00D69EF4 /* OwnFastMallocPtr.h */; settings = {ATTRIBUTES = (Private, ); }; };
                0BF28A2911A33DC300638F84 /* SizeLimits.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0BF28A2811A33DC300638F84 /* SizeLimits.cpp */; };
                0F242DA713F3B1E8007ADD4C /* WeakReferenceHarvester.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F242DA513F3B1BB007ADD4C /* WeakReferenceHarvester.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               0F604E8B142D696D009CEB92 /* BitVector.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F604E8A142D6969009CEB92 /* BitVector.cpp */; };
                0F7700921402FF3C0078EB39 /* SamplingCounter.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F7700911402FF280078EB39 /* SamplingCounter.cpp */; };
                0F963B2713F753BB0002D9B2 /* RedBlackTree.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F963B2613F753990002D9B2 /* RedBlackTree.h */; settings = {ATTRIBUTES = (Private, ); }; };
                0F963B2C13F853EC0002D9B2 /* MetaAllocator.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F963B2B13F853C70002D9B2 /* MetaAllocator.cpp */; settings = {COMPILER_FLAGS = "-fno-strict-aliasing"; }; };
                0BDFFAD40FC6171000D69EF4 /* CrossThreadRefCounted.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CrossThreadRefCounted.h; sourceTree = "<group>"; };
                0BF28A2811A33DC300638F84 /* SizeLimits.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = SizeLimits.cpp; sourceTree = "<group>"; };
                0F242DA513F3B1BB007ADD4C /* WeakReferenceHarvester.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = WeakReferenceHarvester.h; sourceTree = "<group>"; };
+               0F604E8A142D6969009CEB92 /* BitVector.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = BitVector.cpp; sourceTree = "<group>"; };
                0F77008E1402FDD60078EB39 /* SamplingCounter.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SamplingCounter.h; sourceTree = "<group>"; };
                0F7700911402FF280078EB39 /* SamplingCounter.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = SamplingCounter.cpp; sourceTree = "<group>"; };
                0F963B2613F753990002D9B2 /* RedBlackTree.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = RedBlackTree.h; sourceTree = "<group>"; };
                65162EF108E6A21C007556CD /* wtf */ = {
                        isa = PBXGroup;
                        children = (
+                               0F604E8A142D6969009CEB92 /* BitVector.cpp */,
                                0FD82F491428069200179C94 /* BitVector.h */,
                                C22C524813FAF6EF00B7DC0D /* dtoa */,
                                06D358A00DAAD9C4003B174E /* mac */,
                                1A082779142168D70090CCAC /* BinarySemaphore.cpp in Sources */,
                                A70456B11427FB950037DA68 /* AllocationSpace.cpp in Sources */,
                                86FA9E91142BBB2E001773B7 /* JSBoundFunction.cpp in Sources */,
+                               0F604E8B142D696D009CEB92 /* BitVector.cpp in Sources */,
                        );
                        runOnlyForDeploymentPostprocessing = 0;
                };
diff --git a/Source/JavaScriptCore/wtf/BitVector.cpp b/Source/JavaScriptCore/wtf/BitVector.cpp
new file mode 100644 (file)
index 0000000..16c637a
--- /dev/null
@@ -0,0 +1,102 @@
+/*
+ * Copyright (C) 2011 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#include "config.h"
+#include "BitVector.h"
+
+#include <algorithm>
+#include <string.h>
+#include <wtf/Assertions.h>
+#include <wtf/FastMalloc.h>
+#include <wtf/StdLibExtras.h>
+
+BitVector::BitVector(const BitVector& other)
+    : m_bitsOrPointer(makeInlineBits(0))
+{
+    (*this) = other;
+}
+
+BitVector& BitVector::operator=(const BitVector& other)
+{
+    uintptr_t newBitsOrPointer;
+    if (other.isInline())
+        newBitsOrPointer = other.m_bitsOrPointer;
+    else {
+        OutOfLineBits* newOutOfLineBits = OutOfLineBits::create(other.size());
+        memcpy(newOutOfLineBits->bits(), other.bits(), byteCount(other.size()));
+        newBitsOrPointer = bitwise_cast<uintptr_t>(newOutOfLineBits);
+    }
+    if (!isInline())
+        OutOfLineBits::destroy(outOfLineBits());
+    m_bitsOrPointer = newBitsOrPointer;
+    return *this;
+}
+
+void BitVector::resize(size_t numBits)
+{
+    if (numBits <= maxInlineBits()) {
+        if (isInline())
+            return;
+    
+        OutOfLineBits* myOutOfLineBits = outOfLineBits();
+        m_bitsOrPointer = makeInlineBits(*myOutOfLineBits->bits());
+        OutOfLineBits::destroy(myOutOfLineBits);
+        return;
+    }
+    
+    resizeOutOfLine(numBits);
+}
+
+void BitVector::clearAll()
+{
+    if (isInline())
+        m_bitsOrPointer = makeInlineBits(0);
+    else
+        memset(outOfLineBits()->bits(), 0, byteCount(size()));
+}
+
+BitVector::OutOfLineBits* BitVector::OutOfLineBits::create(size_t numBits)
+{
+    numBits = (numBits + bitsInPointer() - 1) & ~(bitsInPointer() - 1);
+    size_t size = sizeof(OutOfLineBits) + sizeof(uintptr_t) * (numBits / bitsInPointer());
+    OutOfLineBits* result = new (fastMalloc(size)) OutOfLineBits(numBits);
+    return result;
+}
+
+void BitVector::OutOfLineBits::destroy(OutOfLineBits* outOfLineBits)
+{
+    fastFree(outOfLineBits);
+}
+
+void BitVector::resizeOutOfLine(size_t numBits)
+{
+    ASSERT(numBits > maxInlineBits());
+    OutOfLineBits* newOutOfLineBits = OutOfLineBits::create(numBits);
+    memcpy(newOutOfLineBits->bits(), bits(), byteCount(std::min(size(), numBits)));
+    if (!isInline())
+        OutOfLineBits::destroy(outOfLineBits());
+    m_bitsOrPointer = bitwise_cast<uintptr_t>(newOutOfLineBits);
+}
+
index b5df415..cc0a6a5 100644 (file)
 #ifndef BitVector_h
 #define BitVector_h
 
-#include <algorithm>
-#include <string.h>
 #include <wtf/Assertions.h>
-#include <wtf/FastMalloc.h>
 #include <wtf/StdLibExtras.h>
 
 namespace WTF {
@@ -61,11 +58,7 @@ public:
     {
     }
     
-    BitVector(const BitVector& other)
-        : m_bitsOrPointer(makeInlineBits(0))
-    {
-        (*this) = other;
-    }
+    BitVector(const BitVector& other);
     
     ~BitVector()
     {
@@ -74,21 +67,7 @@ public:
         OutOfLineBits::destroy(outOfLineBits());
     }
     
-    BitVector& operator=(const BitVector& other)
-    {
-        uintptr_t newBitsOrPointer;
-        if (other.isInline())
-            newBitsOrPointer = other.m_bitsOrPointer;
-        else {
-            OutOfLineBits* newOutOfLineBits = OutOfLineBits::create(other.size());
-            memcpy(newOutOfLineBits->bits(), other.bits(), byteCount(other.size()));
-            newBitsOrPointer = reinterpret_cast<uintptr_t>(newOutOfLineBits);
-        }
-        if (!isInline())
-            OutOfLineBits::destroy(outOfLineBits());
-        m_bitsOrPointer = newBitsOrPointer;
-        return *this;
-    }
+    BitVector& operator=(const BitVector& other);
 
     size_t size() const
     {
@@ -105,45 +84,26 @@ public:
     }
     
     // Like ensureSize(), but supports reducing the size of the bitvector.
-    void resize(size_t numBits)
-    {
-        if (isInline())
-            return;
-        
-        if (numBits <= maxInlineBits()) {
-            OutOfLineBits* myOutOfLineBits = outOfLineBits();
-            m_bitsOrPointer = makeInlineBits(*myOutOfLineBits->bits());
-            OutOfLineBits::destroy(myOutOfLineBits);
-            return;
-        }
-        
-        resizeOutOfLine(numBits);
-    }
+    void resize(size_t numBits);
     
-    void clearAll()
-    {
-        if (isInline())
-            m_bitsOrPointer = makeInlineBits(0);
-        else
-            memset(outOfLineBits()->bits(), 0, byteCount(size()));
-    }
+    void clearAll();
 
     bool get(size_t bit) const
     {
         ASSERT(bit < size());
-        return !!(bits()[bit >> bitsInPointer()] & (static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1))));
+        return !!(bits()[bit / bitsInPointer()] & (static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1))));
     }
     
     void set(size_t bit)
     {
         ASSERT(bit < size());
-        bits()[bit >> bitsInPointer()] |= (static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1)));
+        bits()[bit / bitsInPointer()] |= (static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1)));
     }
     
     void clear(size_t bit)
     {
         ASSERT(bit < size());
-        bits()[bit >> bitsInPointer()] &= ~(static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1)));
+        bits()[bit / bitsInPointer()] &= ~(static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1)));
     }
     
     void set(size_t bit, bool value)
@@ -165,11 +125,9 @@ private:
         return bitsInPointer() - 1;
     }
     
-    // This function relies on bitCount being a multiple of bitsInPointer()
     static size_t byteCount(size_t bitCount)
     {
-        ASSERT(!(bitCount & (bitsInPointer() - 1)));
-        return bitCount >> 3;
+        return (bitCount + 7) >> 3;
     }
     
     static uintptr_t makeInlineBits(uintptr_t bits)
@@ -181,20 +139,13 @@ private:
     class OutOfLineBits {
     public:
         size_t numBits() const { return m_numBits; }
-        size_t numWords() const { return (m_numBits + bitsInPointer() - 1) >> bitsInPointer(); }
-        uintptr_t* bits() { return reinterpret_cast<uintptr_t*>(this + 1); }
-        const uintptr_t* bits() const { return reinterpret_cast<const uintptr_t*>(this + 1); }
+        size_t numWords() const { return (m_numBits + bitsInPointer() - 1) / bitsInPointer(); }
+        uintptr_t* bits() { return bitwise_cast<uintptr_t*>(this + 1); }
+        const uintptr_t* bits() const { return bitwise_cast<const uintptr_t*>(this + 1); }
         
-        static OutOfLineBits* create(size_t numBits)
-        {
-            numBits = (numBits + bitsInPointer() - 1) & ~bitsInPointer();
-            return new (fastMalloc(sizeof(OutOfLineBits) + (numBits >> bitsInPointer()))) OutOfLineBits(numBits);
-        }
+        static OutOfLineBits* create(size_t numBits);
         
-        static void destroy(OutOfLineBits* outOfLineBits)
-        {
-            fastFree(outOfLineBits);
-        }
+        static void destroy(OutOfLineBits*);
 
     private:
         OutOfLineBits(size_t numBits)
@@ -207,18 +158,10 @@ private:
     
     bool isInline() const { return m_bitsOrPointer >> maxInlineBits(); }
     
-    const OutOfLineBits* outOfLineBits() const { return reinterpret_cast<const OutOfLineBits*>(m_bitsOrPointer); }
-    OutOfLineBits* outOfLineBits() { return reinterpret_cast<OutOfLineBits*>(m_bitsOrPointer); }
+    const OutOfLineBits* outOfLineBits() const { return bitwise_cast<const OutOfLineBits*>(m_bitsOrPointer); }
+    OutOfLineBits* outOfLineBits() { return bitwise_cast<OutOfLineBits*>(m_bitsOrPointer); }
     
-    void resizeOutOfLine(size_t numBits)
-    {
-        ASSERT(numBits > maxInlineBits());
-        OutOfLineBits* newOutOfLineBits = OutOfLineBits::create(numBits);
-        memcpy(newOutOfLineBits->bits(), bits(), byteCount(std::min(size(), numBits)));
-        if (!isInline())
-            OutOfLineBits::destroy(outOfLineBits());
-        m_bitsOrPointer = reinterpret_cast<uintptr_t>(newOutOfLineBits);
-    }
+    void resizeOutOfLine(size_t numBits);
     
     uintptr_t* bits()
     {
index 3bf8a1c..d9374af 100644 (file)
@@ -5,6 +5,7 @@ SET(WTF_HEADERS
     AlwaysInline.h
     Assertions.h
     Atomics.h
+    BitVector.h
     Bitmap.h
     BoundsCheckedPointer.h
     BumpPointerAllocator.h
index be94abd..90096f0 100644 (file)
@@ -2,6 +2,7 @@
 
 SOURCES += \
     wtf/Assertions.cpp \
+    wtf/BitVector.cpp \
     wtf/ByteArray.cpp \
     wtf/CryptographicallyRandomNumber.cpp \
     wtf/CurrentTime.cpp \