/*

 * Copyright (c) 2006, 2013, 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_implementation/shared/mutableNUMASpace.hpp"

#include "gc_implementation/shared/spaceDecorator.hpp"

#include "memory/sharedHeap.hpp"

#include "oops/oop.inline.hpp"

#include "runtime/thread.inline.hpp"

MutableNUMASpace::MutableNUMASpace(size_t alignment) : MutableSpace(alignment) {

  _lgrp_spaces = new (ResourceObj::C_HEAP, mtGC) GrowableArray<LGRPSpace*>(0, true);

  _page_size = os::vm_page_size();

  _adaptation_cycles = 0;

  _samples_count = 0;

  update_layout(true);

}

MutableNUMASpace::~MutableNUMASpace() {

  for (int i = 0; i < lgrp_spaces()->length(); i++) {

    delete lgrp_spaces()->at(i);

  }

  delete lgrp_spaces();

}

#ifndef PRODUCT

void MutableNUMASpace::mangle_unused_area() {

  // This method should do nothing.

  // It can be called on a numa space during a full compaction.

}

void MutableNUMASpace::mangle_unused_area_complete() {

  // This method should do nothing.

  // It can be called on a numa space during a full compaction.

}

void MutableNUMASpace::mangle_region(MemRegion mr) {

  // This method should do nothing because numa spaces are not mangled.

}

void MutableNUMASpace::set_top_for_allocations(HeapWord* v) {

  assert(false, "Do not mangle MutableNUMASpace's");

}

void MutableNUMASpace::set_top_for_allocations() {

  // This method should do nothing.

}

void MutableNUMASpace::check_mangled_unused_area(HeapWord* limit) {

  // This method should do nothing.

}

void MutableNUMASpace::check_mangled_unused_area_complete() {

  // This method should do nothing.

}

#endif  // NOT_PRODUCT

// There may be unallocated holes in the middle chunks

void MutableNUMASpace::ensure_parsability() {

  for (int i = 0; i < lgrp_spaces()->length(); i++) {

    LGRPSpace *ls = lgrp_spaces()->at(i);

    MutableSpace *s = ls->space();

    if (s->top() < top()) { // For all spaces preceding the one containing top()

      if (s->free_in_words() > 0) {

        intptr_t cur_top = (intptr_t)s->top();

        size_t words_left_to_fill = pointer_delta(s->end(), s->top());;

        while (words_left_to_fill > 0) {

          size_t words_to_fill = MIN2(words_left_to_fill, CollectedHeap::filler_array_max_size());

          assert(words_to_fill >= CollectedHeap::min_fill_size(),

            err_msg("Remaining size ("SIZE_FORMAT ") is too small to fill (based on " SIZE_FORMAT " and " SIZE_FORMAT ")",

            words_to_fill, words_left_to_fill, CollectedHeap::filler_array_max_size()));

          CollectedHeap::fill_with_object((HeapWord*)cur_top, words_to_fill);

          if (!os::numa_has_static_binding()) {

            size_t touched_words = words_to_fill;

#ifndef ASSERT

            if (!ZapUnusedHeapArea) {

              touched_words = MIN2((size_t)align_object_size(typeArrayOopDesc::header_size(T_INT)),

                touched_words);

            }

#endif

            MemRegion invalid;

            HeapWord *crossing_start = (HeapWord*)round_to(cur_top, os::vm_page_size());

            HeapWord *crossing_end = (HeapWord*)round_to(cur_top + touched_words, os::vm_page_size());

            if (crossing_start != crossing_end) {

              // If object header crossed a small page boundary we mark the area

              // as invalid rounding it to a page_size().

              HeapWord *start = MAX2((HeapWord*)round_down(cur_top, page_size()), s->bottom());

              HeapWord *end = MIN2((HeapWord*)round_to(cur_top + touched_words, page_size()), s->end());

              invalid = MemRegion(start, end);

            }

            ls->add_invalid_region(invalid);

          }

          cur_top = cur_top + (words_to_fill * HeapWordSize);

          words_left_to_fill -= words_to_fill;

        }

      }

    } else {

      if (!os::numa_has_static_binding()) {

#ifdef ASSERT

        MemRegion invalid(s->top(), s->end());

        ls->add_invalid_region(invalid);

#else

        if (ZapUnusedHeapArea) {

          MemRegion invalid(s->top(), s->end());

          ls->add_invalid_region(invalid);

        } else {

          return;

        }

#endif

      } else {

          return;

      }

    }

  }

}

size_t MutableNUMASpace::used_in_words() const {

  size_t s = 0;

  for (int i = 0; i < lgrp_spaces()->length(); i++) {

    s += lgrp_spaces()->at(i)->space()->used_in_words();

  }

  return s;

}

size_t MutableNUMASpace::free_in_words() const {

  size_t s = 0;

  for (int i = 0; i < lgrp_spaces()->length(); i++) {

    s += lgrp_spaces()->at(i)->space()->free_in_words();

  }

  return s;

}

size_t MutableNUMASpace::tlab_capacity(Thread *thr) const {

  guarantee(thr != NULL, "No thread");

  int lgrp_id = thr->lgrp_id();

  if (lgrp_id == -1) {

    // This case can occur after the topology of the system has

    // changed. Thread can change their location, the new home

    // group will be determined during the first allocation

    // attempt. For now we can safely assume that all spaces

    // have equal size because the whole space will be reinitialized.

    if (lgrp_spaces()->length() > 0) {

      return capacity_in_bytes() / lgrp_spaces()->length();

    } else {

      assert(false, "There should be at least one locality group");

      return 0;

    }

  }

  // That's the normal case, where we know the locality group of the thread.

  int i = lgrp_spaces()->find(&lgrp_id, LGRPSpace::equals);

  if (i == -1) {

    return 0;

  }

  return lgrp_spaces()->at(i)->space()->capacity_in_bytes();

}

size_t MutableNUMASpace::unsafe_max_tlab_alloc(Thread *thr) const {

  // Please see the comments for tlab_capacity().

  guarantee(thr != NULL, "No thread");

  int lgrp_id = thr->lgrp_id();

  if (lgrp_id == -1) {

    if (lgrp_spaces()->length() > 0) {

      return free_in_bytes() / lgrp_spaces()->length();

    } else {

      assert(false, "There should be at least one locality group");

      return 0;

    }

  }

  int i = lgrp_spaces()->find(&lgrp_id, LGRPSpace::equals);

  if (i == -1) {

    return 0;

  }

  return lgrp_spaces()->at(i)->space()->free_in_bytes();

}

size_t MutableNUMASpace::capacity_in_words(Thread* thr) const {

  guarantee(thr != NULL, "No thread");

  int lgrp_id = thr->lgrp_id();

  if (lgrp_id == -1) {

    if (lgrp_spaces()->length() > 0) {

      return capacity_in_words() / lgrp_spaces()->length();

    } else {

      assert(false, "There should be at least one locality group");

      return 0;

    }

  }

  int i = lgrp_spaces()->find(&lgrp_id, LGRPSpace::equals);

  if (i == -1) {

    return 0;

  }

  return lgrp_spaces()->at(i)->space()->capacity_in_words();

}

// Check if the NUMA topology has changed. Add and remove spaces if needed.

// The update can be forced by setting the force parameter equal to true.

bool MutableNUMASpace::update_layout(bool force) {

  // Check if the topology had changed.

  bool changed = os::numa_topology_changed();

  if (force || changed) {

    // Compute lgrp intersection. Add/remove spaces.

    int lgrp_limit = (int)os::numa_get_groups_num();

    int *lgrp_ids = NEW_C_HEAP_ARRAY(int, lgrp_limit, mtGC);

    int lgrp_num = (int)os::numa_get_leaf_groups(lgrp_ids, lgrp_limit);

    assert(lgrp_num > 0, "There should be at least one locality group");

    // Add new spaces for the new nodes

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

      bool found = false;

      for (int j = 0; j < lgrp_spaces()->length(); j++) {

        if (lgrp_spaces()->at(j)->lgrp_id() == lgrp_ids[i]) {

          found = true;

          break;

        }

      }

      if (!found) {

        lgrp_spaces()->append(new LGRPSpace(lgrp_ids[i], alignment()));

      }

    }

    // Remove spaces for the removed nodes.

    for (int i = 0; i < lgrp_spaces()->length();) {

      bool found = false;

      for (int j = 0; j < lgrp_num; j++) {

        if (lgrp_spaces()->at(i)->lgrp_id() == lgrp_ids[j]) {

          found = true;

          break;

        }

      }

      if (!found) {

        delete lgrp_spaces()->at(i);

        lgrp_spaces()->remove_at(i);

      } else {

        i++;

      }

    }

    FREE_C_HEAP_ARRAY(int, lgrp_ids, mtGC);

    if (changed) {

      for (JavaThread *thread = Threads::first(); thread; thread = thread->next()) {

        thread->set_lgrp_id(-1);

      }

    }

    return true;

  }

  return false;

}

// Bias region towards the first-touching lgrp. Set the right page sizes.

void MutableNUMASpace::bias_region(MemRegion mr, int lgrp_id) {

  HeapWord *start = (HeapWord*)round_to((intptr_t)mr.start(), page_size());

  HeapWord *end = (HeapWord*)round_down((intptr_t)mr.end(), page_size());

  if (end > start) {

    MemRegion aligned_region(start, end);

    assert((intptr_t)aligned_region.start()     % page_size() == 0 &&

           (intptr_t)aligned_region.byte_size() % page_size() == 0, "Bad alignment");

    assert(region().contains(aligned_region), "Sanity");

    // First we tell the OS which page size we want in the given range. The underlying

    // large page can be broken down if we require small pages.

    os::realign_memory((char*)aligned_region.start(), aligned_region.byte_size(), page_size());

    // Then we uncommit the pages in the range.

    os::free_memory((char*)aligned_region.start(), aligned_region.byte_size(), page_size());

    // And make them local/first-touch biased.

    os::numa_make_local((char*)aligned_region.start(), aligned_region.byte_size(), lgrp_id);

  }

}

// Free all pages in the region.

void MutableNUMASpace::free_region(MemRegion mr) {

  HeapWord *start = (HeapWord*)round_to((intptr_t)mr.start(), page_size());

  HeapWord *end = (HeapWord*)round_down((intptr_t)mr.end(), page_size());

  if (end > start) {

    MemRegion aligned_region(start, end);

    assert((intptr_t)aligned_region.start()     % page_size() == 0 &&

           (intptr_t)aligned_region.byte_size() % page_size() == 0, "Bad alignment");

    assert(region().contains(aligned_region), "Sanity");

    os::free_memory((char*)aligned_region.start(), aligned_region.byte_size(), page_size());

  }

}

// Update space layout. Perform adaptation.

void MutableNUMASpace::update() {

  if (update_layout(false)) {

    // If the topology has changed, make all chunks zero-sized.

    // And clear the alloc-rate statistics.

    // In future we may want to handle this more gracefully in order

    // to avoid the reallocation of the pages as much as possible.

    for (int i = 0; i < lgrp_spaces()->length(); i++) {

      LGRPSpace *ls = lgrp_spaces()->at(i);

      MutableSpace *s = ls->space();

      s->set_end(s->bottom());

      s->set_top(s->bottom());

      ls->clear_alloc_rate();

    }

    // A NUMA space is never mangled

    initialize(region(),

               SpaceDecorator::Clear,

               SpaceDecorator::DontMangle);

  } else {

    bool should_initialize = false;

    if (!os::numa_has_static_binding()) {

      for (int i = 0; i < lgrp_spaces()->length(); i++) {

        if (!lgrp_spaces()->at(i)->invalid_region().is_empty()) {

          should_initialize = true;

          break;

        }

      }

    }

    if (should_initialize ||

        (UseAdaptiveNUMAChunkSizing && adaptation_cycles() < samples_count())) {

      // A NUMA space is never mangled

      initialize(region(),

                 SpaceDecorator::Clear,

                 SpaceDecorator::DontMangle);

    }

  }

  if (NUMAStats) {

    for (int i = 0; i < lgrp_spaces()->length(); i++) {

      lgrp_spaces()->at(i)->accumulate_statistics(page_size());

    }

  }

  scan_pages(NUMAPageScanRate);

}

// Scan pages. Free pages that have smaller size or wrong placement.

void MutableNUMASpace::scan_pages(size_t page_count)

{

  size_t pages_per_chunk = page_count / lgrp_spaces()->length();

  if (pages_per_chunk > 0) {

    for (int i = 0; i < lgrp_spaces()->length(); i++) {

      LGRPSpace *ls = lgrp_spaces()->at(i);

      ls->scan_pages(page_size(), pages_per_chunk);

    }

  }

}

// Accumulate statistics about the allocation rate of each lgrp.

void MutableNUMASpace::accumulate_statistics() {

  if (UseAdaptiveNUMAChunkSizing) {

    for (int i = 0; i < lgrp_spaces()->length(); i++) {

      lgrp_spaces()->at(i)->sample();

    }

    increment_samples_count();

  }

  if (NUMAStats) {

    for (int i = 0; i < lgrp_spaces()->length(); i++) {

      lgrp_spaces()->at(i)->accumulate_statistics(page_size());

    }

  }

}

// Get the current size of a chunk.

// This function computes the size of the chunk based on the

// difference between chunk ends. This allows it to work correctly in

// case the whole space is resized and during the process of adaptive

// chunk resizing.

size_t MutableNUMASpace::current_chunk_size(int i) {

  HeapWord *cur_end, *prev_end;

  if (i == 0) {

    prev_end = bottom();

  } else {

    prev_end = lgrp_spaces()->at(i - 1)->space()->end();

  }

  if (i == lgrp_spaces()->length() - 1) {

    cur_end = end();

  } else {

    cur_end = lgrp_spaces()->at(i)->space()->end();

  }

  if (cur_end > prev_end) {

    return pointer_delta(cur_end, prev_end, sizeof(char));

  }

  return 0;

}

// Return the default chunk size by equally diving the space.

// page_size() aligned.

size_t MutableNUMASpace::default_chunk_size() {

  return base_space_size() / lgrp_spaces()->length() * page_size();

}

// Produce a new chunk size. page_size() aligned.

// This function is expected to be called on sequence of i's from 0 to

// lgrp_spaces()->length().

size_t MutableNUMASpace::adaptive_chunk_size(int i, size_t limit) {

  size_t pages_available = base_space_size();

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

    pages_available -= round_down(current_chunk_size(j), page_size()) / page_size();

  }

  pages_available -= lgrp_spaces()->length() - i - 1;

  assert(pages_available > 0, "No pages left");

  float alloc_rate = 0;

  for (int j = i; j < lgrp_spaces()->length(); j++) {

    alloc_rate += lgrp_spaces()->at(j)->alloc_rate()->average();

  }

  size_t chunk_size = 0;

  if (alloc_rate > 0) {

    LGRPSpace *ls = lgrp_spaces()->at(i);

    chunk_size = (size_t)(ls->alloc_rate()->average() / alloc_rate * pages_available) * page_size();

  }

  chunk_size = MAX2(chunk_size, page_size());

  if (limit > 0) {

    limit = round_down(limit, page_size());

    if (chunk_size > current_chunk_size(i)) {

      size_t upper_bound = pages_available * page_size();

      if (upper_bound > limit &&

          current_chunk_size(i) < upper_bound - limit) {

        // The resulting upper bound should not exceed the available

        // amount of memory (pages_available * page_size()).

        upper_bound = current_chunk_size(i) + limit;

      }

      chunk_size = MIN2(chunk_size, upper_bound);

    } else {

      size_t lower_bound = page_size();

      if (current_chunk_size(i) > limit) { // lower_bound shouldn't underflow.

        lower_bound = current_chunk_size(i) - limit;

      }

      chunk_size = MAX2(chunk_size, lower_bound);

    }

  }

  assert(chunk_size <= pages_available * page_size(), "Chunk size out of range");

  return chunk_size;

}

// Return the bottom_region and the top_region. Align them to page_size() boundary.

// |------------------new_region---------------------------------|

// |----bottom_region--|---intersection---|------top_region------|

void MutableNUMASpace::select_tails(MemRegion new_region, MemRegion intersection,

                                    MemRegion* bottom_region, MemRegion *top_region) {

  // Is there bottom?

  if (new_region.start() < intersection.start()) { // Yes

    // Try to coalesce small pages into a large one.

    if (UseLargePages && page_size() >= alignment()) {

      HeapWord* p = (HeapWord*)round_to((intptr_t) intersection.start(), alignment());

      if (new_region.contains(p)

          && pointer_delta(p, new_region.start(), sizeof(char)) >= alignment()) {

        if (intersection.contains(p)) {

          intersection = MemRegion(p, intersection.end());

        } else {

          intersection = MemRegion(p, p);

        }

      }

    }

    *bottom_region = MemRegion(new_region.start(), intersection.start());

  } else {

    *bottom_region = MemRegion();

  }

  // Is there top?

  if (intersection.end() < new_region.end()) { // Yes

    // Try to coalesce small pages into a large one.

    if (UseLargePages && page_size() >= alignment()) {

      HeapWord* p = (HeapWord*)round_down((intptr_t) intersection.end(), alignment());

      if (new_region.contains(p)

          && pointer_delta(new_region.end(), p, sizeof(char)) >= alignment()) {

        if (intersection.contains(p)) {

          intersection = MemRegion(intersection.start(), p);

        } else {

          intersection = MemRegion(p, p);

        }

      }

    }

    *top_region = MemRegion(intersection.end(), new_region.end());

  } else {

    *top_region = MemRegion();

  }

}

// Try to merge the invalid region with the bottom or top region by decreasing

// the intersection area. Return the invalid_region aligned to the page_size()

// boundary if it's inside the intersection. Return non-empty invalid_region

// if it lies inside the intersection (also page-aligned).

// |------------------new_region---------------------------------|

// |----------------|-------invalid---|--------------------------|

// |----bottom_region--|---intersection---|------top_region------|

void MutableNUMASpace::merge_regions(MemRegion new_region, MemRegion* intersection,

                                     MemRegion *invalid_region) {

  if (intersection->start() >= invalid_region->start() && intersection->contains(invalid_region->end())) {

    *intersection = MemRegion(invalid_region->end(), intersection->end());

    *invalid_region = MemRegion();

  } else

    if (intersection->end() <= invalid_region->end() && intersection->contains(invalid_region->start())) {

      *intersection = MemRegion(intersection->start(), invalid_region->start());

      *invalid_region = MemRegion();

    } else

      if (intersection->equals(*invalid_region) || invalid_region->contains(*intersection)) {

        *intersection = MemRegion(new_region.start(), new_region.start());