folly/experimental/fibers/GuardPageAllocator.cpp

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