folly/detail/CacheLocality.cpp

   1 /*
   2  * Copyright 2014 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 #include <folly/detail/CacheLocality.h>
  18
  19 #define _GNU_SOURCE 1 // for RTLD_NOLOAD
  20 #include <dlfcn.h>
  21 #include <fstream>
  22
  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>
  28
  29 namespace folly { namespace detail {
  30
  31 ///////////// CacheLocality
  32
  33 /// Returns the best real CacheLocality information available
  34 static CacheLocality getSystemLocalityInfo() {
  35 #ifdef __linux__
  36   try {
  37     return CacheLocality::readFromSysfs();
  38   } catch (...) {
  39     // keep trying
  40   }
  41 #endif
  42
  43   long numCpus = sysconf(_SC_NPROCESSORS_CONF);
  44   if (numCpus <= 0) {
  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
  52     // wiggle room
  53     numCpus = 32;
  54   }
  55   return CacheLocality::uniform(numCpus);
  56 }
  57
  58 template <>
  59 const CacheLocality& CacheLocality::system<std::atomic>() {
  60   static CacheLocality cache(getSystemLocalityInfo());
  61   return cache;
  62 }
  63
  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 '-'.
  71 //
  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.
  79
  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 ',', '-',
  82 /// '\n', or eos.
  83 static size_t parseLeadingNumber(const std::string& line) {
  84   auto raw = line.c_str();
  85   char *end;
  86   unsigned long 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());
  90   }
  91   return val;
  92 }
  93
  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;
  98
  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;
 102
 103   std::vector<size_t> cpus;
 104
 105   while (true) {
 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{}/",
 110                         cpu, index).str();
 111       auto cacheType = mapping(dir + "type");
 112       auto equivStr = mapping(dir + "shared_cpu_list");
 113       if (cacheType.size() == 0 || equivStr.size() == 0) {
 114         // no more caches
 115         break;
 116       }
 117       if (cacheType[0] == 'I') {
 118         // cacheType in { "Data", "Instruction", "Unified" }. skip icache
 119         continue;
 120       }
 121       auto equiv = parseLeadingNumber(equivStr);
 122       auto level = levels.size();
 123       levels.push_back(equiv);
 124
 125       if (equiv == cpu) {
 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);
 130         }
 131         numCachesByLevel[level]++;
 132       }
 133     }
 134
 135     if (levels.size() == 0) {
 136       // no levels at all for this cpu, we must be done
 137       break;
 138     }
 139     equivClassesByCpu.emplace_back(std::move(levels));
 140     cpus.push_back(cpu);
 141   }
 142
 143   if (cpus.size() == 0) {
 144     throw std::runtime_error("unable to load cache sharing info");
 145   }
 146
 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
 151     // it won't crash
 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];
 157       }
 158     }
 159
 160     // break ties deterministically by cpu
 161     return lhs < rhs;
 162   });
 163
 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 (size_t i = 0; i < cpus.size(); ++i) {
 169     indexes[cpus[i]] = i;
 170   }
 171
 172   return CacheLocality{
 173       cpus.size(), std::move(numCachesByLevel), std::move(indexes) };
 174 }
 175
 176 CacheLocality CacheLocality::readFromSysfs() {
 177   return readFromSysfsTree([](std::string name) {
 178     std::ifstream xi(name.c_str());
 179     std::string rv;
 180     std::getline(xi, rv);
 181     return rv;
 182   });
 183 }
 184
 185
 186 CacheLocality CacheLocality::uniform(size_t numCpus) {
 187   CacheLocality rv;
 188
 189   rv.numCpus = numCpus;
 190
 191   // one cache shared by all cpus
 192   rv.numCachesByLevel.push_back(numCpus);
 193
 194   // no permutations in locality index mapping
 195   for (size_t cpu = 0; cpu < numCpus; ++cpu) {
 196     rv.localityIndexByCpu.push_back(cpu);
 197   }
 198
 199   return rv;
 200 }
 201
 202 ////////////// Getcpu
 203
 204 /// Resolves the dynamically loaded symbol __vdso_getcpu, returning null
 205 /// on failure
 206 static Getcpu::Func loadVdsoGetcpu() {
 207   void* h = dlopen("linux-vdso.so.1", RTLD_LAZY | RTLD_LOCAL | RTLD_NOLOAD);
 208   if (h == nullptr) {
 209     return nullptr;
 210   }
 211
 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
 218     dlclose(h);
 219   }
 220
 221   return func;
 222 }
 223
 224 Getcpu::Func Getcpu::vdsoFunc() {
 225   static Func func = loadVdsoGetcpu();
 226   return func;
 227 }
 228
 229 /////////////// SequentialThreadId
 230
 231 template<>
 232 std::atomic<size_t> SequentialThreadId<std::atomic>::prevId(0);
 233
 234 template<>
 235 FOLLY_TLS size_t SequentialThreadId<std::atomic>::currentId(0);
 236
 237 /////////////// AccessSpreader
 238
 239 template<>
 240 const AccessSpreader<std::atomic>
 241 AccessSpreader<std::atomic>::stripeByCore(
 242     CacheLocality::system<>().numCachesByLevel.front());
 243
 244 template<>
 245 const AccessSpreader<std::atomic>
 246 AccessSpreader<std::atomic>::stripeByChip(
 247     CacheLocality::system<>().numCachesByLevel.back());
 248
 249 template<>
 250 AccessSpreaderArray<std::atomic,128>
 251 AccessSpreaderArray<std::atomic,128>::sharedInstance = {};
 252
 253 /// Always claims to be on CPU zero, node zero
 254 static int degenerateGetcpu(unsigned* cpu, unsigned* node, void* unused) {
 255   if (cpu != nullptr) {
 256     *cpu = 0;
 257   }
 258   if (node != nullptr) {
 259     *node = 0;
 260   }
 261   return 0;
 262 }
 263
 264 template<>
 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
 270     // function pointer
 271     return &degenerateGetcpu;
 272   } else {
 273     auto best = Getcpu::vdsoFunc();
 274     return best ? best : &SequentialThreadId<std::atomic>::getcpu;
 275   }
 276 }
 277
 278 } } // namespace folly::detail