/*

 * 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"

// See spaceManager.cpp : needed for predicting commit sizes.

namespace metaspace {

  extern size_t get_raw_allocation_word_size(size_t net_word_size);

}

class SpaceManagerTest {

  // One global chunk manager, with an assiociated global virtual space list as backing,

  // and a number of space managers feeding from that manager in parallel.

  CommitLimiter _commit_limiter;

  const size_t _avg_occupancy;

  VirtualSpaceList* _vslist;

  ChunkManager* _cm;

  const ChunkAllocSequence* _alloc_sequence;

  const int _num_spaces;

  size_t _rss_at_start;

  size_t _rss_at_end;

  size_t _rss_after_cleanup;

  // A little test bed holding one SpaceManager and its lock

  //  and keeping track of its allocations.

  struct SpaceManagerTestBed : public CHeapObj<mtInternal> {

    Mutex* _lock;

    SpaceManager* _sm;

    int _index;

    // We keep track of individual allocations. Note that this adds

    // 256K per instance of SpaceManagerTestBed.

    struct allocation_t {

      MetaWord* p;

      size_t word_size;

    };

    static const int _max_allocations = 0x4000;

    int _num_allocations;

    size_t _words_allocated;

    allocation_t _allocations[_max_allocations];

    // Note: used counter contains "used" from the chunk perspective, which is

    // used + freelist + alignment corrections. This does not translate 1:1 to

    // _words_allocated, so this is difficult to test.

    SizeAtomicCounter _used_counter;

  public:

    SpaceManager* sm() { return _sm; }

    SpaceManagerTestBed(int index, ChunkManager* cm, const ChunkAllocSequence* alloc_sequence)

      : _lock(NULL), _sm(NULL), _index(index), _num_allocations(0), _words_allocated(0)

    {

      memset(_allocations, 0, sizeof(_allocations));

      _lock = new Mutex(Monitor::native, "gtest-SpaceManagerTestBed-lock", false, Monitor::_safepoint_check_never);

      {

        // Pull lock during space creation, since this is what happens in the VM too

        // (see ClassLoaderData::metaspace_non_null(), which we mimick here).

        MutexLocker ml(_lock,  Mutex::_no_safepoint_check_flag);

        _sm = new SpaceManager(cm, alloc_sequence, _lock, &_used_counter, "gtest-SpaceManagerTestBed-sm", false);

      }

    }

    ~SpaceManagerTestBed() {

 //     EXPECT_EQ(_used_counter.get(), _words_allocated);

      // Iterate thru all allocation records and test content first.

      for (int i = 0; i < _num_allocations; i ++) {

        const allocation_t* al = _allocations + i;

        EXPECT_TRUE(al->p == NULL || check_marked_range(al->p, (uintx)this, al->word_size));

      }

      // Delete SpaceManager. That should clean up all metaspace.

      delete _sm;

      delete _lock;

    }

    size_t words_allocated() const        { return _words_allocated; }

    int num_allocations() const           { return _num_allocations; }

    int index() const                     { return _index; }

    bool is_full() const                  { return _num_allocations == _max_allocations; }

    bool is_empty() const                 { return _num_allocations == 0; }

    // Allocate from space. Returns NULL if either the bed is full or if the allocation

    // itself failed.

    MetaWord* allocate_and_test(size_t word_size) {

      if (is_full()) {

        return NULL;

      }

      MetaWord* p = _sm->allocate(word_size);

      if (p != NULL) {

        EXPECT_TRUE(is_aligned(p, sizeof(void*)));

        mark_range(p, (uintx)this, word_size);

        // Remember this allocation.

        allocation_t* al = _allocations + _num_allocations;

        al->p = p; al->word_size = word_size;

        _num_allocations ++;

        _words_allocated += word_size;

 //       EXPECT_EQ(_used_counter.get(), _words_allocated);

      }

      return p;

    }

    // Deallocate the last allocation done.

    void deallocate_last() {

      assert(_num_allocations > 0, "Sanity");

      allocation_t* al = &_allocations[_num_allocations - 1];

      _sm->deallocate(al->p, al->word_size);

      al->p = NULL;

      _num_allocations --;

    }

    // Deallocate a random single allocation.

    void deallocate_random() {

      if (_num_allocations > 0) {

        int idx = os::random() % _num_allocations;

        allocation_t* al = _allocations + idx;

        if (al->p == NULL) {

          // already deallocated? Should still have its old word size set

          assert(al->word_size > 0, "Sanity");

        } else {

          _sm->deallocate(al->p, al->word_size);

          al->p = NULL; // but leave word_size, see above

        }

      }

    }

  }; // End: SpaceManagerTestBed

  SpaceManagerTestBed** _testbeds;

  SpaceManagerTestBed* testbed_at(int index) {

    assert(index < _num_spaces, "Sanity");

    // Create on the fly if necessary.

    if (_testbeds[index] == NULL) {

      _testbeds[index] = new SpaceManagerTestBed(index, _cm, _alloc_sequence);

    }

    return _testbeds[index];

  }

  SpaceManagerTestBed* next_testbed(SpaceManagerTestBed* bed) {

    int i = bed->index() + 1;

    if (i == _num_spaces) {

      i = 0;

    }

    return testbed_at(i);

  }

  SpaceManagerTestBed* get_random_testbed() {

    const int index = os::random() % _num_spaces;

    return testbed_at(index);

  }

  SpaceManagerTestBed* get_random_matching_testbed(bool should_be_empty) {

    const int start_index = os::random() % _num_spaces;

    int i = start_index;

    do {

      SpaceManagerTestBed* bed = testbed_at(i);

      if ((should_be_empty && bed->words_allocated() == 0) ||

          (!should_be_empty && bed->words_allocated() > 0)) {

        return bed;

      }

      i ++;

      if (i == _num_spaces) {

        i = 0;

      }

    } while (i != start_index);

    return NULL;

  }

  SpaceManagerTestBed* get_random_nonempty_testbed() {

    return get_random_matching_testbed(false);

  }

  SpaceManagerTestBed* get_random_empty_testbed() {

    return get_random_matching_testbed(true);

  }

  MetaWord* alloc_from_testbed(SpaceManagerTestBed* bed, size_t word_size) {

    MetaWord* p = bed->allocate_and_test(word_size);

    if (p == NULL) {

      // Getting NULL back may mean:

      // - testbed is full.

      // - We hit the commit limit.

      if (!bed->is_full()) {

        EXPECT_LT(_commit_limiter.possible_expansion_words(),

                  metaspace::get_raw_allocation_word_size(word_size));

      }

    }

    return p;

  }

  void delete_testbed_at(int index) {

    delete _testbeds[index];

    _testbeds[index] = NULL;

  }

  void delete_testbed(SpaceManagerTestBed* bed) {

    assert(_testbeds[bed->index()] == bed, "Sanity");

    _testbeds[bed->index()] = NULL;

    delete bed;

  }

  // Allocate multiple times random sizes from a single spacemanager.

  // Will stop allocation prematurely if per-space max is reached or if commit limit is reached.

  bool allocate_multiple_random(SpaceManagerTestBed* bed, int num_allocations, RandSizeGenerator* rgen) {

    for (int n = 0; n < num_allocations; n ++) {

      const size_t alloc_size = rgen->get();

      if (alloc_from_testbed(bed, alloc_size) == NULL) {

        return false;

      }

    }

    return true;

  }

  int get_total_number_of_allocations() const {

    int sum = 0;

    for (int i = 0; i < _num_spaces; i ++) {

      if (_testbeds[i] != NULL) {

        sum += _testbeds[i]->num_allocations();

      }

    }

    return sum;

  }

  size_t get_total_words_allocated() const {

    size_t sum = 0;

    for (int i = 0; i < _num_spaces; i ++) {

      if (_testbeds[i] != NULL) {

        sum += _testbeds[i]->words_allocated();

      }

    }

    return sum;

  }

  // Allocate until you reach avg occupancy, hover there by allocating/freeing.

  void test_hover(int num_cycles, int avg_allocs_per_space_manager, RandSizeGenerator* rgen,

                  bool exercise_reclaim, bool exercise_dealloc) {

    int alloc_cycles = 0;

    int free_cycles = 0;

    for (int cyc = 0; cyc < num_cycles; cyc ++) {

      if (get_total_words_allocated() < _avg_occupancy) {

        SpaceManagerTestBed* bed = get_random_testbed();

        if (allocate_multiple_random(bed, avg_allocs_per_space_manager, rgen)) {

          alloc_cycles ++;

        }

      } else {

        SpaceManagerTestBed* bed = get_random_nonempty_testbed();

        if (bed != NULL) {

          free_cycles ++;

          delete_testbed(bed);

        }

      }

      if (exercise_dealloc) {

        if (os::random() % 100 > 95) {

          SpaceManagerTestBed* bed = get_random_nonempty_testbed();

          if (bed != NULL) {

            bed->deallocate_random();

          }

        }

      }

      if (cyc % 100 == 0) {

        const size_t committed_before = _vslist->committed_words();

        if (exercise_reclaim) {

          _cm->wholesale_reclaim();

        }

        LOG("cyc: %d (a %d f %d) allocated: " SIZE_FORMAT ", committed " SIZE_FORMAT "->" SIZE_FORMAT ".",

            cyc, alloc_cycles, free_cycles, get_total_words_allocated(), committed_before, _vslist->committed_words());

      }

    }

//    _vslist->print_on(tty);

//    _cm->print_on(tty);

  } // end: test_hover

  // Allocate until you reach avg occupancy, then drain completely. Repeat.

  void test_wave(int num_cycles, int avg_allocs_per_space_manager, RandSizeGenerator* rgen,

                 bool exercise_reclaim, bool exercise_dealloc) {

    bool rising = true;

    int num_waves = 0;

    for (int cyc = 0; cyc < num_cycles; cyc ++) {

      if (rising) {

        num_waves ++;

        if (get_total_words_allocated() >= _avg_occupancy) {

          rising = false;

        } else {

          SpaceManagerTestBed* bed = get_random_testbed();

          allocate_multiple_random(bed, avg_allocs_per_space_manager, rgen);

        }

      } else {

        SpaceManagerTestBed* bed = get_random_nonempty_testbed();

        if (bed == NULL) {

          EXPECT_EQ(get_total_words_allocated(), (size_t)0);

          rising = true;

        } else {

          delete_testbed(bed);

        }

      }

      if (exercise_dealloc) {

        if (os::random() % 100 > 95) {

          SpaceManagerTestBed* bed = get_random_nonempty_testbed();

          if (bed != NULL) {

            bed->deallocate_random();

          }

        }

      }

      if (cyc % 100 == 0) {

        LOG("cyc: %d num waves: %d num allocations: %d , words allocated: " SIZE_FORMAT ", committed " SIZE_FORMAT ".",

            cyc, num_waves, get_total_number_of_allocations(), get_total_words_allocated(), _vslist->committed_words());

        const size_t committed_before = _vslist->committed_words();

        if (exercise_reclaim) {

          _cm->wholesale_reclaim();

          LOG(".. reclaim: " SIZE_FORMAT "->" SIZE_FORMAT ".", committed_before, _vslist->committed_words());

        }

      }

    }

//    _vslist->print_on(tty);

    //    _cm->print_on(tty);

  } // end: test_wave

  static void check_sm_stat_is_empty(sm_stats_t& stat) {

    in_use_chunk_stats_t totals = stat.totals();

    EXPECT_EQ(totals.word_size, (size_t)0);

    EXPECT_EQ(totals.committed_words, (size_t)0);

    EXPECT_EQ(totals.used_words, (size_t)0);

    EXPECT_EQ(totals.free_words, (size_t)0);

    EXPECT_EQ(totals.waste_words, (size_t)0);

  }

  static void check_sm_stat_is_consistent(sm_stats_t& stat) {

    in_use_chunk_stats_t totals = stat.totals();

    EXPECT_GE(totals.word_size, totals.committed_words);

    EXPECT_EQ(totals.committed_words, totals.used_words + totals.free_words + totals.waste_words);

    EXPECT_GE(totals.used_words, stat.free_blocks_word_size);

  }

  void test_total_statistics() {

    sm_stats_t totals1;

    check_sm_stat_is_empty(totals1);

    sm_stats_t totals2;

    check_sm_stat_is_empty(totals1);

    for (int i = 0; i < _num_spaces; i ++) {

      if (_testbeds[i] != NULL) {

        sm_stats_t stat;

        _testbeds[i]->_sm->add_to_statistics(&stat);

        check_sm_stat_is_consistent(stat);

        DEBUG_ONLY(stat.verify());

        _testbeds[i]->_sm->add_to_statistics(&totals1);

        check_sm_stat_is_consistent(totals1);

        totals2.add(stat);

        check_sm_stat_is_consistent(totals2);

      }

    }

    EXPECT_EQ(totals1.totals().used_words,

              totals2.totals().used_words);

  }

public:

  void run_test(int num_cycles, int avg_allocs_per_space_manager, RandSizeGenerator* rgen,

            bool exercise_reclaim, bool exercise_dealloc) {

    LOG("hover test");

    test_hover(num_cycles, avg_allocs_per_space_manager, rgen, exercise_reclaim, exercise_dealloc);

    test_total_statistics();

    LOG("wave test");

    test_wave(num_cycles, avg_allocs_per_space_manager, rgen, exercise_reclaim, exercise_dealloc);

    test_total_statistics();

  }

  SpaceManagerTest(int num_spaces, size_t avg_occupancy, size_t max_commit_limit, const ChunkAllocSequence* alloc_sequence)

    : _commit_limiter(max_commit_limit), _avg_occupancy(avg_occupancy), _vslist(NULL), _cm(NULL),

      _alloc_sequence(alloc_sequence), _num_spaces(num_spaces),

      _rss_at_start(0), _rss_at_end(0), _rss_after_cleanup(0),

      _testbeds(NULL)

  {

    _rss_at_start = get_workingset_size();

    // Allocate test bed array

    _testbeds = NEW_C_HEAP_ARRAY(SpaceManagerTestBed*, _num_spaces, mtInternal);

    for (int i = 0; i < _num_spaces; i ++) {

      _testbeds[i] = NULL;

    }

    // Create VirtualSpaceList and ChunkManager as backing memory

    _vslist = new VirtualSpaceList("test_vs", &_commit_limiter);

    _cm = new ChunkManager("test_cm", _vslist);

  }

  ~SpaceManagerTest () {

    _rss_at_end = get_workingset_size();

    // Is the memory footprint abnormal? This is necessarily very fuzzy. The memory footprint of these tests

    // is dominated by all metaspace allocations done and the number of spaces, since the SpaceManagerTestBed

    // - due to the fact that we track individual allocations - is rather big.

    const size_t reasonable_expected_footprint = _avg_occupancy * BytesPerWord +

                                                  sizeof(SpaceManagerTestBed) * _num_spaces +

                                                  sizeof(SpaceManagerTestBed*) * _num_spaces +

                                                  sizeof(ChunkManager) + sizeof(VirtualSpaceList);

    const size_t reasonable_expected_footprint_with_margin =

        (reasonable_expected_footprint * 2) + 1 * M;

    EXPECT_LE(_rss_at_end, _rss_at_start + reasonable_expected_footprint_with_margin);

    for (int i = 0; i < _num_spaces; i ++) {

      delete _testbeds[i];

    }

    FREE_C_HEAP_ARRAY(SpaceManagerTestBed*, _testbeds);

    delete _cm;

    delete _vslist;

    _rss_after_cleanup = get_workingset_size();

    // Check for memory leaks. We should ideally be at the baseline of _rss_at_start. However, this depends

    // on whether this gtest was executed as a first test in the suite, since gtest suite adds overhead of 2-4 MB.

    EXPECT_LE(_rss_after_cleanup, _rss_at_start + 4 * M);

    LOG("rss at start: " INTX_FORMAT ", at end " INTX_FORMAT " (" INTX_FORMAT "), after cleanup: " INTX_FORMAT " (" INTX_FORMAT ").", \

        _rss_at_start, _rss_at_end, _rss_at_end - _rss_at_start, _rss_after_cleanup, _rss_after_cleanup - _rss_at_start); \

  }

  void test_deallocation_in_place() {

    // When deallocating, it is attempted to deallocate in place, i.e.

    // if the allocation is the most recent one, the current usage pointer

    // in the current chunk is just reversed back to its original position

    // before the original allocation.

    //

    // But in-place-deallocation will not reverse allocation of the

    // current chunk itself if its usage pointer reaches 0 due to in-place

    // deallocation!

    //

    // In theory, allocating n times, then deallocation in reverse order should

    // happin in place and at the end the usage counter of the Space Manager should

    // be at the original place.

    // However, this is fragile, since when one of the allocations happens to

    // cause the current chunk to be retired and a new one created, the chain

    // breaks at that point (one cannot deallocate in-place from a non-current chunk).

    //

    // Therefore, to make this test reliable, we work on a new empty testbed - so

    // we have a fresh chunk - and with miniscule allocation sizes, to not

    // cause allocation beyond the smallest possible chunk size. That way we

    // will never cause the initial chunk to be retired, regardless of how small it

    // is.

    delete_testbed_at(0);

    SpaceManagerTestBed* bed = testbed_at(0); // new bed

    const int num_loops = 5;

    const size_t max_alloc_size = metaspace::chklvl::MIN_CHUNK_WORD_SIZE / num_loops * 2;

    // Doing this multiple times should work too as long as we keep the

    // reverse allocation order.

    sm_stats_t stat[10]; // taken before each allocation

    size_t alloc_sizes[10] = {

        max_alloc_size,

        1, 2, 3, // <- small sizes to have difference between raw size and net size

        0, 0, 0, 0, 0, 0 // <- use random values;

    };

    RandSizeGenerator rgen(1, max_alloc_size);

    int i = 0;

    while (i < 10) {

      // take stats before allocating...

      bed->sm()->add_to_statistics(stat + i);

      check_sm_stat_is_consistent(stat[i]);

      // and allocate.

      LOG("alloc round #%d (used: " SIZE_FORMAT ").", i, stat[i].totals().used_words);