/*

 * Copyright (c) 2019, SAP SE. All rights reserved.

 * Copyright (c) 2019, 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 "metaspace/metaspaceTestsCommon.hpp"

static int test_node_id = 100000; // start high to make it stick out in logs.

class VirtualSpaceNodeTest {

  // These counters are updated by the Node.

  SizeCounter _counter_reserved_words;

  SizeCounter _counter_committed_words;

  CommitLimiter _commit_limiter;

  VirtualSpaceNode* _node;

  // These are my checks and counters.

  const size_t _vs_word_size;

  const size_t _commit_limit;

  MetachunkList _root_chunks;

  void verify() const {

    ASSERT_EQ(_root_chunks.size() * metaspace::chklvl::MAX_CHUNK_WORD_SIZE,

              _node->used_words());

    ASSERT_GE(_commit_limit,                      _counter_committed_words.get());

    ASSERT_EQ(_commit_limiter.committed_words(),  _counter_committed_words.get());

    // Since we know _counter_committed_words serves our single node alone, the counter has to

    // match the number of bits in the node internal commit mask.

    ASSERT_EQ(_counter_committed_words.get(), _node->committed_words());

    ASSERT_EQ(_counter_reserved_words.get(), _vs_word_size);

    ASSERT_EQ(_counter_reserved_words.get(), _node->word_size());

  }

  void lock_and_verify_node() {

#ifdef ASSERT

    MutexLocker fcl(MetaspaceExpand_lock, Mutex::_no_safepoint_check_flag);

    _node->verify(true);

#endif

  }

  Metachunk* alloc_root_chunk() {

    verify();

    const bool node_is_full = _node->used_words() == _node->word_size();

    bool may_hit_commit_limit = _commit_limiter.possible_expansion_words() < MAX_CHUNK_WORD_SIZE;

    Metachunk* c = NULL;

    {

      MutexLocker fcl(MetaspaceExpand_lock, Mutex::_no_safepoint_check_flag);

      c = _node->allocate_root_chunk();

    }

    lock_and_verify_node();

    if (node_is_full) {

      EXPECT_NULL(c);

    } else {

      DEBUG_ONLY(c->verify(true);)

      EXPECT_NOT_NULL(c);

      EXPECT_TRUE(c->is_root_chunk());

      EXPECT_TRUE(c->is_free());

      EXPECT_EQ(c->word_size(), metaspace::chklvl::MAX_CHUNK_WORD_SIZE);

      if (!may_hit_commit_limit) {

        if (Settings::newborn_root_chunks_are_fully_committed()) {

          EXPECT_TRUE(c->is_fully_committed());

        } else {

          EXPECT_TRUE(c->is_fully_uncommitted());

        }

      }

      EXPECT_TRUE(_node->contains(c->base()));

      _root_chunks.add(c);

    }

    verify();

    return c;

  }

  bool commit_root_chunk(Metachunk* c, size_t request_commit_words) {

    verify();

    const size_t committed_words_before = _counter_committed_words.get();

    bool rc = c->ensure_committed(request_commit_words);

    verify();

    DEBUG_ONLY(c->verify(true);)

    lock_and_verify_node();

    if (rc == false) {

      // We must have hit the commit limit.

      EXPECT_GE(committed_words_before + request_commit_words, _commit_limit);

    } else {

      // We should not have hit the commit limit.

      EXPECT_LE(_counter_committed_words.get(), _commit_limit);

      // We do not know how much we really committed - maybe nothing if the

      // chunk had been committed before - but we know the numbers should have

      // risen or at least stayed equal.

      EXPECT_GE(_counter_committed_words.get(), committed_words_before);

      // The chunk should be as far committed as was requested

      EXPECT_GE(c->committed_words(), request_commit_words);

      // Zap committed portion.

      DEBUG_ONLY(zap_range(c->base(), c->committed_words());)

    }

    verify();

    return rc;

  } // commit_root_chunk

  void uncommit_chunk(Metachunk* c) {

    verify();

    const size_t committed_words_before = _counter_committed_words.get();

    const size_t available_words_before = _commit_limiter.possible_expansion_words();

    c->uncommit();

    DEBUG_ONLY(c->verify(true);)

    lock_and_verify_node();

    EXPECT_EQ(c->committed_words(), (size_t)0);

    // Commit counter should have gone down (by exactly the size of the chunk) if chunk

    // is larger than a commit granule.

    // For smaller chunks, we do not know, but at least we know the commit size should not

    // have gone up.

    if (c->word_size() >= Settings::commit_granule_words()) {

      EXPECT_EQ(_counter_committed_words.get(), committed_words_before - c->word_size());

      // also, commit number in commit limiter should have gone down, so we have more space

      EXPECT_EQ(_commit_limiter.possible_expansion_words(),

                available_words_before + c->word_size());

    } else {

      EXPECT_LE(_counter_committed_words.get(), committed_words_before);

    }

    verify();

  } // uncommit_chunk

  Metachunk* split_chunk_with_checks(Metachunk* c, chklvl_t target_level, MetachunkListCluster* freelist) {

    DEBUG_ONLY(c->verify(true);)

    const chklvl_t orig_level = c->level();

    assert(orig_level < target_level, "Sanity");

    DEBUG_ONLY(metaspace::chklvl::check_valid_level(target_level);)

    const int total_num_chunks_in_freelist_before = freelist->total_num_chunks();

    const size_t total_word_size_in_freelist_before = freelist->total_word_size();

   // freelist->print_on(tty);

    // Split...

    Metachunk* result = NULL;

    {

      MutexLocker fcl(MetaspaceExpand_lock, Mutex::_no_safepoint_check_flag);

      result = _node->split(target_level, c, freelist);

    }

    // freelist->print_on(tty);

    EXPECT_NOT_NULL(result);

    EXPECT_EQ(result->level(), target_level);

    EXPECT_TRUE(result->is_free());

    // ... check that we get the proper amount of splinters. For every chunk split we expect one

    // buddy chunk to appear of level + 1 (aka, half size).

    size_t expected_wordsize_increase = 0;

    int expected_num_chunks_increase = 0;

    for (chklvl_t l = orig_level + 1; l <= target_level; l ++) {

      expected_wordsize_increase += metaspace::chklvl::word_size_for_level(l);

      expected_num_chunks_increase ++;

    }

    const int total_num_chunks_in_freelist_after = freelist->total_num_chunks();

    const size_t total_word_size_in_freelist_after = freelist->total_word_size();

    EXPECT_EQ(total_num_chunks_in_freelist_after, total_num_chunks_in_freelist_before + expected_num_chunks_increase);

    EXPECT_EQ(total_word_size_in_freelist_after, total_word_size_in_freelist_before + expected_wordsize_increase);

    return result;

  } // end: split_chunk_with_checks

  Metachunk* merge_chunk_with_checks(Metachunk* c, chklvl_t expected_target_level, MetachunkListCluster* freelist) {

    const chklvl_t orig_level = c->level();

    assert(expected_target_level < orig_level, "Sanity");

    const int total_num_chunks_in_freelist_before = freelist->total_num_chunks();

    const size_t total_word_size_in_freelist_before = freelist->total_word_size();

    //freelist->print_on(tty);

    Metachunk* result = NULL;

    {

      MutexLocker fcl(MetaspaceExpand_lock, Mutex::_no_safepoint_check_flag);

      result = _node->merge(c, freelist);

    }

    EXPECT_NOT_NULL(result);

    EXPECT_TRUE(result->level() == expected_target_level);

    //freelist->print_on(tty);

    // ... check that we merged in the proper amount of chunks. For every decreased level

    // of the original chunk (each size doubling) we should see one buddy chunk swallowed up.

    size_t expected_wordsize_decrease = 0;

    int expected_num_chunks_decrease = 0;

    for (chklvl_t l = orig_level; l > expected_target_level; l --) {

      expected_wordsize_decrease += metaspace::chklvl::word_size_for_level(l);

      expected_num_chunks_decrease ++;

    }

    const int total_num_chunks_in_freelist_after = freelist->total_num_chunks();

    const size_t total_word_size_in_freelist_after = freelist->total_word_size();

    EXPECT_EQ(total_num_chunks_in_freelist_after, total_num_chunks_in_freelist_before - expected_num_chunks_decrease);

    EXPECT_EQ(total_word_size_in_freelist_after, total_word_size_in_freelist_before - expected_wordsize_decrease);

    return result;

  } // end: merge_chunk_with_checks

public:

  VirtualSpaceNodeTest(size_t vs_word_size, size_t commit_limit)

    : _counter_reserved_words(), _counter_committed_words(), _commit_limiter(commit_limit),

      _node(NULL), _vs_word_size(vs_word_size), _commit_limit(commit_limit)

  {

    {

      MutexLocker fcl(MetaspaceExpand_lock, Mutex::_no_safepoint_check_flag);

      _node = VirtualSpaceNode::create_node(test_node_id++,

                                            vs_word_size, &_commit_limiter,

                                            &_counter_reserved_words, &_counter_committed_words);

    }

    EXPECT_TRUE(_commit_limiter.possible_expansion_words() == _commit_limit);

    verify();

  }

  ~VirtualSpaceNodeTest() {

    delete _node;

  }

  void test_simple() {

    Metachunk* c = alloc_root_chunk();

    commit_root_chunk(c, Settings::commit_granule_words());

    commit_root_chunk(c, c->word_size());

    uncommit_chunk(c);

  }

  void test_exhaust_node() {

    Metachunk* c = NULL;

    bool rc = true;

    do {

      c = alloc_root_chunk();

      if (c != NULL) {

        rc = commit_root_chunk(c, c->word_size());

      }

    } while (c != NULL && rc);

  }

  void test_arbitrary_commits() {

    assert(_commit_limit >= _vs_word_size, "For this test no commit limit.");

    // Get a root chunk to have a committable region

    Metachunk* c = alloc_root_chunk();

    ASSERT_NOT_NULL(c);

    const address_range_t outer = { c->base(), c->word_size() };

    if (c->committed_words() > 0) {

      c->uncommit();

    }

    ASSERT_EQ(_node->committed_words(), (size_t)0);

    ASSERT_EQ(_counter_committed_words.get(), (size_t)0);

    TestMap testmap(c->word_size());

    assert(testmap.get_num_set() == 0, "Sanity");

    for (int run = 0; run < 1000; run ++) {

      const size_t committed_words_before = testmap.get_num_set();

      ASSERT_EQ(_commit_limiter.committed_words(), committed_words_before);

      ASSERT_EQ(_counter_committed_words.get(), committed_words_before);

      range_t range;

      calc_random_range(c->word_size(), &range, Settings::commit_granule_words());

      const size_t committed_words_in_range_before =

                   testmap.get_num_set(range.from, range.to);

      if (os::random() % 100 < 50) {

        bool rc = false;

        {

          MutexLocker fcl(MetaspaceExpand_lock, Mutex::_no_safepoint_check_flag);

          rc = _node->ensure_range_is_committed(c->base() + range.from, range.to - range.from);

        }

        // Test-zap

        zap_range(c->base() + range.from, range.to - range.from);

        // We should never reach commit limit since it is as large as the whole area.

        ASSERT_TRUE(rc);

        testmap.set_range(range.from, range.to);

      } else {

        {

          MutexLocker fcl(MetaspaceExpand_lock, Mutex::_no_safepoint_check_flag);

          _node->uncommit_range(c->base() + range.from, range.to - range.from);

        }

        testmap.clear_range(range.from, range.to);

      }

      const size_t committed_words_after = testmap.get_num_set();

      ASSERT_EQ(_commit_limiter.committed_words(), committed_words_after);

      ASSERT_EQ(_counter_committed_words.get(), committed_words_after);

      verify();

    }

  }

  // Helper function for test_splitting_chunks_1

  static void check_chunk_is_committed_at_least_up_to(const Metachunk* c, size_t& word_size) {

    if (word_size >= c->word_size()) {

      EXPECT_TRUE(c->is_fully_committed());

      word_size -= c->word_size();

    } else {

      EXPECT_EQ(c->committed_words(), word_size);

      word_size = 0; // clear remaining size if there is.

    }

  }

  void test_split_and_merge_chunks() {

    assert(_commit_limit >= _vs_word_size, "No commit limit here pls");

    // Allocate a root chunk and commit a random part of it. Then repeatedly split

    // it and merge it back together; observe the committed regions of the split chunks.

    Metachunk* c = alloc_root_chunk();

    if (c->committed_words() > 0) {

      c->uncommit();

    }

    // To capture split-off chunks. Note: it is okay to use this here as a temp object.

    MetachunkListCluster freelist;

    const int granules_per_root_chunk = (int)(c->word_size() / Settings::commit_granule_words());

    for (int granules_to_commit = 0; granules_to_commit < granules_per_root_chunk; granules_to_commit ++) {

      const size_t words_to_commit = Settings::commit_granule_words() * granules_to_commit;

      c->ensure_committed(words_to_commit);

      ASSERT_EQ(c->committed_words(), words_to_commit);

      ASSERT_EQ(_counter_committed_words.get(), words_to_commit);

      ASSERT_EQ(_commit_limiter.committed_words(), words_to_commit);

      const size_t committed_words_before = c->committed_words();

      verify();

      for (chklvl_t target_level = LOWEST_CHUNK_LEVEL + 1;

           target_level <= HIGHEST_CHUNK_LEVEL; target_level ++) {

        // Split:

        Metachunk* c2 = split_chunk_with_checks(c, target_level, &freelist);

        c2->set_in_use();

        // Split smallest leftover chunk.

        if (c2->level() < HIGHEST_CHUNK_LEVEL) {

          Metachunk* c3 = freelist.remove_first(c2->level());

          ASSERT_NOT_NULL(c3); // Must exist since c2 must have a splinter buddy now.

          Metachunk* c4 = split_chunk_with_checks(c3, HIGHEST_CHUNK_LEVEL, &freelist);

          c4->set_in_use();

          // Merge it back. We expect this to merge up to c2's level, since c2 is in use.

          c4->set_free();

          Metachunk* c5 = merge_chunk_with_checks(c4, c2->level(), &freelist);

          ASSERT_NOT_NULL(c5);

          freelist.add(c5);

        }

        // Merge c2 back.

        c2->set_free();

        merge_chunk_with_checks(c2, LOWEST_CHUNK_LEVEL, &freelist);

        // After all this splitting and combining committed size should not have changed.

        ASSERT_EQ(c2->committed_words(), committed_words_before);

      }

    }

  } // end: test_splitting_chunks

};

// Note: we unfortunately need TEST_VM even though the system tested

// should be pretty independent since we need things like os::vm_page_size()

// which in turn need OS layer initialization.

TEST_VM(metaspace, virtual_space_node_test_1) {

  VirtualSpaceNodeTest test(metaspace::chklvl::MAX_CHUNK_WORD_SIZE,

      metaspace::chklvl::MAX_CHUNK_WORD_SIZE);

  test.test_simple();