vmkit/lib/vmkit/CommonThread/ObjectLocks.cpp

//===--------- ObjectLocks.cpp - Object-based locks -----------------------===//
//
//                     The VMKit project
//
// This file is distributed under the University of Illinois Open Source 
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//

#include <cassert>

#include "vmkit/Cond.h"
#include "vmkit/Locks.h"
#include "vmkit/ObjectLocks.h"
#include "vmkit/Thread.h"
#include "vmkit/VirtualMachine.h"
#include "VmkitGC.h"
#include <cerrno>
#include <sys/time.h>
#include <pthread.h>

#include "../../j3/VMCore/JavaObject.h"
#include "../../j3/VMCore/JavaClass.h"
#include "../../j3/VMCore/UTF8.h"

namespace vmkit {

void ThinLock::overflowThinLock(gc* object, LockSystem& table) {
  llvm_gcroot(object, 0);
  FatLock* obj = table.allocate(object);
  word_t ID = obj->getID();
  // 1 because we start at 0, and 1 for this lock request.
  obj->acquireAll(object, (ThinCountMask >> ThinCountShift) + 2);
  word_t oldValue = 0;
  word_t newValue = 0;
  word_t yieldedValue = 0;
  do {
    oldValue = object->header();
    newValue = obj->getID() | (oldValue & NonLockBitsMask);
    assert(obj->associatedObject == object);
    yieldedValue = __sync_val_compare_and_swap(&(object->header()), oldValue, newValue);
  } while (((object->header()) & ~NonLockBitsMask) != ID);
  assert(obj->associatedObject == object);
}
 
/// initialise - Initialise the value of the lock.
///
#if 0
// Disable fat lock deflation code in ObjectLocks.cpp
// Fixes occasional assertion failure when running on multi-core machine.
void ThinLock::removeFatLock(FatLock* fatLock, LockSystem& table) {
  gc* object = fatLock->associatedObject;
  llvm_gcroot(object, 0);
  word_t ID;
  word_t oldValue = 0;
  word_t newValue = 0;
  word_t yieldedValue = 0;

  ID = fatLock->getID();
  do {
    oldValue = object->header();
    newValue = oldValue & NonLockBitsMask;
    yieldedValue = __sync_val_compare_and_swap(&object->header(), oldValue, newValue);
  } while (oldValue != yieldedValue);
  assert((oldValue & NonLockBitsMask) != ID);
  fatLock->associatedObject = NULL;
}
#endif
  
FatLock* ThinLock::changeToFatlock(gc* object, LockSystem& table) {
  llvm_gcroot(object, 0);
  if (!(object->header() & FatMask)) {
    FatLock* obj = table.allocate(object);
    uint32 count = (object->header() & ThinCountMask) >> ThinCountShift;
    obj->acquireAll(object, count + 1);
    word_t oldValue = 0;
    word_t newValue = 0;
    word_t yieldedValue = 0;
    word_t ID = obj->getID();
    do {
      oldValue = object->header();
      newValue = ID | (oldValue & NonLockBitsMask);
      assert(obj->associatedObject == object);
      yieldedValue = __sync_val_compare_and_swap(&(object->header()), oldValue, newValue);
    } while (((object->header()) & ~NonLockBitsMask) != ID);
    return obj;
  } else {
    FatLock* res = table.getFatLockFromID(object->header());
    assert(res && "Lock deallocated while held.");
    assert(res->associatedObject == object);
    return res;
  }
}

void printDebugMessage(gc* object, LockSystem& table) {
  gc* assObj = NULL;
  llvm_gcroot(assObj, 0);
  llvm_gcroot(object, 0);
  fprintf(stderr,
      "WARNING: [%p] has been waiting really long for %p (header = %p)\n",
      (void*)vmkit::Thread::get(),
      (void*)object,
      (void*)object->header());
  FatLock* obj = table.getFatLockFromID(object->header());
  if (obj != NULL) {
    fprintf(stderr,
        "WARNING: [%p] is waiting on fatlock %p. "
        "Its associated object is %p. The owner is %p\n",
        (void*)vmkit::Thread::get(),
        (void*)obj,
        (void*)(assObj = obj->getAssociatedObject()),
        (void*)obj->owner());
  }
}

void ThinLock::acquire(gc* object, LockSystem& table) {
  llvm_gcroot(object, 0);
  uint64_t id = vmkit::Thread::get()->getThreadID();
  word_t oldValue = 0;
  word_t newValue = 0;
  word_t yieldedValue = 0;

  if ((object->header() & System::GetThreadIDMask()) == id) {
    assert(owner(object, table) && "Inconsistent lock");
    if ((object->header() & ThinCountMask) != ThinCountMask) {
      uint32 count = object->header() & ThinCountMask;
      do {
        oldValue = object->header();
        newValue = oldValue + ThinCountAdd;
        yieldedValue = __sync_val_compare_and_swap(&(object->header()), oldValue, newValue);
      } while ((object->header() & ThinCountMask) == count);
    } else {
      overflowThinLock(object, table);
    }
    assert(owner(object, table) && "Not owner after quitting acquire!");
    return;
  }

  do {
    oldValue = object->header() & NonLockBitsMask;
    newValue = oldValue | id;
    yieldedValue = __sync_val_compare_and_swap(&(object->header()), oldValue, newValue);
  } while ((object->header() & ~NonLockBitsMask) == 0);

  if (((object->header()) & ~NonLockBitsMask) == id) {
    assert(owner(object, table) && "Not owner after quitting acquire!");
    return;
  }

  // Simple counter to lively diagnose possible dead locks in this code.
  int counter = 0;  
  while (true) {
    if (object->header() & FatMask) {
      FatLock* obj = table.getFatLockFromID(object->header());
      if (obj != NULL) {
        if (obj->acquire(object, table)) {
          assert((object->header() & FatMask) && "Inconsistent lock");
          assert((table.getFatLockFromID(object->header()) == obj) && "Inconsistent lock");
          assert(owner(object, table) && "Not owner after acquiring fat lock!");
          break;
        }
      }
    }
   
    counter++;
    if (counter == 1000) printDebugMessage(object, table);

    while (object->header() & ~NonLockBitsMask) {
      if (object->header() & FatMask) {
        break;
      } else {
        vmkit::Thread::yield();
      }
    }
    
    if ((object->header() & ~NonLockBitsMask) == 0) {
      FatLock* obj = table.allocate(object);
      obj->internalLock.lock();
      do {
        oldValue = object->header() & NonLockBitsMask;
        newValue = oldValue | obj->getID();
        assert(obj->associatedObject == object);
        yieldedValue = __sync_val_compare_and_swap(&object->header(), oldValue, newValue);
      } while ((object->header() & ~NonLockBitsMask) == 0);

      if ((getFatLock(object, table) != obj)) {
        assert((object->header() & ~NonLockBitsMask) != obj->getID());
        obj->internalLock.unlock();
        table.deallocate(obj);
      } else {
        assert((object->header() & ~NonLockBitsMask) == obj->getID());
        assert(owner(object, table) && "Inconsistent lock");
        break;
      }
    }
  }

  assert(owner(object, table) && "Not owner after quitting acquire!");
}

/// release - Release the lock.
void ThinLock::release(gc* object, LockSystem& table, vmkit::Thread* ownerThread) {
  llvm_gcroot(object, 0);
  if (!ownerThread) ownerThread = vmkit::Thread::get();
  assert((getOwner(object, table) == ownerThread) && "Not owner when entering release!");
  uint64 id = ownerThread->getThreadID();
  word_t oldValue = 0;
  word_t newValue = 0;
  word_t yieldedValue = 0;

  if ((object->header() & ~NonLockBitsMask) == id) {
    do {
      oldValue = object->header();
      newValue = oldValue & NonLockBitsMask;
      yieldedValue = __sync_val_compare_and_swap(&object->header(), oldValue, newValue);
    } while ((object->header() & ~NonLockBitsMask) == id);
  } else if (object->header() & FatMask) {
    FatLock* obj = table.getFatLockFromID(object->header());
    assert(obj && "Lock deallocated while held.");
    obj->release(object, table, ownerThread);
  } else {
    assert(((object->header() & ThinCountMask) > 0) && "Inconsistent state");
    uint32 count = (object->header() & ThinCountMask);
    do {
      oldValue = object->header();
      newValue = oldValue - ThinCountAdd;
      yieldedValue = __sync_val_compare_and_swap(&(object->header()), oldValue, newValue);
    } while ((object->header() & ThinCountMask) == count);
  }

}

/// owner - Returns true if the current thread is the owner of this object's
/// lock.
bool ThinLock::owner(gc* object, LockSystem& table) {
  llvm_gcroot(object, 0);
  if (object->header() & FatMask) {
    FatLock* obj = table.getFatLockFromID(object->header());
    if (obj != NULL) return obj->owner();
  } else {
  	bool res = false;
    uint64 id = vmkit::Thread::get()->getThreadID();
    res = ((object->header() & System::GetThreadIDMask()) == id);
    if (res) return true;
  }
  return false;
}

vmkit::Thread* ThinLock::getOwner(gc* object, LockSystem& table)
{
  llvm_gcroot(object, 0);
  if (object->header() & FatMask) {
	FatLock* obj = table.getFatLockFromID(object->header());
	return (!obj) ? NULL : obj->getOwner();
  } else {
	uint64_t threadID = object->header() & System::GetThreadIDMask();
	return vmkit::Thread::getByID(threadID);
  }
}

/// getFatLock - Get the fat lock is the lock is a fat lock, 0 otherwise.
FatLock* ThinLock::getFatLock(gc* object, LockSystem& table) {
  llvm_gcroot(object, 0);
  if (object->header() & FatMask) {
    return table.getFatLockFromID(object->header());
  } else {
    return NULL;
  }
}

void FatLock::acquireAll(gc* object, word_t nb) {
  llvm_gcroot(object, 0);
  assert(associatedObject == object);
  internalLock.lockAll(nb);
}

bool FatLock::owner() {
  return internalLock.selfOwner();
}
 
vmkit::Thread* FatLock::getOwner() {
  return internalLock.getOwner();
}
  
FatLock::FatLock(uint32_t i, gc* a) :
	associatedObjectDead(false)
{
  llvm_gcroot(a, 0);
  assert(a != NULL);
  firstThread = NULL;
  index = i;
  setAssociatedObject(a);
  waitingThreads = 0;
  lockingThreads = 0;
  nextFreeLock = NULL;
}

word_t FatLock::getID() {
  return (index << ThinLock::NonLockBits) | ThinLock::FatMask;
}

void FatLock::release(gc* obj, LockSystem& table, vmkit::Thread* ownerThread) {
  llvm_gcroot(obj, 0);
  assert(associatedObject && "No associated object when releasing");
  assert(associatedObject == obj && "Mismatch object in lock");
#if 0
  // Disable fat lock deflation code in ObjectLocks.cpp
  // Fixes occasional assertion failure when running on multi-core machine.
  if (!waitingThreads && !lockingThreads &&
      internalLock.recursionCount() == 1) {
    vmkit::ThinLock::removeFatLock(this, table);
    table.deallocate(this);
  }
#endif
  internalLock.unlock(ownerThread);
}

/// acquire - Acquires the internalLock.
///
bool FatLock::acquire(gc* obj, LockSystem& table) {
  llvm_gcroot(obj, 0);
    
  spinLock.lock();
  lockingThreads++;
  spinLock.unlock();
    
  internalLock.lock();
    
  spinLock.lock();
  lockingThreads--;
  spinLock.unlock();

  if (this->associatedObjectIsDead()) {
    internalLock.unlock();

//	if (lockingThreads == 0)
//      table.deallocate(this);

	word_t methodIP = System::GetCallerAddress();
	methodIP = System::GetIPFromCallerAddress(methodIP);
    Thread::get()->throwNullPointerException(methodIP);
  }

  if (associatedObject != obj) {
    internalLock.unlock();
    return false;
  }
  assert(obj->header() & ThinLock::FatMask);
  assert((obj->header() & ~ThinLock::NonLockBitsMask) == getID());
  return true;
}


void LockSystem::deallocate(FatLock* lock) {
  lock->associatedObject = NULL;
  threadLock.lock();
  lock->nextFreeLock = freeLock;
  freeLock = lock;
  threadLock.unlock();
}
  
LockSystem::LockSystem(vmkit::BumpPtrAllocator& all) : allocator(all) {
  assert(ThinLock::ThinCountMask > 0);
  LockTable = (FatLock* **)
    allocator.Allocate(GlobalSize * sizeof(FatLock**), "Global LockTable");
  LockTable[0] = (FatLock**)
    allocator.Allocate(IndexSize * sizeof(FatLock*), "Index LockTable");
  currentIndex = 0;
  freeLock = NULL;
}

FatLock* LockSystem::allocate(gc* obj) {  
  llvm_gcroot(obj, 0); 
  FatLock* res = 0;
  threadLock.lock();

  // Try the freeLock list.
  if (freeLock != NULL) {
    res = freeLock;
    freeLock = res->nextFreeLock;
    res->nextFreeLock = 0;
    assert(res->associatedObject == NULL);
    threadLock.unlock();
    res->setAssociatedObject(obj);
  } else { 
    // Get an index.
    uint32_t index = currentIndex++;
    if (index == MaxLocks) {
      fprintf(stderr, "Ran out of space for allocating locks");
      abort();
    }
  
    FatLock** &tab = LockTable[index >> BitIndex];
  
    VirtualMachine* vm = vmkit::Thread::get()->MyVM;
    if (tab == NULL) {
      tab = (FatLock**)vm->allocator.Allocate(
          IndexSize * sizeof(FatLock*), "Index LockTable");
    }
    threadLock.unlock();
   
    // Allocate the lock.
    res = new(vm->allocator, "Lock") FatLock(index, obj);
    
    // Add the lock to the table.
    uint32_t internalIndex = index & BitMask;
    tab[internalIndex] = res;
  }
   
  assert(res->associatedObject == obj);
  // Return the lock.
  return res;
}


FatLock* LockSystem::getFatLockFromID(word_t ID) {
  if (ID & ThinLock::FatMask) {
    uint32_t index = (ID & ~ThinLock::FatMask) >> ThinLock::NonLockBits;
    FatLock* res = getLock(index);
    return res;
  } else {
    return NULL;
  }
}



bool LockingThread::wait(
    gc* self, LockSystem& table, struct timeval* info, bool timed) {
  llvm_gcroot(self, 0);
  assert(vmkit::ThinLock::owner(self, table));

  FatLock* l = vmkit::ThinLock::changeToFatlock(self, table);
  this->waitsOn = l;
  vmkit::Cond& varcondThread = this->varcond;

  if (this->interruptFlag != 0) {
    this->interruptFlag = 0;
    this->waitsOn = 0;
    return true;
  }
  
  this->state = LockingThread::StateWaiting;

  if (l->firstThread) {
    assert(l->firstThread->prevWaiting && l->firstThread->nextWaiting &&
           "Inconsistent list");
    if (l->firstThread->nextWaiting == l->firstThread) {
      l->firstThread->nextWaiting = this;
    } else {
      l->firstThread->prevWaiting->nextWaiting = this;
    } 
    this->prevWaiting = l->firstThread->prevWaiting;
    this->nextWaiting = l->firstThread;
    l->firstThread->prevWaiting = this;
  } else {
    l->firstThread = this;
    this->nextWaiting = this;
    this->prevWaiting = this;
  }
  
  assert(this->prevWaiting && this->nextWaiting && "Inconsistent list");
  assert(l->firstThread->prevWaiting && l->firstThread->nextWaiting &&
         "Inconsistent list");
      
  bool timeout = false;

  l->waitingThreads++;

  while (!this->interruptFlag && this->nextWaiting) {
    if (timed) {
      timeout = varcondThread.timedWait(&l->internalLock, info);
      if (timeout) break;
    } else {
      varcondThread.wait(&l->internalLock);
    }
  }
  assert(vmkit::ThinLock::owner(self, table) && "Not owner after wait");
      
  l->waitingThreads--;
     
  assert((!l->firstThread || (l->firstThread->prevWaiting && 
         l->firstThread->nextWaiting)) && "Inconsistent list");
 
  bool interrupted = (this->interruptFlag != 0);

  if (interrupted || timeout) {
    if (this->nextWaiting) {
      assert(this->prevWaiting && "Inconsistent list");
      if (l->firstThread != this) {
        this->nextWaiting->prevWaiting = this->prevWaiting;
        this->prevWaiting->nextWaiting = this->nextWaiting;
        assert(l->firstThread->prevWaiting && 
               l->firstThread->nextWaiting && "Inconsistent list");
      } else if (this->nextWaiting == this) {
        l->firstThread = NULL;
      } else {
        l->firstThread = this->nextWaiting;
        l->firstThread->prevWaiting = this->prevWaiting;
        this->prevWaiting->nextWaiting = l->firstThread;
        assert(l->firstThread->prevWaiting && 
               l->firstThread->nextWaiting && "Inconsistent list");
      }
      this->nextWaiting = NULL;
      this->prevWaiting = NULL;
    } else {
      assert(!this->prevWaiting && "Inconsistent state");
      // Notify lost, notify someone else.
      notify(self, table);
    }
  } else {
    assert(!this->prevWaiting && !this->nextWaiting &&
           "Inconsistent state");
  }
      
  this->state = LockingThread::StateRunning;
  this->waitsOn = NULL;

  if (interrupted) {
    this->interruptFlag = 0;
    return true;
  }
  
  assert(vmkit::ThinLock::owner(self, table) && "Not owner after wait");
  return false;
}

void LockingThread::notify(gc* self, LockSystem& table, vmkit::Thread* ownerThread) {
  llvm_gcroot(self, 0);
  if (!ownerThread) ownerThread = vmkit::Thread::get();
  assert(vmkit::ThinLock::getOwner(self, table) == ownerThread);
  FatLock* l = vmkit::ThinLock::getFatLock(self, table);
  
  if (l == NULL) return;
  LockingThread* cur = l->firstThread;
  if (cur == NULL) return;
  
  do {
    if (cur->interruptFlag != 0) {
      cur = cur->nextWaiting;
    } else {
      assert(cur->prevWaiting && cur->nextWaiting &&
             "Inconsistent list");
      if (cur != l->firstThread) {
        cur->prevWaiting->nextWaiting = cur->nextWaiting;
        cur->nextWaiting->prevWaiting = cur->prevWaiting;
        assert(l->firstThread->prevWaiting &&
               l->firstThread->nextWaiting && "Inconsistent list");
      } else if (cur->nextWaiting == cur) {
        l->firstThread = NULL;
      } else {
        l->firstThread = cur->nextWaiting;
        l->firstThread->prevWaiting = cur->prevWaiting;
        cur->prevWaiting->nextWaiting = l->firstThread;
        assert(l->firstThread->prevWaiting && 
               l->firstThread->nextWaiting && "Inconsistent list");
      }
      cur->prevWaiting = NULL;
      cur->nextWaiting = NULL;
      cur->varcond.signal();
      break;
    }
  } while (cur != l->firstThread);

  assert((vmkit::ThinLock::getOwner(self, table) == ownerThread) && "Not owner after notify");
}

void LockingThread::notifyAll(gc* self, LockSystem& table, vmkit::Thread* ownerThread) {
  llvm_gcroot(self, 0);
  if (!ownerThread) ownerThread = vmkit::Thread::get();
  assert(vmkit::ThinLock::getOwner(self, table) == ownerThread);
  FatLock* l = vmkit::ThinLock::getFatLock(self, table);
  if (l == NULL) return;
  LockingThread* cur = l->firstThread;
  if (cur == NULL) return;
  do {
    LockingThread* temp = cur->nextWaiting;
    cur->prevWaiting = NULL;
    cur->nextWaiting = NULL;
    cur->varcond.signal();
    cur = temp;
  } while (cur != l->firstThread);
  l->firstThread = NULL;
  assert((vmkit::ThinLock::getOwner(self, table) == ownerThread) && "Not owner after notifyAll");
}

void FatLock::setAssociatedObject(gc* obj) {
  llvm_gcroot(obj, 0);
  vmkit::Collector::objectReferenceNonHeapWriteBarrier((gc**)&associatedObject, (gc*)obj);
}

}