/*

 * 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/padded.hpp"

#include "memory/resourceArea.hpp"

#include "oops/markOop.hpp"

#include "oops/oop.inline.hpp"

#include "runtime/atomic.inline.hpp"

#include "runtime/biasedLocking.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/synchronizer.hpp"

#include "runtime/thread.inline.hpp"

#include "utilities/dtrace.hpp"

#include "utilities/events.hpp"

#include "utilities/preserveException.hpp"

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

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

  #define NOINLINE __attribute__((noinline))

#else

  #define NOINLINE

#endif

PRAGMA_FORMAT_MUTE_WARNINGS_FOR_GCC

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

//

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

#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,                                           \

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

    }                                                                      \

  }

#define HOTSPOT_MONITOR_PROBE_waited HOTSPOT_MONITOR_WAITED

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

  {                                                                        \

    if (DTraceMonitorProbes) {                                             \

      DTRACE_MONITOR_PROBE_COMMON(obj, thread);                            \

      HOTSPOT_MONITOR_PROBE_##probe(jtid, /* probe = waited */             \

                                    (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

// This exists only as a workaround of dtrace bug 6254741

int dtrace_waited_probe(ObjectMonitor* monitor, Handle obj, Thread* thr) {

  DTRACE_MONITOR_PROBE(waited, monitor, obj(), thr);

  return 0;

}

#define NINFLATIONLOCKS 256

static volatile intptr_t InflationLocks[NINFLATIONLOCKS];

// gBlockList is really PaddedEnd<ObjectMonitor> *, but we don't

// want to expose the PaddedEnd template more than necessary.

ObjectMonitor * ObjectSynchronizer::gBlockList = NULL;

ObjectMonitor * volatile ObjectSynchronizer::gFreeList  = NULL;

ObjectMonitor * volatile ObjectSynchronizer::gOmInUseList  = NULL;

int ObjectSynchronizer::gOmInUseCount = 0;

static volatile intptr_t ListLock = 0;      // protects global monitor free-list cache

static volatile int MonitorFreeCount  = 0;  // # on gFreeList

static volatile int MonitorPopulation = 0;  // # Extant -- in circulation

#define CHAINMARKER (cast_to_oop<intptr_t>(-1))

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

//  Fast Monitor Enter/Exit

// This the fast monitor enter. The interpreter and compiler use

// some assembly copies of this code. Make sure update those code

// if the following function is changed. The implementation is

// extremely sensitive to race condition. Be careful.

void ObjectSynchronizer::fast_enter(Handle obj, BasicLock* lock,

                                    bool attempt_rebias, TRAPS) {

  if (UseBiasedLocking) {

    if (!SafepointSynchronize::is_at_safepoint()) {

      BiasedLocking::Condition cond = BiasedLocking::revoke_and_rebias(obj, attempt_rebias, THREAD);

      if (cond == BiasedLocking::BIAS_REVOKED_AND_REBIASED) {

        return;

      }

    } else {

      assert(!attempt_rebias, "can not rebias toward VM thread");

      BiasedLocking::revoke_at_safepoint(obj);

    }

    assert(!obj->mark()->has_bias_pattern(), "biases should be revoked by now");

  }

  slow_enter(obj, lock, THREAD);

}

void ObjectSynchronizer::fast_exit(oop object, BasicLock* lock, TRAPS) {

  assert(!object->mark()->has_bias_pattern(), "should not see bias pattern here");

  // if displaced header is null, the previous enter is recursive enter, no-op

  markOop dhw = lock->displaced_header();

  markOop mark;

  if (dhw == NULL) {

    // Recursive stack-lock.

    // Diagnostics -- Could be: stack-locked, inflating, inflated.

    mark = object->mark();

    assert(!mark->is_neutral(), "invariant");

    if (mark->has_locker() && mark != markOopDesc::INFLATING()) {

      assert(THREAD->is_lock_owned((address)mark->locker()), "invariant");

    }

    if (mark->has_monitor()) {

      ObjectMonitor * m = mark->monitor();

      assert(((oop)(m->object()))->mark() == mark, "invariant");

      assert(m->is_entered(THREAD), "invariant");

    }

    return;

  }

  mark = object->mark();

  // If the object is stack-locked by the current thread, try to

  // swing the displaced header from the box back to the mark.

  if (mark == (markOop) lock) {

    assert(dhw->is_neutral(), "invariant");

    if ((markOop) Atomic::cmpxchg_ptr (dhw, object->mark_addr(), mark) == mark) {

      TEVENT(fast_exit: release stacklock);

      return;

    }

  }

  ObjectSynchronizer::inflate(THREAD, object)->exit(true, THREAD);

}

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

// Interpreter/Compiler Slow Case

// This routine is used to handle interpreter/compiler slow case

// We don't need to use fast path here, because it must have been

// failed in the interpreter/compiler code.

void ObjectSynchronizer::slow_enter(Handle obj, BasicLock* lock, TRAPS) {

  markOop mark = obj->mark();

  assert(!mark->has_bias_pattern(), "should not see bias pattern here");

  if (mark->is_neutral()) {

    // Anticipate successful CAS -- the ST of the displaced mark must

    // be visible <= the ST performed by the CAS.

    lock->set_displaced_header(mark);

    if (mark == (markOop) Atomic::cmpxchg_ptr(lock, obj()->mark_addr(), mark)) {

      TEVENT(slow_enter: release stacklock);

      return;

    }

    // Fall through to inflate() ...

  } else if (mark->has_locker() &&

             THREAD->is_lock_owned((address)mark->locker())) {

    assert(lock != mark->locker(), "must not re-lock the same lock");

    assert(lock != (BasicLock*)obj->mark(), "don't relock with same BasicLock");

    lock->set_displaced_header(NULL);

    return;

  }

  // The object header will never be displaced to this lock,

  // so it does not matter what the value is, except that it

  // must be non-zero to avoid looking like a re-entrant lock,

  // and must not look locked either.

  lock->set_displaced_header(markOopDesc::unused_mark());

  ObjectSynchronizer::inflate(THREAD, obj())->enter(THREAD);

}

// This routine is used to handle interpreter/compiler slow case

// We don't need to use fast path here, because it must have

// failed in the interpreter/compiler code. Simply use the heavy

// weight monitor should be ok, unless someone find otherwise.

void ObjectSynchronizer::slow_exit(oop object, BasicLock* lock, TRAPS) {

  fast_exit(object, lock, THREAD);

}

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

// Class Loader  support to workaround deadlocks on the class loader lock objects

// Also used by GC

// complete_exit()/reenter() are used to wait on a nested lock

// i.e. to give up an outer lock completely and then re-enter

// Used when holding nested locks - lock acquisition order: lock1 then lock2

//  1) complete_exit lock1 - saving recursion count

//  2) wait on lock2

//  3) when notified on lock2, unlock lock2

//  4) reenter lock1 with original recursion count

//  5) lock lock2

// NOTE: must use heavy weight monitor to handle complete_exit/reenter()

intptr_t ObjectSynchronizer::complete_exit(Handle obj, TRAPS) {

  TEVENT(complete_exit);

  if (UseBiasedLocking) {

    BiasedLocking::revoke_and_rebias(obj, false, THREAD);

    assert(!obj->mark()->has_bias_pattern(), "biases should be revoked by now");

  }

  ObjectMonitor* monitor = ObjectSynchronizer::inflate(THREAD, obj());

  return monitor->complete_exit(THREAD);

}

// NOTE: must use heavy weight monitor to handle complete_exit/reenter()

void ObjectSynchronizer::reenter(Handle obj, intptr_t recursion, TRAPS) {

  TEVENT(reenter);

  if (UseBiasedLocking) {

    BiasedLocking::revoke_and_rebias(obj, false, THREAD);

    assert(!obj->mark()->has_bias_pattern(), "biases should be revoked by now");

  }

  ObjectMonitor* monitor = ObjectSynchronizer::inflate(THREAD, obj());

  monitor->reenter(recursion, THREAD);

}

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

// JNI locks on java objects

// NOTE: must use heavy weight monitor to handle jni monitor enter

void ObjectSynchronizer::jni_enter(Handle obj, TRAPS) {

  // the current locking is from JNI instead of Java code

  TEVENT(jni_enter);

  if (UseBiasedLocking) {

    BiasedLocking::revoke_and_rebias(obj, false, THREAD);

    assert(!obj->mark()->has_bias_pattern(), "biases should be revoked by now");

  }

  THREAD->set_current_pending_monitor_is_from_java(false);

  ObjectSynchronizer::inflate(THREAD, obj())->enter(THREAD);

  THREAD->set_current_pending_monitor_is_from_java(true);

}

// NOTE: must use heavy weight monitor to handle jni monitor exit

void ObjectSynchronizer::jni_exit(oop obj, Thread* THREAD) {

  TEVENT(jni_exit);

  if (UseBiasedLocking) {

    Handle h_obj(THREAD, obj);

    BiasedLocking::revoke_and_rebias(h_obj, false, THREAD);

    obj = h_obj();

  }

  assert(!obj->mark()->has_bias_pattern(), "biases should be revoked by now");

  ObjectMonitor* monitor = ObjectSynchronizer::inflate(THREAD, obj);

  // If this thread has locked the object, exit the monitor.  Note:  can't use

  // monitor->check(CHECK); must exit even if an exception is pending.

  if (monitor->check(THREAD)) {

    monitor->exit(true, THREAD);

  }

}

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

// Internal VM locks on java objects

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

  }

}

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

//  Wait/Notify/NotifyAll

// NOTE: must use heavy weight monitor to handle wait()

int ObjectSynchronizer::wait(Handle obj, jlong millis, TRAPS) {

  if (UseBiasedLocking) {

    BiasedLocking::revoke_and_rebias(obj, false, THREAD);

    assert(!obj->mark()->has_bias_pattern(), "biases should be revoked by now");

  }

  if (millis < 0) {

    TEVENT(wait - throw IAX);

    THROW_MSG_0(vmSymbols::java_lang_IllegalArgumentException(), "timeout value is negative");

  }

  ObjectMonitor* monitor = ObjectSynchronizer::inflate(THREAD, obj());

  DTRACE_MONITOR_WAIT_PROBE(monitor, obj(), THREAD, millis);

  monitor->wait(millis, true, THREAD);

  // This dummy call is in place to get around dtrace bug 6254741.  Once

  // that's fixed we can uncomment the following line, remove the call

  // and change this function back into a "void" func.

  // DTRACE_MONITOR_PROBE(waited, monitor, obj(), THREAD);

  return dtrace_waited_probe(monitor, obj, THREAD);

}

void ObjectSynchronizer::waitUninterruptibly(Handle obj, jlong millis, TRAPS) {

  if (UseBiasedLocking) {

    BiasedLocking::revoke_and_rebias(obj, false, THREAD);

    assert(!obj->mark()->has_bias_pattern(), "biases should be revoked by now");

  }

  if (millis < 0) {

    TEVENT(wait - throw IAX);

    THROW_MSG(vmSymbols::java_lang_IllegalArgumentException(), "timeout value is negative");

  }

  ObjectSynchronizer::inflate(THREAD, obj()) -> wait(millis, false, THREAD);

}

void ObjectSynchronizer::notify(Handle obj, TRAPS) {

  if (UseBiasedLocking) {

    BiasedLocking::revoke_and_rebias(obj, false, THREAD);

    assert(!obj->mark()->has_bias_pattern(), "biases should be revoked by now");

  }

  markOop mark = obj->mark();

  if (mark->has_locker() && THREAD->is_lock_owned((address)mark->locker())) {

    return;

  }

  ObjectSynchronizer::inflate(THREAD, obj())->notify(THREAD);

}

// NOTE: see comment of notify()

void ObjectSynchronizer::notifyall(Handle obj, TRAPS) {

  if (UseBiasedLocking) {

    BiasedLocking::revoke_and_rebias(obj, false, THREAD);

    assert(!obj->mark()->has_bias_pattern(), "biases should be revoked by now");

  }

  markOop mark = obj->mark();

  if (mark->has_locker() && THREAD->is_lock_owned((address)mark->locker())) {

    return;

  }

  ObjectSynchronizer::inflate(THREAD, obj())->notifyAll(THREAD);

}

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

// Hash Code handling

//

// Performance concern:

// OrderAccess::storestore() calls release() which at one time stored 0

// into the global volatile OrderAccess::dummy variable. This store was

// unnecessary for correctness. Many threads storing into a common location

// causes considerable cache migration or "sloshing" on large SMP systems.

// As such, I avoided using OrderAccess::storestore(). 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.oracle.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.

struct SharedGlobals {

  char         _pad_prefix[DEFAULT_CACHE_LINE_SIZE];

  // These are highly shared mostly-read variables.

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

  volatile int stwRandom;

  volatile int stwCycle;

  DEFINE_PAD_MINUS_SIZE(1, DEFAULT_CACHE_LINE_SIZE, sizeof(volatile int) * 2);

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

  volatile int hcSequence;

  DEFINE_PAD_MINUS_SIZE(2, DEFAULT_CACHE_LINE_SIZE, sizeof(volatile int));

};

static SharedGlobals GVars;

static int MonitorScavengeThreshold = 1000000;

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

static markOop ReadStableMark(oop obj) {

  markOop mark = obj->mark();

  if (!mark->is_being_inflated()) {

    return mark;       // normal fast-path return

  }

  int its = 0;

  for (;;) {

    markOop mark = obj->mark();

    if (!mark->is_being_inflated()) {

      return mark;    // normal fast-path return

    }

    // The object is being inflated by some other thread.

    // The caller of ReadStableMark() must wait for inflation to complete.

    // Avoid live-lock

    // TODO: consider calling SafepointSynchronize::do_call_back() while

    // spinning to see if there's a safepoint pending.  If so, immediately

    // yielding or blocking would be appropriate.  Avoid spinning while

    // there is a safepoint pending.

    // TODO: add inflation contention performance counters.

    // TODO: restrict the aggregate number of spinners.

    ++its;

    if (its > 10000 || !os::is_MP()) {

      if (its & 1) {

        os::naked_yield();

        TEVENT(Inflate: INFLATING - yield);

      } else {

        // Note that the following code attenuates the livelock problem but is not

        // a complete remedy.  A more complete solution would require that the inflating

        // thread hold the associated inflation lock.  The following code simply restricts

        // the number of spinners to at most one.  We'll have N-2 threads blocked

        // on the inflationlock, 1 thread holding the inflation lock and using

        // a yield/park strategy, and 1 thread in the midst of inflation.

        // A more refined approach would be to change the encoding of INFLATING

        // to allow encapsulation of a native thread pointer.  Threads waiting for

        // inflation to complete would use CAS to push themselves onto a singly linked

        // list rooted at the markword.  Once enqueued, they'd loop, checking a per-thread flag

        // and calling park().  When inflation was complete the thread that accomplished inflation

        // would detach the list and set the markword to inflated with a single CAS and

        // then for each thread on the list, set the flag and unpark() the thread.

        // This is conceptually similar to muxAcquire-muxRelease, except that muxRelease

        // wakes at most one thread whereas we need to wake the entire list.

        int ix = (cast_from_oop<intptr_t>(obj) >> 5) & (NINFLATIONLOCKS-1);

        int YieldThenBlock = 0;

        assert(ix >= 0 && ix < NINFLATIONLOCKS, "invariant");

        assert((NINFLATIONLOCKS & (NINFLATIONLOCKS-1)) == 0, "invariant");

        Thread::muxAcquire(InflationLocks + ix, "InflationLock");

        while (obj->mark() == markOopDesc::INFLATING()) {

          // Beware: NakedYield() is advisory and has almost no effect on some platforms

          // so we periodically call Self->_ParkEvent->park(1).

          // We use a mixed spin/yield/block mechanism.

          if ((YieldThenBlock++) >= 16) {

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

          } else {

            os::naked_yield();

          }

        }

        Thread::muxRelease(InflationLocks + ix);

        TEVENT(Inflate: INFLATING - yield/park);

      }

    } else {

      SpinPause();       // SMP-polite spinning

    }

  }

}

// hashCode() generation :

//

// Possibilities:

// * MD5Digest of {obj,stwRandom}