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 63947 : 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 63947 : region_size_in_pages_(size() / page_size),
23 : max_load_for_randomization_(
24 63947 : static_cast<size_t>(size() * kMaxLoadFactorForRandomization)),
25 : free_size_(0),
26 127894 : page_size_(page_size) {
27 63947 : CHECK_LT(begin(), end());
28 63947 : CHECK(base::bits::IsPowerOfTwo(page_size_));
29 63947 : CHECK(IsAligned(size(), page_size_));
30 63947 : CHECK(IsAligned(begin(), page_size_));
31 :
32 : // Initial region.
33 63947 : Region* region = new Region(whole_region_);
34 :
35 : all_regions_.insert(region);
36 :
37 63947 : FreeListAddRegion(region);
38 63947 : }
39 :
40 127864 : RegionAllocator::~RegionAllocator() {
41 127905 : for (Region* region : all_regions_) {
42 63973 : delete region;
43 : }
44 63932 : }
45 :
46 70 : RegionAllocator::AllRegionsSet::iterator RegionAllocator::FindRegion(
47 : Address address) {
48 131857 : 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 457917 : 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 131728 : return iter == free_regions_.end() ? nullptr : *iter;
69 : }
70 :
71 393975 : 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 393975 : free_size_ -= region->size();
78 : free_regions_.erase(iter);
79 393975 : }
80 :
81 131132 : 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 262264 : new Region(region->begin() + new_size, region->size() - new_size, used);
91 131132 : if (!used) {
92 : // Remove region from the free list before updating it's size.
93 131123 : FreeListRemoveRegion(region);
94 : }
95 : region->set_size(new_size);
96 :
97 : all_regions_.insert(new_region);
98 :
99 131132 : if (!used) {
100 : FreeListAddRegion(region);
101 131123 : FreeListAddRegion(new_region);
102 : }
103 131132 : return new_region;
104 : }
105 :
106 131076 : void RegionAllocator::Merge(AllRegionsSet::iterator prev_iter,
107 : AllRegionsSet::iterator next_iter) {
108 131076 : Region* prev = *prev_iter;
109 131076 : Region* next = *next_iter;
110 : DCHECK_EQ(prev->end(), next->begin());
111 131076 : 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 131076 : delete next;
118 131076 : }
119 :
120 131728 : 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 131728 : if (region == nullptr) return kAllocationFailure;
126 :
127 131722 : if (region->size() != size) {
128 131049 : Split(region, size);
129 : }
130 : DCHECK(IsAligned(region->begin(), page_size_));
131 : DCHECK_EQ(region->size(), size);
132 :
133 : // Mark region as used.
134 131722 : FreeListRemoveRegion(region);
135 : region->set_is_used(true);
136 131722 : 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 55 : 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 55 : 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 55 : if (region_iter == all_regions_.end()) {
170 : return false;
171 : }
172 55 : region = *region_iter;
173 : }
174 110 : if (region->is_used() || region->end() < requested_end) {
175 : return false;
176 : }
177 : // Found free region that includes the requested one.
178 55 : if (region->begin() != requested_address) {
179 : // Split the region at the |requested_address| boundary.
180 22 : size_t new_size = requested_address - region->begin();
181 : DCHECK(IsAligned(new_size, page_size_));
182 22 : region = Split(region, new_size);
183 : }
184 55 : if (region->end() != requested_end) {
185 : // Split the region at the |requested_end| boundary.
186 52 : Split(region, size);
187 : }
188 : DCHECK_EQ(region->begin(), requested_address);
189 : DCHECK_EQ(region->size(), size);
190 :
191 : // Mark region as used.
192 55 : FreeListRemoveRegion(region);
193 : region->set_is_used(true);
194 55 : return true;
195 : }
196 :
197 131724 : 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 131724 : if (region_iter == all_regions_.end()) {
202 : return 0;
203 : }
204 131724 : Region* region = *region_iter;
205 131724 : 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 131724 : 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 131724 : 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 131719 : if (!(*next_iter)->is_used()) {
225 : // |next| region object will be deleted during merge, remove it from
226 : // the free list.
227 64125 : FreeListRemoveRegion(*next_iter);
228 64125 : Merge(region_iter, next_iter);
229 : }
230 : }
231 131724 : 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 68792 : 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 66951 : FreeListRemoveRegion(*prev_iter);
239 66951 : Merge(prev_iter, region_iter);
240 : // |prev| region becomes the current region.
241 : region_iter = prev_iter;
242 66951 : region = *region_iter;
243 : }
244 : }
245 : FreeListAddRegion(region);
246 131724 : 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 2 : bool RegionAllocator::IsFree(Address address, size_t size) {
262 2 : CHECK(contains(address, size));
263 : 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 : 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 121996 : } // namespace v8
|
