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
32namespace bmalloc {
33
34class LargeRange : public Range {
35public:
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
99private:
100 size_t m_startPhysicalSize;
101 size_t m_totalPhysicalSize;
102 unsigned m_isEligible: 1;
103 unsigned m_usedSinceLastScavenge: 1;
104};
105
106inline 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
123inline 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
144inline 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
175