Changeset 95895 in webkit


Ignore:
Timestamp:
Sep 23, 2011 7:07:58 PM (13 years ago)
Author:
fpizlo@apple.com
Message:

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.

(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:
Location:
trunk/Source/JavaScriptCore
Files:
1 added
7 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/ChangeLog

    r95894 r95895  
     12011-09-23  Filip Pizlo  <fpizlo@apple.com>
     2
     3        wtf/BitVector.h has a variety of bugs which manifest when the
     4        vector grows beyond 63 bits
     5        https://bugs.webkit.org/show_bug.cgi?id=68746
     6
     7        Reviewed by Oliver Hunt.
     8       
     9        Out-of-lined slow path code in BitVector so that not every user
     10        of CodeBlock ends up having to compile it. Fixed a variety of
     11        index computation and size computation bugs.
     12       
     13        I have not seen these issues manifest themselves, but they are
     14        blocking a patch that uses BitVector more aggressively.
     15
     16        * GNUmakefile.list.am:
     17        * JavaScriptCore.vcproj/WTF/WTF.vcproj:
     18        * JavaScriptCore.xcodeproj/project.pbxproj:
     19        * wtf/BitVector.cpp: Added.
     20        (BitVector::BitVector):
     21        (BitVector::operator=):
     22        (BitVector::resize):
     23        (BitVector::clearAll):
     24        (BitVector::OutOfLineBits::create):
     25        (BitVector::OutOfLineBits::destroy):
     26        (BitVector::resizeOutOfLine):
     27        * wtf/BitVector.h:
     28        (WTF::BitVector::ensureSize):
     29        (WTF::BitVector::get):
     30        (WTF::BitVector::set):
     31        (WTF::BitVector::clear):
     32        (WTF::BitVector::byteCount):
     33        (WTF::BitVector::OutOfLineBits::numWords):
     34        (WTF::BitVector::OutOfLineBits::bits):
     35        (WTF::BitVector::outOfLineBits):
     36        * wtf/CMakeLists.txt:
     37        * wtf/wtf.pri:
     38
    1392011-09-23  Adam Klein  <adamk@chromium.org>
    240

  • trunk/Source/JavaScriptCore/GNUmakefile.list.am

    r95751 r95895  
    469469        Source/JavaScriptCore/wtf/Atomics.h \
    470470        Source/JavaScriptCore/wtf/AVLTree.h \
     471        Source/JavaScriptCore/wtf/BitVector.cpp \
    471472        Source/JavaScriptCore/wtf/BitVector.h \
    472473        Source/JavaScriptCore/wtf/Bitmap.h \

  • trunk/Source/JavaScriptCore/JavaScriptCore.vcproj/WTF/WTF.vcproj

    r95681 r95895  
    638638                </File>
    639639                <File
     640                        RelativePath="..\..\wtf\BitVector.cpp"
     641                        >
     642                </File>
     643                <File
    640644                        RelativePath="..\..\wtf\BitVector.h"
    641645                        >

  • trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj

    r95872 r95895  
    5151                0BF28A2911A33DC300638F84 /* SizeLimits.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0BF28A2811A33DC300638F84 /* SizeLimits.cpp */; };
    5252                0F242DA713F3B1E8007ADD4C /* WeakReferenceHarvester.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F242DA513F3B1BB007ADD4C /* WeakReferenceHarvester.h */; settings = {ATTRIBUTES = (Private, ); }; };
     53                0F604E8B142D696D009CEB92 /* BitVector.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F604E8A142D6969009CEB92 /* BitVector.cpp */; };
    5354                0F7700921402FF3C0078EB39 /* SamplingCounter.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F7700911402FF280078EB39 /* SamplingCounter.cpp */; };
    5455                0F963B2713F753BB0002D9B2 /* RedBlackTree.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F963B2613F753990002D9B2 /* RedBlackTree.h */; settings = {ATTRIBUTES = (Private, ); }; };
    … …  
    794795                0BF28A2811A33DC300638F84 /* SizeLimits.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = SizeLimits.cpp; sourceTree = "<group>"; };
    795796                0F242DA513F3B1BB007ADD4C /* WeakReferenceHarvester.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = WeakReferenceHarvester.h; sourceTree = "<group>"; };
     797                0F604E8A142D6969009CEB92 /* BitVector.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = BitVector.cpp; sourceTree = "<group>"; };
    796798                0F77008E1402FDD60078EB39 /* SamplingCounter.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SamplingCounter.h; sourceTree = "<group>"; };
    797799                0F7700911402FF280078EB39 /* SamplingCounter.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = SamplingCounter.cpp; sourceTree = "<group>"; };
    … …  
    18131815                        isa = PBXGroup;
    18141816                        children = (
     1817                                0F604E8A142D6969009CEB92 /* BitVector.cpp */,
    18151818                                0FD82F491428069200179C94 /* BitVector.h */,
    18161819                                C22C524813FAF6EF00B7DC0D /* dtoa */,
    … …  
    33473350                                A70456B11427FB950037DA68 /* AllocationSpace.cpp in Sources */,
    33483351                                86FA9E91142BBB2E001773B7 /* JSBoundFunction.cpp in Sources */,
     3352                                0F604E8B142D696D009CEB92 /* BitVector.cpp in Sources */,
    33493353                        );
    33503354                        runOnlyForDeploymentPostprocessing = 0;

  • trunk/Source/JavaScriptCore/wtf/BitVector.h

    r95681 r95895  
    2727#define BitVector_h
    2828
    29 #include <algorithm>
    30 #include <string.h>
    3129#include <wtf/Assertions.h>
    32 #include <wtf/FastMalloc.h>
    3330#include <wtf/StdLibExtras.h>
    3431
    … …  
    6259    }
    6360   
    64     BitVector(const BitVector& other)
    65         : m_bitsOrPointer(makeInlineBits(0))
    66     {
    67         (*this) = other;
    68     }
     61    BitVector(const BitVector& other);
    6962   
    7063    ~BitVector()
    … …  
    7568    }
    7669   
    77     BitVector& operator=(const BitVector& other)
    78     {
    79         uintptr_t newBitsOrPointer;
    80         if (other.isInline())
    81             newBitsOrPointer = other.m_bitsOrPointer;
    82         else {
    83             OutOfLineBits* newOutOfLineBits = OutOfLineBits::create(other.size());
    84             memcpy(newOutOfLineBits->bits(), other.bits(), byteCount(other.size()));
    85             newBitsOrPointer = reinterpret_cast<uintptr_t>(newOutOfLineBits);
    86         }
    87         if (!isInline())
    88             OutOfLineBits::destroy(outOfLineBits());
    89         m_bitsOrPointer = newBitsOrPointer;
    90         return *this;
    91     }
     70    BitVector& operator=(const BitVector& other);
    9271
    9372    size_t size() const
    … …  
    10685   
    10786    // Like ensureSize(), but supports reducing the size of the bitvector.
    108     void resize(size_t numBits)
    109     {
    110         if (isInline())
    111             return;
    112        
    113         if (numBits <= maxInlineBits()) {
    114             OutOfLineBits* myOutOfLineBits = outOfLineBits();
    115             m_bitsOrPointer = makeInlineBits(*myOutOfLineBits->bits());
    116             OutOfLineBits::destroy(myOutOfLineBits);
    117             return;
    118         }
    119        
    120         resizeOutOfLine(numBits);
    121     }
     87    void resize(size_t numBits);
    12288   
    123     void clearAll()
    124     {
    125         if (isInline())
    126             m_bitsOrPointer = makeInlineBits(0);
    127         else
    128             memset(outOfLineBits()->bits(), 0, byteCount(size()));
    129     }
     89    void clearAll();
    13090
    13191    bool get(size_t bit) const
    13292    {
    13393        ASSERT(bit < size());
    134         return !!(bits()[bit >> bitsInPointer()] & (static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1))));
     94        return !!(bits()[bit / bitsInPointer()] & (static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1))));
    13595    }
    13696   
    … …  
    13898    {
    13999        ASSERT(bit < size());
    140         bits()[bit >> bitsInPointer()] |= (static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1)));
     100        bits()[bit / bitsInPointer()] |= (static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1)));
    141101    }
    142102   
    … …  
    144104    {
    145105        ASSERT(bit < size());
    146         bits()[bit >> bitsInPointer()] &= ~(static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1)));
     106        bits()[bit / bitsInPointer()] &= ~(static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1)));
    147107    }
    148108   
    … …  
    166126    }
    167127   
    168     // This function relies on bitCount being a multiple of bitsInPointer()
    169128    static size_t byteCount(size_t bitCount)
    170129    {
    171         ASSERT(!(bitCount & (bitsInPointer() - 1)));
    172         return bitCount >> 3;
     130        return (bitCount + 7) >> 3;
    173131    }
    174132   
    … …  
    182140    public:
    183141        size_t numBits() const { return m_numBits; }
    184         size_t numWords() const { return (m_numBits + bitsInPointer() - 1) >> bitsInPointer(); }
    185         uintptr_t* bits() { return reinterpret_cast<uintptr_t*>(this + 1); }
    186         const uintptr_t* bits() const { return reinterpret_cast<const uintptr_t*>(this + 1); }
     142        size_t numWords() const { return (m_numBits + bitsInPointer() - 1) / bitsInPointer(); }
     143        uintptr_t* bits() { return bitwise_cast<uintptr_t*>(this + 1); }
     144        const uintptr_t* bits() const { return bitwise_cast<const uintptr_t*>(this + 1); }
    187145       
    188         static OutOfLineBits* create(size_t numBits)
    189         {
    190             numBits = (numBits + bitsInPointer() - 1) & ~bitsInPointer();
    191             return new (fastMalloc(sizeof(OutOfLineBits) + (numBits >> bitsInPointer()))) OutOfLineBits(numBits);
    192         }
     146        static OutOfLineBits* create(size_t numBits);
    193147       
    194         static void destroy(OutOfLineBits* outOfLineBits)
    195         {
    196             fastFree(outOfLineBits);
    197         }
     148        static void destroy(OutOfLineBits*);
    198149
    199150    private:
    … …  
    208159    bool isInline() const { return m_bitsOrPointer >> maxInlineBits(); }
    209160   
    210     const OutOfLineBits* outOfLineBits() const { return reinterpret_cast<const OutOfLineBits*>(m_bitsOrPointer); }
    211     OutOfLineBits* outOfLineBits() { return reinterpret_cast<OutOfLineBits*>(m_bitsOrPointer); }
     161    const OutOfLineBits* outOfLineBits() const { return bitwise_cast<const OutOfLineBits*>(m_bitsOrPointer); }
     162    OutOfLineBits* outOfLineBits() { return bitwise_cast<OutOfLineBits*>(m_bitsOrPointer); }
    212163   
    213     void resizeOutOfLine(size_t numBits)
    214     {
    215         ASSERT(numBits > maxInlineBits());
    216         OutOfLineBits* newOutOfLineBits = OutOfLineBits::create(numBits);
    217         memcpy(newOutOfLineBits->bits(), bits(), byteCount(std::min(size(), numBits)));
    218         if (!isInline())
    219             OutOfLineBits::destroy(outOfLineBits());
    220         m_bitsOrPointer = reinterpret_cast<uintptr_t>(newOutOfLineBits);
    221     }
     164    void resizeOutOfLine(size_t numBits);
    222165   
    223166    uintptr_t* bits()

  • trunk/Source/JavaScriptCore/wtf/CMakeLists.txt

    r95140 r95895  
    66    Assertions.h
    77    Atomics.h
     8    BitVector.h
    89    Bitmap.h
    910    BoundsCheckedPointer.h

  • trunk/Source/JavaScriptCore/wtf/wtf.pri

    r94920 r95895  
    33SOURCES += \
    44    wtf/Assertions.cpp \
     5    wtf/BitVector.cpp \
    56    wtf/ByteArray.cpp \
    67    wtf/CryptographicallyRandomNumber.cpp \
Note: See TracChangeset for help on using the changeset viewer.