WebKit Bugzilla
New
Browse
Log In
×
Sign in with GitHub
or
Remember my login
Create Account
·
Forgot Password
Forgotten password account recovery
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
Details
Formatted Diff
Diff
more
(37.61 KB, patch)
2017-06-01 09:17 PDT
,
Filip Pizlo
no flags
Details
Formatted Diff
Diff
it grows
(44.20 KB, patch)
2017-06-01 09:53 PDT
,
Filip Pizlo
no flags
Details
Formatted Diff
Diff
compiles in debug and runs some simple code
(53.89 KB, patch)
2017-06-01 10:32 PDT
,
Filip Pizlo
no flags
Details
Formatted Diff
Diff
release builds and seems to pass some tests
(54.38 KB, patch)
2017-06-01 10:41 PDT
,
Filip Pizlo
no flags
Details
Formatted Diff
Diff
the patch
(54.45 KB, patch)
2017-06-01 11:05 PDT
,
Filip Pizlo
no flags
Details
Formatted Diff
Diff
the patch
(54.42 KB, patch)
2017-06-01 11:22 PDT
,
Filip Pizlo
no flags
Details
Formatted Diff
Diff
removed some pointer chasing
(55.22 KB, patch)
2017-06-01 13:12 PDT
,
Filip Pizlo
no flags
Details
Formatted Diff
Diff
switched to list-of-pointers instead of list-of-offsets
(54.87 KB, patch)
2017-06-01 13:41 PDT
,
Filip Pizlo
no flags
Details
Formatted Diff
Diff
scrambled the free-list instead
(57.47 KB, patch)
2017-06-01 14:35 PDT
,
Filip Pizlo
no flags
Details
Formatted Diff
Diff
the patch
(57.47 KB, patch)
2017-06-01 15:38 PDT
,
Filip Pizlo
no flags
Details
Formatted Diff
Diff
the patch
(57.82 KB, patch)
2017-06-01 15:44 PDT
,
Filip Pizlo
no flags
Details
Formatted Diff
Diff
the patch
(58.39 KB, patch)
2017-06-01 17:03 PDT
,
Filip Pizlo
mark.lam
: review+
Details
Formatted Diff
Diff
Show Obsolete
(12)
View All
Add attachment
proposed patch, testcase, etc.
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
Created
attachment 311709
[details]
more
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
<
rdar://problem/32526204
>
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
Landed in
http://trac.webkit.org/changeset/217711/webkit
Ryan Haddad
Comment 34
2017-06-02 10:52:25 PDT
iOS build fix in
https://trac.webkit.org/changeset/217717/webkit
Csaba Osztrogonác
Comment 35
2017-06-03 06:44:49 PDT
And ARM buildfix landed in
https://trac.webkit.org/changeset/217756/webkit
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.
Top of Page
Format For Printing
XML
Clone This Bug