2 * Copyright 2014 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 #include <folly/detail/CacheLocality.h>
19 #define _GNU_SOURCE 1 // for RTLD_NOLOAD
23 #include <folly/Conv.h>
24 #include <folly/Exception.h>
25 #include <folly/FileUtil.h>
26 #include <folly/Format.h>
27 #include <folly/ScopeGuard.h>
29 namespace folly { namespace detail {
31 ///////////// CacheLocality
33 /// Returns the best real CacheLocality information available
34 static CacheLocality getSystemLocalityInfo() {
37 return CacheLocality::readFromSysfs();
43 long numCpus = sysconf(_SC_NPROCESSORS_CONF);
45 // This shouldn't happen, but if it does we should try to keep
46 // going. We are probably not going to be able to parse /sys on
47 // this box either (although we will try), which means we are going
48 // to fall back to the SequentialThreadId splitter. On my 16 core
49 // (x hyperthreading) dev box 16 stripes is enough to get pretty good
50 // contention avoidance with SequentialThreadId, and there is little
51 // improvement from going from 32 to 64. This default gives us some
55 return CacheLocality::uniform(numCpus);
59 const CacheLocality& CacheLocality::system<std::atomic>() {
60 static CacheLocality cache(getSystemLocalityInfo());
64 // Each level of cache has sharing sets, which are the set of cpus
65 // that share a common cache at that level. These are available in a
66 // hex bitset form (/sys/devices/system/cpu/cpu0/index0/shared_cpu_map,
67 // for example). They are also available in a human-readable list form,
68 // as in /sys/devices/system/cpu/cpu0/index0/shared_cpu_list. The list
69 // is a comma-separated list of numbers and ranges, where the ranges are
70 // a pair of decimal numbers separated by a '-'.
72 // To sort the cpus for optimum locality we don't really need to parse
73 // the sharing sets, we just need a unique representative from the
74 // equivalence class. The smallest value works fine, and happens to be
75 // the first decimal number in the file. We load all of the equivalence
76 // class information from all of the cpu*/index* directories, order the
77 // cpus first by increasing last-level cache equivalence class, then by
78 // the smaller caches. Finally, we break ties with the cpu number itself.
80 /// Returns the first decimal number in the string, or throws an exception
81 /// if the string does not start with a number terminated by ',', '-',
83 static ssize_t parseLeadingNumber(const std::string& line) {
84 auto raw = line.c_str();
86 unsigned val = strtoul(raw, &end, 10);
87 if (end == raw || (*end != ',' && *end != '-' && *end != '\n')) {
88 throw std::runtime_error(to<std::string>(
89 "error parsing list '", line, "'").c_str());
94 CacheLocality CacheLocality::readFromSysfsTree(
95 const std::function<std::string(std::string)>& mapping) {
96 // number of equivalence classes per level
97 std::vector<size_t> numCachesByLevel;
99 // the list of cache equivalence classes, where equivalance classes
100 // are named by the smallest cpu in the class
101 std::vector<std::vector<size_t>> equivClassesByCpu;
103 std::vector<size_t> cpus;
106 auto cpu = cpus.size();
107 std::vector<size_t> levels;
108 for (size_t index = 0; ; ++index) {
109 auto dir = format("/sys/devices/system/cpu/cpu{}/cache/index{}/",
111 auto cacheType = mapping(dir + "type");
112 auto equivStr = mapping(dir + "shared_cpu_list");
113 if (cacheType.size() == 0 || equivStr.size() == 0) {
117 if (cacheType[0] == 'I') {
118 // cacheType in { "Data", "Instruction", "Unified" }. skip icache
121 auto equiv = parseLeadingNumber(equivStr);
122 auto level = levels.size();
123 levels.push_back(equiv);
126 // we only want to count the equiv classes once, so we do it when
127 // we first encounter them
128 while (numCachesByLevel.size() <= level) {
129 numCachesByLevel.push_back(0);
131 numCachesByLevel[level]++;
135 if (levels.size() == 0) {
136 // no levels at all for this cpu, we must be done
139 equivClassesByCpu.emplace_back(std::move(levels));
143 if (cpus.size() == 0) {
144 throw std::runtime_error("unable to load cache sharing info");
147 std::sort(cpus.begin(), cpus.end(), [&](size_t lhs, size_t rhs) -> bool {
148 // sort first by equiv class of cache with highest index, direction
149 // doesn't matter. If different cpus have different numbers of
150 // caches then this code might produce a sub-optimal ordering, but
152 auto& lhsEquiv = equivClassesByCpu[lhs];
153 auto& rhsEquiv = equivClassesByCpu[rhs];
154 for (int i = std::min(lhsEquiv.size(), rhsEquiv.size()) - 1; i >= 0; --i) {
155 if (lhsEquiv[i] != rhsEquiv[i]) {
156 return lhsEquiv[i] < rhsEquiv[i];
160 // break ties deterministically by cpu
164 // the cpus are now sorted by locality, with neighboring entries closer
165 // to each other than entries that are far away. For striping we want
166 // the inverse map, since we are starting with the cpu
167 std::vector<size_t> indexes(cpus.size());
168 for (int i = 0; i < cpus.size(); ++i) {
169 indexes[cpus[i]] = i;
172 return CacheLocality{
173 cpus.size(), std::move(numCachesByLevel), std::move(indexes) };
176 CacheLocality CacheLocality::readFromSysfs() {
177 return readFromSysfsTree([](std::string name) {
178 std::ifstream xi(name.c_str());
180 std::getline(xi, rv);
186 CacheLocality CacheLocality::uniform(size_t numCpus) {
189 rv.numCpus = numCpus;
191 // one cache shared by all cpus
192 rv.numCachesByLevel.push_back(numCpus);
194 // no permutations in locality index mapping
195 for (size_t cpu = 0; cpu < numCpus; ++cpu) {
196 rv.localityIndexByCpu.push_back(cpu);
202 ////////////// Getcpu
204 /// Resolves the dynamically loaded symbol __vdso_getcpu, returning null
206 static Getcpu::Func loadVdsoGetcpu() {
207 void* h = dlopen("linux-vdso.so.1", RTLD_LAZY | RTLD_LOCAL | RTLD_NOLOAD);
212 auto func = Getcpu::Func(dlsym(h, "__vdso_getcpu"));
213 if (func == nullptr) {
214 // technically a null result could either be a failure or a successful
215 // lookup of a symbol with the null value, but the second can't actually
216 // happen for this symbol. No point holding the handle forever if
217 // we don't need the code
224 Getcpu::Func Getcpu::vdsoFunc() {
225 static Func func = loadVdsoGetcpu();
229 /////////////// SequentialThreadId
232 std::atomic<size_t> SequentialThreadId<std::atomic>::prevId(0);
235 FOLLY_TLS size_t SequentialThreadId<std::atomic>::currentId(0);
237 /////////////// AccessSpreader
240 const AccessSpreader<std::atomic>
241 AccessSpreader<std::atomic>::stripeByCore(
242 CacheLocality::system<>().numCachesByLevel.front());
245 const AccessSpreader<std::atomic>
246 AccessSpreader<std::atomic>::stripeByChip(
247 CacheLocality::system<>().numCachesByLevel.back());
250 AccessSpreaderArray<std::atomic,128>
251 AccessSpreaderArray<std::atomic,128>::sharedInstance = {};
253 /// Always claims to be on CPU zero, node zero
254 static int degenerateGetcpu(unsigned* cpu, unsigned* node, void* unused) {
255 if (cpu != nullptr) {
258 if (node != nullptr) {
265 Getcpu::Func AccessSpreader<std::atomic>::pickGetcpuFunc(size_t numStripes) {
266 if (numStripes == 1) {
267 // there's no need to call getcpu if there is only one stripe.
268 // This should not be common, so we don't want to waste a test and
269 // branch in the main code path, but we might as well use a faster
271 return °enerateGetcpu;
273 auto best = Getcpu::vdsoFunc();
274 return best ? best : &SequentialThreadId<std::atomic>::getcpu;
278 } } // namespace folly::detail