folly/concurrency/CacheLocality.h

   1 /*
   2  * Copyright 2017 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
  17 #pragma once
  18
  19 #include <algorithm>
  20 #include <array>
  21 #include <atomic>
  22 #include <cassert>
  23 #include <functional>
  24 #include <limits>
  25 #include <mutex>
  26 #include <string>
  27 #include <type_traits>
  28 #include <unordered_map>
  29 #include <vector>
  30
  31 #include <folly/Hash.h>
  32 #include <folly/Indestructible.h>
  33 #include <folly/Likely.h>
  34 #include <folly/Memory.h>
  35 #include <folly/Portability.h>
  36 #include <folly/ThreadId.h>
  37 #include <folly/portability/BitsFunctexcept.h>
  38 #include <folly/portability/Memory.h>
  39
  40 namespace folly {
  41
  42 // This file contains several classes that might be useful if you are
  43 // trying to dynamically optimize cache locality: CacheLocality reads
  44 // cache sharing information from sysfs to determine how CPUs should be
  45 // grouped to minimize contention, Getcpu provides fast access to the
  46 // current CPU via __vdso_getcpu, and AccessSpreader uses these two to
  47 // optimally spread accesses among a predetermined number of stripes.
  48 //
  49 // AccessSpreader<>::current(n) microbenchmarks at 22 nanos, which is
  50 // substantially less than the cost of a cache miss.  This means that we
  51 // can effectively use it to reduce cache line ping-pong on striped data
  52 // structures such as IndexedMemPool or statistics counters.
  53 //
  54 // Because CacheLocality looks at all of the cache levels, it can be
  55 // used for different levels of optimization.  AccessSpreader(2) does
  56 // per-chip spreading on a dual socket system.  AccessSpreader(numCpus)
  57 // does perfect per-cpu spreading.  AccessSpreader(numCpus / 2) does
  58 // perfect L1 spreading in a system with hyperthreading enabled.
  59
  60 struct CacheLocality {
  61   /// 1 more than the maximum value that can be returned from sched_getcpu
  62   /// or getcpu.  This is the number of hardware thread contexts provided
  63   /// by the processors
  64   size_t numCpus;
  65
  66   /// Holds the number of caches present at each cache level (0 is
  67   /// the closest to the cpu).  This is the number of AccessSpreader
  68   /// stripes needed to avoid cross-cache communication at the specified
  69   /// layer.  numCachesByLevel.front() is the number of L1 caches and
  70   /// numCachesByLevel.back() is the number of last-level caches.
  71   std::vector<size_t> numCachesByLevel;
  72
  73   /// A map from cpu (from sched_getcpu or getcpu) to an index in the
  74   /// range 0..numCpus-1, where neighboring locality indices are more
  75   /// likely to share caches then indices far away.  All of the members
  76   /// of a particular cache level be contiguous in their locality index.
  77   /// For example, if numCpus is 32 and numCachesByLevel.back() is 2,
  78   /// then cpus with a locality index < 16 will share one last-level
  79   /// cache and cpus with a locality index >= 16 will share the other.
  80   std::vector<size_t> localityIndexByCpu;
  81
  82   /// Returns the best CacheLocality information available for the current
  83   /// system, cached for fast access.  This will be loaded from sysfs if
  84   /// possible, otherwise it will be correct in the number of CPUs but
  85   /// not in their sharing structure.
  86   ///
  87   /// If you are into yo dawgs, this is a shared cache of the local
  88   /// locality of the shared caches.
  89   ///
  90   /// The template parameter here is used to allow injection of a
  91   /// repeatable CacheLocality structure during testing.  Rather than
  92   /// inject the type of the CacheLocality provider into every data type
  93   /// that transitively uses it, all components select between the default
  94   /// sysfs implementation and a deterministic implementation by keying
  95   /// off the type of the underlying atomic.  See DeterministicScheduler.
  96   template <template <typename> class Atom = std::atomic>
  97   static const CacheLocality& system();
  98
  99   /// Reads CacheLocality information from a tree structured like
 100   /// the sysfs filesystem.  The provided function will be evaluated
 101   /// for each sysfs file that needs to be queried.  The function
 102   /// should return a string containing the first line of the file
 103   /// (not including the newline), or an empty string if the file does
 104   /// not exist.  The function will be called with paths of the form
 105   /// /sys/devices/system/cpu/cpu*/cache/index*/{type,shared_cpu_list} .
 106   /// Throws an exception if no caches can be parsed at all.
 107   static CacheLocality readFromSysfsTree(
 108       const std::function<std::string(std::string)>& mapping);
 109
 110   /// Reads CacheLocality information from the real sysfs filesystem.
 111   /// Throws an exception if no cache information can be loaded.
 112   static CacheLocality readFromSysfs();
 113
 114   /// Returns a usable (but probably not reflective of reality)
 115   /// CacheLocality structure with the specified number of cpus and a
 116   /// single cache level that associates one cpu per cache.
 117   static CacheLocality uniform(size_t numCpus);
 118
 119   enum {
 120     /// Memory locations on the same cache line are subject to false
 121     /// sharing, which is very bad for performance.  Microbenchmarks
 122     /// indicate that pairs of cache lines also see interference under
 123     /// heavy use of atomic operations (observed for atomic increment on
 124     /// Sandy Bridge).  See FOLLY_ALIGN_TO_AVOID_FALSE_SHARING
 125     kFalseSharingRange = 128
 126   };
 127
 128   static_assert(
 129       kFalseSharingRange == 128,
 130       "FOLLY_ALIGN_TO_AVOID_FALSE_SHARING should track kFalseSharingRange");
 131 };
 132
 133 // TODO replace __attribute__ with alignas and 128 with kFalseSharingRange
 134
 135 /// An attribute that will cause a variable or field to be aligned so that
 136 /// it doesn't have false sharing with anything at a smaller memory address.
 137 #define FOLLY_ALIGN_TO_AVOID_FALSE_SHARING FOLLY_ALIGNED(128)
 138
 139 /// Knows how to derive a function pointer to the VDSO implementation of
 140 /// getcpu(2), if available
 141 struct Getcpu {
 142   /// Function pointer to a function with the same signature as getcpu(2).
 143   typedef int (*Func)(unsigned* cpu, unsigned* node, void* unused);
 144
 145   /// Returns a pointer to the VDSO implementation of getcpu(2), if
 146   /// available, or nullptr otherwise.  This function may be quite
 147   /// expensive, be sure to cache the result.
 148   static Func resolveVdsoFunc();
 149 };
 150
 151 #ifdef FOLLY_TLS
 152 template <template <typename> class Atom>
 153 struct SequentialThreadId {
 154   /// Returns the thread id assigned to the current thread
 155   static unsigned get() {
 156     auto rv = currentId;
 157     if (UNLIKELY(rv == 0)) {
 158       rv = currentId = ++prevId;
 159     }
 160     return rv;
 161   }
 162
 163  private:
 164   static Atom<unsigned> prevId;
 165
 166   static FOLLY_TLS unsigned currentId;
 167 };
 168
 169 template <template <typename> class Atom>
 170 Atom<unsigned> SequentialThreadId<Atom>::prevId(0);
 171
 172 template <template <typename> class Atom>
 173 FOLLY_TLS unsigned SequentialThreadId<Atom>::currentId(0);
 174
 175 // Suppress this instantiation in other translation units. It is
 176 // instantiated in CacheLocality.cpp
 177 extern template struct SequentialThreadId<std::atomic>;
 178 #endif
 179
 180 struct HashingThreadId {
 181   static unsigned get() {
 182     return hash::twang_32from64(getCurrentThreadID());
 183   }
 184 };
 185
 186 /// A class that lazily binds a unique (for each implementation of Atom)
 187 /// identifier to a thread.  This is a fallback mechanism for the access
 188 /// spreader if __vdso_getcpu can't be loaded
 189 template <typename ThreadId>
 190 struct FallbackGetcpu {
 191   /// Fills the thread id into the cpu and node out params (if they
 192   /// are non-null).  This method is intended to act like getcpu when a
 193   /// fast-enough form of getcpu isn't available or isn't desired
 194   static int getcpu(unsigned* cpu, unsigned* node, void* /* unused */) {
 195     auto id = ThreadId::get();
 196     if (cpu) {
 197       *cpu = id;
 198     }
 199     if (node) {
 200       *node = id;
 201     }
 202     return 0;
 203   }
 204 };
 205
 206 #ifdef FOLLY_TLS
 207 typedef FallbackGetcpu<SequentialThreadId<std::atomic>> FallbackGetcpuType;
 208 #else
 209 typedef FallbackGetcpu<HashingThreadId> FallbackGetcpuType;
 210 #endif
 211
 212 /// AccessSpreader arranges access to a striped data structure in such a
 213 /// way that concurrently executing threads are likely to be accessing
 214 /// different stripes.  It does NOT guarantee uncontended access.
 215 /// Your underlying algorithm must be thread-safe without spreading, this
 216 /// is merely an optimization.  AccessSpreader::current(n) is typically
 217 /// much faster than a cache miss (12 nanos on my dev box, tested fast
 218 /// in both 2.6 and 3.2 kernels).
 219 ///
 220 /// If available (and not using the deterministic testing implementation)
 221 /// AccessSpreader uses the getcpu system call via VDSO and the
 222 /// precise locality information retrieved from sysfs by CacheLocality.
 223 /// This provides optimal anti-sharing at a fraction of the cost of a
 224 /// cache miss.
 225 ///
 226 /// When there are not as many stripes as processors, we try to optimally
 227 /// place the cache sharing boundaries.  This means that if you have 2
 228 /// stripes and run on a dual-socket system, your 2 stripes will each get
 229 /// all of the cores from a single socket.  If you have 16 stripes on a
 230 /// 16 core system plus hyperthreading (32 cpus), each core will get its
 231 /// own stripe and there will be no cache sharing at all.
 232 ///
 233 /// AccessSpreader has a fallback mechanism for when __vdso_getcpu can't be
 234 /// loaded, or for use during deterministic testing.  Using sched_getcpu
 235 /// or the getcpu syscall would negate the performance advantages of
 236 /// access spreading, so we use a thread-local value and a shared atomic
 237 /// counter to spread access out.  On systems lacking both a fast getcpu()
 238 /// and TLS, we hash the thread id to spread accesses.
 239 ///
 240 /// AccessSpreader is templated on the template type that is used
 241 /// to implement atomics, as a way to instantiate the underlying
 242 /// heuristics differently for production use and deterministic unit
 243 /// testing.  See DeterministicScheduler for more.  If you aren't using
 244 /// DeterministicScheduler, you can just use the default template parameter
 245 /// all of the time.
 246 template <template <typename> class Atom = std::atomic>
 247 struct AccessSpreader {
 248   /// Returns the stripe associated with the current CPU.  The returned
 249   /// value will be < numStripes.
 250   static size_t current(size_t numStripes) {
 251     // widthAndCpuToStripe[0] will actually work okay (all zeros), but
 252     // something's wrong with the caller
 253     assert(numStripes > 0);
 254
 255     unsigned cpu;
 256     getcpuFunc(&cpu, nullptr, nullptr);
 257     return widthAndCpuToStripe[std::min(size_t(kMaxCpus), numStripes)]
 258                               [cpu % kMaxCpus];
 259   }
 260
 261  private:
 262   /// If there are more cpus than this nothing will crash, but there
 263   /// might be unnecessary sharing
 264   enum { kMaxCpus = 128 };
 265
 266   typedef uint8_t CompactStripe;
 267
 268   static_assert(
 269       (kMaxCpus & (kMaxCpus - 1)) == 0,
 270       "kMaxCpus should be a power of two so modulo is fast");
 271   static_assert(
 272       kMaxCpus - 1 <= std::numeric_limits<CompactStripe>::max(),
 273       "stripeByCpu element type isn't wide enough");
 274
 275   /// Points to the getcpu-like function we are using to obtain the
 276   /// current cpu.  It should not be assumed that the returned cpu value
 277   /// is in range.  We use a static for this so that we can prearrange a
 278   /// valid value in the pre-constructed state and avoid the need for a
 279   /// conditional on every subsequent invocation (not normally a big win,
 280   /// but 20% on some inner loops here).
 281   static Getcpu::Func getcpuFunc;
 282
 283   /// For each level of splitting up to kMaxCpus, maps the cpu (mod
 284   /// kMaxCpus) to the stripe.  Rather than performing any inequalities
 285   /// or modulo on the actual number of cpus, we just fill in the entire
 286   /// array.
 287   static CompactStripe widthAndCpuToStripe[kMaxCpus + 1][kMaxCpus];
 288
 289   static bool initialized;
 290
 291   /// Returns the best getcpu implementation for Atom
 292   static Getcpu::Func pickGetcpuFunc() {
 293     auto best = Getcpu::resolveVdsoFunc();
 294     return best ? best : &FallbackGetcpuType::getcpu;
 295   }
 296
 297   /// Always claims to be on CPU zero, node zero
 298   static int degenerateGetcpu(unsigned* cpu, unsigned* node, void*) {
 299     if (cpu != nullptr) {
 300       *cpu = 0;
 301     }
 302     if (node != nullptr) {
 303       *node = 0;
 304     }
 305     return 0;
 306   }
 307
 308   // The function to call for fast lookup of getcpu is a singleton, as
 309   // is the precomputed table of locality information.  AccessSpreader
 310   // is used in very tight loops, however (we're trying to race an L1
 311   // cache miss!), so the normal singleton mechanisms are noticeably
 312   // expensive.  Even a not-taken branch guarding access to getcpuFunc
 313   // slows AccessSpreader::current from 12 nanos to 14.  As a result, we
 314   // populate the static members with simple (but valid) values that can
 315   // be filled in by the linker, and then follow up with a normal static
 316   // initializer call that puts in the proper version.  This means that
 317   // when there are initialization order issues we will just observe a
 318   // zero stripe.  Once a sanitizer gets smart enough to detect this as
 319   // a race or undefined behavior, we can annotate it.
 320
 321   static bool initialize() {
 322     getcpuFunc = pickGetcpuFunc();
 323
 324     auto& cacheLocality = CacheLocality::system<Atom>();
 325     auto n = cacheLocality.numCpus;
 326     for (size_t width = 0; width <= kMaxCpus; ++width) {
 327       auto numStripes = std::max(size_t{1}, width);
 328       for (size_t cpu = 0; cpu < kMaxCpus && cpu < n; ++cpu) {
 329         auto index = cacheLocality.localityIndexByCpu[cpu];
 330         assert(index < n);
 331         // as index goes from 0..n, post-transform value goes from
 332         // 0..numStripes
 333         widthAndCpuToStripe[width][cpu] =
 334             CompactStripe((index * numStripes) / n);
 335         assert(widthAndCpuToStripe[width][cpu] < numStripes);
 336       }
 337       for (size_t cpu = n; cpu < kMaxCpus; ++cpu) {
 338         widthAndCpuToStripe[width][cpu] = widthAndCpuToStripe[width][cpu - n];
 339       }
 340     }
 341     return true;
 342   }
 343 };
 344
 345 template <template <typename> class Atom>
 346 Getcpu::Func AccessSpreader<Atom>::getcpuFunc =
 347     AccessSpreader<Atom>::degenerateGetcpu;
 348
 349 template <template <typename> class Atom>
 350 typename AccessSpreader<Atom>::CompactStripe
 351     AccessSpreader<Atom>::widthAndCpuToStripe[kMaxCpus + 1][kMaxCpus] = {};
 352
 353 template <template <typename> class Atom>
 354 bool AccessSpreader<Atom>::initialized = AccessSpreader<Atom>::initialize();
 355
 356 // Suppress this instantiation in other translation units. It is
 357 // instantiated in CacheLocality.cpp
 358 extern template struct AccessSpreader<std::atomic>;
 359
 360 /**
 361  * A simple freelist allocator.  Allocates things of size sz, from
 362  * slabs of size allocSize.  Takes a lock on each
 363  * allocation/deallocation.
 364  */
 365 class SimpleAllocator {
 366   std::mutex m_;
 367   uint8_t* mem_{nullptr};
 368   uint8_t* end_{nullptr};
 369   void* freelist_{nullptr};
 370   size_t allocSize_;
 371   size_t sz_;
 372   std::vector<void*> blocks_;
 373
 374  public:
 375   SimpleAllocator(size_t allocSize, size_t sz);
 376   ~SimpleAllocator();
 377   void* allocateHard();
 378
 379   // Inline fast-paths.
 380   void* allocate() {
 381     std::lock_guard<std::mutex> g(m_);
 382     // Freelist allocation.
 383     if (freelist_) {
 384       auto mem = freelist_;
 385       freelist_ = *static_cast<void**>(freelist_);
 386       return mem;
 387     }
 388
 389     // Bump-ptr allocation.
 390     if (intptr_t(mem_) % 128 == 0) {
 391       // Avoid allocating pointers that may look like malloc
 392       // pointers.
 393       mem_ += std::min(sz_, folly::max_align_v);
 394     }
 395     if (mem_ && (mem_ + sz_ <= end_)) {
 396       auto mem = mem_;
 397       mem_ += sz_;
 398
 399       assert(intptr_t(mem) % 128 != 0);
 400       return mem;
 401     }
 402
 403     return allocateHard();
 404   }
 405   void deallocate(void* mem) {
 406     std::lock_guard<std::mutex> g(m_);
 407     *static_cast<void**>(mem) = freelist_;
 408     freelist_ = mem;
 409   }
 410 };
 411
 412 /**
 413  * An allocator that can be used with CacheLocality to allocate
 414  * core-local memory.
 415  *
 416  * There is actually nothing special about the memory itself (it is
 417  * not bound to numa nodes or anything), but the allocator guarantees
 418  * that memory allocatd from the same stripe will only come from cache
 419  * lines also allocated to the same stripe.  This means multiple
 420  * things using CacheLocality can allocate memory in smaller-than
 421  * cacheline increments, and be assured that it won't cause more false
 422  * sharing than it otherwise would.
 423  *
 424  * Note that allocation and deallocation takes a per-sizeclass lock.
 425  */
 426 template <size_t Stripes>
 427 class CoreAllocator {
 428  public:
 429   class Allocator {
 430     static constexpr size_t AllocSize{4096};
 431
 432     uint8_t sizeClass(size_t size) {
 433       if (size <= 8) {
 434         return 0;
 435       } else if (size <= 16) {
 436         return 1;
 437       } else if (size <= 32) {
 438         return 2;
 439       } else if (size <= 64) {
 440         return 3;
 441       } else { // punt to malloc.
 442         return 4;
 443       }
 444     }
 445
 446     std::array<SimpleAllocator, 4> allocators_{
 447         {{AllocSize, 8}, {AllocSize, 16}, {AllocSize, 32}, {AllocSize, 64}}};
 448
 449    public:
 450     void* allocate(size_t size) {
 451       auto cl = sizeClass(size);
 452       if (cl == 4) {
 453         static_assert(
 454             CacheLocality::kFalseSharingRange == 128,
 455             "kFalseSharingRange changed");
 456         // Align to a cacheline
 457         size = size + (CacheLocality::kFalseSharingRange - 1);
 458         size &= ~size_t(CacheLocality::kFalseSharingRange - 1);
 459         void* mem =
 460             detail::aligned_malloc(size, CacheLocality::kFalseSharingRange);
 461         if (!mem) {
 462           std::__throw_bad_alloc();
 463         }
 464         return mem;
 465       }
 466       return allocators_[cl].allocate();
 467     }
 468     void deallocate(void* mem) {
 469       if (!mem) {
 470         return;
 471       }
 472
 473       // See if it came from this allocator or malloc.
 474       if (intptr_t(mem) % 128 != 0) {
 475         auto addr =
 476             reinterpret_cast<void*>(intptr_t(mem) & ~intptr_t(AllocSize - 1));
 477         auto allocator = *static_cast<SimpleAllocator**>(addr);
 478         allocator->deallocate(mem);
 479       } else {
 480         detail::aligned_free(mem);
 481       }
 482     }
 483   };
 484
 485   Allocator* get(size_t stripe) {
 486     assert(stripe < Stripes);
 487     return &allocators_[stripe];
 488   }
 489
 490  private:
 491   Allocator allocators_[Stripes];
 492 };
 493
 494 template <size_t Stripes>
 495 typename CoreAllocator<Stripes>::Allocator* getCoreAllocator(size_t stripe) {
 496   // We cannot make sure that the allocator will be destroyed after
 497   // all the objects allocated with it, so we leak it.
 498   static Indestructible<CoreAllocator<Stripes>> allocator;
 499   return allocator->get(stripe);
 500 }
 501
 502 template <typename T, size_t Stripes>
 503 StlAllocator<typename CoreAllocator<Stripes>::Allocator, T> getCoreAllocatorStl(
 504     size_t stripe) {
 505   auto alloc = getCoreAllocator<Stripes>(stripe);
 506   return StlAllocator<typename CoreAllocator<Stripes>::Allocator, T>(alloc);
 507 }
 508
 509 } // namespace folly