/*
 * 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 <memory/metaspace/settings.hpp>
#include "precompiled.hpp"


#include "logging/log.hpp"
#include "logging/logStream.hpp"
#include "memory/metaspace/chunkAllocSequence.hpp"
#include "memory/metaspace/chunkLevel.hpp"
#include "memory/metaspace/chunkManager.hpp"
#include "memory/metaspace/internStat.hpp"
#include "memory/metaspace/metachunk.hpp"
#include "memory/metaspace/metaspaceCommon.hpp"
#include "memory/metaspace/metaspaceStatistics.hpp"
#include "memory/metaspace/virtualSpaceNode.hpp"
#include "memory/metaspace/virtualSpaceList.hpp"
#include "runtime/mutexLocker.hpp"
#include "utilities/debug.hpp"
#include "utilities/globalDefinitions.hpp"

namespace metaspace {


// Return a single chunk to the freelist and adjust accounting. No merge is attempted.
void ChunkManager::return_chunk_simple(Metachunk* c) {

  assert_lock_strong(MetaspaceExpand_lock);

  DEBUG_ONLY(c->verify(false));

  const chklvl_t lvl = c->level();
  _chunks.add(c);
  c->reset_used_words();

  // Tracing
  log_debug(metaspace)("ChunkManager %s: returned chunk " METACHUNK_FORMAT ".",
                       _name, METACHUNK_FORMAT_ARGS(c));

}

// Take a single chunk from the given freelist and adjust counters. Returns NULL
// if there is no fitting chunk for this level.
Metachunk* ChunkManager::remove_first_chunk_at_level(chklvl_t l) {

  assert_lock_strong(MetaspaceExpand_lock);
  DEBUG_ONLY(chklvl::check_valid_level(l);)

  Metachunk* c = _chunks.remove_first(l);

  // Tracing
  if (c != NULL) {
    log_debug(metaspace)("ChunkManager %s: removed chunk " METACHUNK_FORMAT ".",
                         _name, METACHUNK_FORMAT_ARGS(c));
  } else {
    log_trace(metaspace)("ChunkManager %s: no chunk found for level " CHKLVL_FORMAT,
                         _name, l);
  }

  return c;
}

// Creates a chunk manager with a given name (which is for debug purposes only)
// and an associated space list which will be used to request new chunks from
// (see get_chunk())
ChunkManager::ChunkManager(const char* name, VirtualSpaceList* space_list)
  : _vslist(space_list),
    _name(name),
    _chunks()
{
}

// Given a chunk we are about to handout to the caller, make sure it is committed
// according to constants::committed_words_on_fresh_chunks
bool ChunkManager::commit_chunk_before_handout(Metachunk* c) {
  assert_lock_strong(MetaspaceExpand_lock);
  const size_t must_be_committed = MIN2(c->word_size(), Settings::committed_words_on_fresh_chunks());
  return c->ensure_committed_locked(must_be_committed);
}

// Given a chunk which must be outside of a freelist and must be free, split it to
// meet a target level and return it. Splinters are added to the freelist.
Metachunk* ChunkManager::split_chunk_and_add_splinters(Metachunk* c, chklvl_t target_level) {

  assert_lock_strong(MetaspaceExpand_lock);

  assert(c->is_free() && c->level() < target_level, "Invalid chunk for splitting");
  DEBUG_ONLY(chklvl::check_valid_level(target_level);)

  DEBUG_ONLY(c->verify(true);)
  DEBUG_ONLY(c->vsnode()->verify(true);)

  // Chunk must be outside of our freelists
  assert(_chunks.contains(c) == false, "Chunk is in freelist.");

  log_debug(metaspace)("ChunkManager %s: will split chunk " METACHUNK_FORMAT " to " CHKLVL_FORMAT ".",
                       _name, METACHUNK_FORMAT_ARGS(c), target_level);

  const chklvl_t orig_level = c->level();
  c = c->vsnode()->split(target_level, c, &_chunks);

  // Splitting should never fail.
  assert(c != NULL, "Split failed");
  assert(c->level() == target_level, "Sanity");

  DEBUG_ONLY(c->verify(false));

  DEBUG_ONLY(verify_locked(true);)

  DEBUG_ONLY(c->vsnode()->verify(true);)

  return c;
}

// Get a chunk and be smart about it.
// - 1) Attempt to find a free chunk of exactly the pref_level level
// - 2) Failing that, attempt to find a chunk smaller or equal the max level.
// - 3) Failing that, attempt to find a free chunk of larger size and split it.
// - 4) Failing that, attempt to allocate a new chunk from the connected virtual space.
// - Failing that, give up and return NULL.
// Note: this is not guaranteed to return a *committed* chunk. The chunk manager will
//   attempt to commit the returned chunk according to constants::committed_words_on_fresh_chunks;
//   but this may fail if we hit a commit limit. In that case, a partly uncommit chunk
//   will be returned, and the commit is attempted again when we allocate from the chunk's
//   uncommitted area. See also Metachunk::allocate.
Metachunk* ChunkManager::get_chunk(chklvl_t max_level, chklvl_t pref_level) {

  MutexLocker fcl(MetaspaceExpand_lock, Mutex::_no_safepoint_check_flag);

  DEBUG_ONLY(verify_locked(false);)

  DEBUG_ONLY(chklvl::check_valid_level(max_level);)
  DEBUG_ONLY(chklvl::check_valid_level(pref_level);)
  assert(max_level >= pref_level, "invalid level.");

  Metachunk* c = NULL;

  // Tracing
  log_debug(metaspace)("ChunkManager %s: get chunk: max " CHKLVL_FORMAT " (" SIZE_FORMAT "),"
                       "preferred " CHKLVL_FORMAT " (" SIZE_FORMAT ").",
                       _name, max_level, chklvl::word_size_for_level(max_level),
                       pref_level, chklvl::word_size_for_level(pref_level));

  // 1) Attempt to find a free chunk of exactly the pref_level level
  c = remove_first_chunk_at_level(pref_level);

  // Todo:
  //
  // We need to meditate about steps (2) and (3) a bit more.
  // By simply preferring to reuse small chunks vs splitting larger chunks we may emphasize
  // fragmentation, strangely enough, if callers wanting medium sized chunks take small chunks
  // instead, and taking them away from the many users which prefer small chunks.
  // Alternatives:
  // - alternating between (2) (3) and (3) (2)
  // - mixing (2) and (3) into one loop with a growing delta, and maybe a "hesitance" barrier function
  // - keeping track of chunk demand and adding this into the equation: if e.g. 4K chunks were heavily
  //   preferred in the past, maybe for callers wanting larger chunks leave those alone.
  // - Take into account which chunks are committed? This would require some extra bookkeeping...

  // 2) Failing that, attempt to find a chunk smaller or equal the minimal level.
  if (c == NULL) {
    for (chklvl_t lvl = pref_level + 1; lvl <= max_level; lvl ++) {
      c = remove_first_chunk_at_level(lvl);
      if (c != NULL) {
        break;
      }
    }
  }

  // 3) Failing that, attempt to find a free chunk of larger size and split it.
  if (c == NULL) {
    for (chklvl_t lvl = pref_level - 1; lvl >= chklvl::ROOT_CHUNK_LEVEL; lvl --) {
      c = remove_first_chunk_at_level(lvl);
      if (c != NULL) {
        // Split chunk; add splinters to freelist
        c = split_chunk_and_add_splinters(c, pref_level);
        break;
      }
    }
  }

  // 4) Failing that, attempt to allocate a new chunk from the connected virtual space.
  if (c == NULL) {

    // Tracing
    log_debug(metaspace)("ChunkManager %s: need new root chunk.", _name);

    c = _vslist->allocate_root_chunk();

    // This may have failed if the virtual space list is exhausted but it cannot be expanded
    // by a new node (class space).
    if (c == NULL) {
      return NULL;
    }

    assert(c->level() == chklvl::LOWEST_CHUNK_LEVEL, "Not a root chunk?");

    // Split this root chunk to the desired chunk size.
    if (pref_level > c->level()) {
      c = split_chunk_and_add_splinters(c, pref_level);
    }
  }

  // Note that we should at this point have a chunk; should always work. If we hit
  // a commit limit in the meantime, the chunk may still be uncommitted, but the chunk
  // itself should exist now.
  assert(c != NULL, "Unexpected");

  // Before returning the chunk, attempt to commit it according to the handout rules.
  // If that fails, we ignore the error and return the uncommitted chunk.
  if (commit_chunk_before_handout(c) == false) {
    log_info(gc, metaspace)("Failed to commit chunk prior to handout.");
  }

  // Any chunk returned from ChunkManager shall be marked as in use.
  c->set_in_use();

  DEBUG_ONLY(verify_locked(false);)

  log_debug(metaspace)("ChunkManager %s: handing out chunk " METACHUNK_FORMAT ".",
                       _name, METACHUNK_FORMAT_ARGS(c));


  DEBUG_ONLY(InternalStats::inc_num_chunks_taken_from_freelist();)

  return c;

} // ChunkManager::get_chunk


// Return a single chunk to the ChunkManager and adjust accounting. May merge chunk
//  with neighbors.
// As a side effect this removes the chunk from whatever list it has been in previously.
// Happens after a Classloader was unloaded and releases its metaspace chunks.
// !! Note: this may invalidate the chunk. Do not access the chunk after
//    this function returns !!
void ChunkManager::return_chunk(Metachunk* c) {

  MutexLocker fcl(MetaspaceExpand_lock, Mutex::_no_safepoint_check_flag);

  log_debug(metaspace)("ChunkManager %s: returning chunk " METACHUNK_FORMAT ".",
                       _name, METACHUNK_FORMAT_ARGS(c));

  DEBUG_ONLY(verify_locked(false);)
  DEBUG_ONLY(c->verify(false);)

  assert(!_chunks.contains(c), "A chunk to be added to the freelist must not be in the freelist already.");

  assert(c->is_in_use(), "Unexpected chunk state");
  assert(!c->in_list(), "Remove from list first");
  c->set_free();
  c->reset_used_words();

  const chklvl_t orig_lvl = c->level();

  Metachunk* merged = NULL;
  if (!c->is_root_chunk()) {
    // Only attempt merging if we are not of the lowest level already.
    merged = c->vsnode()->merge(c, &_chunks);
  }

  if (merged != NULL) {

    DEBUG_ONLY(merged->verify(false));

    // We did merge our chunk into a different chunk.

    // We did merge chunks and now have a bigger chunk.
    assert(merged->level() < orig_lvl, "Sanity");

    log_trace(metaspace)("ChunkManager %s: merged into chunk " METACHUNK_FORMAT ".",
                         _name, METACHUNK_FORMAT_ARGS(merged));

    c = merged;

  }

  if (Settings::uncommit_on_return() &&
      Settings::uncommit_on_return_min_word_size() <= c->word_size())
  {
    log_trace(metaspace)("ChunkManager %s: uncommitting free chunk " METACHUNK_FORMAT ".",
                         _name, METACHUNK_FORMAT_ARGS(c));
    c->uncommit_locked();
  }

  return_chunk_simple(c);

  DEBUG_ONLY(verify_locked(false);)
  DEBUG_ONLY(c->vsnode()->verify(true);)

  DEBUG_ONLY(InternalStats::inc_num_chunks_returned_to_freelist();)

}

// Given a chunk c, which must be "in use" and must not be a root chunk, attempt to
// enlarge it in place by claiming its trailing buddy.
//
// This will only work if c is the leader of the buddy pair and the trailing buddy is free.
//
// If successful, the follower chunk will be removed from the freelists, the leader chunk c will
// double in size (level decreased by one).
//
// On success, true is returned, false otherwise.
bool ChunkManager::attempt_enlarge_chunk(Metachunk* c) {
  MutexLocker fcl(MetaspaceExpand_lock, Mutex::_no_safepoint_check_flag);
  return c->vsnode()->attempt_enlarge_chunk(c, &_chunks);
}

static void print_word_size_delta(outputStream* st, size_t word_size_1, size_t word_size_2) {
  if (word_size_1 == word_size_2) {
    print_scaled_words(st, word_size_1);
    st->print (" (no change)");
  } else {
    print_scaled_words(st, word_size_1);
    st->print("->");
    print_scaled_words(st, word_size_2);
    st->print(" (");
    if (word_size_2 <= word_size_1) {
      st->print("-");
      print_scaled_words(st, word_size_1 - word_size_2);
    } else {
      st->print("+");
      print_scaled_words(st, word_size_2 - word_size_1);
    }
    st->print(")");
  }
}

// Attempt to reclaim free areas in metaspace wholesale:
// - first, attempt to purge nodes of the backing virtual space. This can only be successful
//   if whole nodes are only containing free chunks, so it highly depends on fragmentation.
// - then, it will uncommit areas of free chunks according to the rules laid down in
//   settings (see settings.hpp).
void ChunkManager::wholesale_reclaim() {

  MutexLocker fcl(MetaspaceExpand_lock, Mutex::_no_safepoint_check_flag);

  log_info(metaspace)("ChunkManager \"%s\": reclaiming memory...", _name);

  const size_t reserved_before = _vslist->reserved_words();
  const size_t committed_before = _vslist->committed_words();
  int num_nodes_purged = 0;

  if (Settings::delete_nodes_on_purge()) {
    num_nodes_purged = _vslist->purge(&_chunks);
    DEBUG_ONLY(InternalStats::inc_num_purges();)
  }

  if (Settings::uncommit_on_purge()) {
    const chklvl_t max_level =
        chklvl::level_fitting_word_size(Settings::uncommit_on_purge_min_word_size());
    for (chklvl_t l = chklvl::LOWEST_CHUNK_LEVEL;
         l <= max_level;
         l ++)
    {
      for (Metachunk* c = _chunks.first_at_level(l); c != NULL; c = c->next()) {
        c->uncommit_locked();
      }
    }
    DEBUG_ONLY(InternalStats::inc_num_wholesale_uncommits();)
  }

  const size_t reserved_after = _vslist->reserved_words();
  const size_t committed_after = _vslist->committed_words();

  // Print a nice report.
  if (reserved_after == reserved_before && committed_after == committed_before) {
    log_info(metaspace)("ChunkManager %s: ... nothing reclaimed.", _name);
  } else {
    LogTarget(Info, metaspace) lt;
    if (lt.is_enabled()) {
      LogStream ls(lt);
      ls.print_cr("ChunkManager %s: finished reclaiming memory: ", _name);

      ls.print("reserved: ");
      print_word_size_delta(&ls, reserved_before, reserved_after);
      ls.cr();

      ls.print("committed: ");
      print_word_size_delta(&ls, committed_before, committed_after);
      ls.cr();

      ls.print_cr("full nodes purged: %d", num_nodes_purged);
    }
  }

  DEBUG_ONLY(_vslist->verify_locked(true));
  DEBUG_ONLY(verify_locked(true));

}


ChunkManager* ChunkManager::_chunkmanager_class = NULL;
ChunkManager* ChunkManager::_chunkmanager_nonclass = NULL;

void ChunkManager::set_chunkmanager_class(ChunkManager* cm) {
  assert(_chunkmanager_class == NULL, "Sanity");
  _chunkmanager_class = cm;
}

void ChunkManager::set_chunkmanager_nonclass(ChunkManager* cm) {
  assert(_chunkmanager_nonclass == NULL, "Sanity");
  _chunkmanager_nonclass = cm;
}



// Update statistics.
void ChunkManager::add_to_statistics(cm_stats_t* out) const {

  MutexLocker fcl(MetaspaceExpand_lock, Mutex::_no_safepoint_check_flag);

  for (chklvl_t l = chklvl::ROOT_CHUNK_LEVEL; l <= chklvl::HIGHEST_CHUNK_LEVEL; l ++) {
    out->num_chunks[l] += _chunks.num_chunks_at_level(l);
    out->committed_word_size[l] += _chunks.committed_word_size_at_level(l);
  }

  DEBUG_ONLY(out->verify();)

}

#ifdef ASSERT

void ChunkManager::verify(bool slow) const {
  MutexLocker fcl(MetaspaceExpand_lock, Mutex::_no_safepoint_check_flag);
  verify_locked(slow);
}

void ChunkManager::verify_locked(bool slow) const {

  assert_lock_strong(MetaspaceExpand_lock);

  assert(_vslist != NULL, "No vslist");

  // This checks that the lists are wired up correctly, that the counters are valid and
  // that each chunk is (only) in its correct list.
  _chunks.verify(true);

  // Need to check that each chunk is free..._size = 0;
  for (chklvl_t l = chklvl::LOWEST_CHUNK_LEVEL; l <= chklvl::HIGHEST_CHUNK_LEVEL; l ++) {
    for (const Metachunk* c = _chunks.first_at_level(l); c != NULL; c = c->next()) {
      assert(c->is_free(), "Chunk is not free.");
      assert(c->used_words() == 0, "Chunk should have not used words.");
    }
  }

}

#endif // ASSERT

void ChunkManager::print_on(outputStream* st) const {
  MutexLocker fcl(MetaspaceExpand_lock, Mutex::_no_safepoint_check_flag);
  print_on_locked(st);
}

void ChunkManager::print_on_locked(outputStream* st) const {
  assert_lock_strong(MetaspaceExpand_lock);
  st->print_cr("cm %s: %d chunks, total word size: " SIZE_FORMAT ", committed word size: " SIZE_FORMAT, _name,
               total_num_chunks(), total_word_size(), _chunks.total_committed_word_size());
  _chunks.print_on(st);
}

} // namespace metaspace