region-allocator.cc 9.19 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
// 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.

#include "src/base/region-allocator.h"
#include "src/base/bits.h"
#include "src/base/macros.h"

namespace v8 {
namespace base {

// If |free_size| < |region_size| * |kMaxLoadFactorForRandomization| stop trying
// to randomize region allocation.
constexpr double kMaxLoadFactorForRandomization = 0.40;

// Max number of attempts to allocate page at random address.
constexpr int kMaxRandomizationAttempts = 3;

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
      region_size_in_pages_(size() / page_size),
23 24 25
      max_load_for_randomization_(
          static_cast<size_t>(size() * kMaxLoadFactorForRandomization)),
      free_size_(0),
26 27 28 29 30
      page_size_(page_size) {
  CHECK_LT(begin(), end());
  CHECK(base::bits::IsPowerOfTwo(page_size_));
  CHECK(IsAligned(size(), page_size_));
  CHECK(IsAligned(begin(), page_size_));
31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71

  // Initial region.
  Region* region = new Region(whole_region_);

  all_regions_.insert(region);

  FreeListAddRegion(region);
}

RegionAllocator::~RegionAllocator() {
  for (Region* region : all_regions_) {
    delete region;
  }
}

RegionAllocator::AllRegionsSet::iterator RegionAllocator::FindRegion(
    Address address) {
  if (!whole_region_.contains(address)) return all_regions_.end();

  Region key(address, 0, false);
  AllRegionsSet::iterator iter = all_regions_.upper_bound(&key);
  // Regions in |all_regions_| are compared by end() values and key's end()
  // points exactly to the address we are querying, so the upper_bound will
  // find the region whose |end()| is greater than the requested address.
  DCHECK_NE(iter, all_regions_.end());
  DCHECK((*iter)->contains(address));
  return iter;
}

void RegionAllocator::FreeListAddRegion(Region* region) {
  free_size_ += region->size();
  free_regions_.insert(region);
}

RegionAllocator::Region* RegionAllocator::FreeListFindRegion(size_t size) {
  Region key(0, size, false);
  auto iter = free_regions_.lower_bound(&key);
  return iter == free_regions_.end() ? nullptr : *iter;
}

void RegionAllocator::FreeListRemoveRegion(Region* region) {
72
  DCHECK(!region->is_used());
73 74
  auto iter = free_regions_.find(region);
  DCHECK_NE(iter, free_regions_.end());
75
  DCHECK_EQ(region, *iter);
76 77 78 79 80 81 82
  DCHECK_LE(region->size(), free_size_);
  free_size_ -= region->size();
  free_regions_.erase(iter);
}

RegionAllocator::Region* RegionAllocator::Split(Region* region,
                                                size_t new_size) {
83
  DCHECK(IsAligned(new_size, page_size_));
84
  DCHECK_NE(new_size, 0);
85 86 87
  DCHECK_GT(region->size(), new_size);

  // Create new region and put it to the lists after the |region|.
88
  bool used = region->is_used();
89
  Region* new_region =
90 91
      new Region(region->begin() + new_size, region->size() - new_size, used);
  if (!used) {
92 93 94 95 96 97 98
    // Remove region from the free list before updating it's size.
    FreeListRemoveRegion(region);
  }
  region->set_size(new_size);

  all_regions_.insert(new_region);

99 100 101 102
  if (!used) {
    FreeListAddRegion(region);
    FreeListAddRegion(new_region);
  }
103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121
  return new_region;
}

void RegionAllocator::Merge(AllRegionsSet::iterator prev_iter,
                            AllRegionsSet::iterator next_iter) {
  Region* prev = *prev_iter;
  Region* next = *next_iter;
  DCHECK_EQ(prev->end(), next->begin());
  prev->set_size(prev->size() + next->size());

  all_regions_.erase(next_iter);  // prev_iter stays valid.

  // The |next| region must already not be in the free list.
  DCHECK_EQ(free_regions_.find(next), free_regions_.end());
  delete next;
}

RegionAllocator::Address RegionAllocator::AllocateRegion(size_t size) {
  DCHECK_NE(size, 0);
122
  DCHECK(IsAligned(size, page_size_));
123 124 125 126 127 128 129

  Region* region = FreeListFindRegion(size);
  if (region == nullptr) return kAllocationFailure;

  if (region->size() != size) {
    Split(region, size);
  }
130
  DCHECK(IsAligned(region->begin(), page_size_));
131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146
  DCHECK_EQ(region->size(), size);

  // Mark region as used.
  FreeListRemoveRegion(region);
  region->set_is_used(true);
  return region->begin();
}

RegionAllocator::Address RegionAllocator::AllocateRegion(
    RandomNumberGenerator* rng, size_t size) {
  if (free_size() >= max_load_for_randomization_) {
    // There is enough free space for trying to randomize the address.
    size_t random = 0;

    for (int i = 0; i < kMaxRandomizationAttempts; i++) {
      rng->NextBytes(&random, sizeof(random));
147
      size_t random_offset = page_size_ * (random % region_size_in_pages_);
148 149 150 151 152 153 154 155 156 157 158
      Address address = begin() + random_offset;
      if (AllocateRegionAt(address, size)) {
        return address;
      }
    }
    // Fall back to free list allocation.
  }
  return AllocateRegion(size);
}

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 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180

  Address requested_end = requested_address + size;
  DCHECK_LE(requested_end, end());

  Region* region;
  {
    AllRegionsSet::iterator region_iter = FindRegion(requested_address);
    if (region_iter == all_regions_.end()) {
      return false;
    }
    region = *region_iter;
  }
  if (region->is_used() || region->end() < requested_end) {
    return false;
  }
  // Found free region that includes the requested one.
  if (region->begin() != requested_address) {
    // Split the region at the |requested_address| boundary.
    size_t new_size = requested_address - region->begin();
181
    DCHECK(IsAligned(new_size, page_size_));
182 183 184 185 186 187 188 189 190 191 192 193 194 195 196
    region = Split(region, new_size);
  }
  if (region->end() != requested_end) {
    // Split the region at the |requested_end| boundary.
    Split(region, size);
  }
  DCHECK_EQ(region->begin(), requested_address);
  DCHECK_EQ(region->size(), size);

  // Mark region as used.
  FreeListRemoveRegion(region);
  region->set_is_used(true);
  return true;
}

197 198 199
size_t RegionAllocator::TrimRegion(Address address, size_t new_size) {
  DCHECK(IsAligned(new_size, page_size_));

200 201 202 203 204 205 206 207 208 209 210 211
  AllRegionsSet::iterator region_iter = FindRegion(address);
  if (region_iter == all_regions_.end()) {
    return 0;
  }
  Region* region = *region_iter;
  if (region->begin() != address || !region->is_used()) {
    return 0;
  }

  // The region must not be in the free list.
  DCHECK_EQ(free_regions_.find(*region_iter), free_regions_.end());

212 213 214 215 216
  if (new_size > 0) {
    region = Split(region, new_size);
    ++region_iter;
  }
  size_t size = region->size();
217 218 219 220 221 222 223 224 225 226 227 228 229 230
  region->set_is_used(false);

  // Merge current region with the surrounding ones if they are free.
  if (region->end() != whole_region_.end()) {
    // There must be a range after the current one.
    AllRegionsSet::iterator next_iter = std::next(region_iter);
    DCHECK_NE(next_iter, all_regions_.end());
    if (!(*next_iter)->is_used()) {
      // |next| region object will be deleted during merge, remove it from
      // the free list.
      FreeListRemoveRegion(*next_iter);
      Merge(region_iter, next_iter);
    }
  }
231
  if (new_size == 0 && region->begin() != whole_region_.begin()) {
232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248
    // There must be a range before the current one.
    AllRegionsSet::iterator prev_iter = std::prev(region_iter);
    DCHECK_NE(prev_iter, all_regions_.end());
    if (!(*prev_iter)->is_used()) {
      // |prev| region's size will change, we'll have to re-insert it into
      // the proper place of the free list.
      FreeListRemoveRegion(*prev_iter);
      Merge(prev_iter, region_iter);
      // |prev| region becomes the current region.
      region_iter = prev_iter;
      region = *region_iter;
    }
  }
  FreeListAddRegion(region);
  return size;
}

249 250 251 252 253 254 255 256 257 258 259 260
size_t RegionAllocator::CheckRegion(Address address) {
  AllRegionsSet::iterator region_iter = FindRegion(address);
  if (region_iter == all_regions_.end()) {
    return 0;
  }
  Region* region = *region_iter;
  if (region->begin() != address || !region->is_used()) {
    return 0;
  }
  return region->size();
}

261 262 263 264 265 266 267 268 269 270
bool RegionAllocator::IsFree(Address address, size_t size) {
  CHECK(contains(address, size));
  AllRegionsSet::iterator region_iter = FindRegion(address);
  if (region_iter == all_regions_.end()) {
    return true;
  }
  Region* region = *region_iter;
  return !region->is_used() && region->contains(address, size);
}

271 272 273 274 275 276 277 278 279 280 281 282
void RegionAllocator::Region::Print(std::ostream& os) const {
  std::ios::fmtflags flags = os.flags(std::ios::hex | std::ios::showbase);
  os << "[" << begin() << ", " << end() << "), size: " << size();
  os << ", " << (is_used() ? "used" : "free");
  os.flags(flags);
}

void RegionAllocator::Print(std::ostream& os) const {
  std::ios::fmtflags flags = os.flags(std::ios::hex | std::ios::showbase);
  os << "RegionAllocator: [" << begin() << ", " << end() << ")";
  os << "\nsize: " << size();
  os << "\nfree_size: " << free_size();
283
  os << "\npage_size: " << page_size_;
284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301

  os << "\nall regions: ";
  for (const Region* region : all_regions_) {
    os << "\n  ";
    region->Print(os);
  }

  os << "\nfree regions: ";
  for (const Region* region : free_regions_) {
    os << "\n  ";
    region->Print(os);
  }
  os << "\n";
  os.flags(flags);
}

}  // namespace base
}  // namespace v8