Tony:
First I would like to commend you for trying to read that spaghetti bowl of code
buried in many #defines. I have since re-written Judy without many macros
to make it easy to read and understand. I have done many years of study
of Judy performance since I retired from HP in 2002. Someday I will have
a new Judy with at least the code cleaned up.
Toni Cassisi <[EMAIL PROTECTED]> wrote: I have been
examining Judy1 on the latest VS2005 for x86 and noticed a few things that I
would appreciate advise on:
1) Issue of - operator on unsigned data
The following two lines of code provide warnings about signed vs unsigned by
VS2005:
A) return (-(jpm.jpm_TotalMemWords * cJU_BYTESPERWORD));
// The code is correct, perhaps jpm_TotalMemWords
// should of been typed as "long".
and
B) #define JU_MASKHIGHERINC(BITPOS) (-(BITPOS))
// Again the code is correct, however it should of been
// written:
#define JU_MASKHIGHERINC(BITPOS) ((~(BITPOS)) + 1)
A breakpoint at point A) indicated that jpm_TotalMemWords was actually a
negative number being stored in an unsigned variable so am I right in presuming
that the - operator here is being used to do a twos complement: Flip all
bits and add 1?
// Yes, perhaps the code could of been a little more straight forward.
The reason I find it odd is that point B) seems incorrect according to the
comments surrounding it which deal with bit masks and only 1 bit being set.
In this context, surely to flip bits the operator is supposed to be ~, so
-(BITPOS) is actually flipping all bits and then adding 1, something
unintended perhaps?
// No, that was exactly what was intended -- to generate a mask of
upper bits.
2) Heap overruns
If I enable full CRT heap debugging, an exception will be thrown indicating
that Judy1 has somewhere overrun the heap block allocated to it. Specifically,
written past the end of the allocated buffer.
Unfortunately, this is detected only at the next alloc/free point, and given
the (to put it delicately) extensive use of DEFINEs, it is incredibly
difficult to even begin to guess why.
Note that if I change the memory management over to Windows native heaps, and
enable the Windows O/S heap checking, it also throws up similar heap corruption
issues.
As soon as you compile and run with the release CRT heap, no such problems
arise; i.e. its just a crash waiting to happen.
Perhaps I am using Judy1 incorrectly? Fingers crossed this is the case!
// I strongly suspect the bug is somewhere else. Judy has many miles on
it, but I decided to do some test using your specific test program (written in
C).
I modified JudyMalloc() to include "guard" bands on
each side of the malloc'ed buffer and then test the bands at the JudyFree(). I
tried many sizes (1..4096 words) of bands and found no corruption anywhere.
My test system was ubuntu linux with:
gcc version 4.1.2 20060928 (prerelease) (Ubuntu 4.1.1-13ubuntu5)
compiler path.
You are welcome to a copy of the test code I used if you want.
I hope you find the bug, I could not.
Again, thank you for your inputs and let me know if I can
be (no)help again.
Doug Baskins
PS. I just thought of another possibility. I heard that there is a bug in the
routine that allocates the jpm_t buffer. (In Judy1.h and JudyL.h)
typedef struct J_UDY1_POPULATION_AND_MEMORY
{
/* 1 */ Word_t jpm_Pop0; // total population-1 in array.
/* 2 */ jp_t jpm_JP; // JP to first branch; see above.
/* 4 */ Word_t jpm_LastUPop0; // last jpm_Pop0 when convert to BranchU
// Note: Field names match PJError_t for convenience in macros:
/* 7 */ char je_Errno; // one of the enums in Judy.h.
/* 7/8 */ int je_ErrID; // often an internal source line number.
/* 8/9 */ Word_t jpm_TotalMemWords; // words allocated in array.
} j1pm_t, *Pj1pm_t;
Try changing: /* 7 */ char je_Errno to int je_Errno.
This is not a fix, but if it fixes the problem, I will release a new Judy with
a good fix. Thanks in advance for your help.
In some systems, the malloc() does not allocate Word_t * n sized buffers all
the time. This leave "half word" aligned pointers and slow down some
processors.
LPVOID J1Array = NULL; // initialize Judy1 array
for (size_t LOOP = 2; LOOP<=64*1024; LOOP *= 2) {
J1FA(Rc_int, J1Array); ASSERT(Rc_int != JERR);
_IL(L"Setting backwards from %u to 1...\n",LOOP);
for (DWORD i=LOOP; i>0; --i) {
J1S(Rc_int, J1Array, i); ASSERT(Rc_int == 1);
}
_IL(L"\nDONE!\n");
J1MU(Rc_word, J1Array); // how much memory was used?
_WL(L"Time: %I64u ms\tJMemory: %.1fKiB\tFDMemory: %.1fKiB\n",
ms, (double)Rc_word/1024.0,
(double)pThread->dwHeapInUse/1024.0);
}
Output before the Heap failure:
Setting backwards from 2 to 1...
Setting backwards from 4 to 1...
Setting backwards from 8 to 1...
Setting backwards from 16 to 1...
Setting backwards from 32 to 1...
Setting backwards from 64 to 1...
< - - Failure here at i = 22, with callstack:
kernel32.dll!HeapValidate() + 0x14 bytes
Test.exe!JudyMalloc(unsigned long Words=23) Line 57 + 0x15 bytes
C++
Test.exe!j__udy1AllocJLL2(unsigned long Pop1=42, J_UDY1_POPULATION_AND_MEMORY
* Pjpm=0x00157b90) Line 334
Test.exe!j__udy1Cascade3(J_UDY_POINTER * Pjp=0x00172b0b, void *
Pjpm=0x00157b90) Line 761
Test.exe!j__udyInsWalk(J_UDY_POINTER * Pjp=0x00172b0b, unsigned long
Index=22, J_UDY1_POPULATION_AND_MEMORY * Pjpm=0x00157b90) Line 858
Test.exe!j__udyInsWalk(J_UDY_POINTER * Pjp=0x00172b0b, unsigned long
Index=22, J_UDY1_POPULATION_AND_MEMORY * Pjpm=0x00157b90) Line 1718
Test.exe!Judy1Set(void * * PPArray=0x0012ff50, unsigned long Index=22,
J_UDY_ERROR_STRUCT * PJError=0x00000000) Line 1933
Sequence:
a) Set values 64, 63,
23 into a new Judy1 = NULL array
b) When trying to insert 22, a JudyMalloc is finally triggered which is doing
the HeapValidate of this *previous* activity and finding corruption
Any suggestions on correcting my use of Judy or how to narrow down the issue
appreciated,
Regards,
Toni.
----
Toni Cassisi
Tovica Ltd
http://www.tovica.com
Tel: +44 (0) 7971 874 054
IM: AOL/Yahoo/MSN: tcassisi
-------------------------------------------------------------------------
This SF.net email is sponsored by DB2 Express
Download DB2 Express C - the FREE version of DB2 express and take
control of your XML. No limits. Just data. Click to get it now.
http://sourceforge.net/powerbar/db2/_______________________________________________
Judy-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/judy-devel
Doug Baskins <[EMAIL PROTECTED]>
-------------------------------------------------------------------------
This SF.net email is sponsored by DB2 Express
Download DB2 Express C - the FREE version of DB2 express and take
control of your XML. No limits. Just data. Click to get it now.
http://sourceforge.net/powerbar/db2/
_______________________________________________
Judy-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/judy-devel
