/*

 * Copyright (c) 2001, 2017, 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 "gc/cms/allocationStats.hpp"

#include "gc/shared/spaceDecorator.hpp"

#include "logging/log.hpp"

#include "logging/logStream.hpp"

#include "memory/binaryTreeDictionary.hpp"

#include "memory/freeList.hpp"

#include "memory/metachunk.hpp"

#include "memory/resourceArea.hpp"

#include "runtime/globals.hpp"

#include "utilities/macros.hpp"

#include "utilities/ostream.hpp"

#if INCLUDE_ALL_GCS

#include "gc/cms/adaptiveFreeList.hpp"

#include "gc/cms/freeChunk.hpp"

#endif // INCLUDE_ALL_GCS

////////////////////////////////////////////////////////////////////////////////

// A binary tree based search structure for free blocks.

// This is currently used in the Concurrent Mark&Sweep implementation.

////////////////////////////////////////////////////////////////////////////////

template <class Chunk_t, class FreeList_t>

TreeChunk<Chunk_t, FreeList_t>* TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(Chunk_t* fc) {

  // Do some assertion checking here.

  return (TreeChunk<Chunk_t, FreeList_t>*) fc;

}

template <class Chunk_t, class FreeList_t>

void TreeChunk<Chunk_t, FreeList_t>::verify_tree_chunk_list() const {

  TreeChunk<Chunk_t, FreeList_t>* nextTC = (TreeChunk<Chunk_t, FreeList_t>*)next();

  if (prev() != NULL) { // interior list node shouldn't have tree fields

    guarantee(embedded_list()->parent() == NULL && embedded_list()->left() == NULL &&

              embedded_list()->right()  == NULL, "should be clear");

  }

  if (nextTC != NULL) {

    guarantee(as_TreeChunk(nextTC->prev()) == this, "broken chain");

    guarantee(nextTC->size() == size(), "wrong size");

    nextTC->verify_tree_chunk_list();

  }

}

template <class Chunk_t, class FreeList_t>

TreeList<Chunk_t, FreeList_t>::TreeList() : _parent(NULL),

  _left(NULL), _right(NULL) {}

template <class Chunk_t, class FreeList_t>

TreeList<Chunk_t, FreeList_t>*

TreeList<Chunk_t, FreeList_t>::as_TreeList(TreeChunk<Chunk_t,FreeList_t>* tc) {

  // This first free chunk in the list will be the tree list.

  assert((tc->size() >= (TreeChunk<Chunk_t, FreeList_t>::min_size())),

    "Chunk is too small for a TreeChunk");

  TreeList<Chunk_t, FreeList_t>* tl = tc->embedded_list();

  tl->initialize();

  tc->set_list(tl);

  tl->set_size(tc->size());

  tl->link_head(tc);

  tl->link_tail(tc);

  tl->set_count(1);

  assert(tl->parent() == NULL, "Should be clear");

  return tl;

}

template <class Chunk_t, class FreeList_t>

TreeList<Chunk_t, FreeList_t>*

TreeList<Chunk_t, FreeList_t>::as_TreeList(HeapWord* addr, size_t size) {

  TreeChunk<Chunk_t, FreeList_t>* tc = (TreeChunk<Chunk_t, FreeList_t>*) addr;

  assert((size >= TreeChunk<Chunk_t, FreeList_t>::min_size()),

    "Chunk is too small for a TreeChunk");

  // The space will have been mangled initially but

  // is not remangled when a Chunk_t is returned to the free list

  // (since it is used to maintain the chunk on the free list).

  tc->assert_is_mangled();

  tc->set_size(size);

  tc->link_prev(NULL);

  tc->link_next(NULL);

  TreeList<Chunk_t, FreeList_t>* tl = TreeList<Chunk_t, FreeList_t>::as_TreeList(tc);

  return tl;

}

#if INCLUDE_ALL_GCS

// Specialize for AdaptiveFreeList which tries to avoid

// splitting a chunk of a size that is under populated in favor of

// an over populated size.  The general get_better_list() just returns

// the current list.

template <>

TreeList<FreeChunk, AdaptiveFreeList<FreeChunk> >*

TreeList<FreeChunk, AdaptiveFreeList<FreeChunk> >::get_better_list(

  BinaryTreeDictionary<FreeChunk, ::AdaptiveFreeList<FreeChunk> >* dictionary) {

  // A candidate chunk has been found.  If it is already under

  // populated, get a chunk associated with the hint for this

  // chunk.

  TreeList<FreeChunk, ::AdaptiveFreeList<FreeChunk> >* curTL = this;

  if (curTL->surplus() <= 0) {

    /* Use the hint to find a size with a surplus, and reset the hint. */

    TreeList<FreeChunk, ::AdaptiveFreeList<FreeChunk> >* hintTL = this;

    while (hintTL->hint() != 0) {

      assert(hintTL->hint() > hintTL->size(),

        "hint points in the wrong direction");

      hintTL = dictionary->find_list(hintTL->hint());

      assert(curTL != hintTL, "Infinite loop");

      if (hintTL == NULL ||

          hintTL == curTL /* Should not happen but protect against it */ ) {

        // No useful hint.  Set the hint to NULL and go on.

        curTL->set_hint(0);

        break;

      }

      assert(hintTL->size() > curTL->size(), "hint is inconsistent");

      if (hintTL->surplus() > 0) {

        // The hint led to a list that has a surplus.  Use it.

        // Set the hint for the candidate to an overpopulated

        // size.

        curTL->set_hint(hintTL->size());

        // Change the candidate.

        curTL = hintTL;

        break;

      }

    }

  }

  return curTL;

}

#endif // INCLUDE_ALL_GCS

template <class Chunk_t, class FreeList_t>

TreeList<Chunk_t, FreeList_t>*

TreeList<Chunk_t, FreeList_t>::get_better_list(

  BinaryTreeDictionary<Chunk_t, FreeList_t>* dictionary) {

  return this;

}

template <class Chunk_t, class FreeList_t>

TreeList<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::remove_chunk_replace_if_needed(TreeChunk<Chunk_t, FreeList_t>* tc) {

  TreeList<Chunk_t, FreeList_t>* retTL = this;

  Chunk_t* list = head();

  assert(!list || list != list->next(), "Chunk on list twice");

  assert(tc != NULL, "Chunk being removed is NULL");

  assert(parent() == NULL || this == parent()->left() ||

    this == parent()->right(), "list is inconsistent");

  assert(tc->is_free(), "Header is not marked correctly");

  assert(head() == NULL || head()->prev() == NULL, "list invariant");

  assert(tail() == NULL || tail()->next() == NULL, "list invariant");

  Chunk_t* prevFC = tc->prev();

  TreeChunk<Chunk_t, FreeList_t>* nextTC = TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(tc->next());

  assert(list != NULL, "should have at least the target chunk");

  // Is this the first item on the list?

  if (tc == list) {

    // The "getChunk..." functions for a TreeList<Chunk_t, FreeList_t> will not return the

    // first chunk in the list unless it is the last chunk in the list

    // because the first chunk is also acting as the tree node.

    // When coalescing happens, however, the first chunk in the a tree

    // list can be the start of a free range.  Free ranges are removed

    // from the free lists so that they are not available to be

    // allocated when the sweeper yields (giving up the free list lock)

    // to allow mutator activity.  If this chunk is the first in the

    // list and is not the last in the list, do the work to copy the

    // TreeList<Chunk_t, FreeList_t> from the first chunk to the next chunk and update all

    // the TreeList<Chunk_t, FreeList_t> pointers in the chunks in the list.

    if (nextTC == NULL) {

      assert(prevFC == NULL, "Not last chunk in the list");

      set_tail(NULL);

      set_head(NULL);

    } else {

      // copy embedded list.

      nextTC->set_embedded_list(tc->embedded_list());

      retTL = nextTC->embedded_list();

      // Fix the pointer to the list in each chunk in the list.

      // This can be slow for a long list.  Consider having

      // an option that does not allow the first chunk on the

      // list to be coalesced.

      for (TreeChunk<Chunk_t, FreeList_t>* curTC = nextTC; curTC != NULL;

          curTC = TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(curTC->next())) {

        curTC->set_list(retTL);

      }

      // Fix the parent to point to the new TreeList<Chunk_t, FreeList_t>.

      if (retTL->parent() != NULL) {

        if (this == retTL->parent()->left()) {

          retTL->parent()->set_left(retTL);

        } else {

          assert(this == retTL->parent()->right(), "Parent is incorrect");

          retTL->parent()->set_right(retTL);

        }

      }

      // Fix the children's parent pointers to point to the

      // new list.

      assert(right() == retTL->right(), "Should have been copied");

      if (retTL->right() != NULL) {

        retTL->right()->set_parent(retTL);

      }

      assert(left() == retTL->left(), "Should have been copied");

      if (retTL->left() != NULL) {

        retTL->left()->set_parent(retTL);

      }

      retTL->link_head(nextTC);

      assert(nextTC->is_free(), "Should be a free chunk");

    }

  } else {

    if (nextTC == NULL) {

      // Removing chunk at tail of list

      this->link_tail(prevFC);

    }

    // Chunk is interior to the list

    prevFC->link_after(nextTC);

  }

  // Below this point the embedded TreeList<Chunk_t, FreeList_t> being used for the

  // tree node may have changed. Don't use "this"

  // TreeList<Chunk_t, FreeList_t>*.

  // chunk should still be a free chunk (bit set in _prev)

  assert(!retTL->head() || retTL->size() == retTL->head()->size(),

    "Wrong sized chunk in list");

  debug_only(

    tc->link_prev(NULL);

    tc->link_next(NULL);

    tc->set_list(NULL);

    bool prev_found = false;

    bool next_found = false;

    for (Chunk_t* curFC = retTL->head();

         curFC != NULL; curFC = curFC->next()) {

      assert(curFC != tc, "Chunk is still in list");

      if (curFC == prevFC) {

        prev_found = true;

      }

      if (curFC == nextTC) {

        next_found = true;

      }

    }

    assert(prevFC == NULL || prev_found, "Chunk was lost from list");

    assert(nextTC == NULL || next_found, "Chunk was lost from list");

    assert(retTL->parent() == NULL ||

           retTL == retTL->parent()->left() ||

           retTL == retTL->parent()->right(),

           "list is inconsistent");

  )

  retTL->decrement_count();

  assert(tc->is_free(), "Should still be a free chunk");

  assert(retTL->head() == NULL || retTL->head()->prev() == NULL,

    "list invariant");

  assert(retTL->tail() == NULL || retTL->tail()->next() == NULL,

    "list invariant");

  return retTL;

}

template <class Chunk_t, class FreeList_t>

void TreeList<Chunk_t, FreeList_t>::return_chunk_at_tail(TreeChunk<Chunk_t, FreeList_t>* chunk) {

  assert(chunk != NULL, "returning NULL chunk");

  assert(chunk->list() == this, "list should be set for chunk");

  assert(tail() != NULL, "The tree list is embedded in the first chunk");

  // which means that the list can never be empty.

  assert(!this->verify_chunk_in_free_list(chunk), "Double entry");

  assert(head() == NULL || head()->prev() == NULL, "list invariant");

  assert(tail() == NULL || tail()->next() == NULL, "list invariant");

  Chunk_t* fc = tail();

  fc->link_after(chunk);

  this->link_tail(chunk);

  assert(!tail() || size() == tail()->size(), "Wrong sized chunk in list");

  FreeList_t::increment_count();

  debug_only(this->increment_returned_bytes_by(chunk->size()*sizeof(HeapWord));)

  assert(head() == NULL || head()->prev() == NULL, "list invariant");

  assert(tail() == NULL || tail()->next() == NULL, "list invariant");

}

// Add this chunk at the head of the list.  "At the head of the list"

// is defined to be after the chunk pointer to by head().  This is

// because the TreeList<Chunk_t, FreeList_t> is embedded in the first TreeChunk<Chunk_t, FreeList_t> in the

// list.  See the definition of TreeChunk<Chunk_t, FreeList_t>.

template <class Chunk_t, class FreeList_t>

void TreeList<Chunk_t, FreeList_t>::return_chunk_at_head(TreeChunk<Chunk_t, FreeList_t>* chunk) {

  assert(chunk->list() == this, "list should be set for chunk");

  assert(head() != NULL, "The tree list is embedded in the first chunk");

  assert(chunk != NULL, "returning NULL chunk");

  assert(!this->verify_chunk_in_free_list(chunk), "Double entry");

  assert(head() == NULL || head()->prev() == NULL, "list invariant");

  assert(tail() == NULL || tail()->next() == NULL, "list invariant");

  Chunk_t* fc = head()->next();

  if (fc != NULL) {

    chunk->link_after(fc);

  } else {

    assert(tail() == NULL, "List is inconsistent");

    this->link_tail(chunk);

  }

  head()->link_after(chunk);

  assert(!head() || size() == head()->size(), "Wrong sized chunk in list");

  FreeList_t::increment_count();

  debug_only(this->increment_returned_bytes_by(chunk->size()*sizeof(HeapWord));)

  assert(head() == NULL || head()->prev() == NULL, "list invariant");

  assert(tail() == NULL || tail()->next() == NULL, "list invariant");

}

template <class Chunk_t, class FreeList_t>

void TreeChunk<Chunk_t, FreeList_t>::assert_is_mangled() const {

  assert((ZapUnusedHeapArea &&

          SpaceMangler::is_mangled((HeapWord*) Chunk_t::size_addr()) &&

          SpaceMangler::is_mangled((HeapWord*) Chunk_t::prev_addr()) &&

          SpaceMangler::is_mangled((HeapWord*) Chunk_t::next_addr())) ||

          (size() == 0 && prev() == NULL && next() == NULL),

    "Space should be clear or mangled");

}

template <class Chunk_t, class FreeList_t>

TreeChunk<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::head_as_TreeChunk() {

  assert(head() == NULL || (TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(head())->list() == this),

    "Wrong type of chunk?");

  return TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(head());

}

template <class Chunk_t, class FreeList_t>

TreeChunk<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::first_available() {

  assert(head() != NULL, "The head of the list cannot be NULL");

  Chunk_t* fc = head()->next();

  TreeChunk<Chunk_t, FreeList_t>* retTC;

  if (fc == NULL) {

    retTC = head_as_TreeChunk();

  } else {

    retTC = TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(fc);

  }

  assert(retTC->list() == this, "Wrong type of chunk.");

  return retTC;

}

// Returns the block with the largest heap address amongst

// those in the list for this size; potentially slow and expensive,

// use with caution!

template <class Chunk_t, class FreeList_t>

TreeChunk<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::largest_address() {

  assert(head() != NULL, "The head of the list cannot be NULL");

  Chunk_t* fc = head()->next();

  TreeChunk<Chunk_t, FreeList_t>* retTC;

  if (fc == NULL) {

    retTC = head_as_TreeChunk();

  } else {

    // walk down the list and return the one with the highest

    // heap address among chunks of this size.

    Chunk_t* last = fc;

    while (fc->next() != NULL) {

      if ((HeapWord*)last < (HeapWord*)fc) {

        last = fc;

      }

      fc = fc->next();

    }

    retTC = TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(last);

  }

  assert(retTC->list() == this, "Wrong type of chunk.");

  return retTC;

}

template <class Chunk_t, class FreeList_t>

BinaryTreeDictionary<Chunk_t, FreeList_t>::BinaryTreeDictionary(MemRegion mr) {

  assert((mr.byte_size() > min_size()), "minimum chunk size");

  reset(mr);

  assert(root()->left() == NULL, "reset check failed");

  assert(root()->right() == NULL, "reset check failed");

  assert(root()->head()->next() == NULL, "reset check failed");

  assert(root()->head()->prev() == NULL, "reset check failed");

  assert(total_size() == root()->size(), "reset check failed");

  assert(total_free_blocks() == 1, "reset check failed");

}

template <class Chunk_t, class FreeList_t>

void BinaryTreeDictionary<Chunk_t, FreeList_t>::inc_total_size(size_t inc) {

  _total_size = _total_size + inc;

}

template <class Chunk_t, class FreeList_t>

void BinaryTreeDictionary<Chunk_t, FreeList_t>::dec_total_size(size_t dec) {

  _total_size = _total_size - dec;

}

template <class Chunk_t, class FreeList_t>

void BinaryTreeDictionary<Chunk_t, FreeList_t>::reset(MemRegion mr) {

  assert((mr.byte_size() > min_size()), "minimum chunk size");

  set_root(TreeList<Chunk_t, FreeList_t>::as_TreeList(mr.start(), mr.word_size()));

  set_total_size(mr.word_size());

  set_total_free_blocks(1);

}

template <class Chunk_t, class FreeList_t>

void BinaryTreeDictionary<Chunk_t, FreeList_t>::reset(HeapWord* addr, size_t byte_size) {

  MemRegion mr(addr, heap_word_size(byte_size));

  reset(mr);

}

template <class Chunk_t, class FreeList_t>

void BinaryTreeDictionary<Chunk_t, FreeList_t>::reset() {

  set_root(NULL);

  set_total_size(0);

  set_total_free_blocks(0);

}

// Get a free block of size at least size from tree, or NULL.

template <class Chunk_t, class FreeList_t>

TreeChunk<Chunk_t, FreeList_t>*

BinaryTreeDictionary<Chunk_t, FreeList_t>::get_chunk_from_tree(size_t size)

{

  TreeList<Chunk_t, FreeList_t> *curTL, *prevTL;

  TreeChunk<Chunk_t, FreeList_t>* retTC = NULL;

  assert((size >= min_size()), "minimum chunk size");

  if (FLSVerifyDictionary) {

    verify_tree();

  }

  // starting at the root, work downwards trying to find match.

  // Remember the last node of size too great or too small.

  for (prevTL = curTL = root(); curTL != NULL;) {

    if (curTL->size() == size) {        // exact match

      break;

    }

    prevTL = curTL;

    if (curTL->size() < size) {        // proceed to right sub-tree

      curTL = curTL->right();

    } else {                           // proceed to left sub-tree

      assert(curTL->size() > size, "size inconsistency");

      curTL = curTL->left();

    }

  }

  if (curTL == NULL) { // couldn't find exact match

    // try and find the next larger size by walking back up the search path

    for (curTL = prevTL; curTL != NULL;) {

      if (curTL->size() >= size) break;

      else curTL = curTL->parent();

    }

    assert(curTL == NULL || curTL->count() > 0,

      "An empty list should not be in the tree");

  }

  if (curTL != NULL) {

    assert(curTL->size() >= size, "size inconsistency");

    curTL = curTL->get_better_list(this);

    retTC = curTL->first_available();

    assert((retTC != NULL) && (curTL->count() > 0),

      "A list in the binary tree should not be NULL");

    assert(retTC->size() >= size,

      "A chunk of the wrong size was found");

    remove_chunk_from_tree(retTC);

    assert(retTC->is_free(), "Header is not marked correctly");

  }

  if (FLSVerifyDictionary) {

    verify();

  }

  return retTC;

}

template <class Chunk_t, class FreeList_t>

TreeList<Chunk_t, FreeList_t>* BinaryTreeDictionary<Chunk_t, FreeList_t>::find_list(size_t size) const {

  TreeList<Chunk_t, FreeList_t>* curTL;

  for (curTL = root(); curTL != NULL;) {

    if (curTL->size() == size) {        // exact match

      break;

    }

    if (curTL->size() < size) {        // proceed to right sub-tree

      curTL = curTL->right();

    } else {                           // proceed to left sub-tree

      assert(curTL->size() > size, "size inconsistency");

      curTL = curTL->left();

    }

  }

  return curTL;

}

template <class Chunk_t, class FreeList_t>

bool BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_chunk_in_free_list(Chunk_t* tc) const {