natobject.cc

gcc的组建

  struct heavy_lock *next;	// Hash chain link.
				// Traced by GC.
  void * old_client_data;	// The only other field traced by GC.
  GC_finalization_proc old_finalization_proc;
  obj_addr_t address;		// Object to which this lock corresponds.
				// Should not be traced by GC.
  				// Cleared as heavy_lock is destroyed.
  				// Together with the rest of the heavy lock
  				// chain, this is protected by the lock
  				// bit in the hash table entry to which
  				// the chain is attached.
  _Jv_SyncInfo si;
  // The remaining fields save prior finalization info for
  // the object, which we needed to replace in order to arrange
  // for cleanup of the lock structure.
};

#ifdef LOCK_DEBUG
void
print_hl_list(heavy_lock *hl)
{
    heavy_lock *p = hl;
    for (; 0 != p; p = p->next)
      fprintf (stderr, "(hl = %p, addr = %p)", p, (void *)(p -> address));
}
#endif /* LOCK_DEBUG */

#if defined (_Jv_HaveCondDestroy) || defined (_Jv_HaveMutexDestroy)
// If we have to run a destructor for a sync_info member, then this
// function could be registered as a finalizer for the sync_info.
// In fact, we now only invoke it explicitly.
static inline void
heavy_lock_finalization_proc (heavy_lock *hl)
{
#if defined (_Jv_HaveCondDestroy)
  _Jv_CondDestroy (&hl->si.condition);
#endif
#if defined (_Jv_HaveMutexDestroy)
  _Jv_MutexDestroy (&hl->si.mutex);
#endif
  hl->si.init = false;
}
#endif /* defined (_Jv_HaveCondDestroy) || defined (_Jv_HaveMutexDestroy) */

// We convert the lock back to lightweight status when
// we exit, so that a single contention episode doesn't doom the lock
// forever.  But we also need to make sure that lock structures for dead
// objects are eventually reclaimed.  We do that in a an additional
// finalizer on the underlying object.
// Note that if the corresponding object is dead, it is safe to drop
// the heavy_lock structure from its list.  It is not necessarily
// safe to deallocate it, since the unlock code could still be running.

struct hash_entry {
  volatile obj_addr_t address;	// Address of object for which lightweight
  				// k is held.
				// We assume the 3 low order bits are zero.
				// With the Boehm collector and bitmap
				// allocation, objects of size 4 bytes are
				// broken anyway.  Thus this is primarily
				// a constraint on statically allocated
				// objects used for synchronization.
				// This allows us to use the low order
  				// bits as follows:
#   define LOCKED 	1 	// This hash entry is locked, and its
  				// state may be invalid.
  				// The lock protects both the hash_entry
  				// itself (except for the light_count
  				// and light_thr_id fields, which
  				// are protected by the lightweight
  				// lock itself), and any heavy_monitor
  				// structures attached to it.
#   define HEAVY	2	// Heavyweight locks associated with this
  				// hash entry may be held.
				// The lightweight entry is still valid,
  				// if the leading bits of the address
  				// field are nonzero.
  				// If the LOCKED bit is clear, then this is
 				// set exactly when heavy_count is > 0 .
  				// Stored redundantly so a single
  				// compare-and-swap works in the easy case.
  				// If HEAVY is not set, it is safe to use
  				// an available lightweight lock entry
  				// without checking if there is an existing
  				// heavyweight lock for the same object.
  				// (There may be one, but it won't be held
  				// or waited for.)
#   define REQUEST_CONVERSION 4 // The lightweight lock is held.  But
  				// one or more other threads have tried
  				// to acquire the lock, and hence request
  				// conversion to heavyweight status.
  				// The heavyweight lock is already allocated.
  				// Threads requesting conversion are
  				// waiting on the condition variable associated
  				// with the heavyweight lock.
  				// Not used for conversion due to
  				// Object.wait() calls.
#   define FLAGS (LOCKED | HEAVY | REQUEST_CONVERSION)
  volatile _Jv_ThreadId_t light_thr_id;
				// Thr_id of holder of lightweight lock.
  				// Only updated by lightweight lock holder.
				// Must be recognizably invalid if the
				// lightweight lock is not held.
#   define INVALID_THREAD_ID 0  // Works for Linux?
				// If zero doesn't work, we have to
				// initialize lock table.
  volatile unsigned short light_count;
				// Number of times the lightweight lock
  				// is held minus one.  Zero if lightweight
  				// lock is not held.  Only updated by
  				// lightweight lock holder or, in one
  				// case, while holding the LOCKED bit in
  				// a state in which there can be no
  				// lightweight lock holder.
  unsigned short heavy_count; 	// Total number of times heavyweight locks
  				// associated with this hash entry are held
  				// or waiting to be acquired.
  				// Threads in wait() are included eventhough
  				// they have temporarily released the lock.
  				// Protected by LOCKED bit.
  				// Threads requesting conversion to heavyweight
  				// status are also included.
  struct heavy_lock * heavy_locks;
  				// Chain of heavy locks.  Protected
  				// by lockbit for he.  Locks may
  				// remain allocated here even if HEAVY
  				// is not set and heavy_count is 0.
  				// If a lightweight and heavyweight lock
  				// correspond to the same address, the
  				// lightweight lock is the right one.
};

#ifndef JV_SYNC_TABLE_SZ
# define JV_SYNC_TABLE_SZ 2048	// Must be power of 2.
#endif

hash_entry light_locks[JV_SYNC_TABLE_SZ];

#define JV_SYNC_HASH(p) (((long)p ^ ((long)p >> 10)) & (JV_SYNC_TABLE_SZ-1))

// Note that the light_locks table is scanned conservatively by the
// collector.  It is essential the the heavy_locks field is scanned.
// Currently the address field may or may not cause the associated object
// to be retained, depending on whether flag bits are set.
// This means that we can conceivable get an unexpected deadlock if
// 1) Object at address A is locked.
// 2) The client drops A without unlocking it.
// 3) Flag bits in the address entry are set, so the collector reclaims
//    the object at A.
// 4) A is reallocated, and an attempt is made to lock the result.
// This could be fixed by scanning light_locks in a more customized
// manner that ignores the flag bits.  But it can only happen with hand
// generated semi-illegal .class files, and then it doesn't present a
// security hole.

#ifdef LOCK_DEBUG
  void print_he(hash_entry *he)
  {
     fprintf(stderr, "lock hash entry = %p, index = %d, address = 0x%lx\n"
		     "\tlight_thr_id = 0x%lx, light_count = %d, "
		     "heavy_count = %d\n\theavy_locks:", he,
		     he - light_locks, (unsigned long)(he -> address),
		     (unsigned long)(he -> light_thr_id),
		     he -> light_count, he -> heavy_count);
     print_hl_list(he -> heavy_locks);
     fprintf(stderr, "\n");
  }
#endif /* LOCK_DEBUG */

#ifdef LOCK_LOG
  // Log locking operations.  For debugging only.
  // Logging is intended to be as unintrusive as possible.
  // Log calls are made after an operation completes, and hence
  // may not completely reflect actual synchronization ordering.
  // The choice of events to log is currently a bit haphazard.
  // The intent is that if we have to track down any other bugs
  // inthis code, we extend the logging as appropriate.
  typedef enum
  {
    ACQ_LIGHT, ACQ_LIGHT2, ACQ_HEAVY, ACQ_HEAVY2, PROMOTE, REL_LIGHT,
    REL_HEAVY, REQ_CONV, PROMOTE2, WAIT_START, WAIT_END, NOTIFY, NOTIFY_ALL
  } event_type;

  struct lock_history
  {
    event_type tp;
    obj_addr_t addr;  // Often includes flags.
    _Jv_ThreadId_t thr;
  };
     
  const int LOG_SIZE = 128;	// Power of 2.

  lock_history lock_log[LOG_SIZE];

  volatile obj_addr_t log_next = 0;
  			   // Next location in lock_log.
  			   // Really an int, but we need compare_and_swap.

  static void add_log_entry(event_type t, obj_addr_t a, _Jv_ThreadId_t th)
  {
    obj_addr_t my_entry;
    obj_addr_t next_entry;
    do
      {
	my_entry = log_next;
	next_entry = ((my_entry + 1) & (LOG_SIZE - 1));
      }
    while (!compare_and_swap(&log_next, my_entry, next_entry));
    lock_log[my_entry].tp = t;
    lock_log[my_entry].addr = a;
    lock_log[my_entry].thr = th;
  }

# define LOG(t, a, th) add_log_entry(t, a, th)
#else /* !LOCK_LOG */
# define LOG(t, a, th)
#endif

static bool mp = false; // Known multiprocesssor.

// Wait for roughly 2^n units, touching as little memory as possible.
static void
spin(unsigned n)
{
  const unsigned MP_SPINS = 10;
  const unsigned YIELDS = 4;
  const unsigned SPINS_PER_UNIT = 30;
  const unsigned MIN_SLEEP_USECS = 2001; // Shorter times spin under Linux.
  const unsigned MAX_SLEEP_USECS = 200000;
  static unsigned spin_limit = 0;
  static unsigned yield_limit = YIELDS;
  static bool spin_initialized = false;

  if (!spin_initialized)
    {
      mp = is_mp();
      if (mp)
	{
	  spin_limit = MP_SPINS;
	  yield_limit = MP_SPINS + YIELDS;
	}
      spin_initialized = true;
    }
  if (n < spin_limit)
    {
      unsigned i = SPINS_PER_UNIT << n;
      for (; i > 0; --i)
        __asm__ __volatile__("");
    }
  else if (n < yield_limit)
    {
      _Jv_ThreadYield();
    }
  else
    {
      unsigned duration = MIN_SLEEP_USECS << (n - yield_limit);
      if (n >= 15 + yield_limit || duration > MAX_SLEEP_USECS)
        duration = MAX_SLEEP_USECS;
      _Jv_platform_usleep(duration);
    }
}

// Wait for a hash entry to become unlocked.
static void
wait_unlocked (hash_entry *he)
{
  unsigned i = 0;
  while (he -> address & LOCKED)
    spin (i++);
}

// Return the heavy lock for addr if it was already allocated.
// The client passes in the appropriate hash_entry.
// We hold the lock for he.
static inline heavy_lock *
find_heavy (obj_addr_t addr, hash_entry *he)
{
  heavy_lock *hl = he -> heavy_locks;
  while (hl != 0 && hl -> address != addr) hl = hl -> next;
  return hl;
}

// Unlink the heavy lock for the given address from its hash table chain.
// Dies miserably and conspicuously if it's not there, since that should
// be impossible.
static inline void
unlink_heavy (obj_addr_t addr, hash_entry *he)
{
  heavy_lock **currentp = &(he -> heavy_locks);
  while ((*currentp) -> address != addr)
    currentp = &((*currentp) -> next);
  *currentp = (*currentp) -> next;
}

// Finalization procedure for objects that have associated heavy-weight
// locks.  This may replace the real finalization procedure.
static void
heavy_lock_obj_finalization_proc (void *obj, void *cd)
{
  heavy_lock *hl = (heavy_lock *)cd;

// This only addresses misalignment of statics, not heap objects.  It
// works only because registering statics for finalization is a noop,
// no matter what the least significant bits are.
#ifdef JV_LINKER_CANNOT_8BYTE_ALIGN_STATICS
  obj_addr_t addr = (obj_addr_t)obj & ~((obj_addr_t)0x7);
#else
  obj_addr_t addr = (obj_addr_t)obj;
#endif
  hash_entry *he = light_locks + JV_SYNC_HASH(addr);
  obj_addr_t he_address = (he -> address & ~LOCKED);

  // Acquire lock bit immediately.  It's possible that the hl was already
  // destroyed while we were waiting for the finalizer to run.  If it
  // was, the address field was set to zero.  The address filed access is
  // protected by the lock bit to ensure that we do this exactly once.
  // The lock bit also protects updates to the objects finalizer.
  while (!compare_and_swap(&(he -> address), he_address, he_address|LOCKED ))
    {
      // Hash table entry is currently locked.  We can't safely 
      // touch the list of heavy locks.  
      wait_unlocked(he);
      he_address = (he -> address & ~LOCKED);
    }
  if (0 == hl -> address)
    {
      // remove_all_heavy destroyed hl, and took care of the real finalizer.
      release_set(&(he -> address), he_address);
      return;
    }
  JvAssert(hl -> address == addr);
  GC_finalization_proc old_finalization_proc = hl -> old_finalization_proc;
  if (old_finalization_proc != 0)
    {
      // We still need to run a real finalizer.  In an idealized
      // world, in which people write thread-safe finalizers, that is
      // likely to require synchronization.  Thus we reregister
      // ourselves as the only finalizer, and simply run the real one.
      // Thus we don't clean up the lock yet, but we're likely to do so
      // on the next GC cycle.
      // It's OK if remove_all_heavy actually destroys the heavy lock,
      // since we've updated old_finalization_proc, and thus the user's
      // finalizer won't be rerun.
      void * old_client_data = hl -> old_client_data;
      hl -> old_finalization_proc = 0;
      hl -> old_client_data = 0;
#     ifdef HAVE_BOEHM_GC
        GC_REGISTER_FINALIZER_NO_ORDER(obj, heavy_lock_obj_finalization_proc, cd, 0, 0);
#     endif
      release_set(&(he -> address), he_address);
      old_finalization_proc(obj, old_client_data);
    }
  else
    {
      // The object is really dead, although it's conceivable that
      // some thread may still be in the process of releasing the
      // heavy lock.  Unlink it and, if necessary, register a finalizer
      // to destroy sync_info.
      unlink_heavy(addr, he);
      hl -> address = 0; 	// Don't destroy it again.
      release_set(&(he -> address), he_address);
#     if defined (_Jv_HaveCondDestroy) || defined (_Jv_HaveMutexDestroy)
        // Make sure lock is not held and then destroy condvar and mutex.
        _Jv_MutexLock(&(hl->si.mutex));
        _Jv_MutexUnlock(&(hl->si.mutex));