Home | History | Annotate | Download | only in heap
      1 /*
      2  * Copyright (C) 2013 Google 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 are
      6  * met:
      7  *
      8  *     * Redistributions of source code must retain the above copyright
      9  * notice, this list of conditions and the following disclaimer.
     10  *     * Redistributions in binary form must reproduce the above
     11  * copyright notice, this list of conditions and the following disclaimer
     12  * in the documentation and/or other materials provided with the
     13  * distribution.
     14  *     * Neither the name of Google Inc. nor the names of its
     15  * contributors may be used to endorse or promote products derived from
     16  * this software without specific prior written permission.
     17  *
     18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
     19  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
     20  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
     21  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
     22  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
     23  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
     24  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     25  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
     26  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
     28  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     29  */
     30 
     31 #ifndef Heap_h
     32 #define Heap_h
     33 
     34 #include "heap/HeapExport.h"
     35 #include "heap/Visitor.h"
     36 
     37 #include "wtf/Assertions.h"
     38 
     39 #include <stdint.h>
     40 
     41 namespace WebCore {
     42 
     43 // ASAN integration defintions
     44 #if COMPILER(CLANG)
     45 #define USE_ASAN (__has_feature(address_sanitizer) || defined(__SANITIZE_ADDRESS__))
     46 #else
     47 #define USE_ASAN 0
     48 #endif
     49 
     50 #if USE_ASAN
     51 extern "C" {
     52     // Marks memory region [addr, addr+size) as unaddressable.
     53     // This memory must be previously allocated by the user program. Accessing
     54     // addresses in this region from instrumented code is forbidden until
     55     // this region is unpoisoned. This function is not guaranteed to poison
     56     // the whole region - it may poison only subregion of [addr, addr+size) due
     57     // to ASan alignment restrictions.
     58     // Method is NOT thread-safe in the sense that no two threads can
     59     // (un)poison memory in the same memory region simultaneously.
     60     void __asan_poison_memory_region(void const volatile*, size_t);
     61     // Marks memory region [addr, addr+size) as addressable.
     62     // This memory must be previously allocated by the user program. Accessing
     63     // addresses in this region is allowed until this region is poisoned again.
     64     // This function may unpoison a superregion of [addr, addr+size) due to
     65     // ASan alignment restrictions.
     66     // Method is NOT thread-safe in the sense that no two threads can
     67     // (un)poison memory in the same memory region simultaneously.
     68     void __asan_unpoison_memory_region(void const volatile*, size_t);
     69 
     70     // User code should use macros instead of functions.
     71 #define ASAN_POISON_MEMORY_REGION(addr, size)   \
     72     __asan_poison_memory_region((addr), (size))
     73 #define ASAN_UNPOISON_MEMORY_REGION(addr, size) \
     74     __asan_unpoison_memory_region((addr), (size))
     75 #define NO_SANITIZE_ADDRESS __attribute__((no_sanitize_address))
     76     const size_t asanMagic = 0xabefeed0;
     77     const size_t asanDeferMemoryReuseCount = 2;
     78     const size_t asanDeferMemoryReuseMask = 0x3;
     79 }
     80 #else
     81 #define ASAN_POISON_MEMORY_REGION(addr, size)   \
     82     ((void)(addr), (void)(size))
     83 #define ASAN_UNPOISON_MEMORY_REGION(addr, size) \
     84     ((void)(addr), (void)(size))
     85 #define NO_SANITIZE_ADDRESS
     86 #endif
     87 
     88 const size_t blinkPageSizeLog2 = 17;
     89 const size_t blinkPageSize = 1 << blinkPageSizeLog2;
     90 const size_t blinkPageOffsetMask = blinkPageSize - 1;
     91 const size_t blinkPageBaseMask = ~blinkPageOffsetMask;
     92 // Double precision floats are more efficient when 8 byte aligned, so we 8 byte
     93 // align all allocations even on 32 bit.
     94 const size_t allocationGranularity = 8;
     95 const size_t allocationMask = allocationGranularity - 1;
     96 const size_t objectStartBitMapSize = (blinkPageSize + ((8 * allocationGranularity) - 1)) / (8 * allocationGranularity);
     97 const size_t reservedForObjectBitMap = ((objectStartBitMapSize + allocationMask) & ~allocationMask);
     98 const size_t maxHeapObjectSize = 1 << 27;
     99 
    100 const size_t markBitMask = 1;
    101 const size_t freeListMask = 2;
    102 const size_t debugBitMask = 4;
    103 const size_t sizeMask = ~7;
    104 const uint8_t freelistZapValue = 42;
    105 const uint8_t finalizedZapValue = 24;
    106 
    107 typedef uint8_t* Address;
    108 
    109 class PageMemory;
    110 
    111 size_t osPageSize();
    112 
    113 #ifndef NDEBUG
    114 // Sanity check for a page header address: the address of the page
    115 // header should be OS page size away from being Blink page size
    116 // aligned.
    117 inline bool isPageHeaderAddress(Address address)
    118 {
    119     return !((reinterpret_cast<uintptr_t>(address) & blinkPageOffsetMask) - osPageSize());
    120 }
    121 #endif
    122 
    123 // Common header for heap pages.
    124 class BaseHeapPage {
    125 public:
    126     BaseHeapPage(PageMemory* storage, const GCInfo* gcInfo)
    127         : m_storage(storage)
    128         , m_gcInfo(gcInfo)
    129     {
    130         ASSERT(isPageHeaderAddress(reinterpret_cast<Address>(this)));
    131     }
    132 
    133     // Check if the given address could point to an object in this
    134     // heap page. If so, find the start of that object and mark it
    135     // using the given Visitor.
    136     //
    137     // Returns true if the object was found and marked, returns false
    138     // otherwise.
    139     //
    140     // This is used during conservative stack scanning to
    141     // conservatively mark all objects that could be referenced from
    142     // the stack.
    143     virtual bool checkAndMarkPointer(Visitor*, Address) = 0;
    144 
    145     Address address() { return reinterpret_cast<Address>(this); }
    146     PageMemory* storage() const { return m_storage; }
    147     const GCInfo* gcInfo() { return m_gcInfo; }
    148 
    149 private:
    150     PageMemory* m_storage;
    151     // The BaseHeapPage contains three pointers (vtable, m_storage,
    152     // and m_gcInfo) and therefore not 8 byte aligned on 32 bit
    153     // architectures. Force 8 byte alignment with a union.
    154     union {
    155         const GCInfo* m_gcInfo;
    156         uint64_t m_ensureAligned;
    157     };
    158 };
    159 
    160 COMPILE_ASSERT(!(sizeof(BaseHeapPage) % allocationGranularity), BaseHeapPage_should_be_8_byte_aligned);
    161 
    162 // Large allocations are allocated as separate objects and linked in a
    163 // list.
    164 //
    165 // In order to use the same memory allocation routines for everything
    166 // allocated in the heap, large objects are considered heap pages
    167 // containing only one object.
    168 //
    169 // The layout of a large heap object is as follows:
    170 //
    171 // | BaseHeapPage | next pointer | FinalizedHeapObjectHeader or HeapObjectHeader | payload |
    172 template<typename Header>
    173 class LargeHeapObject : public BaseHeapPage {
    174 public:
    175     LargeHeapObject(PageMemory* storage, const GCInfo* gcInfo) : BaseHeapPage(storage, gcInfo) { }
    176 
    177     virtual bool checkAndMarkPointer(Visitor*, Address);
    178 
    179     void link(LargeHeapObject<Header>** previousNext)
    180     {
    181         m_next = *previousNext;
    182         *previousNext = this;
    183     }
    184 
    185     void unlink(LargeHeapObject<Header>** previousNext)
    186     {
    187         *previousNext = m_next;
    188     }
    189 
    190     bool contains(Address object)
    191     {
    192         return (address() <= object) && (object <= (address() + size()));
    193     }
    194 
    195     LargeHeapObject<Header>* next()
    196     {
    197         return m_next;
    198     }
    199 
    200     size_t size()
    201     {
    202         return heapObjectHeader()->size() + sizeof(LargeHeapObject<Header>);
    203     }
    204 
    205     Address payload() { return heapObjectHeader()->payload(); }
    206     size_t payloadSize() { return heapObjectHeader()->payloadSize(); }
    207 
    208     Header* heapObjectHeader()
    209     {
    210         Address headerAddress = address() + sizeof(LargeHeapObject<Header>);
    211         return reinterpret_cast<Header*>(headerAddress);
    212     }
    213 
    214     bool isMarked();
    215     void unmark();
    216     // FIXME: Add back when HeapStats have been added.
    217     // void getStats(HeapStats&);
    218     void mark(Visitor*);
    219     void finalize();
    220 
    221 private:
    222     friend class Heap;
    223     // FIXME: Add back when ThreadHeap has been added.
    224     // friend class ThreadHeap<Header>;
    225 
    226     LargeHeapObject<Header>* m_next;
    227 };
    228 
    229 // The BasicObjectHeader is the minimal object header. It is used when
    230 // encountering heap space of size allocationGranularity to mark it as
    231 // as freelist entry.
    232 class BasicObjectHeader {
    233 public:
    234     NO_SANITIZE_ADDRESS
    235     explicit BasicObjectHeader(size_t encodedSize)
    236         : m_size(encodedSize) { }
    237 
    238     static size_t freeListEncodedSize(size_t size) { return size | freeListMask; }
    239 
    240     NO_SANITIZE_ADDRESS
    241     bool isFree() { return m_size & freeListMask; }
    242 
    243     NO_SANITIZE_ADDRESS
    244     size_t size() const { return m_size & sizeMask; }
    245 
    246 protected:
    247     size_t m_size;
    248 };
    249 
    250 // Our heap object layout is layered with the HeapObjectHeader closest
    251 // to the payload, this can be wrapped in a FinalizedObjectHeader if the
    252 // object is on the GeneralHeap and not on a specific TypedHeap.
    253 // Finally if the object is a large object (> blinkPageSize/2) then it is
    254 // wrapped with a LargeObjectHeader.
    255 //
    256 // Object memory layout:
    257 // [ LargeObjectHeader | ] [ FinalizedObjectHeader | ] HeapObjectHeader | payload
    258 // The [ ] notation denotes that the LargeObjectHeader and the FinalizedObjectHeader
    259 // are independently optional.
    260 class HeapObjectHeader : public BasicObjectHeader {
    261 public:
    262     NO_SANITIZE_ADDRESS
    263     explicit HeapObjectHeader(size_t encodedSize)
    264         : BasicObjectHeader(encodedSize)
    265 #ifndef NDEBUG
    266         , m_magic(magic)
    267 #endif
    268     { }
    269 
    270     NO_SANITIZE_ADDRESS
    271     HeapObjectHeader(size_t encodedSize, const GCInfo*)
    272         : BasicObjectHeader(encodedSize)
    273 #ifndef NDEBUG
    274         , m_magic(magic)
    275 #endif
    276     { }
    277 
    278     inline void checkHeader() const;
    279     inline bool isMarked() const;
    280 
    281     inline void mark();
    282     inline void unmark();
    283 
    284     inline Address payload();
    285     inline size_t payloadSize();
    286     inline Address payloadEnd();
    287 
    288     inline void setDebugMark();
    289     inline void clearDebugMark();
    290     inline bool hasDebugMark() const;
    291 
    292     // Zap magic number with a new magic number that means there was once an
    293     // object allocated here, but it was freed because nobody marked it during
    294     // GC.
    295     void zapMagic();
    296 
    297     static void finalize(const GCInfo*, Address, size_t);
    298     static HeapObjectHeader* fromPayload(const void*);
    299 
    300     static const intptr_t magic = 0xc0de247;
    301     static const intptr_t zappedMagic = 0xC0DEdead;
    302     // The zap value for vtables should be < 4K to ensure it cannot be
    303     // used for dispatch.
    304     static const intptr_t zappedVTable = 0xd0d;
    305 
    306 private:
    307 #ifndef NDEBUG
    308     intptr_t m_magic;
    309 #endif
    310 };
    311 
    312 const size_t objectHeaderSize = sizeof(HeapObjectHeader);
    313 
    314 NO_SANITIZE_ADDRESS
    315 void HeapObjectHeader::checkHeader() const
    316 {
    317     // FIXME: with ThreadLocalHeaps Heap::contains is not thread safe
    318     // but introducing locks in this place does not seem like a good
    319     // idea.
    320 #ifndef NDEBUG
    321     ASSERT(m_magic == magic);
    322 #endif
    323 }
    324 
    325 Address HeapObjectHeader::payload()
    326 {
    327     return reinterpret_cast<Address>(this) + objectHeaderSize;
    328 }
    329 
    330 size_t HeapObjectHeader::payloadSize()
    331 {
    332     return (size() - objectHeaderSize) & ~allocationMask;
    333 }
    334 
    335 Address HeapObjectHeader::payloadEnd()
    336 {
    337     return reinterpret_cast<Address>(this) + size();
    338 }
    339 
    340 NO_SANITIZE_ADDRESS
    341 void HeapObjectHeader::mark()
    342 {
    343     checkHeader();
    344     m_size |= markBitMask;
    345 }
    346 
    347 // Each object on the GeneralHeap needs to carry a pointer to its
    348 // own GCInfo structure for tracing and potential finalization.
    349 class FinalizedHeapObjectHeader : public HeapObjectHeader {
    350 public:
    351     NO_SANITIZE_ADDRESS
    352     FinalizedHeapObjectHeader(size_t encodedSize, const GCInfo* gcInfo)
    353         : HeapObjectHeader(encodedSize)
    354         , m_gcInfo(gcInfo)
    355     {
    356     }
    357 
    358     inline Address payload();
    359     inline size_t payloadSize();
    360 
    361     NO_SANITIZE_ADDRESS
    362     const GCInfo* gcInfo() { return m_gcInfo; }
    363 
    364     NO_SANITIZE_ADDRESS
    365     const char* typeMarker() { return m_gcInfo->m_typeMarker; }
    366 
    367     NO_SANITIZE_ADDRESS
    368     TraceCallback traceCallback() { return m_gcInfo->m_trace; }
    369 
    370     void finalize();
    371 
    372     NO_SANITIZE_ADDRESS
    373     inline bool hasFinalizer() { return m_gcInfo->hasFinalizer(); }
    374 
    375     static FinalizedHeapObjectHeader* fromPayload(const void*);
    376 
    377 #if TRACE_GC_USING_CLASSOF
    378     const char* classOf()
    379     {
    380         const char* className = 0;
    381         if (m_gcInfo->m_classOf)
    382             className = m_gcInfo->m_classOf(payload());
    383         return className ? className : typeMarker();
    384     }
    385 #endif
    386 
    387 private:
    388     const GCInfo* m_gcInfo;
    389 };
    390 
    391 const size_t finalizedHeaderSize = sizeof(FinalizedHeapObjectHeader);
    392 
    393 Address FinalizedHeapObjectHeader::payload()
    394 {
    395     return reinterpret_cast<Address>(this) + finalizedHeaderSize;
    396 }
    397 
    398 size_t FinalizedHeapObjectHeader::payloadSize()
    399 {
    400     return size() - finalizedHeaderSize;
    401 }
    402 
    403 class HEAP_EXPORT Heap {
    404 public:
    405     static void init(intptr_t* startOfStack);
    406     static void shutdown();
    407 };
    408 
    409 }
    410 
    411 #endif // Heap_h
    412