Line data Source code
1 : // Copyright 2018 the V8 project authors. All rights reserved.
2 : // Use of this source code is governed by a BSD-style license that can be
3 : // found in the LICENSE file.
4 :
5 : #include "src/base/region-allocator.h"
6 : #include "src/base/bits.h"
7 : #include "src/base/macros.h"
8 :
9 : namespace v8 {
10 : namespace base {
11 :
12 : // If |free_size| < |region_size| * |kMaxLoadFactorForRandomization| stop trying
13 : // to randomize region allocation.
14 : constexpr double kMaxLoadFactorForRandomization = 0.40;
15 :
16 : // Max number of attempts to allocate page at random address.
17 : constexpr int kMaxRandomizationAttempts = 3;
18 :
19 64408 : RegionAllocator::RegionAllocator(Address memory_region_begin,
20 : size_t memory_region_size, size_t page_size)
21 : : whole_region_(memory_region_begin, memory_region_size, false),
22 64408 : region_size_in_pages_(size() / page_size),
23 : max_load_for_randomization_(
24 64408 : static_cast<size_t>(size() * kMaxLoadFactorForRandomization)),
25 : free_size_(0),
26 128816 : page_size_(page_size) {
27 64408 : CHECK_LT(begin(), end());
28 64408 : CHECK(base::bits::IsPowerOfTwo(page_size_));
29 64408 : CHECK(IsAligned(size(), page_size_));
30 64408 : CHECK(IsAligned(begin(), page_size_));
31 :
32 : // Initial region.
33 64408 : Region* region = new Region(whole_region_);
34 :
35 : all_regions_.insert(region);
36 :
37 64408 : FreeListAddRegion(region);
38 64408 : }
39 :
40 64393 : RegionAllocator::~RegionAllocator() {
41 193220 : for (Region* region : all_regions_) {
42 64434 : delete region;
43 : }
44 64393 : }
45 :
46 134595 : RegionAllocator::AllRegionsSet::iterator RegionAllocator::FindRegion(
47 : Address address) {
48 134595 : if (!whole_region_.contains(address)) return all_regions_.end();
49 :
50 : Region key(address, 0, false);
51 : AllRegionsSet::iterator iter = all_regions_.upper_bound(&key);
52 : // Regions in |all_regions_| are compared by end() values and key's end()
53 : // points exactly to the address we are querying, so the upper_bound will
54 : // find the region whose |end()| is greater than the requested address.
55 : DCHECK_NE(iter, all_regions_.end());
56 : DCHECK((*iter)->contains(address));
57 134589 : return iter;
58 : }
59 :
60 0 : void RegionAllocator::FreeListAddRegion(Region* region) {
61 466461 : free_size_ += region->size();
62 : free_regions_.insert(region);
63 0 : }
64 :
65 134473 : RegionAllocator::Region* RegionAllocator::FreeListFindRegion(size_t size) {
66 : Region key(0, size, false);
67 268947 : auto iter = free_regions_.lower_bound(&key);
68 134474 : return iter == free_regions_.end() ? nullptr : *iter;
69 : }
70 :
71 402060 : void RegionAllocator::FreeListRemoveRegion(Region* region) {
72 : DCHECK(!region->is_used());
73 402060 : auto iter = free_regions_.find(region);
74 : DCHECK_NE(iter, free_regions_.end());
75 : DCHECK_EQ(region, *iter);
76 : DCHECK_LE(region->size(), free_size_);
77 402060 : free_size_ -= region->size();
78 402060 : free_regions_.erase(iter);
79 402060 : }
80 :
81 133803 : RegionAllocator::Region* RegionAllocator::Split(Region* region,
82 : size_t new_size) {
83 : DCHECK(IsAligned(new_size, page_size_));
84 : DCHECK_NE(new_size, 0);
85 : DCHECK_GT(region->size(), new_size);
86 :
87 : // Create new region and put it to the lists after the |region|.
88 : bool used = region->is_used();
89 : Region* new_region =
90 267606 : new Region(region->begin() + new_size, region->size() - new_size, used);
91 133803 : if (!used) {
92 : // Remove region from the free list before updating it's size.
93 133794 : FreeListRemoveRegion(region);
94 : }
95 : region->set_size(new_size);
96 :
97 : all_regions_.insert(new_region);
98 :
99 133802 : if (!used) {
100 : FreeListAddRegion(region);
101 133794 : FreeListAddRegion(new_region);
102 : }
103 133803 : return new_region;
104 : }
105 :
106 133747 : void RegionAllocator::Merge(AllRegionsSet::iterator prev_iter,
107 : AllRegionsSet::iterator next_iter) {
108 133747 : Region* prev = *prev_iter;
109 133747 : Region* next = *next_iter;
110 : DCHECK_EQ(prev->end(), next->begin());
111 133747 : prev->set_size(prev->size() + next->size());
112 :
113 133747 : all_regions_.erase(next_iter); // prev_iter stays valid.
114 :
115 : // The |next| region must already not be in the free list.
116 : DCHECK_EQ(free_regions_.find(next), free_regions_.end());
117 133747 : delete next;
118 133747 : }
119 :
120 134473 : RegionAllocator::Address RegionAllocator::AllocateRegion(size_t size) {
121 : DCHECK_NE(size, 0);
122 : DCHECK(IsAligned(size, page_size_));
123 :
124 134473 : Region* region = FreeListFindRegion(size);
125 134474 : if (region == nullptr) return kAllocationFailure;
126 :
127 268936 : if (region->size() != size) {
128 133728 : Split(region, size);
129 : }
130 : DCHECK(IsAligned(region->begin(), page_size_));
131 : DCHECK_EQ(region->size(), size);
132 :
133 : // Mark region as used.
134 134468 : FreeListRemoveRegion(region);
135 : region->set_is_used(true);
136 134468 : return region->begin();
137 : }
138 :
139 0 : RegionAllocator::Address RegionAllocator::AllocateRegion(
140 0 : RandomNumberGenerator* rng, size_t size) {
141 0 : if (free_size() >= max_load_for_randomization_) {
142 : // There is enough free space for trying to randomize the address.
143 0 : size_t random = 0;
144 :
145 0 : for (int i = 0; i < kMaxRandomizationAttempts; i++) {
146 0 : rng->NextBytes(&random, sizeof(random));
147 0 : size_t random_offset = page_size_ * (random % region_size_in_pages_);
148 0 : Address address = begin() + random_offset;
149 0 : if (AllocateRegionAt(address, size)) {
150 0 : return address;
151 : }
152 : }
153 : // Fall back to free list allocation.
154 : }
155 0 : return AllocateRegion(size);
156 : }
157 :
158 51 : bool RegionAllocator::AllocateRegionAt(Address requested_address, size_t size) {
159 : DCHECK(IsAligned(requested_address, page_size_));
160 : DCHECK_NE(size, 0);
161 : DCHECK(IsAligned(size, page_size_));
162 :
163 51 : Address requested_end = requested_address + size;
164 : DCHECK_LE(requested_end, end());
165 :
166 51 : Region* region;
167 : {
168 51 : AllRegionsSet::iterator region_iter = FindRegion(requested_address);
169 51 : if (region_iter == all_regions_.end()) {
170 : return false;
171 : }
172 51 : region = *region_iter;
173 : }
174 102 : if (region->is_used() || region->end() < requested_end) {
175 : return false;
176 : }
177 : // Found free region that includes the requested one.
178 51 : if (region->begin() != requested_address) {
179 : // Split the region at the |requested_address| boundary.
180 18 : size_t new_size = requested_address - region->begin();
181 : DCHECK(IsAligned(new_size, page_size_));
182 18 : region = Split(region, new_size);
183 : }
184 51 : if (region->end() != requested_end) {
185 : // Split the region at the |requested_end| boundary.
186 48 : Split(region, size);
187 : }
188 : DCHECK_EQ(region->begin(), requested_address);
189 : DCHECK_EQ(region->size(), size);
190 :
191 : // Mark region as used.
192 51 : FreeListRemoveRegion(region);
193 : region->set_is_used(true);
194 51 : return true;
195 : }
196 :
197 134466 : size_t RegionAllocator::TrimRegion(Address address, size_t new_size) {
198 : DCHECK(IsAligned(new_size, page_size_));
199 :
200 134466 : AllRegionsSet::iterator region_iter = FindRegion(address);
201 134466 : if (region_iter == all_regions_.end()) {
202 : return 0;
203 : }
204 268932 : Region* region = *region_iter;
205 537855 : if (region->begin() != address || !region->is_used()) {
206 : return 0;
207 : }
208 :
209 : // The region must not be in the free list.
210 : DCHECK_EQ(free_regions_.find(*region_iter), free_regions_.end());
211 :
212 134466 : if (new_size > 0) {
213 9 : region = Split(region, new_size);
214 : ++region_iter;
215 : }
216 : size_t size = region->size();
217 : region->set_is_used(false);
218 :
219 : // Merge current region with the surrounding ones if they are free.
220 268923 : if (region->end() != whole_region_.end()) {
221 : // There must be a range after the current one.
222 : AllRegionsSet::iterator next_iter = std::next(region_iter);
223 : DCHECK_NE(next_iter, all_regions_.end());
224 134461 : if (!(*next_iter)->is_used()) {
225 : // |next| region object will be deleted during merge, remove it from
226 : // the free list.
227 64992 : FreeListRemoveRegion(*next_iter);
228 64992 : Merge(region_iter, next_iter);
229 : }
230 : }
231 268923 : if (new_size == 0 && region->begin() != whole_region_.begin()) {
232 : // There must be a range before the current one.
233 : AllRegionsSet::iterator prev_iter = std::prev(region_iter);
234 : DCHECK_NE(prev_iter, all_regions_.end());
235 71073 : if (!(*prev_iter)->is_used()) {
236 : // |prev| region's size will change, we'll have to re-insert it into
237 : // the proper place of the free list.
238 68755 : FreeListRemoveRegion(*prev_iter);
239 68755 : Merge(prev_iter, region_iter);
240 : // |prev| region becomes the current region.
241 : region_iter = prev_iter;
242 68755 : region = *region_iter;
243 : }
244 : }
245 : FreeListAddRegion(region);
246 134466 : return size;
247 : }
248 :
249 6 : size_t RegionAllocator::CheckRegion(Address address) {
250 6 : AllRegionsSet::iterator region_iter = FindRegion(address);
251 6 : if (region_iter == all_regions_.end()) {
252 : return 0;
253 : }
254 12 : Region* region = *region_iter;
255 12 : if (region->begin() != address || !region->is_used()) {
256 : return 0;
257 : }
258 6 : return region->size();
259 : }
260 :
261 2 : bool RegionAllocator::IsFree(Address address, size_t size) {
262 2 : CHECK(contains(address, size));
263 2 : AllRegionsSet::iterator region_iter = FindRegion(address);
264 2 : if (region_iter == all_regions_.end()) {
265 : return true;
266 : }
267 2 : Region* region = *region_iter;
268 4 : return !region->is_used() && region->contains(address, size);
269 : }
270 :
271 0 : void RegionAllocator::Region::Print(std::ostream& os) const {
272 0 : std::ios::fmtflags flags = os.flags(std::ios::hex | std::ios::showbase);
273 0 : os << "[" << begin() << ", " << end() << "), size: " << size();
274 0 : os << ", " << (is_used() ? "used" : "free");
275 0 : os.flags(flags);
276 0 : }
277 :
278 0 : void RegionAllocator::Print(std::ostream& os) const {
279 0 : std::ios::fmtflags flags = os.flags(std::ios::hex | std::ios::showbase);
280 0 : os << "RegionAllocator: [" << begin() << ", " << end() << ")";
281 0 : os << "\nsize: " << size();
282 0 : os << "\nfree_size: " << free_size();
283 0 : os << "\npage_size: " << page_size_;
284 :
285 0 : os << "\nall regions: ";
286 0 : for (const Region* region : all_regions_) {
287 0 : os << "\n ";
288 0 : region->Print(os);
289 : }
290 :
291 0 : os << "\nfree regions: ";
292 0 : for (const Region* region : free_regions_) {
293 0 : os << "\n ";
294 0 : region->Print(os);
295 : }
296 0 : os << "\n";
297 0 : os.flags(flags);
298 0 : }
299 :
300 : } // namespace base
301 183867 : } // namespace v8
|
