src/ceph/src/common/lockdep.cc

   1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
   2 // vim: ts=8 sw=2 smarttab
   3 /*
   4  * Ceph - scalable distributed file system
   5  *
   6  * Copyright (C) 2008-2011 New Dream Network
   7  *
   8  * This is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU Lesser General Public
  10  * License version 2.1, as published by the Free Software
  11  * Foundation.  See file COPYING.
  12  *
  13  */
  14 #include "lockdep.h"
  15 #include "common/dout.h"
  16 #include "common/valgrind.h"
  17
  18 #if defined(__FreeBSD__) && defined(__LP64__)   // On FreeBSD pthread_t is a pointer.
  19 namespace std {
  20   template<>
  21     struct hash<pthread_t>
  22     {
  23       size_t
  24       operator()(pthread_t __x) const
  25       { return (uintptr_t)__x; }
  26     };
  27 } // namespace std
  28 #endif
  29
  30 /******* Constants **********/
  31 #define lockdep_dout(v) lsubdout(g_lockdep_ceph_ctx, lockdep, v)
  32 #define MAX_LOCKS  4096   // increase me as needed
  33 #define BACKTRACE_SKIP 2
  34
  35 /******* Globals **********/
  36 int g_lockdep = 0;
  37 struct lockdep_stopper_t {
  38   // disable lockdep when this module destructs.
  39   ~lockdep_stopper_t() {
  40     g_lockdep = 0;
  41   }
  42 };
  43 static pthread_mutex_t lockdep_mutex = PTHREAD_MUTEX_INITIALIZER;
  44 static CephContext *g_lockdep_ceph_ctx = NULL;
  45 static lockdep_stopper_t lockdep_stopper;
  46 static ceph::unordered_map<std::string, int> lock_ids;
  47 static map<int, std::string> lock_names;
  48 static map<int, int> lock_refs;
  49 static char free_ids[MAX_LOCKS/8]; // bit set = free
  50 static ceph::unordered_map<pthread_t, map<int,BackTrace*> > held;
  51 static char follows[MAX_LOCKS][MAX_LOCKS/8]; // follows[a][b] means b taken after a
  52 static BackTrace *follows_bt[MAX_LOCKS][MAX_LOCKS];
  53 unsigned current_maxid;
  54 int last_freed_id;
  55
  56 static bool lockdep_force_backtrace()
  57 {
  58   return (g_lockdep_ceph_ctx != NULL &&
  59           g_lockdep_ceph_ctx->_conf->lockdep_force_backtrace);
  60 }
  61
  62 /******* Functions **********/
  63 void lockdep_register_ceph_context(CephContext *cct)
  64 {
  65   static_assert((MAX_LOCKS > 0) && (MAX_LOCKS % 8 == 0),
  66     "lockdep's MAX_LOCKS needs to be divisible by 8 to operate correctly.");
  67   pthread_mutex_lock(&lockdep_mutex);
  68   if (g_lockdep_ceph_ctx == NULL) {
  69     ANNOTATE_BENIGN_RACE_SIZED(&g_lockdep_ceph_ctx, sizeof(g_lockdep_ceph_ctx),
  70                                "lockdep cct");
  71     ANNOTATE_BENIGN_RACE_SIZED(&g_lockdep, sizeof(g_lockdep),
  72                                "lockdep enabled");
  73     g_lockdep = true;
  74     g_lockdep_ceph_ctx = cct;
  75     lockdep_dout(1) << "lockdep start" << dendl;
  76     current_maxid = 0;
  77         last_freed_id = -1;
  78
  79     memset((void*) &free_ids[0], 255, sizeof(free_ids));
  80   }
  81   pthread_mutex_unlock(&lockdep_mutex);
  82 }
  83
  84 void lockdep_unregister_ceph_context(CephContext *cct)
  85 {
  86   pthread_mutex_lock(&lockdep_mutex);
  87   if (cct == g_lockdep_ceph_ctx) {
  88     lockdep_dout(1) << "lockdep stop" << dendl;
  89     // this cct is going away; shut it down!
  90     g_lockdep = false;
  91     g_lockdep_ceph_ctx = NULL;
  92
  93     // blow away all of our state, too, in case it starts up again.
  94     for (unsigned i = 0; i < current_maxid; ++i) {
  95       for (unsigned j = 0; j < current_maxid; ++j) {
  96         delete follows_bt[i][j];
  97       }
  98     }
  99
 100     held.clear();
 101     lock_names.clear();
 102     lock_ids.clear();
 103     lock_refs.clear();
 104     memset((void*)&free_ids[0], 0, sizeof(free_ids));
 105     memset((void*)&follows[0][0], 0, current_maxid * MAX_LOCKS/8);
 106     memset((void*)&follows_bt[0][0], 0, sizeof(BackTrace*) * current_maxid * MAX_LOCKS);
 107     current_maxid = 0;
 108     last_freed_id = -1;
 109   }
 110   pthread_mutex_unlock(&lockdep_mutex);
 111 }
 112
 113 int lockdep_dump_locks()
 114 {
 115   pthread_mutex_lock(&lockdep_mutex);
 116
 117   for (ceph::unordered_map<pthread_t, map<int,BackTrace*> >::iterator p = held.begin();
 118        p != held.end();
 119        ++p) {
 120     lockdep_dout(0) << "--- thread " << p->first << " ---" << dendl;
 121     for (map<int,BackTrace*>::iterator q = p->second.begin();
 122          q != p->second.end();
 123          ++q) {
 124       lockdep_dout(0) << "  * " << lock_names[q->first] << "\n";
 125       if (q->second)
 126         *_dout << *(q->second);
 127       *_dout << dendl;
 128     }
 129   }
 130
 131   pthread_mutex_unlock(&lockdep_mutex);
 132   return 0;
 133 }
 134
 135 int lockdep_get_free_id(void)
 136 {
 137   // if there's id known to be freed lately, reuse it
 138   if ((last_freed_id >= 0) &&
 139      (free_ids[last_freed_id/8] & (1 << (last_freed_id % 8)))) {
 140     int tmp = last_freed_id;
 141     last_freed_id = -1;
 142     free_ids[tmp/8] &= 255 - (1 << (tmp % 8));
 143     lockdep_dout(1) << "lockdep reusing last freed id " << tmp << dendl;
 144     return tmp;
 145   }
 146
 147   // walk through entire array and locate nonzero char, then find
 148   // actual bit.
 149   for (int i = 0; i < MAX_LOCKS / 8; ++i) {
 150     if (free_ids[i] != 0) {
 151       for (int j = 0; j < 8; ++j) {
 152         if (free_ids[i] & (1 << j)) {
 153           free_ids[i] &= 255 - (1 << j);
 154           lockdep_dout(1) << "lockdep using id " << i * 8 + j << dendl;
 155           return i * 8 + j;
 156         }
 157       }
 158     }
 159   }
 160
 161   // not found
 162   lockdep_dout(0) << "failing miserably..." << dendl;
 163   return -1;
 164 }
 165
 166 int lockdep_register(const char *name)
 167 {
 168   int id;
 169
 170   pthread_mutex_lock(&lockdep_mutex);
 171   ceph::unordered_map<std::string, int>::iterator p = lock_ids.find(name);
 172   if (p == lock_ids.end()) {
 173     id = lockdep_get_free_id();
 174     if (id < 0) {
 175       lockdep_dout(0) << "ERROR OUT OF IDS .. have 0"
 176                       << " max " << MAX_LOCKS << dendl;
 177       for (auto& p : lock_names) {
 178         lockdep_dout(0) << "  lock " << p.first << " " << p.second << dendl;
 179       }
 180       assert(false);
 181     }
 182     if (current_maxid <= (unsigned)id) {
 183         current_maxid = (unsigned)id + 1;
 184     }
 185     lock_ids[name] = id;
 186     lock_names[id] = name;
 187     lockdep_dout(10) << "registered '" << name << "' as " << id << dendl;
 188   } else {
 189     id = p->second;
 190     lockdep_dout(20) << "had '" << name << "' as " << id << dendl;
 191   }
 192
 193   ++lock_refs[id];
 194   pthread_mutex_unlock(&lockdep_mutex);
 195
 196   return id;
 197 }
 198
 199 void lockdep_unregister(int id)
 200 {
 201   if (id < 0) {
 202     return;
 203   }
 204
 205   pthread_mutex_lock(&lockdep_mutex);
 206
 207   map<int, std::string>::iterator p = lock_names.find(id);
 208   assert(p != lock_names.end());
 209
 210   int &refs = lock_refs[id];
 211   if (--refs == 0) {
 212     // reset dependency ordering
 213     memset((void*)&follows[id][0], 0, MAX_LOCKS/8);
 214     for (unsigned i=0; i<current_maxid; ++i) {
 215       delete follows_bt[id][i];
 216       follows_bt[id][i] = NULL;
 217
 218       delete follows_bt[i][id];
 219       follows_bt[i][id] = NULL;
 220       follows[i][id / 8] &= 255 - (1 << (id % 8));
 221     }
 222
 223     lockdep_dout(10) << "unregistered '" << p->second << "' from " << id
 224                      << dendl;
 225     lock_ids.erase(p->second);
 226     lock_names.erase(id);
 227     lock_refs.erase(id);
 228     free_ids[id/8] |= (1 << (id % 8));
 229         last_freed_id = id;
 230   } else {
 231     lockdep_dout(20) << "have " << refs << " of '" << p->second << "' "
 232                      << "from " << id << dendl;
 233   }
 234   pthread_mutex_unlock(&lockdep_mutex);
 235 }
 236
 237
 238 // does b follow a?
 239 static bool does_follow(int a, int b)
 240 {
 241   if (follows[a][b/8] & (1 << (b % 8))) {
 242     lockdep_dout(0) << "\n";
 243     *_dout << "------------------------------------" << "\n";
 244     *_dout << "existing dependency " << lock_names[a] << " (" << a << ") -> "
 245            << lock_names[b] << " (" << b << ") at:\n";
 246     if (follows_bt[a][b]) {
 247       follows_bt[a][b]->print(*_dout);
 248     }
 249     *_dout << dendl;
 250     return true;
 251   }
 252
 253   for (unsigned i=0; i<current_maxid; i++) {
 254     if ((follows[a][i/8] & (1 << (i % 8))) &&
 255         does_follow(i, b)) {
 256       lockdep_dout(0) << "existing intermediate dependency " << lock_names[a]
 257           << " (" << a << ") -> " << lock_names[i] << " (" << i << ") at:\n";
 258       if (follows_bt[a][i]) {
 259         follows_bt[a][i]->print(*_dout);
 260       }
 261       *_dout << dendl;
 262       return true;
 263     }
 264   }
 265
 266   return false;
 267 }
 268
 269 int lockdep_will_lock(const char *name, int id, bool force_backtrace)
 270 {
 271   pthread_t p = pthread_self();
 272   if (id < 0) id = lockdep_register(name);
 273
 274   pthread_mutex_lock(&lockdep_mutex);
 275   lockdep_dout(20) << "_will_lock " << name << " (" << id << ")" << dendl;
 276
 277   // check dependency graph
 278   map<int, BackTrace *> &m = held[p];
 279   for (map<int, BackTrace *>::iterator p = m.begin();
 280        p != m.end();
 281        ++p) {
 282     if (p->first == id) {
 283       lockdep_dout(0) << "\n";
 284       *_dout << "recursive lock of " << name << " (" << id << ")\n";
 285       BackTrace *bt = new BackTrace(BACKTRACE_SKIP);
 286       bt->print(*_dout);
 287       if (p->second) {
 288         *_dout << "\npreviously locked at\n";
 289         p->second->print(*_dout);
 290       }
 291       delete bt;
 292       *_dout << dendl;
 293       ceph_abort();
 294     }
 295     else if (!(follows[p->first][id/8] & (1 << (id % 8)))) {
 296       // new dependency
 297
 298       // did we just create a cycle?
 299       if (does_follow(id, p->first)) {
 300         BackTrace *bt = new BackTrace(BACKTRACE_SKIP);
 301         lockdep_dout(0) << "new dependency " << lock_names[p->first]
 302                 << " (" << p->first << ") -> " << name << " (" << id << ")"
 303                 << " creates a cycle at\n";
 304         bt->print(*_dout);
 305         *_dout << dendl;
 306
 307         lockdep_dout(0) << "btw, i am holding these locks:" << dendl;
 308         for (map<int, BackTrace *>::iterator q = m.begin();
 309              q != m.end();
 310              ++q) {
 311           lockdep_dout(0) << "  " << lock_names[q->first] << " (" << q->first << ")" << dendl;
 312           if (q->second) {
 313             lockdep_dout(0) << " ";
 314             q->second->print(*_dout);
 315             *_dout << dendl;
 316           }
 317         }
 318
 319         lockdep_dout(0) << "\n" << dendl;
 320
 321         // don't add this dependency, or we'll get aMutex. cycle in the graph, and
 322         // does_follow() won't terminate.
 323
 324         ceph_abort();  // actually, we should just die here.
 325       } else {
 326         BackTrace *bt = NULL;
 327         if (force_backtrace || lockdep_force_backtrace()) {
 328           bt = new BackTrace(BACKTRACE_SKIP);
 329         }
 330         follows[p->first][id/8] |= 1 << (id % 8);
 331         follows_bt[p->first][id] = bt;
 332         lockdep_dout(10) << lock_names[p->first] << " -> " << name << " at" << dendl;
 333         //bt->print(*_dout);
 334       }
 335     }
 336   }
 337
 338   pthread_mutex_unlock(&lockdep_mutex);
 339   return id;
 340 }
 341
 342 int lockdep_locked(const char *name, int id, bool force_backtrace)
 343 {
 344   pthread_t p = pthread_self();
 345
 346   if (id < 0) id = lockdep_register(name);
 347
 348   pthread_mutex_lock(&lockdep_mutex);
 349   lockdep_dout(20) << "_locked " << name << dendl;
 350   if (force_backtrace || lockdep_force_backtrace())
 351     held[p][id] = new BackTrace(BACKTRACE_SKIP);
 352   else
 353     held[p][id] = 0;
 354   pthread_mutex_unlock(&lockdep_mutex);
 355   return id;
 356 }
 357
 358 int lockdep_will_unlock(const char *name, int id)
 359 {
 360   pthread_t p = pthread_self();
 361
 362   if (id < 0) {
 363     //id = lockdep_register(name);
 364     assert(id == -1);
 365     return id;
 366   }
 367
 368   pthread_mutex_lock(&lockdep_mutex);
 369   lockdep_dout(20) << "_will_unlock " << name << dendl;
 370
 371   // don't assert.. lockdep may be enabled at any point in time
 372   //assert(held.count(p));
 373   //assert(held[p].count(id));
 374
 375   delete held[p][id];
 376   held[p].erase(id);
 377   pthread_mutex_unlock(&lockdep_mutex);
 378   return id;
 379 }
 380
 381