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 function_id == pt_unlock_id) {
 143                                 /* Assumption: __pthread_(un)lock are called seldomly, so
 144                                  * we simply use the bp functionality here */
 145                                 bp = new Breakpoint(orig_address);
 146                                 bp->activate(inst, am);
 147                         } else {
 148                                 do_patch(am);
 149                         }
 150 #else
 151                         DEBUG() << lockID_to_str(function_id);
 152                         if ((orig_address == 0) or (orig_address == ~0))
 153                                 return;
 154                         bp = new Breakpoint(orig_address);
 155                         bp->activate(inst, am);
 156                         DEBUG() << "BP set.";
 157 #endif
 158                 }
 159
 160
 161                 void do_patch(Romain::App_model *am)
 162                 {
 163 #if INTERNAL_DETERMINISM
 164                         DEBUG() << "=============== Patching " << PURPLE << lockID_to_str(function_id)
 165                                 << NOCOLOR << " ===============";
 166
 167                         lock_info* lockinfo = reinterpret_cast<lock_info*>(am->lockinfo_local());
 168                         if (wrapper_address == ~0)
 169                                 return;
 170
 171                         unsigned char *instructionBuffer = lockinfo->trampolines + function_id * 32;
 172                         memset(instructionBuffer, 0xff, 32);
 173                         instructionBuffer[0] = 0xCC; // INT3
 174                         instructionBuffer[1] = 0xC3; // RET
 175
 176                         return;
 177
 178                         /* XXX: Dead code below ... at least for now.  -> This is how we
 179                          *      would patch the binary if we did not have access to the
 180                          *      pthread implementation.
 181                          */
 182
 183                         DEBUG() << "Patching function at " << std::hex << orig_address;
 184
 185                         l4_addr_t func_local = am->rm()->remote_to_local(orig_address, 0);
 186                         DEBUG() << "function @ " << std::hex << orig_address
 187                                 << " = " << func_local;
 188                         DEBUG() << "Wrapper @ " << std::hex << wrapper_address;
 189
 190                         DEBUG() << "Original code:";
 191                         Romain::dump_mem((void*)func_local, 20);
 192
 193                         /*
 194                          * Patch the target code. We overwrite the first bytes of the
 195                          * function with a CALL into our handler function. Later, we make
 196                          * the handler return so that it executes the original code.
 197                          *
 198                          * To achieve this, we copy the function's first N instructions
 199                          * into a separate buffer. The buffer is then extended with a
 200                          * jump back to the original (non-overwritten) code. For the jump
 201                          * back, we use a jmp through EAX, hence we need 2 additional
 202                          * instructions to save and restore EAX' original value.
 203                          *
 204                          * Hence, 6 bytes of code to be replaced in the original code
 205                          * (5 for the CALL, 1 for PUSHing EAX).
 206                          */
 207
 208                         unsigned bytes = 0;
 209                         l4_addr_t ip   = func_local;
 210                         while (bytes < 6) {
 211                                 Romain::InstructionPrinter(ip, 0);
 212                                 unsigned len = mlde32((void*)ip);
 213                                 bytes += len;
 214                                 ip += len;
 215                         }
 216
 217                         DEBUG() << "Need to store away " << bytes << " bytes. Then return to 0x"
 218                                 << std::hex << orig_address + bytes;
 219
 220 #if 0
 221                         /*
 222                          * -----------------------------------------------------
 223                          *  Create return code in the trampoline page
 224                          * -----------------------------------------------------
 225                          */
 226                         // POP EAX -> this reg was used by wrapper fn to determine
 227                         // where to jump to
 228                         instructionBuffer[0] = 0x58;
 229                         // copy the instructions into buffer
 230                         memcpy(instructionBuffer + 1, (void*)func_local, bytes);
 231                         // + 1 byte:  PUSH eax
 232                         instructionBuffer[bytes + 1] = 0x50;
 233                         // + 5 bytes: MOV eax, $retaddr
 234                         instructionBuffer[bytes + 2] = 0xB8;
 235                         /* Returning to the instruction _after_ our patched JMP */
 236                         *(l4_addr_t*)&instructionBuffer[bytes+3] = orig_address + 5;
 237                         // + 2 bytes: JMP [eax]
 238                         instructionBuffer[bytes + 7] = 0xFF; // 2 bytes: jmp *%eax
 239                         instructionBuffer[bytes + 8] = 0xE0;
 240                         DEBUG() << "Return buffer: ";
 241                         Romain::dump_mem(instructionBuffer, 32, 24);
 242 #endif
 243
 244                         /*
 245                          * -----------------------------------------------------
 246                          *  Patch the target function to jump to our wrapper
 247                          * -----------------------------------------------------
 248                          */
 249                         DEBUG() << "Patching original code... (ibuf @ " << std::hex
 250                                 << (void*)instructionBuffer << ")";
 251                         memset((void*)func_local, 0x90, bytes);
 252                         // 5 bytes: JMP [wrapper_func]
 253                         *((char*)func_local   ) = 0xE9;
 254
 255                         int offset = wrapper_address - orig_address - 5;
 256                         DEBUG() << "Offset: " << std::hex << wrapper_address
 257                                 << " - " << orig_address << " = " << offset;
 258                         *(l4_addr_t*)(func_local + 1) = offset;
 259 #if 0
 260                         // 1 byte: POP eax
 261                         *((char*)func_local + 5) = 0x58;
 262 #endif
 263                         DEBUG() << "Patched function entry: ";
 264                         Romain::dump_mem((char*)func_local, 32, 24);
 265
 266
 267 #endif
 268                 }
 269         };
 270
 271
 272         /*
 273          * Observer responsible for making multithreaded lock acquisition
 274          * deterministic. We achieve this by placing breakpoints on the
 275          * following well-known pthread functions:
 276          *
 277          * __pthread_lock    (internal pthread use)
 278          * __pthread_unlock  (internal pthread use)
 279          * pthread_mutex_init
 280          * pthread_mutex_lock
 281          * pthread_mutex_unlock
 282          *
 283          * Unsupported so far:
 284          *
 285          * pthread_mutex_destroy
 286          * pthread_mutex_trylock
 287          * pthread_mutex_timedlock
 288          *
 289          * Then we intercept all calls to these functions and emulate them
 290          * ourselves. As the observer is only called after all replicas
 291          * agreed to grab a lock, we are sure that we can immediately try
 292          * to grab the lock and cannot see interfering replicas from other threads.
 293          *
 294          * However, we still have a race when two or more thread groups
 295          * successfully decide to acquire the lock. We leave resolution of these
 296          * issues to the underlying pthread implementation. The whole system's
 297          * behavior nevertheless becomes deterministic, because we only need to
 298          * make sure that for this single run we see the same ordering of lock
 299          * acquisitions (and this is ensured by using the pthread lock).
 300          */
 301         class PThreadLock_priv : public Romain::PThreadLockObserver
 302         {
 303                 LockFunction _functions[pt_max_wrappers];
 304                 std::map<l4_umword_t, PThreadMutex*> _locks;
 305                 Romain::App_model::Dataspace         _lip_ds;
 306                 l4_addr_t                            _lip_local;
 307                 pthread_mutex_t                      _tablemtx;
 308
 309                 unsigned /* Internal determinism counters */
 310                              det_lock_count,   // counter: det_lock
 311                          det_unlock_count, // counter: det_unlock
 312                          /* External determinism counters: */
 313                          mtx_lock_count,   // counter: pthread_mutex_lock
 314                          mtx_unlock_count, // counter: pthread_mutex_unlock
 315                          pt_lock_count,    // counter: __pthread_lock
 316                          pt_unlock_count,  // counter: __pthread_unlock
 317                          /* Global counter */
 318                          ignore_count,     // counter: call ignored
 319                          total_count;      // counter: total invocations
 320
 321                 PThreadMutex* lookup_or_fail(unsigned addr)
 322                 {
 323                         pthread_mutex_lock(&_tablemtx);
 324                         PThreadMutex* r = _locks[addr];
 325                         if (!r) {
 326                                 ERROR() << "Called with uninitialized mutex?";
 327                                 enter_kdebug("op on uninitialized mutex");
 328                         }
 329                         pthread_mutex_unlock(&_tablemtx);
 330                         return r;
 331                 }
 332
 333
 334                 PThreadMutex* lookup_or_create(unsigned addr, bool init_locked = false,
 335                                                Romain::Thread_group* tg = 0)
 336                 {
 337                         pthread_mutex_lock(&_tablemtx);
 338                         PThreadMutex* mtx = _locks[addr];
 339                         if (!mtx) {
 340                                 mtx           = new PThreadMutex(false);
 341                                 _locks[addr]  = mtx;
 342
 343                                 if (init_locked) {
 344                                         mtx->lock(tg);
 345                                 }
 346                         }
 347                         pthread_mutex_unlock(&_tablemtx);
 348                         return mtx;
 349                 }
 350
 351
 352                 void det_lock(Romain::App_instance* inst,
 353                               Romain::App_thread*   t,
 354                               Romain::Thread_group* tg,
 355                               Romain::App_model*    am)
 356                 {
 357                         l4_addr_t stackaddr = am->rm()->remote_to_local(t->vcpu()->r()->sp, inst->id());
 358                         l4_addr_t lock      = *(l4_addr_t*)(stackaddr + 4);
 359                         DEBUG() << "\033[35mLOCK @ \033[0m" << std::hex << lock;
 360                         lookup_or_create(lock, true, tg)->lock(tg);
 361                         //enter_kdebug("det_lock");
 362                 }
 363
 364
 365                 void det_unlock(Romain::App_instance* inst,
 366                                 Romain::App_thread*   t,
 367                                 Romain::Thread_group* tg,
 368                                 Romain::App_model*    am)
 369                 {
 370                         l4_addr_t stackaddr = am->rm()->remote_to_local(t->vcpu()->r()->sp, inst->id());
 371                         l4_addr_t lock      = *(l4_addr_t*)(stackaddr + 4);
 372                         DEBUG() << "\033[35mUNLOCK @ \033[0m" << std::hex << lock;
 373
 374                         pthread_mutex_lock(&_tablemtx);
 375                         PThreadMutex* m = _locks[lock];
 376                         if (!m) {
 377                                 /* This may actually happen! The unlocker is simply faster sending the
 378                                  * notification than the locker is in sending his wakeup. Hence,
 379                                  * we need to potentially create the respective lock here.
 380                                  */
 381                                 l4_umword_t mtx_kind_ptr = am->rm()->remote_to_local(lock + 12, inst->id());
 382                                 m            = new PThreadMutex(*(l4_umword_t*)mtx_kind_ptr == PTHREAD_MUTEX_RECURSIVE_NP);
 383                                 _locks[lock] = m;
 384                         }
 385                         pthread_mutex_unlock(&_tablemtx);
 386                         m->unlock();
 387                         //enter_kdebug("det_unlock");
 388                 }
 389
 390
 391                 void attach_lock_info_page(Romain::App_model *am);
 392
 393
 394                 public:
 395                 PThreadLock_priv()
 396                         : det_lock_count(0), det_unlock_count(0),
 397                           mtx_lock_count(0), mtx_unlock_count(0),
 398                           pt_lock_count(0), pt_unlock_count(0),
 399                           ignore_count(0), total_count(0)
 400                 {
 401                         pthread_mutex_init(&_tablemtx, 0);
 402 #if 0
 403                         _functions[mutex_init_id].configure("threads:mutex_init",
 404                                                             "threads:mutex_init_rep",
 405                                                             mutex_init_id);
 406 #endif
 407                         _functions[mutex_lock_id].configure("threads:mutex_lock",
 408                                                             "threads:mutex_lock_rep",
 409                                                             mutex_lock_id);
 410                         _functions[mutex_unlock_id].configure("threads:mutex_unlock",
 411                                                               "threads:mutex_unlock_rep",
 412                                                               mutex_unlock_id);
 413 #if 1
 414                         _functions[pt_lock_id].configure("threads:lock",
 415                                                          "threads:lock_rep",
 416                                                          pt_lock_id);
 417                         _functions[pt_unlock_id].configure("threads:unlock",
 418                                                            "threads:unlock_rep",
 419                                                            pt_unlock_id);
 420 #endif
 421                 }
 422
 423                 DECLARE_OBSERVER("pthread_lock");
 424
 425                 void lock(Romain::App_instance* inst, Romain::App_thread* thread,
 426                           Romain::Thread_group* group, Romain::App_model* model);
 427                 void unlock(Romain::App_instance* inst, Romain::App_thread* thread,
 428                             Romain::Thread_group* group, Romain::App_model* model);
 429
 430                 void mutex_init(Romain::App_instance* inst, Romain::App_thread* thread,
 431                                 Romain::Thread_group* group, Romain::App_model* model);
 432                 void mutex_lock(Romain::App_instance* inst, Romain::App_thread* thread,
 433                                 Romain::Thread_group* group, Romain::App_model* model);
 434                 void mutex_unlock(Romain::App_instance* inst, Romain::App_thread* thread,
 435                                   Romain::Thread_group* group, Romain::App_model* model);
 436         };
 437 }