folly/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 <mutex>
  19
  20 #include <folly/Singleton.h>
  21 #include <folly/SpinLock.h>
  22 #include <folly/portability/SysMman.h>
  23 #include <folly/portability/Unistd.h>
  24
  25 #include <glog/logging.h>
  26
  27 namespace folly {
  28 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) : allocSize_(allocSize(stackSize)) {
  56     auto p = ::mmap(
  57         nullptr,
  58         allocSize_ * kNumGuarded,
  59         PROT_READ | PROT_WRITE,
  60         MAP_PRIVATE | MAP_ANONYMOUS,
  61         -1,
  62         0);
  63     PCHECK(p != (void*)(-1));
  64     storage_ = reinterpret_cast<unsigned char*>(p);
  65
  66     /* Protect the bottommost page of every stack allocation */
  67     for (size_t i = 0; i < kNumGuarded; ++i) {
  68       auto allocBegin = storage_ + allocSize_ * i;
  69       freeList_.emplace_back(allocBegin, /* protected= */ false);
  70     }
  71   }
  72
  73   unsigned char* borrow(size_t size) {
  74     std::lock_guard<folly::SpinLock> lg(lock_);
  75
  76     assert(storage_);
  77
  78     auto as = allocSize(size);
  79     if (as != allocSize_ || freeList_.empty()) {
  80       return nullptr;
  81     }
  82
  83     auto p = freeList_.back().first;
  84     if (!freeList_.back().second) {
  85       PCHECK(0 == ::mprotect(p, pagesize(), PROT_NONE));
  86     }
  87     freeList_.pop_back();
  88
  89     /* We allocate minimum number of pages required, plus a guard page.
  90        Since we use this for stack storage, requested allocation is aligned
  91        at the top of the allocated pages, while the guard page is at the bottom.
  92
  93                -- increasing addresses -->
  94              Guard page     Normal pages
  95             |xxxxxxxxxx|..........|..........|
  96             <- allocSize_ ------------------->
  97          p -^                <- size -------->
  98                       limit -^
  99     */
 100     auto limit = p + allocSize_ - size;
 101     assert(limit >= p + pagesize());
 102     return limit;
 103   }
 104
 105   bool giveBack(unsigned char* limit, size_t size) {
 106     std::lock_guard<folly::SpinLock> lg(lock_);
 107
 108     assert(storage_);
 109
 110     auto as = allocSize(size);
 111     auto p = limit + size - as;
 112     if (p < storage_ || p >= storage_ + allocSize_ * kNumGuarded) {
 113       /* not mine */
 114       return false;
 115     }
 116
 117     assert(as == allocSize_);
 118     assert((p - storage_) % allocSize_ == 0);
 119     freeList_.emplace_back(p, /* protected= */ true);
 120     return true;
 121   }
 122
 123   ~StackCache() {
 124     assert(storage_);
 125     PCHECK(0 == ::munmap(storage_, allocSize_ * kNumGuarded));
 126   }
 127
 128  private:
 129   folly::SpinLock lock_;
 130   unsigned char* storage_{nullptr};
 131   size_t allocSize_{0};
 132
 133   /**
 134    * LIFO free list. Each pair contains stack pointer and protected flag.
 135    */
 136   std::vector<std::pair<unsigned char*, bool>> freeList_;
 137
 138   static size_t pagesize() {
 139     static const size_t pagesize = sysconf(_SC_PAGESIZE);
 140     return pagesize;
 141   }
 142
 143   /* Returns a multiple of pagesize() enough to store size + one guard page */
 144   static size_t allocSize(size_t size) {
 145     return pagesize() * ((size + pagesize() - 1) / pagesize() + 1);
 146   }
 147 };
 148
 149 class CacheManager {
 150  public:
 151   static CacheManager& instance() {
 152     static auto inst = new CacheManager();
 153     return *inst;
 154   }
 155
 156   std::unique_ptr<StackCacheEntry> getStackCache(size_t stackSize) {
 157     std::lock_guard<folly::SpinLock> lg(lock_);
 158     if (inUse_ < kMaxInUse) {
 159       ++inUse_;
 160       return folly::make_unique<StackCacheEntry>(stackSize);
 161     }
 162
 163     return nullptr;
 164   }
 165
 166  private:
 167   folly::SpinLock lock_;
 168   size_t inUse_{0};
 169
 170   friend class StackCacheEntry;
 171
 172   void giveBack(std::unique_ptr<StackCache> /* stackCache_ */) {
 173     assert(inUse_ > 0);
 174     --inUse_;
 175     /* Note: we can add a free list for each size bucket
 176        if stack re-use is important.
 177        In this case this needs to be a folly::Singleton
 178        to make sure the free list is cleaned up on fork.
 179
 180        TODO(t7351705): fix Singleton destruction order
 181     */
 182   }
 183 };
 184
 185 /*
 186  * RAII Wrapper around a StackCache that calls
 187  * CacheManager::giveBack() on destruction.
 188  */
 189 class StackCacheEntry {
 190  public:
 191   explicit StackCacheEntry(size_t stackSize)
 192       : stackCache_(folly::make_unique<StackCache>(stackSize)) {}
 193
 194   StackCache& cache() const noexcept {
 195     return *stackCache_;
 196   }
 197
 198   ~StackCacheEntry() {
 199     CacheManager::instance().giveBack(std::move(stackCache_));
 200   }
 201
 202  private:
 203   std::unique_ptr<StackCache> stackCache_;
 204 };
 205
 206 GuardPageAllocator::GuardPageAllocator(bool useGuardPages)
 207     : useGuardPages_(useGuardPages) {}
 208
 209 GuardPageAllocator::~GuardPageAllocator() = default;
 210
 211 unsigned char* GuardPageAllocator::allocate(size_t size) {
 212   if (useGuardPages_ && !stackCache_) {
 213     stackCache_ = CacheManager::instance().getStackCache(size);
 214   }
 215
 216   if (stackCache_) {
 217     auto p = stackCache_->cache().borrow(size);
 218     if (p != nullptr) {
 219       return p;
 220     }
 221   }
 222   return fallbackAllocator_.allocate(size);
 223 }
 224
 225 void GuardPageAllocator::deallocate(unsigned char* limit, size_t size) {
 226   if (!(stackCache_ && stackCache_->cache().giveBack(limit, size))) {
 227     fallbackAllocator_.deallocate(limit, size);
 228   }
 229 }
 230 }
 231 } // folly::fibers