fix 315545 (find_TTEntry_from_hcode): Assertion '(UChar*)sec->tt[tteNo].tcptr <= (UChar*)hcode' failed

Assertion 
  valgrind: m_transtab.c:674 (find_TTEntry_from_hcode):
  Assertion '(UChar*)sec->tt[tteNo].tcptr <= (UChar*)hcode' failed.
failure (encountered on some platforms while running gdbsrv tests).

The problem is related to invalidated entries and the host_extents
mapping between hostcode and the translation table entry.

The problem: when an entry is invalidated, the translation table
entry is changed to status Deleted. However, the host extent array
element is not cleaned up.
If a search for a host code address (find_TTEntry_from_hcode)
finds this entry, the translation table entry in Deleted status
is considered as a 'not found', which ensures that the invalidated
entry is not used (e.g. for chaining).
This is all ok.

However, it might be that this Deleted entry is re-used
(see function VG_(add_to_transtab), searching for a Empty
or Deleted entry.
If the Deleted entry is re-used, then a search for the
dead host code can give a result pointing to the re-used
entry. That is clearly wrong.
Note that it is unclear if this bug can only be triggered
while using gdbsrv or if this bug can be triggered with
just the "normal" invalidation logic of translation.
gdbsrv being a heavy "user" of invalidation, it might
be it helps to trigger the code. Alternatively, as gdbsrv
invalidation is special (e.g. invalidation of some entries
is done during translation of other entries), it might be
the bug is specific to gdbsrv.

In any case, to avoid the bug:
searching for an host code address must not only
ignore Deleted entries, but must also ignore an entry
found via a host_extent element which is for a Deleted
entry that was re-used afterwards (pointed to by a
newer host_extent element).


Multiple solutions are possible for fixing the bug:
Sol1: cleanup the host_extents array when an entry is deleted.
  The cleanup is however deemed costly:
  Each invalidate operation must do a search in the host_extents.
  The host_extents array must then be "compacted" to remove
  the "dead" host extent element from the array.
  The compact operation can be avoided if instead of removing
  the element, one marks instead the element as "dead"
  e.g. by using one bit of UInt len for that:
     UInt len : 31;
     Bool dead : 1;
  This avoids the compact, but still incurrs the cost of
  search and modify the host_extent for each entry invalidated.
  Invalidating entries seems to be a critical operation
  (e.g. specific ECLASS related  data structures have been
   done to allow fast deletion).
  => it is deemed that a solution not incurring cost during
  invaliation is preferrable.

* Sol 2: detect in find_TTEntry_from_hcode
  that the host_extent element is re-used, and handle it similarly
  to an host_extents which points at a Deleted entry.
  This detection is possible as if an entry is re-used after
  having been deleted, this implies that its host code will be
  after the end of the host code of the deleted entry
  (as host code of a sector is not re-used).
  The attached patch implements this solution.

* Sol 3: avoid re-using an entry : the entry would then stay
  in Deleted state. This is deemed not ok as it would
  imply that invalidation of entries will cause a sector to
  become full faster.

The patch:
* adds a new function
  Bool HostExtent__is_dead (const HostExtent* hx, const Sector* sec)
  telling if the host extent hx from sector sec is a dead entry.
* this function is used in find_TTEntry_from_hcode so that
  dead host extents are not resulting in host code to be found.
* adds a regression test which caused the assert failure before
  (bug was found/reported/isolated in a small test case by Dejan Jevtic).
* To check the logic of HostExtent__is_dead, m_transtab.c sanity check is
  completed to verify that the nr of entries in use in a sector is equal
  to the nr of non dead entries in the host extent array.
* adds/improves traces in m_transtab.c (enabled at compile
  time using #define DEBUG_TRANSTAB).
  Some already existing 'if (0)' conditions are replaced
  by if (DEBUG_TRANSTAB)

Regression tested on 
   f12/x86
   debian6/amd64 (also with export EXTRA_REGTEST_OPTS=--sanity-level=4)




git-svn-id: svn://svn.valgrind.org/valgrind/trunk@13290 a5019735-40e9-0310-863c-91ae7b9d1cf9