/*

 * Copyright (c) 2002, 2015, 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/parallel/gcTaskManager.hpp"

#include "gc/parallel/gcTaskThread.hpp"

#include "gc/shared/adaptiveSizePolicy.hpp"

#include "gc/shared/gcId.hpp"

#include "logging/log.hpp"

#include "memory/allocation.hpp"

#include "memory/allocation.inline.hpp"

#include "runtime/mutex.hpp"

#include "runtime/mutexLocker.hpp"

#include "runtime/orderAccess.inline.hpp"

//

// GCTask

//

const char* GCTask::Kind::to_string(kind value) {

  const char* result = "unknown GCTask kind";

  switch (value) {

  default:

    result = "unknown GCTask kind";

    break;

  case unknown_task:

    result = "unknown task";

    break;

  case ordinary_task:

    result = "ordinary task";

    break;

  case wait_for_barrier_task:

    result = "wait for barrier task";

    break;

  case noop_task:

    result = "noop task";

    break;

  case idle_task:

    result = "idle task";

    break;

  }

  return result;

};

GCTask::GCTask() {

  initialize(Kind::ordinary_task, GCId::current());

}

GCTask::GCTask(Kind::kind kind) {

  initialize(kind, GCId::current());

}

GCTask::GCTask(Kind::kind kind, uint gc_id) {

  initialize(kind, gc_id);

}

void GCTask::initialize(Kind::kind kind, uint gc_id) {

  _kind = kind;

  _affinity = GCTaskManager::sentinel_worker();

  _older = NULL;

  _newer = NULL;

  _gc_id = gc_id;

}

void GCTask::destruct() {

  assert(older() == NULL, "shouldn't have an older task");

  assert(newer() == NULL, "shouldn't have a newer task");

  // Nothing to do.

}

NOT_PRODUCT(

void GCTask::print(const char* message) const {

  tty->print(INTPTR_FORMAT " <- " INTPTR_FORMAT "(%u) -> " INTPTR_FORMAT,

             p2i(newer()), p2i(this), affinity(), p2i(older()));

}

)

//

// GCTaskQueue

//

GCTaskQueue* GCTaskQueue::create() {

  GCTaskQueue* result = new GCTaskQueue(false);

  if (TraceGCTaskQueue) {

    tty->print_cr("GCTaskQueue::create()"

                  " returns " INTPTR_FORMAT, p2i(result));

  }

  return result;

}

GCTaskQueue* GCTaskQueue::create_on_c_heap() {

  GCTaskQueue* result = new(ResourceObj::C_HEAP, mtGC) GCTaskQueue(true);

  if (TraceGCTaskQueue) {

    tty->print_cr("GCTaskQueue::create_on_c_heap()"

                  " returns " INTPTR_FORMAT,

                  p2i(result));

  }

  return result;

}

GCTaskQueue::GCTaskQueue(bool on_c_heap) :

  _is_c_heap_obj(on_c_heap) {

  initialize();

  if (TraceGCTaskQueue) {

    tty->print_cr("[" INTPTR_FORMAT "]"

                  " GCTaskQueue::GCTaskQueue() constructor",

                  p2i(this));

  }

}

void GCTaskQueue::destruct() {

  // Nothing to do.

}

void GCTaskQueue::destroy(GCTaskQueue* that) {

  if (TraceGCTaskQueue) {

    tty->print_cr("[" INTPTR_FORMAT "]"

                  " GCTaskQueue::destroy()"

                  "  is_c_heap_obj:  %s",

                  p2i(that),

                  that->is_c_heap_obj() ? "true" : "false");

  }

  // That instance may have been allocated as a CHeapObj,

  // in which case we have to free it explicitly.

  if (that != NULL) {

    that->destruct();

    assert(that->is_empty(), "should be empty");

    if (that->is_c_heap_obj()) {

      FreeHeap(that);

    }

  }

}

void GCTaskQueue::initialize() {

  set_insert_end(NULL);

  set_remove_end(NULL);

  set_length(0);

}

// Enqueue one task.

void GCTaskQueue::enqueue(GCTask* task) {

  if (TraceGCTaskQueue) {

    tty->print_cr("[" INTPTR_FORMAT "]"

                  " GCTaskQueue::enqueue(task: "

                  INTPTR_FORMAT ")",

                  p2i(this), p2i(task));

    print("before:");

  }

  assert(task != NULL, "shouldn't have null task");

  assert(task->older() == NULL, "shouldn't be on queue");

  assert(task->newer() == NULL, "shouldn't be on queue");

  task->set_newer(NULL);

  task->set_older(insert_end());

  if (is_empty()) {

    set_remove_end(task);

  } else {

    insert_end()->set_newer(task);

  }

  set_insert_end(task);

  increment_length();

  verify_length();

  if (TraceGCTaskQueue) {

    print("after:");

  }

}

// Enqueue a whole list of tasks.  Empties the argument list.

void GCTaskQueue::enqueue(GCTaskQueue* list) {

  if (TraceGCTaskQueue) {

    tty->print_cr("[" INTPTR_FORMAT "]"

                  " GCTaskQueue::enqueue(list: "

                  INTPTR_FORMAT ")",

                  p2i(this), p2i(list));

    print("before:");

    list->print("list:");

  }

  if (list->is_empty()) {

    // Enqueueing the empty list: nothing to do.

    return;

  }

  uint list_length = list->length();

  if (is_empty()) {

    // Enqueueing to empty list: just acquire elements.

    set_insert_end(list->insert_end());

    set_remove_end(list->remove_end());

    set_length(list_length);

  } else {

    // Prepend argument list to our queue.

    list->remove_end()->set_older(insert_end());

    insert_end()->set_newer(list->remove_end());

    set_insert_end(list->insert_end());

    set_length(length() + list_length);

    // empty the argument list.

  }

  list->initialize();

  if (TraceGCTaskQueue) {

    print("after:");

    list->print("list:");

  }

  verify_length();

}

// Dequeue one task.

GCTask* GCTaskQueue::dequeue() {

  if (TraceGCTaskQueue) {

    tty->print_cr("[" INTPTR_FORMAT "]"

                  " GCTaskQueue::dequeue()", p2i(this));

    print("before:");

  }

  assert(!is_empty(), "shouldn't dequeue from empty list");

  GCTask* result = remove();

  assert(result != NULL, "shouldn't have NULL task");

  if (TraceGCTaskQueue) {

    tty->print_cr("    return: " INTPTR_FORMAT, p2i(result));

    print("after:");

  }

  return result;

}

// Dequeue one task, preferring one with affinity.

GCTask* GCTaskQueue::dequeue(uint affinity) {

  if (TraceGCTaskQueue) {

    tty->print_cr("[" INTPTR_FORMAT "]"

                  " GCTaskQueue::dequeue(%u)", p2i(this), affinity);

    print("before:");

  }

  assert(!is_empty(), "shouldn't dequeue from empty list");

  // Look down to the next barrier for a task with this affinity.

  GCTask* result = NULL;

  for (GCTask* element = remove_end();

       element != NULL;

       element = element->newer()) {

    if (element->is_barrier_task()) {

      // Don't consider barrier tasks, nor past them.

      result = NULL;

      break;

    }

    if (element->affinity() == affinity) {

      result = remove(element);

      break;

    }

  }

  // If we didn't find anything with affinity, just take the next task.

  if (result == NULL) {

    result = remove();

  }

  if (TraceGCTaskQueue) {

    tty->print_cr("    return: " INTPTR_FORMAT, p2i(result));

    print("after:");

  }

  return result;

}

GCTask* GCTaskQueue::remove() {

  // Dequeue from remove end.

  GCTask* result = remove_end();

  assert(result != NULL, "shouldn't have null task");

  assert(result->older() == NULL, "not the remove_end");

  set_remove_end(result->newer());

  if (remove_end() == NULL) {

    assert(insert_end() == result, "not a singleton");

    set_insert_end(NULL);

  } else {

    remove_end()->set_older(NULL);

  }

  result->set_newer(NULL);

  decrement_length();

  assert(result->newer() == NULL, "shouldn't be on queue");

  assert(result->older() == NULL, "shouldn't be on queue");

  verify_length();

  return result;

}

GCTask* GCTaskQueue::remove(GCTask* task) {

  // This is slightly more work, and has slightly fewer asserts

  // than removing from the remove end.

  assert(task != NULL, "shouldn't have null task");

  GCTask* result = task;

  if (result->newer() != NULL) {

    result->newer()->set_older(result->older());

  } else {

    assert(insert_end() == result, "not youngest");

    set_insert_end(result->older());

  }

  if (result->older() != NULL) {

    result->older()->set_newer(result->newer());

  } else {

    assert(remove_end() == result, "not oldest");

    set_remove_end(result->newer());

  }

  result->set_newer(NULL);

  result->set_older(NULL);

  decrement_length();

  verify_length();

  return result;

}

NOT_PRODUCT(

// Count the elements in the queue and verify the length against

// that count.

void GCTaskQueue::verify_length() const {

  uint count = 0;

  for (GCTask* element = insert_end();

       element != NULL;

       element = element->older()) {

    count++;

  }

  assert(count == length(), "Length does not match queue");

}

void GCTaskQueue::print(const char* message) const {

  tty->print_cr("[" INTPTR_FORMAT "] GCTaskQueue:"

                "  insert_end: " INTPTR_FORMAT

                "  remove_end: " INTPTR_FORMAT

                "  length:       %d"

                "  %s",

                p2i(this), p2i(insert_end()), p2i(remove_end()), length(), message);

  uint count = 0;

  for (GCTask* element = insert_end();

       element != NULL;

       element = element->older()) {

    element->print("    ");

    count++;

    tty->cr();

  }

  tty->print("Total tasks: %d", count);

}

)

//

// SynchronizedGCTaskQueue

//

SynchronizedGCTaskQueue::SynchronizedGCTaskQueue(GCTaskQueue* queue_arg,

                                                 Monitor *       lock_arg) :

  _unsynchronized_queue(queue_arg),

  _lock(lock_arg) {

  assert(unsynchronized_queue() != NULL, "null queue");

  assert(lock() != NULL, "null lock");

}

SynchronizedGCTaskQueue::~SynchronizedGCTaskQueue() {

  // Nothing to do.

}

//

// GCTaskManager

//

GCTaskManager::GCTaskManager(uint workers) :

  _workers(workers),

  _active_workers(0),

  _idle_workers(0) {

  initialize();

}

void GCTaskManager::initialize() {

  if (TraceGCTaskManager) {

    tty->print_cr("GCTaskManager::initialize: workers: %u", workers());

  }

  assert(workers() != 0, "no workers");

  _monitor = new Monitor(Mutex::barrier,                // rank

                         "GCTaskManager monitor",       // name

                         Mutex::_allow_vm_block_flag,   // allow_vm_block

                         Monitor::_safepoint_check_never);

  // The queue for the GCTaskManager must be a CHeapObj.

  GCTaskQueue* unsynchronized_queue = GCTaskQueue::create_on_c_heap();

  _queue = SynchronizedGCTaskQueue::create(unsynchronized_queue, lock());

  _noop_task = NoopGCTask::create_on_c_heap();

  _resource_flag = NEW_C_HEAP_ARRAY(bool, workers(), mtGC);

  {

    // Set up worker threads.

    //     Distribute the workers among the available processors,

    //     unless we were told not to, or if the os doesn't want to.

    uint* processor_assignment = NEW_C_HEAP_ARRAY(uint, workers(), mtGC);

    if (!BindGCTaskThreadsToCPUs ||

        !os::distribute_processes(workers(), processor_assignment)) {

      for (uint a = 0; a < workers(); a += 1) {

        processor_assignment[a] = sentinel_worker();

      }

    }

    _thread = NEW_C_HEAP_ARRAY(GCTaskThread*, workers(), mtGC);

    for (uint t = 0; t < workers(); t += 1) {

      set_thread(t, GCTaskThread::create(this, t, processor_assignment[t]));

    }

    if (TraceGCTaskThread) {

      tty->print("GCTaskManager::initialize: distribution:");

      for (uint t = 0; t < workers(); t += 1) {

        tty->print("  %u", processor_assignment[t]);

      }

      tty->cr();

    }

    FREE_C_HEAP_ARRAY(uint, processor_assignment);

  }

  reset_busy_workers();

  set_unblocked();

  for (uint w = 0; w < workers(); w += 1) {

    set_resource_flag(w, false);

  }

  reset_delivered_tasks();

  reset_completed_tasks();

  reset_barriers();

  reset_emptied_queue();

  for (uint s = 0; s < workers(); s += 1) {

    thread(s)->start();

  }

}

GCTaskManager::~GCTaskManager() {

  assert(busy_workers() == 0, "still have busy workers");

  assert(queue()->is_empty(), "still have queued work");

  NoopGCTask::destroy(_noop_task);

  _noop_task = NULL;

  if (_thread != NULL) {

    for (uint i = 0; i < workers(); i += 1) {

      GCTaskThread::destroy(thread(i));

      set_thread(i, NULL);

    }

    FREE_C_HEAP_ARRAY(GCTaskThread*, _thread);

    _thread = NULL;

  }

  if (_resource_flag != NULL) {

    FREE_C_HEAP_ARRAY(bool, _resource_flag);

    _resource_flag = NULL;

  }

  if (queue() != NULL) {

    GCTaskQueue* unsynchronized_queue = queue()->unsynchronized_queue();

    GCTaskQueue::destroy(unsynchronized_queue);

    SynchronizedGCTaskQueue::destroy(queue());

    _queue = NULL;

  }

  if (monitor() != NULL) {

    delete monitor();

    _monitor = NULL;

  }

}

void GCTaskManager::set_active_gang() {

  _active_workers =

    AdaptiveSizePolicy::calc_active_workers(workers(),

                                 active_workers(),

                                 Threads::number_of_non_daemon_threads());

  assert(!all_workers_active() || active_workers() == ParallelGCThreads,

         "all_workers_active() is  incorrect: "

         "active %d  ParallelGCThreads %u", active_workers(),

         ParallelGCThreads);

  log_trace(gc, task)("GCTaskManager::set_active_gang(): "

                      "all_workers_active()  %d  workers %d  "

                      "active  %d  ParallelGCThreads %u",

                      all_workers_active(), workers(),  active_workers(),

                      ParallelGCThreads);

}

// Create IdleGCTasks for inactive workers.

// Creates tasks in a ResourceArea and assumes

// an appropriate ResourceMark.

void GCTaskManager::task_idle_workers() {

  {

    int more_inactive_workers = 0;

    {

      // Stop any idle tasks from exiting their IdleGCTask's

      // and get the count for additional IdleGCTask's under

      // the GCTaskManager's monitor so that the "more_inactive_workers"

      // count is correct.

      MutexLockerEx ml(monitor(), Mutex::_no_safepoint_check_flag);

      _wait_helper.set_should_wait(true);

      // active_workers are a number being requested.  idle_workers

      // are the number currently idle.  If all the workers are being

      // requested to be active but some are already idle, reduce

      // the number of active_workers to be consistent with the

      // number of idle_workers.  The idle_workers are stuck in

      // idle tasks and will no longer be release (since a new GC

      // is starting).  Try later to release enough idle_workers

      // to allow the desired number of active_workers.

      more_inactive_workers =

        workers() - active_workers() - idle_workers();

      if (more_inactive_workers < 0) {

        int reduced_active_workers = active_workers() + more_inactive_workers;

        set_active_workers(reduced_active_workers);

        more_inactive_workers = 0;

      }

      log_trace(gc, task)("JT: %d  workers %d  active  %d  idle %d  more %d",

                          Threads::number_of_non_daemon_threads(),

                          workers(),

                          active_workers(),

                          idle_workers(),

                          more_inactive_workers);

    }

    GCTaskQueue* q = GCTaskQueue::create();

    for(uint i = 0; i < (uint) more_inactive_workers; i++) {

      q->enqueue(IdleGCTask::create_on_c_heap());