#25 Judy1 fails on 64 bit for array size >= 15
I had trouble using Judy1 arrays on 64 bit. It works perfectly as long as I don't set more than 15 bits but fails otherwise. I then tried to run Judy1SLCheck program and that too fails. My primary platform is AMD64 but I also found it failing on Mac in 64 bit (although 32 bit works just fine).Here is the output
Solaris/amd64
=== +++++++++ This test runs in 15 seconds on a PIII 750Mhz +++++++
gcc -m64 -O SLcompare.c -DHASHMETHOD -o SL_Hash
gcc -m64 -O SLcompare.c -DSPLAYMETHOD -o SL_Splay
gcc -m64 -O SLcompare.c -DREDBLACKMETHOD -o SL_Redblack
Compiling with Judy library: ../src/obj/.libs/libJudy.a
gcc -m64 -O -I../src SLcompare.c -DJUDYMETHOD -o SL_Judy ../src/obj/.libs/libJudy.a -lm
gcc -m64 -O -I../src Judy1LHCheck.c -o Judy1LHCheck ../src/obj/.libs/libJudy.a -lm
gcc -m64 -O -I../src Judy1LHTime.c -DNOINLINE -o Judy1LHTime ../src/obj/.libs/libJudy.a -lm
=== Pass: Compile of tests
Validate Judy1/JudyL/JudyHS functions (except Judy*ByCount)
Error: JudyLGet failed - Index missing, population = 2, file='Judy1LHCheck.c', 'function='TestJudyIns', line 542
=== 0 Failed: Judy1/JudyL/JudyHS validate program
Mac 64 bit
gcc -m64 -O SLcompare.c -DHASHMETHOD -o SL_Hash
gcc -m64 -O SLcompare.c -DSPLAYMETHOD -o SL_Splay
gcc -m64 -O SLcompare.c -DREDBLACKMETHOD -o SL_Redblack
Compiling with Judy library: ..//src/obj/.libs/libJudy.a
gcc -m64 -O -I../src SLcompare.c -DJUDYMETHOD -o SL_Judy ..//src/obj/.libs/libJudy.a -lm
gcc -m64 -O -I../src Judy1LHCheck.c -o Judy1LHCheck ..//src/obj/.libs/libJudy.a -lm
gcc -m64 -O -I../src Judy1LHTime.c -DNOINLINE -o Judy1LHTime ..//src/obj/.libs/libJudy.a -lm
=== Pass: Compile of tests
Validate Judy1/JudyL/JudyHS functions (except Judy*ByCount)
Error: JudyLGet failed - Index missing, population = 2, file='Judy1LHCheck.c', 'function='TestJudyIns', line 542
=== 0 Failed: Judy1/JudyL/JudyHS validate program
PASS: Checkit
==================
All 1 tests passed
==================
Mac 32 bit (this worked)
Validate Judy1/JudyL/JudyHS functions (except Judy*ByCount)
=== Pass: Judy1/JudyL/JudyHS validate program
Do a few timings tests of Judy1/JudyL/JudyHS
Pop1 Measmts J1S JLI J1T JLG J1MU/I JLMU/I HEAP/I
1 1 0.000 0.000 0.000 0.000 0.000 0.000 20.000 20.000 40.000 1.000 1.000 2.000
10 10 0.111 0.222 0.222 0.000 0.000 0.000 5.200 10.000 12.000 0.667 1.111 1.111
100 100 0.200 0.256 0.289 0.080 0.080 0.100 6.000 10.200 10.400 0.567 0.678 0.678
1000 1000 0.306 0.283 0.314 0.058 0.057 0.074 11.172 13.928 13.948 0.401 0.746 0.746
10000 10000 0.138 0.281 0.310 0.067 0.078 0.095 2.545 9.450 9.452 0.059 1.388 1.388
100000 100000 0.140 0.314 0.315 0.042 0.062 0.082 1.025 7.587 7.587 0.111 0.898 0.898
524284 524284 0.108 0.218 0.252 0.037 0.069 0.089 0.040 4.571 4.571 0.005 0.329 0.329
=== Pass: Judy1/JudyL/JudyHS performance program
Do a few timings tests of JudySL and friends
lines avg_linelen getline StoreD RAMused/line store/ln lookup/ln ADT
2168 37.3 byts 11.539 uS 1094 3833.9 byts 3.270 uS 0.392 uS HASH
2168 37.3 byts 0.190 uS 1094 0.0 byts 0.539 uS 0.364 uS SPLAY
2168 37.3 byts 0.167 uS 1094 0.0 byts 0.548 uS 0.356 uS REDBLACK
2168 37.3 byts 0.194 uS 1094 0.0 byts 0.629 uS 0.415 uS JUDY
=== Pass: JudySL if StoreD numbers are all the same
Another problem is that make check doesn't seems to work by default to compile 64 bit - it tries to compile in 32 bits and then fails with ELF32 class errors.
Addendum - the issue seems to be some kind of memory corruption in 1.0.5 (1.0.4 had no memory corruptions, but I guess I might be using wrong compilation flags with 1.0.4 as its default 64 bit configuration produced compilation errors). Here are some UMEM logs that show the corruption.
Reading Log file: data
umem allocator: redzone violation: write past end of buffer
buffer=4b6b00 bufctl=4b81c0 cache: umem_alloc_48
previous transaction on buffer 4b6b00:
thread=1 time=T-0.000225573 slab=4a3e20 cache: umem_alloc_48
libumem.so.1'umem_nofail_callback+0xfdb
libumem.so.1'umem_cache_alloc+0xc8
libumem.so.1'umem_alloc+0xaf
libumem.so.1'malloc+0x2e
bklogs'j__udy1AllocJLW+0x25
bklogs'Judy1Set+0x1eb
bklogs'BKREAD_Report+0xdc
bklogs'BKREAD_ReadFile+0x21d
bklogs'main+0x9e
bklogs'_start+0x6c
umem: heap corruption detected
stack trace:
libumem.so.1'_PROCEDURE_LINKAGE_TABLE_+0x95e
libumem.so.1'vmem_heap_arena+0x7bd
libumem.so.1'umem_free+0x93
libumem.so.1'valloc+0x1d5
libumem.so.1'free+0x15
bklogs'j__udy1FreeJLW+0x23
bklogs'Judy1Set+0x13b
bklogs'BKREAD_Report+0xdc
bklogs'BKREAD_ReadFile+0x21d
bklogs'main+0x9e
bklogs'_start+0x6c
I have a similar problem where I make a Judy1 array containing 1770 bits (whose indexes are 64-bit values). Then enumerating all the bits set in the array will give nonsense results. Attached the sample program.
Armin:
The enclosed patched JudyPrivateBranch.h file will allow GCC to compile Judy with all options. (-O2 preferred).
The problem does not show up on a MAC because it uses the clang compiler.
Doug -- author of Judy
Doug Baskins dougbaskins@yahoo.com
On Saturday, October 11, 2014 11:20 AM, Armin Rigo arigo@users.sf.net wrote:
Related
Bugs: #25
Thanks, it fixes my problem.