Diff
Modified: branches/safari-607-branch/Source/_javascript_Core/ChangeLog (246422 => 246423)
--- branches/safari-607-branch/Source/_javascript_Core/ChangeLog 2019-06-14 02:54:53 UTC (rev 246422)
+++ branches/safari-607-branch/Source/_javascript_Core/ChangeLog 2019-06-14 02:59:16 UTC (rev 246423)
@@ -1,5 +1,143 @@
2019-06-13 Kocsen Chung <[email protected]>
+ Apply patch. rdar://problem/51656841
+
+ 2019-06-13 Mark Lam <[email protected]>
+
+ Misc cleanup in StructureIDTable after r242096.
+ https://bugs.webkit.org/show_bug.cgi?id=195063
+
+ Reviewed by Saam Barati.
+
+ * runtime/StructureIDTable.cpp:
+ (JSC::StructureIDTable::allocateID):
+ - RELEASE_ASSERT that the StructureID allocation will succeed.
+
+ * runtime/StructureIDTable.h:
+ (JSC::StructureIDTable::decode):
+ (JSC::StructureIDTable::encode):
+ - Add back a comment that Yusuke requested but was lost when the patch was rolled
+ out and relanded.
+ - Applied bitwise_casts that Saam requested.
+
+2019-02-26 Mark Lam <[email protected]>
+
+ [Re-landing] Add some randomness into the StructureID.
+ https://bugs.webkit.org/show_bug.cgi?id=194989
+ <rdar://problem/47975563>
+
+ Reviewed by Yusuke Suzuki.
+
+ 1. On 64-bit, the StructureID will now be encoded as:
+
+ ----------------------------------------------------------------
+ | 1 Nuke Bit | 24 StructureIDTable index bits | 7 entropy bits |
+ ----------------------------------------------------------------
+
+ The entropy bits are chosen at random and assigned when a StructureID is
+ allocated.
+
+ 2. Instead of Structure pointers, the StructureIDTable will now contain
+ encodedStructureBits, which is encoded as such:
+
+ ----------------------------------------------------------------
+ | 7 entropy bits | 57 structure pointer bits |
+ ----------------------------------------------------------------
+
+ The entropy bits here are the same 7 bits used in the encoding of the
+ StructureID for this structure entry in the StructureIDTable.
+
+ 3. Retrieval of the structure pointer given a StructureID is now computed as
+ follows:
+
+ index = structureID >> 7; // with arithmetic shift.
+ encodedStructureBits = structureIDTable[index];
+ structure = encodedStructureBits ^ (structureID << 57);
+
+ We use an arithmetic shift for the right shift because that will preserve
+ the nuke bit in the high bit of the index if the StructureID was not
+ decontaminated before use as expected.
+
+ 4. Remove unused function loadArgumentWithSpecificClass() in SpecializedThunkJIT.
+
+ 5. Define StructureIDTable::m_size to be the number of allocated StructureIDs
+ instead of always being the same as m_capacity.
+
+ 6. Change StructureIDTable::s_unusedID's value to 0.
+
+ Its previous value of unusedPointer i.e. 0xd1e7beef, does not make sense for
+ StructureID on 64-bit. Also, there was never any code that initializes unused
+ IDs to the s_unusedID. The only meaningful value for s_unusedID is 0, which
+ is the ID we'll get when the freelist is empty, prompting a resize of the
+ structureIDTable.
+
+ This patch appears to be perf neutral on JetStream 2 run via the cli on a
+ 11" MacBook Air, 13" MacBook Pro, iPhone 6S, and iPhone XR.
+
+ * ftl/FTLLowerDFGToB3.cpp:
+ (JSC::FTL::DFG::LowerDFGToB3::loadStructure):
+ * heap/SlotVisitor.cpp:
+ (JSC::SlotVisitor::appendJSCellOrAuxiliary):
+ * jit/AssemblyHelpers.cpp:
+ (JSC::AssemblyHelpers::emitLoadStructure):
+ * jit/AssemblyHelpers.h:
+ * jit/SpecializedThunkJIT.h:
+ (JSC::SpecializedThunkJIT::loadArgumentWithSpecificClass): Deleted.
+ * llint/LowLevelInterpreter.asm:
+ * llint/LowLevelInterpreter64.asm:
+ * runtime/StructureIDTable.cpp:
+ (JSC::StructureIDTable::StructureIDTable):
+ (JSC::StructureIDTable::makeFreeListFromRange):
+ (JSC::StructureIDTable::resize):
+ (JSC::StructureIDTable::allocateID):
+ (JSC::StructureIDTable::deallocateID):
+ * runtime/StructureIDTable.h:
+ (JSC::StructureIDTable::decode):
+ (JSC::StructureIDTable::encode):
+ (JSC::StructureIDTable::get):
+ (JSC::StructureIDTable::isValid):
+
+2019-02-13 Mark Lam <[email protected]>
+
+ Create a randomized free list for new StructureIDs on StructureIDTable resize.
+ https://bugs.webkit.org/show_bug.cgi?id=194566
+ <rdar://problem/47975502>
+
+ Reviewed by Michael Saboff.
+
+ Also isolate 32-bit implementation of StructureIDTable out more so the 64-bit
+ implementation is a little easier to read.
+
+ This patch appears to be perf neutral on JetStream2 (as run from the command line).
+
+ * runtime/StructureIDTable.cpp:
+ (JSC::StructureIDTable::StructureIDTable):
+ (JSC::StructureIDTable::makeFreeListFromRange):
+ (JSC::StructureIDTable::resize):
+ (JSC::StructureIDTable::allocateID):
+ (JSC::StructureIDTable::deallocateID):
+ * runtime/StructureIDTable.h:
+ (JSC::StructureIDTable::get):
+ (JSC::StructureIDTable::deallocateID):
+ (JSC::StructureIDTable::allocateID):
+ (JSC::StructureIDTable::flushOldTables):
+
+2019-02-11 Mark Lam <[email protected]>
+
+ Randomize insertion of deallocated StructureIDs into the StructureIDTable's free list.
+ https://bugs.webkit.org/show_bug.cgi?id=194512
+ <rdar://problem/47975465>
+
+ Reviewed by Yusuke Suzuki.
+
+ * runtime/StructureIDTable.cpp:
+ (JSC::StructureIDTable::StructureIDTable):
+ (JSC::StructureIDTable::allocateID):
+ (JSC::StructureIDTable::deallocateID):
+ * runtime/StructureIDTable.h:
+
+2019-06-13 Kocsen Chung <[email protected]>
+
Apply patch. rdar://problem/51656844
2019-06-13 Tadeu Zagallo <[email protected]>
Modified: branches/safari-607-branch/Source/_javascript_Core/ftl/FTLLowerDFGToB3.cpp (246422 => 246423)
--- branches/safari-607-branch/Source/_javascript_Core/ftl/FTLLowerDFGToB3.cpp 2019-06-14 02:54:53 UTC (rev 246422)
+++ branches/safari-607-branch/Source/_javascript_Core/ftl/FTLLowerDFGToB3.cpp 2019-06-14 02:59:16 UTC (rev 246423)
@@ -16928,12 +16928,13 @@
LValue loadStructure(LValue value)
{
- LValue tableIndex = m_out.load32(value, m_heaps.JSCell_structureID);
- LValue tableBase = m_out.loadPtr(
- m_out.absolute(vm().heap.structureIDTable().base()));
- TypedPointer address = m_out.baseIndex(
- m_heaps.structureTable, tableBase, m_out.zeroExtPtr(tableIndex));
- return m_out.loadPtr(address);
+ LValue structureID = m_out.load32(value, m_heaps.JSCell_structureID);
+ LValue tableBase = m_out.loadPtr(m_out.absolute(vm().heap.structureIDTable().base()));
+ LValue tableIndex = m_out.aShr(structureID, m_out.constInt32(StructureIDTable::s_numberOfEntropyBits));
+ LValue entropyBits = m_out.shl(m_out.zeroExtPtr(structureID), m_out.constInt32(StructureIDTable::s_entropyBitsShiftForStructurePointer));
+ TypedPointer address = m_out.baseIndex(m_heaps.structureTable, tableBase, m_out.zeroExtPtr(tableIndex));
+ LValue encodedStructureBits = m_out.loadPtr(address);
+ return m_out.bitXor(encodedStructureBits, entropyBits);
}
LValue weakPointer(JSCell* pointer)
Modified: branches/safari-607-branch/Source/_javascript_Core/heap/SlotVisitor.cpp (246422 => 246423)
--- branches/safari-607-branch/Source/_javascript_Core/heap/SlotVisitor.cpp 2019-06-14 02:54:53 UTC (rev 246422)
+++ branches/safari-607-branch/Source/_javascript_Core/heap/SlotVisitor.cpp 2019-06-14 02:59:16 UTC (rev 246423)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2012-2018 Apple Inc. All rights reserved.
+ * Copyright (C) 2012-2019 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -198,8 +198,8 @@
#if USE(JSVALUE64)
// This detects the worst of the badness.
- if (structureID >= heap()->structureIDTable().size())
- die("GC scan found corrupt object: structureID is out of bounds!\n");
+ if (!heap()->structureIDTable().isValid(structureID))
+ die("GC scan found corrupt object: structureID is invalid!\n");
#endif
};
Modified: branches/safari-607-branch/Source/_javascript_Core/jit/AssemblyHelpers.cpp (246422 => 246423)
--- branches/safari-607-branch/Source/_javascript_Core/jit/AssemblyHelpers.cpp 2019-06-14 02:54:53 UTC (rev 246422)
+++ branches/safari-607-branch/Source/_javascript_Core/jit/AssemblyHelpers.cpp 2019-06-14 02:59:16 UTC (rev 246423)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2011-2018 Apple Inc. All rights reserved.
+ * Copyright (C) 2011-2019 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -369,15 +369,30 @@
void AssemblyHelpers::emitLoadStructure(VM& vm, RegisterID source, RegisterID dest, RegisterID scratch)
{
#if USE(JSVALUE64)
+#if CPU(ARM64)
+ RegisterID scratch2 = dataTempRegister;
+#elif CPU(X86_64)
+ RegisterID scratch2 = scratchRegister();
+#else
+#error "Unsupported cpu"
+#endif
+
ASSERT(dest != scratch);
- load32(MacroAssembler::Address(source, JSCell::structureIDOffset()), dest);
+ ASSERT(dest != scratch2);
+ ASSERT(scratch != scratch2);
+
+ load32(MacroAssembler::Address(source, JSCell::structureIDOffset()), scratch2);
loadPtr(vm.heap.structureIDTable().base(), scratch);
+ rshift32(scratch2, TrustedImm32(StructureIDTable::s_numberOfEntropyBits), dest);
loadPtr(MacroAssembler::BaseIndex(scratch, dest, MacroAssembler::TimesEight), dest);
-#else
+ lshiftPtr(TrustedImm32(StructureIDTable::s_entropyBitsShiftForStructurePointer), scratch2);
+ xorPtr(scratch2, dest);
+#else // not USE(JSVALUE64)
UNUSED_PARAM(scratch);
+ UNUSED_PARAM(scratch2);
UNUSED_PARAM(vm);
loadPtr(MacroAssembler::Address(source, JSCell::structureIDOffset()), dest);
-#endif
+#endif // not USE(JSVALUE64)
}
void AssemblyHelpers::makeSpaceOnStackForCCall()
Modified: branches/safari-607-branch/Source/_javascript_Core/jit/AssemblyHelpers.h (246422 => 246423)
--- branches/safari-607-branch/Source/_javascript_Core/jit/AssemblyHelpers.h 2019-06-14 02:54:53 UTC (rev 246422)
+++ branches/safari-607-branch/Source/_javascript_Core/jit/AssemblyHelpers.h 2019-06-14 02:59:16 UTC (rev 246423)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2011-2018 Apple Inc. All rights reserved.
+ * Copyright (C) 2011-2019 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -1781,7 +1781,7 @@
storePtr(TrustedImmPtr(nullptr), Address(resultGPR, JSObject::butterflyOffset()));
}
- JumpList branchIfValue(VM&, JSValueRegs value, GPRReg scratch, GPRReg scratchIfShouldCheckMasqueradesAsUndefined, FPRReg, FPRReg, bool shouldCheckMasqueradesAsUndefined, JSGlobalObject*, bool negateResult);
+ JumpList branchIfValue(VM&, JSValueRegs, GPRReg scratch, GPRReg scratchIfShouldCheckMasqueradesAsUndefined, FPRReg, FPRReg, bool shouldCheckMasqueradesAsUndefined, JSGlobalObject*, bool negateResult);
JumpList branchIfTruthy(VM& vm, JSValueRegs value, GPRReg scratch, GPRReg scratchIfShouldCheckMasqueradesAsUndefined, FPRReg scratchFPR0, FPRReg scratchFPR1, bool shouldCheckMasqueradesAsUndefined, JSGlobalObject* globalObject)
{
return branchIfValue(vm, value, scratch, scratchIfShouldCheckMasqueradesAsUndefined, scratchFPR0, scratchFPR1, shouldCheckMasqueradesAsUndefined, globalObject, false);
@@ -1790,7 +1790,7 @@
{
return branchIfValue(vm, value, scratch, scratchIfShouldCheckMasqueradesAsUndefined, scratchFPR0, scratchFPR1, shouldCheckMasqueradesAsUndefined, globalObject, true);
}
- void emitConvertValueToBoolean(VM&, JSValueRegs value, GPRReg result, GPRReg scratchIfShouldCheckMasqueradesAsUndefined, FPRReg, FPRReg, bool shouldCheckMasqueradesAsUndefined, JSGlobalObject*, bool negateResult = false);
+ void emitConvertValueToBoolean(VM&, JSValueRegs, GPRReg result, GPRReg scratchIfShouldCheckMasqueradesAsUndefined, FPRReg, FPRReg, bool shouldCheckMasqueradesAsUndefined, JSGlobalObject*, bool negateResult = false);
template<typename ClassType>
void emitAllocateDestructibleObject(VM& vm, GPRReg resultGPR, Structure* structure, GPRReg scratchGPR1, GPRReg scratchGPR2, JumpList& slowPath)
Modified: branches/safari-607-branch/Source/_javascript_Core/jit/SpecializedThunkJIT.h (246422 => 246423)
--- branches/safari-607-branch/Source/_javascript_Core/jit/SpecializedThunkJIT.h 2019-06-14 02:54:53 UTC (rev 246422)
+++ branches/safari-607-branch/Source/_javascript_Core/jit/SpecializedThunkJIT.h 2019-06-14 02:59:16 UTC (rev 246423)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2010-2018 Apple Inc. All rights reserved.
+ * Copyright (C) 2010-2019 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -71,15 +71,6 @@
m_failures.append(branchIfNotString(dst));
}
- void loadArgumentWithSpecificClass(const ClassInfo* classInfo, int argument, RegisterID dst, RegisterID scratch)
- {
- loadCellArgument(argument, dst);
- emitLoadStructure(*vm(), dst, scratch, dst);
- appendFailure(branchPtr(NotEqual, Address(scratch, Structure::classInfoOffset()), TrustedImmPtr(PoisonedClassInfoPtr(classInfo).bits())));
- // We have to reload the argument since emitLoadStructure clobbered it.
- loadCellArgument(argument, dst);
- }
-
void loadInt32Argument(int argument, RegisterID dst, Jump& failTarget)
{
unsigned src = ""
Modified: branches/safari-607-branch/Source/_javascript_Core/llint/LowLevelInterpreter.asm (246422 => 246423)
--- branches/safari-607-branch/Source/_javascript_Core/llint/LowLevelInterpreter.asm 2019-06-14 02:54:53 UTC (rev 246422)
+++ branches/safari-607-branch/Source/_javascript_Core/llint/LowLevelInterpreter.asm 2019-06-14 02:59:16 UTC (rev 246423)
@@ -204,6 +204,11 @@
const LowestTag = constexpr JSValue::LowestTag
end
+if JSVALUE64
+ const NumberOfStructureIDEntropyBits = constexpr StructureIDTable::s_numberOfEntropyBits
+ const StructureEntropyBitsShift = constexpr StructureIDTable::s_entropyBitsShiftForStructurePointer
+end
+
const CallOpCodeSize = constexpr op_call_length
const maxFrameExtentForSlowPathCall = constexpr maxFrameExtentForSlowPathCall
Modified: branches/safari-607-branch/Source/_javascript_Core/llint/LowLevelInterpreter64.asm (246422 => 246423)
--- branches/safari-607-branch/Source/_javascript_Core/llint/LowLevelInterpreter64.asm 2019-06-14 02:54:53 UTC (rev 246422)
+++ branches/safari-607-branch/Source/_javascript_Core/llint/LowLevelInterpreter64.asm 2019-06-14 02:59:16 UTC (rev 246423)
@@ -535,8 +535,12 @@
loadp CodeBlock[cfr], scratch
loadp CodeBlock::m_poisonedVM[scratch], scratch
unpoison(_g_CodeBlockPoison, scratch, scratch2)
+ move structureIDThenStructure, scratch2
+ rshifti NumberOfStructureIDEntropyBits, scratch2
loadp VM::heap + Heap::m_structureIDTable + StructureIDTable::m_table[scratch], scratch
- loadp [scratch, structureIDThenStructure, PtrSize], structureIDThenStructure
+ loadp [scratch, scratch2, PtrSize], scratch2
+ lshiftp StructureEntropyBitsShift, structureIDThenStructure
+ xorp scratch2, structureIDThenStructure
end
macro loadStructureWithScratch(cell, structure, scratch, scratch2)
@@ -1175,7 +1179,7 @@
move ValueFalse, t1
return(t1)
.masqueradesAsUndefined:
- loadStructureWithScratch(t0, t3, t1, t5)
+ loadStructureWithScratch(t0, t3, t1, t2)
loadp CodeBlock[cfr], t1
loadp CodeBlock::m_globalObject[t1], t1
cpeq Structure::m_globalObject[t3], t1, t0
Modified: branches/safari-607-branch/Source/_javascript_Core/runtime/StructureIDTable.cpp (246422 => 246423)
--- branches/safari-607-branch/Source/_javascript_Core/runtime/StructureIDTable.cpp 2019-06-14 02:54:53 UTC (rev 246422)
+++ branches/safari-607-branch/Source/_javascript_Core/runtime/StructureIDTable.cpp 2019-06-14 02:59:16 UTC (rev 246423)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2013 Apple Inc. All rights reserved.
+ * Copyright (C) 2013-2019 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -31,19 +31,77 @@
namespace JSC {
+#if USE(JSVALUE64)
+
StructureIDTable::StructureIDTable()
- : m_firstFreeOffset(0)
- , m_table(makeUniqueArray<StructureOrOffset>(s_initialSize))
- , m_size(0)
+ : m_table(makeUniqueArray<StructureOrOffset>(s_initialSize))
+ , m_size(1)
, m_capacity(s_initialSize)
{
// We pre-allocate the first offset so that the null Structure
// can still be represented as the StructureID '0'.
- allocateID(0);
+ table()[0].encodedStructureBits = 0;
+
+ makeFreeListFromRange(1, m_capacity - 1);
}
+void StructureIDTable::makeFreeListFromRange(uint32_t first, uint32_t last)
+{
+ ASSERT(!m_firstFreeOffset);
+ ASSERT(!m_lastFreeOffset);
+
+ // Put all the new IDs on the free list sequentially.
+ uint32_t head = first;
+ uint32_t tail = last;
+ for (uint32_t i = first; i < last; ++i)
+ table()[i].offset = i + 1;
+ table()[last].offset = 0;
+
+ // Randomize the free list.
+ uint32_t size = last - first + 1;
+ uint32_t maxIterations = (size * 2) / 3;
+ for (uint32_t count = 0; count < maxIterations; ++count) {
+ // Move a random pick either to the head or the tail of the free list.
+ uint32_t random = m_weakRandom.getUint32();
+ uint32_t nodeBefore = first + (random % size);
+ uint32_t pick = table()[nodeBefore].offset;
+ if (pick) {
+ uint32_t nodeAfter = table()[pick].offset;
+ table()[nodeBefore].offset = nodeAfter;
+ if ((random & 1) || !nodeAfter) {
+ // Move to the head.
+ table()[pick].offset = head;
+ head = pick;
+ if (!nodeAfter)
+ tail = nodeBefore;
+ } else {
+ // Move to the tail.
+ table()[pick].offset = 0;
+ table()[tail].offset = pick;
+ tail = pick;
+ }
+ }
+ }
+
+ // Cut list in half and swap halves.
+ uint32_t cut = first + (m_weakRandom.getUint32() % size);
+ uint32_t afterCut = table()[cut].offset;
+ if (afterCut) {
+ table()[tail].offset = head;
+ tail = cut;
+ head = afterCut;
+ table()[cut].offset = 0;
+ }
+
+ m_firstFreeOffset = head;
+ m_lastFreeOffset = tail;
+}
+
void StructureIDTable::resize(size_t newCapacity)
{
+ if (newCapacity > s_maximumNumberOfStructures)
+ newCapacity = s_maximumNumberOfStructures;
+
// Create the new table.
auto newTable = makeUniqueArray<StructureOrOffset>(newCapacity);
@@ -61,6 +119,8 @@
// Update the capacity.
m_capacity = newCapacity;
+
+ makeFreeListFromRange(m_size, m_capacity - 1);
}
void StructureIDTable::flushOldTables()
@@ -70,52 +130,62 @@
StructureID StructureIDTable::allocateID(Structure* structure)
{
-#if USE(JSVALUE64)
- if (!m_firstFreeOffset) {
- RELEASE_ASSERT(m_capacity <= UINT_MAX);
- if (m_size == m_capacity)
- resize(m_capacity * 2);
+ if (UNLIKELY(!m_firstFreeOffset)) {
+ RELEASE_ASSERT(m_capacity <= s_maximumNumberOfStructures);
+ ASSERT(m_size == m_capacity);
+ resize(m_capacity * 2);
ASSERT(m_size < m_capacity);
+ RELEASE_ASSERT(m_firstFreeOffset);
+ }
- StructureOrOffset newEntry;
- newEntry.structure = structure;
-
- if (m_size == s_unusedID) {
- m_size++;
- return allocateID(structure);
- }
-
- StructureID result = m_size;
- table()[result] = newEntry;
- m_size++;
- ASSERT(!isNuked(result));
- return result;
+ // entropyBits must not be zero. This ensures that if a corrupted
+ // structureID is encountered (with incorrect entropyBits), the decoded
+ // structure pointer for that ID will be always be a bad pointer with
+ // high bits set.
+ constexpr uint32_t entropyBitsMask = (1 << s_numberOfEntropyBits) - 1;
+ uint32_t entropyBits = m_weakRandom.getUint32() & entropyBitsMask;
+ if (UNLIKELY(!entropyBits)) {
+ constexpr uint32_t numberOfValuesToPickFrom = entropyBitsMask;
+ entropyBits = (m_weakRandom.getUint32() % numberOfValuesToPickFrom) + 1;
}
- ASSERT(m_firstFreeOffset != s_unusedID);
+ uint32_t structureIndex = m_firstFreeOffset;
+ m_firstFreeOffset = table()[m_firstFreeOffset].offset;
+ if (!m_firstFreeOffset)
+ m_lastFreeOffset = 0;
- StructureID result = m_firstFreeOffset;
- m_firstFreeOffset = table()[m_firstFreeOffset].offset;
- table()[result].structure = structure;
+ StructureID result = (structureIndex << s_numberOfEntropyBits) | entropyBits;
+ table()[structureIndex].encodedStructureBits = encode(structure, result);
+ m_size++;
ASSERT(!isNuked(result));
return result;
-#else
- ASSERT(!isNuked(structure));
- return structure;
-#endif
}
void StructureIDTable::deallocateID(Structure* structure, StructureID structureID)
{
-#if USE(JSVALUE64)
ASSERT(structureID != s_unusedID);
- RELEASE_ASSERT(table()[structureID].structure == structure);
- table()[structureID].offset = m_firstFreeOffset;
- m_firstFreeOffset = structureID;
-#else
- UNUSED_PARAM(structure);
- UNUSED_PARAM(structureID);
-#endif
+ uint32_t structureIndex = structureID >> s_numberOfEntropyBits;
+ ASSERT(structureIndex && structureIndex < s_maximumNumberOfStructures);
+ RELEASE_ASSERT(table()[structureIndex].encodedStructureBits == encode(structure, structureID));
+ m_size--;
+ if (!m_firstFreeOffset) {
+ table()[structureIndex].offset = 0;
+ m_firstFreeOffset = structureIndex;
+ m_lastFreeOffset = structureIndex;
+ return;
+ }
+
+ bool insertAtHead = m_weakRandom.getUint32() & 1;
+ if (insertAtHead) {
+ table()[structureIndex].offset = m_firstFreeOffset;
+ m_firstFreeOffset = structureIndex;
+ } else {
+ table()[structureIndex].offset = 0;
+ table()[m_lastFreeOffset].offset = structureIndex;
+ m_lastFreeOffset = structureIndex;
+ }
}
+#endif // USE(JSVALUE64)
+
} // namespace JSC
Modified: branches/safari-607-branch/Source/_javascript_Core/runtime/StructureIDTable.h (246422 => 246423)
--- branches/safari-607-branch/Source/_javascript_Core/runtime/StructureIDTable.h 2019-06-14 02:54:53 UTC (rev 246422)
+++ branches/safari-607-branch/Source/_javascript_Core/runtime/StructureIDTable.h 2019-06-14 02:59:16 UTC (rev 246423)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2013 Apple Inc. All rights reserved.
+ * Copyright (C) 2013-2019 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -28,6 +28,7 @@
#include "UnusedPointer.h"
#include <wtf/UniqueArray.h>
#include <wtf/Vector.h>
+#include <wtf/WeakRandom.h>
namespace JSC {
@@ -55,7 +56,7 @@
{
return id & ~nukedStructureIDBit();
}
-#else
+#else // not USE(JSVALUE64)
typedef Structure* StructureID;
inline StructureID nukedStructureIDBit()
@@ -77,8 +78,12 @@
{
return bitwise_cast<StructureID>(bitwise_cast<uintptr_t>(id) & ~bitwise_cast<uintptr_t>(nukedStructureIDBit()));
}
-#endif
+#endif // not USE(JSVALUE64)
+#if USE(JSVALUE64)
+
+using EncodedStructureBits = uintptr_t;
+
class StructureIDTable {
friend class LLIntOffsetsExtractor;
public:
@@ -86,6 +91,7 @@
void** base() { return reinterpret_cast<void**>(&m_table); }
+ bool isValid(StructureID);
Structure* get(StructureID);
void deallocateID(Structure*, StructureID);
StructureID allocateID(Structure*);
@@ -96,41 +102,114 @@
private:
void resize(size_t newCapacity);
+ void makeFreeListFromRange(uint32_t first, uint32_t last);
union StructureOrOffset {
WTF_MAKE_FAST_ALLOCATED;
public:
- Structure* structure;
+ EncodedStructureBits encodedStructureBits;
StructureID offset;
};
StructureOrOffset* table() const { return m_table.get(); }
- static const size_t s_initialSize = 256;
+ static Structure* decode(EncodedStructureBits, StructureID);
+ static EncodedStructureBits encode(Structure*, StructureID);
+ static constexpr size_t s_initialSize = 512;
+
Vector<UniqueArray<StructureOrOffset>> m_oldTables;
- uint32_t m_firstFreeOffset;
+ uint32_t m_firstFreeOffset { 0 };
+ uint32_t m_lastFreeOffset { 0 };
UniqueArray<StructureOrOffset> m_table;
- size_t m_size;
+ size_t m_size { 0 };
size_t m_capacity;
-#if USE(JSVALUE64)
- static const StructureID s_unusedID = unusedPointer;
-#endif
+ WeakRandom m_weakRandom;
+
+ static constexpr StructureID s_unusedID = 0;
+
+public:
+ // 1. StructureID is encoded as:
+ //
+ // ----------------------------------------------------------------
+ // | 1 Nuke Bit | 24 StructureIDTable index bits | 7 entropy bits |
+ // ----------------------------------------------------------------
+ //
+ // The entropy bits are chosen at random and assigned when a StructureID
+ // is allocated.
+ //
+ // 2. For each StructureID, the StructureIDTable stores encodedStructureBits
+ // which are encoded from the structure pointer as such:
+ //
+ // ----------------------------------------------------------------
+ // | 7 entropy bits | 57 structure pointer bits |
+ // ----------------------------------------------------------------
+ //
+ // The entropy bits here are the same 7 bits used in the encoding of the
+ // StructureID for this structure entry in the StructureIDTable.
+
+ static constexpr uint32_t s_numberOfNukeBits = 1;
+ static constexpr uint32_t s_numberOfEntropyBits = 7;
+ static constexpr uint32_t s_entropyBitsShiftForStructurePointer = (sizeof(intptr_t) * 8) - s_numberOfEntropyBits;
+
+ static constexpr uint32_t s_maximumNumberOfStructures = 1 << (32 - s_numberOfEntropyBits - s_numberOfNukeBits);
};
+ALWAYS_INLINE Structure* StructureIDTable::decode(EncodedStructureBits bits, StructureID structureID)
+{
+ return bitwise_cast<Structure*>(bits ^ (static_cast<uintptr_t>(structureID) << s_entropyBitsShiftForStructurePointer));
+}
+
+ALWAYS_INLINE EncodedStructureBits StructureIDTable::encode(Structure* structure, StructureID structureID)
+{
+ return bitwise_cast<EncodedStructureBits>(structure) ^ (static_cast<EncodedStructureBits>(structureID) << s_entropyBitsShiftForStructurePointer);
+}
+
inline Structure* StructureIDTable::get(StructureID structureID)
{
-#if USE(JSVALUE64)
ASSERT_WITH_SECURITY_IMPLICATION(structureID);
ASSERT_WITH_SECURITY_IMPLICATION(!isNuked(structureID));
- ASSERT_WITH_SECURITY_IMPLICATION(structureID < m_capacity);
- return table()[structureID].structure;
-#else
- return structureID;
+ uint32_t structureIndex = structureID >> s_numberOfEntropyBits;
+ ASSERT_WITH_SECURITY_IMPLICATION(structureIndex < m_capacity);
+ return decode(table()[structureIndex].encodedStructureBits, structureID);
+}
+
+inline bool StructureIDTable::isValid(StructureID structureID)
+{
+ if (!structureID)
+ return false;
+ uint32_t structureIndex = structureID >> s_numberOfEntropyBits;
+ if (structureIndex >= m_capacity)
+ return false;
+#if CPU(ADDRESS64)
+ Structure* structure = decode(table()[structureIndex].encodedStructureBits, structureID);
+ if (reinterpret_cast<uintptr_t>(structure) >> s_entropyBitsShiftForStructurePointer)
+ return false;
#endif
+ return true;
}
+#else // not USE(JSVALUE64)
+
+class StructureIDTable {
+ friend class LLIntOffsetsExtractor;
+public:
+ StructureIDTable() = default;
+
+ Structure* get(StructureID structureID) { return structureID; }
+ void deallocateID(Structure*, StructureID) { }
+ StructureID allocateID(Structure* structure)
+ {
+ ASSERT(!isNuked(structure));
+ return structure;
+ };
+
+ void flushOldTables() { }
+};
+
+#endif // not USE(JSVALUE64)
+
} // namespace JSC
