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
8 files changed