bmalloc
[WebKit-https.git] / Source / bmalloc / bmalloc / Heap.cpp
1 /*
2  * Copyright (C) 2014 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 #include "BoundaryTagInlines.h"
27 #include "Heap.h"
28 #include "LargeChunk.h"
29 #include "Line.h"
30 #include "MediumChunk.h"
31 #include "Page.h"
32 #include "PerProcess.h"
33 #include "SmallChunk.h"
34 #include "XLargeChunk.h"
35 #include <thread>
36
37 namespace bmalloc {
38
39 static inline void sleep(std::unique_lock<Mutex>& lock, std::chrono::milliseconds duration)
40 {
41     lock.unlock();
42     std::this_thread::sleep_for(duration);
43     lock.lock();
44 }
45
46 Heap::Heap(std::lock_guard<Mutex>&)
47     : m_scavenger(*this, &Heap::concurrentScavenge)
48     , m_isAllocatingPages(false)
49 {
50 }
51
52 void Heap::concurrentScavenge()
53 {
54     std::unique_lock<Mutex> lock(PerProcess<Heap>::mutex());
55     scavengeSmallPages(lock);
56     scavengeMediumPages(lock);
57     scavengeLargeRanges(lock);
58
59     sleep(lock, scavengeSleepDuration);
60 }
61
62 void Heap::scavengeSmallPages(std::unique_lock<Mutex>& lock)
63 {
64     while (1) {
65         if (m_isAllocatingPages) {
66             m_isAllocatingPages = false;
67
68             sleep(lock, scavengeSleepDuration);
69             continue;
70         }
71
72         if (!m_smallPages.size())
73             return;
74         m_vmHeap.deallocateSmallPage(lock, m_smallPages.pop());
75     }
76 }
77
78 void Heap::scavengeMediumPages(std::unique_lock<Mutex>& lock)
79 {
80     while (1) {
81         if (m_isAllocatingPages) {
82             m_isAllocatingPages = false;
83
84             sleep(lock, scavengeSleepDuration);
85             continue;
86         }
87
88         if (!m_mediumPages.size())
89             return;
90         m_vmHeap.deallocateMediumPage(lock, m_mediumPages.pop());
91     }
92 }
93
94 void Heap::scavengeLargeRanges(std::unique_lock<Mutex>& lock)
95 {
96     while (1) {
97         if (m_isAllocatingPages) {
98             m_isAllocatingPages = false;
99
100             sleep(lock, scavengeSleepDuration);
101             continue;
102         }
103
104         Range range = m_largeRanges.takeGreedy(vmPageSize);
105         if (!range)
106             return;
107         m_vmHeap.deallocateLargeRange(lock, range);
108     }
109 }
110
111 SmallLine* Heap::allocateSmallLineSlowCase(std::lock_guard<Mutex>& lock)
112 {
113     m_isAllocatingPages = true;
114
115     SmallPage* page = [this]() {
116         if (m_smallPages.size())
117             return m_smallPages.pop();
118         
119         SmallPage* page = m_vmHeap.allocateSmallPage();
120         vmAllocatePhysicalPages(page->begin()->begin(), vmPageSize);
121         return page;
122     }();
123
124     SmallLine* line = page->begin();
125     for (auto it = line + 1; it != page->end(); ++it)
126         m_smallLines.push(it);
127
128     page->ref(lock);
129     return line;
130 }
131
132 MediumLine* Heap::allocateMediumLineSlowCase(std::lock_guard<Mutex>& lock)
133 {
134     m_isAllocatingPages = true;
135
136     MediumPage* page = [this]() {
137         if (m_mediumPages.size())
138             return m_mediumPages.pop();
139         
140         MediumPage* page = m_vmHeap.allocateMediumPage();
141         vmAllocatePhysicalPages(page->begin()->begin(), vmPageSize);
142         return page;
143     }();
144
145     MediumLine* line = page->begin();
146     for (auto it = line + 1; it != page->end(); ++it)
147         m_mediumLines.push(it);
148
149     page->ref(lock);
150     return line;
151 }
152
153 void* Heap::allocateXLarge(std::lock_guard<Mutex>&, size_t size)
154 {
155     XLargeChunk* chunk = XLargeChunk::create(size);
156
157     BeginTag* beginTag = LargeChunk::beginTag(chunk->begin());
158     beginTag->setXLarge();
159     beginTag->setFree(false);
160     beginTag->setHasPhysicalPages(true);
161     
162     return chunk->begin();
163 }
164
165 void Heap::deallocateXLarge(std::lock_guard<Mutex>&, void* object)
166 {
167     XLargeChunk* chunk = XLargeChunk::get(object);
168     XLargeChunk::destroy(chunk);
169 }
170
171 void* Heap::allocateLarge(std::lock_guard<Mutex>& lock, size_t size)
172 {
173     ASSERT(size <= largeMax);
174     ASSERT(size >= largeMin);
175     
176     m_isAllocatingPages = true;
177
178     Range range = m_largeRanges.take(size);
179     if (!range)
180         range = m_vmHeap.allocateLargeRange(size);
181     
182     Range leftover;
183     bool hasPhysicalPages;
184     BoundaryTag::allocate(size, range, leftover, hasPhysicalPages);
185
186     if (!!leftover)
187         m_largeRanges.insert(leftover);
188     
189     if (!hasPhysicalPages)
190         vmAllocatePhysicalPagesSloppy(range.begin(), range.size());
191
192     return range.begin();
193 }
194
195 void Heap::deallocateLarge(std::lock_guard<Mutex>& lock, void* object)
196 {
197     Range range = BoundaryTag::deallocate(object);
198     m_largeRanges.insert(range);
199     m_scavenger.run();
200 }
201
202 } // namespace bmalloc