folly/experimental/fibers/GuardPageAllocator.cpp

   1 /*
   2  * Copyright 2016 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16 #include "GuardPageAllocator.h"
  17
  18 #include <unistd.h>
  19
  20 #include <mutex>
  21
  22 #include <folly/Singleton.h>
  23 #include <folly/SpinLock.h>
  24 #include <folly/portability/SysMman.h>
  25
  26 #include <glog/logging.h>
  27
  28 namespace folly {
  29 namespace fibers {
  30
  31 /**
  32  * Each stack with a guard page creates two memory mappings.
  33  * Since this is a limited resource, we don't want to create too many of these.
  34  *
  35  * The upper bound on total number of mappings created
  36  * is kNumGuarded * kMaxInUse.
  37  */
  38
  39 /**
  40  * Number of guarded stacks per allocator instance
  41  */
  42 constexpr size_t kNumGuarded = 100;
  43
  44 /**
  45  * Maximum number of allocator instances with guarded stacks enabled
  46  */
  47 constexpr size_t kMaxInUse = 100;
  48
  49 /**
  50  * A cache for kNumGuarded stacks of a given size
  51  *
  52  * Thread safe.
  53  */
  54 class StackCache {
  55  public:
  56   explicit StackCache(size_t stackSize) : allocSize_(allocSize(stackSize)) {
  57     auto p = ::mmap(
  58         nullptr,
  59         allocSize_ * kNumGuarded,
  60         PROT_READ | PROT_WRITE,
  61         MAP_PRIVATE | MAP_ANONYMOUS,
  62         -1,
  63         0);
  64     PCHECK(p != (void*)(-1));
  65     storage_ = reinterpret_cast<unsigned char*>(p);
  66
  67     /* Protect the bottommost page of every stack allocation */
  68     for (size_t i = 0; i < kNumGuarded; ++i) {
  69       auto allocBegin = storage_ + allocSize_ * i;
  70       freeList_.emplace_back(allocBegin, /* protected= */ false);
  71     }
  72   }
  73
  74   unsigned char* borrow(size_t size) {
  75     std::lock_guard<folly::SpinLock> lg(lock_);
  76
  77     assert(storage_);
  78
  79     auto as = allocSize(size);
  80     if (as != allocSize_ || freeList_.empty()) {
  81       return nullptr;
  82     }
  83
  84     auto p = freeList_.back().first;
  85     if (!freeList_.back().second) {
  86       PCHECK(0 == ::mprotect(p, pagesize(), PROT_NONE));
  87     }
  88     freeList_.pop_back();
  89
  90     /* We allocate minimum number of pages required, plus a guard page.
  91        Since we use this for stack storage, requested allocation is aligned
  92        at the top of the allocated pages, while the guard page is at the bottom.
  93
  94                -- increasing addresses -->
  95              Guard page     Normal pages
  96             |xxxxxxxxxx|..........|..........|
  97             <- allocSize_ ------------------->
  98          p -^                <- size -------->
  99                       limit -^
 100     */
 101     auto limit = p + allocSize_ - size;
 102     assert(limit >= p + pagesize());
 103     return limit;
 104   }
 105
 106   bool giveBack(unsigned char* limit, size_t size) {
 107     std::lock_guard<folly::SpinLock> lg(lock_);
 108
 109     assert(storage_);
 110
 111     auto as = allocSize(size);
 112     auto p = limit + size - as;
 113     if (p < storage_ || p >= storage_ + allocSize_ * kNumGuarded) {
 114       /* not mine */
 115       return false;
 116     }
 117
 118     assert(as == allocSize_);
 119     assert((p - storage_) % allocSize_ == 0);
 120     freeList_.emplace_back(p, /* protected= */ true);
 121     return true;
 122   }
 123
 124   ~StackCache() {
 125     assert(storage_);
 126     PCHECK(0 == ::munmap(storage_, allocSize_ * kNumGuarded));
 127   }
 128
 129  private:
 130   folly::SpinLock lock_;
 131   unsigned char* storage_{nullptr};
 132   size_t allocSize_{0};
 133
 134   /**
 135    * LIFO free list. Each pair contains stack pointer and protected flag.
 136    */
 137   std::vector<std::pair<unsigned char*, bool>> freeList_;
 138
 139   static size_t pagesize() {
 140     static const size_t pagesize = sysconf(_SC_PAGESIZE);
 141     return pagesize;
 142   }
 143
 144   /* Returns a multiple of pagesize() enough to store size + one guard page */
 145   static size_t allocSize(size_t size) {
 146     return pagesize() * ((size + pagesize() - 1) / pagesize() + 1);
 147   }
 148 };
 149
 150 class CacheManager {
 151  public:
 152   static CacheManager& instance() {
 153     static auto inst = new CacheManager();
 154     return *inst;
 155   }
 156
 157   std::unique_ptr<StackCacheEntry> getStackCache(size_t stackSize) {
 158     std::lock_guard<folly::SpinLock> lg(lock_);
 159     if (inUse_ < kMaxInUse) {
 160       ++inUse_;
 161       return folly::make_unique<StackCacheEntry>(stackSize);
 162     }
 163
 164     return nullptr;
 165   }
 166
 167  private:
 168   folly::SpinLock lock_;
 169   size_t inUse_{0};
 170
 171   friend class StackCacheEntry;
 172
 173   void giveBack(std::unique_ptr<StackCache> /* stackCache_ */) {
 174     assert(inUse_ > 0);
 175     --inUse_;
 176     /* Note: we can add a free list for each size bucket
 177        if stack re-use is important.
 178        In this case this needs to be a folly::Singleton
 179        to make sure the free list is cleaned up on fork.
 180
 181        TODO(t7351705): fix Singleton destruction order
 182     */
 183   }
 184 };
 185
 186 /*
 187  * RAII Wrapper around a StackCache that calls
 188  * CacheManager::giveBack() on destruction.
 189  */
 190 class StackCacheEntry {
 191  public:
 192   explicit StackCacheEntry(size_t stackSize)
 193       : stackCache_(folly::make_unique<StackCache>(stackSize)) {}
 194
 195   StackCache& cache() const noexcept {
 196     return *stackCache_;
 197   }
 198
 199   ~StackCacheEntry() {
 200     CacheManager::instance().giveBack(std::move(stackCache_));
 201   }
 202
 203  private:
 204   std::unique_ptr<StackCache> stackCache_;
 205 };
 206
 207 GuardPageAllocator::GuardPageAllocator(bool useGuardPages)
 208     : useGuardPages_(useGuardPages) {}
 209
 210 GuardPageAllocator::~GuardPageAllocator() = default;
 211
 212 unsigned char* GuardPageAllocator::allocate(size_t size) {
 213   if (useGuardPages_ && !stackCache_) {
 214     stackCache_ = CacheManager::instance().getStackCache(size);
 215   }
 216
 217   if (stackCache_) {
 218     auto p = stackCache_->cache().borrow(size);
 219     if (p != nullptr) {
 220       return p;
 221     }
 222   }
 223   return fallbackAllocator_.allocate(size);
 224 }
 225
 226 void GuardPageAllocator::deallocate(unsigned char* limit, size_t size) {
 227   if (!(stackCache_ && stackCache_->cache().giveBack(limit, size))) {
 228     fallbackAllocator_.deallocate(limit, size);
 229   }
 230 }
 231 }
 232 } // folly::fibers