/*
 * 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.
 *
 */
#ifndef SHARE_MEMORY_METASPACE_METACHUNK_HPP
#define SHARE_MEMORY_METASPACE_METACHUNK_HPP


#include "memory/metaspace/counter.hpp"
#include "memory/metaspace/chunkLevel.hpp"
#include "utilities/debug.hpp"
#include "utilities/globalDefinitions.hpp"


class outputStream;

namespace metaspace {

class VirtualSpaceNode;

//  Metachunk - Quantum of allocation from a Virtualspace
//    Metachunks are reused (when freed are put on a global freelist) and
//    have no permanent association to a SpaceManager.

//            +--------------+ <- end    ----+         --+
//            |              |               |           |
//            |              |               | free      |
//            |              |               |
//            |              |               |           | size (aka capacity)
//            |              |               |           |
//            | -----------  | <- top     -- +           |
//            |              |               |           |
//            |              |               | used      |
//            +--------------+ <- start   -- +        -- +

// Note: this is a chunk **descriptor**. The real Payload area lives in metaspace,
// this class lives somewhere else.
class Metachunk {

  // start of chunk memory; NULL if dead.
  MetaWord* _base;

  // Used words.
  size_t _used_words;

  // Guaranteed-to-be-committed-words, counted from base
  //  (This is a performance optimization. The underlying VirtualSpaceNode knows
  //  which granules are committed; but we want to avoid asking it unnecessarily
  //  in Metachunk::allocate(), so we keep a limit until which we are guaranteed
  //  to have committed memory under us.)
  size_t _committed_words;

  chklvl_t _level; // aka size.

  // state_free:    free, owned by ChunkManager
  // state_in_use:  in-use, owned by SpaceManager
  // dead:          just a hollow chunk header without associated memory, owned
  //                 by chunk header pool.
  enum state_t {
    state_free = 0,
    state_in_use = 1,
    state_dead = 2
  };
  state_t _state;

  // We need unfortunately a back link to the virtual space node
  // for splitting and merging nodes.
  VirtualSpaceNode* _vsnode;


  // A chunk header is kept in a list:
  // - in the list of used chunks inside a SpaceManager, if it is in use
  // - in the list of free chunks inside a ChunkManager, if it is free
  // - in the freelist of unused headers inside the ChunkHeaderPool,
  //   if it is unused (e.g. result of chunk merging) and has no associated
  //   memory area.
  Metachunk* _prev;
  Metachunk* _next;

  // Furthermore, we keep, per chunk, information about the neighboring chunks.
  // This is needed to split and merge chunks.
  Metachunk* _prev_in_vs;
  Metachunk* _next_in_vs;

  MetaWord* top() const           { return base() + _used_words; }

  // Commit uncommitted section of the chunk.
  // Fails if we hit a commit limit.
  bool commit_up_to(size_t new_committed_words);

public:

  Metachunk()
    : _base(NULL),
      _used_words(0),
      _committed_words(0),
      _level(chklvl::ROOT_CHUNK_LEVEL),
      _state(state_free),
      _vsnode(NULL),
      _prev(NULL), _next(NULL),
      _prev_in_vs(NULL), _next_in_vs(NULL)
  {}

  size_t word_size() const        { return chklvl::word_size_for_level(_level); }

  MetaWord* base() const          { return _base; }
//  void set_base(MetaWord* p)      { _base = p; }
  MetaWord* end() const           { return base() + word_size(); }

  // Chunk list wiring
  void set_prev(Metachunk* c)     { _prev = c; }
  Metachunk* prev() const         { return _prev; }
  void set_next(Metachunk* c)     { _next = c; }
  Metachunk* next() const         { return _next; }

  DEBUG_ONLY(bool in_list() const { return _prev != NULL || _next != NULL; })

  // Physical neighbors wiring
  void set_prev_in_vs(Metachunk* c) { _prev_in_vs = c; }
  Metachunk* prev_in_vs() const     { return _prev_in_vs; }
  void set_next_in_vs(Metachunk* c) { _next_in_vs = c; }
  Metachunk* next_in_vs() const     { return _next_in_vs; }

  bool is_free() const            { return _state == state_free; }
  bool is_in_use() const          { return _state == state_in_use; }
  bool is_dead() const            { return _state == state_dead; }
  void set_free()                 { _state = state_free; }
  void set_in_use()               { _state = state_in_use; }
  void set_dead()                 { _state = state_dead; }

  // Return a single char presentation of the state ('f', 'u', 'd')
  char get_state_char() const;

  void inc_level()                { _level ++; DEBUG_ONLY(chklvl::is_valid_level(_level);) }
  void dec_level()                { _level --; DEBUG_ONLY(chklvl::is_valid_level(_level);) }
//  void set_level(chklvl_t v)      { _level = v; DEBUG_ONLY(chklvl::is_valid_level(_level);) }
  chklvl_t level() const          { return _level; }

  // Convenience functions for extreme levels.
  bool is_root_chunk() const      { return chklvl::ROOT_CHUNK_LEVEL == _level; }
  bool is_leaf_chunk() const      { return chklvl::HIGHEST_CHUNK_LEVEL == _level; }

  VirtualSpaceNode* vsnode() const        { return _vsnode; }
//  void set_vsnode(VirtualSpaceNode* n)    { _vsnode = n; }

  size_t used_words() const                   { return _used_words; }
  size_t free_words() const                   { return word_size() - used_words(); }
  size_t free_below_committed_words() const   { return committed_words() - used_words(); }
  void reset_used_words()                     { _used_words = 0; }

  size_t committed_words() const      { return _committed_words; }
  void set_committed_words(size_t v);
  bool is_fully_committed() const     { return committed_words() == word_size(); }
  bool is_fully_uncommitted() const   { return committed_words() == 0; }

  // Ensure that chunk is committed up to at least new_committed_words words.
  // Fails if we hit a commit limit.
  bool ensure_committed(size_t new_committed_words);
  bool ensure_committed_locked(size_t new_committed_words);

  bool ensure_fully_committed()           { return ensure_committed(word_size()); }
  bool ensure_fully_committed_locked()    { return ensure_committed_locked(word_size()); }

  // Uncommit chunk area. The area must be a common multiple of the
  // commit granule size (in other words, we cannot uncommit chunks smaller than
  // a commit granule size).
  void uncommit();
  void uncommit_locked();

  // Alignment of an allocation.
  static const size_t allocation_alignment_bytes = 8;
  static const size_t allocation_alignment_words = allocation_alignment_bytes / BytesPerWord;

  // Allocation from a chunk

  // Allocate word_size words from this chunk (word_size must be aligned to
  //  allocation_alignment_words).
  //
  // May cause memory to be committed. That may fail if we hit a commit limit. In that case,
  //  NULL is returned and p_did_hit_commit_limit will be set to true.
  // If the remainder portion of the chunk was too small to hold the allocation,
  //  NULL is returned and p_did_hit_commit_limit will be set to false.
  MetaWord* allocate(size_t net_word_size, bool* p_did_hit_commit_limit);

  // Given a memory range which may or may not have been allocated from this chunk, attempt
  // to roll its allocation back. This can work if this is the very last allocation we did
  // from this chunk, in which case we just lower the top pointer again.
  // Returns true if this succeeded, false if it failed.
  bool attempt_rollback_allocation(MetaWord* p, size_t word_size);

  // Initialize structure for reuse.
  void initialize(VirtualSpaceNode* node, MetaWord* base, chklvl_t lvl) {
    _vsnode = node; _base = base; _level = lvl;
    _used_words = _committed_words = 0; _state = state_free;
    _next = _prev = _next_in_vs = _prev_in_vs = NULL;
  }

  // Returns true if this chunk is the leader in its buddy pair, false if not.
  // Must not be called for root chunks.
  bool is_leader() const {
    assert(!is_root_chunk(), "Root chunks have no buddy.");
    // I am sure this can be done smarter...
    return is_aligned(base(), chklvl::word_size_for_level(level() - 1) * BytesPerWord);
  }

  //// Debug stuff ////
#ifdef ASSERT
  void verify(bool slow) const;
  void zap_header(uint8_t c = 0x17);
  void fill_with_pattern(MetaWord pattern, size_t word_size);
  void check_pattern(MetaWord pattern, size_t word_size);

  // Returns true if pointer points into the used area of this chunk.
  bool is_valid_pointer(const MetaWord* p) const {
    return base() <= p && p < top();
  }
#endif // ASSERT

  void print_on(outputStream* st) const;

};

// Little print helpers: since we often print out chunks, here some convenience macros
#define METACHUNK_FORMAT                "@" PTR_FORMAT ", %c, base " PTR_FORMAT ", level " CHKLVL_FORMAT
#define METACHUNK_FORMAT_ARGS(chunk)    p2i(chunk), chunk->get_state_char(), p2i(chunk->base()), chunk->level()

#define METACHUNK_FULL_FORMAT                "@" PTR_FORMAT ", %c, base " PTR_FORMAT ", level " CHKLVL_FORMAT " (" SIZE_FORMAT "), used: " SIZE_FORMAT ", committed: " SIZE_FORMAT
#define METACHUNK_FULL_FORMAT_ARGS(chunk)    p2i(chunk), chunk->get_state_char(), p2i(chunk->base()), chunk->level(), chunk->word_size(), chunk->used_words(), chunk->committed_words()

/////////
// A list of Metachunks.
class MetachunkList {

  Metachunk* _first;

  // Number of chunks
  IntCounter _num;

public:

  MetachunkList() : _first(NULL), _num() {}

  Metachunk* first() const { return _first; }
  int size() const { return _num.get(); }

  void add(Metachunk* c) {
    assert(!c->in_list(), "Chunk must not be in a list");
    if (_first) {
      _first->set_prev(c);
    }
    c->set_next(_first);
    c->set_prev(NULL);
    _first = c;
    _num.increment();
  }

  // Remove first node unless empty. Returns node or NULL.
  Metachunk* remove_first() {
    Metachunk* c = _first;
    if (c != NULL) {
      assert(c->prev() == NULL, "Sanity");
      Metachunk* c2 = c->next();
      if (c2 != NULL) {
        c2->set_prev(NULL);
      }
      _first = c2;
      c->set_next(NULL);
      _num.decrement();
    }
    return c;
  }

  // Remove given chunk from list. List must contain that chunk.
  void remove(Metachunk* c) {
    assert(contains(c), "List does not contain this chunk");
    if (_first == c) {
      _first = c->next();
      if (_first != NULL) {
        _first->set_prev(NULL);
      }
    } else {
      if (c->next() != NULL) {
        c->next()->set_prev(c->prev());
      }
      if (c->prev() != NULL) {
        c->prev()->set_next(c->next());
      }
    }
    c->set_prev(NULL);
    c->set_next(NULL);
    _num.decrement();
  }

#ifdef ASSERT
  bool contains(const Metachunk* c) const;
  void verify(bool slow) const;
#endif

  // Returns size, in words, of committed space of all chunks in this list.
  // Note: walks list.
  size_t committed_word_size() const {
    size_t l = 0;
    for (const Metachunk* c = _first; c != NULL; c = c->next()) {
      l += c->committed_words();
    }
    return l;
  }

  void print_on(outputStream* st) const;

};

//////////////////
// A cluster of Metachunk Lists, one for each chunk level, together with associated counters.
class MetachunkListCluster {

  MetachunkList _lists[chklvl::NUM_CHUNK_LEVELS];
  SizeCounter   _total_word_size;
  IntCounter    _total_num_chunks;

  const MetachunkList* list_for_level(chklvl_t lvl) const         { DEBUG_ONLY(chklvl::check_valid_level(lvl)); return _lists + lvl; }
  MetachunkList* list_for_level(chklvl_t lvl)                     { DEBUG_ONLY(chklvl::check_valid_level(lvl)); return _lists + lvl; }

  const MetachunkList* list_for_chunk(const Metachunk* c) const   { return list_for_level(c->level()); }
  MetachunkList* list_for_chunk(const Metachunk* c)               { return list_for_level(c->level()); }

public:

  const Metachunk* first_at_level(chklvl_t lvl) const   { return list_for_level(lvl)->first(); }
  Metachunk* first_at_level(chklvl_t lvl)               { return list_for_level(lvl)->first(); }

  // Remove given chunk from its list. List must contain that chunk.
  void remove(Metachunk* c) {
    list_for_chunk(c)->remove(c);
    _total_word_size.decrement_by(c->word_size());
    _total_num_chunks.decrement();
  }

  // Remove first node unless empty. Returns node or NULL.
  Metachunk* remove_first(chklvl_t lvl) {
    Metachunk* c = list_for_level(lvl)->remove_first();
    if (c != NULL) {
      _total_word_size.decrement_by(c->word_size());
      _total_num_chunks.decrement();
    }
    return c;
  }

  void add(Metachunk* c) {
    list_for_chunk(c)->add(c);
    _total_word_size.increment_by(c->word_size());
    _total_num_chunks.increment();
  }

  // Returns number of chunks for a given level.
  int num_chunks_at_level(chklvl_t lvl) const {
    return list_for_level(lvl)->size();
  }

  // Returns number of chunks for a given level.
  size_t committed_word_size_at_level(chklvl_t lvl) const {
    return list_for_level(lvl)->committed_word_size();
  }

  // Returs word size, in total, of all chunks in all lists.
  size_t total_word_size() const          { return _total_word_size.get(); }

  // Returns number of chunks in total
  int total_num_chunks() const            { return _total_num_chunks.get(); }

  // Returns size, in words, of committed space of all chunks in all list.
  // Note: walks lists.
  size_t total_committed_word_size() const {
    size_t l = 0;
    for (chklvl_t l = chklvl::LOWEST_CHUNK_LEVEL; l <= chklvl::HIGHEST_CHUNK_LEVEL; l ++) {
      l += list_for_level(l)->committed_word_size();
    }
    return l;
  }

  DEBUG_ONLY(void verify(bool slow) const;)
  DEBUG_ONLY(bool contains(const Metachunk* c) const;)

  void print_on(outputStream* st) const;

};


} // namespace metaspace

#endif // SHARE_MEMORY_METASPACE_METACHUNK_HPP