hphp/util/rank.cpp

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-present 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/util/rank.h"
  17
  18 #include <cstdio>
  19 #include <cstdint>
  20 #include <stack>
  21 #include <cinttypes>
  22
  23 #include "hphp/util/mutex.h"
  24 #include "hphp/util/process.h"
  25
  26 namespace HPHP {
  27 #ifndef NDEBUG
  28 static const int kMaxLockDepth=256;
  29 static __thread Rank tl_rankStack[kMaxLockDepth];
  30 static __thread int tl_curRankDepth;
  31
  32 Rank currentRank() {
  33   // Our current rank is the most recent ranked lock we've acquired.
  34   for (int i = tl_curRankDepth - 1; i >= 0; i--) {
  35     if (tl_rankStack[i] != RankUnranked) return tl_rankStack[i];
  36   }
  37   return RankBase;
  38 }
  39
  40 void checkRank(Rank r) {
  41   if (tl_curRankDepth >= 1) {
  42     Rank prev = currentRank();
  43     /*
  44      * >= implies the ranks are a total order. If you want to allow
  45      * partial orders, make the constituent locks unranked.
  46      */
  47     if (prev >= r && r != RankUnranked) {
  48       if (r == RankLeaf) {
  49         fprintf(stderr,
  50                 "Rank violation in thr%" PRIx64 "! leaf lock from leaf rank; ",
  51                 Process::GetThreadIdForTrace());
  52       } else {
  53         fprintf(stderr, "Rank violation in thr%" PRIx64 "! lock of rank %d; ",
  54                 Process::GetThreadIdForTrace(), r);
  55       }
  56       fprintf(stderr, "held locks:\n");
  57       for (int i = tl_curRankDepth - 1; i >= 0; --i) {
  58         fprintf(stderr, "%10d\n", tl_rankStack[i]);
  59       }
  60       assert(false);
  61     }
  62   }
  63 }
  64
  65 void pushRank(Rank r) {
  66   checkRank(r);
  67   assert(tl_curRankDepth < kMaxLockDepth);
  68   tl_rankStack[tl_curRankDepth++] = r;
  69 }
  70
  71 /*
  72  * Insert a rank that may be lower than the current rank in an
  73  * appropriate position in the stack. This should only be used after a
  74  * successful trylock of a lock with rank r.
  75  */
  76 void insertRank(Rank r) {
  77   assert(r != RankUnranked);
  78   if (currentRank() <= r) {
  79     pushRank(r);
  80     return;
  81   }
  82   // Find the first real rank < r
  83   int i;
  84   for (i = tl_curRankDepth; i >= 0; i--) {
  85     if (tl_rankStack[i] < r && tl_rankStack[i] != RankUnranked) {
  86       break;
  87     }
  88   }
  89   memmove(&tl_rankStack[i+1], &tl_rankStack[i],
  90           sizeof(Rank) * (tl_curRankDepth - i));
  91   tl_rankStack[i] = r;
  92 }
  93
  94 void popRank(Rank rank) {
  95   /*
  96    * We may safely release locks out of order; this can't disturb the
  97    * global order.
  98    */
  99   assert(tl_curRankDepth >= 1);
 100   for (int i = tl_curRankDepth; i >= 0; i--) {
 101     if (tl_rankStack[i] == rank) {
 102       memmove(&tl_rankStack[i], &tl_rankStack[i + 1],
 103               sizeof(Rank) * (tl_curRankDepth - i));
 104       tl_curRankDepth--;
 105       return;
 106     }
 107   }
 108   // If you hit this, you popped a rank that was never pushed.
 109   not_reached();
 110 }
 111 #endif
 112
 113 }