hphp/util/rank.cpp

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