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
14namespace v8 {
15namespace 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.
26class V8_BASE_EXPORT RegionAllocator final {
27 public:
28  using Address = uintptr_t;
29
30  using SplitMergeCallback = std::function<void(Address start, size_t size)>;
31
32  static constexpr Address kAllocationFailure = static_cast<Address>(-1);
33
34  enum class RegionState {
35    // The region can be allocated from.
36    kFree,
37    // The region has been carved out of the wider area and is not allocatable.
38    kExcluded,
39    // The region has been allocated and is managed by a RegionAllocator.
40    kAllocated,
41  };
42
43  RegionAllocator(Address address, size_t size, size_t page_size);
44  RegionAllocator(const RegionAllocator&) = delete;
45  RegionAllocator& operator=(const RegionAllocator&) = delete;
46  ~RegionAllocator();
47
48  // Split and merge callbacks.
49  //
50  // These callbacks can be installed to perform additional logic when regions
51  // are split or merged. For example, when managing Windows placeholder
52  // regions, a region must be split into sub-regions (using
53  // VirtualFree(MEM_PRESERVE_PLACEHOLDER)) before a part of it can be replaced
54  // with an actual memory mapping. Similarly, multiple sub-regions must be
55  // merged (using VirtualFree(MEM_COALESCE_PLACEHOLDERS)) when coalescing them
56  // into a larger, free region again.
57  //
58  // The on_split callback is called to signal that an existing region is split
59  // so that [start, start+size) becomes a new region.
60  void set_on_split_callback(SplitMergeCallback callback) {
61    on_split_ = callback;
62  }
63  // The on_merge callback is called to signal that all regions in the range
64  // [start, start+size) are merged into a single one.
65  void set_on_merge_callback(SplitMergeCallback callback) {
66    on_merge_ = callback;
67  }
68
69  // Allocates region of |size| (must be |page_size|-aligned). Returns
70  // the address of the region on success or kAllocationFailure.
71  Address AllocateRegion(size_t size);
72  // Same as above but tries to randomize the region displacement.
73  Address AllocateRegion(RandomNumberGenerator* rng, size_t size);
74
75  // Allocates region of |size| at |requested_address| if it's free. Both the
76  // address and the size must be |page_size|-aligned. On success returns
77  // true.
78  // This kind of allocation is supposed to be used during setup phase to mark
79  // certain regions as used or for randomizing regions displacement.
80  // By default regions are marked as used, but can also be allocated as
81  // RegionState::kExcluded to prevent the RegionAllocator from using that
82  // memory range, which is useful when reserving any area to remap shared
83  // memory into.
84  bool AllocateRegionAt(Address requested_address, size_t size,
85                        RegionState region_state = RegionState::kAllocated);
86
87  // Allocates a region of |size| aligned to |alignment|. The size and alignment
88  // must be a multiple of |page_size|. Returns the address of the region on
89  // success or kAllocationFailure.
90  Address AllocateAlignedRegion(size_t size, size_t alignment);
91
92  // Attempts to allocate a region of the given size and alignment at the
93  // specified address but fall back to allocating the region elsewhere if
94  // necessary.
95  Address AllocateRegion(Address hint, size_t size, size_t alignment);
96
97  // Frees region at given |address|, returns the size of the region.
98  // There must be a used region starting at given address otherwise nothing
99  // will be freed and 0 will be returned.
100  size_t FreeRegion(Address address) { return TrimRegion(address, 0); }
101
102  // Decreases size of the previously allocated region at |address|, returns
103  // freed size. |new_size| must be |page_size|-aligned and
104  // less than or equal to current region's size. Setting new size to zero
105  // frees the region.
106  size_t TrimRegion(Address address, size_t new_size);
107
108  // If there is a used region starting at given address returns its size
109  // otherwise 0.
110  size_t CheckRegion(Address address);
111
112  // Returns true if there are no pages allocated in given region.
113  bool IsFree(Address address, size_t size);
114
115  Address begin() const { return whole_region_.begin(); }
116  Address end() const { return whole_region_.end(); }
117  size_t size() const { return whole_region_.size(); }
118
119  bool contains(Address address) const {
120    return whole_region_.contains(address);
121  }
122
123  bool contains(Address address, size_t size) const {
124    return whole_region_.contains(address, size);
125  }
126
127  // Total size of not yet aquired regions.
128  size_t free_size() const { return free_size_; }
129
130  // The alignment of the allocated region's addresses and granularity of
131  // the allocated region's sizes.
132  size_t page_size() const { return page_size_; }
133
134  void Print(std::ostream& os) const;
135
136 private:
137  class Region : public AddressRegion {
138   public:
139    Region(Address address, size_t size, RegionState state)
140        : AddressRegion(address, size), state_(state) {}
141
142    bool is_free() const { return state_ == RegionState::kFree; }
143    bool is_allocated() const { return state_ == RegionState::kAllocated; }
144    bool is_excluded() const { return state_ == RegionState::kExcluded; }
145
146    RegionState state() { return state_; }
147    void set_state(RegionState state) { state_ = state; }
148
149    void Print(std::ostream& os) const;
150
151   private:
152    RegionState state_;
153  };
154
155  // The whole region.
156  const Region whole_region_;
157
158  // Number of |page_size_| in the whole region.
159  const size_t region_size_in_pages_;
160
161  // If the free size is less than this value - stop trying to randomize the
162  // allocation addresses.
163  const size_t max_load_for_randomization_;
164
165  // Size of all free regions.
166  size_t free_size_;
167
168  // Minimum region size. Must be a pow of 2.
169  const size_t page_size_;
170
171  struct AddressEndOrder {
172    bool operator()(const Region* a, const Region* b) const {
173      return a->end() < b->end();
174    }
175  };
176  // All regions ordered by addresses.
177  using AllRegionsSet = std::set<Region*, AddressEndOrder>;
178  AllRegionsSet all_regions_;
179
180  struct SizeAddressOrder {
181    bool operator()(const Region* a, const Region* b) const {
182      if (a->size() != b->size()) return a->size() < b->size();
183      return a->begin() < b->begin();
184    }
185  };
186  // Free regions ordered by sizes and addresses.
187  std::set<Region*, SizeAddressOrder> free_regions_;
188
189  // Callbacks called when regions are split or merged.
190  SplitMergeCallback on_split_;
191  SplitMergeCallback on_merge_;
192
193  // Returns region containing given address or nullptr.
194  AllRegionsSet::iterator FindRegion(Address address);
195
196  // Adds given region to the set of free regions.
197  void FreeListAddRegion(Region* region);
198
199  // Finds best-fit free region for given size.
200  Region* FreeListFindRegion(size_t size);
201
202  // Removes given region from the set of free regions.
203  void FreeListRemoveRegion(Region* region);
204
205  // Splits given |region| into two: one of |new_size| size and a new one
206  // having the rest. The new region is returned.
207  Region* Split(Region* region, size_t new_size);
208
209  // For two coalescing regions merges |next| to |prev| and deletes |next|.
210  void Merge(AllRegionsSet::iterator prev_iter,
211             AllRegionsSet::iterator next_iter);
212
213  FRIEND_TEST(RegionAllocatorTest, AllocateExcluded);
214  FRIEND_TEST(RegionAllocatorTest, AllocateRegionRandom);
215  FRIEND_TEST(RegionAllocatorTest, Contains);
216  FRIEND_TEST(RegionAllocatorTest, FindRegion);
217  FRIEND_TEST(RegionAllocatorTest, Fragmentation);
218};
219
220}  // namespace base
221}  // namespace v8
222
223#endif  // V8_BASE_REGION_ALLOCATOR_H_
224