Issue with Bit mask and Buffer Overruns

[Toni C. <tca...@to...>]

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)); 

and

B)  #define JU_MASKHIGHERINC(BITPOS)  (-(BITPOS))

 

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 two's complement:
Flip all bits and add 1? 

 

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?

 

 

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. it's just a crash waiting to happen.

 

Perhaps I am using Judy1 incorrectly? Fingers crossed this is the case!

 

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> http://www.tovica.com

Tel: +44 (0) 7971 874 054

IM: AOL/Yahoo/MSN: tcassisi