folly/detail/CacheLocality.h

   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
  17 #ifndef FOLLY_DETAIL_CACHELOCALITY_H_
  18 #define FOLLY_DETAIL_CACHELOCALITY_H_
  19
  20 #include <sched.h>
  21 #include <algorithm>
  22 #include <atomic>
  23 #include <cassert>
  24 #include <functional>
  25 #include <limits>
  26 #include <string>
  27 #include <type_traits>
  28 #include <vector>
  29 #include <folly/Hash.h>
  30 #include <folly/Likely.h>
  31 #include <folly/Portability.h>
  32
  33 namespace folly {
  34 namespace detail {
  35
  36 // This file contains several classes that might be useful if you are
  37 // trying to dynamically optimize cache locality: CacheLocality reads
  38 // cache sharing information from sysfs to determine how CPUs should be
  39 // grouped to minimize contention, Getcpu provides fast access to the
  40 // current CPU via __vdso_getcpu, and AccessSpreader uses these two to
  41 // optimally spread accesses among a predetermined number of stripes.
  42 //
  43 // AccessSpreader<>::current(n) microbenchmarks at 22 nanos, which is
  44 // substantially less than the cost of a cache miss.  This means that we
  45 // can effectively use it to reduce cache line ping-pong on striped data
  46 // structures such as IndexedMemPool or statistics counters.
  47 //
  48 // Because CacheLocality looks at all of the cache levels, it can be
  49 // used for different levels of optimization.  AccessSpreader(2) does
  50 // per-chip spreading on a dual socket system.  AccessSpreader(numCpus)
  51 // does perfect per-cpu spreading.  AccessSpreader(numCpus / 2) does
  52 // perfect L1 spreading in a system with hyperthreading enabled.
  53
  54 struct CacheLocality {
  55
  56   /// 1 more than the maximum value that can be returned from sched_getcpu
  57   /// or getcpu.  This is the number of hardware thread contexts provided
  58   /// by the processors
  59   size_t numCpus;
  60
  61   /// Holds the number of caches present at each cache level (0 is
  62   /// the closest to the cpu).  This is the number of AccessSpreader
  63   /// stripes needed to avoid cross-cache communication at the specified
  64   /// layer.  numCachesByLevel.front() is the number of L1 caches and
  65   /// numCachesByLevel.back() is the number of last-level caches.
  66   std::vector<size_t> numCachesByLevel;
  67
  68   /// A map from cpu (from sched_getcpu or getcpu) to an index in the
  69   /// range 0..numCpus-1, where neighboring locality indices are more
  70   /// likely to share caches then indices far away.  All of the members
  71   /// of a particular cache level be contiguous in their locality index.
  72   /// For example, if numCpus is 32 and numCachesByLevel.back() is 2,
  73   /// then cpus with a locality index < 16 will share one last-level
  74   /// cache and cpus with a locality index >= 16 will share the other.
  75   std::vector<size_t> localityIndexByCpu;
  76
  77   /// Returns the best CacheLocality information available for the current
  78   /// system, cached for fast access.  This will be loaded from sysfs if
  79   /// possible, otherwise it will be correct in the number of CPUs but
  80   /// not in their sharing structure.
  81   ///
  82   /// If you are into yo dawgs, this is a shared cache of the local
  83   /// locality of the shared caches.
  84   ///
  85   /// The template parameter here is used to allow injection of a
  86   /// repeatable CacheLocality structure during testing.  Rather than
  87   /// inject the type of the CacheLocality provider into every data type
  88   /// that transitively uses it, all components select between the default
  89   /// sysfs implementation and a deterministic implementation by keying
  90   /// off the type of the underlying atomic.  See DeterministicScheduler.
  91   template <template <typename> class Atom = std::atomic>
  92   static const CacheLocality& system();
  93
  94   /// Reads CacheLocality information from a tree structured like
  95   /// the sysfs filesystem.  The provided function will be evaluated
  96   /// for each sysfs file that needs to be queried.  The function
  97   /// should return a string containing the first line of the file
  98   /// (not including the newline), or an empty string if the file does
  99   /// not exist.  The function will be called with paths of the form
 100   /// /sys/devices/system/cpu/cpu*/cache/index*/{type,shared_cpu_list} .
 101   /// Throws an exception if no caches can be parsed at all.
 102   static CacheLocality readFromSysfsTree(
 103       const std::function<std::string(std::string)>& mapping);
 104
 105   /// Reads CacheLocality information from the real sysfs filesystem.
 106   /// Throws an exception if no cache information can be loaded.
 107   static CacheLocality readFromSysfs();
 108
 109   /// Returns a usable (but probably not reflective of reality)
 110   /// CacheLocality structure with the specified number of cpus and a
 111   /// single cache level that associates one cpu per cache.
 112   static CacheLocality uniform(size_t numCpus);
 113
 114   enum {
 115     /// Memory locations on the same cache line are subject to false
 116     /// sharing, which is very bad for performance.  Microbenchmarks
 117     /// indicate that pairs of cache lines also see interference under
 118     /// heavy use of atomic operations (observed for atomic increment on
 119     /// Sandy Bridge).  See FOLLY_ALIGN_TO_AVOID_FALSE_SHARING
 120     kFalseSharingRange = 128
 121   };
 122
 123   static_assert(
 124       kFalseSharingRange == 128,
 125       "FOLLY_ALIGN_TO_AVOID_FALSE_SHARING should track kFalseSharingRange");
 126 };
 127
 128 // TODO replace __attribute__ with alignas and 128 with kFalseSharingRange
 129
 130 /// An attribute that will cause a variable or field to be aligned so that
 131 /// it doesn't have false sharing with anything at a smaller memory address.
 132 #define FOLLY_ALIGN_TO_AVOID_FALSE_SHARING FOLLY_ALIGNED(128)
 133
 134 /// Holds a function pointer to the VDSO implementation of getcpu(2),
 135 /// if available
 136 struct Getcpu {
 137   /// Function pointer to a function with the same signature as getcpu(2).
 138   typedef int (*Func)(unsigned* cpu, unsigned* node, void* unused);
 139
 140   /// Returns a pointer to the VDSO implementation of getcpu(2), if
 141   /// available, or nullptr otherwise
 142   static Func vdsoFunc();
 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 size_t 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<size_t> prevId;
 160
 161   static FOLLY_TLS size_t currentId;
 162 };
 163 #endif
 164
 165 struct HashingThreadId {
 166   static size_t get() {
 167     pthread_t pid = pthread_self();
 168     uint64_t id = 0;
 169     memcpy(&id, &pid, std::min(sizeof(pid), sizeof(id)));
 170     return hash::twang_32from64(id);
 171   }
 172 };
 173
 174 /// A class that lazily binds a unique (for each implementation of Atom)
 175 /// identifier to a thread.  This is a fallback mechanism for the access
 176 /// spreader if __vdso_getcpu can't be loaded
 177 template <typename ThreadId>
 178 struct FallbackGetcpu {
 179   /// Fills the thread id into the cpu and node out params (if they
 180   /// are non-null).  This method is intended to act like getcpu when a
 181   /// fast-enough form of getcpu isn't available or isn't desired
 182   static int getcpu(unsigned* cpu, unsigned* node, void* /* unused */) {
 183     auto id = ThreadId::get();
 184     if (cpu) {
 185       *cpu = id;
 186     }
 187     if (node) {
 188       *node = id;
 189     }
 190     return 0;
 191   }
 192 };
 193
 194 #ifdef FOLLY_TLS
 195 typedef FallbackGetcpu<SequentialThreadId<std::atomic>> FallbackGetcpuType;
 196 #else
 197 typedef FallbackGetcpu<HashingThreadId> FallbackGetcpuType;
 198 #endif
 199
 200 template <template <typename> class Atom, size_t kMaxCpus>
 201 struct AccessSpreaderArray;
 202
 203 /// AccessSpreader arranges access to a striped data structure in such a
 204 /// way that concurrently executing threads are likely to be accessing
 205 /// different stripes.  It does NOT guarantee uncontended access.
 206 /// Your underlying algorithm must be thread-safe without spreading, this
 207 /// is merely an optimization.  AccessSpreader::current(n) is typically
 208 /// much faster than a cache miss (22 nanos on my dev box, tested fast
 209 /// in both 2.6 and 3.2 kernels).
 210 ///
 211 /// You are free to create your own AccessSpreader-s or to cache the
 212 /// results of AccessSpreader<>::shared(n), but you will probably want
 213 /// to use one of the system-wide shared ones.  Calling .current() on
 214 /// a particular AccessSpreader instance only saves about 1 nanosecond
 215 /// over calling AccessSpreader<>::shared(n).
 216 ///
 217 /// If available (and not using the deterministic testing implementation)
 218 /// AccessSpreader uses the getcpu system call via VDSO and the
 219 /// precise locality information retrieved from sysfs by CacheLocality.
 220 /// This provides optimal anti-sharing at a fraction of the cost of a
 221 /// cache miss.
 222 ///
 223 /// When there are not as many stripes as processors, we try to optimally
 224 /// place the cache sharing boundaries.  This means that if you have 2
 225 /// stripes and run on a dual-socket system, your 2 stripes will each get
 226 /// all of the cores from a single socket.  If you have 16 stripes on a
 227 /// 16 core system plus hyperthreading (32 cpus), each core will get its
 228 /// own stripe and there will be no cache sharing at all.
 229 ///
 230 /// AccessSpreader has a fallback mechanism for when __vdso_getcpu can't be
 231 /// loaded, or for use during deterministic testing.  Using sched_getcpu or
 232 /// the getcpu syscall would negate the performance advantages of access
 233 /// spreading, so we use a thread-local value and a shared atomic counter
 234 /// to spread access out.
 235 ///
 236 /// AccessSpreader is templated on the template type that is used
 237 /// to implement atomics, as a way to instantiate the underlying
 238 /// heuristics differently for production use and deterministic unit
 239 /// testing.  See DeterministicScheduler for more.  If you aren't using
 240 /// DeterministicScheduler, you can just use the default template parameter
 241 /// all of the time.
 242 template <template <typename> class Atom = std::atomic>
 243 struct AccessSpreader {
 244
 245   /// Returns a never-destructed shared AccessSpreader instance.
 246   /// numStripes should be > 0.
 247   static const AccessSpreader& shared(size_t numStripes) {
 248     // sharedInstances[0] actually has numStripes == 1
 249     assert(numStripes > 0);
 250
 251     // the last shared element handles all large sizes
 252     return AccessSpreaderArray<Atom, kMaxCpus>::sharedInstance[std::min(
 253         size_t(kMaxCpus), numStripes)];
 254   }
 255
 256   /// Returns the stripe associated with the current CPU, assuming
 257   /// that there are numStripes (non-zero) stripes.  Equivalent to
 258   /// AccessSpreader::shared(numStripes)->current.
 259   static size_t current(size_t numStripes) {
 260     return shared(numStripes).current();
 261   }
 262
 263   /// stripeByCore uses 1 stripe per L1 cache, according to
 264   /// CacheLocality::system<>().  Use stripeByCore.numStripes() to see
 265   /// its width, or stripeByCore.current() to get the current stripe
 266   static const AccessSpreader stripeByCore;
 267
 268   /// stripeByChip uses 1 stripe per last-level cache, which is the fewest
 269   /// number of stripes for which off-chip communication can be avoided
 270   /// (assuming all caches are on-chip).  Use stripeByChip.numStripes()
 271   /// to see its width, or stripeByChip.current() to get the current stripe
 272   static const AccessSpreader stripeByChip;
 273
 274   /// Constructs an AccessSpreader that will return values from
 275   /// 0 to numStripes-1 (inclusive), precomputing the mapping
 276   /// from CPU to stripe.  There is no use in having more than
 277   /// CacheLocality::system<Atom>().localityIndexByCpu.size() stripes or
 278   /// kMaxCpus stripes
 279   explicit AccessSpreader(
 280       size_t spreaderNumStripes,
 281       const CacheLocality& cacheLocality = CacheLocality::system<Atom>(),
 282       Getcpu::Func getcpuFunc = nullptr)
 283       : getcpuFunc_(getcpuFunc ? getcpuFunc
 284                                : pickGetcpuFunc(spreaderNumStripes)),
 285         numStripes_(spreaderNumStripes) {
 286     auto n = cacheLocality.numCpus;
 287     for (size_t cpu = 0; cpu < kMaxCpus && cpu < n; ++cpu) {
 288       auto index = cacheLocality.localityIndexByCpu[cpu];
 289       assert(index < n);
 290       // as index goes from 0..n, post-transform value goes from
 291       // 0..numStripes
 292       stripeByCpu[cpu] = (index * numStripes_) / n;
 293       assert(stripeByCpu[cpu] < numStripes_);
 294     }
 295     for (size_t cpu = n; cpu < kMaxCpus; ++cpu) {
 296       stripeByCpu[cpu] = stripeByCpu[cpu - n];
 297     }
 298   }
 299
 300   /// Returns 1 more than the maximum value that can be returned from
 301   /// current()
 302   size_t numStripes() const { return numStripes_; }
 303
 304   /// Returns the stripe associated with the current CPU
 305   size_t current() const {
 306     unsigned cpu;
 307     getcpuFunc_(&cpu, nullptr, nullptr);
 308     return stripeByCpu[cpu % kMaxCpus];
 309   }
 310
 311  private:
 312   /// If there are more cpus than this nothing will crash, but there
 313   /// might be unnecessary sharing
 314   enum { kMaxCpus = 128 };
 315
 316   typedef uint8_t CompactStripe;
 317
 318   static_assert((kMaxCpus & (kMaxCpus - 1)) == 0,
 319                 "kMaxCpus should be a power of two so modulo is fast");
 320   static_assert(kMaxCpus - 1 <= std::numeric_limits<CompactStripe>::max(),
 321                 "stripeByCpu element type isn't wide enough");
 322
 323   /// Points to the getcpu-like function we are using to obtain the
 324   /// current cpu.  It should not be assumed that the returned cpu value
 325   /// is in range.  We use a member for this instead of a static so that
 326   /// this fetch preloads a prefix the stripeByCpu array
 327   Getcpu::Func getcpuFunc_;
 328
 329   /// A precomputed map from cpu to stripe.  Rather than add a layer of
 330   /// indirection requiring a dynamic bounds check and another cache miss,
 331   /// we always precompute the whole array
 332   CompactStripe stripeByCpu[kMaxCpus];
 333
 334   size_t numStripes_;
 335
 336   /// Returns the best getcpu implementation for this type and width
 337   /// of AccessSpreader
 338   static Getcpu::Func pickGetcpuFunc(size_t numStripes);
 339 };
 340
 341 template <>
 342 Getcpu::Func AccessSpreader<std::atomic>::pickGetcpuFunc(size_t);
 343
 344 /// An array of kMaxCpus+1 AccessSpreader<Atom> instances constructed
 345 /// with default params, with the zero-th element having 1 stripe
 346 template <template <typename> class Atom, size_t kMaxStripe>
 347 struct AccessSpreaderArray {
 348
 349   AccessSpreaderArray() {
 350     for (size_t i = 0; i <= kMaxStripe; ++i) {
 351       new (raw + i) AccessSpreader<Atom>(std::max(size_t(1), i));
 352     }
 353   }
 354
 355   ~AccessSpreaderArray() {
 356     for (size_t i = 0; i <= kMaxStripe; ++i) {
 357       auto p = static_cast<AccessSpreader<Atom>*>(static_cast<void*>(raw + i));
 358       p->~AccessSpreader();
 359     }
 360   }
 361
 362   AccessSpreader<Atom> const& operator[](size_t index) const {
 363     return *static_cast<AccessSpreader<Atom> const*>(
 364                static_cast<void const*>(raw + index));
 365   }
 366
 367  private:
 368   // AccessSpreader uses sharedInstance
 369   friend AccessSpreader<Atom>;
 370
 371   static AccessSpreaderArray<Atom, kMaxStripe> sharedInstance;
 372
 373   /// aligned_storage is uninitialized, we use placement new since there
 374   /// is no AccessSpreader default constructor
 375   typename std::aligned_storage<sizeof(AccessSpreader<Atom>),
 376                                 CacheLocality::kFalseSharingRange>::type
 377       raw[kMaxStripe + 1];
 378 };
 379 }
 380 }
 381
 382 #endif /* FOLLY_DETAIL_CacheLocality_H_ */