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 : #ifndef V8_BASE_REGION_ALLOCATOR_H_
6 : #define V8_BASE_REGION_ALLOCATOR_H_
7 :
8 : #include <set>
9 :
10 : #include "src/base/address-region.h"
11 : #include "src/base/utils/random-number-generator.h"
12 : #include "testing/gtest/include/gtest/gtest_prod.h" // nogncheck
13 :
14 : namespace v8 {
15 : namespace base {
16 :
17 : // Helper class for managing used/free regions within [address, address+size)
18 : // region. Minimum allocation unit is |page_size|. Requested allocation size
19 : // is rounded up to |page_size|.
20 : // The region allocation algorithm implements best-fit with coalescing strategy:
21 : // it tries to find a smallest suitable free region upon allocation and tries
22 : // to merge region with its neighbors upon freeing.
23 : //
24 : // This class does not perform any actual region reservation.
25 : // Not thread-safe.
26 : class V8_BASE_EXPORT RegionAllocator final {
27 : public:
28 : typedef uintptr_t Address;
29 :
30 : static constexpr Address kAllocationFailure = static_cast<Address>(-1);
31 :
32 : RegionAllocator(Address address, size_t size, size_t page_size);
33 : ~RegionAllocator();
34 :
35 : // Allocates region of |size| (must be |page_size|-aligned). Returns
36 : // the address of the region on success or kAllocationFailure.
37 : Address AllocateRegion(size_t size);
38 : // Same as above but tries to randomize the region displacement.
39 : Address AllocateRegion(RandomNumberGenerator* rng, size_t size);
40 :
41 : // Allocates region of |size| at |requested_address| if it's free. Both the
42 : // address and the size must be |page_size|-aligned. On success returns
43 : // true.
44 : // This kind of allocation is supposed to be used during setup phase to mark
45 : // certain regions as used or for randomizing regions displacement.
46 : bool AllocateRegionAt(Address requested_address, size_t size);
47 :
48 : // Frees region at given |address|, returns the size of the region.
49 : // There must be a used region starting at given address otherwise nothing
50 : // will be freed and 0 will be returned.
51 133839 : size_t FreeRegion(Address address) { return TrimRegion(address, 0); }
52 :
53 : // Decreases size of the previously allocated region at |address|, returns
54 : // freed size. |new_size| must be |page_size|-aligned and
55 : // less than or equal to current region's size. Setting new size to zero
56 : // frees the region.
57 : size_t TrimRegion(Address address, size_t new_size);
58 :
59 : // If there is a used region starting at given address returns its size
60 : // otherwise 0.
61 : size_t CheckRegion(Address address);
62 :
63 : // Returns true if there are no pages allocated in given region.
64 : bool IsFree(Address address, size_t size);
65 :
66 0 : Address begin() const { return whole_region_.begin(); }
67 : Address end() const { return whole_region_.end(); }
68 0 : size_t size() const { return whole_region_.size(); }
69 :
70 : bool contains(Address address) const {
71 : return whole_region_.contains(address);
72 : }
73 :
74 : bool contains(Address address, size_t size) const {
75 : return whole_region_.contains(address, size);
76 : }
77 :
78 : // Total size of not yet aquired regions.
79 : size_t free_size() const { return free_size_; }
80 :
81 : // The alignment of the allocated region's addresses and granularity of
82 : // the allocated region's sizes.
83 : size_t page_size() const { return page_size_; }
84 :
85 : void Print(std::ostream& os) const;
86 :
87 : private:
88 : class Region : public AddressRegion {
89 : public:
90 : Region(Address address, size_t size, bool is_used)
91 329552 : : AddressRegion(address, size), is_used_(is_used) {}
92 :
93 : bool is_used() const { return is_used_; }
94 267751 : void set_is_used(bool used) { is_used_ = used; }
95 :
96 : void Print(std::ostream& os) const;
97 :
98 : private:
99 : bool is_used_;
100 : };
101 :
102 : // The whole region.
103 : const Region whole_region_;
104 :
105 : // Number of |page_size_| in the whole region.
106 : const size_t region_size_in_pages_;
107 :
108 : // If the free size is less than this value - stop trying to randomize the
109 : // allocation addresses.
110 : const size_t max_load_for_randomization_;
111 :
112 : // Size of all free regions.
113 : size_t free_size_;
114 :
115 : // Minimum region size. Must be a pow of 2.
116 : const size_t page_size_;
117 :
118 : struct AddressEndOrder {
119 : bool operator()(const Region* a, const Region* b) const {
120 235432 : return a->end() < b->end();
121 : }
122 : };
123 : // All regions ordered by addresses.
124 : typedef std::set<Region*, AddressEndOrder> AllRegionsSet;
125 : AllRegionsSet all_regions_;
126 :
127 : struct SizeAddressOrder {
128 : bool operator()(const Region* a, const Region* b) const {
129 1548483 : if (a->size() != b->size()) return a->size() < b->size();
130 801119 : return a->begin() < b->begin();
131 : }
132 : };
133 : // Free regions ordered by sizes and addresses.
134 : std::set<Region*, SizeAddressOrder> free_regions_;
135 :
136 : // Returns region containing given address or nullptr.
137 : AllRegionsSet::iterator FindRegion(Address address);
138 :
139 : // Adds given region to the set of free regions.
140 : void FreeListAddRegion(Region* region);
141 :
142 : // Finds best-fit free region for given size.
143 : Region* FreeListFindRegion(size_t size);
144 :
145 : // Removes given region from the set of free regions.
146 : void FreeListRemoveRegion(Region* region);
147 :
148 : // Splits given |region| into two: one of |new_size| size and a new one
149 : // having the rest. The new region is returned.
150 : Region* Split(Region* region, size_t new_size);
151 :
152 : // For two coalescing regions merges |next| to |prev| and deletes |next|.
153 : void Merge(AllRegionsSet::iterator prev_iter,
154 : AllRegionsSet::iterator next_iter);
155 :
156 : FRIEND_TEST(RegionAllocatorTest, AllocateRegionRandom);
157 : FRIEND_TEST(RegionAllocatorTest, Fragmentation);
158 : FRIEND_TEST(RegionAllocatorTest, FindRegion);
159 : FRIEND_TEST(RegionAllocatorTest, Contains);
160 :
161 : DISALLOW_COPY_AND_ASSIGN(RegionAllocator);
162 : };
163 :
164 : } // namespace base
165 : } // namespace v8
166 :
167 : #endif // V8_BASE_REGION_ALLOCATOR_H_
|
