region-allocator.h 5.62 KB
Newer Older
1 2 3 4 5 6 7 8 9
// Copyright 2018 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_BASE_REGION_ALLOCATOR_H_
#define V8_BASE_REGION_ALLOCATOR_H_

#include <set>

10
#include "src/base/address-region.h"
11 12 13 14 15 16 17
#include "src/base/utils/random-number-generator.h"
#include "testing/gtest/include/gtest/gtest_prod.h"  // nogncheck

namespace v8 {
namespace base {

// Helper class for managing used/free regions within [address, address+size)
18 19
// region. Minimum allocation unit is |page_size|. Requested allocation size
// is rounded up to |page_size|.
20 21 22 23 24 25 26 27
// The region allocation algorithm implements best-fit with coalescing strategy:
// it tries to find a smallest suitable free region upon allocation and tries
// to merge region with its neighbors upon freeing.
//
// This class does not perform any actual region reservation.
// Not thread-safe.
class V8_BASE_EXPORT RegionAllocator final {
 public:
28
  using Address = uintptr_t;
29 30 31

  static constexpr Address kAllocationFailure = static_cast<Address>(-1);

32
  RegionAllocator(Address address, size_t size, size_t page_size);
33 34
  ~RegionAllocator();

35
  // Allocates region of |size| (must be |page_size|-aligned). Returns
36 37 38 39 40 41
  // the address of the region on success or kAllocationFailure.
  Address AllocateRegion(size_t size);
  // Same as above but tries to randomize the region displacement.
  Address AllocateRegion(RandomNumberGenerator* rng, size_t size);

  // 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 44 45 46 47 48
  // true.
  // This kind of allocation is supposed to be used during setup phase to mark
  // certain regions as used or for randomizing regions displacement.
  bool AllocateRegionAt(Address requested_address, size_t size);

  // Frees region at given |address|, returns the size of the region.
49 50
  // There must be a used region starting at given address otherwise nothing
  // will be freed and 0 will be returned.
51 52 53 54 55 56 57
  size_t FreeRegion(Address address) { return TrimRegion(address, 0); }

  // Decreases size of the previously allocated region at |address|, returns
  // freed size. |new_size| must be |page_size|-aligned and
  // less than or equal to current region's size. Setting new size to zero
  // frees the region.
  size_t TrimRegion(Address address, size_t new_size);
58

59 60 61 62
  // If there is a used region starting at given address returns its size
  // otherwise 0.
  size_t CheckRegion(Address address);

63 64 65
  // Returns true if there are no pages allocated in given region.
  bool IsFree(Address address, size_t size);

66 67 68 69
  Address begin() const { return whole_region_.begin(); }
  Address end() const { return whole_region_.end(); }
  size_t size() const { return whole_region_.size(); }

70 71 72 73
  bool contains(Address address) const {
    return whole_region_.contains(address);
  }

74 75 76 77
  bool contains(Address address, size_t size) const {
    return whole_region_.contains(address, size);
  }

78 79 80
  // Total size of not yet aquired regions.
  size_t free_size() const { return free_size_; }

81 82 83 84
  // The alignment of the allocated region's addresses and granularity of
  // the allocated region's sizes.
  size_t page_size() const { return page_size_; }

85 86 87
  void Print(std::ostream& os) const;

 private:
88
  class Region : public AddressRegion {
89
   public:
90 91
    Region(Address address, size_t size, bool is_used)
        : AddressRegion(address, size), is_used_(is_used) {}
92

93 94 95 96 97 98 99 100 101 102 103 104
    bool is_used() const { return is_used_; }
    void set_is_used(bool used) { is_used_ = used; }

    void Print(std::ostream& os) const;

   private:
    bool is_used_;
  };

  // The whole region.
  const Region whole_region_;

105 106
  // Number of |page_size_| in the whole region.
  const size_t region_size_in_pages_;
107 108 109 110 111 112 113 114 115

  // If the free size is less than this value - stop trying to randomize the
  // allocation addresses.
  const size_t max_load_for_randomization_;

  // Size of all free regions.
  size_t free_size_;

  // Minimum region size. Must be a pow of 2.
116
  const size_t page_size_;
117 118 119 120 121 122 123

  struct AddressEndOrder {
    bool operator()(const Region* a, const Region* b) const {
      return a->end() < b->end();
    }
  };
  // All regions ordered by addresses.
124
  using AllRegionsSet = std::set<Region*, AddressEndOrder>;
125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158
  AllRegionsSet all_regions_;

  struct SizeAddressOrder {
    bool operator()(const Region* a, const Region* b) const {
      if (a->size() != b->size()) return a->size() < b->size();
      return a->begin() < b->begin();
    }
  };
  // Free regions ordered by sizes and addresses.
  std::set<Region*, SizeAddressOrder> free_regions_;

  // Returns region containing given address or nullptr.
  AllRegionsSet::iterator FindRegion(Address address);

  // Adds given region to the set of free regions.
  void FreeListAddRegion(Region* region);

  // Finds best-fit free region for given size.
  Region* FreeListFindRegion(size_t size);

  // Removes given region from the set of free regions.
  void FreeListRemoveRegion(Region* region);

  // Splits given |region| into two: one of |new_size| size and a new one
  // having the rest. The new region is returned.
  Region* Split(Region* region, size_t new_size);

  // For two coalescing regions merges |next| to |prev| and deletes |next|.
  void Merge(AllRegionsSet::iterator prev_iter,
             AllRegionsSet::iterator next_iter);

  FRIEND_TEST(RegionAllocatorTest, AllocateRegionRandom);
  FRIEND_TEST(RegionAllocatorTest, Fragmentation);
  FRIEND_TEST(RegionAllocatorTest, FindRegion);
159
  FRIEND_TEST(RegionAllocatorTest, Contains);
160 161 162 163 164 165 166 167

  DISALLOW_COPY_AND_ASSIGN(RegionAllocator);
};

}  // namespace base
}  // namespace v8

#endif  // V8_BASE_REGION_ALLOCATOR_H_