bmalloc should honor the FastMalloc statistics API
[WebKit-https.git] / Source / bmalloc / bmalloc / Heap.h
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 #ifndef Heap_h
27 #define Heap_h
28
29 #include "FixedVector.h"
30 #include "VMHeap.h"
31 #include "MediumLine.h"
32 #include "Mutex.h"
33 #include "SmallPage.h"
34 #include "MediumChunk.h"
35 #include "MediumPage.h"
36 #include "SegregatedFreeList.h"
37 #include "SmallChunk.h"
38 #include "SmallLine.h"
39 #include "Vector.h"
40 #include <array>
41 #include <mutex>
42
43 namespace bmalloc {
44
45 class BeginTag;
46 class EndTag;
47
48 class Heap {
49 public:
50     Heap(std::lock_guard<StaticMutex>&);
51
52     SmallLine* allocateSmallLine(std::lock_guard<StaticMutex>&, size_t smallSizeClass);
53     void deallocateSmallLine(std::lock_guard<StaticMutex>&, SmallLine*);
54
55     MediumLine* allocateMediumLine(std::lock_guard<StaticMutex>&);
56     void deallocateMediumLine(std::lock_guard<StaticMutex>&, MediumLine*);
57     
58     void* allocateLarge(std::lock_guard<StaticMutex>&, size_t);
59     void deallocateLarge(std::lock_guard<StaticMutex>&, void*);
60
61     void* allocateXLarge(std::lock_guard<StaticMutex>&, size_t);
62     void deallocateXLarge(std::lock_guard<StaticMutex>&, void*);
63
64     void scavenge(std::unique_lock<StaticMutex>&, std::chrono::milliseconds sleepDuration);
65
66     size_t size(std::lock_guard<StaticMutex>&);
67     size_t capacity(std::lock_guard<StaticMutex>&);
68
69 private:
70     ~Heap() = delete;
71
72     SmallLine* allocateSmallLineSlowCase(std::lock_guard<StaticMutex>&, size_t smallSizeClass);
73     MediumLine* allocateMediumLineSlowCase(std::lock_guard<StaticMutex>&);
74
75     void* allocateLarge(Range, size_t);
76     Range allocateLargeChunk();
77
78     void splitLarge(BeginTag*, size_t, EndTag*&, Range&);
79     void mergeLarge(BeginTag*&, EndTag*&, Range&);
80     void mergeLargeLeft(EndTag*&, BeginTag*&, Range&, bool& hasPhysicalPages);
81     void mergeLargeRight(EndTag*&, BeginTag*&, Range&, bool& hasPhysicalPages);
82     
83     void concurrentScavenge();
84     void scavengeSmallPages(std::unique_lock<StaticMutex>&, std::chrono::milliseconds);
85     void scavengeMediumPages(std::unique_lock<StaticMutex>&, std::chrono::milliseconds);
86     void scavengeLargeRanges(std::unique_lock<StaticMutex>&, std::chrono::milliseconds);
87
88     std::array<Vector<SmallLine*>, smallMax / alignment> m_smallLines;
89     Vector<MediumLine*> m_mediumLines;
90
91     Vector<SmallPage*> m_smallPages;
92     Vector<MediumPage*> m_mediumPages;
93
94     SegregatedFreeList m_largeRanges;
95
96     bool m_isAllocatingPages;
97
98     VMHeap m_vmHeap;
99     AsyncTask<Heap, decltype(&Heap::concurrentScavenge)> m_scavenger;
100 };
101
102 inline void Heap::deallocateSmallLine(std::lock_guard<StaticMutex>& lock, SmallLine* line)
103 {
104     BASSERT(!line->refCount(lock));
105     SmallPage* page = SmallPage::get(line);
106     if (page->deref(lock)) {
107         m_smallPages.push(page);
108         m_scavenger.run();
109         return;
110     }
111     m_smallLines[page->smallSizeClass()].push(line);
112 }
113
114 inline SmallLine* Heap::allocateSmallLine(std::lock_guard<StaticMutex>& lock, size_t smallSizeClass)
115 {
116     Vector<SmallLine*>& smallLines = m_smallLines[smallSizeClass];
117     while (smallLines.size()) {
118         SmallLine* line = smallLines.pop();
119         SmallPage* page = SmallPage::get(line);
120         if (!page->refCount(lock) || page->smallSizeClass() != smallSizeClass) // The line was promoted to the small pages list.
121             continue;
122         BASSERT(!line->refCount(lock));
123         page->ref(lock);
124         return line;
125     }
126
127     return allocateSmallLineSlowCase(lock, smallSizeClass);
128 }
129
130 inline void Heap::deallocateMediumLine(std::lock_guard<StaticMutex>& lock, MediumLine* line)
131 {
132     BASSERT(!line->refCount(lock));
133     MediumPage* page = MediumPage::get(line);
134     if (page->deref(lock)) {
135         m_mediumPages.push(page);
136         m_scavenger.run();
137         return;
138     }
139     m_mediumLines.push(line);
140 }
141
142 inline MediumLine* Heap::allocateMediumLine(std::lock_guard<StaticMutex>& lock)
143 {
144     while (m_mediumLines.size()) {
145         MediumLine* line = m_mediumLines.pop();
146         MediumPage* page = MediumPage::get(line);
147         if (!page->refCount(lock)) // The line was promoted to the medium pages list.
148             continue;
149         BASSERT(!line->refCount(lock));
150         page->ref(lock);
151         return line;
152     }
153
154     return allocateMediumLineSlowCase(lock);
155 }
156
157 } // namespace bmalloc
158
159 #endif // Heap_h