r134080 causes heap problem on linux systems where PAGESIZE != 4096

[Balazs Kilvady]

On linux systems where PAGESIZE == 16k we could use webkit/jsc with USE_SYSTEM_MALLOC=1 until r134080 caused memory handling problems like FastMalloc. With modifying 2 constant values it can be fixed. Still a question if static const size_t s_regionSize = 64 * KB; in class Region; of BlockAllocator.h should also be modified ( a higher value would be more efficient for bigger PAGESIZE?).

[Balazs Kilvady]

Created attachment 175259 [details]
proposed patch

[Mark Hahnenberg]

Comment on attachment 175259 [details]
proposed patch

View in context: https://bugs.webkit.org/attachment.cgi?id=175259&action=review

I'm somewhat confused as to why a different page size makes things segfault. Where exactly did it segfault? I wouldn't be opposed to making the Region size variable, e.g. 16 * WTF::pageSize() or something like that.

> Source/JavaScriptCore/heap/MarkStack.cpp:48
> +#if OS(LINUX) && COMPILER(GCC)

Instead of putting a bunch of nasty ifdefs everywhere, maybe you could use WTF::pageSize()?

[Balazs Kilvady]

(In reply to comment #2)
> (From update of attachment 175259 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=175259&action=review
> 
> I'm somewhat confused as to why a different page size makes things segfault. Where exactly did it segfault? I wouldn't be opposed to making the Region size variable, e.g. 16 * WTF::pageSize() or something like that.
I don't know where exactly the error comes from (it varies by tests, debug/release) but it always happens in a heap operation since r134080. This patch fixed the problem.

> > Source/JavaScriptCore/heap/MarkStack.cpp:48
> > +#if OS(LINUX) && COMPILER(GCC)
> 
> Instead of putting a bunch of nasty ifdefs everywhere, maybe you could use WTF::pageSize()?
Would be better but I cannot test in on windows and a WTF::pageSize() should be multi platform I guess. I will try to add a WTF::pageSize() implementation for Linux.

[Balazs Kilvady]

Created attachment 176210 [details]
proposed patch (fixed)

[Balazs Kilvady]

Comment on attachment 176210 [details]
proposed patch (fixed)

I have found the WTF::pageSize() implementation so I made a new patch using it. Also interested in why different pagesize causes a heap problem. Also would be fine to find out how to make FastMalloc to work with not 4k pagesize. I hope some heap/alloc specialist can find it out :)

[Balazs Kilvady]

Created attachment 176212 [details]
proposed patch (fixed)

ChangeLog text changed.

[Filip Pizlo]

(In reply to comment #3)
> (In reply to comment #2)
> > (From update of attachment 175259 [details] [details])
> > View in context: https://bugs.webkit.org/attachment.cgi?id=175259&action=review
> > 
> > I'm somewhat confused as to why a different page size makes things segfault. Where exactly did it segfault? I wouldn't be opposed to making the Region size variable, e.g. 16 * WTF::pageSize() or something like that.
> I don't know where exactly the error comes from (it varies by tests, debug/release) but it always happens in a heap operation since r134080. This patch fixed the problem.

I don't like the idea of doing a blind fix.  Can you try to do more investigation into where in our memory management logic things go wrong?

It would be good to understand this.  It may even be that you've found a more fundamental bug that happens to only show up with larger page sizes, but is just harder to spot with the usual page sizes that most WebKit clients use.

> 
> > > Source/JavaScriptCore/heap/MarkStack.cpp:48
> > > +#if OS(LINUX) && COMPILER(GCC)
> > 
> > Instead of putting a bunch of nasty ifdefs everywhere, maybe you could use WTF::pageSize()?
> Would be better but I cannot test in on windows and a WTF::pageSize() should be multi platform I guess. I will try to add a WTF::pageSize() implementation for Linux.

[Balazs Kilvady]

(In reply to comment #7)
> (In reply to comment #3)
> > (In reply to comment #2)
> > > (From update of attachment 175259 [details] [details] [details])
> > > View in context: https://bugs.webkit.org/attachment.cgi?id=175259&action=review
> > > 
> > > I'm somewhat confused as to why a different page size makes things segfault. Where exactly did it segfault? I wouldn't be opposed to making the Region size variable, e.g. 16 * WTF::pageSize() or something like that.
> > I don't know where exactly the error comes from (it varies by tests, debug/release) but it always happens in a heap operation since r134080. This patch fixed the problem.
> 
> I don't like the idea of doing a blind fix.  Can you try to do more investigation into where in our memory management logic things go wrong?
> 
> It would be good to understand this.  It may even be that you've found a more fundamental bug that happens to only show up with larger page sizes, but is just harder to spot with the usual page sizes that most WebKit clients use.
I will try to find it.

[Build Bot]

Comment on attachment 176212 [details]
proposed patch (fixed)

Attachment 176212 [details] did not pass mac-ews (mac):
Output: http://queues.webkit.org/results/15025099

[Balazs Kilvady]

(In reply to comment #7)
> (In reply to comment #3)
> > (In reply to comment #2)
> > > (From update of attachment 175259 [details] [details] [details])
happens in a heap operation since r134080. This patch fixed the problem.
> 
> I don't like the idea of doing a blind fix.  Can you try to do more investigation into where in our memory management logic things go wrong?
> 
> It would be good to understand this.  It may even be that you've found a more fundamental bug that happens to only show up with larger page sizes, but is just harder to spot with the usual page sizes that most WebKit clients use.

The bug comes up at GC visiting when regexp of v8 performance test executed on a MIPS board where the (linux) kernel’s pagesize is 16KB and WeakBLock::blockSize == MarkStackSegment::blockSize == 4KB. In each tests I modified only WeakBLock::blockSize and MarkStackSegment::blockSize in the current master branch.

When a particular MarkedBlock is allocated from WeakSet::addAllocator() the weakSet looks like:

this WeakSet: 0x2e010224
(gdb) p this->m_blocks
$2 = {m_head = 0x2db93000, m_tail = 0x2db96000}
(gdb) p this->m_blocks.m_head.m_next
$3 = (class JSC::WeakBlock *) 0x2db96000

After allocating some longer (> 3000 bytes) strings the GarbageCollector starts to visit MarkedBlocks and jsc crashes on an invalid block:
(gdb) p &this->m_weakSet
$5 = (JSC::WeakSet *) 0x2e010224
(gdb) p this->m_weakSet.m_blocks
$7 = {m_head = 0x2db93000, m_tail = 0x2db96000}
(gdb) p *this->m_weakSet.m_blocks.m_head
$9 = {<JSC::HeapBlock<JSC::WeakBlock>> = {<WTF::DoublyLinkedListNode<JSC::WeakBlock>> = {<No data fields>}, 
   m_region = 0x2e1a6800, m_prev = 0x2e1a67e0, m_next = 0x2e1a67a0}, static blockSize = 4096, m_sweepResult = {
   blockIsFree = 96, freeList = 0x2e1a6720}}

So the block in the head of the weakSet’s m_blocks was overwritten while m_blocks.m_tail.m_prev == 0x2db93000 == m_blocks.m_head. It seems like a WeakImpl (WeakBlock::FreeCell?) list node would be written to the address of a WeakBlock node.

The ASSERT failure with backtrace:
ASSERTION FAILED: isCell()
/data/kilvadyb/webkit-mips/webkit/Source/JavaScriptCore/runtime/JSValueInlines.h(295) : JSC::JSCell* JSC::JSValue::asCell() const

Program received signal SIGBUS, Bus error.
0x2ad71ec8 in JSC::JSValue::asCell (this=0x2e2367c0)
    at /data/kilvadyb/webkit-mips/webkit/Source/JavaScriptCore/runtime/JSValueInlines.h:295
295	        ASSERT(isCell());
(gdb) bt
#0  0x2ad71ec8 in JSC::JSValue::asCell (this=0x2e2367c0)
    at /data/kilvadyb/webkit-mips/webkit/Source/JavaScriptCore/runtime/JSValueInlines.h:295
#1  0x2aef3170 in JSC::WeakBlock::visit (this=0x2e2367a0, heapRootVisitor=...)
    at /data/kilvadyb/webkit-mips/webkit/Source/JavaScriptCore/heap/WeakBlock.cpp:103
#2  0x2af29000 in JSC::WeakSet::visit (this=0x2e090224, visitor=...)
    at /data/kilvadyb/webkit-mips/webkit/Source/JavaScriptCore/heap/WeakSet.h:104
#3  0x2af29364 in JSC::MarkedBlock::visitWeakSet (this=0x2e090000, heapRootVisitor=...)
    at /data/kilvadyb/webkit-mips/webkit/Source/JavaScriptCore/heap/MarkedBlock.h:300
#4  0x2af29cc4 in JSC::VisitWeakSet::operator() (this=0x7fff1f78, block=0x2e090000)
    at /data/kilvadyb/webkit-mips/webkit/Source/JavaScriptCore/heap/MarkedSpace.cpp:71
#5  0x2af2b790 in JSC::MarkedAllocator::forEachBlock<JSC::VisitWeakSet> (this=0x46a3f0, functor=...)
    at /data/kilvadyb/webkit-mips/webkit/Source/JavaScriptCore/heap/MarkedAllocator.h:116

I have made some testing on mac and ARMv7 linux qt environments with WeakBLock::blockSize == MarkStackSegment::blockSize == 1KB. In this case these blockSizes are one fourth of the WTF::pageSize() like 4KB on MIPS 16KB pagesize. On both arches the same ASSERT failure comes up (but different from the MIPS failure):

ASSERTION FAILED: node != m_head
/Users/bali/Work/MattaKis/webkit/WebKitBuild/Debug/usr/local/include/wtf/DoublyLinkedList.h(165) : void WTF::DoublyLinkedList<JSC::DeadBlock>::remove(JSC::DeadBlock *)
1   0x1000af862 WTF::DoublyLinkedList<JSC::DeadBlock>::remove(JSC::DeadBlock*)
2   0x1000af7c8 WTF::DoublyLinkedList<JSC::DeadBlock>::removeHead()
3   0x1000af787 JSC::Region::allocate()DoublyLinkedList<T>::remove(T* node)
…
at DoublyLinkedList.h:165
   162 	template<typename T> inline void DoublyLinkedList<T>::remove(T* node)
   163 	{
   164 	    if (node->prev()) {
-> 165 	        ASSERT(node != m_head);
   166 	        node->prev()->setNext(node->next());
   167 	    } else {

[Balazs Kilvady]

> I don't like the idea of doing a blind fix.  Can you try to do more investigation into where in our memory management logic things go wrong?
> 
> It would be good to understand this.  It may even be that you've found a more fundamental bug that happens to only show up with larger page sizes, but is just harder to spot with the usual page sizes that most WebKit clients use.

The problem is caused by the default value of the gcMarkStackSegmentSize JSC VM option. This default value is (WTF::)pageSize() which is 16KB on our MIPS target device. In heap/MarkStack.cpp the constructor of MarkStackArray initializes its segment's capacity with this value:
MarkStackArray::MarkStackArray(BlockAllocator& blockAllocator)
   : m_blockAllocator(blockAllocator)
   , m_segmentCapacity(MarkStackSegment::capacityFromSize(Options::gcMarkStackSegmentSize()))
   , m_top(0)
   , m_numberOfSegments(0)
{
   ASSERT(MarkStackSegment::blockSize == WeakBlock::blockSize);

So in the MarkStackArray::append function the overwriting might happen as it believes from a 4KB block that that has a 16KB capacity:
inline void MarkStackArray::append(const JSCell* cell)
{
   if (m_top == m_segmentCapacity)
       expand();
   m_segments.head()->data()[postIncTop()] = cell;
}

If I run a problematic test with a right option then it works fine and passes:
/data/kilvadyb/webkit-mips/webkit/WebKitBuild/Debug/bin/jsc --gcMarkStackSegmentSize=4096 -s js1_5/shell.js js1_5/Regress/regress-159334.js

[Balazs Kilvady]

Created attachment 181941 [details]
proposed patch.

We are not satisfied with this patch, but would like to start a discussion. One possible solution is what we did in the patch: to introduce a new base class which defines the block size for the HeapBlocks in question (forcing a common value). Another possible solution would be to just introduce a new constant for this purpose and use it as the default value for both the blockSize in the heap blocks and the  gcMarkStackSegmentSize option.

An other option is to fix MarkStackArray to use block size of heap blocks. We aren't sure if gcMarkStackSegmentSize is good to use in MarkStackArray implementation as it depends on MarkStackSegment::blockSize.

[Build Bot]

Comment on attachment 181941 [details]
proposed patch.

Attachment 181941 [details] did not pass mac-ews (mac):
Output: http://queues.webkit.org/results/15763610

[Mark Hahnenberg]

Comment on attachment 181941 [details]
proposed patch.

View in context: https://bugs.webkit.org/attachment.cgi?id=181941&action=review

> Source/JavaScriptCore/heap/BaseBlock.h:33
> +class BaseBlock {

It seems like major overkill to define an entirely new class whose sole purpose is to make sure a static constant is the same between two classes. Why not just use a COMPILE_ASSERT? And why not just change the value in Options.cpp to be 4 KB rather than pageSize()?

> Source/JavaScriptCore/heap/MarkStack.cpp:-54
> -    ASSERT(MarkStackSegment::blockSize == WeakBlock::blockSize);

Why wasn't this ASSERT firing before if the MarkStackSegment blockSize was not equal to the WeakBlock blockSize?

[Balazs Kilvady]

(In reply to comment #14)
> (From update of attachment 181941 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=181941&action=review
> 
> > Source/JavaScriptCore/heap/BaseBlock.h:33
> > +class BaseBlock {
> 
> It seems like major overkill to define an entirely new class whose sole purpose is to make sure a static constant is the same between two classes. Why not just use a COMPILE_ASSERT? And why not just change the value in Options.cpp to be 4 KB rather than pageSize()?

That also works and we said in the comment that we can provide such a patch also if you like. In that case the 4 KB is a "magic value" and must be matching at 3 different places. With this common base class the same value is guaranteed/forced at all the 3 places. But of course we will create an other patch with a static constant.

> 
> > Source/JavaScriptCore/heap/MarkStack.cpp:-54
> > -    ASSERT(MarkStackSegment::blockSize == WeakBlock::blockSize);
> 
> Why wasn't this ASSERT firing before if the MarkStackSegment blockSize was not equal to the WeakBlock blockSize?
Because both MarkStackSegment::blockSize and WeakBlock::blockSize  are 4 KB so the ASSERT condition is matching but MarkStackArray::m_segmentCapacity == MarkStackSegment::capacityFromSize(Options::gcMarkStackSegmentSize()))
and Options::gcMarkStackSegmentSize() == WTF::pageSize() by default. So MarkStackArray believes that a MarkStackSegment block has a pageSize capacity (16 KB) while it has only a MarkStackSegment::blockSize (4 KB). And in MarkStackArray::append function it expands the segments when the currently used block's capacity is exhausted but the array objects believes that a segment block has 4 times bigger capacity then in reality:
inline void MarkStackArray::append(const JSCell* cell)
{
   if (m_top == m_segmentCapacity)
       expand();
   m_segments.head()->data()[postIncTop()] = cell;
}

when m_top reaches 102x then the m_segments.head()->data()[postIncTop()] points to m_segments.m_head + sizeof(MarkStackSegment) + 102x * sizeof(JSCell*) which is over the 4 KB size of the MarkStackSegment block. So it overwrites the next block's data even its link node part and corrupts the block list.

[Balazs Kilvady]

(In reply to comment #14)

And thank you very much for the quick review.

[Mark Hahnenberg]

> That also works and we said in the comment that we can provide such a patch also if you like. In that case the 4 KB is a "magic value" and must be matching at 3 different places. With this common base class the same value is guaranteed/forced at all the 3 places. But of course we will create an other patch with a static constant.

In this case it's not a magic value since we're giving it a meaningful name. Classes are more for encapsulating a particular functionality behind a coherent interface. They're not really for enforcing runtime/compile-time constraints; that's what assertions are for!

> Because both MarkStackSegment::blockSize and WeakBlock::blockSize  are 4 KB so the ASSERT condition is matching but MarkStackArray::m_segmentCapacity == MarkStackSegment::capacityFromSize(Options::gcMarkStackSegmentSize()))

That makes sense, I overlooked the m_segmentCapacity field. Maybe it would make sense to remove Options::gcMarkStackSegmentSize since MarkStackSegments define their own size/capacity now? Along with some COMPILE_ASSERTs to make sure we don't get out of sync in the future, I think that would fix this bug entirely.

[Balazs Kilvady]

Created attachment 182107 [details]
proposed patch.

Removes gcMarkStackSegmentSize option and fixes MarkStackArray's capacity.

[Balazs Kilvady]

Created attachment 182109 [details]
Make capacity field static.

Like the previous patch but also makes the capacity field static.

[Build Bot]

Comment on attachment 182109 [details]
Make capacity field static.

Attachment 182109 [details] did not pass win-ews (win):
Output: http://queues.webkit.org/results/15760858

[Build Bot]

Comment on attachment 182109 [details]
Make capacity field static.

Attachment 182109 [details] did not pass mac-ews (mac):
Output: http://queues.webkit.org/results/15760857

[Benjamin Poulain]

Comment on attachment 182109 [details]
Make capacity field static.

View in context: https://bugs.webkit.org/attachment.cgi?id=182109&action=review

> Source/JavaScriptCore/ChangeLog:6
> +        Reviewed by Mark Hahnenberg.

I don't see this in the history. Why do you say it is reviewed?

[Mark Hahnenberg]

Also, don't forget to add the COMPILE_ASSERTs to make sure that WeakBlock and MarkStackSegments have the same blockSize.

[Balazs Kilvady]

Created attachment 183406 [details]
Make capacity field static.

[Build Bot]

Comment on attachment 183406 [details]
Make capacity field static.

Attachment 183406 [details] did not pass mac-wk2-ews (mac-wk2):
Output: http://queues.webkit.org/results/15955133

[Build Bot]

Comment on attachment 183406 [details]
Make capacity field static.

Attachment 183406 [details] did not pass win-ews (win):
Output: http://queues.webkit.org/results/15937633

[Build Bot]

Comment on attachment 183406 [details]
Make capacity field static.

Attachment 183406 [details] did not pass mac-ews (mac):
Output: http://queues.webkit.org/results/15938590

[Build Bot]

Comment on attachment 183406 [details]
Make capacity field static.

Attachment 183406 [details] did not pass mac-ews (mac):
Output: http://queues.webkit.org/results/15944486

[Balazs Kilvady]

Created attachment 183468 [details]
Make capacity field static.

JS_EXPORT_PRIVATE added.

[Balazs Kilvady]

Comment on attachment 183468 [details]
Make capacity field static.

Rebased on r140150

[Build Bot]

Comment on attachment 183468 [details]
Make capacity field static.

Attachment 183468 [details] did not pass win-ews (win):
Output: http://queues.webkit.org/results/15944623

[Mark Hahnenberg]

Comment on attachment 183468 [details]
Make capacity field static.

View in context: https://bugs.webkit.org/attachment.cgi?id=183468&action=review

Additionally, there's a function named "sizeFromCapacity" in MarkStackSegment. That doesn't appear to be called from anywhere, so let's remove it while we're here.

> Source/JavaScriptCore/heap/MarkStack.cpp:47
> +#if COMPILER(CLANG)

Let's not ignore the warnings.

> Source/JavaScriptCore/heap/MarkStack.cpp:52
> +const size_t MarkStackArray::s_segmentCapacity = MarkStackSegment::capacityFromSize(MarkStackSegment::blockSize);

If we could use C++11, we could just add constexpr to capacityFromSize and call it a day. Unfortunately we can't, so we have to use some template magic.

Instead of using the old capacityFromSize static function, let's rework the code a little bit. From some brief grepping, it appears that this is the only client of the capacityFromSize function. So in order to get a compile-time constant value, we can instead use a template. Something along the lines of:

template <size_t size> struct CapacityFromSize {
    static const size_t value = // body of current capacityFromSize
};

Stick that somewhere private in MarkStackArray and grab the ::value when defining s_segmentCapacity.

[Balazs Kilvady]

(In reply to comment #32)
> (From update of attachment 183468 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=183468&action=review
> 
> Additionally, there's a function named "sizeFromCapacity" in MarkStackSegment. That doesn't appear to be called from anywhere, so let's remove it while we're here.
> 
> > Source/JavaScriptCore/heap/MarkStack.cpp:47
> > +#if COMPILER(CLANG)
> 
> Let's not ignore the warnings.
> 
> > Source/JavaScriptCore/heap/MarkStack.cpp:52
> > +const size_t MarkStackArray::s_segmentCapacity = MarkStackSegment::capacityFromSize(MarkStackSegment::blockSize);
> 
> If we could use C++11, we could just add constexpr to capacityFromSize and call it a day. Unfortunately we can't, so we have to use some template magic.
> 
> Instead of using the old capacityFromSize static function, let's rework the code a little bit. From some brief grepping, it appears that this is the only client of the capacityFromSize function. So in order to get a compile-time constant value, we can instead use a template. Something along the lines of:
> 
> template <size_t size> struct CapacityFromSize {
>     static const size_t value = // body of current capacityFromSize
> };
> 
> Stick that somewhere private in MarkStackArray and grab the ::value when defining s_segmentCapacity.

Thank you for reviewing. I also see a windows specific problem. A static member should be used only in it's dll |(otherwise there are memory address problems in dllexport - JavaScriptCore and dllimport - WebCore modules) so the inline functions which are using it should be moved to the .cpp file. Is the template trick solves this problem also or should I return to the non-static member solution?

[Mark Hahnenberg]

> Thank you for reviewing. I also see a windows specific problem. A static member should be used only in it's dll |(otherwise there are memory address problems in dllexport - JavaScriptCore and dllimport - WebCore modules) so the inline functions which are using it should be moved to the .cpp file. Is the template trick solves this problem also or should I return to the non-static member solution?

The template solution won't solve that particular linking issue, but I believe you just need to add the symbol it references in the build log to the JavaScriptCoreExports.def file.

[Balazs Kilvady]

(In reply to comment #34)
> > Thank you for reviewing. I also see a windows specific problem. A static member should be used only in it's dll |(otherwise there are memory address problems in dllexport - JavaScriptCore and dllimport - WebCore modules) so the inline functions which are using it should be moved to the .cpp file. Is the template trick solves this problem also or should I return to the non-static member solution?
> 
> The template solution won't solve that particular linking issue, but I believe you just need to add the symbol it references in the build log to the JavaScriptCoreExports.def file.

Thank you for the info. I hope it helps.

[Balazs Kilvady]

Created attachment 183513 [details]
Make capacity field static.

[Mark Hahnenberg]

Comment on attachment 183513 [details]
Make capacity field static.

View in context: https://bugs.webkit.org/attachment.cgi?id=183513&action=review

r=me with small edit and no EWS issues.

> Source/JavaScriptCore/heap/MarkStack.h:79
>      static size_t sizeFromCapacity(size_t capacity)

One more change. Remove this function, since nobody calls it.

[Balazs Kilvady]

Created attachment 183522 [details]
Make capacity field static.

[WebKit Review Bot]

Comment on attachment 183522 [details]
Make capacity field static.

Clearing flags on attachment: 183522

Committed r140195: <http://trac.webkit.org/changeset/140195>

[WebKit Review Bot]

All reviewed patches have been landed.  Closing bug.