1/*
2 * Copyright (C) 2007, 2008, 2012-2015 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 *
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * 3. Neither the name of Apple Inc. ("Apple") nor the names of
14 * its contributors may be used to endorse or promote products derived
15 * from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
18 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
19 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
20 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
21 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
23 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
24 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29#ifndef SymbolTable_h
30#define SymbolTable_h
31
32#include "ConcurrentJITLock.h"
33#include "ConstantMode.h"
34#include "InferredValue.h"
35#include "JSObject.h"
36#include "ScopedArgumentsTable.h"
37#include "TypeLocation.h"
38#include "VarOffset.h"
39#include "Watchpoint.h"
40#include <memory>
41#include <wtf/HashTraits.h>
42#include <wtf/text/UniquedStringImpl.h>
43
44namespace JSC {
45
46class SymbolTable;
47
48static ALWAYS_INLINE int missingSymbolMarker() { return std::numeric_limits<int>::max(); }
49
50// The bit twiddling in this class assumes that every register index is a
51// reasonably small positive or negative number, and therefore has its high
52// four bits all set or all unset.
53
54// In addition to implementing semantics-mandated variable attributes and
55// implementation-mandated variable indexing, this class also implements
56// watchpoints to be used for JIT optimizations. Because watchpoints are
57// meant to be relatively rare, this class optimizes heavily for the case
58// that they are not being used. To that end, this class uses the thin-fat
59// idiom: either it is thin, in which case it contains an in-place encoded
60// word that consists of attributes, the index, and a bit saying that it is
61// thin; or it is fat, in which case it contains a pointer to a malloc'd
62// data structure and a bit saying that it is fat. The malloc'd data
63// structure will be malloced a second time upon copy, to preserve the
64// property that in-place edits to SymbolTableEntry do not manifest in any
65// copies. However, the malloc'd FatEntry data structure contains a ref-
66// counted pointer to a shared WatchpointSet. Thus, in-place edits of the
67// WatchpointSet will manifest in all copies. Here's a picture:
68//
69// SymbolTableEntry --> FatEntry --> WatchpointSet
70//
71// If you make a copy of a SymbolTableEntry, you will have:
72//
73// original: SymbolTableEntry --> FatEntry --> WatchpointSet
74// copy: SymbolTableEntry --> FatEntry -----^
75
76struct SymbolTableEntry {
77private:
78 static VarOffset varOffsetFromBits(intptr_t bits)
79 {
80 VarKind kind;
81 intptr_t kindBits = bits & KindBitsMask;
82 if (kindBits <= UnwatchableScopeKindBits)
83 kind = VarKind::Scope;
84 else if (kindBits == StackKindBits)
85 kind = VarKind::Stack;
86 else
87 kind = VarKind::DirectArgument;
88 return VarOffset::assemble(kind, static_cast<int>(bits >> FlagBits));
89 }
90
91 static ScopeOffset scopeOffsetFromBits(intptr_t bits)
92 {
93 ASSERT((bits & KindBitsMask) <= UnwatchableScopeKindBits);
94 return ScopeOffset(static_cast<int>(bits >> FlagBits));
95 }
96
97public:
98
99 // Use the SymbolTableEntry::Fast class, either via implicit cast or by calling
100 // getFast(), when you (1) only care about isNull(), getIndex(), and isReadOnly(),
101 // and (2) you are in a hot path where you need to minimize the number of times
102 // that you branch on isFat() when getting the bits().
103 class Fast {
104 public:
105 Fast()
106 : m_bits(SlimFlag)
107 {
108 }
109
110 ALWAYS_INLINE Fast(const SymbolTableEntry& entry)
111 : m_bits(entry.bits())
112 {
113 }
114
115 bool isNull() const
116 {
117 return !(m_bits & ~SlimFlag);
118 }
119
120 VarOffset varOffset() const
121 {
122 return varOffsetFromBits(m_bits);
123 }
124
125 // Asserts if the offset is anything but a scope offset. This structures the assertions
126 // in a way that may result in better code, even in release, than doing
127 // varOffset().scopeOffset().
128 ScopeOffset scopeOffset() const
129 {
130 return scopeOffsetFromBits(m_bits);
131 }
132
133 bool isReadOnly() const
134 {
135 return m_bits & ReadOnlyFlag;
136 }
137
138 bool isDontEnum() const
139 {
140 return m_bits & DontEnumFlag;
141 }
142
143 unsigned getAttributes() const
144 {
145 unsigned attributes = 0;
146 if (isReadOnly())
147 attributes |= ReadOnly;
148 if (isDontEnum())
149 attributes |= DontEnum;
150 return attributes;
151 }
152
153 bool isFat() const
154 {
155 return !(m_bits & SlimFlag);
156 }
157
158 private:
159 friend struct SymbolTableEntry;
160 intptr_t m_bits;
161 };
162
163 SymbolTableEntry()
164 : m_bits(SlimFlag)
165 {
166 }
167
168 SymbolTableEntry(VarOffset offset)
169 : m_bits(SlimFlag)
170 {
171 ASSERT(isValidVarOffset(offset));
172 pack(offset, true, false, false);
173 }
174
175 SymbolTableEntry(VarOffset offset, unsigned attributes)
176 : m_bits(SlimFlag)
177 {
178 ASSERT(isValidVarOffset(offset));
179 pack(offset, true, attributes & ReadOnly, attributes & DontEnum);
180 }
181
182 ~SymbolTableEntry()
183 {
184 freeFatEntry();
185 }
186
187 SymbolTableEntry(const SymbolTableEntry& other)
188 : m_bits(SlimFlag)
189 {
190 *this = other;
191 }
192
193 SymbolTableEntry& operator=(const SymbolTableEntry& other)
194 {
195 if (UNLIKELY(other.isFat()))
196 return copySlow(other);
197 freeFatEntry();
198 m_bits = other.m_bits;
199 return *this;
200 }
201
202 bool isNull() const
203 {
204 return !(bits() & ~SlimFlag);
205 }
206
207 VarOffset varOffset() const
208 {
209 return varOffsetFromBits(bits());
210 }
211
212 bool isWatchable() const
213 {
214 return (m_bits & KindBitsMask) == ScopeKindBits;
215 }
216
217 // Asserts if the offset is anything but a scope offset. This structures the assertions
218 // in a way that may result in better code, even in release, than doing
219 // varOffset().scopeOffset().
220 ScopeOffset scopeOffset() const
221 {
222 return scopeOffsetFromBits(bits());
223 }
224
225 ALWAYS_INLINE Fast getFast() const
226 {
227 return Fast(*this);
228 }
229
230 ALWAYS_INLINE Fast getFast(bool& wasFat) const
231 {
232 Fast result;
233 wasFat = isFat();
234 if (wasFat)
235 result.m_bits = fatEntry()->m_bits | SlimFlag;
236 else
237 result.m_bits = m_bits;
238 return result;
239 }
240
241 unsigned getAttributes() const
242 {
243 return getFast().getAttributes();
244 }
245
246 void setAttributes(unsigned attributes)
247 {
248 pack(varOffset(), isWatchable(), attributes & ReadOnly, attributes & DontEnum);
249 }
250
251 bool isReadOnly() const
252 {
253 return bits() & ReadOnlyFlag;
254 }
255
256 ConstantMode constantMode() const
257 {
258 return modeForIsConstant(isReadOnly());
259 }
260
261 bool isDontEnum() const
262 {
263 return bits() & DontEnumFlag;
264 }
265
266 void disableWatching()
267 {
268 if (WatchpointSet* set = watchpointSet())
269 set->invalidate("Disabling watching in symbol table");
270 if (varOffset().isScope())
271 pack(varOffset(), false, isReadOnly(), isDontEnum());
272 }
273
274 void prepareToWatch();
275
276 void addWatchpoint(Watchpoint*);
277
278 // This watchpoint set is initialized clear, and goes through the following state transitions:
279 //
280 // First write to this var, in any scope that has this symbol table: Clear->IsWatched.
281 //
282 // Second write to this var, in any scope that has this symbol table: IsWatched->IsInvalidated.
283 //
284 // We ensure that we touch the set (i.e. trigger its state transition) after we do the write. This
285 // means that if you're in the compiler thread, and you:
286 //
287 // 1) Observe that the set IsWatched and commit to adding your watchpoint.
288 // 2) Load a value from any scope that has this watchpoint set.
289 //
290 // Then you can be sure that that value is either going to be the correct value for that var forever,
291 // or the watchpoint set will invalidate and you'll get fired.
292 //
293 // It's possible to write a program that first creates multiple scopes with the same var, and then
294 // initializes that var in just one of them. This means that a compilation could constant-fold to one
295 // of the scopes that still has an undefined value for this variable. That's fine, because at that
296 // point any write to any of the instances of that variable would fire the watchpoint.
297 WatchpointSet* watchpointSet()
298 {
299 if (!isFat())
300 return 0;
301 return fatEntry()->m_watchpoints.get();
302 }
303
304private:
305 static const intptr_t SlimFlag = 0x1;
306 static const intptr_t ReadOnlyFlag = 0x2;
307 static const intptr_t DontEnumFlag = 0x4;
308 static const intptr_t NotNullFlag = 0x8;
309 static const intptr_t KindBitsMask = 0x30;
310 static const intptr_t ScopeKindBits = 0x00;
311 static const intptr_t UnwatchableScopeKindBits = 0x10;
312 static const intptr_t StackKindBits = 0x20;
313 static const intptr_t DirectArgumentKindBits = 0x30;
314 static const intptr_t FlagBits = 6;
315
316 class FatEntry {
317 WTF_MAKE_FAST_ALLOCATED;
318 public:
319 FatEntry(intptr_t bits)
320 : m_bits(bits & ~SlimFlag)
321 {
322 }
323
324 intptr_t m_bits; // always has FatFlag set and exactly matches what the bits would have been if this wasn't fat.
325
326 RefPtr<WatchpointSet> m_watchpoints;
327 };
328
329 SymbolTableEntry& copySlow(const SymbolTableEntry&);
330 JS_EXPORT_PRIVATE void notifyWriteSlow(VM&, JSValue, const FireDetail&);
331
332 bool isFat() const
333 {
334 return !(m_bits & SlimFlag);
335 }
336
337 const FatEntry* fatEntry() const
338 {
339 ASSERT(isFat());
340 return bitwise_cast<const FatEntry*>(m_bits);
341 }
342
343 FatEntry* fatEntry()
344 {
345 ASSERT(isFat());
346 return bitwise_cast<FatEntry*>(m_bits);
347 }
348
349 FatEntry* inflate()
350 {
351 if (LIKELY(isFat()))
352 return fatEntry();
353 return inflateSlow();
354 }
355
356 FatEntry* inflateSlow();
357
358 ALWAYS_INLINE intptr_t bits() const
359 {
360 if (isFat())
361 return fatEntry()->m_bits;
362 return m_bits;
363 }
364
365 ALWAYS_INLINE intptr_t& bits()
366 {
367 if (isFat())
368 return fatEntry()->m_bits;
369 return m_bits;
370 }
371
372 void freeFatEntry()
373 {
374 if (LIKELY(!isFat()))
375 return;
376 freeFatEntrySlow();
377 }
378
379 JS_EXPORT_PRIVATE void freeFatEntrySlow();
380
381 void pack(VarOffset offset, bool isWatchable, bool readOnly, bool dontEnum)
382 {
383 ASSERT(!isFat());
384 intptr_t& bitsRef = bits();
385 bitsRef =
386 (static_cast<intptr_t>(offset.rawOffset()) << FlagBits) | NotNullFlag | SlimFlag;
387 if (readOnly)
388 bitsRef |= ReadOnlyFlag;
389 if (dontEnum)
390 bitsRef |= DontEnumFlag;
391 switch (offset.kind()) {
392 case VarKind::Scope:
393 if (isWatchable)
394 bitsRef |= ScopeKindBits;
395 else
396 bitsRef |= UnwatchableScopeKindBits;
397 break;
398 case VarKind::Stack:
399 bitsRef |= StackKindBits;
400 break;
401 case VarKind::DirectArgument:
402 bitsRef |= DirectArgumentKindBits;
403 break;
404 default:
405 RELEASE_ASSERT_NOT_REACHED();
406 break;
407 }
408 }
409
410 static bool isValidVarOffset(VarOffset offset)
411 {
412 return ((static_cast<intptr_t>(offset.rawOffset()) << FlagBits) >> FlagBits) == static_cast<intptr_t>(offset.rawOffset());
413 }
414
415 intptr_t m_bits;
416};
417
418struct SymbolTableIndexHashTraits : HashTraits<SymbolTableEntry> {
419 static const bool needsDestruction = true;
420};
421
422class SymbolTable final : public JSCell {
423public:
424 typedef JSCell Base;
425 static const unsigned StructureFlags = Base::StructureFlags | StructureIsImmortal;
426
427 typedef HashMap<RefPtr<UniquedStringImpl>, SymbolTableEntry, IdentifierRepHash, HashTraits<RefPtr<UniquedStringImpl>>, SymbolTableIndexHashTraits> Map;
428 typedef HashMap<RefPtr<UniquedStringImpl>, GlobalVariableID, IdentifierRepHash> UniqueIDMap;
429 typedef HashMap<RefPtr<UniquedStringImpl>, RefPtr<TypeSet>, IdentifierRepHash> UniqueTypeSetMap;
430 typedef HashMap<VarOffset, RefPtr<UniquedStringImpl>> OffsetToVariableMap;
431 typedef Vector<SymbolTableEntry*> LocalToEntryVec;
432
433 static SymbolTable* create(VM& vm)
434 {
435 SymbolTable* symbolTable = new (NotNull, allocateCell<SymbolTable>(vm.heap)) SymbolTable(vm);
436 symbolTable->finishCreation(vm);
437 return symbolTable;
438 }
439
440 static SymbolTable* createNameScopeTable(VM& vm, const Identifier& ident, unsigned attributes)
441 {
442 SymbolTable* result = create(vm);
443 result->add(ident.impl(), SymbolTableEntry(VarOffset(ScopeOffset(0)), attributes));
444 return result;
445 }
446
447 static const bool needsDestruction = true;
448 static void destroy(JSCell*);
449
450 static Structure* createStructure(VM& vm, JSGlobalObject* globalObject, JSValue prototype)
451 {
452 return Structure::create(vm, globalObject, prototype, TypeInfo(CellType, StructureFlags), info());
453 }
454
455 // You must hold the lock until after you're done with the iterator.
456 Map::iterator find(const ConcurrentJITLocker&, UniquedStringImpl* key)
457 {
458 return m_map.find(key);
459 }
460
461 Map::iterator find(const GCSafeConcurrentJITLocker&, UniquedStringImpl* key)
462 {
463 return m_map.find(key);
464 }
465
466 SymbolTableEntry get(const ConcurrentJITLocker&, UniquedStringImpl* key)
467 {
468 return m_map.get(key);
469 }
470
471 SymbolTableEntry get(UniquedStringImpl* key)
472 {
473 ConcurrentJITLocker locker(m_lock);
474 return get(locker, key);
475 }
476
477 SymbolTableEntry inlineGet(const ConcurrentJITLocker&, UniquedStringImpl* key)
478 {
479 return m_map.inlineGet(key);
480 }
481
482 SymbolTableEntry inlineGet(UniquedStringImpl* key)
483 {
484 ConcurrentJITLocker locker(m_lock);
485 return inlineGet(locker, key);
486 }
487
488 Map::iterator begin(const ConcurrentJITLocker&)
489 {
490 return m_map.begin();
491 }
492
493 Map::iterator end(const ConcurrentJITLocker&)
494 {
495 return m_map.end();
496 }
497
498 Map::iterator end(const GCSafeConcurrentJITLocker&)
499 {
500 return m_map.end();
501 }
502
503 size_t size(const ConcurrentJITLocker&) const
504 {
505 return m_map.size();
506 }
507
508 size_t size() const
509 {
510 ConcurrentJITLocker locker(m_lock);
511 return size(locker);
512 }
513
514 ScopeOffset maxScopeOffset() const
515 {
516 return m_maxScopeOffset;
517 }
518
519 void didUseScopeOffset(ScopeOffset offset)
520 {
521 if (!m_maxScopeOffset || m_maxScopeOffset < offset)
522 m_maxScopeOffset = offset;
523 }
524
525 void didUseVarOffset(VarOffset offset)
526 {
527 if (offset.isScope())
528 didUseScopeOffset(offset.scopeOffset());
529 }
530
531 unsigned scopeSize() const
532 {
533 ScopeOffset maxScopeOffset = this->maxScopeOffset();
534
535 // Do some calculation that relies on invalid scope offset plus one being zero.
536 unsigned fastResult = maxScopeOffset.offsetUnchecked() + 1;
537
538 // Assert that this works.
539 ASSERT(fastResult == (!maxScopeOffset ? 0 : maxScopeOffset.offset() + 1));
540
541 return fastResult;
542 }
543
544 ScopeOffset nextScopeOffset() const
545 {
546 return ScopeOffset(scopeSize());
547 }
548
549 ScopeOffset takeNextScopeOffset(const ConcurrentJITLocker&)
550 {
551 ScopeOffset result = nextScopeOffset();
552 m_maxScopeOffset = result;
553 return result;
554 }
555
556 ScopeOffset takeNextScopeOffset()
557 {
558 ConcurrentJITLocker locker(m_lock);
559 return takeNextScopeOffset(locker);
560 }
561
562 void add(const ConcurrentJITLocker&, UniquedStringImpl* key, const SymbolTableEntry& entry)
563 {
564 RELEASE_ASSERT(!m_localToEntry);
565 didUseVarOffset(entry.varOffset());
566 Map::AddResult result = m_map.add(key, entry);
567 ASSERT_UNUSED(result, result.isNewEntry);
568 }
569
570 void add(UniquedStringImpl* key, const SymbolTableEntry& entry)
571 {
572 ConcurrentJITLocker locker(m_lock);
573 add(locker, key, entry);
574 }
575
576 void set(const ConcurrentJITLocker&, UniquedStringImpl* key, const SymbolTableEntry& entry)
577 {
578 RELEASE_ASSERT(!m_localToEntry);
579 didUseVarOffset(entry.varOffset());
580 m_map.set(key, entry);
581 }
582
583 void set(UniquedStringImpl* key, const SymbolTableEntry& entry)
584 {
585 ConcurrentJITLocker locker(m_lock);
586 set(locker, key, entry);
587 }
588
589 bool contains(const ConcurrentJITLocker&, UniquedStringImpl* key)
590 {
591 return m_map.contains(key);
592 }
593
594 bool contains(UniquedStringImpl* key)
595 {
596 ConcurrentJITLocker locker(m_lock);
597 return contains(locker, key);
598 }
599
600 // The principle behind ScopedArgumentsTable modifications is that we will create one and
601 // leave it unlocked - thereby allowing in-place changes - until someone asks for a pointer to
602 // the table. Then, we will lock it. Then both our future changes and their future changes
603 // will first have to make a copy. This discipline means that usually when we create a
604 // ScopedArguments object, we don't have to make a copy of the ScopedArgumentsTable - instead
605 // we just take a reference to one that we already have.
606
607 uint32_t argumentsLength() const
608 {
609 if (!m_arguments)
610 return 0;
611 return m_arguments->length();
612 }
613
614 void setArgumentsLength(VM& vm, uint32_t length)
615 {
616 if (UNLIKELY(!m_arguments))
617 m_arguments.set(vm, this, ScopedArgumentsTable::create(vm));
618 m_arguments.set(vm, this, m_arguments->setLength(vm, length));
619 }
620
621 ScopeOffset argumentOffset(uint32_t i) const
622 {
623 ASSERT_WITH_SECURITY_IMPLICATION(m_arguments);
624 return m_arguments->get(i);
625 }
626
627 void setArgumentOffset(VM& vm, uint32_t i, ScopeOffset offset)
628 {
629 ASSERT_WITH_SECURITY_IMPLICATION(m_arguments);
630 m_arguments.set(vm, this, m_arguments->set(vm, i, offset));
631 }
632
633 ScopedArgumentsTable* arguments() const
634 {
635 if (!m_arguments)
636 return nullptr;
637 m_arguments->lock();
638 return m_arguments.get();
639 }
640
641 const LocalToEntryVec& localToEntry(const ConcurrentJITLocker&);
642 SymbolTableEntry* entryFor(const ConcurrentJITLocker&, ScopeOffset);
643
644 GlobalVariableID uniqueIDForVariable(const ConcurrentJITLocker&, UniquedStringImpl* key, VM&);
645 GlobalVariableID uniqueIDForOffset(const ConcurrentJITLocker&, VarOffset, VM&);
646 RefPtr<TypeSet> globalTypeSetForOffset(const ConcurrentJITLocker&, VarOffset, VM&);
647 RefPtr<TypeSet> globalTypeSetForVariable(const ConcurrentJITLocker&, UniquedStringImpl* key, VM&);
648
649 bool usesNonStrictEval() const { return m_usesNonStrictEval; }
650 void setUsesNonStrictEval(bool usesNonStrictEval) { m_usesNonStrictEval = usesNonStrictEval; }
651
652 bool isNestedLexicalScope() const { return m_nestedLexicalScope; }
653 void markIsNestedLexicalScope() { ASSERT(scopeType() == LexicalScope); m_nestedLexicalScope = true; }
654
655 enum ScopeType {
656 VarScope,
657 GlobalLexicalScope,
658 LexicalScope,
659 CatchScope,
660 FunctionNameScope
661 };
662 void setScopeType(ScopeType type) { m_scopeType = type; }
663 ScopeType scopeType() const { return static_cast<ScopeType>(m_scopeType); }
664
665 SymbolTable* cloneScopePart(VM&);
666
667 void prepareForTypeProfiling(const ConcurrentJITLocker&);
668
669 InferredValue* singletonScope() { return m_singletonScope.get(); }
670
671 static void visitChildren(JSCell*, SlotVisitor&);
672
673 DECLARE_EXPORT_INFO;
674
675private:
676 JS_EXPORT_PRIVATE SymbolTable(VM&);
677 ~SymbolTable();
678
679 JS_EXPORT_PRIVATE void finishCreation(VM&);
680
681 Map m_map;
682 ScopeOffset m_maxScopeOffset;
683
684 struct TypeProfilingRareData {
685 UniqueIDMap m_uniqueIDMap;
686 OffsetToVariableMap m_offsetToVariableMap;
687 UniqueTypeSetMap m_uniqueTypeSetMap;
688 };
689 std::unique_ptr<TypeProfilingRareData> m_typeProfilingRareData;
690
691 bool m_usesNonStrictEval : 1;
692 bool m_nestedLexicalScope : 1; // Non-function LexicalScope.
693 unsigned m_scopeType : 3; // ScopeType
694
695 WriteBarrier<ScopedArgumentsTable> m_arguments;
696 WriteBarrier<InferredValue> m_singletonScope;
697
698 std::unique_ptr<LocalToEntryVec> m_localToEntry;
699
700public:
701 mutable ConcurrentJITLock m_lock;
702};
703
704} // namespace JSC
705
706#endif // SymbolTable_h
707