/*
 * Copyright (c) 2018, 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 "logging/log.hpp"
#include "memory/metaspace/constants.hpp"
#include "memory/metaspace/chunkAllocSequence.hpp"
#include "memory/metaspace/chunkLevel.hpp"
#include "memory/metaspace/chunkManager.hpp"
#include "memory/metaspace/metachunk.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) {
  DEBUG_ONLY(c->verify(false));
  const chklvl_t lvl = c->level();
  _chunks[lvl].add(c);
  _total_word_size.increment_by(c->word_size());
  _committed_word_size.increment_by(c->committed_words());
}

// 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) {
  DEBUG_ONLY(chklvl::check_valid_level(l);)
  Metachunk* c = _chunks[l].remove_first();
  if (c != NULL) {
    _total_word_size.decrement_by(c->word_size());
    _committed_word_size.decrement_by(c->committed_words());
  }
  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) {
  const size_t must_be_committed = MIN2(c->word_size(), constants::committed_words_on_fresh_chunks);
  return c->ensure_committed(must_be_committed);
}

#ifdef ASSERT
// Given a splinters array returned from a split operation, check that it meets expectations
static void check_splinters_array(Metachunk* splinters[chklvl::NUM_CHUNK_LEVELS], chklvl_t min, chklvl_t max) {
  // The array shall contain splinters in the range [min, max] and nothing outside. The chunk levels for
  // the chunks must match too.
  for (chklvl_t l = chklvl::ROOT_CHUNK_LEVEL; l <= chklvl::HIGHEST_CHUNK_LEVEL; l ++) {
    if (l >= min && l < max) {
      assert(splinters[l] != NULL, "Missing splinters");
      assert(splinters[l]->level() == l, "Unexpected level");
      splinters[l]->verify(false);
    } else {
      assert(splinters[l] == NULL, "Unexpected splinters");
    }
  }
}
#endif


// 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(c->is_free() && c->level() > target_level, "Invalid chunk for splitting");
  DEBUG_ONLY(chklvl::check_valid_level(target_level);)

  const chklvl_t orig_level = c->level();
  Metachunk* splinters[chklvl::NUM_CHUNK_LEVELS] = { 0 };
  c = c->vsnode()->split(target_level, c, splinters);

  // Splitting should never fail.
  assert(c != NULL, "Split failed");
  assert(c->level() == target_level, "Sanity");
  DEBUG_ONLY(c->verify(false));
  DEBUG_ONLY(check_splinters_array(splinters, orig_level + 1, target_level);)

  // Return splinters to freelist.
  for (chklvl_t l = orig_level + 1; l <= target_level; l ++) {
    return_chunk_simple(splinters[l]);
  }

  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 minimal 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 min_level, chklvl_t pref_level) {

  assert_lock_strong(MetaspaceExpand_lock);
  DEBUG_ONLY(chklvl::check_valid_level(min_level);)
  DEBUG_ONLY(chklvl::check_valid_level(pref_level);)

  Metachunk* c = NULL;

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

  // 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 <= min_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) {

    c = _vslist->allocate_root_chunk();

    // This should always work. Note that getting the root chunk may not mean we committed memory.
    assert(c != NULL, "Unexpected");

    // Split this root chunk to the desired chunk size.
    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.");
  }

  DEBUG_ONLY(verify(false);)

  return c;

} // ChunkManager::get_chunk


// Return a single chunk to the ChunkManager and adjust accounting. May merge chunk
//  with neighbors.
// 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) {

  assert_lock_strong(MetaspaceExpand_lock);
  DEBUG_ONLY(c->verify(false);)

  const chklvl_t orig_lvl = c->level();

  int num_merged[chklvl::NUM_CHUNK_LEVELS] = { 0 };
  Metachunk* c2 = c->vsnode()->merge(c, num_merged);

  if (c2 != NULL) {
    DEBUG_ONLY(c2->verify(false));

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

    // Adjust counters - the merged-in chunks have been removed from the free lists, but the counters
    // in this chunk manager must be adjusted too.
    size_t size_chunks_removed = 0;
    for (chklvl_t l = chklvl::ROOT_CHUNK_LEVEL; l <= chklvl::HIGHEST_CHUNK_LEVEL; l ++) {
      if (num_merged[l] > 0) {
        // Since we have a binary tree, we should exactly see one merge per level.
        assert(num_merged[l] == 1, "sanity");
        _chunks[l].dec_counter_by(1);
        size_chunks_removed += chklvl::word_size_for_level(l);
      }
    }
    _total_word_size.decrement_by(size_chunks_removed);

    c = c2;
  }

  return_chunk_simple(c);

}


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(ChunkManagerStatistics* out) const {

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

}

#ifdef ASSERT

void ChunkManager::verify(bool slow) const {

  size_t word_size = 0;
  size_t committed_word_size = 0;
  for (chklvl_t l = chklvl::LOWEST_CHUNK_LEVEL;
       l <= chklvl::HIGHEST_CHUNK_LEVEL; l ++)
  {
    const Metachunk* c = _chunks[l].first();
    int num = 0;
    while (c) {
      assert(c->level() == l, "Wrong level");
      assert(c->is_free(), "Chunk is not free.");
      num ++;
      committed_word_size += c->committed_words();
      c->verify(slow);
      c = c->next();
    }
    assert(num == _chunks[l].size(), "Sanity");
    word_size += num * chklvl::word_size_for_level(l);
  }
  _total_word_size.check(word_size);
  _committed_word_size.check(committed_word_size);

}

#endif // ASSERT


} // namespace metaspace