diff --git a/src/heap.cc b/src/heap.cc
index 86d19a8..fc3fce0 100644
--- a/src/heap.cc
+++ b/src/heap.cc
@@ -37,6 +37,19 @@
 MemberOffset Heap::reference_pendingNext_offset_ = MemberOffset(0);
 MemberOffset Heap::finalizer_reference_zombie_offset_ = MemberOffset(0);
 
+Mutex* Heap::lock_ = NULL;
+
+class ScopedHeapLock {
+ public:
+  ScopedHeapLock() {
+    Heap::Lock();
+  }
+
+  ~ScopedHeapLock() {
+    Heap::Unlock();
+  }
+};
+
 bool Heap::Init(size_t initial_size, size_t maximum_size,
                 const char* boot_image_file_name,
                 std::vector<const char*>& image_file_names) {
@@ -115,10 +128,16 @@
     RecordImageAllocations(image_spaces[i]);
   }
 
+  // It's still to early to take a lock because there are no threads yet,
+  // but we can create the heap lock now. We don't create it earlier to
+  // make it clear that you can't use locks during heap initialization.
+  lock_ = Mutex::Create("Heap lock");
+
   return true;
 }
 
 void Heap::Destroy() {
+  ScopedHeapLock lock;
   STLDeleteElements(&spaces_);
   if (mark_bitmap_ != NULL) {
     delete mark_bitmap_;
@@ -131,12 +150,13 @@
 }
 
 Object* Heap::AllocObject(Class* klass, size_t num_bytes) {
+  ScopedHeapLock lock;
   DCHECK(klass == NULL
          || klass->GetDescriptor() == NULL
          || (klass->IsClassClass() && num_bytes >= sizeof(Class))
          || (klass->IsVariableSize() || klass->GetObjectSize() == num_bytes));
   DCHECK(num_bytes >= sizeof(Object));
-  Object* obj = Allocate(num_bytes);
+  Object* obj = AllocateLocked(num_bytes);
   if (obj != NULL) {
     obj->SetClass(klass);
   }
@@ -144,6 +164,8 @@
 }
 
 bool Heap::IsHeapAddress(const Object* obj) {
+  // Note: we deliberately don't take the lock here, and mustn't test anything that would
+  // require taking the lock.
   if (!IsAligned(obj, kObjectAlignment)) {
     return false;
   }
@@ -155,6 +177,13 @@
 
 #if VERIFY_OBJECT_ENABLED
 void Heap::VerifyObject(const Object* obj) {
+  ScopedHeapLock lock;
+  Heap::VerifyObjectLocked(obj);
+}
+#endif
+
+void Heap::VerifyObjectLocked(const Object* obj) {
+  DCHECK_LOCK_HELD(lock_);
   if (obj != NULL && !verify_object_disabled_) {
     if (!IsAligned(obj, kObjectAlignment)) {
       LOG(FATAL) << "Object isn't aligned: " << obj;
@@ -188,18 +217,23 @@
     }
   }
 }
-#endif
 
-static void HeapVerifyCallback(Object* obj, void *arg) {
+void Heap::VerificationCallback(Object* obj, void *arg) {
   DCHECK(obj != NULL);
-  Heap::VerifyObject(obj);
+  Heap::VerifyObjectLocked(obj);
 }
 
 void Heap::VerifyHeap() {
-  live_bitmap_->Walk(HeapVerifyCallback, NULL);
+  ScopedHeapLock lock;
+  live_bitmap_->Walk(Heap::VerificationCallback, NULL);
 }
 
-void Heap::RecordAllocation(Space* space, const Object* obj) {
+void Heap::RecordAllocationLocked(Space* space, const Object* obj) {
+#ifndef NDEBUG
+  if (Runtime::Current()->IsStarted()) {
+    DCHECK_LOCK_HELD(lock_);
+  }
+#endif
   size_t size = space->AllocationSize(obj);
   DCHECK_NE(size, 0u);
   num_bytes_allocated_ += size;
@@ -207,7 +241,8 @@
   live_bitmap_->Set(obj);
 }
 
-void Heap::RecordFree(Space* space, const Object* obj) {
+void Heap::RecordFreeLocked(Space* space, const Object* obj) {
+  DCHECK_LOCK_HELD(lock_);
   size_t size = space->AllocationSize(obj);
   DCHECK_NE(size, 0u);
   if (size < num_bytes_allocated_) {
@@ -222,6 +257,7 @@
 }
 
 void Heap::RecordImageAllocations(Space* space) {
+  DCHECK(!Runtime::Current()->IsStarted());
   CHECK(space != NULL);
   CHECK(live_bitmap_ != NULL);
   byte* current = space->GetBase() + RoundUp(sizeof(ImageHeader), kObjectAlignment);
@@ -233,17 +269,20 @@
   }
 }
 
-Object* Heap::Allocate(size_t size) {
+Object* Heap::AllocateLocked(size_t size) {
+  DCHECK_LOCK_HELD(lock_);
   DCHECK(alloc_space_ != NULL);
   Space* space = alloc_space_;
-  Object* obj = Allocate(space, size);
+  Object* obj = AllocateLocked(space, size);
   if (obj != NULL) {
-    RecordAllocation(space, obj);
+    RecordAllocationLocked(space, obj);
   }
   return obj;
 }
 
-Object* Heap::Allocate(Space* space, size_t size) {
+Object* Heap::AllocateLocked(Space* space, size_t size) {
+  DCHECK_LOCK_HELD(lock_);
+
   // Fail impossible allocations.  TODO: collect soft references.
   if (size > maximum_size_) {
     return NULL;
@@ -328,11 +367,12 @@
 }
 
 void Heap::CollectGarbage() {
+  ScopedHeapLock lock;
   CollectGarbageInternal();
 }
 
 void Heap::CollectGarbageInternal() {
-  // TODO: check that heap lock is held
+  DCHECK_LOCK_HELD(lock_);
 
   // TODO: Suspend all threads
   {
@@ -369,13 +409,25 @@
 }
 
 void Heap::WaitForConcurrentGcToComplete() {
+  DCHECK_LOCK_HELD(lock_);
 }
 
 // Given the current contents of the active heap, increase the allowed
 // heap footprint to match the target utilization ratio.  This should
 // only be called immediately after a full garbage collection.
 void Heap::GrowForUtilization() {
+  DCHECK_LOCK_HELD(lock_);
   UNIMPLEMENTED(ERROR);
 }
 
+void Heap::Lock() {
+  // TODO: grab the lock, but put ourselves into THREAD_VMWAIT if it looks like
+  // we're going to have to wait on the mutex.
+  lock_->Lock();
+}
+
+void Heap::Unlock() {
+  lock_->Unlock();
+}
+
 }  // namespace art
diff --git a/src/heap.h b/src/heap.h
index 3dc612a..296266a 100644
--- a/src/heap.h
+++ b/src/heap.h
@@ -67,9 +67,9 @@
   // Blocks the caller until the garbage collector becomes idle.
   static void WaitForConcurrentGcToComplete();
 
-  static Mutex* GetLock() {
-    return lock_;
-  }
+  static void Lock();
+
+  static void Unlock();
 
   static const std::vector<Space*>& GetSpaces() {
     return spaces_;
@@ -134,20 +134,25 @@
     verify_object_disabled_ = true;
   }
 
-  static void RecordFree(Space* space, const Object* object);
+  // Callers must hold the heap lock.
+  static void RecordFreeLocked(Space* space, const Object* object);
 
  private:
   // Allocates uninitialized storage.
-  static Object* Allocate(size_t num_bytes);
-  static Object* Allocate(Space* space, size_t num_bytes);
+  static Object* AllocateLocked(size_t num_bytes);
+  static Object* AllocateLocked(Space* space, size_t num_bytes);
 
-  static void RecordAllocation(Space* space, const Object* object);
+  static void RecordAllocationLocked(Space* space, const Object* object);
   static void RecordImageAllocations(Space* space);
 
   static void CollectGarbageInternal();
 
   static void GrowForUtilization();
 
+  static void VerifyObjectLocked(const Object *obj);
+
+  static void VerificationCallback(Object* obj, void *arg);
+
   static Mutex* lock_;
 
   static std::vector<Space*> spaces_;
diff --git a/src/logging.h b/src/logging.h
index 43596b5..66190ac 100644
--- a/src/logging.h
+++ b/src/logging.h
@@ -72,8 +72,20 @@
 #define DCHECK_STREQ(s1, s2) CHECK_STREQ(s1, s2)
 #define DCHECK_STRNE(s1, s2) CHECK_STRNE(s1, s2)
 
+  // These require "utils.h" and only work with bionic (not glibc).
+#ifdef __BIONIC__
+#define DCHECK_LOCK_HELD(l) CHECK_EQ(art::GetOwner(l->GetImpl()), art::GetTid())
+#define DCHECK_LOCK_NOT_HELD(l) CHECK_NE(art::GetOwner(l->GetImpl()), art::GetTid())
+#else
+#define DCHECK_LOCK_HELD(l)
+#define DCHECK_LOCK_NOT_HELD(l)
+#endif
+
 #else  // NDEBUG
 
+#define DCHECK_LOCK_HELD(l)
+#define DCHECK_LOCK_NOT_HELD(l)
+
 #define DCHECK(condition) \
   while (false) \
     CHECK(condition)
diff --git a/src/mark_sweep.cc b/src/mark_sweep.cc
index 307a804..c947da3 100644
--- a/src/mark_sweep.cc
+++ b/src/mark_sweep.cc
@@ -151,7 +151,7 @@
   Space* space = static_cast<Space*>(arg);
   for (size_t i = 0; i < num_ptrs; ++i) {
     Object* obj = static_cast<Object*>(ptrs[i]);
-    Heap::RecordFree(space, obj);
+    Heap::RecordFreeLocked(space, obj);
     space->Free(obj);
   }
   // TODO, unlock heap if concurrent
diff --git a/src/thread.cc b/src/thread.cc
index 6109825..ae926ad 100644
--- a/src/thread.cc
+++ b/src/thread.cc
@@ -193,53 +193,59 @@
 
 Mutex* Mutex::Create(const char* name) {
   Mutex* mu = new Mutex(name);
-  int result = pthread_mutex_init(&mu->lock_impl_, NULL);
-  CHECK_EQ(result, 0);
+#ifndef NDEBUG
+  pthread_mutexattr_t debug_attributes;
+  errno = pthread_mutexattr_init(&debug_attributes);
+  if (errno != 0) {
+    PLOG(FATAL) << "pthread_mutexattr_init failed";
+  }
+  errno = pthread_mutexattr_settype(&debug_attributes, PTHREAD_MUTEX_ERRORCHECK);
+  if (errno != 0) {
+    PLOG(FATAL) << "pthread_mutexattr_settype failed";
+  }
+  errno = pthread_mutex_init(&mu->lock_impl_, &debug_attributes);
+  if (errno != 0) {
+    PLOG(FATAL) << "pthread_mutex_init failed";
+  }
+  errno = pthread_mutexattr_destroy(&debug_attributes);
+  if (errno != 0) {
+    PLOG(FATAL) << "pthread_mutexattr_destroy failed";
+  }
+#else
+  errno = pthread_mutex_init(&mu->lock_impl_, NULL);
+  if (errno != 0) {
+    PLOG(FATAL) << "pthread_mutex_init failed";
+  }
+#endif
   return mu;
 }
 
 void Mutex::Lock() {
   int result = pthread_mutex_lock(&lock_impl_);
-  CHECK_EQ(result, 0);
-  SetOwner(Thread::Current());
+  if (result != 0) {
+    errno = result;
+    PLOG(FATAL) << "pthread_mutex_lock failed";
+  }
 }
 
 bool Mutex::TryLock() {
-  int result = pthread_mutex_lock(&lock_impl_);
+  int result = pthread_mutex_trylock(&lock_impl_);
   if (result == EBUSY) {
     return false;
-  } else {
-    CHECK_EQ(result, 0);
-    SetOwner(Thread::Current());
-    return true;
   }
+  if (result != 0) {
+    errno = result;
+    PLOG(FATAL) << "pthread_mutex_trylock failed";
+  }
+  return true;
 }
 
 void Mutex::Unlock() {
-#ifndef NDEBUG
-  Thread* self = Thread::Current();
-  std::stringstream os;
-  os << "owner=";
-  if (owner_ != NULL) {
-    os << *owner_;
-  } else {
-    os << "NULL";
-  }
-  os << " self=";
-  if (self != NULL) {
-    os << *self;
-  } else {
-    os << "NULL";
-  }
-  DCHECK(HaveLock()) << os.str();
-#endif
-  SetOwner(NULL);
   int result = pthread_mutex_unlock(&lock_impl_);
-  CHECK_EQ(result, 0);
-}
-
-bool Mutex::HaveLock() {
-  return owner_ == Thread::Current();
+  if (result != 0) {
+    errno = result;
+    PLOG(FATAL) << "pthread_mutex_unlock failed";
+  }
 }
 
 void Frame::Next() {
@@ -933,14 +939,14 @@
 }
 
 void ThreadList::Register(Thread* thread) {
-  //LOG(INFO) << "ThreadList::Register() " << *thread;
+  LOG(INFO) << "ThreadList::Register() " << *thread;
   MutexLock mu(lock_);
   CHECK(!Contains(thread));
   list_.push_back(thread);
 }
 
 void ThreadList::Unregister() {
-  //LOG(INFO) << "ThreadList::Unregister() " << *Thread::Current();
+  LOG(INFO) << "ThreadList::Unregister() " << *Thread::Current();
   MutexLock mu(lock_);
   Thread* self = Thread::Current();
   CHECK(Contains(self));
@@ -959,7 +965,7 @@
 }
 
 uint32_t ThreadList::AllocThreadId() {
-  DCHECK(lock_->HaveLock());
+  DCHECK_LOCK_HELD(lock_);
   for (size_t i = 0; i < allocated_ids_.size(); ++i) {
     if (!allocated_ids_[i]) {
       allocated_ids_.set(i);
@@ -971,7 +977,7 @@
 }
 
 void ThreadList::ReleaseThreadId(uint32_t id) {
-  DCHECK(lock_->HaveLock());
+  DCHECK_LOCK_HELD(lock_);
   --id; // Zero is reserved to mean "invalid".
   DCHECK(allocated_ids_[id]) << id;
   allocated_ids_.reset(id);
diff --git a/src/thread.h b/src/thread.h
index ba5d6ef..d50b45b 100644
--- a/src/thread.h
+++ b/src/thread.h
@@ -48,24 +48,15 @@
 
   const char* GetName() { return name_; }
 
-  Thread* GetOwner() { return owner_; }
-
-  bool HaveLock();
-
   static Mutex* Create(const char* name);
 
-  // TODO: only needed because we lack a condition variable abstraction.
   pthread_mutex_t* GetImpl() { return &lock_impl_; }
 
  private:
-  explicit Mutex(const char* name) : name_(name), owner_(NULL) {}
-
-  void SetOwner(Thread* thread) { owner_ = thread; }
+  explicit Mutex(const char* name) : name_(name) {}
 
   const char* name_;
 
-  Thread* owner_;
-
   pthread_mutex_t lock_impl_;
 
   DISALLOW_COPY_AND_ASSIGN(Mutex);
diff --git a/src/utils.cc b/src/utils.cc
index d890d29..fed8a5e 100644
--- a/src/utils.cc
+++ b/src/utils.cc
@@ -3,6 +3,7 @@
 
 #include "utils.h"
 
+#include <pthread.h>
 #include <sys/syscall.h>
 #include <sys/types.h>
 #include <unistd.h>
@@ -251,6 +252,15 @@
 #endif
 }
 
+pid_t GetOwner(pthread_mutex_t* mutex) {
+#ifdef __BIONIC__
+  return static_cast<pid_t>(((mutex)->value >> 16) & 0xffff);
+#else
+  UNIMPLEMENTED(FATAL);
+  return 0;
+#endif
+}
+
 }  // namespace art
 
 // Neither bionic nor glibc exposes gettid(2).
diff --git a/src/utils.h b/src/utils.h
index 78d655e..135ea59 100644
--- a/src/utils.h
+++ b/src/utils.h
@@ -8,6 +8,7 @@
 #include "stringpiece.h"
 #include "stringprintf.h"
 
+#include <pthread.h>
 #include <string>
 #include <vector>
 
@@ -180,6 +181,9 @@
 // Returns the calling thread's tid. (The C libraries don't expose this.)
 pid_t GetTid();
 
+// Returns the tid of the thread that owns the given pthread mutex, or 0.
+pid_t GetOwner(pthread_mutex_t* mutex);
+
 // Sets the name of the current thread. The name may be truncated to an
 // implementation-defined limit.
 void SetThreadName(const char* name);