hphp/runtime/vm/type_profile.cpp

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010- Facebook, Inc. (http://www.facebook.com)         |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.php.net/license/3_01.txt                                  |
  11    | If you did not receive a copy of the PHP license and are unable to   |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@php.net so we can mail you a copy immediately.               |
  14    +----------------------------------------------------------------------+
  15 */
  16 #include "hphp/runtime/vm/type_profile.h"
  17 #include "hphp/runtime/base/runtime_option.h"
  18 #include "hphp/runtime/base/stats.h"
  19 #include "hphp/runtime/vm/translator/translator.h"
  20 #include "hphp/util/trace.h"
  21
  22 #include <string.h>
  23 #include "sys/types.h"
  24 #include "sys/stat.h"
  25 #include "sys/mman.h"
  26 #include <unistd.h>
  27 #include <fcntl.h>
  28
  29 namespace HPHP {
  30
  31 TRACE_SET_MOD(typeProfile);
  32
  33 /*
  34  * It is useful at translation time to have a hunch as to the types a given
  35  * instruction is likely to produce. This is a probabilistic data structure
  36  * that tries to balance: cost of reading and writing; memory overhead;
  37  * prediction recall (percentage of time we make a prediction); prediction
  38  * accuracy (fidelity relative to reality); and prediction precision
  39  * (fidelity relative to ourselves).
  40  */
  41
  42 typedef uint16_t Counter;
  43 static const Counter kMaxCounter = USHRT_MAX;
  44
  45 struct ValueProfile {
  46   uint32_t m_tag;
  47   // All of these saturate at 255.
  48   Counter m_totalSamples;
  49   Counter m_samples[MaxNumDataTypesIndex];
  50   void dump() {
  51     for (int i = 0; i < MaxNumDataTypesIndex; i++) {
  52       TRACE(0, "t%3d: %4d\n", i, m_samples[getDataTypeValue(i)]);
  53     }
  54   }
  55 };
  56
  57 /*
  58  * Magic tunables.
  59  */
  60
  61 /*
  62  * kNumEntries
  63  *
  64  * Tradeoff: size vs. accuracy.
  65  *
  66  * ~256K entries.
  67  *
  68  * Size: (sizeof(ValueProfile) == 16) B -> 4MB
  69  *
  70  * Accuracy: If we collide further than kLineSize, we toss out perfectly
  71  * good evidence. www seems to use about 12000 method names at this
  72  * writing, so we have a decent pad for collisions.
  73  */
  74
  75 static const int kNumEntries = 1 << 18;
  76 static const int kLineSizeLog2 = 2;
  77 static const int kLineSize = 1 << kLineSizeLog2;
  78 static const int kNumLines = kNumEntries / kLineSize;
  79 static const int kNumLinesMask = kNumLines - 1;
  80
  81 /*
  82  * kMinInstances
  83  *
  84  * Tradeoff: recall vs. accuracy. This is the minimum number of examples
  85  * before we'll report any information at all.
  86  *
  87  * Recall: If we set this too high, we'll never be able to predict
  88  * anything.
  89  *
  90  * Accuracy: If we set this too low, we'll be "jumpy", eagerly predicting
  91  * types on the basis of weak evidence.
  92  */
  93 static const double kMinInstances = 99.0;
  94
  95 typedef ValueProfile ValueProfileLine[kLineSize];
  96 static ValueProfileLine* profiles;
  97
  98 static ValueProfileLine*
  99 profileInitMmap() {
 100   const std::string& path = RuntimeOption::EvalJitProfilePath;
 101   if (path.empty()) {
 102     return nullptr;
 103   }
 104
 105   TRACE(1, "profileInit: path %s\n", path.c_str());
 106   int fd = open(path.c_str(), O_RDWR | O_CREAT, 0600);
 107   if (fd < 0) {
 108     TRACE(0, "profileInit: open %s failed: %s\n", path.c_str(),
 109           strerror(errno));
 110     perror("open");
 111     return nullptr;
 112   }
 113
 114   size_t len = sizeof(ValueProfileLine) * kNumLines;
 115   int retval = ftruncate(fd, len);
 116   if (retval < 0) {
 117     perror("truncate");
 118     TRACE(0, "profileInit: truncate %s failed: %s\n", path.c_str(),
 119           strerror(errno));
 120     return nullptr;
 121   }
 122
 123   int flags = PROT_READ |
 124     (RuntimeOption::EvalJitProfileRecord ? PROT_WRITE : 0);
 125   void* mmapRet = mmap(0, len, flags, MAP_SHARED, // Yes, shared.
 126                        fd, 0);
 127   if (mmapRet == MAP_FAILED) {
 128     perror("mmap");
 129     TRACE(0, "profileInit: mmap %s failed: %s\n", path.c_str(),
 130           strerror(errno));
 131     return nullptr;
 132   }
 133   return (ValueProfileLine*)mmapRet;
 134 }
 135
 136 void
 137 profileInit() {
 138   if (!profiles) {
 139     profiles = profileInitMmap();
 140     if (!profiles) {
 141       TRACE(1, "profileInit: anonymous memory.\n");
 142       profiles = (ValueProfileLine*)calloc(sizeof(ValueProfileLine), kNumLines);
 143       assert(profiles);
 144     }
 145   }
 146 }
 147
 148 /*
 149  * Warmup.
 150  *
 151  * In cli mode, we only record samples if we're in recording to replay
 152  * later.
 153  *
 154  * For server mode, we record samples for all requests started after
 155  * the EvalJitWarmupRequests'th req.
 156  */
 157 bool __thread profileOn = false;
 158 static int64_t numRequests;
 159
 160 static inline bool warmedUp() {
 161   return (numRequests >= RuntimeOption::EvalJitWarmupRequests) ||
 162     (RuntimeOption::clientExecutionMode() &&
 163      !RuntimeOption::EvalJitProfileRecord);
 164 }
 165
 166 static inline bool profileThisRequest() {
 167   if (warmedUp()) return false;
 168   if (RuntimeOption::serverExecutionMode()) return true;
 169   return RuntimeOption::EvalJitProfileRecord;
 170 }
 171
 172 void
 173 profileRequestStart() {
 174   bool p = profileThisRequest();
 175   if (p != profileOn) {
 176     profileOn = p;
 177     if (!ThreadInfo::s_threadInfo.isNull()) {
 178       ThreadInfo::s_threadInfo->m_reqInjectionData.updateJit();
 179     }
 180   }
 181 }
 182
 183 void profileRequestEnd() {
 184   numRequests++; // racy RMW; ok to miss a rare few.
 185 }
 186
 187 enum KeyToVPMode {
 188   Read, Write
 189 };
 190
 191 uint64_t
 192 TypeProfileKey::hash() const {
 193   return hash_int64_pair(m_kind, m_name->hash());
 194 }
 195
 196 static inline ValueProfile*
 197 keyToVP(TypeProfileKey key, KeyToVPMode mode) {
 198   assert(profiles);
 199   uint64_t h = key.hash();
 200   // Use the low-order kLineSizeLog2 bits to as tag bits to distinguish
 201   // within the line, rather than to choose a line. Without the shift, all
 202   // the tags in the line would have the same low-order bits, making
 203   // collisions kLineSize times more likely.
 204   int hidx = (h >> kLineSizeLog2) & kNumLinesMask;
 205   ValueProfileLine& l = profiles[hidx];
 206   int replaceCandidate = 0;
 207   int minCount = 255;
 208   for (int i = 0; i < kLineSize; i++) {
 209     if (l[i].m_tag == uint32_t(h)) {
 210       TRACE(2, "Found %d for %s -> %d\n",
 211             l[i].m_tag, key.m_name->data(), uint32_t(h));
 212       return &l[i];
 213     }
 214     if (mode == Write && l[i].m_totalSamples < minCount) {
 215       replaceCandidate = i;
 216       minCount = l[i].m_totalSamples;
 217     }
 218   }
 219   if (mode == Write) {
 220     assert(replaceCandidate >= 0 && replaceCandidate < kLineSize);
 221     ValueProfile& vp = l[replaceCandidate];
 222     Stats::inc(Stats::TypePred_Evict, vp.m_totalSamples != 0);
 223     Stats::inc(Stats::TypePred_Insert);
 224     TRACE(1, "Killing %d in favor of %s -> %d\n",
 225           vp.m_tag, key.m_name ? key.m_name->data() : "NULL", uint32_t(h));
 226     vp.m_totalSamples = 0;
 227     memset(&vp.m_samples, 0, sizeof(vp.m_samples));
 228     // Zero first, then claim. It seems safer to temporarily zero out some
 229     // other function's values than to have this new function using the
 230     // possibly-non-trivial prediction from an unrelated function.
 231     Util::compiler_membar();
 232     vp.m_tag = uint32_t(h);
 233     return &l[replaceCandidate];
 234   }
 235   return nullptr;
 236 }
 237
 238 void recordType(TypeProfileKey key, DataType dt) {
 239   if (!profiles) return;
 240   if (!shouldProfile()) return;
 241   assert(dt != KindOfUninit);
 242   // Normalize strings to KindOfString.
 243   if (dt == KindOfStaticString) dt = KindOfString;
 244   TRACE(1, "recordType lookup: %s -> %d\n", key.m_name->data(), dt);
 245   ValueProfile *prof = keyToVP(key, Write);
 246   if (prof->m_totalSamples != kMaxCounter) {
 247     prof->m_totalSamples++;
 248     // NB: we can't quite assert that we have fewer than kMaxCounter samples,
 249     // because other threads are updating this structure without locks.
 250     int dtIndex = getDataTypeIndex(dt);
 251     if (prof->m_samples[dtIndex] < kMaxCounter) {
 252       prof->m_samples[dtIndex]++;
 253     }
 254   }
 255   ONTRACE(2, prof->dump());
 256 }
 257
 258 typedef std::pair<DataType, double> PredVal;
 259
 260 PredVal predictType(TypeProfileKey key) {
 261   PredVal kNullPred = std::make_pair(KindOfUninit, 0.0);
 262   if (!profiles) return kNullPred;
 263   const ValueProfile *prof = keyToVP(key, Read);
 264   if (!prof) {
 265     TRACE(2, "predictType lookup: %s -> MISS\n", key.m_name->data());
 266     Stats::inc(Stats::TypePred_Miss);
 267     return kNullPred;
 268   }
 269   double total = prof->m_totalSamples;
 270   if (total < kMinInstances) {
 271     Stats::inc(Stats::TypePred_MissTooFew);
 272     TRACE(2, "TypePred: hit %s but too few samples numSamples %d\n",
 273           key.m_name->data(), prof->m_totalSamples);
 274     return kNullPred;
 275   }
 276   double maxProb = 0.0;
 277   DataType pred = KindOfUninit;
 278   // If we have fewer than kMinInstances predictions, consider it too
 279   // little data to be actionable.
 280   for (int i = 0; i < MaxNumDataTypesIndex; ++i) {
 281     double prob = (1.0 * prof->m_samples[i]) / total;
 282     if (prob > maxProb) {
 283       maxProb = prob;
 284       pred = getDataTypeValue(i);
 285     }
 286     if (prob >= 1.0) break;
 287   }
 288   Stats::inc(Stats::TypePred_Hit, maxProb >= 1.0);
 289   Stats::inc(Stats::TypePred_MissTooWeak, maxProb < 1.0);
 290   TRACE(2, "TypePred: hit %s numSamples %d pred %d prob %g\n",
 291         key.m_name->data(), prof->m_totalSamples, pred, maxProb);
 292   // Probabilities over 1.0 are possible due to racy updates.
 293   if (maxProb > 1.0) maxProb = 1.0;
 294   return std::make_pair(pred, maxProb);
 295 }
 296
 297 bool isProfileOpcode(const PC& pc) {
 298   return *pc == OpRetC || *pc == OpCGetM;
 299 }
 300
 301 }