runtime/SymbolTable.h

   1 /*
   2  * Copyright (C) 2007, 2008, 2012 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 Computer, 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 "JSObject.h"
  33 #include "Watchpoint.h"
  34 #include <wtf/HashTraits.h>
  35 #include <wtf/text/StringImpl.h>
  36
  37 namespace JSC {
  38
  39 class Watchpoint;
  40 class WatchpointSet;
  41
  42 struct SlowArgument {
  43     enum Status {
  44         Normal = 0,
  45         Captured = 1,
  46         Deleted = 2
  47     };
  48
  49     SlowArgument()
  50         : status(Normal)
  51         , index(0)
  52     {
  53     }
  54
  55     Status status;
  56     int index; // If status is 'Deleted', index is bogus.
  57 };
  58
  59 static ALWAYS_INLINE int missingSymbolMarker() { return std::numeric_limits<int>::max(); }
  60
  61 // The bit twiddling in this class assumes that every register index is a
  62 // reasonably small positive or negative number, and therefore has its high
  63 // four bits all set or all unset.
  64
  65 // In addition to implementing semantics-mandated variable attributes and
  66 // implementation-mandated variable indexing, this class also implements
  67 // watchpoints to be used for JIT optimizations. Because watchpoints are
  68 // meant to be relatively rare, this class optimizes heavily for the case
  69 // that they are not being used. To that end, this class uses the thin-fat
  70 // idiom: either it is thin, in which case it contains an in-place encoded
  71 // word that consists of attributes, the index, and a bit saying that it is
  72 // thin; or it is fat, in which case it contains a pointer to a malloc'd
  73 // data structure and a bit saying that it is fat. The malloc'd data
  74 // structure will be malloced a second time upon copy, to preserve the
  75 // property that in-place edits to SymbolTableEntry do not manifest in any
  76 // copies. However, the malloc'd FatEntry data structure contains a ref-
  77 // counted pointer to a shared WatchpointSet. Thus, in-place edits of the
  78 // WatchpointSet will manifest in all copies. Here's a picture:
  79 //
  80 // SymbolTableEntry --> FatEntry --> WatchpointSet
  81 //
  82 // If you make a copy of a SymbolTableEntry, you will have:
  83 //
  84 // original: SymbolTableEntry --> FatEntry --> WatchpointSet
  85 // copy:     SymbolTableEntry --> FatEntry -----^
  86
  87 struct SymbolTableEntry {
  88     // Use the SymbolTableEntry::Fast class, either via implicit cast or by calling
  89     // getFast(), when you (1) only care about isNull(), getIndex(), and isReadOnly(),
  90     // and (2) you are in a hot path where you need to minimize the number of times
  91     // that you branch on isFat() when getting the bits().
  92     class Fast {
  93     public:
  94         Fast()
  95             : m_bits(SlimFlag)
  96         {
  97         }
  98
  99         ALWAYS_INLINE Fast(const SymbolTableEntry& entry)
 100             : m_bits(entry.bits())
 101         {
 102         }
 103
 104         bool isNull() const
 105         {
 106             return !(m_bits & ~SlimFlag);
 107         }
 108
 109         int getIndex() const
 110         {
 111             return static_cast<int>(m_bits >> FlagBits);
 112         }
 113
 114         bool isReadOnly() const
 115         {
 116             return m_bits & ReadOnlyFlag;
 117         }
 118
 119         unsigned getAttributes() const
 120         {
 121             unsigned attributes = 0;
 122             if (m_bits & ReadOnlyFlag)
 123                 attributes |= ReadOnly;
 124             if (m_bits & DontEnumFlag)
 125                 attributes |= DontEnum;
 126             return attributes;
 127         }
 128
 129         bool isFat() const
 130         {
 131             return !(m_bits & SlimFlag);
 132         }
 133
 134     private:
 135         friend struct SymbolTableEntry;
 136         intptr_t m_bits;
 137     };
 138
 139     SymbolTableEntry()
 140         : m_bits(SlimFlag)
 141     {
 142     }
 143
 144     SymbolTableEntry(int index)
 145         : m_bits(SlimFlag)
 146     {
 147         ASSERT(isValidIndex(index));
 148         pack(index, false, false);
 149     }
 150
 151     SymbolTableEntry(int index, unsigned attributes)
 152         : m_bits(SlimFlag)
 153     {
 154         ASSERT(isValidIndex(index));
 155         pack(index, attributes & ReadOnly, attributes & DontEnum);
 156     }
 157
 158     ~SymbolTableEntry()
 159     {
 160         freeFatEntry();
 161     }
 162
 163     SymbolTableEntry(const SymbolTableEntry& other)
 164         : m_bits(SlimFlag)
 165     {
 166         *this = other;
 167     }
 168
 169     SymbolTableEntry& operator=(const SymbolTableEntry& other)
 170     {
 171         if (UNLIKELY(other.isFat()))
 172             return copySlow(other);
 173         freeFatEntry();
 174         m_bits = other.m_bits;
 175         return *this;
 176     }
 177
 178     bool isNull() const
 179     {
 180         return !(bits() & ~SlimFlag);
 181     }
 182
 183     int getIndex() const
 184     {
 185         return static_cast<int>(bits() >> FlagBits);
 186     }
 187
 188     ALWAYS_INLINE Fast getFast() const
 189     {
 190         return Fast(*this);
 191     }
 192
 193     ALWAYS_INLINE Fast getFast(bool& wasFat) const
 194     {
 195         Fast result;
 196         wasFat = isFat();
 197         if (wasFat)
 198             result.m_bits = fatEntry()->m_bits | SlimFlag;
 199         else
 200             result.m_bits = m_bits;
 201         return result;
 202     }
 203
 204     unsigned getAttributes() const
 205     {
 206         return getFast().getAttributes();
 207     }
 208
 209     void setAttributes(unsigned attributes)
 210     {
 211         pack(getIndex(), attributes & ReadOnly, attributes & DontEnum);
 212     }
 213
 214     bool isReadOnly() const
 215     {
 216         return bits() & ReadOnlyFlag;
 217     }
 218
 219     bool couldBeWatched();
 220
 221     // Notify an opportunity to create a watchpoint for a variable. This is
 222     // idempotent and fail-silent. It is idempotent in the sense that if
 223     // a watchpoint set had already been created, then another one will not
 224     // be created. Hence two calls to this method have the same effect as
 225     // one call. It is also fail-silent, in the sense that if a watchpoint
 226     // set had been created and had already been invalidated, then this will
 227     // just return. This means that couldBeWatched() may return false even
 228     // immediately after a call to attemptToWatch().
 229     void attemptToWatch();
 230
 231     bool* addressOfIsWatched();
 232
 233     void addWatchpoint(Watchpoint*);
 234
 235     WatchpointSet* watchpointSet()
 236     {
 237         return fatEntry()->m_watchpoints.get();
 238     }
 239
 240     ALWAYS_INLINE void notifyWrite()
 241     {
 242         if (LIKELY(!isFat()))
 243             return;
 244         notifyWriteSlow();
 245     }
 246
 247 private:
 248     static const intptr_t SlimFlag = 0x1;
 249     static const intptr_t ReadOnlyFlag = 0x2;
 250     static const intptr_t DontEnumFlag = 0x4;
 251     static const intptr_t NotNullFlag = 0x8;
 252     static const intptr_t FlagBits = 4;
 253
 254     class FatEntry {
 255         WTF_MAKE_FAST_ALLOCATED;
 256     public:
 257         FatEntry(intptr_t bits)
 258             : m_bits(bits & ~SlimFlag)
 259         {
 260         }
 261
 262         intptr_t m_bits; // always has FatFlag set and exactly matches what the bits would have been if this wasn't fat.
 263
 264         RefPtr<WatchpointSet> m_watchpoints;
 265     };
 266
 267     SymbolTableEntry& copySlow(const SymbolTableEntry&);
 268     JS_EXPORT_PRIVATE void notifyWriteSlow();
 269
 270     bool isFat() const
 271     {
 272         return !(m_bits & SlimFlag);
 273     }
 274
 275     const FatEntry* fatEntry() const
 276     {
 277         ASSERT(isFat());
 278         return bitwise_cast<const FatEntry*>(m_bits);
 279     }
 280
 281     FatEntry* fatEntry()
 282     {
 283         ASSERT(isFat());
 284         return bitwise_cast<FatEntry*>(m_bits);
 285     }
 286
 287     FatEntry* inflate()
 288     {
 289         if (LIKELY(isFat()))
 290             return fatEntry();
 291         return inflateSlow();
 292     }
 293
 294     FatEntry* inflateSlow();
 295
 296     ALWAYS_INLINE intptr_t bits() const
 297     {
 298         if (isFat())
 299             return fatEntry()->m_bits;
 300         return m_bits;
 301     }
 302
 303     ALWAYS_INLINE intptr_t& bits()
 304     {
 305         if (isFat())
 306             return fatEntry()->m_bits;
 307         return m_bits;
 308     }
 309
 310     void freeFatEntry()
 311     {
 312         if (LIKELY(!isFat()))
 313             return;
 314         freeFatEntrySlow();
 315     }
 316
 317     JS_EXPORT_PRIVATE void freeFatEntrySlow();
 318
 319     void pack(int index, bool readOnly, bool dontEnum)
 320     {
 321         ASSERT(!isFat());
 322         intptr_t& bitsRef = bits();
 323         bitsRef = (static_cast<intptr_t>(index) << FlagBits) | NotNullFlag | SlimFlag;
 324         if (readOnly)
 325             bitsRef |= ReadOnlyFlag;
 326         if (dontEnum)
 327             bitsRef |= DontEnumFlag;
 328     }
 329
 330     bool isValidIndex(int index)
 331     {
 332         return ((static_cast<intptr_t>(index) << FlagBits) >> FlagBits) == static_cast<intptr_t>(index);
 333     }
 334
 335     intptr_t m_bits;
 336 };
 337
 338 struct SymbolTableIndexHashTraits : HashTraits<SymbolTableEntry> {
 339     static const bool needsDestruction = true;
 340 };
 341
 342 typedef HashMap<RefPtr<StringImpl>, SymbolTableEntry, IdentifierRepHash, HashTraits<RefPtr<StringImpl> >, SymbolTableIndexHashTraits> SymbolTable;
 343
 344 class SharedSymbolTable : public JSCell, public SymbolTable {
 345 public:
 346     typedef JSCell Base;
 347
 348     static SharedSymbolTable* create(VM& vm)
 349     {
 350         SharedSymbolTable* sharedSymbolTable = new (NotNull, allocateCell<SharedSymbolTable>(vm.heap)) SharedSymbolTable(vm);
 351         sharedSymbolTable->finishCreation(vm);
 352         return sharedSymbolTable;
 353     }
 354     static const bool needsDestruction = true;
 355     static const bool hasImmortalStructure = true;
 356     static void destroy(JSCell*);
 357
 358     static Structure* createStructure(VM& vm, JSGlobalObject* globalObject, JSValue prototype)
 359     {
 360         return Structure::create(vm, globalObject, prototype, TypeInfo(LeafType, StructureFlags), &s_info);
 361     }
 362
 363     bool usesNonStrictEval() { return m_usesNonStrictEval; }
 364     void setUsesNonStrictEval(bool usesNonStrictEval) { m_usesNonStrictEval = usesNonStrictEval; }
 365
 366     int captureStart() { return m_captureStart; }
 367     void setCaptureStart(int captureStart) { m_captureStart = captureStart; }
 368
 369     int captureEnd() { return m_captureEnd; }
 370     void setCaptureEnd(int captureEnd) { m_captureEnd = captureEnd; }
 371
 372     int captureCount() { return m_captureEnd - m_captureStart; }
 373
 374     int parameterCount() { return m_parameterCountIncludingThis - 1; }
 375     int parameterCountIncludingThis() { return m_parameterCountIncludingThis; }
 376     void setParameterCountIncludingThis(int parameterCountIncludingThis) { m_parameterCountIncludingThis = parameterCountIncludingThis; }
 377
 378     // 0 if we don't capture any arguments; parameterCount() in length if we do.
 379     const SlowArgument* slowArguments() { return m_slowArguments.get(); }
 380     void setSlowArguments(PassOwnArrayPtr<SlowArgument> slowArguments) { m_slowArguments = slowArguments; }
 381
 382     static JS_EXPORTDATA const ClassInfo s_info;
 383
 384 private:
 385     SharedSymbolTable(VM& vm)
 386         : JSCell(vm, vm.sharedSymbolTableStructure.get())
 387         , m_parameterCountIncludingThis(0)
 388         , m_usesNonStrictEval(false)
 389         , m_captureStart(0)
 390         , m_captureEnd(0)
 391     {
 392     }
 393
 394     int m_parameterCountIncludingThis;
 395     bool m_usesNonStrictEval;
 396
 397     int m_captureStart;
 398     int m_captureEnd;
 399
 400     OwnArrayPtr<SlowArgument> m_slowArguments;
 401 };
 402
 403 } // namespace JSC
 404
 405 #endif // SymbolTable_h