|
From: <sv...@va...> - 2008-01-17 23:19:52
|
Author: sewardj
Date: 2008-01-17 23:19:54 +0000 (Thu, 17 Jan 2008)
New Revision: 7353
Log:
Allow a WordFM iterator to be initialised so as to exclude all key
values below a given value. This allows efficiently iterating over
small subsets of a mapping. Use this in Helgrind to avoid a
performance bad case. Patch from Konstantin Serebryany.
Modified:
trunk/helgrind/hg_main.c
trunk/helgrind/hg_wordfm.c
trunk/helgrind/hg_wordfm.h
Modified: trunk/helgrind/hg_main.c
===================================================================
--- trunk/helgrind/hg_main.c 2008-01-17 14:37:24 UTC (rev 7352)
+++ trunk/helgrind/hg_main.c 2008-01-17 23:19:54 UTC (rev 7353)
@@ -4947,13 +4947,14 @@
(void*)firstA, (UWord)len, (void*)lastA);
locksToDelete = HG_(emptyWS)( univ_lsets );
- /* FIXME: don't iterate over the complete lock set */
- HG_(initIterFM)( map_locks );
- while (HG_(nextIterFM)( map_locks,
- (Word*)&gla, (Word*)&lk )) {
+ /* Iterate over all locks in the range firstA .. lastA inclusive. */
+ HG_(initIterAtFM)( map_locks, firstA );
+ while (HG_(nextIterFM)( map_locks, (Word*)&gla, (Word*)&lk )
+ && gla <= lastA) {
tl_assert(is_sane_LockN(lk));
- if (gla < firstA || gla > lastA)
- continue;
+ tl_assert(gla >= firstA);
+ tl_assert(gla <= lastA);
+
locksToDelete = HG_(addToWS)( univ_lsets, locksToDelete, (Word)lk );
/* If the lock is held, we must remove it from the currlock sets
of all threads that hold it. Also take the opportunity to
Modified: trunk/helgrind/hg_wordfm.c
===================================================================
--- trunk/helgrind/hg_wordfm.c 2008-01-17 14:37:24 UTC (rev 7352)
+++ trunk/helgrind/hg_wordfm.c 2008-01-17 23:19:54 UTC (rev 7353)
@@ -53,6 +53,24 @@
#include "pub_tool_libcassert.h"
#include "pub_tool_libcbase.h"
+
+#ifdef HG_WORDFM_STANDALONE // standalone compilation
+// Standalone mode (for testing).
+// On x86_64 compile like this:
+// gcc -m64 hg_wordfm.c -I../include -I../VEX/pub
+// -DVGA_amd64=1 -DHG_WORDFM_STANDALONE -g -O -Wall
+# include <assert.h>
+# include <string.h>
+# include <stdio.h>
+# include <stdlib.h>
+
+# undef tl_assert
+# define tl_assert assert
+# define vgPlain_memset memset
+
+#endif /* def HG_WORDFM_STANDALONE */
+
+
#define HG_(str) VGAPPEND(vgHelgrind_,str)
#include "hg_wordfm.h"
@@ -628,8 +646,59 @@
stackPush(fm, fm->root, 1);
}
+// set up FM for iteration
+// so that the first key subsequently produced by HG_(nextIterFM) is
+// the smallest key in the map >= start_at.
+void HG_(initIterAtFM) ( WordFM* fm, Word start_at )
+{
+ Int i;
+ AvlNode *n, *t;
+ Word cmpresS; /* signed */
+ UWord cmpresU; /* unsigned */
+
+ tl_assert(fm);
+ stackClear(fm);
+
+ if (!fm->root)
+ return;
+
+ n = NULL;
+ // We need to do regular search and fill in the stack.
+ t = fm->root;
+
+ while (True) {
+ if (t == NULL) return;
+
+ cmpresS
+ = fm->kCmp ? /*boxed*/ fm->kCmp( t->key, start_at )
+ : /*unboxed*/ cmp_signed_Words( t->key, start_at );
+
+ if (cmpresS == 0) {
+ // We found the exact key -- we are done.
+ // The iteration should start with this node.
+ stackPush(fm, t, 2);
+ // The stack now looks like {2, 2, ... ,2, 2}
+ return;
+ }
+ cmpresU = (UWord)cmpresS;
+ cmpresU >>=/*unsigned*/ (8 * sizeof(cmpresU) - 1);
+ if (!cmpresU) {
+ // Push this node only if we go to the left child.
+ stackPush(fm, t, 2);
+ }
+ t = t->child[cmpresU];
+ }
+ if (stackPop(fm, &n, &i)) {
+ // If we've pushed something to stack and did not find the exact key,
+ // we must fix the top element of stack.
+ tl_assert(i == 2);
+ stackPush(fm, n, 3);
+ // the stack looks like {2, 2, ..., 2, 3}
+ }
+}
+
// get next key/val pair. Will tl_assert if fm has been modified
-// or looked up in since initIterFM was called.
+// or looked up in since initIter{,At}FM was called.
Bool HG_(nextIterFM) ( WordFM* fm, /*OUT*/Word* pKey, /*OUT*/Word* pVal )
{
Int i = 0;
@@ -840,6 +909,119 @@
//--- Implementation ---//
//------------------------------------------------------------------//
+
+#ifdef HG_WORDFM_STANDALONE
+
+//------------------------------------------------------------------//
+//--- Simple test driver. ---//
+//------------------------------------------------------------------//
+
+// We create a map with N values {1, 3, 5, ..., (N*2-1)}
+// and do some trivial stuff with it.
+
+
+// Return the number of elements in range [beg, end).
+// Just lookup for each element in range and count.
+int search_all_elements_in_range_1(WordFM *map, long beg, long end)
+{
+ int n_found = 0;
+ int i;
+ for(i = beg; i < end; i++) {
+ Word key, val;
+ if(HG_(lookupFM)(map, &key, &val, (Word)i)){
+ n_found++;
+ assert(key == -val);
+ assert(key == (Word)i);
+ }
+ }
+ return n_found;
+}
+
+// Return the number of elements in range [beg, end).
+// Start with the largest element 'e' such that 'e <= beg'
+// and iterate until 'e < end'.
+int search_all_elements_in_range_2(WordFM *map, long beg, long end)
+{
+ int n_found = 0;
+ Word key, val;
+ HG_(initIterAtFM)(map, beg);
+ while(HG_(nextIterFM)(map, &key, &val) && (int)key < end) {
+ assert(key == -val);
+ n_found++;
+ }
+ HG_(doneIterFM)(map);
+ return n_found;
+}
+
+int main(void)
+{
+ int i, n = 10;
+ Word key, val;
+ int beg, end;
+
+ printf("Create the map, n=%d\n", n);
+ WordFM *map = HG_(newFM)(malloc, free, NULL/*unboxed Word cmp*/);
+
+ printf("Add keys: ");
+ for(i = 0; i < n; i++) {
+ long val = i * 2 + 1; // 1, 3, 5, ... (n*2-1)
+ printf("%ld ", val);
+ HG_(addToFM)(map, val, -val);
+ }
+ assert(HG_(sizeFM)(map) == n);
+ printf("\n");
+ printf("Iterate elements, size=%d\n", (int)HG_(sizeFM)(map));
+ HG_(initIterFM)(map);
+
+ while(HG_(nextIterFM(map, &key, &val))){
+ // int j;
+ // printf("Stack k=%d\n", (int)key);
+ // for(j = map->stackTop-1; j >= 0; j--) {
+ // printf("\t[%d]: k=%d s=%d\n", j,
+ // (int)map->nodeStack[j]->key, (int)map->numStack[j]);
+ // }
+ assert(key == -val);
+ }
+ HG_(doneIterFM)(map);
+
+ printf("Test initIterAtFM\n");
+ for(beg = 0; beg <= n*2; beg++) {
+ HG_(initIterAtFM)(map, (Word)beg);
+ int prev = -1;
+ printf("StartWith: %d: ", beg);
+ int n_iter = 0;
+
+ while(HG_(nextIterFM(map, &key, &val))) {
+ printf("%d ", (int)key);
+ assert(key == -val);
+ if(prev > 0) assert(prev + 2 == (int)key);
+ prev = (int)key;
+ n_iter++;
+ }
+ HG_(doneIterFM)(map);
+
+ printf("\ntotal: %d\n", n_iter);
+ if (beg < 1 ) assert(n_iter == n);
+ else if (beg >= n*2) assert(n_iter == 0);
+ else assert(n_iter == (n - beg/2));
+ }
+
+ printf("Compare search_all_elements_in_range_[12]\n");
+ for (beg = 0; beg <= n*2; beg++) {
+ for (end = 0; end <= n*2; end++) {
+ assert( search_all_elements_in_range_1(map, beg, end)
+ == search_all_elements_in_range_2(map, beg, end));
+ }
+ }
+
+ printf("Delete the map\n");
+ HG_(deleteFM)(map, NULL, NULL);
+ printf("Ok!\n");
+ return 0;
+}
+
+#endif
+
/*--------------------------------------------------------------------*/
/*--- end hg_wordfm.c ---*/
/*--------------------------------------------------------------------*/
Modified: trunk/helgrind/hg_wordfm.h
===================================================================
--- trunk/helgrind/hg_wordfm.h 2008-01-17 14:37:24 UTC (rev 7352)
+++ trunk/helgrind/hg_wordfm.h 2008-01-17 23:19:54 UTC (rev 7353)
@@ -87,8 +87,13 @@
// set up FM for iteration
void HG_(initIterFM) ( WordFM* fm );
+// set up FM for iteration
+// so that the first key subsequently produced by HG_(nextIterFM) is
+// the smallest key in the map >= start_at.
+void HG_(initIterAtFM) ( WordFM* fm, Word start_at );
+
// get next key/val pair. Will assert if fm has been modified
-// or looked up in since initIterFM was called.
+// or looked up in since initIterFM/initIterWithStartFM was called.
Bool HG_(nextIterFM) ( WordFM* fm,
/*OUT*/Word* pKey, /*OUT*/Word* pVal );
|
|
From: Konstantin S. <kon...@gm...> - 2008-01-21 10:07:56
|
Hi Julian,
I found out that this fix has an issue (which appears only in 32-bit mode).
+ while (HG_(nextIterFM)( map_locks, (Word*)&gla, (Word*)&lk )
+ && gla <= lastA) {
This should look like
+ while (HG_(nextIterFM)( map_locks, (Word*)&gla, (Word*)&lk )
+ && (Word)gla <= (Word)lastA) {
gla and lastA are unsigned variables, but we need signed comparison since
unboxed comparison in FM is signed.
So, we need to cast 'gla' and 'lastA' to Word before comparing them.
The same for
+ tl_assert(gla >= firstA);
+ tl_assert(gla <= lastA);
Thanks!
--kcc
On Jan 18, 2008 2:19 AM, <sv...@va...> wrote:
> Author: sewardj
> Date: 2008-01-17 23:19:54 +0000 (Thu, 17 Jan 2008)
> New Revision: 7353
>
> Log:
> Allow a WordFM iterator to be initialised so as to exclude all key
> values below a given value. This allows efficiently iterating over
> small subsets of a mapping. Use this in Helgrind to avoid a
> performance bad case. Patch from Konstantin Serebryany.
>
> Modified:
> trunk/helgrind/hg_main.c
> trunk/helgrind/hg_wordfm.c
> trunk/helgrind/hg_wordfm.h
>
>
> Modified: trunk/helgrind/hg_main.c
> ===================================================================
> --- trunk/helgrind/hg_main.c 2008-01-17 14:37:24 UTC (rev 7352)
> +++ trunk/helgrind/hg_main.c 2008-01-17 23:19:54 UTC (rev 7353)
> @@ -4947,13 +4947,14 @@
> (void*)firstA, (UWord)len, (void*)lastA);
> locksToDelete = HG_(emptyWS)( univ_lsets );
>
> - /* FIXME: don't iterate over the complete lock set */
> - HG_(initIterFM)( map_locks );
> - while (HG_(nextIterFM)( map_locks,
> - (Word*)&gla, (Word*)&lk )) {
> + /* Iterate over all locks in the range firstA .. lastA inclusive. */
> + HG_(initIterAtFM)( map_locks, firstA );
> + while (HG_(nextIterFM)( map_locks, (Word*)&gla, (Word*)&lk )
> + && gla <= lastA) {
> tl_assert(is_sane_LockN(lk));
> - if (gla < firstA || gla > lastA)
> - continue;
> + tl_assert(gla >= firstA);
> + tl_assert(gla <= lastA);
> +
> locksToDelete = HG_(addToWS)( univ_lsets, locksToDelete, (Word)lk );
> /* If the lock is held, we must remove it from the currlock sets
> of all threads that hold it. Also take the opportunity to
>
> Modified: trunk/helgrind/hg_wordfm.c
> ===================================================================
> --- trunk/helgrind/hg_wordfm.c 2008-01-17 14:37:24 UTC (rev 7352)
> +++ trunk/helgrind/hg_wordfm.c 2008-01-17 23:19:54 UTC (rev 7353)
> @@ -53,6 +53,24 @@
> #include "pub_tool_libcassert.h"
> #include "pub_tool_libcbase.h"
>
> +
> +#ifdef HG_WORDFM_STANDALONE // standalone compilation
> +// Standalone mode (for testing).
> +// On x86_64 compile like this:
> +// gcc -m64 hg_wordfm.c -I../include -I../VEX/pub
> +// -DVGA_amd64=1 -DHG_WORDFM_STANDALONE -g -O -Wall
> +# include <assert.h>
> +# include <string.h>
> +# include <stdio.h>
> +# include <stdlib.h>
> +
> +# undef tl_assert
> +# define tl_assert assert
> +# define vgPlain_memset memset
> +
> +#endif /* def HG_WORDFM_STANDALONE */
> +
> +
> #define HG_(str) VGAPPEND(vgHelgrind_,str)
> #include "hg_wordfm.h"
>
> @@ -628,8 +646,59 @@
> stackPush(fm, fm->root, 1);
> }
>
> +// set up FM for iteration
> +// so that the first key subsequently produced by HG_(nextIterFM) is
> +// the smallest key in the map >= start_at.
> +void HG_(initIterAtFM) ( WordFM* fm, Word start_at )
> +{
> + Int i;
> + AvlNode *n, *t;
> + Word cmpresS; /* signed */
> + UWord cmpresU; /* unsigned */
> +
> + tl_assert(fm);
> + stackClear(fm);
> +
> + if (!fm->root)
> + return;
> +
> + n = NULL;
> + // We need to do regular search and fill in the stack.
> + t = fm->root;
> +
> + while (True) {
> + if (t == NULL) return;
> +
> + cmpresS
> + = fm->kCmp ? /*boxed*/ fm->kCmp( t->key, start_at )
> + : /*unboxed*/ cmp_signed_Words( t->key, start_at );
> +
> + if (cmpresS == 0) {
> + // We found the exact key -- we are done.
> + // The iteration should start with this node.
> + stackPush(fm, t, 2);
> + // The stack now looks like {2, 2, ... ,2, 2}
> + return;
> + }
> + cmpresU = (UWord)cmpresS;
> + cmpresU >>=/*unsigned*/ (8 * sizeof(cmpresU) - 1);
> + if (!cmpresU) {
> + // Push this node only if we go to the left child.
> + stackPush(fm, t, 2);
> + }
> + t = t->child[cmpresU];
> + }
> + if (stackPop(fm, &n, &i)) {
> + // If we've pushed something to stack and did not find the exact
> key,
> + // we must fix the top element of stack.
> + tl_assert(i == 2);
> + stackPush(fm, n, 3);
> + // the stack looks like {2, 2, ..., 2, 3}
> + }
> +}
> +
> // get next key/val pair. Will tl_assert if fm has been modified
> -// or looked up in since initIterFM was called.
> +// or looked up in since initIter{,At}FM was called.
> Bool HG_(nextIterFM) ( WordFM* fm, /*OUT*/Word* pKey, /*OUT*/Word* pVal )
> {
> Int i = 0;
> @@ -840,6 +909,119 @@
> //--- Implementation ---//
> //------------------------------------------------------------------//
>
> +
> +#ifdef HG_WORDFM_STANDALONE
> +
> +//------------------------------------------------------------------//
> +//--- Simple test driver. ---//
> +//------------------------------------------------------------------//
> +
> +// We create a map with N values {1, 3, 5, ..., (N*2-1)}
> +// and do some trivial stuff with it.
> +
> +
> +// Return the number of elements in range [beg, end).
> +// Just lookup for each element in range and count.
> +int search_all_elements_in_range_1(WordFM *map, long beg, long end)
> +{
> + int n_found = 0;
> + int i;
> + for(i = beg; i < end; i++) {
> + Word key, val;
> + if(HG_(lookupFM)(map, &key, &val, (Word)i)){
> + n_found++;
> + assert(key == -val);
> + assert(key == (Word)i);
> + }
> + }
> + return n_found;
> +}
> +
> +// Return the number of elements in range [beg, end).
> +// Start with the largest element 'e' such that 'e <= beg'
> +// and iterate until 'e < end'.
> +int search_all_elements_in_range_2(WordFM *map, long beg, long end)
> +{
> + int n_found = 0;
> + Word key, val;
> + HG_(initIterAtFM)(map, beg);
> + while(HG_(nextIterFM)(map, &key, &val) && (int)key < end) {
> + assert(key == -val);
> + n_found++;
> + }
> + HG_(doneIterFM)(map);
> + return n_found;
> +}
> +
> +int main(void)
> +{
> + int i, n = 10;
> + Word key, val;
> + int beg, end;
> +
> + printf("Create the map, n=%d\n", n);
> + WordFM *map = HG_(newFM)(malloc, free, NULL/*unboxed Word cmp*/);
> +
> + printf("Add keys: ");
> + for(i = 0; i < n; i++) {
> + long val = i * 2 + 1; // 1, 3, 5, ... (n*2-1)
> + printf("%ld ", val);
> + HG_(addToFM)(map, val, -val);
> + }
> + assert(HG_(sizeFM)(map) == n);
> + printf("\n");
> + printf("Iterate elements, size=%d\n", (int)HG_(sizeFM)(map));
> + HG_(initIterFM)(map);
> +
> + while(HG_(nextIterFM(map, &key, &val))){
> + // int j;
> + // printf("Stack k=%d\n", (int)key);
> + // for(j = map->stackTop-1; j >= 0; j--) {
> + // printf("\t[%d]: k=%d s=%d\n", j,
> + // (int)map->nodeStack[j]->key, (int)map->numStack[j]);
> + // }
> + assert(key == -val);
> + }
> + HG_(doneIterFM)(map);
> +
> + printf("Test initIterAtFM\n");
> + for(beg = 0; beg <= n*2; beg++) {
> + HG_(initIterAtFM)(map, (Word)beg);
> + int prev = -1;
> + printf("StartWith: %d: ", beg);
> + int n_iter = 0;
> +
> + while(HG_(nextIterFM(map, &key, &val))) {
> + printf("%d ", (int)key);
> + assert(key == -val);
> + if(prev > 0) assert(prev + 2 == (int)key);
> + prev = (int)key;
> + n_iter++;
> + }
> + HG_(doneIterFM)(map);
> +
> + printf("\ntotal: %d\n", n_iter);
> + if (beg < 1 ) assert(n_iter == n);
> + else if (beg >= n*2) assert(n_iter == 0);
> + else assert(n_iter == (n - beg/2));
> + }
> +
> + printf("Compare search_all_elements_in_range_[12]\n");
> + for (beg = 0; beg <= n*2; beg++) {
> + for (end = 0; end <= n*2; end++) {
> + assert( search_all_elements_in_range_1(map, beg, end)
> + == search_all_elements_in_range_2(map, beg, end));
> + }
> + }
> +
> + printf("Delete the map\n");
> + HG_(deleteFM)(map, NULL, NULL);
> + printf("Ok!\n");
> + return 0;
> +}
> +
> +#endif
> +
> /*--------------------------------------------------------------------*/
> /*--- end hg_wordfm.c ---*/
> /*--------------------------------------------------------------------*/
>
> Modified: trunk/helgrind/hg_wordfm.h
> ===================================================================
> --- trunk/helgrind/hg_wordfm.h 2008-01-17 14:37:24 UTC (rev 7352)
> +++ trunk/helgrind/hg_wordfm.h 2008-01-17 23:19:54 UTC (rev 7353)
> @@ -87,8 +87,13 @@
> // set up FM for iteration
> void HG_(initIterFM) ( WordFM* fm );
>
> +// set up FM for iteration
> +// so that the first key subsequently produced by HG_(nextIterFM) is
> +// the smallest key in the map >= start_at.
> +void HG_(initIterAtFM) ( WordFM* fm, Word start_at );
> +
> // get next key/val pair. Will assert if fm has been modified
> -// or looked up in since initIterFM was called.
> +// or looked up in since initIterFM/initIterWithStartFM was called.
> Bool HG_(nextIterFM) ( WordFM* fm,
> /*OUT*/Word* pKey, /*OUT*/Word* pVal );
>
>
>
> -------------------------------------------------------------------------
> This SF.net email is sponsored by: Microsoft
> Defy all challenges. Microsoft(R) Visual Studio 2008.
> http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/
> _______________________________________________
> Valgrind-developers mailing list
> Val...@li...
> https://lists.sourceforge.net/lists/listinfo/valgrind-developers
>
|
|
From: Julian S. <js...@ac...> - 2008-01-21 12:29:50
|
On Monday 21 January 2008 11:08, Konstantin Serebryany wrote:
> Hi Julian,
>
> I found out that this fix has an issue (which appears only in 32-bit mode).
>
> + while (HG_(nextIterFM)( map_locks, (Word*)&gla, (Word*)&lk )
> + && gla <= lastA) {
>
> This should look like
> + while (HG_(nextIterFM)( map_locks, (Word*)&gla, (Word*)&lk )
> + && (Word)gla <= (Word)lastA) {
Good observation. Unfortunately I don't think this really fixes it.
Consider on a 32-bit platform, we want to iterate over locks in the
range
Addr firstA = 0x70000000
Addr lastA = 0x90000000 - 1
(UWord)firstA = 1879048192
(UWord)lastA = 2415919104
(Word)firstA = 1879048192
(Word)lastA = -1879048192
Since the trees will be ordered by Word, this means we are asking to
iterate over the range 1879048192 .. -1879048192, which is empty, and
so the iteration loop will terminate immediately.
I think the only fix is to change all the unboxed comparison stuff
in WordFM to use unsigned Words. Maybe it would be better to change
WordFM to used unsigned Words throughout.
This also shows there is a specification problem in HG_(initIterAt).
Using only HG_(initIter) and HG_(nextIter), we could iterate over
all elements of the tree, in some order - it did not matter what.
But HG_(initIterAt)(x) guarantees not to present any value < x;
unfortunately we did not say how "<" is defined in the unboxed case.
J
|
|
From: Julian S. <js...@ac...> - 2008-02-15 22:29:49
|
I believe this bug is finally fixed by r7409.
J
On Monday 21 January 2008 13:27, Julian Seward wrote:
> On Monday 21 January 2008 11:08, Konstantin Serebryany wrote:
> > Hi Julian,
> >
> > I found out that this fix has an issue (which appears only in 32-bit
> > mode).
> >
> > + while (HG_(nextIterFM)( map_locks, (Word*)&gla, (Word*)&lk )
> > + && gla <= lastA) {
> >
> > This should look like
> > + while (HG_(nextIterFM)( map_locks, (Word*)&gla, (Word*)&lk )
> > + && (Word)gla <= (Word)lastA) {
>
> Good observation. Unfortunately I don't think this really fixes it.
>
> Consider on a 32-bit platform, we want to iterate over locks in the
> range
>
> Addr firstA = 0x70000000
> Addr lastA = 0x90000000 - 1
>
> (UWord)firstA = 1879048192
> (UWord)lastA = 2415919104
>
> (Word)firstA = 1879048192
> (Word)lastA = -1879048192
>
> Since the trees will be ordered by Word, this means we are asking to
> iterate over the range 1879048192 .. -1879048192, which is empty, and
> so the iteration loop will terminate immediately.
>
> I think the only fix is to change all the unboxed comparison stuff
> in WordFM to use unsigned Words. Maybe it would be better to change
> WordFM to used unsigned Words throughout.
>
> This also shows there is a specification problem in HG_(initIterAt).
> Using only HG_(initIter) and HG_(nextIter), we could iterate over
> all elements of the tree, in some order - it did not matter what.
> But HG_(initIterAt)(x) guarantees not to present any value < x;
> unfortunately we did not say how "<" is defined in the unboxed case.
>
> J
>
> -------------------------------------------------------------------------
> This SF.net email is sponsored by: Microsoft
> Defy all challenges. Microsoft(R) Visual Studio 2008.
> http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/
> _______________________________________________
> Valgrind-developers mailing list
> Val...@li...
> https://lists.sourceforge.net/lists/listinfo/valgrind-developers
|
|
From: Konstantin S. <kon...@gm...> - 2008-01-21 12:40:43
|
>> Unfortunately I don't think this really fixes it.
Ouch!
Yep, it does not. It just hides the problem and makes it extremely rare.
>> I think the only fix is to change all the unboxed comparison stuff in
WordFM to use unsigned Words.
Yea... And we probably need to export one more FM method:
+ while (HG_(nextIterFM)( map_locks, (Word*)&gla, (Word*)&lk )
+ && compareFM(map_locks, gla,lastA) <= 0) { // use the comparison
function from map_locks
--kcc
On Jan 21, 2008 3:27 PM, Julian Seward <js...@ac...> wrote:
> On Monday 21 January 2008 11:08, Konstantin Serebryany wrote:
> > Hi Julian,
> >
> > I found out that this fix has an issue (which appears only in 32-bit
> mode).
> >
> > + while (HG_(nextIterFM)( map_locks, (Word*)&gla, (Word*)&lk )
> > + && gla <= lastA) {
> >
> > This should look like
> > + while (HG_(nextIterFM)( map_locks, (Word*)&gla, (Word*)&lk )
> > + && (Word)gla <= (Word)lastA) {
>
> Good observation. Unfortunately I don't think this really fixes it.
>
> Consider on a 32-bit platform, we want to iterate over locks in the
> range
>
> Addr firstA = 0x70000000
> Addr lastA = 0x90000000 - 1
>
> (UWord)firstA = 1879048192
> (UWord)lastA = 2415919104
>
> (Word)firstA = 1879048192
> (Word)lastA = -1879048192
>
> Since the trees will be ordered by Word, this means we are asking to
> iterate over the range 1879048192 .. -1879048192, which is empty, and
> so the iteration loop will terminate immediately.
>
> I think the only fix is to change all the unboxed comparison stuff
> in WordFM to use unsigned Words. Maybe it would be better to change
> WordFM to used unsigned Words throughout.
>
> This also shows there is a specification problem in HG_(initIterAt).
> Using only HG_(initIter) and HG_(nextIter), we could iterate over
> all elements of the tree, in some order - it did not matter what.
> But HG_(initIterAt)(x) guarantees not to present any value < x;
> unfortunately we did not say how "<" is defined in the unboxed case.
>
> J
>
|
|
From: Julian S. <js...@ac...> - 2008-01-21 13:01:51
|
> Yea... And we probably need to export one more FM method:
> + while (HG_(nextIterFM)( map_locks, (Word*)&gla, (Word*)&lk )
> + && compareFM(map_locks, gla,lastA) <= 0) { // use the comparison
> function from map_locks
Urr. You're right. That's ugly. That means 2 function calls per
element now.
Maybe it would be easier to have this:
// unchanged -- set up for unbounded iteration
initIterFM( WordFM* fm )
// change this back to the original version
nextIterFM( WordFM* fm, UWord* key, UWord* val)
// set up for bounded iteration, first value >= notBelow
initBoundedIterFM( WordFM* fm, UWord notBelow )
// get next value, except stop if > notAbove
nextBoundedIterFM( WordFM* fm, UWord notAbove, UWord* key, UWord* val )
That removes the extra compareFM call.
J
|