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 124591 : 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 124591 : region_size_in_pages_(size() / page_size),
23 : max_load_for_randomization_(
24 124591 : static_cast<size_t>(size() * kMaxLoadFactorForRandomization)),
25 : free_size_(0),
26 249182 : page_size_(page_size) {
27 124591 : CHECK_LT(begin(), end());
28 124591 : CHECK(base::bits::IsPowerOfTwo(page_size_));
29 124591 : CHECK(IsAligned(size(), page_size_));
30 124591 : CHECK(IsAligned(begin(), page_size_));
31 :
32 : // Initial region.
33 124591 : Region* region = new Region(whole_region_);
34 :
35 : all_regions_.insert(region);
36 :
37 124591 : FreeListAddRegion(region);
38 124592 : }
39 :
40 249124 : RegionAllocator::~RegionAllocator() {
41 372201 : for (Region* region : all_regions_) {
42 247639 : delete region;
43 : }
44 124562 : }
45 :
46 70 : RegionAllocator::AllRegionsSet::iterator RegionAllocator::FindRegion(
47 : Address address) {
48 993217 : 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 64 : return iter;
58 : }
59 :
60 0 : void RegionAllocator::FreeListAddRegion(Region* region) {
61 3118215 : free_size_ += region->size();
62 : free_regions_.insert(region);
63 0 : }
64 :
65 0 : RegionAllocator::Region* RegionAllocator::FreeListFindRegion(size_t size) {
66 : Region key(0, size, false);
67 : auto iter = free_regions_.lower_bound(&key);
68 931672 : return iter == free_regions_.end() ? nullptr : *iter;
69 : }
70 :
71 2932085 : void RegionAllocator::FreeListRemoveRegion(Region* region) {
72 : DCHECK(!region->is_used());
73 : 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 2932088 : free_size_ -= region->size();
78 : free_regions_.erase(iter);
79 2932091 : }
80 :
81 1031076 : 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 2062152 : new Region(region->begin() + new_size, region->size() - new_size, used);
91 1031076 : if (!used) {
92 : // Remove region from the free list before updating it's size.
93 1031026 : FreeListRemoveRegion(region);
94 : }
95 : region->set_size(new_size);
96 :
97 : all_regions_.insert(new_region);
98 :
99 1031074 : if (!used) {
100 : FreeListAddRegion(region);
101 1031026 : FreeListAddRegion(new_region);
102 : }
103 1031074 : return new_region;
104 : }
105 :
106 907827 : void RegionAllocator::Merge(AllRegionsSet::iterator prev_iter,
107 : AllRegionsSet::iterator next_iter) {
108 907827 : Region* prev = *prev_iter;
109 907827 : Region* next = *next_iter;
110 : DCHECK_EQ(prev->end(), next->begin());
111 907827 : prev->set_size(prev->size() + next->size());
112 :
113 : 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 907827 : delete next;
118 907829 : }
119 :
120 931672 : RegionAllocator::Address RegionAllocator::AllocateRegion(size_t size) {
121 : DCHECK_NE(size, 0);
122 : DCHECK(IsAligned(size, page_size_));
123 :
124 : Region* region = FreeListFindRegion(size);
125 931672 : if (region == nullptr) return kAllocationFailure;
126 :
127 931666 : if (region->size() != size) {
128 907915 : Split(region, size);
129 : }
130 : DCHECK(IsAligned(region->begin(), page_size_));
131 : DCHECK_EQ(region->size(), size);
132 :
133 : // Mark region as used.
134 931666 : FreeListRemoveRegion(region);
135 : region->set_is_used(true);
136 931664 : return region->begin();
137 : }
138 :
139 0 : RegionAllocator::Address RegionAllocator::AllocateRegion(
140 : 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 61574 : 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 61574 : Address requested_end = requested_address + size;
164 : DCHECK_LE(requested_end, end());
165 :
166 : Region* region;
167 : {
168 : AllRegionsSet::iterator region_iter = FindRegion(requested_address);
169 61574 : if (region_iter == all_regions_.end()) {
170 : return false;
171 : }
172 61574 : region = *region_iter;
173 : }
174 123148 : if (region->is_used() || region->end() < requested_end) {
175 : return false;
176 : }
177 : // Found free region that includes the requested one.
178 61574 : if (region->begin() != requested_address) {
179 : // Split the region at the |requested_address| boundary.
180 61541 : size_t new_size = requested_address - region->begin();
181 : DCHECK(IsAligned(new_size, page_size_));
182 61541 : region = Split(region, new_size);
183 : }
184 61574 : if (region->end() != requested_end) {
185 : // Split the region at the |requested_end| boundary.
186 61571 : Split(region, size);
187 : }
188 : DCHECK_EQ(region->begin(), requested_address);
189 : DCHECK_EQ(region->size(), size);
190 :
191 : // Mark region as used.
192 61574 : FreeListRemoveRegion(region);
193 : region->set_is_used(true);
194 61574 : return true;
195 : }
196 :
197 931567 : size_t RegionAllocator::TrimRegion(Address address, size_t new_size) {
198 : DCHECK(IsAligned(new_size, page_size_));
199 :
200 : AllRegionsSet::iterator region_iter = FindRegion(address);
201 931567 : if (region_iter == all_regions_.end()) {
202 : return 0;
203 : }
204 931567 : Region* region = *region_iter;
205 931567 : 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 931569 : if (new_size > 0) {
213 49 : 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 931570 : 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 931562 : if (!(*next_iter)->is_used()) {
225 : // |next| region object will be deleted during merge, remove it from
226 : // the free list.
227 345595 : FreeListRemoveRegion(*next_iter);
228 345596 : Merge(region_iter, next_iter);
229 : }
230 : }
231 931570 : 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 807966 : 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 562232 : FreeListRemoveRegion(*prev_iter);
239 562234 : Merge(prev_iter, region_iter);
240 : // |prev| region becomes the current region.
241 : region_iter = prev_iter;
242 562235 : region = *region_iter;
243 : }
244 : }
245 : FreeListAddRegion(region);
246 931572 : return size;
247 : }
248 :
249 6 : size_t RegionAllocator::CheckRegion(Address address) {
250 : AllRegionsSet::iterator region_iter = FindRegion(address);
251 6 : if (region_iter == all_regions_.end()) {
252 : return 0;
253 : }
254 6 : Region* region = *region_iter;
255 6 : if (region->begin() != address || !region->is_used()) {
256 : return 0;
257 : }
258 6 : return region->size();
259 : }
260 :
261 0 : bool RegionAllocator::IsFree(Address address, size_t size) {
262 0 : CHECK(contains(address, size));
263 : AllRegionsSet::iterator region_iter = FindRegion(address);
264 0 : if (region_iter == all_regions_.end()) {
265 : return true;
266 : }
267 0 : Region* region = *region_iter;
268 0 : 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 : 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 : os << "\nsize: " << size();
282 : 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 120216 : } // namespace v8
|
