Ignore:
Timestamp:
Feb 16, 2010, 4:01:58 PM (15 years ago)
Author:
[email protected]
Message:

​https://bugs.webkit.org/show_bug.cgi?id=34964
Leaks tool reports false memory leaks due to Rope implementation.

Reviewed by Oliver Hunt.

JavaScriptCore:

A rope is a recursive data structure where each node in the rope holds a set of
pointers, each of which may reference either a string (in UStringImpl form) or
another rope node. A low bit in each pointer is used to distinguish between
rope & string elements, in a fashion similar to the recently-removed
PtrAndFlags class (see ​https://bugs.webkit.org/show_bug.cgi?id=33731 ). Again,
this causes a problem for Leaks – refactor to remove the magic pointer
mangling.

Move Rope out from JSString.h and rename to URopeImpl, to match UStringImpl.
Give UStringImpl and URopeImpl a common parent class, UStringOrRopeImpl.
Repurpose an otherwise invalid permutation to flags (static & should report
memory cost) to identify ropes.

This allows us to change the rope's fibers to interrogate the object rather
than storing a bool within the low bits of the pointer (or in some cases the
use of a common parent class removes the need to determine the type at all -
there is a common interface to ref or get the length of either ropes or strings).

  • API/JSClassRef.cpp:

(OpaqueJSClass::OpaqueJSClass):
(OpaqueJSClassContextData::OpaqueJSClassContextData):

  • bytecompiler/BytecodeGenerator.cpp:

(JSC::keyForCharacterSwitch):

  • interpreter/Interpreter.cpp:

(JSC::Interpreter::privateExecute):

  • jit/JITStubs.cpp:

(JSC::DEFINE_STUB_FUNCTION):

  • runtime/ArrayPrototype.cpp:

(JSC::arrayProtoFuncToString):

  • runtime/Identifier.cpp:

(JSC::Identifier::equal):
(JSC::Identifier::addSlowCase):

  • runtime/JSString.cpp:

(JSC::JSString::resolveRope):

  • runtime/JSString.h:

(JSC::):
(JSC::RopeBuilder::JSString):
(JSC::RopeBuilder::~JSString):
(JSC::RopeBuilder::appendStringInConstruct):
(JSC::RopeBuilder::appendValueInConstructAndIncrementLength):
(JSC::RopeBuilder::JSStringFinalizerStruct::JSStringFinalizerStruct):
(JSC::RopeBuilder::JSStringFinalizerStruct::):

  • runtime/UString.cpp:

(JSC::UString::toStrictUInt32):
(JSC::equal):

  • runtime/UString.h:

(JSC::UString::isEmpty):
(JSC::UString::size):

  • runtime/UStringImpl.cpp:

(JSC::URopeImpl::derefFibersNonRecursive):
(JSC::URopeImpl::destructNonRecursive):

  • runtime/UStringImpl.h:

(JSC::UStringOrRopeImpl::isRope):
(JSC::UStringOrRopeImpl::length):
(JSC::UStringOrRopeImpl::ref):
(JSC::UStringOrRopeImpl::):
(JSC::UStringOrRopeImpl::operator new):
(JSC::UStringOrRopeImpl::UStringOrRopeImpl):
(JSC::UStringImpl::adopt):
(JSC::UStringImpl::createUninitialized):
(JSC::UStringImpl::tryCreateUninitialized):
(JSC::UStringImpl::data):
(JSC::UStringImpl::cost):
(JSC::UStringImpl::deref):
(JSC::UStringImpl::UStringImpl):
(JSC::UStringImpl::):
(JSC::URopeImpl::tryCreateUninitialized):
(JSC::URopeImpl::initializeFiber):
(JSC::URopeImpl::fiberCount):
(JSC::URopeImpl::fibers):
(JSC::URopeImpl::deref):
(JSC::URopeImpl::URopeImpl):
(JSC::URopeImpl::hasOneRef):
(JSC::UStringOrRopeImpl::deref):

WebCore:

Renamed cUStringImpl::size() to UStringImpl::size()UStringImpl::length()
(matches WebCore::StringImpl).

  • bridge/jni/jsc/JavaStringJSC.h:

(JSC::Bindings::JavaStringImpl::length):

  • platform/text/AtomicString.cpp:

(WebCore::AtomicString::add):
(WebCore::AtomicString::find):

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/JavaScriptCore/runtime/UStringImpl.h

    r54789 r54843  
    4141typedef CrossThreadRefCounted<OwnFastMallocPtr<UChar> > SharedUChar;
    4242
    43 class UStringImpl : Noncopyable {
     43class UStringOrRopeImpl : public Noncopyable {
     44public:
     45    bool isRope() { return (m_refCountAndFlags & s_refCountIsRope) == s_refCountIsRope; }
     46    unsigned length() const { return m_length; }
     47
     48    void ref() { m_refCountAndFlags += s_refCountIncrement; }
     49    inline void deref();
     50
     51protected:
     52    enum BufferOwnership {
     53        BufferInternal,
     54        BufferOwned,
     55        BufferSubstring,
     56        BufferShared,
     57    };
     58
     59    using Noncopyable::operator new;
     60    void* operator new(size_t, void* inPlace) { return inPlace; }
     61
     62    // For SmallStringStorage, which allocates an array and uses an in-place new.
     63    UStringOrRopeImpl() { }
     64
     65    UStringOrRopeImpl(unsigned length, BufferOwnership ownership)
     66        : m_refCountAndFlags(s_refCountIncrement | s_refCountFlagShouldReportedCost | ownership)
     67        , m_length(length)
     68    {
     69        ASSERT(!isRope());
     70    }
     71
     72    enum StaticStringConstructType { ConstructStaticString };
     73    UStringOrRopeImpl(unsigned length, StaticStringConstructType)
     74        : m_refCountAndFlags(s_refCountFlagStatic | BufferOwned)
     75        , m_length(length)
     76    {
     77        ASSERT(!isRope());
     78    }
     79
     80    enum RopeConstructType { ConstructRope };
     81    UStringOrRopeImpl(RopeConstructType)
     82        : m_refCountAndFlags(s_refCountIncrement | s_refCountIsRope)
     83        , m_length(0)
     84    {
     85        ASSERT(isRope());
     86    }
     87
     88    // The bottom 5 bits hold flags, the top 27 bits hold the ref count.
     89    // When dereferencing UStringImpls we check for the ref count AND the
     90    // static bit both being zero - static strings are never deleted.
     91    static const unsigned s_refCountMask = 0xFFFFFFE0;
     92    static const unsigned s_refCountIncrement = 0x20;
     93    static const unsigned s_refCountFlagStatic = 0x10;
     94    static const unsigned s_refCountFlagShouldReportedCost = 0x8;
     95    static const unsigned s_refCountFlagIsIdentifier = 0x4;
     96    static const unsigned s_refCountMaskBufferOwnership = 0x3;
     97    // Use an otherwise invalid permutation of flags (static & shouldReportedCost -
     98    // static strings do not set shouldReportedCost in the constructor, and this bit
     99    // is only ever cleared, not set) to identify objects that are ropes.
     100    static const unsigned s_refCountIsRope = s_refCountFlagStatic | s_refCountFlagShouldReportedCost;
     101
     102    unsigned m_refCountAndFlags;
     103    unsigned m_length;
     104};
     105
     106class UStringImpl : public UStringOrRopeImpl {
    44107public:
    45108    template<size_t inlineCapacity>
    … …  
    48111        if (unsigned length = vector.size()) {
    49112            ASSERT(vector.data());
    50             return adoptRef(new UStringImpl(vector.releaseBuffer(), length, BufferOwned));
     113            return adoptRef(new UStringImpl(vector.releaseBuffer(), length));
    51114        }
    52115        return &empty();
    … …  
    80143        UStringImpl* resultImpl = static_cast<UStringImpl*>(fastMalloc(sizeof(UChar) * length + sizeof(UStringImpl)));
    81144        output = reinterpret_cast<UChar*>(resultImpl + 1);
    82         return adoptRef(new(resultImpl) UStringImpl(output, length, BufferInternal));
     145        return adoptRef(new(resultImpl) UStringImpl(length));
    83146    }
    84147
    … …  
    96159            return 0;
    97160        output = reinterpret_cast<UChar*>(resultImpl + 1);
    98         return adoptRef(new(resultImpl) UStringImpl(output, length, BufferInternal));
     161        return adoptRef(new(resultImpl) UStringImpl(length));
    99162    }
    100163
    101164    SharedUChar* sharedBuffer();
    102165    UChar* data() const { return m_data; }
    103     unsigned size() const { return m_length; }
    104166    size_t cost()
    105167    {
    … …  
    108170            return m_bufferSubstring->cost();
    109171
    110         if (m_refCountAndFlags & s_refCountFlagHasReportedCost)
    111             return 0;
    112         m_refCountAndFlags |= s_refCountFlagHasReportedCost;
    113         return m_length;
     172        if (m_refCountAndFlags & s_refCountFlagShouldReportedCost) {
     173            m_refCountAndFlags &= ~s_refCountFlagShouldReportedCost;
     174            return m_length;
     175        }
     176        return 0;
    114177    }
    115178    unsigned hash() const { if (!m_hash) m_hash = computeHash(data(), m_length); return m_hash; }
    … …  
    125188    }
    126189
    127     UStringImpl* ref() { m_refCountAndFlags += s_refCountIncrement; return this; }
    128     ALWAYS_INLINE void deref() { m_refCountAndFlags -= s_refCountIncrement; if (!(m_refCountAndFlags & s_refCountMask)) delete this; }
     190    ALWAYS_INLINE void deref() { m_refCountAndFlags -= s_refCountIncrement; if (!(m_refCountAndFlags & (s_refCountMask | s_refCountFlagStatic))) delete this; }
    129191
    130192    static void copyChars(UChar* destination, const UChar* source, unsigned numCharacters)
    … …  
    152214
    153215private:
    154     enum BufferOwnership {
    155         BufferInternal,
    156         BufferOwned,
    157         BufferSubstring,
    158         BufferShared,
    159     };
    160 
    161216    // For SmallStringStorage, which allocates an array and uses an in-place new.
    162217    UStringImpl() { }
    163218
    164     // Used to construct normal strings with an internal or external buffer.
    165     UStringImpl(UChar* data, unsigned length, BufferOwnership ownership)
    166         : m_data(data)
     219    // Used to construct normal strings with an internal buffer.
     220    UStringImpl(unsigned length)
     221        : UStringOrRopeImpl(length, BufferInternal)
     222        , m_data(reinterpret_cast<UChar*>(this + 1))
    167223        , m_buffer(0)
    168         , m_length(length)
    169         , m_refCountAndFlags(s_refCountIncrement | ownership)
    170         , m_hash(0)
    171     {
    172         ASSERT((ownership == BufferInternal) || (ownership == BufferOwned));
     224        , m_hash(0)
     225    {
     226        checkConsistency();
     227    }
     228
     229    // Used to construct normal strings with an external buffer.
     230    UStringImpl(UChar* data, unsigned length)
     231        : UStringOrRopeImpl(length, BufferOwned)
     232        , m_data(data)
     233        , m_buffer(0)
     234        , m_hash(0)
     235    {
    173236        checkConsistency();
    174237    }
    … …  
    177240    // This means that the static string will never be destroyed, which is important because
    178241    // static strings will be shared across threads & ref-counted in a non-threadsafe manner.
    179     enum StaticStringConstructType { ConstructStaticString };
    180242    UStringImpl(UChar* data, unsigned length, StaticStringConstructType)
    181         : m_data(data)
     243        : UStringOrRopeImpl(length, ConstructStaticString)
     244        , m_data(data)
    182245        , m_buffer(0)
    183         , m_length(length)
    184         , m_refCountAndFlags(s_refCountFlagStatic | BufferOwned)
    185246        , m_hash(0)
    186247    {
    … …  
    190251    // Used to create new strings that are a substring of an existing string.
    191252    UStringImpl(UChar* data, unsigned length, PassRefPtr<UStringImpl> base)
    192         : m_data(data)
     253        : UStringOrRopeImpl(length, BufferSubstring)
     254        , m_data(data)
    193255        , m_bufferSubstring(base.releaseRef())
    194         , m_length(length)
    195         , m_refCountAndFlags(s_refCountIncrement | BufferSubstring)
    196256        , m_hash(0)
    197257    {
    … …  
    199259        // that all pointers will be at least 8-byte aligned, we cannot guarantee that of
    200260        // UStringImpls that are not heap allocated.
    201         ASSERT(m_bufferSubstring->size());
     261        ASSERT(m_bufferSubstring->length());
    202262        ASSERT(!m_bufferSubstring->isStatic());
    203263        checkConsistency();
    … …  
    206266    // Used to construct new strings sharing an existing shared buffer.
    207267    UStringImpl(UChar* data, unsigned length, PassRefPtr<SharedUChar> sharedBuffer)
    208         : m_data(data)
     268        : UStringOrRopeImpl(length, BufferShared)
     269        , m_data(data)
    209270        , m_bufferShared(sharedBuffer.releaseRef())
    210         , m_length(length)
    211         , m_refCountAndFlags(s_refCountIncrement | BufferShared)
    212         , m_hash(0)
    213     {
    214         checkConsistency();
    215     }
    216 
    217     using Noncopyable::operator new;
    218     void* operator new(size_t, void* inPlace) { return inPlace; }
     271        , m_hash(0)
     272    {
     273        checkConsistency();
     274    }
    219275
    220276    ~UStringImpl();
    … …  
    223279    static const unsigned s_minLengthToShare = 10;
    224280    static const unsigned s_copyCharsInlineCutOff = 20;
    225     // We initialize and increment/decrement the refCount for all normal (non-static) strings by the value 2.
    226     // We initialize static strings with an odd number (specifically, 1), such that the refCount cannot reach zero.
    227     static const unsigned s_refCountMask = 0xFFFFFFF0;
    228     static const unsigned s_refCountIncrement = 0x20;
    229     static const unsigned s_refCountFlagStatic = 0x10;
    230     static const unsigned s_refCountFlagHasReportedCost = 0x8;
    231     static const unsigned s_refCountFlagIsIdentifier = 0x4;
    232     static const unsigned s_refCountMaskBufferOwnership = 0x3;
    233281
    234282    UStringImpl* bufferOwnerString() { return (bufferOwnership() == BufferSubstring) ? m_bufferSubstring :  this; }
    … …  
    245293        SharedUChar* m_bufferShared;
    246294    };
    247     unsigned m_length;
    248     unsigned m_refCountAndFlags;
    249295    mutable unsigned m_hash;
    250296
    … …  
    253299    friend class JIT;
    254300    friend class SmallStringsStorage;
     301    friend class UStringOrRopeImpl;
    255302    friend void initializeUString();
    256303};
    257304
     305class URopeImpl : public UStringOrRopeImpl {
     306public:
     307    // A URopeImpl is composed from a set of smaller strings called Fibers.
     308    // Each Fiber in a rope is either UStringImpl or another URopeImpl.
     309    typedef UStringOrRopeImpl* Fiber;
     310
     311    // Creates a URopeImpl comprising of 'fiberCount' Fibers.
     312    // The URopeImpl is constructed in an uninitialized state - initialize must be called for each Fiber in the URopeImpl.
     313    static PassRefPtr<URopeImpl> tryCreateUninitialized(unsigned fiberCount)
     314    {
     315        void* allocation;
     316        if (tryFastMalloc(sizeof(URopeImpl) + (fiberCount - 1) * sizeof(Fiber)).getValue(allocation))
     317            return adoptRef(new (allocation) URopeImpl(fiberCount));
     318        return 0;
     319    }
     320
     321    void initializeFiber(unsigned &index, Fiber fiber)
     322    {
     323        m_fibers[index++] = fiber;
     324        fiber->ref();
     325        m_length += fiber->length();
     326    }
     327
     328    unsigned fiberCount() { return m_fiberCount; }
     329    Fiber& fibers(unsigned index) { return m_fibers[index]; }
     330
     331    ALWAYS_INLINE void deref() { m_refCountAndFlags -= s_refCountIncrement; if (!(m_refCountAndFlags & s_refCountMask)) destructNonRecursive(); }
     332
     333private:
     334    URopeImpl(unsigned fiberCount) : UStringOrRopeImpl(ConstructRope), m_fiberCount(fiberCount) {}
     335
     336    void destructNonRecursive();
     337    void derefFibersNonRecursive(Vector<URopeImpl*, 32>& workQueue);
     338
     339    bool hasOneRef() { return (m_refCountAndFlags & s_refCountMask) == s_refCountIncrement; }
     340
     341    unsigned m_fiberCount;
     342    Fiber m_fibers[1];
     343};
     344
     345inline void UStringOrRopeImpl::deref()
     346{
     347    m_refCountAndFlags -= s_refCountIncrement;
     348    if (!(m_refCountAndFlags & s_refCountMask)) {
     349        if (isRope())
     350            delete static_cast<URopeImpl*>(this);
     351        else if (!s_refCountFlagStatic)
     352            delete static_cast<UStringImpl*>(this);
     353    }
     354}
     355
    258356bool equal(const UStringImpl*, const UStringImpl*);
    259357
Note: See TracChangeset for help on using the changeset viewer.