/*

 * Copyright (c) 1998, 2010, 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/handles.inline.hpp"

#include "runtime/interfaceSupport.hpp"

#include "runtime/mutexLocker.hpp"

#include "runtime/objectMonitor.hpp"

#include "runtime/objectMonitor.inline.hpp"

#include "runtime/osThread.hpp"

#include "runtime/stubRoutines.hpp"

#include "runtime/thread.hpp"

#include "services/threadService.hpp"

#include "utilities/dtrace.hpp"

#include "utilities/preserveException.hpp"

#ifdef TARGET_OS_FAMILY_linux

# include "os_linux.inline.hpp"

# include "thread_linux.inline.hpp"

#endif

#ifdef TARGET_OS_FAMILY_solaris

# include "os_solaris.inline.hpp"

# include "thread_solaris.inline.hpp"

#endif

#ifdef TARGET_OS_FAMILY_windows

# include "os_windows.inline.hpp"

# include "thread_windows.inline.hpp"

#endif

#if defined(__GNUC__) && !defined(IA64)

  // Need to inhibit inlining for older versions of GCC to avoid build-time failures

  #define ATTR __attribute__((noinline))

#else

  #define ATTR

#endif

#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.

HS_DTRACE_PROBE_DECL4(hotspot, monitor__notify,

  jlong, uintptr_t, char*, int);

HS_DTRACE_PROBE_DECL4(hotspot, monitor__notifyAll,

  jlong, uintptr_t, char*, int);

HS_DTRACE_PROBE_DECL4(hotspot, monitor__contended__enter,

  jlong, uintptr_t, char*, int);

HS_DTRACE_PROBE_DECL4(hotspot, monitor__contended__entered,

  jlong, uintptr_t, char*, int);

HS_DTRACE_PROBE_DECL4(hotspot, monitor__contended__exit,

  jlong, uintptr_t, char*, int);

#define DTRACE_MONITOR_PROBE_COMMON(klassOop, thread)                      \

  char* bytes = NULL;                                                      \

  int len = 0;                                                             \

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

  if (klassname != NULL) {                                                 \

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

    len = klassname->utf8_length();                                        \

  }

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

  {                                                                        \

    if (DTraceMonitorProbes) {                                            \

      DTRACE_MONITOR_PROBE_COMMON(klassOop, thread);                       \

      HS_DTRACE_PROBE5(hotspot, monitor__wait, jtid,                       \

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

    }                                                                      \

  }

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

  {                                                                        \

    if (DTraceMonitorProbes) {                                            \

      DTRACE_MONITOR_PROBE_COMMON(klassOop, thread);                       \

      HS_DTRACE_PROBE4(hotspot, monitor__##probe, jtid,                    \

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

    }                                                                      \

  }

#else //  ndef DTRACE_ENABLED

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

#define DTRACE_MONITOR_PROBE(probe, klassOop, 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_Verbose    = 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.

//   See http://j2se.east/~dice/PERSIST/040825-LockFreeQueues.html

//

// * 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() epilog) 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 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

bool ObjectMonitor::try_enter(Thread* THREAD) {

  if (THREAD != _owner) {

    if (THREAD->is_lock_owned ((address)_owner)) {

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

       _owner = THREAD ;

       _recursions = 1 ;

       OwnerIsThread = 1 ;

       return true;

    }

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

      return false;

    }

    return true;

  } else {

    _recursions++;

    return true;

  }

}

void ATTR ObjectMonitor::enter(TRAPS) {

  // 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 ;

  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") ;

     // CONSIDER: set or assert OwnerIsThread == 1

     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 ;

    OwnerIsThread = 1 ;

    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_ptr(&_count);

  { // 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);

    }

    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 (Self) ;

      jt->java_suspend_self();

    }

    Self->set_current_pending_monitor(NULL);

  }

  Atomic::dec_ptr(&_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);

  }

  if (ObjectMonitor::_sync_ContendedLockAttempts != NULL) {

     ObjectMonitor::_sync_ContendedLockAttempts->inc() ;

  }

}

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

// Callers must compensate as needed.

int ObjectMonitor::TryLock (Thread * Self) {

   for (;;) {

      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") ;

         // CONSIDER: set or assert that OwnerIsThread == 1

         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.

      if (true) return -1 ;

   }

}

void ATTR ObjectMonitor::EnterI (TRAPS) {

    Thread * 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.

    // The Responsible thread uses a timed park instead of a normal indefinite park

    // operation -- it periodically wakes and checks for and recovers from potential

    // strandings admitted by 1-0 exit operations.   We need at most one Responsible

    // thread per-monitor at any given moment.  Only threads on cxq|EntryList may

    // be responsible for a monitor.

    //

    // Currently, one of the contended threads takes on the added role of "Responsible".

    // A viable alternative would be to use a dedicated "stranding checker" thread

    // that periodically iterated over all the threads (or active monitors) and unparked

    // successors where there was risk of stranding.  This would help eliminate the

    // timer scalability issues we see on some platforms as we'd only have one thread

    // -- the checker -- parked on a timer.