/*

 * Copyright (c) 1998, 2016, 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 "classfile/vmSymbols.hpp"

#include "memory/resourceArea.hpp"

#include "oops/markOop.hpp"

#include "oops/oop.inline.hpp"

#include "runtime/atomic.inline.hpp"

#include "runtime/handles.inline.hpp"

#include "runtime/interfaceSupport.hpp"

#include "runtime/mutexLocker.hpp"

#include "runtime/objectMonitor.hpp"

#include "runtime/objectMonitor.inline.hpp"

#include "runtime/orderAccess.inline.hpp"

#include "runtime/osThread.hpp"

#include "runtime/stubRoutines.hpp"

#include "runtime/thread.inline.hpp"

#include "services/threadService.hpp"

#include "trace/tracing.hpp"

#include "trace/traceMacros.hpp"

#include "utilities/dtrace.hpp"

#include "utilities/macros.hpp"

#include "utilities/preserveException.hpp"

#ifdef DTRACE_ENABLED

// Only bother with this argument setup if dtrace is available

// TODO-FIXME: probes should not fire when caller is _blocked.  assert() accordingly.

#define DTRACE_MONITOR_PROBE_COMMON(obj, thread)                           \

  char* bytes = NULL;                                                      \

  int len = 0;                                                             \

  jlong jtid = SharedRuntime::get_java_tid(thread);                        \

  Symbol* klassname = ((oop)obj)->klass()->name();                         \

  if (klassname != NULL) {                                                 \

    bytes = (char*)klassname->bytes();                                     \

    len = klassname->utf8_length();                                        \

  }

#define DTRACE_MONITOR_WAIT_PROBE(monitor, obj, thread, millis)            \

  {                                                                        \

    if (DTraceMonitorProbes) {                                             \

      DTRACE_MONITOR_PROBE_COMMON(obj, thread);                            \

      HOTSPOT_MONITOR_WAIT(jtid,                                           \

                           (monitor), bytes, len, (millis));               \

    }                                                                      \

  }

#define HOTSPOT_MONITOR_contended__enter HOTSPOT_MONITOR_CONTENDED_ENTER

#define HOTSPOT_MONITOR_contended__entered HOTSPOT_MONITOR_CONTENDED_ENTERED

#define HOTSPOT_MONITOR_contended__exit HOTSPOT_MONITOR_CONTENDED_EXIT

#define HOTSPOT_MONITOR_notify HOTSPOT_MONITOR_NOTIFY

#define HOTSPOT_MONITOR_notifyAll HOTSPOT_MONITOR_NOTIFYALL

#define DTRACE_MONITOR_PROBE(probe, monitor, obj, thread)                  \

  {                                                                        \

    if (DTraceMonitorProbes) {                                             \

      DTRACE_MONITOR_PROBE_COMMON(obj, thread);                            \

      HOTSPOT_MONITOR_##probe(jtid,                                        \

                              (uintptr_t)(monitor), bytes, len);           \

    }                                                                      \

  }

#else //  ndef DTRACE_ENABLED

#define DTRACE_MONITOR_WAIT_PROBE(obj, thread, millis, mon)    {;}

#define DTRACE_MONITOR_PROBE(probe, obj, thread, mon)          {;}

#endif // ndef DTRACE_ENABLED

// Tunables ...

// The knob* variables are effectively final.  Once set they should

// never be modified hence.  Consider using __read_mostly with GCC.

int ObjectMonitor::Knob_ExitRelease = 0;

int ObjectMonitor::Knob_Verbose     = 0;

int ObjectMonitor::Knob_VerifyInUse = 0;

int ObjectMonitor::Knob_VerifyMatch = 0;

int ObjectMonitor::Knob_SpinLimit   = 5000;    // derived by an external tool -

static int Knob_LogSpins            = 0;       // enable jvmstat tally for spins

static int Knob_HandOff             = 0;

static int Knob_ReportSettings      = 0;

static int Knob_SpinBase            = 0;       // Floor AKA SpinMin

static int Knob_SpinBackOff         = 0;       // spin-loop backoff

static int Knob_CASPenalty          = -1;      // Penalty for failed CAS

static int Knob_OXPenalty           = -1;      // Penalty for observed _owner change

static int Knob_SpinSetSucc         = 1;       // spinners set the _succ field

static int Knob_SpinEarly           = 1;

static int Knob_SuccEnabled         = 1;       // futile wake throttling

static int Knob_SuccRestrict        = 0;       // Limit successors + spinners to at-most-one

static int Knob_MaxSpinners         = -1;      // Should be a function of # CPUs

static int Knob_Bonus               = 100;     // spin success bonus

static int Knob_BonusB              = 100;     // spin success bonus

static int Knob_Penalty             = 200;     // spin failure penalty

static int Knob_Poverty             = 1000;

static int Knob_SpinAfterFutile     = 1;       // Spin after returning from park()

static int Knob_FixedSpin           = 0;

static int Knob_OState              = 3;       // Spinner checks thread state of _owner

static int Knob_UsePause            = 1;

static int Knob_ExitPolicy          = 0;

static int Knob_PreSpin             = 10;      // 20-100 likely better

static int Knob_ResetEvent          = 0;

static int BackOffMask              = 0;

static int Knob_FastHSSEC           = 0;

static int Knob_MoveNotifyee        = 2;       // notify() - disposition of notifyee

static int Knob_QMode               = 0;       // EntryList-cxq policy - queue discipline

static volatile int InitDone        = 0;

#define TrySpin TrySpin_VaryDuration

// -----------------------------------------------------------------------------

// Theory of operations -- Monitors lists, thread residency, etc:

//

// * A thread acquires ownership of a monitor by successfully

//   CAS()ing the _owner field from null to non-null.

//

// * Invariant: A thread appears on at most one monitor list --

//   cxq, EntryList or WaitSet -- at any one time.

//

// * Contending threads "push" themselves onto the cxq with CAS

//   and then spin/park.

//

// * After a contending thread eventually acquires the lock it must

//   dequeue itself from either the EntryList or the cxq.

//

// * The exiting thread identifies and unparks an "heir presumptive"

//   tentative successor thread on the EntryList.  Critically, the

//   exiting thread doesn't unlink the successor thread from the EntryList.

//   After having been unparked, the wakee will recontend for ownership of

//   the monitor.   The successor (wakee) will either acquire the lock or

//   re-park itself.

//

//   Succession is provided for by a policy of competitive handoff.

//   The exiting thread does _not_ grant or pass ownership to the

//   successor thread.  (This is also referred to as "handoff" succession").

//   Instead the exiting thread releases ownership and possibly wakes

//   a successor, so the successor can (re)compete for ownership of the lock.

//   If the EntryList is empty but the cxq is populated the exiting

//   thread will drain the cxq into the EntryList.  It does so by

//   by detaching the cxq (installing null with CAS) and folding

//   the threads from the cxq into the EntryList.  The EntryList is

//   doubly linked, while the cxq is singly linked because of the

//   CAS-based "push" used to enqueue recently arrived threads (RATs).

//

// * Concurrency invariants:

//

//   -- only the monitor owner may access or mutate the EntryList.

//      The mutex property of the monitor itself protects the EntryList

//      from concurrent interference.

//   -- Only the monitor owner may detach the cxq.

//

// * The monitor entry list operations avoid locks, but strictly speaking

//   they're not lock-free.  Enter is lock-free, exit is not.

//   For a description of 'Methods and apparatus providing non-blocking access

//   to a resource,' see U.S. Pat. No. 7844973.

//

// * The cxq can have multiple concurrent "pushers" but only one concurrent

//   detaching thread.  This mechanism is immune from the ABA corruption.

//   More precisely, the CAS-based "push" onto cxq is ABA-oblivious.

//

// * Taken together, the cxq and the EntryList constitute or form a

//   single logical queue of threads stalled trying to acquire the lock.

//   We use two distinct lists to improve the odds of a constant-time

//   dequeue operation after acquisition (in the ::enter() epilogue) and

//   to reduce heat on the list ends.  (c.f. Michael Scott's "2Q" algorithm).

//   A key desideratum is to minimize queue & monitor metadata manipulation

//   that occurs while holding the monitor lock -- that is, we want to

//   minimize monitor lock holds times.  Note that even a small amount of

//   fixed spinning will greatly reduce the # of enqueue-dequeue operations

//   on EntryList|cxq.  That is, spinning relieves contention on the "inner"

//   locks and monitor metadata.

//

//   Cxq points to the set of Recently Arrived Threads attempting entry.

//   Because we push threads onto _cxq with CAS, the RATs must take the form of

//   a singly-linked LIFO.  We drain _cxq into EntryList  at unlock-time when

//   the unlocking thread notices that EntryList is null but _cxq is != null.

//

//   The EntryList is ordered by the prevailing queue discipline and

//   can be organized in any convenient fashion, such as a doubly-linked list or

//   a circular doubly-linked list.  Critically, we want insert and delete operations

//   to operate in constant-time.  If we need a priority queue then something akin

//   to Solaris' sleepq would work nicely.  Viz.,

//   http://agg.eng/ws/on10_nightly/source/usr/src/uts/common/os/sleepq.c.

//   Queue discipline is enforced at ::exit() time, when the unlocking thread

//   drains the cxq into the EntryList, and orders or reorders the threads on the

//   EntryList accordingly.

//

//   Barring "lock barging", this mechanism provides fair cyclic ordering,

//   somewhat similar to an elevator-scan.

//

// * The monitor synchronization subsystem avoids the use of native

//   synchronization primitives except for the narrow platform-specific

//   park-unpark abstraction.  See the comments in os_solaris.cpp regarding

//   the semantics of park-unpark.  Put another way, this monitor implementation

//   depends only on atomic operations and park-unpark.  The monitor subsystem

//   manages all RUNNING->BLOCKED and BLOCKED->READY transitions while the

//   underlying OS manages the READY<->RUN transitions.

//

// * Waiting threads reside on the WaitSet list -- wait() puts

//   the caller onto the WaitSet.

//

// * notify() or notifyAll() simply transfers threads from the WaitSet to

//   either the EntryList or cxq.  Subsequent exit() operations will

//   unpark the notifyee.  Unparking a notifee in notify() is inefficient -

//   it's likely the notifyee would simply impale itself on the lock held

//   by the notifier.

//

// * An interesting alternative is to encode cxq as (List,LockByte) where

//   the LockByte is 0 iff the monitor is owned.  _owner is simply an auxiliary

//   variable, like _recursions, in the scheme.  The threads or Events that form

//   the list would have to be aligned in 256-byte addresses.  A thread would

//   try to acquire the lock or enqueue itself with CAS, but exiting threads

//   could use a 1-0 protocol and simply STB to set the LockByte to 0.

//   Note that is is *not* word-tearing, but it does presume that full-word

//   CAS operations are coherent with intermix with STB operations.  That's true

//   on most common processors.

//

// * See also http://blogs.sun.com/dave

// -----------------------------------------------------------------------------

// Enter support

  // The following code is ordered to check the most common cases first

  // and to reduce RTS->RTO cache line upgrades on SPARC and IA32 processors.

  Thread * const Self = THREAD;

  void * cur = Atomic::cmpxchg_ptr (Self, &_owner, NULL);

  if (cur == NULL) {

    // Either ASSERT _recursions == 0 or explicitly set _recursions = 0.

    assert(_recursions == 0, "invariant");

    assert(_owner == Self, "invariant");

    return;

  }

  if (cur == Self) {

    // TODO-FIXME: check for integer overflow!  BUGID 6557169.

    _recursions++;

    return;

  }

  if (Self->is_lock_owned ((address)cur)) {

    assert(_recursions == 0, "internal state error");

    _recursions = 1;

    // Commute owner from a thread-specific on-stack BasicLockObject address to

    // a full-fledged "Thread *".

    _owner = Self;

    return;

  }

  // We've encountered genuine contention.

  assert(Self->_Stalled == 0, "invariant");

  Self->_Stalled = intptr_t(this);

  // Try one round of spinning *before* enqueueing Self

  // and before going through the awkward and expensive state

  // transitions.  The following spin is strictly optional ...

  // Note that if we acquire the monitor from an initial spin

  // we forgo posting JVMTI events and firing DTRACE probes.

  if (Knob_SpinEarly && TrySpin (Self) > 0) {

    assert(_owner == Self, "invariant");

    assert(_recursions == 0, "invariant");

    assert(((oop)(object()))->mark() == markOopDesc::encode(this), "invariant");

    Self->_Stalled = 0;

    return;

  }

  assert(_owner != Self, "invariant");

  assert(_succ != Self, "invariant");

  assert(Self->is_Java_thread(), "invariant");

  JavaThread * jt = (JavaThread *) Self;

  assert(!SafepointSynchronize::is_at_safepoint(), "invariant");

  assert(jt->thread_state() != _thread_blocked, "invariant");

  assert(this->object() != NULL, "invariant");

  assert(_count >= 0, "invariant");

  // Prevent deflation at STW-time.  See deflate_idle_monitors() and is_busy().

  // Ensure the object-monitor relationship remains stable while there's contention.

  Atomic::inc(&_count);

  EventJavaMonitorEnter event;

  { // Change java thread status to indicate blocked on monitor enter.

    JavaThreadBlockedOnMonitorEnterState jtbmes(jt, this);

    DTRACE_MONITOR_PROBE(contended__enter, this, object(), jt);

    if (JvmtiExport::should_post_monitor_contended_enter()) {

      JvmtiExport::post_monitor_contended_enter(jt, this);

      // The current thread does not yet own the monitor and does not

      // yet appear on any queues that would get it made the successor.

      // This means that the JVMTI_EVENT_MONITOR_CONTENDED_ENTER event

      // handler cannot accidentally consume an unpark() meant for the

      // ParkEvent associated with this ObjectMonitor.

    }

    OSThreadContendState osts(Self->osthread());

    ThreadBlockInVM tbivm(jt);

    Self->set_current_pending_monitor(this);

    // TODO-FIXME: change the following for(;;) loop to straight-line code.

    for (;;) {

      jt->set_suspend_equivalent();

      // cleared by handle_special_suspend_equivalent_condition()

      // or java_suspend_self()

      EnterI(THREAD);

      if (!ExitSuspendEquivalent(jt)) break;

      // We have acquired the contended monitor, but while we were

      // waiting another thread suspended us. We don't want to enter

      // the monitor while suspended because that would surprise the

      // thread that suspended us.

      //

      _recursions = 0;

      _succ = NULL;

      exit(false, Self);

      jt->java_suspend_self();

    }

    Self->set_current_pending_monitor(NULL);

    // We cleared the pending monitor info since we've just gotten past

    // the enter-check-for-suspend dance and we now own the monitor free

    // and clear, i.e., it is no longer pending. The ThreadBlockInVM

    // destructor can go to a safepoint at the end of this block. If we

    // do a thread dump during that safepoint, then this thread will show

    // as having "-locked" the monitor, but the OS and java.lang.Thread

    // states will still report that the thread is blocked trying to

    // acquire it.

  }

  Atomic::dec(&_count);

  assert(_count >= 0, "invariant");

  Self->_Stalled = 0;

  // Must either set _recursions = 0 or ASSERT _recursions == 0.

  assert(_recursions == 0, "invariant");

  assert(_owner == Self, "invariant");

  assert(_succ != Self, "invariant");

  assert(((oop)(object()))->mark() == markOopDesc::encode(this), "invariant");

  // The thread -- now the owner -- is back in vm mode.

  // Report the glorious news via TI,DTrace and jvmstat.

  // The probe effect is non-trivial.  All the reportage occurs

  // while we hold the monitor, increasing the length of the critical

  // section.  Amdahl's parallel speedup law comes vividly into play.

  //

  // Another option might be to aggregate the events (thread local or

  // per-monitor aggregation) and defer reporting until a more opportune

  // time -- such as next time some thread encounters contention but has

  // yet to acquire the lock.  While spinning that thread could

  // spinning we could increment JVMStat counters, etc.

  DTRACE_MONITOR_PROBE(contended__entered, this, object(), jt);

  if (JvmtiExport::should_post_monitor_contended_entered()) {

    JvmtiExport::post_monitor_contended_entered(jt, this);

    // The current thread already owns the monitor and is not going to

    // call park() for the remainder of the monitor enter protocol. So

    // it doesn't matter if the JVMTI_EVENT_MONITOR_CONTENDED_ENTERED

    // event handler consumed an unpark() issued by the thread that

    // just exited the monitor.

  }

  if (event.should_commit()) {

    event.set_klass(((oop)this->object())->klass());

    event.set_previousOwner((TYPE_THREAD)_previous_owner_tid);

    event.set_address((TYPE_ADDRESS)(uintptr_t)(this->object_addr()));

    event.commit();

  }

  OM_PERFDATA_OP(ContendedLockAttempts, inc());

}

// Caveat: TryLock() is not necessarily serializing if it returns failure.

// Callers must compensate as needed.

int ObjectMonitor::TryLock(Thread * Self) {

  void * own = _owner;

  if (own != NULL) return 0;

  if (Atomic::cmpxchg_ptr (Self, &_owner, NULL) == NULL) {

    // Either guarantee _recursions == 0 or set _recursions = 0.

    assert(_recursions == 0, "invariant");

    assert(_owner == Self, "invariant");

    return 1;

  }

  // The lock had been free momentarily, but we lost the race to the lock.

  // Interference -- the CAS failed.

  // We can either return -1 or retry.

  // Retry doesn't make as much sense because the lock was just acquired.

  return -1;

}

#define MAX_RECHECK_INTERVAL 1000

  Thread * const Self = THREAD;

  assert(Self->is_Java_thread(), "invariant");

  assert(((JavaThread *) Self)->thread_state() == _thread_blocked, "invariant");

  // Try the lock - TATAS

  if (TryLock (Self) > 0) {

    assert(_succ != Self, "invariant");

    assert(_owner == Self, "invariant");

    assert(_Responsible != Self, "invariant");

    return;

  }

  DeferredInitialize();

  // We try one round of spinning *before* enqueueing Self.

  //

  // If the _owner is ready but OFFPROC we could use a YieldTo()

  // operation to donate the remainder of this thread's quantum

  // to the owner.  This has subtle but beneficial affinity

  // effects.

  if (TrySpin (Self) > 0) {

    assert(_owner == Self, "invariant");

    assert(_succ != Self, "invariant");

    assert(_Responsible != Self, "invariant");

    return;

  }

  // The Spin failed -- Enqueue and park the thread ...

  assert(_succ != Self, "invariant");

  assert(_owner != Self, "invariant");

  assert(_Responsible != Self, "invariant");

  // Enqueue "Self" on ObjectMonitor's _cxq.

  //

  // Node acts as a proxy for Self.

  // As an aside, if were to ever rewrite the synchronization code mostly

  // in Java, WaitNodes, ObjectMonitors, and Events would become 1st-class

  // Java objects.  This would avoid awkward lifecycle and liveness issues,

  // as well as eliminate a subset of ABA issues.

  // TODO: eliminate ObjectWaiter and enqueue either Threads or Events.

  ObjectWaiter node(Self);

  Self->_ParkEvent->reset();

  node._prev   = (ObjectWaiter *) 0xBAD;

  node.TState  = ObjectWaiter::TS_CXQ;

  // Push "Self" onto the front of the _cxq.

  // Once on cxq/EntryList, Self stays on-queue until it acquires the lock.

  // Note that spinning tends to reduce the rate at which threads

  // enqueue and dequeue on EntryList|cxq.

  ObjectWaiter * nxt;

  for (;;) {

    node._next = nxt = _cxq;

    if (Atomic::cmpxchg_ptr(&node, &_cxq, nxt) == nxt) break;

    // Interference - the CAS failed because _cxq changed.  Just retry.

    // As an optional optimization we retry the lock.

    if (TryLock (Self) > 0) {

      assert(_succ != Self, "invariant");

      assert(_owner == Self, "invariant");

      assert(_Responsible != Self, "invariant");

      return;

    }

  }

  // Check for cxq|EntryList edge transition to non-null.  This indicates

  // the onset of contention.  While contention persists exiting threads

  // will use a ST:MEMBAR:LD 1-1 exit protocol.  When contention abates exit

  // operations revert to the faster 1-0 mode.  This enter operation may interleave

  // (race) a concurrent 1-0 exit operation, resulting in stranding, so we

  // arrange for one of the contending thread to use a timed park() operations

  // to detect and recover from the race.  (Stranding is form of progress failure

  // where the monitor is unlocked but all the contending threads remain parked).

  // That is, at least one of the contended threads will periodically poll _owner.

  // One of the contending threads will become the designated "Responsible" thread.