Re: Elusive bug with JudySLLast(), 64-bit mode

[john s. <sk...@us...>]

On 17/11/2012, at 2:30 AM, Tim Margheim wrote:

> I've got a situation where JudySLLast() is mistakenly returning NULL when searching with certain Index values, when it should be returning the last item on the tree.  I managed to reproduce it in this stripped-down test code.  It only occurs in the 64-bit version.  Can anyone reproduce it?

I tried but failed:

#include <judy.h>
#include <strings.h>
#include <stdio.h>

int main() {
Pvoid_t JudySLRoot = NULL;   // main JudySL array
PPvoid_t PValue = NULL;      // pointer to JudySL array value
char *Strings[8] = {"'hood", "'round", "'s gravenhage", "'tween", "'tween decks", ".22", ".22 caliber", ".22 calibre"};
//char *Strings[8] = {"'hood", "'round", "'s gravenhage", "'tween", "'tween decks", ".22", ".22 baliber", ".22 calibre"}; //using this makes the bug go away (changed the 2nd-to-last string)
char *String_Key = NULL;

for (size_t I=0; I<8; I++) { // add all 8 strings
   String_Key = Strings[I];
   PValue = JudySLIns(&JudySLRoot, (uint8_t*)String_Key, PJE0);
   *((Word_t*)PValue) = I; //Assign each one a corresponding value
}

uint8_t Retrieved_String[500]={0};
strcpy ((char*)Retrieved_String, ".22-calibre");
PValue = JudySLLast(JudySLRoot, (uint8_t*)Retrieved_String, PJE0); //WRONG: returns NULL
if (PValue == NULL) printf ("%s -> NULL\n", (char*)Retrieved_String);
else printf ("%s -> %ld\n", (char*)Retrieved_String,*(long*)PValue);

strcpy ((char*)Retrieved_String, ".22 calibre");
PValue = JudySLLast(JudySLRoot, (uint8_t*)Retrieved_String, PJE0); //RIGHT: returns ".22 calibre"'s entry
if (PValue == NULL) printf ("%s -> NULL\n", (char*)Retrieved_String);
else printf ("%s -> %ld\n", (char*)Retrieved_String,*(long*)PValue);

strcpy ((char*)Retrieved_String, ".22 calibres");
PValue = JudySLLast(JudySLRoot, (uint8_t*)Retrieved_String, PJE0); //RIGHT: returns ".22 calibre"'s entry
if (PValue == NULL) printf ("%s -> NULL\n", (char*)Retrieved_String);
else printf ("%s -> %ld\n", (char*)Retrieved_String,*(long*)PValue);

strcpy ((char*)Retrieved_String, ".22 calicre");
PValue = JudySLLast(JudySLRoot, (uint8_t*)Retrieved_String, PJE0); //RIGHT: returns ".22 calibre"'s entry
if (PValue == NULL) printf ("%s -> NULL\n", (char*)Retrieved_String);
else printf ("%s -> %ld\n", (char*)Retrieved_String,*(long*)PValue);

strcpy ((char*)Retrieved_String, ".22 caljbre");
PValue = JudySLLast(JudySLRoot, (uint8_t*)Retrieved_String, PJE0); //WRONG: returns NULL
if (PValue == NULL) printf ("%s -> NULL\n", (char*)Retrieved_String);
else printf ("%s -> %ld\n", (char*)Retrieved_String,*(long*)PValue);

}


~/felix>gcc --version
i686-apple-darwin10-gcc-4.2.1 (GCC) 4.2.1 (Apple Inc. build 5666) (dot 3)

~/felix>g++ -m64  -I build/release/lib/rtl -Lbuild/release/lib/rtl/ -ljudy_static jt.cpp
jt.cpp: In function ‘int main()’:
jt.cpp:8: warning: deprecated conversion from string constant to ‘char*’
...

~/felix>./a.out
.22 calibre -> 7
.22 calibre -> 7
.22 calibre -> 7
.22 calibre -> 7
.22 calibre -> 7

I also tried with clang.
~/felix>clang --version
clang version 3.1 (tags/RELEASE_31/final)
Target: x86_64-apple-darwin10.8.0

Same result. Note I'm using C++ not C, hence the warning.
Also tried with dynamic linkage, worked as well.

I have vague idea: if you're using "the very latest gcc" with -O2 or higher
optimisation -- your code (and Judy) are not ISO compliant, they break
strict aliasing rules. Later versions of gcc actually use this rule for
optimisation.

The rule says type punning is not allowed. So this means pointer
casts are always wrong, other than two and fro with void*.
I found my code broke apart on Linux where I have a later version
of gcc than on my Mac, so I had to turn on -fnostrict-aliasing with -O2.


--
john skaller
sk...@us...
http://felix-lang.org