/*

 * Copyright (c) 2018, Oracle and/or its affiliates. All rights reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 */

#include "precompiled.hpp"

#include "gc/shared/oopStorage.inline.hpp"

#include "gc/shared/oopStorageParState.inline.hpp"

#include "gc/shared/workgroup.hpp"

#include "memory/allocation.inline.hpp"

#include "memory/resourceArea.hpp"

#include "metaprogramming/conditional.hpp"

#include "metaprogramming/enableIf.hpp"

#include "runtime/handles.inline.hpp"

#include "runtime/interfaceSupport.hpp"

#include "runtime/mutex.hpp"

#include "runtime/mutexLocker.hpp"

#include "runtime/thread.hpp"

#include "runtime/vm_operations.hpp"

#include "runtime/vmThread.hpp"

#include "utilities/align.hpp"

#include "utilities/ostream.hpp"

#include "utilities/quickSort.hpp"

#include "unittest.hpp"

// --- FIXME: Disable some tests on 32bit Windows, because SafeFetch

//     (which is used by allocation_status) doesn't currently provide

//     protection in the context where gtests are run; see JDK-8185734.

#ifdef _WIN32

#define DISABLE_GARBAGE_ALLOCATION_STATUS_TESTS

#endif

// Access storage internals.

class OopStorage::TestAccess : public AllStatic {

public:

  typedef OopStorage::Block Block;

  typedef OopStorage::BlockList BlockList;

  static BlockList& active_list(OopStorage& storage) {

    return storage._active_list;

  }

  static BlockList& allocate_list(OopStorage& storage) {

    return storage._allocate_list;

  }

  static const BlockList& allocate_list(const OopStorage& storage) {

    return storage._allocate_list;

  }

  static Mutex* allocate_mutex(const OopStorage& storage) {

    return storage._allocate_mutex;

  }

  static bool reduce_deferred_updates(OopStorage& storage) {

    return storage.reduce_deferred_updates();

  }

  static bool block_is_empty(const Block& block) {

    return block.is_empty();

  }

  static bool block_is_full(const Block& block) {

    return block.is_full();

  }

  static unsigned block_allocation_count(const Block& block) {

    uintx bitmask = block.allocated_bitmask();

    unsigned count = 0;

    for ( ; bitmask != 0; bitmask >>= 1) {

      if ((bitmask & 1) != 0) {

        ++count;

      }

    }

    return count;

  }

  static size_t memory_per_block() {

    return Block::allocation_size();

  }

};

typedef OopStorage::TestAccess TestAccess;

// --- FIXME: Should be just Block, but that collides with opto Block

//     when building with precompiled headers.  There really should be

//     an opto namespace.

typedef TestAccess::Block OopBlock;

// --- FIXME: Similarly, this typedef collides with opto BlockList.

// typedef TestAccess::BlockList BlockList;

// Using EXPECT_EQ can't use NULL directly. Otherwise AIX build breaks.

const OopBlock* const NULL_BLOCK = NULL;

static size_t list_length(const TestAccess::BlockList& list) {

  size_t result = 0;

  for (const OopBlock* block = list.chead();

       block != NULL;

       block = list.next(*block)) {

    ++result;

  }

  return result;

}

static void clear_list(TestAccess::BlockList& list) {

  OopBlock* next;

  for (OopBlock* block = list.head(); block != NULL; block = next) {

    next = list.next(*block);

    list.unlink(*block);

  }

}

static bool is_list_empty(const TestAccess::BlockList& list) {

  return list.chead() == NULL;

}

static bool process_deferred_updates(OopStorage& storage) {

  MutexLockerEx ml(TestAccess::allocate_mutex(storage), Mutex::_no_safepoint_check_flag);

  bool result = false;

  while (TestAccess::reduce_deferred_updates(storage)) {

    result = true;

  }

  return result;

}

static void release_entry(OopStorage& storage, oop* entry, bool process_deferred = true) {

  *entry = NULL;

  storage.release(entry);

  if (process_deferred) {

    process_deferred_updates(storage);

  }

}

static size_t empty_block_count(const OopStorage& storage) {

  const TestAccess::BlockList& list = TestAccess::allocate_list(storage);

  size_t count = 0;

  for (const OopBlock* block = list.ctail();

       (block != NULL) && block->is_empty();

       ++count, block = list.prev(*block))

  {}

  return count;

}

class OopStorageTest : public ::testing::Test {

public:

  OopStorageTest();

  ~OopStorageTest();

  Mutex _allocate_mutex;

  Mutex _active_mutex;

  OopStorage _storage;

  static const int _active_rank = Mutex::leaf - 1;

  static const int _allocate_rank = Mutex::leaf;

  class CountingIterateClosure;

  template<bool is_const> class VM_CountAtSafepoint;

};

OopStorageTest::OopStorageTest() :

  _allocate_mutex(_allocate_rank,

                  "test_OopStorage_allocate",

                  false,

                  Mutex::_safepoint_check_never),

  _active_mutex(_active_rank,

                "test_OopStorage_active",

                false,

                Mutex::_safepoint_check_never),

  _storage("Test Storage", &_allocate_mutex, &_active_mutex)

{ }

OopStorageTest::~OopStorageTest() {

  clear_list(TestAccess::allocate_list(_storage));

  clear_list(TestAccess::active_list(_storage));

}

class OopStorageTestWithAllocation : public OopStorageTest {

public:

  OopStorageTestWithAllocation();

  static const size_t _max_entries = 1000;

  oop* _entries[_max_entries];

  class VM_DeleteBlocksAtSafepoint;

};

OopStorageTestWithAllocation::OopStorageTestWithAllocation() {

  for (size_t i = 0; i < _max_entries; ++i) {

    _entries[i] = _storage.allocate();

    EXPECT_TRUE(_entries[i] != NULL);

    EXPECT_EQ(i + 1, _storage.allocation_count());

  }

};

const size_t OopStorageTestWithAllocation::_max_entries;

class OopStorageTestWithAllocation::VM_DeleteBlocksAtSafepoint

  : public VM_GTestExecuteAtSafepoint {

public:

  VM_DeleteBlocksAtSafepoint(OopStorage* storage) : _storage(storage) {}

  void doit() {

    _storage->delete_empty_blocks_safepoint();

  }

private:

  OopStorage* _storage;

};

static bool is_allocate_list_sorted(const OopStorage& storage) {

  // The allocate_list isn't strictly sorted.  Rather, all empty

  // blocks are segregated to the end of the list.

  const TestAccess::BlockList& list = TestAccess::allocate_list(storage);

  const OopBlock* block = list.ctail();

  for ( ; (block != NULL) && block->is_empty(); block = list.prev(*block)) {}

  for ( ; block != NULL; block = list.prev(*block)) {

    if (block->is_empty()) {

      return false;

    }

  }

  return true;

}

static size_t total_allocation_count(const TestAccess::BlockList& list) {

  size_t total_count = 0;

  for (const OopBlock* block = list.chead();

       block != NULL;

       block = list.next(*block)) {

    total_count += TestAccess::block_allocation_count(*block);

  }

  return total_count;

}

TEST_VM_F(OopStorageTest, allocate_one) {

  EXPECT_TRUE(is_list_empty(TestAccess::active_list(_storage)));

  EXPECT_TRUE(is_list_empty(TestAccess::allocate_list(_storage)));

  oop* ptr = _storage.allocate();

  EXPECT_TRUE(ptr != NULL);

  EXPECT_EQ(1u, _storage.allocation_count());

  EXPECT_EQ(1u, list_length(TestAccess::active_list(_storage)));

  EXPECT_EQ(1u, _storage.block_count());

  EXPECT_EQ(1u, list_length(TestAccess::allocate_list(_storage)));

  EXPECT_EQ(0u, empty_block_count(_storage));

  const OopBlock* block = TestAccess::allocate_list(_storage).chead();

  EXPECT_NE(block, (OopBlock*)NULL);

  EXPECT_EQ(block, (TestAccess::active_list(_storage).chead()));

  EXPECT_FALSE(TestAccess::block_is_empty(*block));

  EXPECT_FALSE(TestAccess::block_is_full(*block));

  EXPECT_EQ(1u, TestAccess::block_allocation_count(*block));

  release_entry(_storage, ptr);

  EXPECT_EQ(0u, _storage.allocation_count());

  EXPECT_EQ(1u, list_length(TestAccess::active_list(_storage)));

  EXPECT_EQ(1u, _storage.block_count());

  EXPECT_EQ(1u, list_length(TestAccess::allocate_list(_storage)));

  EXPECT_EQ(1u, empty_block_count(_storage));

  const OopBlock* new_block = TestAccess::allocate_list(_storage).chead();

  EXPECT_EQ(block, new_block);

  EXPECT_EQ(block, (TestAccess::active_list(_storage).chead()));

  EXPECT_TRUE(TestAccess::block_is_empty(*block));

  EXPECT_FALSE(TestAccess::block_is_full(*block));

  EXPECT_EQ(0u, TestAccess::block_allocation_count(*block));

}

TEST_VM_F(OopStorageTest, allocation_count) {

  static const size_t max_entries = 1000;

  oop* entries[max_entries];

  TestAccess::BlockList& active_list = TestAccess::active_list(_storage);

  TestAccess::BlockList& allocate_list = TestAccess::allocate_list(_storage);

  EXPECT_TRUE(is_list_empty(active_list));

  EXPECT_EQ(0u, _storage.block_count());

  EXPECT_TRUE(is_list_empty(allocate_list));

  size_t allocated = 0;

  for ( ; allocated < max_entries; ++allocated) {

    EXPECT_EQ(allocated, _storage.allocation_count());

    if (!is_list_empty(active_list)) {

      EXPECT_EQ(1u, list_length(active_list));

      EXPECT_EQ(1u, _storage.block_count());

      const OopBlock& block = *active_list.chead();

      EXPECT_EQ(allocated, TestAccess::block_allocation_count(block));

      if (TestAccess::block_is_full(block)) {

        break;

      } else {

        EXPECT_FALSE(is_list_empty(allocate_list));

        EXPECT_EQ(&block, allocate_list.chead());

      }

    }

    entries[allocated] = _storage.allocate();

  }

  EXPECT_EQ(allocated, _storage.allocation_count());

  EXPECT_EQ(1u, list_length(active_list));

  EXPECT_EQ(1u, _storage.block_count());

  EXPECT_TRUE(is_list_empty(allocate_list));

  const OopBlock& block = *active_list.chead();

  EXPECT_TRUE(TestAccess::block_is_full(block));

  EXPECT_EQ(allocated, TestAccess::block_allocation_count(block));

  for (size_t i = 0; i < allocated; ++i) {

    release_entry(_storage, entries[i]);

    size_t remaining = allocated - (i + 1);

    EXPECT_EQ(remaining, TestAccess::block_allocation_count(block));

    EXPECT_EQ(remaining, _storage.allocation_count());

    EXPECT_FALSE(is_list_empty(allocate_list));

  }

}

TEST_VM_F(OopStorageTest, allocate_many) {

  static const size_t max_entries = 1000;

  oop* entries[max_entries];

  TestAccess::BlockList& active_list = TestAccess::active_list(_storage);

  TestAccess::BlockList& allocate_list = TestAccess::allocate_list(_storage);

  EXPECT_EQ(0u, empty_block_count(_storage));

  entries[0] = _storage.allocate();

  ASSERT_TRUE(entries[0] != NULL);

  EXPECT_EQ(1u, list_length(active_list));

  EXPECT_EQ(1u, _storage.block_count());

  EXPECT_EQ(1u, list_length(allocate_list));

  EXPECT_EQ(0u, empty_block_count(_storage));

  const OopBlock* block = active_list.chead();

  EXPECT_EQ(1u, TestAccess::block_allocation_count(*block));

  EXPECT_EQ(block, allocate_list.chead());

  for (size_t i = 1; i < max_entries; ++i) {

    entries[i] = _storage.allocate();

    EXPECT_EQ(i + 1, _storage.allocation_count());

    ASSERT_TRUE(entries[i] != NULL);

    EXPECT_EQ(0u, empty_block_count(_storage));

    if (block == NULL) {

      ASSERT_FALSE(is_list_empty(allocate_list));

      EXPECT_EQ(1u, list_length(allocate_list));

      block = allocate_list.chead();

      EXPECT_EQ(1u, TestAccess::block_allocation_count(*block));

      EXPECT_EQ(block, active_list.chead());

    } else if (TestAccess::block_is_full(*block)) {

      EXPECT_TRUE(is_list_empty(allocate_list));

      block = NULL;

    } else {

      EXPECT_FALSE(is_list_empty(allocate_list));

      EXPECT_EQ(block, allocate_list.chead());

      EXPECT_EQ(block, active_list.chead());

    }

  }

  if (block != NULL) {

    EXPECT_NE(0u, TestAccess::block_allocation_count(*block));

    EXPECT_FALSE(is_list_empty(allocate_list));

    EXPECT_EQ(block, allocate_list.chead());

    EXPECT_EQ(block, active_list.chead());

  }

  size_t active_count = list_length(active_list);

  for (size_t i = 0; i < max_entries; ++i) {

    release_entry(_storage, entries[i]);

    EXPECT_TRUE(is_allocate_list_sorted(_storage));

    EXPECT_EQ(max_entries - (i + 1), total_allocation_count(active_list));

  }

  EXPECT_EQ(list_length(active_list), list_length(allocate_list));

  EXPECT_EQ(list_length(active_list), _storage.block_count());

  EXPECT_EQ(list_length(active_list), empty_block_count(_storage));

  for (const OopBlock* block = allocate_list.chead();

       block != NULL;

       block = allocate_list.next(*block)) {

    EXPECT_TRUE(TestAccess::block_is_empty(*block));

  }

}

TEST_VM_F(OopStorageTestWithAllocation, random_release) {

  static const size_t step = 11;

  ASSERT_NE(0u, _max_entries % step); // max_entries and step are mutually prime

  EXPECT_EQ(0u, empty_block_count(_storage));

  TestAccess::BlockList& active_list = TestAccess::active_list(_storage);

  TestAccess::BlockList& allocate_list = TestAccess::allocate_list(_storage);

  EXPECT_EQ(_max_entries, total_allocation_count(active_list));

  EXPECT_GE(1u, list_length(allocate_list));

  // Release all entries in "random" order.

  size_t released = 0;

  for (size_t i = 0; released < _max_entries; i = (i + step) % _max_entries) {

    if (_entries[i] != NULL) {

      release_entry(_storage, _entries[i]);

      _entries[i] = NULL;

      ++released;

      EXPECT_EQ(_max_entries - released, total_allocation_count(active_list));

      EXPECT_TRUE(is_allocate_list_sorted(_storage));

    }

  }

  EXPECT_EQ(list_length(active_list), list_length(allocate_list));

  EXPECT_EQ(list_length(active_list), _storage.block_count());

  EXPECT_EQ(0u, total_allocation_count(active_list));

  EXPECT_EQ(list_length(allocate_list), empty_block_count(_storage));

}

TEST_VM_F(OopStorageTestWithAllocation, random_allocate_release) {

  static const size_t release_step = 11;

  static const size_t allocate_step = 5;

  ASSERT_NE(0u, _max_entries % release_step); // max_entries and step are mutually prime

  EXPECT_EQ(0u, empty_block_count(_storage));

  TestAccess::BlockList& active_list = TestAccess::active_list(_storage);

  TestAccess::BlockList& allocate_list = TestAccess::allocate_list(_storage);

  EXPECT_EQ(_max_entries, total_allocation_count(active_list));

  EXPECT_GE(1u, list_length(allocate_list));

  // Release all entries in "random" order, "randomly" interspersed

  // with additional allocations.

  size_t released = 0;

  size_t total_released = 0;

  for (size_t i = 0; released < _max_entries; i = (i + release_step) % _max_entries) {

    if (_entries[i] != NULL) {

      release_entry(_storage, _entries[i]);

      _entries[i] = NULL;

      ++released;

      ++total_released;

      EXPECT_EQ(_max_entries - released, total_allocation_count(active_list));

      EXPECT_TRUE(is_allocate_list_sorted(_storage));

      if (total_released % allocate_step == 0) {

        _entries[i] = _storage.allocate();

        --released;

        EXPECT_EQ(_max_entries - released, total_allocation_count(active_list));

        EXPECT_TRUE(is_allocate_list_sorted(_storage));

      }

    }

  }

  EXPECT_EQ(list_length(active_list), list_length(allocate_list));

  EXPECT_EQ(list_length(active_list), _storage.block_count());

  EXPECT_EQ(0u, total_allocation_count(active_list));

  EXPECT_EQ(list_length(allocate_list), empty_block_count(_storage));

}

template<bool sorted>

class OopStorageTestBlockRelease : public OopStorageTestWithAllocation {

public:

  void SetUp() {

    size_t nrelease = _max_entries / 2;

    oop** to_release = NEW_C_HEAP_ARRAY(oop*, nrelease, mtInternal);

    for (size_t i = 0; i < nrelease; ++i) {

      to_release[i] = _entries[2 * i];

      *to_release[i] = NULL;

    }

    if (sorted) {

      QuickSort::sort(to_release, nrelease, PointerCompare(), false);

    }

    _storage.release(to_release, nrelease);

    EXPECT_EQ(_max_entries - nrelease, _storage.allocation_count());

    for (size_t i = 0; i < nrelease; ++i) {

      release_entry(_storage, _entries[2 * i + 1], false);

      EXPECT_EQ(_max_entries - nrelease - (i + 1), _storage.allocation_count());

    }

    EXPECT_TRUE(process_deferred_updates(_storage));

    EXPECT_EQ(_storage.block_count(), empty_block_count(_storage));

    FREE_C_HEAP_ARRAY(oop*, to_release);

  }

  struct PointerCompare {

    int operator()(const void* p, const void* q) const {

      return (p < q) ? -1 : int(p != q);

    }

  };

};

typedef OopStorageTestBlockRelease<true> OopStorageTestBlockReleaseSorted;

typedef OopStorageTestBlockRelease<false> OopStorageTestBlockReleaseUnsorted;

TEST_VM_F(OopStorageTestBlockReleaseSorted, block_release) {}

TEST_VM_F(OopStorageTestBlockReleaseUnsorted, block_release) {}

#ifndef DISABLE_GARBAGE_ALLOCATION_STATUS_TESTS

TEST_VM_F(OopStorageTest, invalid_pointer) {

  {

    char* mem = NEW_C_HEAP_ARRAY(char, 1000, mtInternal);

    oop* ptr = reinterpret_cast<oop*>(align_down(mem + 250, sizeof(oop)));

    // Predicate returns false for some malloc'ed block.

    EXPECT_EQ(OopStorage::INVALID_ENTRY, _storage.allocation_status(ptr));

    FREE_C_HEAP_ARRAY(char, mem);

  }