1/*
2 * Copyright (C) 2013 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#ifndef JSC_Region_h
27#define JSC_Region_h
28
29#include "HeapBlock.h"
30#include "SuperRegion.h"
31#include <wtf/DoublyLinkedList.h>
32#include <wtf/MetaAllocatorHandle.h>
33#include <wtf/PageAllocationAligned.h>
34
35#define HEAP_MEMORY_ID reinterpret_cast<void*>(static_cast<intptr_t>(-3))
36
37#define ENABLE_SUPER_REGION 0
38
39#ifndef ENABLE_SUPER_REGION
40#if USE(JSVALUE64)
41#define ENABLE_SUPER_REGION 1
42#else
43#define ENABLE_SUPER_REGION 0
44#endif
45#endif
46
47namespace JSC {
48
49class DeadBlock : public HeapBlock<DeadBlock> {
50public:
51    DeadBlock(Region*);
52};
53
54inline DeadBlock::DeadBlock(Region* region)
55    : HeapBlock<DeadBlock>(region)
56{
57}
58
59class Region : public DoublyLinkedListNode<Region> {
60    friend CLASS_IF_GCC DoublyLinkedListNode<Region>;
61    friend class BlockAllocator;
62public:
63    ~Region();
64    static Region* create(SuperRegion*, size_t blockSize);
65    static Region* createCustomSize(SuperRegion*, size_t blockSize, size_t blockAlignment);
66    Region* reset(size_t blockSize);
67    void destroy();
68
69    size_t blockSize() const { return m_blockSize; }
70    bool isFull() const { return m_blocksInUse == m_totalBlocks; }
71    bool isEmpty() const { return !m_blocksInUse; }
72    bool isCustomSize() const { return m_isCustomSize; }
73
74    DeadBlock* allocate();
75    void deallocate(void*);
76
77    static const size_t s_regionSize = 64 * KB;
78    static const size_t s_regionMask = ~(s_regionSize - 1);
79
80protected:
81    Region(size_t blockSize, size_t totalBlocks, bool isExcess);
82    void initializeBlockList();
83
84    bool m_isExcess;
85
86private:
87    void* base();
88    size_t size();
89
90    size_t m_totalBlocks;
91    size_t m_blocksInUse;
92    size_t m_blockSize;
93    bool m_isCustomSize;
94    Region* m_prev;
95    Region* m_next;
96    DoublyLinkedList<DeadBlock> m_deadBlocks;
97};
98
99
100class NormalRegion : public Region {
101    friend class Region;
102private:
103    NormalRegion(PassRefPtr<WTF::MetaAllocatorHandle>, size_t blockSize, size_t totalBlocks);
104
105    static NormalRegion* tryCreate(SuperRegion*, size_t blockSize);
106    static NormalRegion* tryCreateCustomSize(SuperRegion*, size_t blockSize, size_t blockAlignment);
107
108    void* base() { return m_allocation->start(); }
109    size_t size() { return m_allocation->sizeInBytes(); }
110
111    NormalRegion* reset(size_t blockSize);
112
113    RefPtr<WTF::MetaAllocatorHandle> m_allocation;
114};
115
116class ExcessRegion : public Region {
117    friend class Region;
118private:
119    ExcessRegion(PageAllocationAligned&, size_t blockSize, size_t totalBlocks);
120
121    ~ExcessRegion();
122
123    static ExcessRegion* create(size_t blockSize);
124    static ExcessRegion* createCustomSize(size_t blockSize, size_t blockAlignment);
125
126    void* base() { return m_allocation.base(); }
127    size_t size() { return m_allocation.size(); }
128
129    ExcessRegion* reset(size_t blockSize);
130
131    PageAllocationAligned m_allocation;
132};
133
134inline NormalRegion::NormalRegion(PassRefPtr<WTF::MetaAllocatorHandle> allocation, size_t blockSize, size_t totalBlocks)
135    : Region(blockSize, totalBlocks, false)
136    , m_allocation(allocation)
137{
138    initializeBlockList();
139}
140
141inline NormalRegion* NormalRegion::tryCreate(SuperRegion* superRegion, size_t blockSize)
142{
143    RefPtr<WTF::MetaAllocatorHandle> allocation = superRegion->allocate(s_regionSize, HEAP_MEMORY_ID);
144    if (!allocation)
145        return 0;
146    return new NormalRegion(allocation, blockSize, s_regionSize / blockSize);
147}
148
149inline NormalRegion* NormalRegion::tryCreateCustomSize(SuperRegion* superRegion, size_t blockSize, size_t blockAlignment)
150{
151    ASSERT_UNUSED(blockAlignment, blockAlignment <= s_regionSize);
152    RefPtr<WTF::MetaAllocatorHandle> allocation = superRegion->allocate(blockSize, HEAP_MEMORY_ID);
153    if (!allocation)
154        return 0;
155    return new NormalRegion(allocation, blockSize, 1);
156}
157
158inline NormalRegion* NormalRegion::reset(size_t blockSize)
159{
160    ASSERT(!m_isExcess);
161    RefPtr<WTF::MetaAllocatorHandle> allocation = m_allocation.release();
162    return new (NotNull, this) NormalRegion(allocation.release(), blockSize, s_regionSize / blockSize);
163}
164
165inline ExcessRegion::ExcessRegion(PageAllocationAligned& allocation, size_t blockSize, size_t totalBlocks)
166    : Region(blockSize, totalBlocks, true)
167    , m_allocation(allocation)
168{
169    initializeBlockList();
170}
171
172inline ExcessRegion::~ExcessRegion()
173{
174    m_allocation.deallocate();
175}
176
177inline ExcessRegion* ExcessRegion::create(size_t blockSize)
178{
179    PageAllocationAligned allocation = PageAllocationAligned::allocate(s_regionSize, s_regionSize, OSAllocator::JSGCHeapPages);
180    ASSERT(static_cast<bool>(allocation));
181    return new ExcessRegion(allocation, blockSize, s_regionSize / blockSize);
182}
183
184inline ExcessRegion* ExcessRegion::createCustomSize(size_t blockSize, size_t blockAlignment)
185{
186    PageAllocationAligned allocation = PageAllocationAligned::allocate(blockSize, blockAlignment, OSAllocator::JSGCHeapPages);
187    ASSERT(static_cast<bool>(allocation));
188    return new ExcessRegion(allocation, blockSize, 1);
189}
190
191inline ExcessRegion* ExcessRegion::reset(size_t blockSize)
192{
193    ASSERT(m_isExcess);
194    PageAllocationAligned allocation = m_allocation;
195    return new (NotNull, this) ExcessRegion(allocation, blockSize, s_regionSize / blockSize);
196}
197
198inline Region::Region(size_t blockSize, size_t totalBlocks, bool isExcess)
199    : DoublyLinkedListNode<Region>()
200    , m_isExcess(isExcess)
201    , m_totalBlocks(totalBlocks)
202    , m_blocksInUse(0)
203    , m_blockSize(blockSize)
204    , m_isCustomSize(false)
205    , m_prev(0)
206    , m_next(0)
207{
208}
209
210inline void Region::initializeBlockList()
211{
212    char* start = static_cast<char*>(base());
213    char* current = start;
214    for (size_t i = 0; i < m_totalBlocks; i++) {
215        ASSERT(current < start + size());
216        m_deadBlocks.append(new (NotNull, current) DeadBlock(this));
217        current += m_blockSize;
218    }
219}
220
221inline Region* Region::create(SuperRegion* superRegion, size_t blockSize)
222{
223#if ENABLE(SUPER_REGION)
224    ASSERT(blockSize <= s_regionSize);
225    ASSERT(!(s_regionSize % blockSize));
226    Region* region = NormalRegion::tryCreate(superRegion, blockSize);
227    if (LIKELY(!!region))
228        return region;
229#else
230    UNUSED_PARAM(superRegion);
231#endif
232    return ExcessRegion::create(blockSize);
233}
234
235inline Region* Region::createCustomSize(SuperRegion* superRegion, size_t blockSize, size_t blockAlignment)
236{
237#if ENABLE(SUPER_REGION)
238    Region* region = NormalRegion::tryCreateCustomSize(superRegion, blockSize, blockAlignment);
239    if (UNLIKELY(!region))
240        region = ExcessRegion::createCustomSize(blockSize, blockAlignment);
241#else
242    UNUSED_PARAM(superRegion);
243    Region* region = ExcessRegion::createCustomSize(blockSize, blockAlignment);
244#endif
245    region->m_isCustomSize = true;
246    return region;
247}
248
249inline Region::~Region()
250{
251    ASSERT(isEmpty());
252}
253
254inline void Region::destroy()
255{
256#if ENABLE(SUPER_REGION)
257    if (UNLIKELY(m_isExcess))
258        delete static_cast<ExcessRegion*>(this);
259    else
260        delete static_cast<NormalRegion*>(this);
261#else
262    delete static_cast<ExcessRegion*>(this);
263#endif
264}
265
266inline Region* Region::reset(size_t blockSize)
267{
268#if ENABLE(SUPER_REGION)
269    ASSERT(isEmpty());
270    if (UNLIKELY(m_isExcess))
271        return static_cast<ExcessRegion*>(this)->reset(blockSize);
272    return static_cast<NormalRegion*>(this)->reset(blockSize);
273#else
274    return static_cast<ExcessRegion*>(this)->reset(blockSize);
275#endif
276}
277
278inline DeadBlock* Region::allocate()
279{
280    ASSERT(!isFull());
281    m_blocksInUse++;
282    return m_deadBlocks.removeHead();
283}
284
285inline void Region::deallocate(void* base)
286{
287    ASSERT(base);
288    ASSERT(m_blocksInUse);
289    ASSERT(base >= this->base() && base < static_cast<char*>(this->base()) + size());
290    DeadBlock* block = new (NotNull, base) DeadBlock(this);
291    m_deadBlocks.push(block);
292    m_blocksInUse--;
293}
294
295inline void* Region::base()
296{
297#if ENABLE(SUPER_REGION)
298    if (UNLIKELY(m_isExcess))
299        return static_cast<ExcessRegion*>(this)->ExcessRegion::base();
300    return static_cast<NormalRegion*>(this)->NormalRegion::base();
301#else
302    return static_cast<ExcessRegion*>(this)->ExcessRegion::base();
303#endif
304}
305
306inline size_t Region::size()
307{
308#if ENABLE(SUPER_REGION)
309    if (UNLIKELY(m_isExcess))
310        return static_cast<ExcessRegion*>(this)->ExcessRegion::size();
311    return static_cast<NormalRegion*>(this)->NormalRegion::size();
312#else
313    return static_cast<ExcessRegion*>(this)->ExcessRegion::size();
314#endif
315}
316
317} // namespace JSC
318
319#endif // JSC_Region_h
320