/*

 * Copyright (c) 1998, 2009, 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 "incls/_precompiled.incl"

# include "incls/_synchronizer.cpp.incl"

#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

// Native markword accessors for synchronization and hashCode().

//

// The "core" versions of monitor enter and exit reside in this file.

// The interpreter and compilers contain specialized transliterated

// variants of the enter-exit fast-path operations.  See i486.ad fast_lock(),

// for instance.  If you make changes here, make sure to modify the

// interpreter, and both C1 and C2 fast-path inline locking code emission.

//

// TODO: merge the objectMonitor and synchronizer classes.

//

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

#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_DECL5(hotspot, monitor__wait,

  jlong, uintptr_t, char*, int, long);

HS_DTRACE_PROBE_DECL4(hotspot, monitor__waited,

  jlong, uintptr_t, char*, int);

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

  symbolOop klassname = ((oop)(klassOop))->klass()->klass_part()->name();  \

  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

// ObjectWaiter serves as a "proxy" or surrogate thread.

// TODO-FIXME: Eliminate ObjectWaiter and use the thread-specific

// ParkEvent instead.  Beware, however, that the JVMTI code

// knows about ObjectWaiters, so we'll have to reconcile that code.

// See next_waiter(), first_waiter(), etc.

class ObjectWaiter : public StackObj {

 public:

  enum TStates { TS_UNDEF, TS_READY, TS_RUN, TS_WAIT, TS_ENTER, TS_CXQ } ;

  enum Sorted  { PREPEND, APPEND, SORTED } ;

  ObjectWaiter * volatile _next;

  ObjectWaiter * volatile _prev;

  Thread*       _thread;

  ParkEvent *   _event;

  volatile int  _notified ;

  volatile TStates TState ;

  Sorted        _Sorted ;           // List placement disposition

  bool          _active ;           // Contention monitoring is enabled

 public:

  ObjectWaiter(Thread* thread) {

    _next     = NULL;

    _prev     = NULL;

    _notified = 0;

    TState    = TS_RUN ;

    _thread   = thread;

    _event    = thread->_ParkEvent ;

    _active   = false;

    assert (_event != NULL, "invariant") ;

  }

  void wait_reenter_begin(ObjectMonitor *mon) {

    JavaThread *jt = (JavaThread *)this->_thread;

    _active = JavaThreadBlockedOnMonitorEnterState::wait_reenter_begin(jt, mon);

  }

  void wait_reenter_end(ObjectMonitor *mon) {

    JavaThread *jt = (JavaThread *)this->_thread;

    JavaThreadBlockedOnMonitorEnterState::wait_reenter_end(jt, _active);

  }

};

enum ManifestConstants {

    ClearResponsibleAtSTW   = 0,

    MaximumRecheckInterval  = 1000

} ;

#undef TEVENT

#define TEVENT(nom) {if (SyncVerbose) FEVENT(nom); }

#define FEVENT(nom) { static volatile int ctr = 0 ; int v = ++ctr ; if ((v & (v-1)) == 0) { ::printf (#nom " : %d \n", v); ::fflush(stdout); }}

#undef  TEVENT

#define TEVENT(nom) {;}

// Performance concern:

// OrderAccess::storestore() calls release() which STs 0 into the global volatile

// OrderAccess::Dummy variable.  This store is unnecessary for correctness.

// Many threads STing into a common location causes considerable cache migration

// or "sloshing" on large SMP system.  As such, I avoid using OrderAccess::storestore()

// until it's repaired.  In some cases OrderAccess::fence() -- which incurs local

// latency on the executing processor -- is a better choice as it scales on SMP

// systems.  See http://blogs.sun.com/dave/entry/biased_locking_in_hotspot for a

// discussion of coherency costs.  Note that all our current reference platforms

// provide strong ST-ST order, so the issue is moot on IA32, x64, and SPARC.

//

// As a general policy we use "volatile" to control compiler-based reordering

// and explicit fences (barriers) to control for architectural reordering performed

// by the CPU(s) or platform.

static int  MBFence (int x) { OrderAccess::fence(); return x; }

struct SharedGlobals {

    // These are highly shared mostly-read variables.

    // To avoid false-sharing they need to be the sole occupants of a $ line.

    double padPrefix [8];

    volatile int stwRandom ;

    volatile int stwCycle ;

    // Hot RW variables -- Sequester to avoid false-sharing

    double padSuffix [16];

    volatile int hcSequence ;

    double padFinal [8] ;

} ;

static SharedGlobals GVars ;

static int MonitorScavengeThreshold = 1000000 ;

static volatile int ForceMonitorScavenge = 0 ; // Scavenge required and pending

// Tunables ...

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

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

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

static int Knob_HandOff            = 0 ;

static int Knob_Verbose            = 0 ;

static int Knob_ReportSettings     = 0 ;

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

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 ;

// hashCode() generation :

//

// Possibilities:

// * MD5Digest of {obj,stwRandom}

// * CRC32 of {obj,stwRandom} or any linear-feedback shift register function.

// * A DES- or AES-style SBox[] mechanism

// * One of the Phi-based schemes, such as:

//   2654435761 = 2^32 * Phi (golden ratio)

//   HashCodeValue = ((uintptr_t(obj) >> 3) * 2654435761) ^ GVars.stwRandom ;

// * A variation of Marsaglia's shift-xor RNG scheme.

// * (obj ^ stwRandom) is appealing, but can result

//   in undesirable regularity in the hashCode values of adjacent objects

//   (objects allocated back-to-back, in particular).  This could potentially

//   result in hashtable collisions and reduced hashtable efficiency.

//   There are simple ways to "diffuse" the middle address bits over the

//   generated hashCode values:

//

static inline intptr_t get_next_hash(Thread * Self, oop obj) {

  intptr_t value = 0 ;

  if (hashCode == 0) {

     // This form uses an unguarded global Park-Miller RNG,

     // so it's possible for two threads to race and generate the same RNG.

     // On MP system we'll have lots of RW access to a global, so the

     // mechanism induces lots of coherency traffic.

     value = os::random() ;

  } else

  if (hashCode == 1) {

     // This variation has the property of being stable (idempotent)

     // between STW operations.  This can be useful in some of the 1-0

     // synchronization schemes.

     intptr_t addrBits = intptr_t(obj) >> 3 ;

     value = addrBits ^ (addrBits >> 5) ^ GVars.stwRandom ;

  } else

  if (hashCode == 2) {

     value = 1 ;            // for sensitivity testing

  } else

  if (hashCode == 3) {

     value = ++GVars.hcSequence ;

  } else

  if (hashCode == 4) {

     value = intptr_t(obj) ;

  } else {

     // Marsaglia's xor-shift scheme with thread-specific state

     // This is probably the best overall implementation -- we'll

     // likely make this the default in future releases.

     unsigned t = Self->_hashStateX ;

     t ^= (t << 11) ;

     Self->_hashStateX = Self->_hashStateY ;

     Self->_hashStateY = Self->_hashStateZ ;

     Self->_hashStateZ = Self->_hashStateW ;

     unsigned v = Self->_hashStateW ;

     v = (v ^ (v >> 19)) ^ (t ^ (t >> 8)) ;

     Self->_hashStateW = v ;

     value = v ;

  }

  value &= markOopDesc::hash_mask;

  if (value == 0) value = 0xBAD ;

  assert (value != markOopDesc::no_hash, "invariant") ;

  TEVENT (hashCode: GENERATE) ;

  return value;

}

void BasicLock::print_on(outputStream* st) const {

  st->print("monitor");

}

void BasicLock::move_to(oop obj, BasicLock* dest) {

  // Check to see if we need to inflate the lock. This is only needed

  // if an object is locked using "this" lightweight monitor. In that

  // case, the displaced_header() is unlocked, because the

  // displaced_header() contains the header for the originally unlocked

  // object. However the object could have already been inflated. But it

  // does not matter, the inflation will just a no-op. For other cases,

  // the displaced header will be either 0x0 or 0x3, which are location

  // independent, therefore the BasicLock is free to move.

  //

  // During OSR we may need to relocate a BasicLock (which contains a

  // displaced word) from a location in an interpreter frame to a

  // new location in a compiled frame.  "this" refers to the source

  // basiclock in the interpreter frame.  "dest" refers to the destination

  // basiclock in the new compiled frame.  We *always* inflate in move_to().

  // The always-Inflate policy works properly, but in 1.5.0 it can sometimes

  // cause performance problems in code that makes heavy use of a small # of

  // uncontended locks.   (We'd inflate during OSR, and then sync performance

  // would subsequently plummet because the thread would be forced thru the slow-path).

  // This problem has been made largely moot on IA32 by inlining the inflated fast-path

  // operations in Fast_Lock and Fast_Unlock in i486.ad.

  //

  // Note that there is a way to safely swing the object's markword from

  // one stack location to another.  This avoids inflation.  Obviously,

  // we need to ensure that both locations refer to the current thread's stack.

  // There are some subtle concurrency issues, however, and since the benefit is

  // is small (given the support for inflated fast-path locking in the fast_lock, etc)

  // we'll leave that optimization for another time.

  if (displaced_header()->is_neutral()) {

    ObjectSynchronizer::inflate_helper(obj);

    // WARNING: We can not put check here, because the inflation

    // will not update the displaced header. Once BasicLock is inflated,

    // no one should ever look at its content.

  } else {

    // Typically the displaced header will be 0 (recursive stack lock) or

    // unused_mark.  Naively we'd like to assert that the displaced mark

    // value is either 0, neutral, or 3.  But with the advent of the

    // store-before-CAS avoidance in fast_lock/compiler_lock_object

    // we can find any flavor mark in the displaced mark.

  }

// [RGV] The next line appears to do nothing!

  intptr_t dh = (intptr_t) displaced_header();

  dest->set_displaced_header(displaced_header());

}

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

// standard constructor, allows locking failures

ObjectLocker::ObjectLocker(Handle obj, Thread* thread, bool doLock) {

  _dolock = doLock;

  _thread = thread;

  debug_only(if (StrictSafepointChecks) _thread->check_for_valid_safepoint_state(false);)

  _obj = obj;

  if (_dolock) {

    TEVENT (ObjectLocker) ;

    ObjectSynchronizer::fast_enter(_obj, &_lock, false, _thread);

  }

}

ObjectLocker::~ObjectLocker() {

  if (_dolock) {

    ObjectSynchronizer::fast_exit(_obj(), &_lock, _thread);

  }

}

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

PerfCounter * ObjectSynchronizer::_sync_Inflations                  = NULL ;

PerfCounter * ObjectSynchronizer::_sync_Deflations                  = NULL ;

PerfCounter * ObjectSynchronizer::_sync_ContendedLockAttempts       = NULL ;

PerfCounter * ObjectSynchronizer::_sync_FutileWakeups               = NULL ;

PerfCounter * ObjectSynchronizer::_sync_Parks                       = NULL ;

PerfCounter * ObjectSynchronizer::_sync_EmptyNotifications          = NULL ;

PerfCounter * ObjectSynchronizer::_sync_Notifications               = NULL ;

PerfCounter * ObjectSynchronizer::_sync_PrivateA                    = NULL ;

PerfCounter * ObjectSynchronizer::_sync_PrivateB                    = NULL ;

PerfCounter * ObjectSynchronizer::_sync_SlowExit                    = NULL ;

PerfCounter * ObjectSynchronizer::_sync_SlowEnter                   = NULL ;

PerfCounter * ObjectSynchronizer::_sync_SlowNotify                  = NULL ;

PerfCounter * ObjectSynchronizer::_sync_SlowNotifyAll               = NULL ;

PerfCounter * ObjectSynchronizer::_sync_FailedSpins                 = NULL ;

PerfCounter * ObjectSynchronizer::_sync_SuccessfulSpins             = NULL ;

PerfCounter * ObjectSynchronizer::_sync_MonInCirculation            = NULL ;

PerfCounter * ObjectSynchronizer::_sync_MonScavenged                = NULL ;

PerfLongVariable * ObjectSynchronizer::_sync_MonExtant              = NULL ;

// One-shot global initialization for the sync subsystem.

// We could also defer initialization and initialize on-demand

// the first time we call inflate().  Initialization would

// be protected - like so many things - by the MonitorCache_lock.

void ObjectSynchronizer::Initialize () {

  static int InitializationCompleted = 0 ;

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

  InitializationCompleted = 1 ;

  if (UsePerfData) {

      EXCEPTION_MARK ;

      #define NEWPERFCOUNTER(n)   {n = PerfDataManager::create_counter(SUN_RT, #n, PerfData::U_Events,CHECK); }

      #define NEWPERFVARIABLE(n)  {n = PerfDataManager::create_variable(SUN_RT, #n, PerfData::U_Events,CHECK); }

      NEWPERFCOUNTER(_sync_Inflations) ;

      NEWPERFCOUNTER(_sync_Deflations) ;

      NEWPERFCOUNTER(_sync_ContendedLockAttempts) ;

      NEWPERFCOUNTER(_sync_FutileWakeups) ;

      NEWPERFCOUNTER(_sync_Parks) ;

      NEWPERFCOUNTER(_sync_EmptyNotifications) ;

      NEWPERFCOUNTER(_sync_Notifications) ;

      NEWPERFCOUNTER(_sync_SlowEnter) ;

      NEWPERFCOUNTER(_sync_SlowExit) ;

      NEWPERFCOUNTER(_sync_SlowNotify) ;

      NEWPERFCOUNTER(_sync_SlowNotifyAll) ;

      NEWPERFCOUNTER(_sync_FailedSpins) ;

      NEWPERFCOUNTER(_sync_SuccessfulSpins) ;

      NEWPERFCOUNTER(_sync_PrivateA) ;

      NEWPERFCOUNTER(_sync_PrivateB) ;

      NEWPERFCOUNTER(_sync_MonInCirculation) ;

      NEWPERFCOUNTER(_sync_MonScavenged) ;

      NEWPERFVARIABLE(_sync_MonExtant) ;

      #undef NEWPERFCOUNTER

  }

}

// Compile-time asserts

// When possible, it's better to catch errors deterministically at

// compile-time than at runtime.  The down-side to using compile-time

// asserts is that error message -- often something about negative array

// indices -- is opaque.

#define CTASSERT(x) { int tag[1-(2*!(x))]; printf ("Tag @" INTPTR_FORMAT "\n", (intptr_t)tag); }

void ObjectMonitor::ctAsserts() {

  CTASSERT(offset_of (ObjectMonitor, _header) == 0);

}

static int Adjust (volatile int * adr, int dx) {

  int v ;

  for (v = *adr ; Atomic::cmpxchg (v + dx, adr, v) != v; v = *adr) ;

  return v ;

}

// Ad-hoc mutual exclusion primitives: SpinLock and Mux

//

// We employ SpinLocks _only for low-contention, fixed-length

// short-duration critical sections where we're concerned

// about native mutex_t or HotSpot Mutex:: latency.

// The mux construct provides a spin-then-block mutual exclusion

// mechanism.

//

// Testing has shown that contention on the ListLock guarding gFreeList

// is common.  If we implement ListLock as a simple SpinLock it's common

// for the JVM to devolve to yielding with little progress.  This is true

// despite the fact that the critical sections protected by ListLock are

// extremely short.

//

// TODO-FIXME: ListLock should be of type SpinLock.

// We should make this a 1st-class type, integrated into the lock

// hierarchy as leaf-locks.  Critically, the SpinLock structure

// should have sufficient padding to avoid false-sharing and excessive

// cache-coherency traffic.

typedef volatile int SpinLockT ;

void Thread::SpinAcquire (volatile int * adr, const char * LockName) {

  if (Atomic::cmpxchg (1, adr, 0) == 0) {

     return ;   // normal fast-path return

  }

  // Slow-path : We've encountered contention -- Spin/Yield/Block strategy.

  TEVENT (SpinAcquire - ctx) ;

  int ctr = 0 ;

  int Yields = 0 ;

  for (;;) {

     while (*adr != 0) {

        ++ctr ;

        if ((ctr & 0xFFF) == 0 || !os::is_MP()) {

           if (Yields > 5) {

             // Consider using a simple NakedSleep() instead.

             // Then SpinAcquire could be called by non-JVM threads

             Thread::current()->_ParkEvent->park(1) ;

           } else {

             os::NakedYield() ;

             ++Yields ;

           }

        } else {

           SpinPause() ;

        }

     }

     if (Atomic::cmpxchg (1, adr, 0) == 0) return ;

  }

}

void Thread::SpinRelease (volatile int * adr) {

  assert (*adr != 0, "invariant") ;

  OrderAccess::fence() ;      // guarantee at least release consistency.

  // Roach-motel semantics.

  // It's safe if subsequent LDs and STs float "up" into the critical section,

  // but prior LDs and STs within the critical section can't be allowed

  // to reorder or float past the ST that releases the lock.

  *adr = 0 ;

}

// muxAcquire and muxRelease:

//

// *  muxAcquire and muxRelease support a single-word lock-word construct.

//    The LSB of the word is set IFF the lock is held.

//    The remainder of the word points to the head of a singly-linked list

//    of threads blocked on the lock.

//

// *  The current implementation of muxAcquire-muxRelease uses its own

//    dedicated Thread._MuxEvent instance.  If we're interested in

//    minimizing the peak number of extant ParkEvent instances then

//    we could eliminate _MuxEvent and "borrow" _ParkEvent as long

//    as certain invariants were satisfied.  Specifically, care would need

//    to be taken with regards to consuming unpark() "permits".

//    A safe rule of thumb is that a thread would never call muxAcquire()

//    if it's enqueued (cxq, EntryList, WaitList, etc) and will subsequently

//    park().  Otherwise the _ParkEvent park() operation in muxAcquire() could

//    consume an unpark() permit intended for monitorenter, for instance.

//    One way around this would be to widen the restricted-range semaphore

//    implemented in park().  Another alternative would be to provide

//    multiple instances of the PlatformEvent() for each thread.  One

//    instance would be dedicated to muxAcquire-muxRelease, for instance.

//

// *  Usage:

//    -- Only as leaf locks

//    -- for short-term locking only as muxAcquire does not perform