1/*
2 * Copyright (C) 2009-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. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#pragma once
27
28#include "CommonIdentifiers.h"
29#include "Identifier.h"
30#include <array>
31#include <type_traits>
32#include <wtf/SegmentedVector.h>
33
34namespace JSC {
35
36 class ParserArenaDeletable;
37
38 class IdentifierArena {
39 WTF_MAKE_FAST_ALLOCATED;
40 public:
41 IdentifierArena()
42 {
43 clear();
44 }
45
46 template <typename T>
47 ALWAYS_INLINE const Identifier& makeIdentifier(VM&, const T* characters, size_t length);
48 ALWAYS_INLINE const Identifier& makeEmptyIdentifier(VM&);
49 ALWAYS_INLINE const Identifier& makeIdentifierLCharFromUChar(VM&, const UChar* characters, size_t length);
50 ALWAYS_INLINE const Identifier& makeIdentifier(VM&, SymbolImpl*);
51
52 const Identifier& makeNumericIdentifier(VM&, double number);
53
54 public:
55 static const int MaximumCachableCharacter = 128;
56 typedef SegmentedVector<Identifier, 64> IdentifierVector;
57 void clear()
58 {
59 m_identifiers.clear();
60 for (int i = 0; i < MaximumCachableCharacter; i++)
61 m_shortIdentifiers[i] = 0;
62 for (int i = 0; i < MaximumCachableCharacter; i++)
63 m_recentIdentifiers[i] = 0;
64 }
65
66 private:
67 IdentifierVector m_identifiers;
68 std::array<Identifier*, MaximumCachableCharacter> m_shortIdentifiers;
69 std::array<Identifier*, MaximumCachableCharacter> m_recentIdentifiers;
70 };
71
72 template <typename T>
73 ALWAYS_INLINE const Identifier& IdentifierArena::makeIdentifier(VM& vm, const T* characters, size_t length)
74 {
75 if (!length)
76 return vm.propertyNames->emptyIdentifier;
77 if (characters[0] >= MaximumCachableCharacter) {
78 m_identifiers.append(Identifier::fromString(vm, characters, length));
79 return m_identifiers.last();
80 }
81 if (length == 1) {
82 if (Identifier* ident = m_shortIdentifiers[characters[0]])
83 return *ident;
84 m_identifiers.append(Identifier::fromString(vm, characters, length));
85 m_shortIdentifiers[characters[0]] = &m_identifiers.last();
86 return m_identifiers.last();
87 }
88 Identifier* ident = m_recentIdentifiers[characters[0]];
89 if (ident && Identifier::equal(ident->impl(), characters, length))
90 return *ident;
91 m_identifiers.append(Identifier::fromString(vm, characters, length));
92 m_recentIdentifiers[characters[0]] = &m_identifiers.last();
93 return m_identifiers.last();
94 }
95
96 ALWAYS_INLINE const Identifier& IdentifierArena::makeIdentifier(VM&, SymbolImpl* symbol)
97 {
98 ASSERT(symbol);
99 m_identifiers.append(Identifier::fromUid(*symbol));
100 return m_identifiers.last();
101 }
102
103 ALWAYS_INLINE const Identifier& IdentifierArena::makeEmptyIdentifier(VM& vm)
104 {
105 return vm.propertyNames->emptyIdentifier;
106 }
107
108 ALWAYS_INLINE const Identifier& IdentifierArena::makeIdentifierLCharFromUChar(VM& vm, const UChar* characters, size_t length)
109 {
110 if (!length)
111 return vm.propertyNames->emptyIdentifier;
112 if (characters[0] >= MaximumCachableCharacter) {
113 m_identifiers.append(Identifier::createLCharFromUChar(vm, characters, length));
114 return m_identifiers.last();
115 }
116 if (length == 1) {
117 if (Identifier* ident = m_shortIdentifiers[characters[0]])
118 return *ident;
119 m_identifiers.append(Identifier::fromString(vm, characters, length));
120 m_shortIdentifiers[characters[0]] = &m_identifiers.last();
121 return m_identifiers.last();
122 }
123 Identifier* ident = m_recentIdentifiers[characters[0]];
124 if (ident && Identifier::equal(ident->impl(), characters, length))
125 return *ident;
126 m_identifiers.append(Identifier::createLCharFromUChar(vm, characters, length));
127 m_recentIdentifiers[characters[0]] = &m_identifiers.last();
128 return m_identifiers.last();
129 }
130
131 inline const Identifier& IdentifierArena::makeNumericIdentifier(VM& vm, double number)
132 {
133 // FIXME: Why doesn't this use the Identifier::from overload that takes a double?
134 // Seems we are missing out on multiple optimizations by not using it.
135 m_identifiers.append(Identifier::fromString(vm, String::number(number)));
136 return m_identifiers.last();
137 }
138
139 class ParserArena {
140 WTF_MAKE_NONCOPYABLE(ParserArena);
141 public:
142 ParserArena();
143 ~ParserArena();
144
145 void swap(ParserArena& otherArena)
146 {
147 std::swap(m_freeableMemory, otherArena.m_freeableMemory);
148 std::swap(m_freeablePoolEnd, otherArena.m_freeablePoolEnd);
149 m_identifierArena.swap(otherArena.m_identifierArena);
150 m_freeablePools.swap(otherArena.m_freeablePools);
151 m_deletableObjects.swap(otherArena.m_deletableObjects);
152 }
153
154 void* allocateFreeable(size_t size)
155 {
156 ASSERT(size);
157 ASSERT(size <= freeablePoolSize);
158 size_t alignedSize = alignSize(size);
159 ASSERT(alignedSize <= freeablePoolSize);
160 if (UNLIKELY(static_cast<size_t>(m_freeablePoolEnd - m_freeableMemory) < alignedSize))
161 allocateFreeablePool();
162 void* block = m_freeableMemory;
163 m_freeableMemory += alignedSize;
164 return block;
165 }
166
167 template<typename T, typename = std::enable_if_t<std::is_base_of<ParserArenaDeletable, T>::value>>
168 void* allocateDeletable(size_t size)
169 {
170 // T may extend ParserArenaDeletable via multiple inheritance, but not as T's first
171 // base class. m_deletableObjects is expecting pointers to objects of the shape of
172 // ParserArenaDeletable. We ensure this by allocating T, and casting it to
173 // ParserArenaDeletable to get the correct pointer to append to m_deletableObjects.
174 T* instance = static_cast<T*>(allocateFreeable(size));
175 ParserArenaDeletable* deletable = static_cast<ParserArenaDeletable*>(instance);
176 m_deletableObjects.append(deletable);
177 return instance;
178 }
179
180 IdentifierArena& identifierArena()
181 {
182 if (UNLIKELY (!m_identifierArena))
183 m_identifierArena = makeUnique<IdentifierArena>();
184 return *m_identifierArena;
185 }
186
187 private:
188 static const size_t freeablePoolSize = 8000;
189
190 static size_t alignSize(size_t size)
191 {
192 return (size + sizeof(WTF::AllocAlignmentInteger) - 1) & ~(sizeof(WTF::AllocAlignmentInteger) - 1);
193 }
194
195 void* freeablePool();
196 void allocateFreeablePool();
197 void deallocateObjects();
198
199 char* m_freeableMemory;
200 char* m_freeablePoolEnd;
201
202 std::unique_ptr<IdentifierArena> m_identifierArena;
203 Vector<void*> m_freeablePools;
204 Vector<ParserArenaDeletable*> m_deletableObjects;
205 };
206
207} // namespace JSC
208