From e2facc5b18cd756a8b5500fb3d90da69c9ee0fb7 Mon Sep 17 00:00:00 2001 From: Igor Murashkin Date: Fri, 10 Jul 2015 13:49:08 -0700 Subject: [PATCH] runtime: Add lambda box/unbox object equality A lambda that is boxed with box-lambda is now stored as a weak reference in a global runtime table (lambda::BoxTable). Repeatedly boxing the same lambda closure value will always return the same java.lang.Object back. Since there is no way to observe the address of an object, a GC can happen and clean up the table of any dead boxed lambdas, which can also shrink the table to prevent the memory use from growing too much. (Note that a lambda closure is immutable, so hashing over it is guaranteed safe.) Change-Id: I786c1323ff14eed937936b303d511875f9642524 --- runtime/Android.mk | 1 + runtime/base/allocator.h | 1 + runtime/base/hash_set.h | 42 ++++-- runtime/base/hash_set_test.cc | 6 + runtime/base/mutex.cc | 6 + runtime/base/mutex.h | 5 + runtime/interpreter/interpreter_common.h | 42 ++---- runtime/lambda/box_table.cc | 220 +++++++++++++++++++++++++++++ runtime/lambda/box_table.h | 148 +++++++++++++++++++ runtime/runtime.cc | 8 ++ runtime/runtime.h | 10 ++ runtime/verifier/method_verifier.cc | 6 + test/955-lambda-smali/expected.txt | 1 + test/955-lambda-smali/smali/BoxUnbox.smali | 61 +++++++- 14 files changed, 514 insertions(+), 43 deletions(-) create mode 100644 runtime/lambda/box_table.cc create mode 100644 runtime/lambda/box_table.h diff --git a/runtime/Android.mk b/runtime/Android.mk index dd1613e1e..fe79e7203 100644 --- a/runtime/Android.mk +++ b/runtime/Android.mk @@ -98,6 +98,7 @@ LIBART_COMMON_SRC_FILES := \ jit/jit.cc \ jit/jit_code_cache.cc \ jit/jit_instrumentation.cc \ + lambda/box_table.cc \ jni_internal.cc \ jobject_comparator.cc \ linear_alloc.cc \ diff --git a/runtime/base/allocator.h b/runtime/base/allocator.h index 07daa7e0f..342262528 100644 --- a/runtime/base/allocator.h +++ b/runtime/base/allocator.h @@ -50,6 +50,7 @@ enum AllocatorTag { kAllocatorTagMonitorList, kAllocatorTagClassTable, kAllocatorTagInternTable, + kAllocatorTagLambdaBoxTable, kAllocatorTagMaps, kAllocatorTagLOS, kAllocatorTagSafeMap, diff --git a/runtime/base/hash_set.h b/runtime/base/hash_set.h index f2c8355f5..709d9ae77 100644 --- a/runtime/base/hash_set.h +++ b/runtime/base/hash_set.h @@ -231,19 +231,33 @@ class HashSet { return ret; } + // Lower case for c++11 for each. const version. + ConstIterator begin() const { + ConstIterator ret(this, 0); + if (num_buckets_ != 0 && IsFreeSlot(ret.index_)) { + ++ret; // Skip all the empty slots. + } + return ret; + } + // Lower case for c++11 for each. Iterator end() { return Iterator(this, NumBuckets()); } + // Lower case for c++11 for each. const version. + ConstIterator end() const { + return ConstIterator(this, NumBuckets()); + } + bool Empty() { return Size() == 0; } // Erase algorithm: // Make an empty slot where the iterator is pointing. - // Scan fowards until we hit another empty slot. - // If an element inbetween doesn't rehash to the range from the current empty slot to the + // Scan forwards until we hit another empty slot. + // If an element in between doesn't rehash to the range from the current empty slot to the // iterator. It must be before the empty slot, in that case we can move it to the empty slot // and set the empty slot to be the location we just moved from. // Relies on maintaining the invariant that there's no empty slots from the 'ideal' index of an @@ -299,23 +313,23 @@ class HashSet { // Set of Class* sorted by name, want to find a class with a name but can't allocate a dummy // object in the heap for performance solution. template - Iterator Find(const K& element) { - return FindWithHash(element, hashfn_(element)); + Iterator Find(const K& key) { + return FindWithHash(key, hashfn_(key)); } template - ConstIterator Find(const K& element) const { - return FindWithHash(element, hashfn_(element)); + ConstIterator Find(const K& key) const { + return FindWithHash(key, hashfn_(key)); } template - Iterator FindWithHash(const K& element, size_t hash) { - return Iterator(this, FindIndex(element, hash)); + Iterator FindWithHash(const K& key, size_t hash) { + return Iterator(this, FindIndex(key, hash)); } template - ConstIterator FindWithHash(const K& element, size_t hash) const { - return ConstIterator(this, FindIndex(element, hash)); + ConstIterator FindWithHash(const K& key, size_t hash) const { + return ConstIterator(this, FindIndex(key, hash)); } // Insert an element, allows duplicates. @@ -399,6 +413,10 @@ class HashSet { } size_t IndexForHash(size_t hash) const { + // Protect against undefined behavior (division by zero). + if (UNLIKELY(num_buckets_ == 0)) { + return 0; + } return hash % num_buckets_; } @@ -414,6 +432,10 @@ class HashSet { // This value for not found is important so that Iterator(this, FindIndex(...)) == end(). template size_t FindIndex(const K& element, size_t hash) const { + // Guard against failing to get an element for a non-existing index. + if (UNLIKELY(NumBuckets() == 0)) { + return 0; + } DCHECK_EQ(hashfn_(element), hash); size_t index = IndexForHash(hash); while (true) { diff --git a/runtime/base/hash_set_test.cc b/runtime/base/hash_set_test.cc index fd9eb45e3..4ef1f9e8c 100644 --- a/runtime/base/hash_set_test.cc +++ b/runtime/base/hash_set_test.cc @@ -186,6 +186,12 @@ TEST_F(HashSetTest, TestShrink) { // Shrink again, the load factor should be good again. hash_set.ShrinkToMaximumLoad(); EXPECT_DOUBLE_EQ(initial_load, hash_set.CalculateLoadFactor()); + + // Make sure all the initial elements we had are still there + for (const std::string& initial_string : strings) { + EXPECT_NE(hash_set.end(), hash_set.Find(initial_string)) + << "expected to find " << initial_string; + } } TEST_F(HashSetTest, TestStress) { diff --git a/runtime/base/mutex.cc b/runtime/base/mutex.cc index e48d17063..c591a5188 100644 --- a/runtime/base/mutex.cc +++ b/runtime/base/mutex.cc @@ -61,6 +61,7 @@ ConditionVariable* Locks::thread_exit_cond_ = nullptr; Mutex* Locks::thread_suspend_count_lock_ = nullptr; Mutex* Locks::trace_lock_ = nullptr; Mutex* Locks::unexpected_signal_lock_ = nullptr; +Mutex* Locks::lambda_table_lock_ = nullptr; struct AllMutexData { // A guard for all_mutexes_ that's not a mutex (Mutexes must CAS to acquire and busy wait). @@ -946,6 +947,7 @@ void Locks::Init() { DCHECK(thread_suspend_count_lock_ != nullptr); DCHECK(trace_lock_ != nullptr); DCHECK(unexpected_signal_lock_ != nullptr); + DCHECK(lambda_table_lock_ != nullptr); } else { // Create global locks in level order from highest lock level to lowest. LockLevel current_lock_level = kInstrumentEntrypointsLock; @@ -1048,6 +1050,10 @@ void Locks::Init() { DCHECK(reference_queue_soft_references_lock_ == nullptr); reference_queue_soft_references_lock_ = new Mutex("ReferenceQueue soft references lock", current_lock_level); + UPDATE_CURRENT_LOCK_LEVEL(kLambdaTableLock); + DCHECK(lambda_table_lock_ == nullptr); + lambda_table_lock_ = new Mutex("lambda table lock", current_lock_level); + UPDATE_CURRENT_LOCK_LEVEL(kAbortLock); DCHECK(abort_lock_ == nullptr); abort_lock_ = new Mutex("abort lock", current_lock_level, true); diff --git a/runtime/base/mutex.h b/runtime/base/mutex.h index f87467a0e..5b258e5dd 100644 --- a/runtime/base/mutex.h +++ b/runtime/base/mutex.h @@ -60,6 +60,7 @@ enum LockLevel { kUnexpectedSignalLock, kThreadSuspendCountLock, kAbortLock, + kLambdaTableLock, kJdwpSocketLock, kRegionSpaceRegionLock, kTransactionLogLock, @@ -648,6 +649,10 @@ class Locks { // Have an exclusive logging thread. static Mutex* logging_lock_ ACQUIRED_AFTER(unexpected_signal_lock_); + + // Allow reader-writer mutual exclusion on the boxed table of lambda objects. + // TODO: this should be a RW mutex lock, except that ConditionVariables don't work with it. + static Mutex* lambda_table_lock_ ACQUIRED_AFTER(mutator_lock_); }; } // namespace art diff --git a/runtime/interpreter/interpreter_common.h b/runtime/interpreter/interpreter_common.h index 776b6a352..9babb1832 100644 --- a/runtime/interpreter/interpreter_common.h +++ b/runtime/interpreter/interpreter_common.h @@ -34,6 +34,7 @@ #include "dex_instruction-inl.h" #include "entrypoints/entrypoint_utils-inl.h" #include "handle_scope-inl.h" +#include "lambda/box_table.h" #include "mirror/class-inl.h" #include "mirror/method.h" #include "mirror/object-inl.h" @@ -506,8 +507,8 @@ static inline bool DoBoxLambda(Thread* self, ShadowFrame& shadow_frame, const In uint32_t vreg_target_object = inst->VRegA_22x(inst_data); uint32_t vreg_source_closure = inst->VRegB_22x(); - ArtMethod* const closure_method = ReadLambdaClosureFromVRegsOrThrow(shadow_frame, - vreg_source_closure); + ArtMethod* closure_method = ReadLambdaClosureFromVRegsOrThrow(shadow_frame, + vreg_source_closure); // Failed lambda target runtime check, an exception was raised. if (UNLIKELY(closure_method == nullptr)) { @@ -515,28 +516,21 @@ static inline bool DoBoxLambda(Thread* self, ShadowFrame& shadow_frame, const In return false; } - // Convert the ArtMethod into a java.lang.reflect.Method which will serve - // as the temporary 'boxed' version of the lambda. This is good enough - // to check all the basic object identities that a boxed lambda must retain. + mirror::Object* closure_as_object = + Runtime::Current()->GetLambdaBoxTable()->BoxLambda(closure_method); - // TODO: Boxing an innate lambda (i.e. made with create-lambda) should make a proxy class - // TODO: Boxing a learned lambda (i.e. made with unbox-lambda) should return the original object - // TODO: Repeated boxing should return the same object reference - mirror::Method* method_as_object = - mirror::Method::CreateFromArtMethod(self, closure_method); - - if (UNLIKELY(method_as_object == nullptr)) { - // Most likely an OOM has occurred. + // Failed to box the lambda, an exception was raised. + if (UNLIKELY(closure_as_object == nullptr)) { CHECK(self->IsExceptionPending()); return false; } - shadow_frame.SetVRegReference(vreg_target_object, method_as_object); + shadow_frame.SetVRegReference(vreg_target_object, closure_as_object); return true; } template SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) -static inline bool DoUnboxLambda(Thread* self ATTRIBUTE_UNUSED, +static inline bool DoUnboxLambda(Thread* self, ShadowFrame& shadow_frame, const Instruction* inst, uint16_t inst_data) { @@ -556,23 +550,15 @@ static inline bool DoUnboxLambda(Thread* self ATTRIBUTE_UNUSED, return false; } - // Raise ClassCastException if object is not instanceof java.lang.reflect.Method - if (UNLIKELY(!boxed_closure_object->InstanceOf(mirror::Method::StaticClass()))) { - ThrowClassCastException(mirror::Method::StaticClass(), boxed_closure_object->GetClass()); + ArtMethod* unboxed_closure = nullptr; + // Raise an exception if unboxing fails. + if (!Runtime::Current()->GetLambdaBoxTable()->UnboxLambda(boxed_closure_object, + &unboxed_closure)) { + CHECK(self->IsExceptionPending()); return false; } - // TODO(iam): We must check that the closure object extends/implements the type - // specified in [type id]. This is not currently implemented since it's always a Method. - - // If we got this far, the inputs are valid. - // Write out the java.lang.reflect.Method's embedded ArtMethod* into the vreg target. - mirror::AbstractMethod* boxed_closure_as_method = - down_cast(boxed_closure_object); - - ArtMethod* unboxed_closure = boxed_closure_as_method->GetArtMethod(); DCHECK(unboxed_closure != nullptr); - WriteLambdaClosureIntoVRegs(shadow_frame, *unboxed_closure, vreg_target_closure); return true; } diff --git a/runtime/lambda/box_table.cc b/runtime/lambda/box_table.cc new file mode 100644 index 000000000..64a6076ae --- /dev/null +++ b/runtime/lambda/box_table.cc @@ -0,0 +1,220 @@ +/* + * Copyright (C) 2015 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +#include "lambda/box_table.h" + +#include "base/mutex.h" +#include "common_throws.h" +#include "gc_root-inl.h" +#include "mirror/method.h" +#include "mirror/object-inl.h" +#include "thread.h" + +#include + +namespace art { +namespace lambda { + +BoxTable::BoxTable() + : allow_new_weaks_(true), + new_weaks_condition_("lambda box table allowed weaks", *Locks::lambda_table_lock_) {} + +mirror::Object* BoxTable::BoxLambda(const ClosureType& closure) { + Thread* self = Thread::Current(); + + { + // TODO: Switch to ReaderMutexLock if ConditionVariable ever supports RW Mutexes + /*Reader*/MutexLock mu(self, *Locks::lambda_table_lock_); + BlockUntilWeaksAllowed(); + + // Attempt to look up this object, it's possible it was already boxed previously. + // If this is the case we *must* return the same object as before to maintain + // referential equality. + // + // In managed code: + // Functional f = () -> 5; // vF = create-lambda + // Object a = f; // vA = box-lambda vA + // Object b = f; // vB = box-lambda vB + // assert(a == f) + ValueType value = FindBoxedLambda(closure); + if (!value.IsNull()) { + return value.Read(); + } + + // Otherwise we need to box ourselves and insert it into the hash map + } + + // Release the lambda table lock here, so that thread suspension is allowed. + + // Convert the ArtMethod into a java.lang.reflect.Method which will serve + // as the temporary 'boxed' version of the lambda. This is good enough + // to check all the basic object identities that a boxed lambda must retain. + + // TODO: Boxing an innate lambda (i.e. made with create-lambda) should make a proxy class + // TODO: Boxing a learned lambda (i.e. made with unbox-lambda) should return the original object + mirror::Method* method_as_object = + mirror::Method::CreateFromArtMethod(self, closure); + // There are no thread suspension points after this, so we don't need to put it into a handle. + + if (UNLIKELY(method_as_object == nullptr)) { + // Most likely an OOM has occurred. + CHECK(self->IsExceptionPending()); + return nullptr; + } + + // The method has been successfully boxed into an object, now insert it into the hash map. + { + MutexLock mu(self, *Locks::lambda_table_lock_); + BlockUntilWeaksAllowed(); + + // Lookup the object again, it's possible another thread already boxed it while + // we were allocating the object before. + ValueType value = FindBoxedLambda(closure); + if (UNLIKELY(!value.IsNull())) { + // Let the GC clean up method_as_object at a later time. + return value.Read(); + } + + // Otherwise we should insert it into the hash map in this thread. + map_.Insert(std::make_pair(closure, ValueType(method_as_object))); + } + + return method_as_object; +} + +bool BoxTable::UnboxLambda(mirror::Object* object, ClosureType* out_closure) { + DCHECK(object != nullptr); + *out_closure = nullptr; + + // Note that we do not need to access lambda_table_lock_ here + // since we don't need to look at the map. + + mirror::Object* boxed_closure_object = object; + + // Raise ClassCastException if object is not instanceof java.lang.reflect.Method + if (UNLIKELY(!boxed_closure_object->InstanceOf(mirror::Method::StaticClass()))) { + ThrowClassCastException(mirror::Method::StaticClass(), boxed_closure_object->GetClass()); + return false; + } + + // TODO(iam): We must check that the closure object extends/implements the type + // specified in [type id]. This is not currently implemented since it's always a Method. + + // If we got this far, the inputs are valid. + // Write out the java.lang.reflect.Method's embedded ArtMethod* into the vreg target. + mirror::AbstractMethod* boxed_closure_as_method = + down_cast(boxed_closure_object); + + ArtMethod* unboxed_closure = boxed_closure_as_method->GetArtMethod(); + DCHECK(unboxed_closure != nullptr); + + *out_closure = unboxed_closure; + return true; +} + +BoxTable::ValueType BoxTable::FindBoxedLambda(const ClosureType& closure) const { + auto map_iterator = map_.Find(closure); + if (map_iterator != map_.end()) { + const std::pair& key_value_pair = *map_iterator; + const ValueType& value = key_value_pair.second; + + DCHECK(!value.IsNull()); // Never store null boxes. + return value; + } + + return ValueType(nullptr); +} + +void BoxTable::BlockUntilWeaksAllowed() { + Thread* self = Thread::Current(); + while (UNLIKELY(allow_new_weaks_ == false)) { + new_weaks_condition_.WaitHoldingLocks(self); // wait while holding mutator lock + } +} + +void BoxTable::SweepWeakBoxedLambdas(IsMarkedVisitor* visitor) { + DCHECK(visitor != nullptr); + + Thread* self = Thread::Current(); + MutexLock mu(self, *Locks::lambda_table_lock_); + + /* + * Visit every weak root in our lambda box table. + * Remove unmarked objects, update marked objects to new address. + */ + std::vector remove_list; + for (auto map_iterator = map_.begin(); map_iterator != map_.end(); ) { + std::pair& key_value_pair = *map_iterator; + + const ValueType& old_value = key_value_pair.second; + + // This does not need a read barrier because this is called by GC. + mirror::Object* old_value_raw = old_value.Read(); + mirror::Object* new_value = visitor->IsMarked(old_value_raw); + + if (new_value == nullptr) { + const ClosureType& closure = key_value_pair.first; + // The object has been swept away. + // Delete the entry from the map. + map_iterator = map_.Erase(map_.Find(closure)); + } else { + // The object has been moved. + // Update the map. + key_value_pair.second = ValueType(new_value); + ++map_iterator; + } + } + + // Occasionally shrink the map to avoid growing very large. + if (map_.CalculateLoadFactor() < kMinimumLoadFactor) { + map_.ShrinkToMaximumLoad(); + } +} + +void BoxTable::DisallowNewWeakBoxedLambdas() { + Thread* self = Thread::Current(); + MutexLock mu(self, *Locks::lambda_table_lock_); + + allow_new_weaks_ = false; +} + +void BoxTable::AllowNewWeakBoxedLambdas() { + Thread* self = Thread::Current(); + MutexLock mu(self, *Locks::lambda_table_lock_); + + allow_new_weaks_ = true; + new_weaks_condition_.Broadcast(self); +} + +void BoxTable::EnsureNewWeakBoxedLambdasDisallowed() { + Thread* self = Thread::Current(); + MutexLock mu(self, *Locks::lambda_table_lock_); + CHECK_NE(allow_new_weaks_, false); +} + +bool BoxTable::EqualsFn::operator()(const ClosureType& lhs, const ClosureType& rhs) const { + // Nothing needs this right now, but leave this assertion for later when + // we need to look at the references inside of the closure. + if (kIsDebugBuild) { + Locks::mutator_lock_->AssertSharedHeld(Thread::Current()); + } + + // TODO: Need rework to use read barriers once closures have references inside of them that can + // move. Until then, it's safe to just compare the data inside of it directly. + return lhs == rhs; +} + +} // namespace lambda +} // namespace art diff --git a/runtime/lambda/box_table.h b/runtime/lambda/box_table.h new file mode 100644 index 000000000..12d3ff3ac --- /dev/null +++ b/runtime/lambda/box_table.h @@ -0,0 +1,148 @@ +/* + * Copyright (C) 2015 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +#ifndef ART_RUNTIME_LAMBDA_BOX_TABLE_H_ +#define ART_RUNTIME_LAMBDA_BOX_TABLE_H_ + +#include "base/allocator.h" +#include "base/hash_map.h" +#include "gc_root.h" +#include "base/macros.h" +#include "base/mutex.h" +#include "object_callbacks.h" + +#include + +namespace art { + +class ArtMethod; // forward declaration + +namespace mirror { +class Object; // forward declaration +} // namespace mirror + +namespace lambda { + +/* + * Store a table of boxed lambdas. This is required to maintain object referential equality + * when a lambda is re-boxed. + * + * Conceptually, we store a mapping of Closures -> Weak Reference. + * When too many objects get GCd, we shrink the underlying table to use less space. + */ +class BoxTable FINAL { + public: + using ClosureType = art::ArtMethod*; + + // Boxes a closure into an object. Returns null and throws an exception on failure. + mirror::Object* BoxLambda(const ClosureType& closure) + SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) + LOCKS_EXCLUDED(Locks::lambda_table_lock_); + + // Unboxes an object back into the lambda. Returns false and throws an exception on failure. + bool UnboxLambda(mirror::Object* object, ClosureType* out_closure) + SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); + + // Sweep weak references to lambda boxes. Update the addresses if the objects have been + // moved, and delete them from the table if the objects have been cleaned up. + void SweepWeakBoxedLambdas(IsMarkedVisitor* visitor) + SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) + LOCKS_EXCLUDED(Locks::lambda_table_lock_); + + // GC callback: Temporarily block anyone from touching the map. + void DisallowNewWeakBoxedLambdas() + LOCKS_EXCLUDED(Locks::lambda_table_lock_); + + // GC callback: Unblock any readers who have been queued waiting to touch the map. + void AllowNewWeakBoxedLambdas() + LOCKS_EXCLUDED(Locks::lambda_table_lock_); + + // GC callback: Verify that the state is now blocking anyone from touching the map. + void EnsureNewWeakBoxedLambdasDisallowed() + LOCKS_EXCLUDED(Locks::lambda_table_lock_); + + BoxTable(); + ~BoxTable() = default; + + private: + // FIXME: This needs to be a GcRoot. + // Explanation: + // - After all threads are suspended (exclusive mutator lock), + // the concurrent-copying GC can move objects from the "from" space to the "to" space. + // If an object is moved at that time and *before* SweepSystemWeaks are called then + // we don't know if the move has happened yet. + // Successive reads will then (incorrectly) look at the objects in the "from" space, + // which is a problem since the objects have been already forwarded and mutations + // would not be visible in the right space. + // Instead, use a GcRoot here which will be automatically updated by the GC. + // + // Also, any reads should be protected by a read barrier to always give us the "to" space address. + using ValueType = GcRoot; + + // Attempt to look up the lambda in the map, or return null if it's not there yet. + ValueType FindBoxedLambda(const ClosureType& closure) const + SHARED_LOCKS_REQUIRED(Locks::lambda_table_lock_); + + // If the GC has come in and temporarily disallowed touching weaks, block until is it allowed. + void BlockUntilWeaksAllowed() + SHARED_LOCKS_REQUIRED(Locks::lambda_table_lock_); + + // EmptyFn implementation for art::HashMap + struct EmptyFn { + void MakeEmpty(std::pair& item) const { + item.first = nullptr; + } + bool IsEmpty(const std::pair& item) const { + return item.first == nullptr; + } + }; + + // HashFn implementation for art::HashMap + struct HashFn { + size_t operator()(const ClosureType& key) const { + // TODO(iam): Rewrite hash function when ClosureType is no longer an ArtMethod* + return static_cast(reinterpret_cast(key)); + } + }; + + // EqualsFn implementation for art::HashMap + struct EqualsFn { + bool operator()(const ClosureType& lhs, const ClosureType& rhs) const; + }; + + using UnorderedMap = art::HashMap, + kAllocatorTagLambdaBoxTable>>; + + UnorderedMap map_ GUARDED_BY(Locks::lambda_table_lock_); + bool allow_new_weaks_ GUARDED_BY(Locks::lambda_table_lock_); + ConditionVariable new_weaks_condition_ GUARDED_BY(Locks::lambda_table_lock_); + + // Shrink the map when we get below this load factor. + // (This is an arbitrary value that should be large enough to prevent aggressive map erases + // from shrinking the table too often.) + static constexpr double kMinimumLoadFactor = UnorderedMap::kDefaultMinLoadFactor / 2; + + DISALLOW_COPY_AND_ASSIGN(BoxTable); +}; + +} // namespace lambda +} // namespace art + +#endif // ART_RUNTIME_LAMBDA_BOX_TABLE_H_ diff --git a/runtime/runtime.cc b/runtime/runtime.cc index d7bbeb70b..cc8b21504 100644 --- a/runtime/runtime.cc +++ b/runtime/runtime.cc @@ -75,6 +75,7 @@ #include "jit/jit.h" #include "jni_internal.h" #include "linear_alloc.h" +#include "lambda/box_table.h" #include "mirror/array.h" #include "mirror/class-inl.h" #include "mirror/class_loader.h" @@ -408,6 +409,7 @@ void Runtime::SweepSystemWeaks(IsMarkedVisitor* visitor) { GetMonitorList()->SweepMonitorList(visitor); GetJavaVM()->SweepJniWeakGlobals(visitor); GetHeap()->SweepAllocationRecords(visitor); + GetLambdaBoxTable()->SweepWeakBoxedLambdas(visitor); } bool Runtime::Create(const RuntimeOptions& options, bool ignore_unrecognized) { @@ -912,6 +914,9 @@ bool Runtime::Init(const RuntimeOptions& raw_options, bool ignore_unrecognized) jit_options_->SetUseJIT(false); } + // Allocate a global table of boxed lambda objects <-> closures. + lambda_box_table_ = MakeUnique(); + // Use MemMap arena pool for jit, malloc otherwise. Malloc arenas are faster to allocate but // can't be trimmed as easily. const bool use_malloc = IsAotCompiler(); @@ -1500,6 +1505,7 @@ void Runtime::DisallowNewSystemWeaks() { intern_table_->ChangeWeakRootState(gc::kWeakRootStateNoReadsOrWrites); java_vm_->DisallowNewWeakGlobals(); heap_->DisallowNewAllocationRecords(); + lambda_box_table_->DisallowNewWeakBoxedLambdas(); } void Runtime::AllowNewSystemWeaks() { @@ -1507,6 +1513,7 @@ void Runtime::AllowNewSystemWeaks() { intern_table_->ChangeWeakRootState(gc::kWeakRootStateNormal); // TODO: Do this in the sweeping? java_vm_->AllowNewWeakGlobals(); heap_->AllowNewAllocationRecords(); + lambda_box_table_->AllowNewWeakBoxedLambdas(); } void Runtime::EnsureNewSystemWeaksDisallowed() { @@ -1515,6 +1522,7 @@ void Runtime::EnsureNewSystemWeaksDisallowed() { monitor_list_->EnsureNewMonitorsDisallowed(); intern_table_->EnsureNewWeakInternsDisallowed(); java_vm_->EnsureNewWeakGlobalsDisallowed(); + lambda_box_table_->EnsureNewWeakBoxedLambdasDisallowed(); } void Runtime::BroadcastForNewSystemWeaks() { diff --git a/runtime/runtime.h b/runtime/runtime.h index 806292f3d..55adaf127 100644 --- a/runtime/runtime.h +++ b/runtime/runtime.h @@ -53,6 +53,10 @@ namespace jit { class JitOptions; } // namespace jit +namespace lambda { + class BoxTable; +} // namespace lambda + namespace mirror { class ClassLoader; class Array; @@ -532,6 +536,10 @@ class Runtime { return experimental_lambdas_; } + lambda::BoxTable* GetLambdaBoxTable() const { + return lambda_box_table_.get(); + } + // Create the JIT and instrumentation and code cache. void CreateJit(); @@ -646,6 +654,8 @@ class Runtime { std::unique_ptr jit_; std::unique_ptr jit_options_; + std::unique_ptr lambda_box_table_; + // Fault message, printed when we get a SIGSEGV. Mutex fault_message_lock_ DEFAULT_MUTEX_ACQUIRED_AFTER; std::string fault_message_ GUARDED_BY(fault_message_lock_); diff --git a/runtime/verifier/method_verifier.cc b/runtime/verifier/method_verifier.cc index 11c3e659e..764b6ba0a 100644 --- a/runtime/verifier/method_verifier.cc +++ b/runtime/verifier/method_verifier.cc @@ -2946,6 +2946,12 @@ bool MethodVerifier::CodeFlowVerifyInstruction(uint32_t* start_guess) { // If the code would've normally hard-failed, then the interpreter will throw the // appropriate verification errors at runtime. Fail(VERIFY_ERROR_FORCE_INTERPRETER); // TODO(iam): implement box-lambda verification + + // Partial verification. Sets the resulting type to always be an object, which + // is good enough for some other verification to occur without hard-failing. + const uint32_t vreg_target_object = inst->VRegA_22x(); // box-lambda vA, vB + const RegType& reg_type = reg_types_.JavaLangObject(need_precise_constants_); + work_line_->SetRegisterType(this, vreg_target_object, reg_type); break; } diff --git a/test/955-lambda-smali/expected.txt b/test/955-lambda-smali/expected.txt index 0a5b5fd37..5059f4be1 100644 --- a/test/955-lambda-smali/expected.txt +++ b/test/955-lambda-smali/expected.txt @@ -3,6 +3,7 @@ Hello world! (0-args, no closure) ABCD Hello world! (4-args, no closure) Caught NPE (BoxUnbox) Hello boxing world! (0-args, no closure) +(BoxUnbox) Boxing repeatedly yields referentially-equal objects (BoxUnbox) Caught NPE for unbox-lambda (BoxUnbox) Caught NPE for box-lambda (BoxUnbox) Caught ClassCastException for unbox-lambda diff --git a/test/955-lambda-smali/smali/BoxUnbox.smali b/test/955-lambda-smali/smali/BoxUnbox.smali index 5e6673368..108b5fafb 100644 --- a/test/955-lambda-smali/smali/BoxUnbox.smali +++ b/test/955-lambda-smali/smali/BoxUnbox.smali @@ -23,15 +23,14 @@ .end method .method public static run()V -.registers 2 - # Trivial 0-arg hello world - create-lambda v0, LBoxUnbox;->doHelloWorld(Ljava/lang/reflect/ArtMethod;)V - # TODO: create-lambda should not write to both v0 and v1 - invoke-lambda v0, {} + .registers 0 + invoke-static {}, LBoxUnbox;->testBox()V + invoke-static {}, LBoxUnbox;->testBoxEquality()V invoke-static {}, LBoxUnbox;->testFailures()V invoke-static {}, LBoxUnbox;->testFailures2()V invoke-static {}, LBoxUnbox;->testFailures3()V + invoke-static {}, LBoxUnbox;->forceGC()V return-void .end method @@ -48,6 +47,47 @@ return-void .end method +# Test boxing and unboxing; the same lambda should be invoked as if there was no box. +.method private static testBox()V + .registers 3 + + create-lambda v0, LBoxUnbox;->doHelloWorld(Ljava/lang/reflect/ArtMethod;)V + box-lambda v2, v0 # v2 = box(v0) + unbox-lambda v0, v2, Ljava/lang/reflect/ArtMethod; # v0 = unbox(v2) + invoke-lambda v0, {} + + return-void +.end method + +# Test that boxing the same lambda twice yield the same object. +.method private static testBoxEquality()V + .registers 6 # 0 parameters, 6 locals + + create-lambda v0, LBoxUnbox;->doHelloWorld(Ljava/lang/reflect/ArtMethod;)V + box-lambda v2, v0 # v2 = box(v0) + box-lambda v3, v0 # v3 = box(v0) + + # The objects should be not-null, and they should have the same reference + if-eqz v2, :is_zero + if-ne v2, v3, :is_not_equal + + const-string v4, "(BoxUnbox) Boxing repeatedly yields referentially-equal objects" + goto :end + +:is_zero + const-string v4, "(BoxUnbox) Boxing repeatedly FAILED: boxing returned null" + goto :end + +:is_not_equal + const-string v4, "(BoxUnbox) Boxing repeatedly FAILED: objects were not same reference" + goto :end + +:end + sget-object v5, Ljava/lang/System;->out:Ljava/io/PrintStream; + invoke-virtual {v5, v4}, Ljava/io/PrintStream;->println(Ljava/lang/String;)V + return-void +.end method + # Test exceptions are thrown as expected when used opcodes incorrectly .method private static testFailures()V .registers 4 # 0 parameters, 4 locals @@ -116,3 +156,14 @@ .catch Ljava/lang/ClassCastException; {:start .. :end} :handler .end method + + +# Force a GC. Used to ensure our weak reference table of boxed lambdas is getting swept. +.method private static forceGC()V + .registers 1 + invoke-static {}, Ljava/lang/Runtime;->getRuntime()Ljava/lang/Runtime; + move-result-object v0 + invoke-virtual {v0}, Ljava/lang/Runtime;->gc()V + + return-void +.end method -- 2.11.0