John:

Yes, I have seen the problem with Judy1 64Bit  using apt-get from ubuntu.  I have also found it only happens with the  GCC-4.8 compiler with -O2  and -O3.

If I fix the punning warnings, the problem goes away.   The problem does not show up using
the icc or clang compilers.  I am working on a fix.

The source code is "rusty" as Alan S. put it -- it is about 10 years old.  

The real exciting thing I discovered about a week ago is with the Linux 3.11 kernel  (Ubuntu 14.04).
I am getting about 3x speed improvement with JudyL 64bit, when malloc() is modified to use
2MB page sizes.  I cannot think of any reason why malloc uses 4KB pages anymore.
I have contended since 1977 that 1000 pages is enough for a process -- 1000 * 2MB = 2GB.
My latest ASUS laptop buy from Walmart cost $250 and had 4GB RAM.   I welcome comments.

doug
 
Doug Baskins <dougbaskins@yahoo.com>
On Thursday, May 8, 2014 5:38 PM, john skaller <skaller@users.sourceforge.net> wrote:
Hi, I am using Judy and Judy1 in particular, and one of my products
users is having a problem which he believes is a bug in Judy1.
his analysis is here:

https://github.com/felix-lang/felix/issues/59#issuecomment-42574599

He cited this:

http://sourceforge.net/p/judy/bugs/25/

as extra evidence.

I have built and run the same code on Ubuntu with gcc, and OSX with
clang and do not see the same problem, but of course this proves nothing.

It seems Judy1 is returning a key that wasn't inserted into it.
Since my code is a garbage collector that traces pointers,
an invalid value is causing a crash.

A copy of his comments from the GitHub bug system:

"""
Perplexingly the invalid pointer was still there at the end of the several hundred meg gc.log that list-02 would spew out. According to the code, the only other Judy1Set() would be in the code called from sweep(). While this was going on I was also trying things out with valgrind. Due to the nature of the pointer searching there should be plenty of invalid reads, however I did spot some invalid writes. Deep within the calls from Judy1Set there were some calls with either "invalid write 0 bytes after alloc'd 0" or "invalid write 8 bytes after alloc'd 0".

Quite odd, but perhaps it wasn't expecting malloc() to return a non-null value for malloc(0), so I fixed that in the judy code. It still errored, so I just gave it a bit of memory just in case this was a basic off by one mistake. I added some extra printfs now that the error was back out of the judy code and lo and behold the pointer from nowhere was still there. it was never inserted into the judy array. I made sure that array was nuked at the start of sweep(), but by the time it got to reap() it was there, just a few dozen bytes after the previous valid address.

Judy is just a efficient means of creating a set for integer valued keys after all, so lets just do that.
A set, a std::set. There shouldn't be any magical appearing values within that, not unless some erroneous code can hit some address perfectly while blind to where it is (otherwise valgrind would surely note it). it works...

So, the addresses observed in j_tmp in reap() contains at least one element that was not inserted into it in sweep() when the crash occurs.

Based upon the fact that the only invalid writes observed were deep within the judy call stack then the most likely cause is either a logical bug in the judy code or a bug introduced through the compilation of the judy code.
The very unlikely yet possible alternative would be a hardware bug as I've been doing this testing on one computer.
"""


--
john skaller
skaller@users.sourceforge.net
http://felix-lang.org




------------------------------------------------------------------------------
Is your legacy SCM system holding you back? Join Perforce May 7 to find out:
• 3 signs your SCM is hindering your productivity
• Requirements for releasing software faster
• Expert tips and advice for migrating your SCM now
http://p.sf.net/sfu/perforce
_______________________________________________
Judy-devel mailing list
Judy-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/judy-devel