[BMalloc] Scavenger should react to recent memory activity
[WebKit-https.git] / Source / bmalloc / bmalloc / LargeRange.h
1 /*
2  * Copyright (C) 2016-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 LargeRange_h
27 #define LargeRange_h
28
29 #include "BAssert.h"
30 #include "Range.h"
31
32 namespace bmalloc {
33
34 class LargeRange : public Range {
35 public:
36     LargeRange()
37         : Range()
38         , m_startPhysicalSize(0)
39         , m_totalPhysicalSize(0)
40         , m_isEligible(true)
41         , m_usedSinceLastScavenge(false)
42     {
43     }
44
45     LargeRange(const Range& other, size_t startPhysicalSize, size_t totalPhysicalSize)
46         : Range(other)
47         , m_startPhysicalSize(startPhysicalSize)
48         , m_totalPhysicalSize(totalPhysicalSize)
49         , m_isEligible(true)
50         , m_usedSinceLastScavenge(false)
51     {
52         BASSERT(this->size() >= this->totalPhysicalSize());
53         BASSERT(this->totalPhysicalSize() >= this->startPhysicalSize());
54     }
55
56     LargeRange(void* begin, size_t size, size_t startPhysicalSize, size_t totalPhysicalSize, bool usedSinceLastScavenge = false)
57         : Range(begin, size)
58         , m_startPhysicalSize(startPhysicalSize)
59         , m_totalPhysicalSize(totalPhysicalSize)
60         , m_isEligible(true)
61         , m_usedSinceLastScavenge(usedSinceLastScavenge)
62     {
63         BASSERT(this->size() >= this->totalPhysicalSize());
64         BASSERT(this->totalPhysicalSize() >= this->startPhysicalSize());
65     }
66
67     // Returns a lower bound on physical size at the start of the range. Ranges that
68     // span non-physical fragments use this number to remember the physical size of
69     // the first fragment.
70     size_t startPhysicalSize() const { return m_startPhysicalSize; }
71     void setStartPhysicalSize(size_t startPhysicalSize) { m_startPhysicalSize = startPhysicalSize; }
72
73     // This is accurate in the sense that if you take a range A and split it N ways
74     // and sum totalPhysicalSize over each of the N splits, you'll end up with A's
75     // totalPhysicalSize. This means if you take a LargeRange out of a LargeMap, split it,
76     // then insert the subsequent two ranges back into the LargeMap, the sum of the
77     // totalPhysicalSize of each LargeRange in the LargeMap will stay constant. This
78     // property is not true of startPhysicalSize. This invariant about totalPhysicalSize
79     // is good enough to get an accurate footprint estimate for memory used in bmalloc.
80     // The reason this is just an estimate is that splitting LargeRanges may lead to this
81     // number being rebalanced in arbitrary ways between the two resulting ranges. This
82     // is why the footprint is just an estimate. In practice, this arbitrary rebalance
83     // doesn't really affect accuracy.
84     size_t totalPhysicalSize() const { return m_totalPhysicalSize; }
85     void setTotalPhysicalSize(size_t totalPhysicalSize) { m_totalPhysicalSize = totalPhysicalSize; }
86
87     std::pair<LargeRange, LargeRange> split(size_t) const;
88
89     void setEligible(bool eligible) { m_isEligible = eligible; }
90     bool isEligibile() const { return m_isEligible; }
91
92     bool usedSinceLastScavenge() const { return m_usedSinceLastScavenge; }
93     void clearUsedSinceLastScavenge() { m_usedSinceLastScavenge = false; }
94     void setUsedSinceLastScavenge() { m_usedSinceLastScavenge = true; }
95
96     bool operator<(const void* other) const { return begin() < other; }
97     bool operator<(const LargeRange& other) const { return begin() < other.begin(); }
98
99 private:
100     size_t m_startPhysicalSize;
101     size_t m_totalPhysicalSize;
102     unsigned m_isEligible: 1;
103     unsigned m_usedSinceLastScavenge: 1;
104 };
105
106 inline bool canMerge(const LargeRange& a, const LargeRange& b)
107 {
108     if (!a.isEligibile() || !b.isEligibile()) {
109         // FIXME: We can make this work if we find it's helpful as long as the merged
110         // range is only eligible if a and b are eligible.
111         return false;
112     }
113
114     if (a.end() == b.begin())
115         return true;
116     
117     if (b.end() == a.begin())
118         return true;
119     
120     return false;
121 }
122
123 inline LargeRange merge(const LargeRange& a, const LargeRange& b)
124 {
125     const LargeRange& left = std::min(a, b);
126     bool mergedUsedSinceLastScavenge = a.usedSinceLastScavenge() || b.usedSinceLastScavenge();
127     if (left.size() == left.startPhysicalSize()) {
128         return LargeRange(
129             left.begin(),
130             a.size() + b.size(),
131             a.startPhysicalSize() + b.startPhysicalSize(),
132             a.totalPhysicalSize() + b.totalPhysicalSize(),
133             mergedUsedSinceLastScavenge);
134     }
135
136     return LargeRange(
137         left.begin(),
138         a.size() + b.size(),
139         left.startPhysicalSize(),
140         a.totalPhysicalSize() + b.totalPhysicalSize(),
141         mergedUsedSinceLastScavenge);
142 }
143
144 inline std::pair<LargeRange, LargeRange> LargeRange::split(size_t leftSize) const
145 {
146     BASSERT(leftSize <= this->size());
147     size_t rightSize = this->size() - leftSize;
148
149     if (leftSize <= startPhysicalSize()) {
150         BASSERT(totalPhysicalSize() >= leftSize);
151         LargeRange left(begin(), leftSize, leftSize, leftSize);
152         LargeRange right(left.end(), rightSize, startPhysicalSize() - leftSize, totalPhysicalSize() - leftSize);
153         return std::make_pair(left, right);
154     }
155
156     double ratio = static_cast<double>(leftSize) / static_cast<double>(this->size());
157     size_t leftTotalPhysicalSize = static_cast<size_t>(ratio * totalPhysicalSize());
158     BASSERT(leftTotalPhysicalSize <= leftSize);
159     leftTotalPhysicalSize = std::max(startPhysicalSize(), leftTotalPhysicalSize);
160     size_t rightTotalPhysicalSize = totalPhysicalSize() - leftTotalPhysicalSize;
161     if (rightTotalPhysicalSize > rightSize) { // This may happen because of rounding.
162         leftTotalPhysicalSize += rightTotalPhysicalSize - rightSize;
163         BASSERT(leftTotalPhysicalSize <= leftSize);
164         rightTotalPhysicalSize = rightSize;
165     }
166
167     LargeRange left(begin(), leftSize, startPhysicalSize(), leftTotalPhysicalSize);
168     LargeRange right(left.end(), rightSize, 0, rightTotalPhysicalSize);
169     return std::make_pair(left, right);
170 }
171
172 } // namespace bmalloc
173
174 #endif // LargeRange_h