RESOLVED FIXED 172793
GC should use scrambled free-lists
https://bugs.webkit.org/show_bug.cgi?id=172793
Summary GC should use scrambled free-lists
Filip Pizlo
Reported 2017-05-31 20:37:52 PDT
Patch forthcoming.
Attachments
it's a start (32.09 KB, patch)
2017-05-31 20:38 PDT, Filip Pizlo
no flags
more (37.61 KB, patch)
2017-06-01 09:17 PDT, Filip Pizlo
no flags
it grows (44.20 KB, patch)
2017-06-01 09:53 PDT, Filip Pizlo
no flags
compiles in debug and runs some simple code (53.89 KB, patch)
2017-06-01 10:32 PDT, Filip Pizlo
no flags
release builds and seems to pass some tests (54.38 KB, patch)
2017-06-01 10:41 PDT, Filip Pizlo
no flags
the patch (54.45 KB, patch)
2017-06-01 11:05 PDT, Filip Pizlo
no flags
the patch (54.42 KB, patch)
2017-06-01 11:22 PDT, Filip Pizlo
no flags
removed some pointer chasing (55.22 KB, patch)
2017-06-01 13:12 PDT, Filip Pizlo
no flags
switched to list-of-pointers instead of list-of-offsets (54.87 KB, patch)
2017-06-01 13:41 PDT, Filip Pizlo
no flags
scrambled the free-list instead (57.47 KB, patch)
2017-06-01 14:35 PDT, Filip Pizlo
no flags
the patch (57.47 KB, patch)
2017-06-01 15:38 PDT, Filip Pizlo
no flags
the patch (57.82 KB, patch)
2017-06-01 15:44 PDT, Filip Pizlo
no flags
the patch (58.39 KB, patch)
2017-06-01 17:03 PDT, Filip Pizlo
mark.lam: review+
Filip Pizlo
Comment 1 2017-05-31 20:38:30 PDT
Created attachment 311676 [details] it's a start
Filip Pizlo
Comment 2 2017-06-01 09:17:10 PDT
Filip Pizlo
Comment 3 2017-06-01 09:53:46 PDT
Created attachment 311711 [details] it grows
Filip Pizlo
Comment 4 2017-06-01 10:32:46 PDT
Created attachment 311722 [details] compiles in debug and runs some simple code Building and testing release now.
Build Bot
Comment 5 2017-06-01 10:34:42 PDT
Attachment 311722 [details] did not pass style-queue: ERROR: Source/JavaScriptCore/heap/MarkedAllocator.cpp:159: More than one command on the same line [whitespace/newline] [4] Total errors found: 1 in 23 files If any of these errors are false positives, please file a bug against check-webkit-style.
Filip Pizlo
Comment 6 2017-06-01 10:41:53 PDT
Created attachment 311724 [details] release builds and seems to pass some tests
Build Bot
Comment 7 2017-06-01 10:44:44 PDT
Attachment 311724 [details] did not pass style-queue: ERROR: Source/JavaScriptCore/heap/MarkedAllocator.cpp:159: More than one command on the same line [whitespace/newline] [4] Total errors found: 1 in 24 files If any of these errors are false positives, please file a bug against check-webkit-style.
Filip Pizlo
Comment 8 2017-06-01 11:05:46 PDT
Created attachment 311728 [details] the patch Fix builds
Build Bot
Comment 9 2017-06-01 11:07:29 PDT
Attachment 311728 [details] did not pass style-queue: ERROR: Source/JavaScriptCore/heap/MarkedAllocator.cpp:159: More than one command on the same line [whitespace/newline] [4] Total errors found: 1 in 24 files If any of these errors are false positives, please file a bug against check-webkit-style.
Filip Pizlo
Comment 10 2017-06-01 11:22:54 PDT
Created attachment 311733 [details] the patch
Build Bot
Comment 11 2017-06-01 11:25:23 PDT
Attachment 311733 [details] did not pass style-queue: ERROR: Source/JavaScriptCore/heap/MarkedAllocator.cpp:159: More than one command on the same line [whitespace/newline] [4] Total errors found: 1 in 24 files If any of these errors are false positives, please file a bug against check-webkit-style.
Oliver Hunt
Comment 12 2017-06-01 11:27:45 PDT
View in context: https://bugs.webkit.org/attachment.cgi?id=311728&action=review lgtm (with comments), but i'd obviously prefer someone more familiar with ToT to actually r+ > Source/JavaScriptCore/heap/FreeList.cpp:71 > + m_remaining = remaining; can you add a RELEASE_ASSERT(remaining % cellSize == 0 ) ? > Source/JavaScriptCore/heap/FreeListInlines.h:43 > + unsigned remaining = m_remaining; Can you see if making this Checked<unsigned> has a perf impact? This is simply paranoia and the code does not obviously overflow, but i'm increasingly paranoid about almost math these days :D > Source/JavaScriptCore/heap/FreeListInlines.h:47 > + m_remaining = remaining; This being safe is dependent on remaining always being a multiple of m_cellSize. > Source/JavaScriptCore/heap/MarkedAllocator.cpp:159 > + [] () -> HeapCell* { RELEASE_ASSERT_NOT_REACHED(); return nullptr; }); nice
Mark Lam
Comment 13 2017-06-01 11:35:41 PDT
Comment on attachment 311724 [details] release builds and seems to pass some tests View in context: https://bugs.webkit.org/attachment.cgi?id=311724&action=review > Source/JavaScriptCore/heap/FreeList.cpp:38 > + static_assert(MarkedBlock::blockSize <= (1u << (sizeof(FreeOffset) * 8)), "FreeList assumes that FreeOffset is big enough to express all possible block offsets"); Why 8? Why not MarkedBlock::atomSize? According to MarkedBlock::Handle::cellSize(), the cellSize is m_atomsPerCell * atomSize. That means the minimum cellSize is atomSize (which incidentally is 16 bytes). > Source/JavaScriptCore/heap/FreeList.cpp:46 > +FreeList::~FreeList() > +{ > +} Can we delete this since it does nothing? > Source/JavaScriptCore/heap/FreeList.h:-82 > - bool operator==(const FreeList& other) const > - { > - return head == other.head > - && payloadEnd == other.payloadEnd > - && remaining == other.remaining > - && originalSize == other.originalSize; > - } > - > - bool operator!=(const FreeList& other) const > - { > - return !(*this == other); > - } > - > - explicit operator bool() const > - { > - return *this != FreeList(); > - } Are these unused? Would you mind adding = delete versions of these in the private section just to make sure that we're not using the default versions of them unexpectedly? > Source/JavaScriptCore/heap/FreeList.h:43 > + ~FreeList(); Delete since it does nothing? > Source/JavaScriptCore/heap/FreeList.h:80 > + unsigned m_cellSize { UINT_MAX }; nit: can we group this with the other unsigneds below for better packing (though it happens to not matter right now because you have an odd number of unsigneds at the moment )? > Source/JavaScriptCore/heap/FreeList.h:84 > + unsigned m_listSize { 0 }; > + unsigned m_index { 0 }; nit: Why not make these of type FreeOffset since they should be bounded by FreeOffset, no? Oh wait ... is there an atomicity requirement that requires that these be 32-bit? Or is it just because it's bothersome to have the JIT code read/write a 16bit field?
Filip Pizlo
Comment 14 2017-06-01 11:45:05 PDT
(In reply to Oliver Hunt from comment #12) > View in context: > https://bugs.webkit.org/attachment.cgi?id=311728&action=review > > lgtm (with comments), but i'd obviously prefer someone more familiar with > ToT to actually r+ > > > Source/JavaScriptCore/heap/FreeList.cpp:71 > > + m_remaining = remaining; > > can you add a RELEASE_ASSERT(remaining % cellSize == 0 ) ? I suppose. > > > Source/JavaScriptCore/heap/FreeListInlines.h:43 > > + unsigned remaining = m_remaining; > > Can you see if making this Checked<unsigned> has a perf impact? This is > simply paranoia and the code does not obviously overflow, but i'm > increasingly paranoid about almost math these days :D I don't think we want to use Checked<> everywhere. This bump allocator is unchanged in this patch, so even if we did want to harden it, we'd want to do this in another patch. I wouldn't want to see that, though. This code is meant to be compact. > > > Source/JavaScriptCore/heap/FreeListInlines.h:47 > > + m_remaining = remaining; > > This being safe is dependent on remaining always being a multiple of > m_cellSize. Which has always been true. I'm not worried about that path. > > > Source/JavaScriptCore/heap/MarkedAllocator.cpp:159 > > + [] () -> HeapCell* { RELEASE_ASSERT_NOT_REACHED(); return nullptr; }); > > nice
Filip Pizlo
Comment 15 2017-06-01 11:49:35 PDT
(In reply to Mark Lam from comment #13) > Comment on attachment 311724 [details] > release builds and seems to pass some tests > > View in context: > https://bugs.webkit.org/attachment.cgi?id=311724&action=review > > > Source/JavaScriptCore/heap/FreeList.cpp:38 > > + static_assert(MarkedBlock::blockSize <= (1u << (sizeof(FreeOffset) * 8)), "FreeList assumes that FreeOffset is big enough to express all possible block offsets"); > > Why 8? Why not MarkedBlock::atomSize? According to > MarkedBlock::Handle::cellSize(), the cellSize is m_atomsPerCell * atomSize. > That means the minimum cellSize is atomSize (which incidentally is 16 bytes). sizeof(blah)*8 is a way of counting the bits in blah. This is counting the number of bits in FreeOffset, which is 16. The result is 16K, which is also blockSize. The point is: if we made blockSize any bigger, then a 16-bit offset wouldn't work anymore. > > > Source/JavaScriptCore/heap/FreeList.cpp:46 > > +FreeList::~FreeList() > > +{ > > +} > > Can we delete this since it does nothing? It deallocates the m_list, which is a unique_ptr. I like having those kinds of things get outlined. Makes debugging easier IMO. > > > Source/JavaScriptCore/heap/FreeList.h:-82 > > - bool operator==(const FreeList& other) const > > - { > > - return head == other.head > > - && payloadEnd == other.payloadEnd > > - && remaining == other.remaining > > - && originalSize == other.originalSize; > > - } > > - > > - bool operator!=(const FreeList& other) const > > - { > > - return !(*this == other); > > - } > > - > > - explicit operator bool() const > > - { > > - return *this != FreeList(); > > - } > > Are these unused? Would you mind adding = delete versions of these in the > private section just to make sure that we're not using the default versions > of them unexpectedly? Don't need to =delete them because these don't get defaults. > > > Source/JavaScriptCore/heap/FreeList.h:43 > > + ~FreeList(); > > Delete since it does nothing? > > > Source/JavaScriptCore/heap/FreeList.h:80 > > + unsigned m_cellSize { UINT_MAX }; > > nit: can we group this with the other unsigneds below for better packing > (though it happens to not matter right now because you have an odd number of > unsigneds at the moment )? Interesting, I'll look at this. > > > Source/JavaScriptCore/heap/FreeList.h:84 > > + unsigned m_listSize { 0 }; > > + unsigned m_index { 0 }; > > nit: Why not make these of type FreeOffset since they should be bounded by > FreeOffset, no? 32-bit is cheaper to load/store on x86 than 16-bit, just in the sense that 16-bit operations need the 16-bit prefix byte. So, I only use 16-bit for the array, since there we get a nice space savings. > > Oh wait ... is there an atomicity requirement that requires that these be > 32-bit? Or is it just because it's bothersome to have the JIT code > read/write a 16bit field? Yeah, the bothersome part. Specifically, code bloat.
Mark Lam
Comment 16 2017-06-01 11:58:38 PDT
Comment on attachment 311724 [details] release builds and seems to pass some tests View in context: https://bugs.webkit.org/attachment.cgi?id=311724&action=review >>> Source/JavaScriptCore/heap/FreeList.cpp:38 >>> + static_assert(MarkedBlock::blockSize <= (1u << (sizeof(FreeOffset) * 8)), "FreeList assumes that FreeOffset is big enough to express all possible block offsets"); >> >> Why 8? Why not MarkedBlock::atomSize? According to MarkedBlock::Handle::cellSize(), the cellSize is m_atomsPerCell * atomSize. That means the minimum cellSize is atomSize (which incidentally is 16 bytes). > > sizeof(blah)*8 is a way of counting the bits in blah. This is counting the number of bits in FreeOffset, which is 16. The result is 16K, which is also blockSize. The point is: if we made blockSize any bigger, then a 16-bit offset wouldn't work anymore. Oh, I totally misread that. Ignore me.
Filip Pizlo
Comment 17 2017-06-01 12:15:34 PDT
It looks like this is having some perf issues in splay. Investigating...
Filip Pizlo
Comment 18 2017-06-01 13:12:19 PDT
Created attachment 311747 [details] removed some pointer chasing It's not much faster though
Filip Pizlo
Comment 19 2017-06-01 13:30:14 PDT
Hmmmm. This might be a lost cause. I cannot seem to be able to get it to be fast on splay. I'm going to try a few more things...
Filip Pizlo
Comment 20 2017-06-01 13:41:06 PDT
Created attachment 311752 [details] switched to list-of-pointers instead of list-of-offsets Still slow
Filip Pizlo
Comment 21 2017-06-01 14:35:41 PDT
Created attachment 311759 [details] scrambled the free-list instead This *looks* like it will be perf-neutral!
Filip Pizlo
Comment 22 2017-06-01 15:38:55 PDT
Created attachment 311767 [details] the patch
Build Bot
Comment 23 2017-06-01 15:41:44 PDT
Attachment 311767 [details] did not pass style-queue: ERROR: Source/JavaScriptCore/heap/MarkedAllocator.cpp:159: More than one command on the same line [whitespace/newline] [4] Total errors found: 1 in 27 files If any of these errors are false positives, please file a bug against check-webkit-style.
Filip Pizlo
Comment 24 2017-06-01 15:44:18 PDT
Created attachment 311769 [details] the patch
Build Bot
Comment 25 2017-06-01 15:45:57 PDT
Attachment 311769 [details] did not pass style-queue: ERROR: Source/JavaScriptCore/heap/MarkedAllocator.cpp:159: More than one command on the same line [whitespace/newline] [4] Total errors found: 1 in 27 files If any of these errors are false positives, please file a bug against check-webkit-style.
Filip Pizlo
Comment 26 2017-06-01 17:03:22 PDT
Created attachment 311783 [details] the patch
Build Bot
Comment 27 2017-06-01 17:05:28 PDT
Attachment 311783 [details] did not pass style-queue: ERROR: Source/JavaScriptCore/heap/MarkedAllocator.cpp:159: More than one command on the same line [whitespace/newline] [4] Total errors found: 1 in 28 files If any of these errors are false positives, please file a bug against check-webkit-style.
Mark Lam
Comment 28 2017-06-01 17:13:52 PDT
Comment on attachment 311783 [details] the patch View in context: https://bugs.webkit.org/attachment.cgi?id=311783&action=review r=me > Source/JavaScriptCore/ChangeLog:3 > + GC should use a scrambled free-list Please update to match your changed bug title. > Source/JavaScriptCore/jit/AssemblyHelpers.h:1494 > + if (isX86()) > + xorPtr(Address(allocatorGPR, MarkedAllocator::offsetOfFreeList() + FreeList::offsetOfSecret()), resultGPR); > + else { > + loadPtr(Address(allocatorGPR, MarkedAllocator::offsetOfFreeList() + FreeList::offsetOfSecret()), scratchGPR); > + xorPtr(scratchGPR, resultGPR); > + } Do we still need to have this conditional on isX86() given that you've added the xorPtr impls for ARM64 and ARMv7? Maybe make it #if CPU(...) to be nice to other ports that don't have the xorPtr(Address src, RegisterID dest) impl yet? Otherwise, they get a build failure.
Filip Pizlo
Comment 29 2017-06-01 17:38:54 PDT
(In reply to Mark Lam from comment #28) > Comment on attachment 311783 [details] > the patch > > View in context: > https://bugs.webkit.org/attachment.cgi?id=311783&action=review > > r=me > > > Source/JavaScriptCore/ChangeLog:3 > > + GC should use a scrambled free-list > > Please update to match your changed bug title. > > > Source/JavaScriptCore/jit/AssemblyHelpers.h:1494 > > + if (isX86()) > > + xorPtr(Address(allocatorGPR, MarkedAllocator::offsetOfFreeList() + FreeList::offsetOfSecret()), resultGPR); > > + else { > > + loadPtr(Address(allocatorGPR, MarkedAllocator::offsetOfFreeList() + FreeList::offsetOfSecret()), scratchGPR); > > + xorPtr(scratchGPR, resultGPR); > > + } > > Do we still need to have this conditional on isX86() given that you've added > the xorPtr impls for ARM64 and ARMv7? Maybe make it #if CPU(...) to be nice > to other ports that don't have the xorPtr(Address src, RegisterID dest) impl > yet? Otherwise, they get a build failure. We need this because of the scratch register issue: this code cannot use the scratch register because it's called from FTL patchpoints that aren't marked as clobbering the scratch register. Most patchpoints don't behave this way. This one is special. The rest of this function uses "if" instead of "#if", so I just went with the style. That forced me to implement that function. I think that eventually we want all variants of these opcodes in all masms, so that for normal JIT code (which doesn't get called from the super special kinds of patchpoints) we can just say op(addr, reg).
Radar WebKit Bug Importer
Comment 30 2017-06-01 17:39:12 PDT
Mark Lam
Comment 31 2017-06-01 17:54:17 PDT
(In reply to Filip Pizlo from comment #29) > (In reply to Mark Lam from comment #28) > > > Source/JavaScriptCore/jit/AssemblyHelpers.h:1494 > > > + if (isX86()) > > > + xorPtr(Address(allocatorGPR, MarkedAllocator::offsetOfFreeList() + FreeList::offsetOfSecret()), resultGPR); > > > + else { > > > + loadPtr(Address(allocatorGPR, MarkedAllocator::offsetOfFreeList() + FreeList::offsetOfSecret()), scratchGPR); > > > + xorPtr(scratchGPR, resultGPR); > > > + } > > > > Do we still need to have this conditional on isX86() given that you've added > > the xorPtr impls for ARM64 and ARMv7? Maybe make it #if CPU(...) to be nice > > to other ports that don't have the xorPtr(Address src, RegisterID dest) impl > > yet? Otherwise, they get a build failure. > > We need this because of the scratch register issue: this code cannot use the > scratch register because it's called from FTL patchpoints that aren't marked > as clobbering the scratch register. Most patchpoints don't behave this way. > This one is special. > > The rest of this function uses "if" instead of "#if", so I just went with > the style. That forced me to implement that function. I think that > eventually we want all variants of these opcodes in all masms, so that for > normal JIT code (which doesn't get called from the super special kinds of > patchpoints) we can just say op(addr, reg). By scratch register, I presume you meant the dataTempRegister and not the scratchGPR in the code? Perhaps a comment to document this restriction would be good because it's not obvious from the code, and someone might come along later and break this code unknowingly.
Filip Pizlo
Comment 32 2017-06-02 08:58:23 PDT
(In reply to Mark Lam from comment #31) > (In reply to Filip Pizlo from comment #29) > > (In reply to Mark Lam from comment #28) > > > > Source/JavaScriptCore/jit/AssemblyHelpers.h:1494 > > > > + if (isX86()) > > > > + xorPtr(Address(allocatorGPR, MarkedAllocator::offsetOfFreeList() + FreeList::offsetOfSecret()), resultGPR); > > > > + else { > > > > + loadPtr(Address(allocatorGPR, MarkedAllocator::offsetOfFreeList() + FreeList::offsetOfSecret()), scratchGPR); > > > > + xorPtr(scratchGPR, resultGPR); > > > > + } > > > > > > Do we still need to have this conditional on isX86() given that you've added > > > the xorPtr impls for ARM64 and ARMv7? Maybe make it #if CPU(...) to be nice > > > to other ports that don't have the xorPtr(Address src, RegisterID dest) impl > > > yet? Otherwise, they get a build failure. > > > > We need this because of the scratch register issue: this code cannot use the > > scratch register because it's called from FTL patchpoints that aren't marked > > as clobbering the scratch register. Most patchpoints don't behave this way. > > This one is special. > > > > The rest of this function uses "if" instead of "#if", so I just went with > > the style. That forced me to implement that function. I think that > > eventually we want all variants of these opcodes in all masms, so that for > > normal JIT code (which doesn't get called from the super special kinds of > > patchpoints) we can just say op(addr, reg). > > By scratch register, I presume you meant the dataTempRegister and not the > scratchGPR in the code? Perhaps a comment to document this restriction > would be good because it's not obvious from the code, and someone might come > along later and break this code unknowingly. There already is a comment: // NOTE: This is carefully written so that we can call it while we disallow scratch // register usage.
Filip Pizlo
Comment 33 2017-06-02 09:00:09 PDT
Ryan Haddad
Comment 34 2017-06-02 10:52:25 PDT
Csaba Osztrogonác
Comment 35 2017-06-03 06:44:49 PDT
Guillaume Emont
Comment 36 2017-06-09 11:27:20 PDT
Build fix for MIPS provided in bug#173170
Note You need to log in before you can comment on or make changes to this bug.