bmalloc: Merge the large and xlarge allocators
[WebKit.git] / Source / bmalloc / bmalloc / Heap.h
1 /*
2  * Copyright (C) 2014-2016 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 #ifndef Heap_h
27 #define Heap_h
28
29 #include "BumpRange.h"
30 #include "Environment.h"
31 #include "LineMetadata.h"
32 #include "List.h"
33 #include "Map.h"
34 #include "Mutex.h"
35 #include "Object.h"
36 #include "SmallLine.h"
37 #include "SmallPage.h"
38 #include "VMHeap.h"
39 #include "Vector.h"
40 #include "XLargeMap.h"
41 #include <array>
42 #include <mutex>
43
44 namespace bmalloc {
45
46 class BeginTag;
47 class BumpAllocator;
48 class EndTag;
49
50 class Heap {
51 public:
52     Heap(std::lock_guard<StaticMutex>&);
53     
54     Environment& environment() { return m_environment; }
55
56     void allocateSmallBumpRanges(std::lock_guard<StaticMutex>&, size_t sizeClass, BumpAllocator&, BumpRangeCache&);
57     void derefSmallLine(std::lock_guard<StaticMutex>&, Object);
58
59     void* allocateLarge(std::lock_guard<StaticMutex>&, size_t alignment, size_t);
60     void* tryAllocateLarge(std::lock_guard<StaticMutex>&, size_t alignment, size_t);
61     void deallocateLarge(std::lock_guard<StaticMutex>&, void*);
62
63     bool isLarge(std::lock_guard<StaticMutex>&, void*);
64     size_t largeSize(std::lock_guard<StaticMutex>&, void*);
65     void shrinkLarge(std::lock_guard<StaticMutex>&, const Range&, size_t);
66
67     void scavenge(std::unique_lock<StaticMutex>&, std::chrono::milliseconds sleepDuration);
68
69 private:
70     struct LargeObjectHash {
71         static unsigned hash(void* key)
72         {
73             return static_cast<unsigned>(
74                 reinterpret_cast<uintptr_t>(key) / smallMax);
75         }
76     };
77
78     ~Heap() = delete;
79     
80     void initializeLineMetadata();
81     void initializePageMetadata();
82
83     void allocateSmallBumpRangesByMetadata(std::lock_guard<StaticMutex>&,
84         size_t sizeClass, BumpAllocator&, BumpRangeCache&);
85     void allocateSmallBumpRangesByObject(std::lock_guard<StaticMutex>&,
86         size_t sizeClass, BumpAllocator&, BumpRangeCache&);
87
88     SmallPage* allocateSmallPage(std::lock_guard<StaticMutex>&, size_t sizeClass);
89
90     void deallocateSmallLine(std::lock_guard<StaticMutex>&, Object);
91
92     void mergeLarge(BeginTag*&, EndTag*&, Range&);
93     void mergeLargeLeft(EndTag*&, BeginTag*&, Range&, bool& inVMHeap);
94     void mergeLargeRight(EndTag*&, BeginTag*&, Range&, bool& inVMHeap);
95
96     XLargeRange splitAndAllocate(XLargeRange&, size_t alignment, size_t);
97
98     void concurrentScavenge();
99     void scavengeSmallPages(std::unique_lock<StaticMutex>&, std::chrono::milliseconds);
100     void scavengeLargeObjects(std::unique_lock<StaticMutex>&, std::chrono::milliseconds);
101
102     size_t m_vmPageSizePhysical;
103     Vector<LineMetadata> m_smallLineMetadata;
104     std::array<size_t, sizeClassCount> m_pageClasses;
105
106     std::array<List<SmallPage>, sizeClassCount> m_smallPagesWithFreeLines;
107     std::array<List<SmallPage>, pageClassCount> m_smallPages;
108
109     Map<void*, size_t, LargeObjectHash> m_largeAllocated;
110     XLargeMap m_largeFree;
111
112     Map<Chunk*, ObjectType, ChunkHash> m_objectTypes;
113
114     bool m_isAllocatingPages;
115     AsyncTask<Heap, decltype(&Heap::concurrentScavenge)> m_scavenger;
116
117     Environment m_environment;
118
119     VMHeap m_vmHeap;
120 };
121
122 inline void Heap::allocateSmallBumpRanges(
123     std::lock_guard<StaticMutex>& lock, size_t sizeClass,
124     BumpAllocator& allocator, BumpRangeCache& rangeCache)
125 {
126     if (sizeClass < bmalloc::sizeClass(smallLineSize))
127         return allocateSmallBumpRangesByMetadata(lock, sizeClass, allocator, rangeCache);
128     return allocateSmallBumpRangesByObject(lock, sizeClass, allocator, rangeCache);
129 }
130
131 inline void Heap::derefSmallLine(std::lock_guard<StaticMutex>& lock, Object object)
132 {
133     if (!object.line()->deref(lock))
134         return;
135     deallocateSmallLine(lock, object);
136 }
137
138 } // namespace bmalloc
139
140 #endif // Heap_h