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 { namespace fibers {
  29
  30 /**
  31  * Each stack with a guard page creates two memory mappings.
  32  * Since this is a limited resource, we don't want to create too many of these.
  33  *
  34  * The upper bound on total number of mappings created
  35  * is kNumGuarded * kMaxInUse.
  36  */
  37
  38 /**
  39  * Number of guarded stacks per allocator instance
  40  */
  41 constexpr size_t kNumGuarded = 100;
  42
  43 /**
  44  * Maximum number of allocator instances with guarded stacks enabled
  45  */
  46 constexpr size_t kMaxInUse = 100;
  47
  48 /**
  49  * A cache for kNumGuarded stacks of a given size
  50  *
  51  * Thread safe.
  52  */
  53 class StackCache {
  54  public:
  55   explicit StackCache(size_t stackSize)
  56       : allocSize_(allocSize(stackSize)) {
  57     auto p = ::mmap(nullptr, allocSize_ * kNumGuarded,
  58                     PROT_READ | PROT_WRITE,
  59                     MAP_PRIVATE | MAP_ANONYMOUS,
  60                     -1, 0);
  61     PCHECK(p != (void*)(-1));
  62     storage_ = reinterpret_cast<unsigned char*>(p);
  63
  64     /* Protect the bottommost page of every stack allocation */
  65     for (size_t i = 0; i < kNumGuarded; ++i) {
  66       auto allocBegin = storage_ + allocSize_ * i;
  67       freeList_.push_back(allocBegin);
  68       PCHECK(0 == ::mprotect(allocBegin, pagesize(), PROT_NONE));
  69     }
  70   }
  71
  72   unsigned char* borrow(size_t size) {
  73     std::lock_guard<folly::SpinLock> lg(lock_);
  74
  75     assert(storage_);
  76
  77     auto as = allocSize(size);
  78     if (as != allocSize_ || freeList_.empty()) {
  79       return nullptr;
  80     }
  81
  82     auto p = freeList_.back();
  83     freeList_.pop_back();
  84
  85     /* We allocate minimum number of pages required, plus a guard page.
  86        Since we use this for stack storage, requested allocation is aligned
  87        at the top of the allocated pages, while the guard page is at the bottom.
  88
  89                -- increasing addresses -->
  90              Guard page     Normal pages
  91             |xxxxxxxxxx|..........|..........|
  92             <- allocSize_ ------------------->
  93          p -^                <- size -------->
  94                       limit -^
  95     */
  96     auto limit = p + allocSize_ - size;
  97     assert(limit >= p + pagesize());
  98     return limit;
  99   }
 100
 101   bool giveBack(unsigned char* limit, size_t size) {
 102     std::lock_guard<folly::SpinLock> lg(lock_);
 103
 104     assert(storage_);
 105
 106     auto as = allocSize(size);
 107     auto p = limit + size - as;
 108     if (p < storage_ || p >= storage_ + allocSize_ * kNumGuarded) {
 109       /* not mine */
 110       return false;
 111     }
 112
 113     assert(as == allocSize_);
 114     assert((p - storage_) % allocSize_ == 0);
 115     freeList_.push_back(p);
 116     return true;
 117   }
 118
 119   ~StackCache() {
 120     assert(storage_);
 121     PCHECK(0 == ::munmap(storage_, allocSize_ * kNumGuarded));
 122   }
 123
 124  private:
 125   folly::SpinLock lock_;
 126   unsigned char* storage_{nullptr};
 127   size_t allocSize_{0};
 128
 129   /**
 130    * LIFO free list
 131    */
 132   std::vector<unsigned char*> freeList_;
 133
 134   static size_t pagesize() {
 135     static const size_t pagesize = sysconf(_SC_PAGESIZE);
 136     return pagesize;
 137   }
 138
 139   /* Returns a multiple of pagesize() enough to store size + one guard page */
 140   static size_t allocSize(size_t size) {
 141     return pagesize() * ((size + pagesize() - 1)/pagesize() + 1);
 142   }
 143 };
 144
 145 class CacheManager {
 146  public:
 147   static CacheManager& instance() {
 148     static auto inst = new CacheManager();
 149     return *inst;
 150   }
 151
 152   std::unique_ptr<StackCacheEntry> getStackCache(size_t stackSize) {
 153     std::lock_guard<folly::SpinLock> lg(lock_);
 154     if (inUse_ < kMaxInUse) {
 155       ++inUse_;
 156       return folly::make_unique<StackCacheEntry>(stackSize);
 157     }
 158
 159     return nullptr;
 160   }
 161
 162  private:
 163   folly::SpinLock lock_;
 164   size_t inUse_{0};
 165
 166   friend class StackCacheEntry;
 167
 168   void giveBack(std::unique_ptr<StackCache> /* stackCache_ */) {
 169     assert(inUse_ > 0);
 170     --inUse_;
 171     /* Note: we can add a free list for each size bucket
 172        if stack re-use is important.
 173        In this case this needs to be a folly::Singleton
 174        to make sure the free list is cleaned up on fork.
 175
 176        TODO(t7351705): fix Singleton destruction order
 177     */
 178   }
 179 };
 180
 181 /*
 182  * RAII Wrapper around a StackCache that calls
 183  * CacheManager::giveBack() on destruction.
 184  */
 185 class StackCacheEntry {
 186  public:
 187   explicit StackCacheEntry(size_t stackSize)
 188       : stackCache_(folly::make_unique<StackCache>(stackSize)) {
 189   }
 190
 191   StackCache& cache() const noexcept {
 192     return *stackCache_;
 193   }
 194
 195   ~StackCacheEntry() {
 196     CacheManager::instance().giveBack(std::move(stackCache_));
 197   }
 198
 199  private:
 200   std::unique_ptr<StackCache> stackCache_;
 201 };
 202
 203 GuardPageAllocator::GuardPageAllocator(bool useGuardPages)
 204   : useGuardPages_(useGuardPages) {
 205 }
 206
 207 GuardPageAllocator::~GuardPageAllocator() = default;
 208
 209 unsigned char* GuardPageAllocator::allocate(size_t size) {
 210   if (useGuardPages_ && !stackCache_) {
 211     stackCache_ = CacheManager::instance().getStackCache(size);
 212   }
 213
 214   if (stackCache_) {
 215     auto p = stackCache_->cache().borrow(size);
 216     if (p != nullptr) {
 217       return p;
 218     }
 219   }
 220   return fallbackAllocator_.allocate(size);
 221 }
 222
 223 void GuardPageAllocator::deallocate(unsigned char* limit, size_t size) {
 224   if (!(stackCache_ && stackCache_->cache().giveBack(limit, size))) {
 225     fallbackAllocator_.deallocate(limit, size);
 226   }
 227 }
 228
 229 }}  // folly::fibers