b67cf66633095e59bc725b4b08db9ed1e3f546ea
[WebKit-https.git] / Source / bmalloc / bmalloc / Heap.h
1 /*
2  * Copyright (C) 2014-2018 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 "Chunk.h"
31 #include "HeapKind.h"
32 #include "LargeMap.h"
33 #include "LineMetadata.h"
34 #include "List.h"
35 #include "Map.h"
36 #include "Mutex.h"
37 #include "Object.h"
38 #include "PerHeapKind.h"
39 #include "PerProcess.h"
40 #include "PhysicalPageMap.h"
41 #include "SmallLine.h"
42 #include "SmallPage.h"
43 #include "Vector.h"
44 #include <array>
45 #include <condition_variable>
46 #include <mutex>
47 #include <vector>
48
49 namespace bmalloc {
50
51 class BeginTag;
52 class BulkDecommit;
53 class BumpAllocator;
54 class DebugHeap;
55 class EndTag;
56 class Scavenger;
57
58 class Heap {
59 public:
60     Heap(HeapKind, std::lock_guard<Mutex>&);
61     
62     static Mutex& mutex() { return PerProcess<PerHeapKind<Heap>>::mutex(); }
63     
64     HeapKind kind() const { return m_kind; }
65     
66     void allocateSmallBumpRanges(std::unique_lock<Mutex>&, size_t sizeClass,
67         BumpAllocator&, BumpRangeCache&, LineCache&);
68     void derefSmallLine(std::unique_lock<Mutex>&, Object, LineCache&);
69     void deallocateLineCache(std::unique_lock<Mutex>&, LineCache&);
70
71     void* allocateLarge(std::unique_lock<Mutex>&, size_t alignment, size_t);
72     void* tryAllocateLarge(std::unique_lock<Mutex>&, size_t alignment, size_t);
73     void deallocateLarge(std::unique_lock<Mutex>&, void*);
74
75     bool isLarge(std::unique_lock<Mutex>&, void*);
76     size_t largeSize(std::unique_lock<Mutex>&, void*);
77     void shrinkLarge(std::unique_lock<Mutex>&, const Range&, size_t);
78
79     void scavenge(std::lock_guard<Mutex>&, BulkDecommit&);
80     void scavenge(std::lock_guard<Mutex>&, BulkDecommit&, size_t& freed, size_t goal);
81     void scavengeToHighWatermark(std::lock_guard<Mutex>&, BulkDecommit&);
82
83     size_t freeableMemory(std::lock_guard<Mutex>&);
84     size_t footprint();
85
86     void externalDecommit(void* ptr, size_t);
87     void externalDecommit(std::unique_lock<Mutex>&, void* ptr, size_t);
88     void externalCommit(void* ptr, size_t);
89     void externalCommit(std::unique_lock<Mutex>&, void* ptr, size_t);
90
91     void markAllLargeAsEligibile(std::lock_guard<Mutex>&);
92
93 private:
94     void decommitLargeRange(std::lock_guard<Mutex>&, LargeRange&, BulkDecommit&);
95
96     struct LargeObjectHash {
97         static unsigned hash(void* key)
98         {
99             return static_cast<unsigned>(
100                 reinterpret_cast<uintptr_t>(key) / smallMax);
101         }
102     };
103
104     ~Heap() = delete;
105     
106     bool usingGigacage();
107     void* gigacageBasePtr(); // May crash if !usingGigacage().
108     size_t gigacageSize();
109     
110     void initializeLineMetadata();
111     void initializePageMetadata();
112
113     void allocateSmallBumpRangesByMetadata(std::unique_lock<Mutex>&,
114         size_t sizeClass, BumpAllocator&, BumpRangeCache&, LineCache&);
115     void allocateSmallBumpRangesByObject(std::unique_lock<Mutex>&,
116         size_t sizeClass, BumpAllocator&, BumpRangeCache&, LineCache&);
117
118     SmallPage* allocateSmallPage(std::unique_lock<Mutex>&, size_t sizeClass, LineCache&);
119     void deallocateSmallLine(std::unique_lock<Mutex>&, Object, LineCache&);
120
121     void allocateSmallChunk(std::unique_lock<Mutex>&, size_t pageClass);
122     void deallocateSmallChunk(Chunk*, size_t pageClass);
123
124     void mergeLarge(BeginTag*&, EndTag*&, Range&);
125     void mergeLargeLeft(EndTag*&, BeginTag*&, Range&, bool& inVMHeap);
126     void mergeLargeRight(EndTag*&, BeginTag*&, Range&, bool& inVMHeap);
127
128     LargeRange splitAndAllocate(std::unique_lock<Mutex>&, LargeRange&, size_t alignment, size_t);
129
130     HeapKind m_kind;
131
132     bool m_hasPendingDecommits { false };
133     std::condition_variable_any m_condition;
134
135     size_t m_vmPageSizePhysical;
136     Vector<LineMetadata> m_smallLineMetadata;
137     std::array<size_t, sizeClassCount> m_pageClasses;
138
139     LineCache m_lineCache;
140     std::array<List<Chunk>, pageClassCount> m_freePages;
141     std::array<List<Chunk>, pageClassCount> m_chunkCache;
142
143     Map<void*, size_t, LargeObjectHash> m_largeAllocated;
144     LargeMap m_largeFree;
145
146     Map<Chunk*, ObjectType, ChunkHash> m_objectTypes;
147
148     Scavenger* m_scavenger { nullptr };
149
150     size_t m_footprint { 0 };
151     size_t m_freeableMemory { 0 };
152
153 #if ENABLE_PHYSICAL_PAGE_MAP 
154     PhysicalPageMap m_physicalPageMap;
155 #endif
156
157     void* m_highWatermark { nullptr };
158 };
159
160 inline void Heap::allocateSmallBumpRanges(
161     std::unique_lock<Mutex>& lock, size_t sizeClass,
162     BumpAllocator& allocator, BumpRangeCache& rangeCache,
163     LineCache& lineCache)
164 {
165     if (sizeClass < bmalloc::sizeClass(smallLineSize))
166         return allocateSmallBumpRangesByMetadata(lock, sizeClass, allocator, rangeCache, lineCache);
167     return allocateSmallBumpRangesByObject(lock, sizeClass, allocator, rangeCache, lineCache);
168 }
169
170 inline void Heap::derefSmallLine(std::unique_lock<Mutex>& lock, Object object, LineCache& lineCache)
171 {
172     if (!object.line()->deref(lock))
173         return;
174     deallocateSmallLine(lock, object, lineCache);
175 }
176
177 } // namespace bmalloc
178
179 #endif // Heap_h