1/*
2 * Copyright (C) 2013-2019 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
14 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23 * THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#pragma once
27
28#include "UnusedPointer.h"
29#include <wtf/UniqueArray.h>
30#include <wtf/Vector.h>
31#include <wtf/WeakRandom.h>
32
33namespace JSC {
34
35class Structure;
36
37#if USE(JSVALUE64)
38typedef uint32_t StructureID;
39
40inline StructureID nukedStructureIDBit()
41{
42 return 0x80000000u;
43}
44
45inline StructureID nuke(StructureID id)
46{
47 return id | nukedStructureIDBit();
48}
49
50inline bool isNuked(StructureID id)
51{
52 return !!(id & nukedStructureIDBit());
53}
54
55inline StructureID decontaminate(StructureID id)
56{
57 return id & ~nukedStructureIDBit();
58}
59#else // not USE(JSVALUE64)
60typedef Structure* StructureID;
61
62inline StructureID nukedStructureIDBit()
63{
64 return bitwise_cast<StructureID>(static_cast<uintptr_t>(1));
65}
66
67inline StructureID nuke(StructureID id)
68{
69 return bitwise_cast<StructureID>(bitwise_cast<uintptr_t>(id) | bitwise_cast<uintptr_t>(nukedStructureIDBit()));
70}
71
72inline bool isNuked(StructureID id)
73{
74 return !!(bitwise_cast<uintptr_t>(id) & bitwise_cast<uintptr_t>(nukedStructureIDBit()));
75}
76
77inline StructureID decontaminate(StructureID id)
78{
79 return bitwise_cast<StructureID>(bitwise_cast<uintptr_t>(id) & ~bitwise_cast<uintptr_t>(nukedStructureIDBit()));
80}
81#endif // not USE(JSVALUE64)
82
83#if USE(JSVALUE64)
84
85using EncodedStructureBits = uintptr_t;
86
87class StructureIDTable {
88 friend class LLIntOffsetsExtractor;
89public:
90 StructureIDTable();
91
92 void** base() { return reinterpret_cast<void**>(&m_table); }
93
94 bool isValid(StructureID);
95 Structure* get(StructureID);
96 void deallocateID(Structure*, StructureID);
97 StructureID allocateID(Structure*);
98
99 void flushOldTables();
100
101 size_t size() const { return m_size; }
102
103private:
104 void resize(size_t newCapacity);
105 void makeFreeListFromRange(uint32_t first, uint32_t last);
106
107 union StructureOrOffset {
108 WTF_MAKE_FAST_ALLOCATED;
109 public:
110 EncodedStructureBits encodedStructureBits;
111 StructureID offset;
112 };
113
114 StructureOrOffset* table() const { return m_table.get(); }
115 static Structure* decode(EncodedStructureBits, StructureID);
116 static EncodedStructureBits encode(Structure*, StructureID);
117
118 static constexpr size_t s_initialSize = 512;
119
120 Vector<UniqueArray<StructureOrOffset>> m_oldTables;
121
122 uint32_t m_firstFreeOffset { 0 };
123 uint32_t m_lastFreeOffset { 0 };
124 UniqueArray<StructureOrOffset> m_table;
125
126 size_t m_size { 0 };
127 size_t m_capacity;
128
129 WeakRandom m_weakRandom;
130
131 static constexpr StructureID s_unusedID = 0;
132
133public:
134 // 1. StructureID is encoded as:
135 //
136 // ----------------------------------------------------------------
137 // | 1 Nuke Bit | 24 StructureIDTable index bits | 7 entropy bits |
138 // ----------------------------------------------------------------
139 //
140 // The entropy bits are chosen at random and assigned when a StructureID
141 // is allocated.
142 //
143 // 2. For each StructureID, the StructureIDTable stores encodedStructureBits
144 // which are encoded from the structure pointer as such:
145 //
146 // ----------------------------------------------------------------
147 // | 7 entropy bits | 57 structure pointer bits |
148 // ----------------------------------------------------------------
149 //
150 // The entropy bits here are the same 7 bits used in the encoding of the
151 // StructureID for this structure entry in the StructureIDTable.
152
153 static constexpr uint32_t s_numberOfNukeBits = 1;
154 static constexpr uint32_t s_numberOfEntropyBits = 7;
155 static constexpr uint32_t s_entropyBitsShiftForStructurePointer = (sizeof(intptr_t) * 8) - s_numberOfEntropyBits;
156
157 static constexpr uint32_t s_maximumNumberOfStructures = 1 << (32 - s_numberOfEntropyBits - s_numberOfNukeBits);
158};
159
160ALWAYS_INLINE Structure* StructureIDTable::decode(EncodedStructureBits bits, StructureID structureID)
161{
162 return bitwise_cast<Structure*>(bits ^ (static_cast<uintptr_t>(structureID) << s_entropyBitsShiftForStructurePointer));
163}
164
165ALWAYS_INLINE EncodedStructureBits StructureIDTable::encode(Structure* structure, StructureID structureID)
166{
167 return bitwise_cast<EncodedStructureBits>(structure) ^ (static_cast<EncodedStructureBits>(structureID) << s_entropyBitsShiftForStructurePointer);
168}
169
170inline Structure* StructureIDTable::get(StructureID structureID)
171{
172 ASSERT_WITH_SECURITY_IMPLICATION(structureID);
173 ASSERT_WITH_SECURITY_IMPLICATION(!isNuked(structureID));
174 uint32_t structureIndex = structureID >> s_numberOfEntropyBits;
175 ASSERT_WITH_SECURITY_IMPLICATION(structureIndex < m_capacity);
176 return decode(table()[structureIndex].encodedStructureBits, structureID);
177}
178
179inline bool StructureIDTable::isValid(StructureID structureID)
180{
181 if (!structureID)
182 return false;
183 uint32_t structureIndex = structureID >> s_numberOfEntropyBits;
184 if (structureIndex >= m_capacity)
185 return false;
186#if CPU(ADDRESS64)
187 Structure* structure = decode(table()[structureIndex].encodedStructureBits, structureID);
188 if (reinterpret_cast<uintptr_t>(structure) >> s_entropyBitsShiftForStructurePointer)
189 return false;
190#endif
191 return true;
192}
193
194#else // not USE(JSVALUE64)
195
196class StructureIDTable {
197 friend class LLIntOffsetsExtractor;
198public:
199 StructureIDTable() = default;
200
201 Structure* get(StructureID structureID) { return structureID; }
202 void deallocateID(Structure*, StructureID) { }
203 StructureID allocateID(Structure* structure)
204 {
205 ASSERT(!isNuked(structure));
206 return structure;
207 };
208
209 void flushOldTables() { }
210};
211
212#endif // not USE(JSVALUE64)
213
214} // namespace JSC
215