2011-02-23 20:25:17 +00:00
|
|
|
/*
|
|
|
|
* 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. AND ITS CONTRIBUTORS ``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 ITS 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.
|
|
|
|
*/
|
|
|
|
|
2018-10-15 14:24:49 +00:00
|
|
|
#pragma once
|
2011-02-23 20:25:17 +00:00
|
|
|
|
|
|
|
namespace WTF {
|
|
|
|
|
2011-05-26 20:39:30 +00:00
|
|
|
// This class allows nodes to share code without dictating data member layout.
|
|
|
|
template<typename T> class DoublyLinkedListNode {
|
|
|
|
public:
|
|
|
|
DoublyLinkedListNode();
|
|
|
|
|
|
|
|
void setPrev(T*);
|
|
|
|
void setNext(T*);
|
|
|
|
|
|
|
|
T* prev() const;
|
|
|
|
T* next() const;
|
|
|
|
};
|
|
|
|
|
|
|
|
template<typename T> inline DoublyLinkedListNode<T>::DoublyLinkedListNode()
|
|
|
|
{
|
|
|
|
setPrev(0);
|
|
|
|
setNext(0);
|
|
|
|
}
|
|
|
|
|
|
|
|
template<typename T> inline void DoublyLinkedListNode<T>::setPrev(T* prev)
|
|
|
|
{
|
|
|
|
static_cast<T*>(this)->m_prev = prev;
|
|
|
|
}
|
|
|
|
|
|
|
|
template<typename T> inline void DoublyLinkedListNode<T>::setNext(T* next)
|
|
|
|
{
|
|
|
|
static_cast<T*>(this)->m_next = next;
|
|
|
|
}
|
|
|
|
|
|
|
|
template<typename T> inline T* DoublyLinkedListNode<T>::prev() const
|
|
|
|
{
|
|
|
|
return static_cast<const T*>(this)->m_prev;
|
|
|
|
}
|
|
|
|
|
|
|
|
template<typename T> inline T* DoublyLinkedListNode<T>::next() const
|
|
|
|
{
|
|
|
|
return static_cast<const T*>(this)->m_next;
|
|
|
|
}
|
|
|
|
|
2019-08-12 20:57:15 +00:00
|
|
|
template<typename T>
|
|
|
|
class DoublyLinkedList {
|
2011-02-23 20:25:17 +00:00
|
|
|
public:
|
|
|
|
DoublyLinkedList();
|
|
|
|
|
2011-05-26 20:39:30 +00:00
|
|
|
bool isEmpty() const;
|
|
|
|
size_t size() const; // This is O(n).
|
|
|
|
void clear();
|
2011-02-23 20:25:17 +00:00
|
|
|
|
2011-05-26 20:39:30 +00:00
|
|
|
T* head() const;
|
|
|
|
T* removeHead();
|
2011-02-23 20:25:17 +00:00
|
|
|
|
Introduce ShadowRootList.
https://bugs.webkit.org/show_bug.cgi?id=78069
Patch by Shinya Kawanaka <shinyak@google.com> on 2012-02-12
Reviewed by Hajime Morita.
Source/JavaScriptCore:
DoublyLinkedList should have tail() method to take the last element.
* wtf/DoublyLinkedList.h:
(DoublyLinkedList):
(WTF::::tail):
(WTF):
Source/WebCore:
This is a step to implement multiple shadow subtrees.
This patch introduces a shadow root list. ShadowRootList is a doubly linked list,
and each shadow root now has a younger shadow root and older shadow root,
which are a previous element and a next element respectively.
Since a visual tree traversal, which will be introduced in coming patches, will need a older shadow root,
we make a shadow root list a doubly linked list.
However, ShadowRootList does not have more than one shadow root now.
This will be changed in a series of coming patches.
Element::shadowRoot(), setShadowRoot(), ensureShadowRoot(), and removeShadowRoot() are
emulated using ShadowRootList for a while. These API will be replaced to ShadowRootList API later.
No new tests, no change in behavior.
* CMakeLists.txt:
* GNUmakefile.list.am:
* Target.pri:
* WebCore.gypi:
* WebCore.xcodeproj/project.pbxproj:
* dom/DOMAllInOne.cpp:
* dom/Element.cpp:
(WebCore::Element::hasShadowRoot):
Retruns true if an element has a shadowRoot.
(WebCore::Element::shadowRootList):
Gets shadow root list if any.
(WebCore::Element::shadowRoot):
Gets the first shadow root from the shadow root list.
(WebCore::Element::setShadowRoot):
Sets the first shadow root to the shadow root list.
(WebCore::Element::removeShadowRoot):
Removes all the shadow roots in the shadow root list.
* dom/Element.h:
(WebCore):
(Element):
* dom/ElementRareData.h:
(ElementRareData):
(WebCore::ElementRareData::ElementRareData):
Has shadow root lists instead of shadow root.
(WebCore::ElementRareData::~ElementRareData):
* dom/ShadowRoot.cpp:
(WebCore::ShadowRoot::ShadowRoot):
(WebCore::ShadowRoot::~ShadowRoot):
* dom/ShadowRoot.h:
(ShadowRoot):
(WebCore::ShadowRoot::youngerShadowRoot):
(WebCore::ShadowRoot::olderShadowRoot):
* dom/ShadowRootList.cpp: Added.
(WebCore):
(WebCore::ShadowRootList::ShadowRootList):
(WebCore::ShadowRootList::~ShadowRootList):
(WebCore::ShadowRootList::pushShadowRoot):
Adds a shadow root into the list. Currently we limit the list can have only one shadow root.
(WebCore::ShadowRootList::popShadowRoot):
Removes and returns the youngest shadow root if any.
* dom/ShadowRootList.h: Added.
(WebCore):
(ShadowRootList):
(WebCore::ShadowRootList::hasShadowRoot):
(WebCore::ShadowRootList::youngestShadowRoot):
(WebCore::ShadowRootList::oldestShadowRoot):
Canonical link: https://commits.webkit.org/95387@main
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@107525 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2012-02-13 04:15:49 +00:00
|
|
|
T* tail() const;
|
|
|
|
|
Implement a new allocator for backing stores
https://bugs.webkit.org/show_bug.cgi?id=75181
Reviewed by Filip Pizlo.
Source/JavaScriptCore:
We want to move away from using fastMalloc for the backing stores for
some of our objects (e.g. JSArray, JSObject, JSString, etc). These backing
stores have a nice property in that they only have a single owner (i.e. a
single pointer to them at any one time). One way that we can take advantage
of this property is to implement a simple bump allocator/copying collector,
which will run alongside our normal mark/sweep collector, that only needs to
update the single owner pointer rather than having to redirect an arbitrary
number of pointers in from-space to to-space.
This plan can give us a number of benefits. We can beat fastMalloc in terms
of both performance and memory usage, we can track how much memory we're using
far more accurately than our rough estimation now through the use of
reportExtraMemoryCost, and we can allocate arbitrary size objects (as opposed
to being limited to size classes like we have been historically). This is also
another step toward moving away from lazy destruction, which will improve our memory footprint.
We start by creating said allocator and moving the ArrayStorage for JSArray
to use it rather than fastMalloc.
The design of the collector is as follows:
Allocation:
-The collector allocates 64KB chunks from the OS to use for object allocation.
-Each chunk contains an offset, a flag indicating if the block has been pinned,
and a payload, along with next and prev pointers so that they can be put in DoublyLinkedLists.
-Any allocation greater than 64KB gets its own separate oversize block, which
is managed separately from the rest.
-If the allocator receives a request for more than the remaining amount in the
current block, it grabs a fresh block.
-Grabbing a fresh block means grabbing one off of the global free list (which is now
shared between the mark/sweep allocator and the bump allocator) if there is one.
If there isn't a new one we do one of two things: allocate a new block from the OS
if we're not ready for a GC yet, or run a GC and then try again. If we still don't
have enough space after the GC, we allocate a new block from the OS.
Garbage collection:
-At the start of garbage collection during conservative stack scanning, if we encounter
what appears to be a pointer to a bump-allocated block of memory, we pin that block so
that it will not be copied for this round of collection.
-We also pin any oversize blocks that we encounter, which effectively doubles as a
"mark bit" for that block. Any oversize blocks that aren't pinned at the end of copying
are given back to the OS.
-Marking threads are now also responsible for copying bump-allocated objects to newSpace
-Each marking thread has a private 64KB block into which it copies bump-allocated objects that it encounters.
-When that block fills up, the marking thread gives it back to the allocator and requests a new one.
-When all marking has concluded, each thread gives back its copy block, even if it isn't full.
-At the conclusion of copying (which is done by the end of the marking phase), we un-pin
any pinned blocks and give any blocks left in from-space to the global free list.
* CMakeLists.txt:
* GNUmakefile.list.am:
* JavaScriptCore.gypi:
* JavaScriptCore.vcproj/JavaScriptCore/JavaScriptCore.vcproj:
* JavaScriptCore.vcproj/WTF/WTF.vcproj:
* JavaScriptCore.xcodeproj/project.pbxproj:
* Target.pri:
* heap/AllocationSpace.cpp:
(JSC::AllocationSpace::allocateSlowCase):
(JSC::AllocationSpace::allocateBlock):
(JSC::AllocationSpace::freeBlocks):
* heap/AllocationSpace.h:
(JSC::AllocationSpace::waterMark):
* heap/BumpBlock.h: Added.
(JSC::BumpBlock::BumpBlock):
* heap/BumpSpace.cpp: Added.
(JSC::BumpSpace::tryAllocateSlowCase):
* heap/BumpSpace.h: Added.
(JSC::BumpSpace::isInCopyPhase):
(JSC::BumpSpace::totalMemoryAllocated):
(JSC::BumpSpace::totalMemoryUtilized):
* heap/BumpSpaceInlineMethods.h: Added.
(JSC::BumpSpace::BumpSpace):
(JSC::BumpSpace::init):
(JSC::BumpSpace::contains):
(JSC::BumpSpace::pin):
(JSC::BumpSpace::startedCopying):
(JSC::BumpSpace::doneCopying):
(JSC::BumpSpace::doneFillingBlock):
(JSC::BumpSpace::recycleBlock):
(JSC::BumpSpace::getFreshBlock):
(JSC::BumpSpace::borrowBlock):
(JSC::BumpSpace::addNewBlock):
(JSC::BumpSpace::allocateNewBlock):
(JSC::BumpSpace::fitsInBlock):
(JSC::BumpSpace::fitsInCurrentBlock):
(JSC::BumpSpace::tryAllocate):
(JSC::BumpSpace::tryAllocateOversize):
(JSC::BumpSpace::allocateFromBlock):
(JSC::BumpSpace::tryReallocate):
(JSC::BumpSpace::tryReallocateOversize):
(JSC::BumpSpace::isOversize):
(JSC::BumpSpace::isPinned):
(JSC::BumpSpace::oversizeBlockFor):
(JSC::BumpSpace::blockFor):
* heap/ConservativeRoots.cpp:
(JSC::ConservativeRoots::ConservativeRoots):
(JSC::ConservativeRoots::genericAddPointer):
(JSC::ConservativeRoots::add):
* heap/ConservativeRoots.h:
* heap/Heap.cpp:
(JSC::Heap::Heap):
(JSC::Heap::blockFreeingThreadMain):
(JSC::Heap::reportExtraMemoryCostSlowCase):
(JSC::Heap::getConservativeRegisterRoots):
(JSC::Heap::markRoots):
(JSC::Heap::collect):
(JSC::Heap::releaseFreeBlocks):
* heap/Heap.h:
(JSC::Heap::waterMark):
(JSC::Heap::highWaterMark):
(JSC::Heap::setHighWaterMark):
(JSC::Heap::tryAllocateStorage):
(JSC::Heap::tryReallocateStorage):
* heap/HeapBlock.h: Added.
(JSC::HeapBlock::HeapBlock):
* heap/MarkStack.cpp:
(JSC::MarkStackThreadSharedData::MarkStackThreadSharedData):
(JSC::SlotVisitor::drain):
(JSC::SlotVisitor::drainFromShared):
(JSC::SlotVisitor::startCopying):
(JSC::SlotVisitor::allocateNewSpace):
(JSC::SlotVisitor::copy):
(JSC::SlotVisitor::copyAndAppend):
(JSC::SlotVisitor::doneCopying):
* heap/MarkStack.h:
* heap/MarkedBlock.cpp:
(JSC::MarkedBlock::recycle):
(JSC::MarkedBlock::MarkedBlock):
* heap/MarkedBlock.h:
* heap/MarkedSpace.cpp:
(JSC::MarkedSpace::MarkedSpace):
* heap/MarkedSpace.h:
(JSC::MarkedSpace::allocate):
(JSC::MarkedSpace::forEachBlock):
(JSC::MarkedSpace::SizeClass::resetAllocator):
* heap/SlotVisitor.h:
(JSC::SlotVisitor::SlotVisitor):
* heap/TinyBloomFilter.h:
(JSC::TinyBloomFilter::reset):
* runtime/JSArray.cpp:
(JSC::JSArray::JSArray):
(JSC::JSArray::finishCreation):
(JSC::JSArray::tryFinishCreationUninitialized):
(JSC::JSArray::~JSArray):
(JSC::JSArray::enterSparseMode):
(JSC::JSArray::defineOwnNumericProperty):
(JSC::JSArray::setLengthWritable):
(JSC::JSArray::getOwnPropertySlotByIndex):
(JSC::JSArray::getOwnPropertyDescriptor):
(JSC::JSArray::putByIndexBeyondVectorLength):
(JSC::JSArray::deletePropertyByIndex):
(JSC::JSArray::getOwnPropertyNames):
(JSC::JSArray::increaseVectorLength):
(JSC::JSArray::unshiftCountSlowCase):
(JSC::JSArray::setLength):
(JSC::JSArray::pop):
(JSC::JSArray::unshiftCount):
(JSC::JSArray::visitChildren):
(JSC::JSArray::sortNumeric):
(JSC::JSArray::sort):
(JSC::JSArray::compactForSorting):
(JSC::JSArray::subclassData):
(JSC::JSArray::setSubclassData):
(JSC::JSArray::checkConsistency):
* runtime/JSArray.h:
(JSC::JSArray::inSparseMode):
(JSC::JSArray::isLengthWritable):
* wtf/CheckedBoolean.h: Added.
(CheckedBoolean::CheckedBoolean):
(CheckedBoolean::~CheckedBoolean):
(CheckedBoolean::operator bool):
* wtf/DoublyLinkedList.h:
(WTF::::push):
* wtf/StdLibExtras.h:
(WTF::isPointerAligned):
Source/JavaScriptGlue:
Added forwarding header for new CheckedBoolean used in the bump allocator.
* ForwardingHeaders/wtf/CheckedBoolean.h: Added.
Source/WebCore:
No new tests.
Added forwarding header for new CheckedBoolean used in the bump allocator.
* ForwardingHeaders/wtf/CheckedBoolean.h: Added.
Canonical link: https://commits.webkit.org/93486@main
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@105442 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2012-01-19 21:49:56 +00:00
|
|
|
void push(T*);
|
2011-05-26 20:39:30 +00:00
|
|
|
void append(T*);
|
|
|
|
void remove(T*);
|
2014-01-06 17:41:25 +00:00
|
|
|
void append(DoublyLinkedList<T>&);
|
2011-02-23 20:25:17 +00:00
|
|
|
|
|
|
|
private:
|
2011-05-26 20:39:30 +00:00
|
|
|
T* m_head;
|
|
|
|
T* m_tail;
|
2011-02-23 20:25:17 +00:00
|
|
|
};
|
|
|
|
|
2011-05-26 20:39:30 +00:00
|
|
|
template<typename T> inline DoublyLinkedList<T>::DoublyLinkedList()
|
2011-02-23 20:25:17 +00:00
|
|
|
: m_head(0)
|
|
|
|
, m_tail(0)
|
|
|
|
{
|
|
|
|
}
|
|
|
|
|
2011-05-26 20:39:30 +00:00
|
|
|
template<typename T> inline bool DoublyLinkedList<T>::isEmpty() const
|
2011-02-23 20:25:17 +00:00
|
|
|
{
|
|
|
|
return !m_head;
|
|
|
|
}
|
|
|
|
|
2011-05-26 20:39:30 +00:00
|
|
|
template<typename T> inline size_t DoublyLinkedList<T>::size() const
|
|
|
|
{
|
|
|
|
size_t size = 0;
|
|
|
|
for (T* node = m_head; node; node = node->next())
|
|
|
|
++size;
|
|
|
|
return size;
|
|
|
|
}
|
|
|
|
|
|
|
|
template<typename T> inline void DoublyLinkedList<T>::clear()
|
|
|
|
{
|
|
|
|
m_head = 0;
|
|
|
|
m_tail = 0;
|
|
|
|
}
|
|
|
|
|
|
|
|
template<typename T> inline T* DoublyLinkedList<T>::head() const
|
2011-02-23 20:25:17 +00:00
|
|
|
{
|
|
|
|
return m_head;
|
|
|
|
}
|
|
|
|
|
Introduce ShadowRootList.
https://bugs.webkit.org/show_bug.cgi?id=78069
Patch by Shinya Kawanaka <shinyak@google.com> on 2012-02-12
Reviewed by Hajime Morita.
Source/JavaScriptCore:
DoublyLinkedList should have tail() method to take the last element.
* wtf/DoublyLinkedList.h:
(DoublyLinkedList):
(WTF::::tail):
(WTF):
Source/WebCore:
This is a step to implement multiple shadow subtrees.
This patch introduces a shadow root list. ShadowRootList is a doubly linked list,
and each shadow root now has a younger shadow root and older shadow root,
which are a previous element and a next element respectively.
Since a visual tree traversal, which will be introduced in coming patches, will need a older shadow root,
we make a shadow root list a doubly linked list.
However, ShadowRootList does not have more than one shadow root now.
This will be changed in a series of coming patches.
Element::shadowRoot(), setShadowRoot(), ensureShadowRoot(), and removeShadowRoot() are
emulated using ShadowRootList for a while. These API will be replaced to ShadowRootList API later.
No new tests, no change in behavior.
* CMakeLists.txt:
* GNUmakefile.list.am:
* Target.pri:
* WebCore.gypi:
* WebCore.xcodeproj/project.pbxproj:
* dom/DOMAllInOne.cpp:
* dom/Element.cpp:
(WebCore::Element::hasShadowRoot):
Retruns true if an element has a shadowRoot.
(WebCore::Element::shadowRootList):
Gets shadow root list if any.
(WebCore::Element::shadowRoot):
Gets the first shadow root from the shadow root list.
(WebCore::Element::setShadowRoot):
Sets the first shadow root to the shadow root list.
(WebCore::Element::removeShadowRoot):
Removes all the shadow roots in the shadow root list.
* dom/Element.h:
(WebCore):
(Element):
* dom/ElementRareData.h:
(ElementRareData):
(WebCore::ElementRareData::ElementRareData):
Has shadow root lists instead of shadow root.
(WebCore::ElementRareData::~ElementRareData):
* dom/ShadowRoot.cpp:
(WebCore::ShadowRoot::ShadowRoot):
(WebCore::ShadowRoot::~ShadowRoot):
* dom/ShadowRoot.h:
(ShadowRoot):
(WebCore::ShadowRoot::youngerShadowRoot):
(WebCore::ShadowRoot::olderShadowRoot):
* dom/ShadowRootList.cpp: Added.
(WebCore):
(WebCore::ShadowRootList::ShadowRootList):
(WebCore::ShadowRootList::~ShadowRootList):
(WebCore::ShadowRootList::pushShadowRoot):
Adds a shadow root into the list. Currently we limit the list can have only one shadow root.
(WebCore::ShadowRootList::popShadowRoot):
Removes and returns the youngest shadow root if any.
* dom/ShadowRootList.h: Added.
(WebCore):
(ShadowRootList):
(WebCore::ShadowRootList::hasShadowRoot):
(WebCore::ShadowRootList::youngestShadowRoot):
(WebCore::ShadowRootList::oldestShadowRoot):
Canonical link: https://commits.webkit.org/95387@main
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@107525 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2012-02-13 04:15:49 +00:00
|
|
|
template<typename T> inline T* DoublyLinkedList<T>::tail() const
|
|
|
|
{
|
|
|
|
return m_tail;
|
|
|
|
}
|
|
|
|
|
Implement a new allocator for backing stores
https://bugs.webkit.org/show_bug.cgi?id=75181
Reviewed by Filip Pizlo.
Source/JavaScriptCore:
We want to move away from using fastMalloc for the backing stores for
some of our objects (e.g. JSArray, JSObject, JSString, etc). These backing
stores have a nice property in that they only have a single owner (i.e. a
single pointer to them at any one time). One way that we can take advantage
of this property is to implement a simple bump allocator/copying collector,
which will run alongside our normal mark/sweep collector, that only needs to
update the single owner pointer rather than having to redirect an arbitrary
number of pointers in from-space to to-space.
This plan can give us a number of benefits. We can beat fastMalloc in terms
of both performance and memory usage, we can track how much memory we're using
far more accurately than our rough estimation now through the use of
reportExtraMemoryCost, and we can allocate arbitrary size objects (as opposed
to being limited to size classes like we have been historically). This is also
another step toward moving away from lazy destruction, which will improve our memory footprint.
We start by creating said allocator and moving the ArrayStorage for JSArray
to use it rather than fastMalloc.
The design of the collector is as follows:
Allocation:
-The collector allocates 64KB chunks from the OS to use for object allocation.
-Each chunk contains an offset, a flag indicating if the block has been pinned,
and a payload, along with next and prev pointers so that they can be put in DoublyLinkedLists.
-Any allocation greater than 64KB gets its own separate oversize block, which
is managed separately from the rest.
-If the allocator receives a request for more than the remaining amount in the
current block, it grabs a fresh block.
-Grabbing a fresh block means grabbing one off of the global free list (which is now
shared between the mark/sweep allocator and the bump allocator) if there is one.
If there isn't a new one we do one of two things: allocate a new block from the OS
if we're not ready for a GC yet, or run a GC and then try again. If we still don't
have enough space after the GC, we allocate a new block from the OS.
Garbage collection:
-At the start of garbage collection during conservative stack scanning, if we encounter
what appears to be a pointer to a bump-allocated block of memory, we pin that block so
that it will not be copied for this round of collection.
-We also pin any oversize blocks that we encounter, which effectively doubles as a
"mark bit" for that block. Any oversize blocks that aren't pinned at the end of copying
are given back to the OS.
-Marking threads are now also responsible for copying bump-allocated objects to newSpace
-Each marking thread has a private 64KB block into which it copies bump-allocated objects that it encounters.
-When that block fills up, the marking thread gives it back to the allocator and requests a new one.
-When all marking has concluded, each thread gives back its copy block, even if it isn't full.
-At the conclusion of copying (which is done by the end of the marking phase), we un-pin
any pinned blocks and give any blocks left in from-space to the global free list.
* CMakeLists.txt:
* GNUmakefile.list.am:
* JavaScriptCore.gypi:
* JavaScriptCore.vcproj/JavaScriptCore/JavaScriptCore.vcproj:
* JavaScriptCore.vcproj/WTF/WTF.vcproj:
* JavaScriptCore.xcodeproj/project.pbxproj:
* Target.pri:
* heap/AllocationSpace.cpp:
(JSC::AllocationSpace::allocateSlowCase):
(JSC::AllocationSpace::allocateBlock):
(JSC::AllocationSpace::freeBlocks):
* heap/AllocationSpace.h:
(JSC::AllocationSpace::waterMark):
* heap/BumpBlock.h: Added.
(JSC::BumpBlock::BumpBlock):
* heap/BumpSpace.cpp: Added.
(JSC::BumpSpace::tryAllocateSlowCase):
* heap/BumpSpace.h: Added.
(JSC::BumpSpace::isInCopyPhase):
(JSC::BumpSpace::totalMemoryAllocated):
(JSC::BumpSpace::totalMemoryUtilized):
* heap/BumpSpaceInlineMethods.h: Added.
(JSC::BumpSpace::BumpSpace):
(JSC::BumpSpace::init):
(JSC::BumpSpace::contains):
(JSC::BumpSpace::pin):
(JSC::BumpSpace::startedCopying):
(JSC::BumpSpace::doneCopying):
(JSC::BumpSpace::doneFillingBlock):
(JSC::BumpSpace::recycleBlock):
(JSC::BumpSpace::getFreshBlock):
(JSC::BumpSpace::borrowBlock):
(JSC::BumpSpace::addNewBlock):
(JSC::BumpSpace::allocateNewBlock):
(JSC::BumpSpace::fitsInBlock):
(JSC::BumpSpace::fitsInCurrentBlock):
(JSC::BumpSpace::tryAllocate):
(JSC::BumpSpace::tryAllocateOversize):
(JSC::BumpSpace::allocateFromBlock):
(JSC::BumpSpace::tryReallocate):
(JSC::BumpSpace::tryReallocateOversize):
(JSC::BumpSpace::isOversize):
(JSC::BumpSpace::isPinned):
(JSC::BumpSpace::oversizeBlockFor):
(JSC::BumpSpace::blockFor):
* heap/ConservativeRoots.cpp:
(JSC::ConservativeRoots::ConservativeRoots):
(JSC::ConservativeRoots::genericAddPointer):
(JSC::ConservativeRoots::add):
* heap/ConservativeRoots.h:
* heap/Heap.cpp:
(JSC::Heap::Heap):
(JSC::Heap::blockFreeingThreadMain):
(JSC::Heap::reportExtraMemoryCostSlowCase):
(JSC::Heap::getConservativeRegisterRoots):
(JSC::Heap::markRoots):
(JSC::Heap::collect):
(JSC::Heap::releaseFreeBlocks):
* heap/Heap.h:
(JSC::Heap::waterMark):
(JSC::Heap::highWaterMark):
(JSC::Heap::setHighWaterMark):
(JSC::Heap::tryAllocateStorage):
(JSC::Heap::tryReallocateStorage):
* heap/HeapBlock.h: Added.
(JSC::HeapBlock::HeapBlock):
* heap/MarkStack.cpp:
(JSC::MarkStackThreadSharedData::MarkStackThreadSharedData):
(JSC::SlotVisitor::drain):
(JSC::SlotVisitor::drainFromShared):
(JSC::SlotVisitor::startCopying):
(JSC::SlotVisitor::allocateNewSpace):
(JSC::SlotVisitor::copy):
(JSC::SlotVisitor::copyAndAppend):
(JSC::SlotVisitor::doneCopying):
* heap/MarkStack.h:
* heap/MarkedBlock.cpp:
(JSC::MarkedBlock::recycle):
(JSC::MarkedBlock::MarkedBlock):
* heap/MarkedBlock.h:
* heap/MarkedSpace.cpp:
(JSC::MarkedSpace::MarkedSpace):
* heap/MarkedSpace.h:
(JSC::MarkedSpace::allocate):
(JSC::MarkedSpace::forEachBlock):
(JSC::MarkedSpace::SizeClass::resetAllocator):
* heap/SlotVisitor.h:
(JSC::SlotVisitor::SlotVisitor):
* heap/TinyBloomFilter.h:
(JSC::TinyBloomFilter::reset):
* runtime/JSArray.cpp:
(JSC::JSArray::JSArray):
(JSC::JSArray::finishCreation):
(JSC::JSArray::tryFinishCreationUninitialized):
(JSC::JSArray::~JSArray):
(JSC::JSArray::enterSparseMode):
(JSC::JSArray::defineOwnNumericProperty):
(JSC::JSArray::setLengthWritable):
(JSC::JSArray::getOwnPropertySlotByIndex):
(JSC::JSArray::getOwnPropertyDescriptor):
(JSC::JSArray::putByIndexBeyondVectorLength):
(JSC::JSArray::deletePropertyByIndex):
(JSC::JSArray::getOwnPropertyNames):
(JSC::JSArray::increaseVectorLength):
(JSC::JSArray::unshiftCountSlowCase):
(JSC::JSArray::setLength):
(JSC::JSArray::pop):
(JSC::JSArray::unshiftCount):
(JSC::JSArray::visitChildren):
(JSC::JSArray::sortNumeric):
(JSC::JSArray::sort):
(JSC::JSArray::compactForSorting):
(JSC::JSArray::subclassData):
(JSC::JSArray::setSubclassData):
(JSC::JSArray::checkConsistency):
* runtime/JSArray.h:
(JSC::JSArray::inSparseMode):
(JSC::JSArray::isLengthWritable):
* wtf/CheckedBoolean.h: Added.
(CheckedBoolean::CheckedBoolean):
(CheckedBoolean::~CheckedBoolean):
(CheckedBoolean::operator bool):
* wtf/DoublyLinkedList.h:
(WTF::::push):
* wtf/StdLibExtras.h:
(WTF::isPointerAligned):
Source/JavaScriptGlue:
Added forwarding header for new CheckedBoolean used in the bump allocator.
* ForwardingHeaders/wtf/CheckedBoolean.h: Added.
Source/WebCore:
No new tests.
Added forwarding header for new CheckedBoolean used in the bump allocator.
* ForwardingHeaders/wtf/CheckedBoolean.h: Added.
Canonical link: https://commits.webkit.org/93486@main
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@105442 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2012-01-19 21:49:56 +00:00
|
|
|
template<typename T> inline void DoublyLinkedList<T>::push(T* node)
|
|
|
|
{
|
|
|
|
if (!m_head) {
|
|
|
|
ASSERT(!m_tail);
|
|
|
|
m_head = node;
|
|
|
|
m_tail = node;
|
|
|
|
node->setPrev(0);
|
|
|
|
node->setNext(0);
|
|
|
|
return;
|
|
|
|
}
|
|
|
|
|
|
|
|
ASSERT(m_tail);
|
|
|
|
m_head->setPrev(node);
|
|
|
|
node->setNext(m_head);
|
|
|
|
node->setPrev(0);
|
|
|
|
m_head = node;
|
|
|
|
}
|
|
|
|
|
2011-05-26 20:39:30 +00:00
|
|
|
template<typename T> inline void DoublyLinkedList<T>::append(T* node)
|
2011-02-23 20:25:17 +00:00
|
|
|
{
|
|
|
|
if (!m_tail) {
|
|
|
|
ASSERT(!m_head);
|
|
|
|
m_head = node;
|
|
|
|
m_tail = node;
|
|
|
|
node->setPrev(0);
|
|
|
|
node->setNext(0);
|
|
|
|
return;
|
|
|
|
}
|
|
|
|
|
|
|
|
ASSERT(m_head);
|
|
|
|
m_tail->setNext(node);
|
|
|
|
node->setPrev(m_tail);
|
|
|
|
node->setNext(0);
|
|
|
|
m_tail = node;
|
|
|
|
}
|
|
|
|
|
2011-05-26 20:39:30 +00:00
|
|
|
template<typename T> inline void DoublyLinkedList<T>::remove(T* node)
|
2011-02-23 20:25:17 +00:00
|
|
|
{
|
|
|
|
if (node->prev()) {
|
|
|
|
ASSERT(node != m_head);
|
|
|
|
node->prev()->setNext(node->next());
|
|
|
|
} else {
|
|
|
|
ASSERT(node == m_head);
|
|
|
|
m_head = node->next();
|
|
|
|
}
|
|
|
|
|
|
|
|
if (node->next()) {
|
|
|
|
ASSERT(node != m_tail);
|
|
|
|
node->next()->setPrev(node->prev());
|
|
|
|
} else {
|
|
|
|
ASSERT(node == m_tail);
|
|
|
|
m_tail = node->prev();
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
2011-05-26 20:39:30 +00:00
|
|
|
template<typename T> inline T* DoublyLinkedList<T>::removeHead()
|
|
|
|
{
|
|
|
|
T* node = head();
|
|
|
|
if (node)
|
|
|
|
remove(node);
|
|
|
|
return node;
|
|
|
|
}
|
|
|
|
|
2014-01-06 17:41:25 +00:00
|
|
|
template<typename T> inline void DoublyLinkedList<T>::append(DoublyLinkedList<T>& other)
|
|
|
|
{
|
|
|
|
if (!other.head())
|
|
|
|
return;
|
|
|
|
|
|
|
|
if (!head()) {
|
|
|
|
m_head = other.head();
|
|
|
|
m_tail = other.tail();
|
|
|
|
other.clear();
|
|
|
|
return;
|
|
|
|
}
|
|
|
|
|
|
|
|
ASSERT(tail());
|
|
|
|
ASSERT(other.head());
|
|
|
|
T* otherHead = other.head();
|
|
|
|
T* otherTail = other.tail();
|
|
|
|
other.clear();
|
|
|
|
|
|
|
|
ASSERT(!m_tail->next());
|
|
|
|
m_tail->setNext(otherHead);
|
|
|
|
ASSERT(!otherHead->prev());
|
|
|
|
otherHead->setPrev(m_tail);
|
|
|
|
m_tail = otherTail;
|
|
|
|
}
|
|
|
|
|
2011-02-23 20:25:17 +00:00
|
|
|
} // namespace WTF
|
|
|
|
|
2011-05-26 20:39:30 +00:00
|
|
|
using WTF::DoublyLinkedListNode;
|
2011-02-23 20:25:17 +00:00
|
|
|
using WTF::DoublyLinkedList;
|