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