/*
 * 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 "mod_union_table-inl.h"

#include "class_linker-inl.h"
#include "class_root-inl.h"
#include "common_runtime_test.h"
#include "gc/space/space-inl.h"
#include "mirror/array-alloc-inl.h"
#include "mirror/array-inl.h"
#include "space_bitmap-inl.h"
#include "thread-current-inl.h"
#include "thread_list.h"

namespace art HIDDEN {
namespace gc {
namespace accounting {

class ModUnionTableFactory {
 public:
  enum TableType {
    kTableTypeCardCache,
    kTableTypeReferenceCache,
    kTableTypeCount,  // Number of values in the enum.
  };

  // Target space is ignored for the card cache implementation.
  static ModUnionTable* Create(
      TableType type, space::ContinuousSpace* space, space::ContinuousSpace* target_space);
};

class ModUnionTableTest : public CommonRuntimeTest {
 public:
  ModUnionTableTest() : java_lang_object_array_(nullptr) {
    use_boot_image_ = true;  // Make the Runtime creation cheaper.
  }
  mirror::ObjectArray<mirror::Object>* AllocObjectArray(
      Thread* self, space::ContinuousMemMapAllocSpace* space, size_t component_count)
      REQUIRES_SHARED(Locks::mutator_lock_) {
    auto* klass = GetObjectArrayClass(self, space);
    const size_t size = mirror::ComputeArraySize(component_count, 2);
    size_t bytes_allocated = 0, bytes_tl_bulk_allocated;
    auto* obj = down_cast<mirror::ObjectArray<mirror::Object>*>(
        space->Alloc(self, size, &bytes_allocated, nullptr, &bytes_tl_bulk_allocated));
    if (obj != nullptr) {
      obj->SetClass(klass);
      obj->SetLength(static_cast<int32_t>(component_count));
      space->GetLiveBitmap()->Set(obj);
      EXPECT_GE(bytes_allocated, size);
    }
    return obj;
  }
  void ResetClass() {
    java_lang_object_array_ = nullptr;
  }
  void RunTest(ModUnionTableFactory::TableType type);

 private:
  mirror::Class* GetObjectArrayClass(Thread* self, space::ContinuousMemMapAllocSpace* space)
      REQUIRES_SHARED(Locks::mutator_lock_) {
    if (java_lang_object_array_ == nullptr) {
      java_lang_object_array_ = GetClassRoot<mirror::ObjectArray<mirror::Object>>().Ptr();
      // Since the test doesn't have an image, the class of the object array keeps cards live
      // inside the card cache mod-union table and causes the check
      // ASSERT_FALSE(table->ContainsCardFor(reinterpret_cast<uintptr_t>(obj3)));
      // to fail since the class ends up keeping the card dirty. To get around this, we make a fake
      // copy of the class in the same space that we are allocating in.
      DCHECK(java_lang_object_array_ != nullptr);
      const size_t class_size = java_lang_object_array_->GetClassSize();
      size_t bytes_allocated = 0, bytes_tl_bulk_allocated;
      auto* klass = down_cast<mirror::Class*>(space->Alloc(self, class_size, &bytes_allocated,
                                                           nullptr,
                                                           &bytes_tl_bulk_allocated));
      DCHECK(klass != nullptr);
      memcpy(klass, java_lang_object_array_, class_size);
      Runtime::Current()->GetHeap()->GetCardTable()->MarkCard(klass);
      java_lang_object_array_ = klass;
    }
    return java_lang_object_array_;
  }
  mirror::Class* java_lang_object_array_;
};

// Collect visited objects into container.
class CollectVisitedVisitor : public MarkObjectVisitor {
 public:
  explicit CollectVisitedVisitor(std::set<mirror::Object*>* out) : out_(out) {}
  void MarkHeapReference(mirror::HeapReference<mirror::Object>* ref,
                         [[maybe_unused]] bool do_atomic_update) override
      REQUIRES_SHARED(Locks::mutator_lock_) {
    DCHECK(ref != nullptr);
    MarkObject(ref->AsMirrorPtr());
  }
  mirror::Object* MarkObject(mirror::Object* obj) override
      REQUIRES_SHARED(Locks::mutator_lock_) {
    DCHECK(obj != nullptr);
    out_->insert(obj);
    return obj;
  }

 private:
  std::set<mirror::Object*>* const out_;
};

// A mod union table that only holds references to a specified target space.
class ModUnionTableRefCacheToSpace : public ModUnionTableReferenceCache {
 public:
  explicit ModUnionTableRefCacheToSpace(
      const std::string& name, Heap* heap, space::ContinuousSpace* space,
      space::ContinuousSpace* target_space)
      : ModUnionTableReferenceCache(name, heap, space), target_space_(target_space) {}

  bool ShouldAddReference(const mirror::Object* ref) const override {
    return target_space_->HasAddress(ref);
  }

 private:
  space::ContinuousSpace* const target_space_;
};

std::ostream& operator<<(std::ostream& oss, ModUnionTableFactory::TableType type) {
  switch (type) {
    case ModUnionTableFactory::kTableTypeCardCache: {
      oss << "CardCache";
      break;
    }
    case ModUnionTableFactory::kTableTypeReferenceCache: {
      oss << "ReferenceCache";
      break;
    }
    default: {
      UNIMPLEMENTED(FATAL) << static_cast<size_t>(type);
    }
  }
  return oss;
}

ModUnionTable* ModUnionTableFactory::Create(
    TableType type, space::ContinuousSpace* space, space::ContinuousSpace* target_space) {
  std::ostringstream name;
  name << "Mod union table: " << type;
  switch (type) {
    case kTableTypeCardCache: {
      return new ModUnionTableCardCache(name.str(), Runtime::Current()->GetHeap(), space);
    }
    case kTableTypeReferenceCache: {
      return new ModUnionTableRefCacheToSpace(name.str(), Runtime::Current()->GetHeap(), space,
                                              target_space);
    }
    default: {
      UNIMPLEMENTED(FATAL) << "Invalid type " << type;
      UNREACHABLE();
    }
  }
}

TEST_F(ModUnionTableTest, TestCardCache) {
  RunTest(ModUnionTableFactory::kTableTypeCardCache);
}

TEST_F(ModUnionTableTest, TestReferenceCache) {
  RunTest(ModUnionTableFactory::kTableTypeReferenceCache);
}

void ModUnionTableTest::RunTest(ModUnionTableFactory::TableType type) {
  Thread* const self = Thread::Current();
  ScopedObjectAccess soa(self);
  Runtime* const runtime = Runtime::Current();
  gc::Heap* const heap = runtime->GetHeap();
  // Use non moving space since moving GC don't necessarily have a primary free list space.
  auto* space = heap->GetNonMovingSpace();
  ResetClass();
  // Create another space that we can put references in.
  std::unique_ptr<space::DlMallocSpace> other_space(space::DlMallocSpace::Create(
      "other space", 128 * KB, 4 * MB, 4 * MB, /*can_move_objects=*/ false));
  ASSERT_TRUE(other_space.get() != nullptr);
  {
    ScopedThreadSuspension sts(self, ThreadState::kSuspended);
    ScopedSuspendAll ssa("Add image space");
    heap->AddSpace(other_space.get());
  }
  std::unique_ptr<ModUnionTable> table(ModUnionTableFactory::Create(
      type, space, other_space.get()));
  ASSERT_TRUE(table.get() != nullptr);
  // Create some fake objects and put the main space and dirty cards in the non moving space.
  auto* obj1 = AllocObjectArray(self, space, CardTable::kCardSize);
  ASSERT_TRUE(obj1 != nullptr);
  auto* obj2 = AllocObjectArray(self, space, CardTable::kCardSize);
  ASSERT_TRUE(obj2 != nullptr);
  auto* obj3 = AllocObjectArray(self, space, CardTable::kCardSize);
  ASSERT_TRUE(obj3 != nullptr);
  auto* obj4 = AllocObjectArray(self, space, CardTable::kCardSize);
  ASSERT_TRUE(obj4 != nullptr);
  // Dirty some cards.
  obj1->Set(0, obj2);
  obj2->Set(0, obj3);
  obj3->Set(0, obj4);
  obj4->Set(0, obj1);
  // Dirty some more cards to objects in another space.
  auto* other_space_ref1 = AllocObjectArray(self, other_space.get(), CardTable::kCardSize);
  ASSERT_TRUE(other_space_ref1 != nullptr);
  auto* other_space_ref2 = AllocObjectArray(self, other_space.get(), CardTable::kCardSize);
  ASSERT_TRUE(other_space_ref2 != nullptr);
  obj1->Set(1, other_space_ref1);
  obj2->Set(3, other_space_ref2);
  table->ProcessCards();
  std::set<mirror::Object*> visited_before;
  CollectVisitedVisitor collector_before(&visited_before);
  table->UpdateAndMarkReferences(&collector_before);
  // Check that we visited all the references in other spaces only.
  ASSERT_GE(visited_before.size(), 2u);
  ASSERT_TRUE(visited_before.find(other_space_ref1) != visited_before.end());
  ASSERT_TRUE(visited_before.find(other_space_ref2) != visited_before.end());
  // Verify that all the other references were visited.
  // obj1, obj2 cards should still be in mod union table since they have references to other
  // spaces.
  ASSERT_TRUE(table->ContainsCardFor(reinterpret_cast<uintptr_t>(obj1)));
  ASSERT_TRUE(table->ContainsCardFor(reinterpret_cast<uintptr_t>(obj2)));
  // obj3, obj4 don't have a reference to any object in the other space, their cards should have
  // been removed from the mod union table during UpdateAndMarkReferences.
  ASSERT_FALSE(table->ContainsCardFor(reinterpret_cast<uintptr_t>(obj3)));
  ASSERT_FALSE(table->ContainsCardFor(reinterpret_cast<uintptr_t>(obj4)));
  {
    // Currently no-op, make sure it still works however.
    ReaderMutexLock mu(self, *Locks::heap_bitmap_lock_);
    table->Verify();
  }
  // Verify that dump doesn't crash.
  std::ostringstream oss;
  table->Dump(oss);
  // Set all the cards, then verify.
  table->SetCards();
  // TODO: Check that the cards are actually set.
  for (auto* ptr = space->Begin(); ptr < AlignUp(space->End(), CardTable::kCardSize);
      ptr += CardTable::kCardSize) {
    ASSERT_TRUE(table->ContainsCardFor(reinterpret_cast<uintptr_t>(ptr)));
  }
  // Visit again and make sure the cards got cleared back to their expected state.
  std::set<mirror::Object*> visited_after;
  CollectVisitedVisitor collector_after(&visited_after);
  table->UpdateAndMarkReferences(&collector_after);
  // Check that we visited a superset after.
  for (auto* obj : visited_before) {
    ASSERT_TRUE(visited_after.find(obj) != visited_after.end()) << obj;
  }
  // Verify that the dump still works.
  std::ostringstream oss2;
  table->Dump(oss2);
  // Remove the space we added so it doesn't persist to the next test.
  ScopedThreadSuspension sts(self, ThreadState::kSuspended);
  ScopedSuspendAll ssa("Add image space");
  heap->RemoveSpace(other_space.get());
}

}  // namespace accounting
}  // namespace gc
}  // namespace art