On Dec 8, 2007 12:02 PM, Julian Seward <[EMAIL PROTECTED]> wrote:
> > On Saturday 08 December 2007 12:10, Christoph Bartoschek wrote:
> >
> > In my opinion the problem is, that you have lost transitivity. Assume Word
>
> If transitivity is lost, then it means fast_cmp is broken.
>
> My current hypothesis is: the ordering of two N-bit signed words X, Y
> cannot be correctly established by examining the sign of the N-bit
> subtraction X - Y (which is what fast_cmp does). It is necessary to examine
> N+1 bits of subtraction result to establish the correct ordering. I think
> this is what John Reiser's comment about the carry flag means.
I've established now (after writing more sanity check code for the AVL
tree) that the problem is that the tree invariants are locally correct
(so each node's children correctly compare as less than or greater
than it ) but may be globally incorrect - so comparing a node to it's
ancestors all the way up to the root may yield a result which is not
correct.
The attached patch adds just such a sanity check - it is expensive
(order n squared in the size of the tree) as it recursively checks
that, for each node, all the nodes in it's left subtree are less than
it and all those in the right subtree greater than it.
With my test case this sanity check fails unless I use Nick's modified
fast_cmp routine.
> This seems to fit the facts best of all:
>
> - Problem is not to do with gcc -fstrict-overflow.
>
> * That is a recent phenomenon (gcc-4.3 ?) and #147545 was
> reported in early July.
See my other mail - I am on gcc 4.1.2 here.
> - Problem happened w/ Wine because perhaps Wine is doing some
> wierd address space games, and/or Tom is running a 4G+4G kernel, so
> there is stuff above 0xC000'0000 when there isn't usually.
Well I'm using a 64 bit kernel, but am valgrinding a 32 bit process.
Tom
--
Tom Hughes ([EMAIL PROTECTED])
http://www.compton.nu/
Index: include/pub_tool_oset.h
===================================================================
--- include/pub_tool_oset.h (revision 7279)
+++ include/pub_tool_oset.h (working copy)
@@ -147,6 +147,7 @@
extern Bool VG_(OSetWord_Remove) ( OSet* os, Word val );
extern void VG_(OSetWord_ResetIter) ( OSet* os );
extern Bool VG_(OSetWord_Next) ( OSet* os, Word* val );
+extern Bool VG_(OSetWord_SanityCheck) ( OSet *os );
/*--------------------------------------------------------------------*/
@@ -242,6 +243,7 @@
extern void* VG_(OSetGen_Remove) ( OSet* os, void* key );
extern void VG_(OSetGen_ResetIter) ( OSet* os );
extern void* VG_(OSetGen_Next) ( OSet* os );
+extern Bool VG_(OSetGen_SanityCheck) ( OSet *os );
#endif // __PUB_TOOL_OSET_H
Index: coregrind/m_oset.c
===================================================================
--- coregrind/m_oset.c (revision 7279)
+++ coregrind/m_oset.c (working copy)
@@ -761,6 +761,58 @@
}
/*--------------------------------------------------------------------*/
+/*--- Sanity checks ---*/
+/*--------------------------------------------------------------------*/
+static Bool avl_check_less(AvlTree* t, AvlNode* n, void* k)
+{
+ if (t->cmp) {
+ if (slow_cmp(t, k, n) < 0) return False;
+ } else {
+ if (fast_cmp(k, n) < 0) return False;
+ }
+ if (n->left && !avl_check_less(t, n->left, k)) return False;
+ if (n->right && !avl_check_less(t, n->right, k)) return False;
+ return True;
+}
+
+static Bool avl_check_greater(AvlTree* t, AvlNode* n, void* k)
+{
+ if (t->cmp) {
+ if (slow_cmp(t, k, n) > 0) return False;
+ } else {
+ if (fast_cmp(k, n) > 0) return False;
+ }
+ if (n->left && !avl_check_greater(t, n->left, k)) return False;
+ if (n->right && !avl_check_greater(t, n->right, k)) return False;
+ return True;
+}
+
+static Bool avl_check(AvlTree* t, AvlNode* n)
+{
+ if (t->cmp) {
+ if (n->left && !avl_check_less(t, n->left, slow_key_of_node(t, n))) return False;
+ if (n->right && !avl_check_greater(t, n->right, slow_key_of_node(t, n))) return False;
+ } else {
+ if (n->left && !avl_check_less(t, n->left, fast_key_of_node(n))) return False;
+ if (n->right && !avl_check_greater(t, n->right, fast_key_of_node(n))) return False;
+ }
+ if (n->left && !avl_check(t, n->left)) return False;
+ if (n->right && !avl_check(t, n->right)) return False;
+ return True;
+}
+
+Bool VG_(OSetGen_SanityCheck)(AvlTree* t)
+{
+ vg_assert(t);
+ return t->root ? avl_check(t, t->root) : True;
+}
+
+Bool VG_(OSetWord_SanityCheck)(AvlTree* t)
+{
+ return VG_(OSetGen_SanityCheck)(t);
+}
+
+/*--------------------------------------------------------------------*/
/*--- Miscellaneous operations ---*/
/*--------------------------------------------------------------------*/
Index: memcheck/mc_main.c
===================================================================
--- memcheck/mc_main.c (revision 7279)
+++ memcheck/mc_main.c (working copy)
@@ -4313,6 +4313,12 @@
return False;
}
+ /* Check that secondary V bit table is valid. */
+ if (!VG_(OSetGen_SanityCheck)(secVBitTable)) {
+ VG_(printf)("memcheck expensive sanity: secondary V bit table invalid");
+ return False;
+ }
+
/* If we're not checking for undefined value errors, the secondary V bit
* table should be empty. */
if (!MC_(clo_undef_value_errors)) {
-------------------------------------------------------------------------
SF.Net email is sponsored by:
Check out the new SourceForge.net Marketplace.
It's the best place to buy or sell services for
just about anything Open Source.
http://sourceforge.net/services/buy/index.php
_______________________________________________
Valgrind-developers mailing list
Valgrind-developers@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/valgrind-developers
