[Valgrind-developers] Overlap between valgrind and libcwd

[Carlo W. <ca...@al...>]

Hiya fellow hackers,

I am the author of libcwd - which exists a lot longer than valgrind! heheh.

I recently started to use valgrind and I find a few overlapping
functionalities (sadly) that probably should be turned into
a new library and then being used by both from one source...

- Reading and analysing ELF symbol tables
- Lookup of source file line number locations and function names
- Demangling of new ABI mangled function names (gcc-3.x)

Also, although not for use by the users of libcwd, I wrote
code to test potential deadlocks in POSIX threaded applications
(in fact, to test libcwd itself for potential deadlocks).

The latter might be a nice (new?) skin, or be added to helgrind.

---------------------------------------------------------------------------
Let me see what I did...

Aha, basically I call a function 'test_for_deadlock' with some
parameters, every time a lock is set.  The parameters specify
among others a unique id of the lock.  'test_for_deadlock'
then does the following (just scan quickly over it):

void test_for_deadlock(int instance, struct TSD_st& __libcwd_tsd, void const* from)
{
  if (!WST_multi_threaded)
    return;                     // Give libcwd the time to get initialized.

  if (instance == keypair_map_instance)
    return;

  set_alloc_checking_off(__libcwd_tsd);

  // Initialization.
  if (!keypair_map)
    keypair_map = new keypair_map_t;

  // We don't use a lock here because we can't.  I hope that in fact this is
  // not a problem because threadlist is a list<> and new elements will be added
  // to the end.  None of the new items will be of interest to us.  It is possible
  // that an item is *removed* from the list (see thread_ct::tsd_destroyed above)
  // but that is very unlikely in the cases where this test is actually being
  // used (we don't test with more than 1024 threads).
  for (threadlist_t::iterator iter = threadlist->begin(); iter != threadlist->end(); ++iter)
  {
    mutex_ct const* mutex = &((*iter).thread_mutex);
    if (mutex->M_locked_by == __libcwd_tsd.tid && mutex->M_instance_locked >= 1)
      test_lock_pair(reinterpret_cast<int>(mutex), mutex->M_locked_from, instance, from);
  }
  for (int inst = 0; inst < instance_locked_size; ++inst)
  {
    // Check for read locks that are already set.  Because it was never stored wether or not
    // it was a high priority lock, this information is lost.  This is not a problem though
    // because we treat high priority and normal read locks the same when they are set first.
    if (inst < instance_rdlocked_size && __libcwd_tsd.rdlocked_by1[inst] == __libcwd_tsd.tid && __libcwd_tsd.instance_rdlocked[inst] >= 1)
      test_lock_pair(inst + read_lock_offset, __libcwd_tsd.rdlocked_from1[inst], instance, from);
    if (inst < instance_rdlocked_size && __libcwd_tsd.rdlocked_by2[inst] == __libcwd_tsd.tid && __libcwd_tsd.instance_rdlocked[inst] >= 2)
      test_lock_pair(inst + read_lock_offset, __libcwd_tsd.rdlocked_from2[inst], instance, from);
    // Check for write locks and normal mutexes.
    if (locked_by[inst] == __libcwd_tsd.tid && instance_locked[inst] >= 1 && inst != keypair_map_instance)
      test_lock_pair(inst, locked_from[inst], instance, from);
  }

  set_alloc_checking_on(__libcwd_tsd);
}

What this does is the following: It calls 'test_lock_pair' for every
combination of two lock ids (including the location at which they were locked)
where the first one is any lock that is locked at this moment, and the
second one is the new lock that is being set right now.

test_lock_pair does the following (just scan quickly over it):

// These are the different groups that are allowed together.
uint16_t const group1 = 0x002;	// Instance 1 locked first.
uint16_t const group2 = 0x004;	// Instance 2 locked first.
uint16_t const group3 = 0x020;	// Instance 1 read only and high_priority when second.
uint16_t const group4 = 0x040;	// Instance 2 read only and high_priority when second.
uint16_t const group5 = 0x200;	// (Instance 1 locked first and (either one read only and high_priority when second))
				// or (both read only and high_priority when second).
uint16_t const group6 = 0x400;	// (Instance 2 locked first and (either one read only and high_priority when second))
				// or (both read only and high_priority when second).

struct keypair_key_st {
  int instance1;
  int instance2;
};

struct keypair_info_st {
  uint16_t state;
  int limited;
  void const* from_first[5];
  void const* from_second[5];
};

struct keypair_compare_st {
  bool operator()(keypair_key_st const& a, keypair_key_st const& b) const;
};

// Definition of the map<> that holds the key instance pairs that are ever locked simultaneously by the same thread.
typedef std::pair<keypair_key_st const, keypair_info_st> keypair_map_value_t;
typedef std::map<keypair_key_st, keypair_info_st, keypair_compare_st> keypair_map_t;
static keypair_map_t* keypair_map;

// Bring some arbitrary ordering into the map with key pairs.
bool keypair_compare_st::operator()(keypair_key_st const& a, keypair_key_st const& b) const
{
  return (a.instance1 == b.instance1) ? (a.instance2 < b.instance2) : (a.instance1 < b.instance1);
}

extern "C" int raise(int);
void test_lock_pair(int instance_first, void const* from_first, int instance_second, void const* from_second)
{
  if (instance_first == instance_second)
    return;	// Must have been a recursive lock.

  keypair_key_st keypair_key;
  keypair_info_st keypair_info;

  // Do some decoding and get rid of the 'read_lock_offset' and 'high_priority_read_lock_offset' flags.
 
  // During the decoding, we assume that the first instance is the smallest (instance 1).
  keypair_info.state = group1;
  bool first_is_readonly = false;
  bool second_is_high_priority = false;
  if (instance_first < 0x10000)
  {
    if (instance_first >= read_lock_offset)
    {
      first_is_readonly = true;
      keypair_info.state |= (group3 | group5);
    }
    instance_first %= read_lock_offset;
  }
  if (instance_second < 0x10000)
  {
    if (instance_second >= high_priority_read_lock_offset)
    {
      second_is_high_priority = true;
      keypair_info.state |= (group4 | group5);
      if (first_is_readonly)
	keypair_info.state |= group6;
    }
    instance_second %= read_lock_offset;
  }

  // Put the smallest instance in instance1.
  if (instance_first < instance_second)
  {
    keypair_key.instance1 = instance_first;
    keypair_key.instance2 = instance_second;
  }
  else
  {
    keypair_key.instance1 = instance_second;
    keypair_key.instance2 = instance_first;
    // Correct the state by swapping groups 1 <-> 2, 3 <-> 4, and 5 <-> 6.
    keypair_info.state = ((keypair_info.state << 1) | (keypair_info.state >> 1)) & (group1|group2|group3|group4|group5|group6);
  }

  // Store the locations where the locks were set.
  keypair_info.limited = 0;
  keypair_info.from_first[0] = from_first;
  keypair_info.from_second[0] = from_second;

  mutex_tct<keypair_map_instance>::lock();
  std::pair<keypair_map_t::iterator, bool> result = keypair_map->insert(keypair_map_value_t(keypair_key, keypair_info));
  if (!result.second)
  {
    keypair_info_st& stored_info((*result.first).second);
    uint16_t prev_state = stored_info.state;
    stored_info.state &= keypair_info.state;			// Limit possible groups.
    if (prev_state != stored_info.state)
    {
      stored_info.limited++;
      stored_info.from_first[stored_info.limited] = from_first;
      stored_info.from_second[stored_info.limited] = from_second;
      DEBUGDEBUG_CERR("\nKEYPAIR: first: " << instance_first << "; second: " << instance_second << "; groups: " << (void*)(unsigned long)stored_info.state << '\n');
    }
    if (stored_info.state == 0)					// No group left?
    {
      FATALDEBUGDEBUG_CERR("\nKEYPAIR: There is a potential deadlock between lock " << keypair_key.instance1 << " and " << keypair_key.instance2 << '.');
      FATALDEBUGDEBUG_CERR("\nKEYPAIR: Previously, these locks were locked in the following locations:");
      for (int cnt = 0; cnt <= stored_info.limited; ++cnt)
	FATALDEBUGDEBUG_CERR("\nKEYPAIR: First at " << stored_info.from_first[cnt] << " and then at " << stored_info.from_second[cnt]);
      mutex_tct<keypair_map_instance>::unlock();
      core_dump();
    }
  }
  else
  {
    DEBUGDEBUG_CERR("\nKEYPAIR: first: " << instance_first << "; second: " << instance_second << "; groups: " << (void*)(unsigned long)keypair_info.state << '\n');

#if 0
    // X1,W/R2 + Y2,Z3 imply X1,Z3.
    // First assume the new pair is a possible X1,W/R2:
    if (!second_is_high_priority)
    {
      for (keypair_map_t::iterator iter = keypair_map->begin(); iter != keypair_map->end(); ++iter)
      {
      }
    }
#endif
  }
  mutex_tct<keypair_map_instance>::unlock();
}

If this gives you a headache, then just look at the possible
fatal debug output that this can cause:

KEYPAIR: There is a potential deadlock between lock " << keypair_key.instance1 << " and " << keypair_key.instance2 << '.'
KEYPAIR: Previously, these locks were locked in the following locations:"
KEYPAIR: First at " << stored_info.from_first[cnt] << " and then at " << stored_info.from_second[cnt]

Basically, this detects that if a thread first locks 'A' and then locked 'B'
it is never allowed that another thread at another time first locks 'B' and
then locks 'A'.  And then multiply the complexity of that with 1000 by
introducing read-locks, write-locks and high priority locks.
Where, a 'read lock' blocks other write locks, but not other read locks.
A 'write lock' locks both, other read and write locks.
And a high priority (read) lock is libcwd specific and has to do with
the queueing order in which pending locks are waiting. Normally a pending
write lock gets precendence over new read-lock attempts, but not when the
new read-lock attempt is high priority.  I needed this to fix all possible
dead locks.

If you would add this, then realize that it still is VERY hard to fix
a deadlock related bug - even while with the above code you can easily
and likely detect them all.  What is needed is a full backtrace of where
and when locks where set (that are involved in a potential deadlock)
and an administration per lock of where it is waiting for.

More complexity is needed to detect potential deadlocks.
For example if first instance 1 is locked (read or write) and
then a write lock is set (any) OR instance 2 is read locked,
and at any other time (different thread, different time)
first instance 2 is locked (read or write) and then an
instance 3 is locked (read or write), then a potential
deadlock needs to be detected when later (possibily different thread,
different time) first instance 3 is locked and then instance 1
is locked.  Hence the remark that X1,W/R2 + Y2,Z3 implies a X1,Z3 pair.
There are more "formulas" like that to be considered.

-- 
Carlo Wood <ca...@al...>