l4/pkg/plr/server/src/fault_handlers/lock_observer.h

   1 #pragma once
   2
   3 /*
   4  * lock_observer.h --
   5  *
   6  *     Deterministic lock acquisition
   7  *
   8  * (c) 2012-2013 Björn Döbel <doebel@os.inf.tu-dresden.de>,
   9  *     economic rights: Technische Universität Dresden (Germany)
  10  * This file is part of TUD:OS and distributed under the terms of the
  11  * GNU General Public License 2.
  12  * Please see the COPYING-GPL-2 file for details.
  13  */
  14
  15 #include "observers.h"
  16 #include "../instruction_length.h"
  17
  18 #define EXTERNAL_DETERMINISM 0
  19 #define INTERNAL_DETERMINISM 1
  20
  21 EXTERN_C_BEGIN
  22 #include <l4/plr/pthread_rep.h>
  23 EXTERN_C_END
  24
  25 namespace Romain
  26 {
  27         /*
  28          * Wrapper for a pthread mutex.
  29          *
  30          * We delegate the actual locking (management, sleep handling) work to a
  31          * pthread mutex.
  32          *
  33          * Additionally, we add a wrapper that allows replicated threads to acquire
  34          * a recursive mutex even if the thread calling lock() the 2nd time is !=
  35          * the first lock acquirer.
  36          */
  37         class PThreadMutex
  38         {
  39                 pthread_mutex_t mtx;          // the mutex
  40                 sem_t           sem;
  41                 bool recursive;               // this is a recursive mtx?
  42                 Romain::Thread_group* owner;  // owning thread group
  43                 unsigned counter;             // recursive lock counter
  44
  45                 public:
  46
  47                 PThreadMutex(bool rec)
  48                         : recursive(rec), owner(0), counter(0)
  49                 {
  50                         /*
  51                          * Even if the mutex is recursive, we only create a
  52                          * simple one here, because we deal with lock recursion
  53                          * ourselves.
  54                          *
  55                          * (Actually, we cannot use pthread recursion, because it
  56                          * checks that the recursive call comes from the same thread,
  57                          * which may not be the case due to replication).
  58                          */
  59                         sem_init(&sem, 0, 1);
  60                         pthread_mutex_init(&mtx, 0);
  61                 }
  62
  63
  64                 /*
  65                  * Acquire mutex
  66                  */
  67                 int lock(Romain::Thread_group* tg)
  68                 {
  69                         pthread_mutex_lock(&mtx);
  70                         /*
  71                          * If this is recursive, only increment the counter.
  72                          */
  73                         if (recursive and counter) {
  74                                 if (tg != owner) {
  75                                         pthread_mutex_unlock(&mtx);
  76                                         return 1; // EPERM
  77                                 }
  78                                 counter++;
  79                                 pthread_mutex_unlock(&mtx);
  80                                 return 0;
  81                         }
  82
  83                         owner = tg;
  84                         counter++;
  85                         pthread_mutex_unlock(&mtx);
  86
  87                         return sem_wait(&sem);
  88                         //return pthread_mutex_lock(&mtx);
  89                 }
  90
  91
  92                 /*
  93                  * Release mutex
  94                  */
  95                 int unlock()
  96                 {
  97                         pthread_mutex_lock(&mtx);
  98                         counter--;
  99
 100                         if (recursive and (counter == 0)) {
 101                                 owner = 0;
 102                         }
 103                         pthread_mutex_unlock(&mtx);
 104
 105                         return sem_post(&sem);
 106                         //return pthread_mutex_unlock(&mtx);
 107                 }
 108         };
 109
 110
 111         struct LockFunction
 112         {
 113                 l4_addr_t   orig_address;
 114                 Breakpoint  *bp;
 115                 unsigned    function_id;
 116                 l4_addr_t   wrapper_address;
 117
 118
 119                 LockFunction()
 120                         : orig_address(0), bp(0), function_id(~0UL), wrapper_address(0)
 121                 { }
 122
 123
 124                 void configure(char const *configString, char const *alternativeString,
 125                                unsigned id)
 126                 {
 127                         DEBUG() << configString;
 128                         orig_address    = ConfigIntValue(configString);
 129 #if INTERNAL_DETERMINISM
 130                         wrapper_address = ConfigIntValue(alternativeString);
 131                         function_id     = id;
 132 #else
 133                         bp           = new Breakpoint(orig_address);
 134 #endif
 135                         DEBUG() << std::hex << orig_address;
 136                 }
 137
 138
 139                 void activate(Romain::App_instance *inst, Romain::App_model* am)
 140                 {
 141 #if INTERNAL_DETERMINISM
 142                         if (((function_id == pt_lock_id) or
 143                              (function_id == pt_unlock_id)) and
 144                                 (orig_address != ~0UL)) {
 145                                 /* Assumption: __pthread_(un)lock are called seldomly, so
 146                                  * we simply use the bp functionality here */
 147                                 bp = new Breakpoint(orig_address);
 148                                 bp->activate(inst, am);
 149                         } else {
 150                                 do_patch(am);
 151                         }
 152 #else
 153                         DEBUG() << lockID_to_str(function_id);
 154                         if ((orig_address == 0) or (orig_address == ~0))
 155                                 return;
 156                         bp = new Breakpoint(orig_address);
 157                         bp->activate(inst, am);
 158                         DEBUG() << "BP set.";
 159 #endif
 160                 }
 161
 162
 163                 void do_patch(Romain::App_model *am)
 164                 {
 165 #if INTERNAL_DETERMINISM
 166                         DEBUG() << "=============== Patching " << PURPLE << lockID_to_str(function_id)
 167                                 << NOCOLOR << " ===============";
 168
 169                         lock_info* lockinfo = reinterpret_cast<lock_info*>(am->lockinfo_local());
 170                         if (wrapper_address == ~0) {
 171                                 DEBUG() << BLUE << "   no known address" << NOCOLOR;
 172                                 return;
 173                         }
 174
 175                         unsigned char *instructionBuffer = lockinfo->trampolines + function_id * 32;
 176                         memset(instructionBuffer, 0xff, 32);
 177                         instructionBuffer[0] = 0xCC; // INT3
 178                         instructionBuffer[1] = 0xC3; // RET
 179
 180                         return;
 181
 182                         /* XXX: Dead code below ... at least for now.  -> This is how we
 183                          *      would patch the binary if we did not have access to the
 184                          *      pthread implementation.
 185                          */
 186
 187                         DEBUG() << "Patching function at " << std::hex << orig_address;
 188
 189                         l4_addr_t func_local = am->rm()->remote_to_local(orig_address, 0);
 190                         DEBUG() << "function @ " << std::hex << orig_address
 191                                 << " = " << func_local;
 192                         DEBUG() << "Wrapper @ " << std::hex << wrapper_address;
 193
 194                         DEBUG() << "Original code:";
 195                         Romain::dump_mem((void*)func_local, 20);
 196
 197                         /*
 198                          * Patch the target code. We overwrite the first bytes of the
 199                          * function with a CALL into our handler function. Later, we make
 200                          * the handler return so that it executes the original code.
 201                          *
 202                          * To achieve this, we copy the function's first N instructions
 203                          * into a separate buffer. The buffer is then extended with a
 204                          * jump back to the original (non-overwritten) code. For the jump
 205                          * back, we use a jmp through EAX, hence we need 2 additional
 206                          * instructions to save and restore EAX' original value.
 207                          *
 208                          * Hence, 6 bytes of code to be replaced in the original code
 209                          * (5 for the CALL, 1 for PUSHing EAX).
 210                          */
 211
 212                         unsigned bytes = 0;
 213                         l4_addr_t ip   = func_local;
 214                         while (bytes < 6) {
 215                                 Romain::InstructionPrinter(ip, 0);
 216                                 unsigned len = mlde32((void*)ip);
 217                                 bytes += len;
 218                                 ip += len;
 219                         }
 220
 221                         DEBUG() << "Need to store away " << bytes << " bytes. Then return to 0x"
 222                                 << std::hex << orig_address + bytes;
 223
 224 #if 0
 225                         /*
 226                          * -----------------------------------------------------
 227                          *  Create return code in the trampoline page
 228                          * -----------------------------------------------------
 229                          */
 230                         // POP EAX -> this reg was used by wrapper fn to determine
 231                         // where to jump to
 232                         instructionBuffer[0] = 0x58;
 233                         // copy the instructions into buffer
 234                         memcpy(instructionBuffer + 1, (void*)func_local, bytes);
 235                         // + 1 byte:  PUSH eax
 236                         instructionBuffer[bytes + 1] = 0x50;
 237                         // + 5 bytes: MOV eax, $retaddr
 238                         instructionBuffer[bytes + 2] = 0xB8;
 239                         /* Returning to the instruction _after_ our patched JMP */
 240                         *(l4_addr_t*)&instructionBuffer[bytes+3] = orig_address + 5;
 241                         // + 2 bytes: JMP [eax]
 242                         instructionBuffer[bytes + 7] = 0xFF; // 2 bytes: jmp *%eax
 243                         instructionBuffer[bytes + 8] = 0xE0;
 244                         DEBUG() << "Return buffer: ";
 245                         Romain::dump_mem(instructionBuffer, 32, 24);
 246 #endif
 247
 248                         /*
 249                          * -----------------------------------------------------
 250                          *  Patch the target function to jump to our wrapper
 251                          * -----------------------------------------------------
 252                          */
 253                         DEBUG() << "Patching original code... (ibuf @ " << std::hex
 254                                 << (void*)instructionBuffer << ")";
 255                         memset((void*)func_local, 0x90, bytes);
 256                         // 5 bytes: JMP [wrapper_func]
 257                         *((char*)func_local   ) = 0xE9;
 258
 259                         int offset = wrapper_address - orig_address - 5;
 260                         DEBUG() << "Offset: " << std::hex << wrapper_address
 261                                 << " - " << orig_address << " = " << offset;
 262                         *(l4_addr_t*)(func_local + 1) = offset;
 263 #if 0
 264                         // 1 byte: POP eax
 265                         *((char*)func_local + 5) = 0x58;
 266 #endif
 267                         DEBUG() << "Patched function entry: ";
 268                         Romain::dump_mem((char*)func_local, 32, 24);
 269
 270
 271 #endif
 272                 }
 273         };
 274
 275
 276         /*
 277          * Observer responsible for making multithreaded lock acquisition
 278          * deterministic. We achieve this by placing breakpoints on the
 279          * following well-known pthread functions:
 280          *
 281          * __pthread_lock    (internal pthread use)
 282          * __pthread_unlock  (internal pthread use)
 283          * pthread_mutex_init
 284          * pthread_mutex_lock
 285          * pthread_mutex_unlock
 286          *
 287          * Unsupported so far:
 288          *
 289          * pthread_mutex_destroy
 290          * pthread_mutex_trylock
 291          * pthread_mutex_timedlock
 292          *
 293          * Then we intercept all calls to these functions and emulate them
 294          * ourselves. As the observer is only called after all replicas
 295          * agreed to grab a lock, we are sure that we can immediately try
 296          * to grab the lock and cannot see interfering replicas from other threads.
 297          *
 298          * However, we still have a race when two or more thread groups
 299          * successfully decide to acquire the lock. We leave resolution of these
 300          * issues to the underlying pthread implementation. The whole system's
 301          * behavior nevertheless becomes deterministic, because we only need to
 302          * make sure that for this single run we see the same ordering of lock
 303          * acquisitions (and this is ensured by using the pthread lock).
 304          */
 305         class PThreadLock_priv : public Romain::PThreadLockObserver
 306         {
 307                 LockFunction _functions[pt_max_wrappers];
 308                 std::map<l4_umword_t, PThreadMutex*> _locks;
 309                 Romain::App_model::Dataspace         _lip_ds;
 310                 l4_addr_t                            _lip_local;
 311                 pthread_mutex_t                      _tablemtx;
 312
 313                 unsigned /* Internal determinism counters */
 314                              det_lock_count,   // counter: det_lock
 315                          det_unlock_count, // counter: det_unlock
 316                          /* External determinism counters: */
 317                          mtx_lock_count,   // counter: pthread_mutex_lock
 318                          mtx_unlock_count, // counter: pthread_mutex_unlock
 319                          pt_lock_count,    // counter: __pthread_lock
 320                          pt_unlock_count,  // counter: __pthread_unlock
 321                          /* Global counter */
 322                          ignore_count,     // counter: call ignored
 323                          total_count;      // counter: total invocations
 324
 325                 PThreadMutex* lookup_or_fail(unsigned addr)
 326                 {
 327                         pthread_mutex_lock(&_tablemtx);
 328                         PThreadMutex* r = _locks[addr];
 329                         if (!r) {
 330                                 ERROR() << "Called with uninitialized mutex?";
 331                                 enter_kdebug("op on uninitialized mutex");
 332                         }
 333                         pthread_mutex_unlock(&_tablemtx);
 334                         return r;
 335                 }
 336
 337
 338                 PThreadMutex* lookup_or_create(unsigned addr, bool init_locked = false,
 339                                                Romain::Thread_group* tg = 0)
 340                 {
 341                         pthread_mutex_lock(&_tablemtx);
 342                         PThreadMutex* mtx = _locks[addr];
 343                         if (!mtx) {
 344                                 mtx           = new PThreadMutex(false);
 345                                 _locks[addr]  = mtx;
 346
 347                                 if (init_locked) {
 348                                         mtx->lock(tg);
 349                                 }
 350                         }
 351                         pthread_mutex_unlock(&_tablemtx);
 352                         return mtx;
 353                 }
 354
 355
 356                 void det_lock(Romain::App_instance* inst,
 357                               Romain::App_thread*   t,
 358                               Romain::Thread_group* tg,
 359                               Romain::App_model*    am)
 360                 {
 361                         l4_addr_t stackaddr = am->rm()->remote_to_local(t->vcpu()->r()->sp, inst->id());
 362                         l4_addr_t lock      = *(l4_addr_t*)(stackaddr + 4);
 363                         DEBUG() << "\033[35mLOCK @ \033[0m" << std::hex << lock;
 364                         lookup_or_create(lock, true, tg)->lock(tg);
 365                         //enter_kdebug("det_lock");
 366                 }
 367
 368
 369                 void det_unlock(Romain::App_instance* inst,
 370                                 Romain::App_thread*   t,
 371                                 Romain::Thread_group* tg,
 372                                 Romain::App_model*    am)
 373                 {
 374                         l4_addr_t stackaddr = am->rm()->remote_to_local(t->vcpu()->r()->sp, inst->id());
 375                         l4_addr_t lock      = *(l4_addr_t*)(stackaddr + 4);
 376                         DEBUG() << "\033[35mUNLOCK @ \033[0m" << std::hex << lock;
 377
 378                         pthread_mutex_lock(&_tablemtx);
 379                         PThreadMutex* m = _locks[lock];
 380                         if (!m) {
 381                                 /* This may actually happen! The unlocker is simply faster sending the
 382                                  * notification than the locker is in sending his wakeup. Hence,
 383                                  * we need to potentially create the respective lock here.
 384                                  */
 385                                 l4_umword_t mtx_kind_ptr = am->rm()->remote_to_local(lock + 12, inst->id());
 386                                 m            = new PThreadMutex(*(l4_umword_t*)mtx_kind_ptr == PTHREAD_MUTEX_RECURSIVE_NP);
 387                                 _locks[lock] = m;
 388                         }
 389                         pthread_mutex_unlock(&_tablemtx);
 390                         m->unlock();
 391                         //enter_kdebug("det_unlock");
 392                 }
 393
 394
 395                 void attach_lock_info_page(Romain::App_model *am);
 396
 397
 398                 public:
 399                 PThreadLock_priv()
 400                         : det_lock_count(0), det_unlock_count(0),
 401                           mtx_lock_count(0), mtx_unlock_count(0),
 402                           pt_lock_count(0), pt_unlock_count(0),
 403                           ignore_count(0), total_count(0)
 404                 {
 405                         pthread_mutex_init(&_tablemtx, 0);
 406 #if 0
 407                         _functions[mutex_init_id].configure("threads:mutex_init",
 408                                                             "threads:mutex_init_rep",
 409                                                             mutex_init_id);
 410 #endif
 411                         _functions[mutex_lock_id].configure("threads:mutex_lock",
 412                                                             "threads:mutex_lock_rep",
 413                                                             mutex_lock_id);
 414                         _functions[mutex_unlock_id].configure("threads:mutex_unlock",
 415                                                               "threads:mutex_unlock_rep",
 416                                                               mutex_unlock_id);
 417 #if 1
 418                         _functions[pt_lock_id].configure("threads:lock",
 419                                                          "threads:lock_rep",
 420                                                          pt_lock_id);
 421                         _functions[pt_unlock_id].configure("threads:unlock",
 422                                                            "threads:unlock_rep",
 423                                                            pt_unlock_id);
 424 #endif
 425                 }
 426
 427                 DECLARE_OBSERVER("pthread_lock");
 428
 429                 void lock(Romain::App_instance* inst, Romain::App_thread* thread,
 430                           Romain::Thread_group* group, Romain::App_model* model);
 431                 void unlock(Romain::App_instance* inst, Romain::App_thread* thread,
 432                             Romain::Thread_group* group, Romain::App_model* model);
 433
 434                 void mutex_init(Romain::App_instance* inst, Romain::App_thread* thread,
 435                                 Romain::Thread_group* group, Romain::App_model* model);
 436                 void mutex_lock(Romain::App_instance* inst, Romain::App_thread* thread,
 437                                 Romain::Thread_group* group, Romain::App_model* model);
 438                 void mutex_unlock(Romain::App_instance* inst, Romain::App_thread* thread,
 439                                   Romain::Thread_group* group, Romain::App_model* model);
 440         };
 441 }