Add some randomness into the StructureID.
authormark.lam@apple.com <mark.lam@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 26 Feb 2019 05:54:22 +0000 (05:54 +0000)
committermark.lam@apple.com <mark.lam@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 26 Feb 2019 05:54:22 +0000 (05:54 +0000)
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):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@242071 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp
Source/JavaScriptCore/heap/SlotVisitor.cpp
Source/JavaScriptCore/jit/AssemblyHelpers.cpp
Source/JavaScriptCore/jit/AssemblyHelpers.h
Source/JavaScriptCore/jit/SpecializedThunkJIT.h
Source/JavaScriptCore/llint/LowLevelInterpreter.asm
Source/JavaScriptCore/llint/LowLevelInterpreter64.asm
Source/JavaScriptCore/runtime/StructureIDTable.cpp
Source/JavaScriptCore/runtime/StructureIDTable.h

index fe4d36b..ed735f0 100644 (file)
@@ -1,3 +1,80 @@
+2019-02-25  Mark Lam  <mark.lam@apple.com>
+
+        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-25  Yusuke Suzuki  <ysuzuki@apple.com>
 
         [JSC] Revert r226885 to make SlotVisitor creation lazy
index f8a7912..a19f505 100644 (file)
@@ -16944,12 +16944,13 @@ private:
 
     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)
index 5908296..2b03d0a 100644 (file)
@@ -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 @@ void SlotVisitor::appendJSCellOrAuxiliary(HeapCell* heapCell)
         
 #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
     };
     
index 973fd3c..51bd547 100644 (file)
@@ -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::loadProperty(GPRReg object, GPRReg offset, JSValueRegs res
 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()
index 16e3620..b90856f 100644 (file)
@@ -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
@@ -1782,7 +1782,7 @@ public:
         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);
@@ -1791,7 +1791,7 @@ public:
     {
         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)
index 70666fa..102a43a 100644 (file)
@@ -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 @@ namespace JSC {
             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 = CallFrame::argumentOffset(argument);
index d86857d..479a167 100644 (file)
@@ -204,6 +204,11 @@ else
     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
index 7ba94b6..d86eae7 100644 (file)
@@ -530,16 +530,20 @@ macro writeBarrierOnGlobalLexicalEnvironment(size, get, valueFieldName)
         end)
 end
 
-macro structureIDToStructureWithScratch(structureIDThenStructure, scratch)
+macro structureIDToStructureWithScratch(structureIDThenStructure, scratch, scratch2)
     loadp CodeBlock[cfr], scratch
+    move structureIDThenStructure, scratch2
     loadp CodeBlock::m_vm[scratch], scratch
+    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)
+macro loadStructureWithScratch(cell, structure, scratch, scratch2)
     loadi JSCell::m_structureID[cell], structure
-    structureIDToStructureWithScratch(structure, scratch)
+    structureIDToStructureWithScratch(structure, scratch, scratch2)
 end
 
 # Entrypoints into the interpreter.
@@ -694,7 +698,7 @@ llintOpWithMetadata(op_to_this, OpToThis, macro (size, get, dispatch, metadata,
     loadq [cfr, t0, 8], t0
     btqnz t0, tagMask, .opToThisSlow
     bbneq JSCell::m_type[t0], FinalObjectType, .opToThisSlow
-    loadStructureWithScratch(t0, t1, t2)
+    loadStructureWithScratch(t0, t1, t2, t3)
     metadata(t2, t3)
     loadp OpToThis::Metadata::m_cachedStructure[t2], t2
     bpneq t1, t2, .opToThisSlow
@@ -764,7 +768,7 @@ macro equalNullComparisonOp(opcodeName, opcodeStruct, fn)
         move 0, t0
         jmp .done
     .masqueradesAsUndefined:
-        loadStructureWithScratch(t0, t2, t1)
+        loadStructureWithScratch(t0, t2, t1, t3)
         loadp CodeBlock[cfr], t0
         loadp CodeBlock::m_globalObject[t0], t0
         cpeq Structure::m_globalObject[t2], t0, t0
@@ -1182,7 +1186,7 @@ llintOpWithReturn(op_is_undefined, OpIsUndefined, macro (size, get, dispatch, re
     move ValueFalse, t1
     return(t1)
 .masqueradesAsUndefined:
-    loadStructureWithScratch(t0, t3, t1)
+    loadStructureWithScratch(t0, t3, t1, t2)
     loadp CodeBlock[cfr], t1
     loadp CodeBlock::m_globalObject[t1], t1
     cpeq Structure::m_globalObject[t3], t1, t0
@@ -1353,7 +1357,7 @@ llintOpWithMetadata(op_put_by_id, OpPutById, macro (size, get, dispatch, metadat
     loadp OpPutById::Metadata::m_structureChain[t5], t3
     btpz t3, .opPutByIdTransitionDirect
 
-    structureIDToStructureWithScratch(t2, t1)
+    structureIDToStructureWithScratch(t2, t1, t3)
 
     # reload the StructureChain since we used t3 as a scratch above
     loadp OpPutById::Metadata::m_structureChain[t5], t3
@@ -1691,7 +1695,7 @@ macro equalNullJumpOp(opcodeName, opcodeStruct, cellHandler, immediateHandler)
         assertNotConstant(size, t0)
         loadq [cfr, t0, 8], t0
         btqnz t0, tagMask, .immediate
-        loadStructureWithScratch(t0, t2, t1)
+        loadStructureWithScratch(t0, t2, t1, t3)
         cellHandler(t2, JSCell::m_flags[t0], .target)
         dispatch()
 
@@ -2214,7 +2218,7 @@ end)
 macro loadWithStructureCheck(opcodeStruct, get, slowPath)
     get(m_scope, t0)
     loadq [cfr, t0, 8], t0
-    loadStructureWithScratch(t0, t2, t1)
+    loadStructureWithScratch(t0, t2, t1, t3)
     loadp %opcodeStruct%::Metadata::m_structure[t5], t1
     bpneq t2, t1, slowPath
 end
index 67283a5..f2a87f1 100644 (file)
@@ -35,14 +35,14 @@ namespace JSC {
 
 StructureIDTable::StructureIDTable()
     : 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'.
-    table()[0].structure = nullptr;
+    table()[0].encodedStructureBits = 0;
 
     makeFreeListFromRange(1, m_capacity - 1);
-    ASSERT(m_size == m_capacity);
 }
 
 void StructureIDTable::makeFreeListFromRange(uint32_t first, uint32_t last)
@@ -95,11 +95,13 @@ void StructureIDTable::makeFreeListFromRange(uint32_t first, uint32_t last)
 
     m_firstFreeOffset = head;
     m_lastFreeOffset = tail;
-    m_size = m_capacity;
 }
 
 void StructureIDTable::resize(size_t newCapacity)
 {
+    if (newCapacity > s_maximumNumberOfStructures)
+        newCapacity = s_maximumNumberOfStructures;
+
     // Create the new table.
     auto newTable = makeUniqueArray<StructureOrOffset>(newCapacity);
 
@@ -128,22 +130,35 @@ void StructureIDTable::flushOldTables()
 
 StructureID StructureIDTable::allocateID(Structure* structure)
 {
-    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);
         ASSERT(m_firstFreeOffset);
     }
 
     ASSERT(m_firstFreeOffset != s_unusedID);
 
-    StructureID result = m_firstFreeOffset;
+    // 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;
+    }
+
+    uint32_t structureIndex = m_firstFreeOffset;
     m_firstFreeOffset = table()[m_firstFreeOffset].offset;
     if (!m_firstFreeOffset)
         m_lastFreeOffset = 0;
 
-    table()[result].structure = structure;
+    StructureID result = (structureIndex << s_numberOfEntropyBits) | entropyBits;
+    table()[structureIndex].encodedStructureBits = encode(structure, result);
+    m_size++;
     ASSERT(!isNuked(result));
     return result;
 }
@@ -151,23 +166,25 @@ StructureID StructureIDTable::allocateID(Structure* structure)
 void StructureIDTable::deallocateID(Structure* structure, StructureID structureID)
 {
     ASSERT(structureID != s_unusedID);
-    RELEASE_ASSERT(table()[structureID].structure == structure);
-
+    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()[structureID].offset = 0;
-        m_firstFreeOffset = structureID;
-        m_lastFreeOffset = structureID;
+        table()[structureIndex].offset = 0;
+        m_firstFreeOffset = structureIndex;
+        m_lastFreeOffset = structureIndex;
         return;
     }
 
     bool insertAtHead = m_weakRandom.getUint32() & 1;
     if (insertAtHead) {
-        table()[structureID].offset = m_firstFreeOffset;
-        m_firstFreeOffset = structureID;
+        table()[structureIndex].offset = m_firstFreeOffset;
+        m_firstFreeOffset = structureIndex;
     } else {
-        table()[structureID].offset = 0;
-        table()[m_lastFreeOffset].offset = structureID;
-        m_lastFreeOffset = structureID;
+        table()[structureIndex].offset = 0;
+        table()[m_lastFreeOffset].offset = structureIndex;
+        m_lastFreeOffset = structureIndex;
     }
 }
 
index 2a3a0f5..a520a69 100644 (file)
@@ -82,6 +82,8 @@ inline StructureID decontaminate(StructureID id)
 
 #if USE(JSVALUE64)
 
+using EncodedStructureBits = uintptr_t;
+
 class StructureIDTable {
     friend class LLIntOffsetsExtractor;
 public:
@@ -89,6 +91,7 @@ public:
 
     void** base() { return reinterpret_cast<void**>(&m_table); }
 
+    bool isValid(StructureID);
     Structure* get(StructureID);
     void deallocateID(Structure*, StructureID);
     StructureID allocateID(Structure*);
@@ -104,12 +107,14 @@ private:
     union StructureOrOffset {
         WTF_MAKE_FAST_ALLOCATED;
     public:
-        Structure* structure;
+        EncodedStructureBits encodedStructureBits;
         StructureID offset;
     };
 
     StructureOrOffset* table() const { return m_table.get(); }
-    
+    static Structure* decode(EncodedStructureBits, StructureID);
+    static EncodedStructureBits encode(Structure*, StructureID);
+
     static constexpr size_t s_initialSize = 512;
 
     Vector<UniqueArray<StructureOrOffset>> m_oldTables;
@@ -123,15 +128,65 @@ private:
 
     WeakRandom m_weakRandom;
 
-    static const StructureID s_unusedID = unusedPointer;
+    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 = 64 - s_numberOfEntropyBits;
+
+    static constexpr uint32_t s_maximumNumberOfStructures = 1 << (32 - s_numberOfEntropyBits - s_numberOfNukeBits);
 };
 
+ALWAYS_INLINE Structure* StructureIDTable::decode(EncodedStructureBits bits, StructureID structureID)
+{
+    return reinterpret_cast<Structure*>(bits ^ (static_cast<uintptr_t>(structureID) << s_entropyBitsShiftForStructurePointer));
+}
+
+ALWAYS_INLINE EncodedStructureBits StructureIDTable::encode(Structure* structure, StructureID structureID)
+{
+    return reinterpret_cast<EncodedStructureBits>(structure) ^ (static_cast<EncodedStructureBits>(structureID) << s_entropyBitsShiftForStructurePointer);
+}
+
 inline Structure* StructureIDTable::get(StructureID structureID)
 {
     ASSERT_WITH_SECURITY_IMPLICATION(structureID);
     ASSERT_WITH_SECURITY_IMPLICATION(!isNuked(structureID));
-    ASSERT_WITH_SECURITY_IMPLICATION(structureID < m_capacity);
-    return table()[structureID].structure;
+    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;
+    Structure* structure = decode(table()[structureIndex].encodedStructureBits, structureID);
+    if (reinterpret_cast<uintptr_t>(structure) >> s_entropyBitsShiftForStructurePointer)
+        return false;
+    return true;
 }
 
 #else // not USE(JSVALUE64)