folly/detail/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 <atomic>
  21 #include <cassert>
  22 #include <functional>
  23 #include <limits>
  24 #include <string>
  25 #include <type_traits>
  26 #include <vector>
  27 #include <pthread.h>
  28 #include <folly/Hash.h>
  29 #include <folly/Likely.h>
  30 #include <folly/Portability.h>
  31
  32 namespace folly {
  33 namespace detail {
  34
  35 // This file contains several classes that might be useful if you are
  36 // trying to dynamically optimize cache locality: CacheLocality reads
  37 // cache sharing information from sysfs to determine how CPUs should be
  38 // grouped to minimize contention, Getcpu provides fast access to the
  39 // current CPU via __vdso_getcpu, and AccessSpreader uses these two to
  40 // optimally spread accesses among a predetermined number of stripes.
  41 //
  42 // AccessSpreader<>::current(n) microbenchmarks at 22 nanos, which is
  43 // substantially less than the cost of a cache miss.  This means that we
  44 // can effectively use it to reduce cache line ping-pong on striped data
  45 // structures such as IndexedMemPool or statistics counters.
  46 //
  47 // Because CacheLocality looks at all of the cache levels, it can be
  48 // used for different levels of optimization.  AccessSpreader(2) does
  49 // per-chip spreading on a dual socket system.  AccessSpreader(numCpus)
  50 // does perfect per-cpu spreading.  AccessSpreader(numCpus / 2) does
  51 // perfect L1 spreading in a system with hyperthreading enabled.
  52
  53 struct CacheLocality {
  54
  55   /// 1 more than the maximum value that can be returned from sched_getcpu
  56   /// or getcpu.  This is the number of hardware thread contexts provided
  57   /// by the processors
  58   size_t numCpus;
  59
  60   /// Holds the number of caches present at each cache level (0 is
  61   /// the closest to the cpu).  This is the number of AccessSpreader
  62   /// stripes needed to avoid cross-cache communication at the specified
  63   /// layer.  numCachesByLevel.front() is the number of L1 caches and
  64   /// numCachesByLevel.back() is the number of last-level caches.
  65   std::vector<size_t> numCachesByLevel;
  66
  67   /// A map from cpu (from sched_getcpu or getcpu) to an index in the
  68   /// range 0..numCpus-1, where neighboring locality indices are more
  69   /// likely to share caches then indices far away.  All of the members
  70   /// of a particular cache level be contiguous in their locality index.
  71   /// For example, if numCpus is 32 and numCachesByLevel.back() is 2,
  72   /// then cpus with a locality index < 16 will share one last-level
  73   /// cache and cpus with a locality index >= 16 will share the other.
  74   std::vector<size_t> localityIndexByCpu;
  75
  76   /// Returns the best CacheLocality information available for the current
  77   /// system, cached for fast access.  This will be loaded from sysfs if
  78   /// possible, otherwise it will be correct in the number of CPUs but
  79   /// not in their sharing structure.
  80   ///
  81   /// If you are into yo dawgs, this is a shared cache of the local
  82   /// locality of the shared caches.
  83   ///
  84   /// The template parameter here is used to allow injection of a
  85   /// repeatable CacheLocality structure during testing.  Rather than
  86   /// inject the type of the CacheLocality provider into every data type
  87   /// that transitively uses it, all components select between the default
  88   /// sysfs implementation and a deterministic implementation by keying
  89   /// off the type of the underlying atomic.  See DeterministicScheduler.
  90   template <template <typename> class Atom = std::atomic>
  91   static const CacheLocality& system();
  92
  93   /// Reads CacheLocality information from a tree structured like
  94   /// the sysfs filesystem.  The provided function will be evaluated
  95   /// for each sysfs file that needs to be queried.  The function
  96   /// should return a string containing the first line of the file
  97   /// (not including the newline), or an empty string if the file does
  98   /// not exist.  The function will be called with paths of the form
  99   /// /sys/devices/system/cpu/cpu*/cache/index*/{type,shared_cpu_list} .
 100   /// Throws an exception if no caches can be parsed at all.
 101   static CacheLocality readFromSysfsTree(
 102       const std::function<std::string(std::string)>& mapping);
 103
 104   /// Reads CacheLocality information from the real sysfs filesystem.
 105   /// Throws an exception if no cache information can be loaded.
 106   static CacheLocality readFromSysfs();
 107
 108   /// Returns a usable (but probably not reflective of reality)
 109   /// CacheLocality structure with the specified number of cpus and a
 110   /// single cache level that associates one cpu per cache.
 111   static CacheLocality uniform(size_t numCpus);
 112
 113   enum {
 114     /// Memory locations on the same cache line are subject to false
 115     /// sharing, which is very bad for performance.  Microbenchmarks
 116     /// indicate that pairs of cache lines also see interference under
 117     /// heavy use of atomic operations (observed for atomic increment on
 118     /// Sandy Bridge).  See FOLLY_ALIGN_TO_AVOID_FALSE_SHARING
 119     kFalseSharingRange = 128
 120   };
 121
 122   static_assert(
 123       kFalseSharingRange == 128,
 124       "FOLLY_ALIGN_TO_AVOID_FALSE_SHARING should track kFalseSharingRange");
 125 };
 126
 127 // TODO replace __attribute__ with alignas and 128 with kFalseSharingRange
 128
 129 /// An attribute that will cause a variable or field to be aligned so that
 130 /// it doesn't have false sharing with anything at a smaller memory address.
 131 #define FOLLY_ALIGN_TO_AVOID_FALSE_SHARING FOLLY_ALIGNED(128)
 132
 133 /// Knows how to derive a function pointer to the VDSO implementation of
 134 /// getcpu(2), if available
 135 struct Getcpu {
 136   /// Function pointer to a function with the same signature as getcpu(2).
 137   typedef int (*Func)(unsigned* cpu, unsigned* node, void* unused);
 138
 139   /// Returns a pointer to the VDSO implementation of getcpu(2), if
 140   /// available, or nullptr otherwise.  This function may be quite
 141   /// expensive, be sure to cache the result.
 142   static Func resolveVdsoFunc();
 143 };
 144
 145 #ifdef FOLLY_TLS
 146 template <template <typename> class Atom>
 147 struct SequentialThreadId {
 148
 149   /// Returns the thread id assigned to the current thread
 150   static unsigned get() {
 151     auto rv = currentId;
 152     if (UNLIKELY(rv == 0)) {
 153       rv = currentId = ++prevId;
 154     }
 155     return rv;
 156   }
 157
 158  private:
 159   static Atom<unsigned> prevId;
 160
 161   static FOLLY_TLS unsigned currentId;
 162 };
 163
 164 template <template <typename> class Atom>
 165 Atom<unsigned> SequentialThreadId<Atom>::prevId(0);
 166
 167 template <template <typename> class Atom>
 168 FOLLY_TLS unsigned SequentialThreadId<Atom>::currentId(0);
 169
 170 // Suppress this instantiation in other translation units. It is
 171 // instantiated in CacheLocality.cpp
 172 extern template struct SequentialThreadId<std::atomic>;
 173 #endif
 174
 175 struct HashingThreadId {
 176   static unsigned get() {
 177     pthread_t pid = pthread_self();
 178     uint64_t id = 0;
 179     memcpy(&id, &pid, std::min(sizeof(pid), sizeof(id)));
 180     return hash::twang_32from64(id);
 181   }
 182 };
 183
 184 /// A class that lazily binds a unique (for each implementation of Atom)
 185 /// identifier to a thread.  This is a fallback mechanism for the access
 186 /// spreader if __vdso_getcpu can't be loaded
 187 template <typename ThreadId>
 188 struct FallbackGetcpu {
 189   /// Fills the thread id into the cpu and node out params (if they
 190   /// are non-null).  This method is intended to act like getcpu when a
 191   /// fast-enough form of getcpu isn't available or isn't desired
 192   static int getcpu(unsigned* cpu, unsigned* node, void* /* unused */) {
 193     auto id = ThreadId::get();
 194     if (cpu) {
 195       *cpu = id;
 196     }
 197     if (node) {
 198       *node = id;
 199     }
 200     return 0;
 201   }
 202 };
 203
 204 #ifdef FOLLY_TLS
 205 typedef FallbackGetcpu<SequentialThreadId<std::atomic>> FallbackGetcpuType;
 206 #else
 207 typedef FallbackGetcpu<HashingThreadId> FallbackGetcpuType;
 208 #endif
 209
 210 /// AccessSpreader arranges access to a striped data structure in such a
 211 /// way that concurrently executing threads are likely to be accessing
 212 /// different stripes.  It does NOT guarantee uncontended access.
 213 /// Your underlying algorithm must be thread-safe without spreading, this
 214 /// is merely an optimization.  AccessSpreader::current(n) is typically
 215 /// much faster than a cache miss (12 nanos on my dev box, tested fast
 216 /// in both 2.6 and 3.2 kernels).
 217 ///
 218 /// If available (and not using the deterministic testing implementation)
 219 /// AccessSpreader uses the getcpu system call via VDSO and the
 220 /// precise locality information retrieved from sysfs by CacheLocality.
 221 /// This provides optimal anti-sharing at a fraction of the cost of a
 222 /// cache miss.
 223 ///
 224 /// When there are not as many stripes as processors, we try to optimally
 225 /// place the cache sharing boundaries.  This means that if you have 2
 226 /// stripes and run on a dual-socket system, your 2 stripes will each get
 227 /// all of the cores from a single socket.  If you have 16 stripes on a
 228 /// 16 core system plus hyperthreading (32 cpus), each core will get its
 229 /// own stripe and there will be no cache sharing at all.
 230 ///
 231 /// AccessSpreader has a fallback mechanism for when __vdso_getcpu can't be
 232 /// loaded, or for use during deterministic testing.  Using sched_getcpu
 233 /// or the getcpu syscall would negate the performance advantages of
 234 /// access spreading, so we use a thread-local value and a shared atomic
 235 /// counter to spread access out.  On systems lacking both a fast getcpu()
 236 /// and TLS, we hash the thread id to spread accesses.
 237 ///
 238 /// AccessSpreader is templated on the template type that is used
 239 /// to implement atomics, as a way to instantiate the underlying
 240 /// heuristics differently for production use and deterministic unit
 241 /// testing.  See DeterministicScheduler for more.  If you aren't using
 242 /// DeterministicScheduler, you can just use the default template parameter
 243 /// all of the time.
 244 template <template <typename> class Atom = std::atomic>
 245 struct AccessSpreader {
 246
 247   /// Returns the stripe associated with the current CPU.  The returned
 248   /// value will be < numStripes.
 249   static size_t current(size_t numStripes) {
 250     // widthAndCpuToStripe[0] will actually work okay (all zeros), but
 251     // something's wrong with the caller
 252     assert(numStripes > 0);
 253
 254     unsigned cpu;
 255     getcpuFunc(&cpu, nullptr, nullptr);
 256     return widthAndCpuToStripe[std::min(size_t(kMaxCpus),
 257                                         numStripes)][cpu % kMaxCpus];
 258   }
 259
 260  private:
 261   /// If there are more cpus than this nothing will crash, but there
 262   /// might be unnecessary sharing
 263   enum { kMaxCpus = 128 };
 264
 265   typedef uint8_t CompactStripe;
 266
 267   static_assert((kMaxCpus & (kMaxCpus - 1)) == 0,
 268                 "kMaxCpus should be a power of two so modulo is fast");
 269   static_assert(kMaxCpus - 1 <= std::numeric_limits<CompactStripe>::max(),
 270                 "stripeByCpu element type isn't wide enough");
 271
 272   /// Points to the getcpu-like function we are using to obtain the
 273   /// current cpu.  It should not be assumed that the returned cpu value
 274   /// is in range.  We use a static for this so that we can prearrange a
 275   /// valid value in the pre-constructed state and avoid the need for a
 276   /// conditional on every subsequent invocation (not normally a big win,
 277   /// but 20% on some inner loops here).
 278   static Getcpu::Func getcpuFunc;
 279
 280   /// For each level of splitting up to kMaxCpus, maps the cpu (mod
 281   /// kMaxCpus) to the stripe.  Rather than performing any inequalities
 282   /// or modulo on the actual number of cpus, we just fill in the entire
 283   /// array.
 284   static CompactStripe widthAndCpuToStripe[kMaxCpus + 1][kMaxCpus];
 285
 286   static bool initialized;
 287
 288   /// Returns the best getcpu implementation for Atom
 289   static Getcpu::Func pickGetcpuFunc() {
 290     auto best = Getcpu::resolveVdsoFunc();
 291     return best ? best : &FallbackGetcpuType::getcpu;
 292   }
 293
 294   /// Always claims to be on CPU zero, node zero
 295   static int degenerateGetcpu(unsigned* cpu, unsigned* node, void*) {
 296     if (cpu != nullptr) {
 297       *cpu = 0;
 298     }
 299     if (node != nullptr) {
 300       *node = 0;
 301     }
 302     return 0;
 303   }
 304
 305   // The function to call for fast lookup of getcpu is a singleton, as
 306   // is the precomputed table of locality information.  AccessSpreader
 307   // is used in very tight loops, however (we're trying to race an L1
 308   // cache miss!), so the normal singleton mechanisms are noticeably
 309   // expensive.  Even a not-taken branch guarding access to getcpuFunc
 310   // slows AccessSpreader::current from 12 nanos to 14.  As a result, we
 311   // populate the static members with simple (but valid) values that can
 312   // be filled in by the linker, and then follow up with a normal static
 313   // initializer call that puts in the proper version.  This means that
 314   // when there are initialization order issues we will just observe a
 315   // zero stripe.  Once a sanitizer gets smart enough to detect this as
 316   // a race or undefined behavior, we can annotate it.
 317
 318   static bool initialize() {
 319     getcpuFunc = pickGetcpuFunc();
 320
 321     auto& cacheLocality = CacheLocality::system<Atom>();
 322     auto n = cacheLocality.numCpus;
 323     for (size_t width = 0; width <= kMaxCpus; ++width) {
 324       auto numStripes = std::max(size_t{1}, width);
 325       for (size_t cpu = 0; cpu < kMaxCpus && cpu < n; ++cpu) {
 326         auto index = cacheLocality.localityIndexByCpu[cpu];
 327         assert(index < n);
 328         // as index goes from 0..n, post-transform value goes from
 329         // 0..numStripes
 330         widthAndCpuToStripe[width][cpu] =
 331             CompactStripe((index * numStripes) / n);
 332         assert(widthAndCpuToStripe[width][cpu] < numStripes);
 333       }
 334       for (size_t cpu = n; cpu < kMaxCpus; ++cpu) {
 335         widthAndCpuToStripe[width][cpu] = widthAndCpuToStripe[width][cpu - n];
 336       }
 337     }
 338     return true;
 339   }
 340 };
 341
 342 template <template <typename> class Atom>
 343 Getcpu::Func AccessSpreader<Atom>::getcpuFunc =
 344     AccessSpreader<Atom>::degenerateGetcpu;
 345
 346 template <template <typename> class Atom>
 347 typename AccessSpreader<Atom>::CompactStripe
 348     AccessSpreader<Atom>::widthAndCpuToStripe[kMaxCpus + 1][kMaxCpus] = {};
 349
 350 template <template <typename> class Atom>
 351 bool AccessSpreader<Atom>::initialized = AccessSpreader<Atom>::initialize();
 352
 353 // Suppress this instantiation in other translation units. It is
 354 // instantiated in CacheLocality.cpp
 355 extern template struct AccessSpreader<std::atomic>;
 356
 357 } // namespace detail
 358 } // namespace folly