Stack-based memory corruption

NTDEV
1

I have a user-mode test app ive written for both win2k and winxp and so as a result
I am unable to use the InterlockedPushSList() and InterlockedPopSList() functions
and had to roll my own using InterlockedCompareExchange(). I’ve examined this function
hundreds of times and i still keep getting an access violation on the line pointed to
by the arrow. This function is supposed to do the *exact* same thing as InterlockedPopSList()
except without the windows XP dependancy.

Whats happening is pList is a valid pointer to a GENERIC_LIST structure and
pList->pFirst is a valid pointer to a GENERIC_ITEM structure. However in the time frame
between pTop=pList->pFirst and pNext=pTop->next, pTop is getting change to a seemingly random
value. I cannot see how this would be as its a stack-based variable, so its not being changed
by another thread. It also have allocated no arrays in this function, so i cant be going out of
bounds, but somehow, something is *corrupting* my stack based variables. After typing this
i realize that pTop->next could be free’d in the timeframe from pTop=pList->pFirst, but in
my test program i dont have to code against that possiblity as the list is never free’d unless
the program is shut down. Its an automatically adjusting user-mode look aside list, but thats
an aside from my real issue here, random stack corruption…

PGENERIC_ITEM POP_SLIST(PGENERIC_LIST pList)
{
PGENERIC_ITEM pTop, pNext;

do
{
pTop=pList->pFirst;
if(pTop==NULL) return NULL;

—>>>> pNext=pTop->next;
} while( InterlockedCompareExchangePointer( (PVOID *) &(pList->pFirst), pNext, pTop) != pTop);
InterlockedDecrement(&pList->dwNumItems);

return pTop;
}

Structure Definitions:

typedef struct _GENERIC_ITEM
{
struct _GENERIC_ITEM * prev;
struct _GENERIC_ITEM * next;

LPVOID lpVoid;
} GENERIC_ITEM, *PGENERIC_ITEM;

typedef struct _GENERIC_LIST
{
BYTE[48] lock;
volatile LONG dwNumItems;

volatile PGENERIC_ITEM pFirst;
PGENERIC_ITEM pLast;
} GENERIC_LIST, *PGENERIC_LIST;

Any Ideas anyone???

Asa

2

I’m feeling a little too foggy to analyze the code here, but my feeling is
that if is the CMPXCHG8B that is doing it to you. The way this op words
(ignoring the locking for simplicity) is:

IF (EDX:EAX = DEST)
ZF <- 1
DESC <- ECX:EBX
ELSE
ZF <- 0
EDX:EAX <- DEST

Note that this basically says “if the comparand equals the destination, set
the result to the destination. Otherwise set the comparand to the
destination.”

The manual says InterlockedCompareExchangePointer is implemented by inline
code, which would be this op, and maybe a couple others.

Now, what InterlockedCompareExchangePointer says it returns is “the pointer
value pointed to by Destination”. But is this the value BEFORE the
exchange, or the value AFTER the exchange? The documentation leaves that to
your imagination. From the operation of cmpxchg8b, what has to be happening
is this op is returning the Comparand field, which will be overloaded with
the original source value if it was different (in which case the exchange
store WILL NOT happen).

So what this routine must be doing is:

PVOID
InterlockedCompareExchangePointer(
IN OUT PVOID *Destination,
IN PVOID Exchange,
IN PVOID Comparand
)
{
if (Comparand == *Destination)
*Destination = Exchange;
else
Comparand = *Destination;
return Comparand;
}

This makes your overall loop:

do
{
pTop=pList->pFirst;
if (pTop==NULL)
return NULL;
pNext=pTop->next;
} while
(
//InterlockedCompareExchangePointer(
//(PVOID *) &(pList->pFirst), pNext, pTop) != pTop);

if (&(pList->pFirst) == pTop)
{
&(pList->pFirst) = pNext;
return pTop;
}
else
return &(pList->pFirst);
}

3

Note that one of the effect of cmpxchg8b is to leave edx:eax
loaded with the old value of dest. I didn’t disassemble the
function, but I imagine that it’s basically a wrapper around
cmpxchg8b, so, I expect it to always return the old dest; hence
the problem.

Assuming that, let me look at the code again. Assume you have a
list with two items, I’ll call them I1 and I2. Let pFirst point
to I1.
Here’s the code:

do
{
pTop=pList->pFirst;
if (pTop==NULL)
return NULL;
pNext=pTop->next;
} while (InterlockedCompareExchangePointer((PVOID *)
&(pList->pFirst), pNext, pTop) != pTop);

Now, this is what could be happening:

do {
pTop = I1
pNext = I1.next = I2
}
pFirst = I1, pTop = I1, pFirst==pTop, pFirst = pNext = I2, I2
!= pTop, so,

do {
pTop = I2
pNext = I2.next = NULL
}
pFirst = I2, pTop = I2, pFirst==pTop, pFirst = pNext = NULL,
NULL != pTop, so,

do {
pTop = NULL
pNext = NULL.next =====> CRASH, BANG!

I did it a bit too fast, so, I may be wrong, but a quick step
through with a debugger will clear it up.

Alberto.

----- Original Message -----
From: “Loren Wilton”
To: “Windows System Software Devs Interest List”

Sent: Sunday, May 01, 2005 9:26 PM
Subject: Re: [ntdev] Stack-based memory corruption

> I’m feeling a little too foggy to analyze the code here, but
> my feeling is
> that if is the CMPXCHG8B that is doing it to you. The way
> this op words
> (ignoring the locking for simplicity) is:
>
> IF (EDX:EAX = DEST)
> ZF <- 1
> DESC <- ECX:EBX
> ELSE
> ZF <- 0
> EDX:EAX <- DEST
>
> Note that this basically says “if the comparand equals the
> destination, set
> the result to the destination. Otherwise set the comparand to
> the
> destination.”
>
> The manual says InterlockedCompareExchangePointer is
> implemented by inline
> code, which would be this op, and maybe a couple others.
>
> Now, what InterlockedCompareExchangePointer says it returns is
> “the pointer
> value pointed to by Destination”. But is this the value
> BEFORE the
> exchange, or the value AFTER the exchange? The documentation
> leaves that to
> your imagination. From the operation of cmpxchg8b, what has
> to be happening
> is this op is returning the Comparand field, which will be
> overloaded with
> the original source value if it was different (in which case
> the exchange
> store WILL NOT happen).
>
> So what this routine must be doing is:
>
> PVOID
> InterlockedCompareExchangePointer(
> IN OUT PVOID *Destination,
> IN PVOID Exchange,
> IN PVOID Comparand
> )
> {
> if (Comparand == *Destination)
> *Destination = Exchange;
> else
> Comparand = *Destination;
> return Comparand;
> }
>
> This makes your overall loop:
>
> do
> {
> pTop=pList->pFirst;
> if (pTop==NULL)
> return NULL;
> pNext=pTop->next;
> } while
> (
> //InterlockedCompareExchangePointer(
> //(PVOID *) &(pList->pFirst), pNext, pTop) != pTop);
>
> if (&(pList->pFirst) == pTop)
> {
> &(pList->pFirst) = pNext;
> return pTop;
> }
> else
> return &(pList->pFirst);
> }
>
>
>
> —
> Questions? First check the Kernel Driver FAQ at
> http://www.osronline.com/article.cfm?id=256
>
> You are currently subscribed to ntdev as: xxxxx@ieee.org
> To unsubscribe send a blank email to
> xxxxx@lists.osr.com

4

I realize what InterlockedCompareExchange does, thats why i used it here. My eventual
goal is to create a platform independent InterlockedPopSList as i need the program to
run on Windows 2000, and that function is available only on XP+.

Ive stepped through it with WinDBG and the failure *looks* like it is occuring between
pTop=pList->pFirst and pNext=pTop->next;
I have windbg open with locals showing and everything, i click the + next to pList
and click the + next to pFirst and i see the *value* of pFirst. however the statement
it access violations at, pNext=pTop->next pTop now has some *bizarre* value. whereas before
it went through the if statement, it had the *correct* value.

im rather sure the issue doesnt involve any sort of side effect of InterlockedComp.Exg.
If anyone can come up with a better implementation of InterlockedPopSList, id be glad to take
it though :smiley:

asa

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of Alberto Moreira
Sent: Monday, May 02, 2005 9:29 PM
To: Windows System Software Devs Interest List
Subject: Re: [ntdev] Stack-based memory corruption

Note that one of the effect of cmpxchg8b is to leave edx:eax
loaded with the old value of dest. I didn’t disassemble the
function, but I imagine that it’s basically a wrapper around
cmpxchg8b, so, I expect it to always return the old dest; hence
the problem.

Assuming that, let me look at the code again. Assume you have a
list with two items, I’ll call them I1 and I2. Let pFirst point
to I1.
Here’s the code:

do
{
pTop=pList->pFirst;
if (pTop==NULL)
return NULL;
pNext=pTop->next;
} while (InterlockedCompareExchangePointer((PVOID *)
&(pList->pFirst), pNext, pTop) != pTop);

Now, this is what could be happening:

do {
pTop = I1
pNext = I1.next = I2
}
pFirst = I1, pTop = I1, pFirst==pTop, pFirst = pNext = I2, I2
!= pTop, so,

do {
pTop = I2
pNext = I2.next = NULL
}
pFirst = I2, pTop = I2, pFirst==pTop, pFirst = pNext = NULL,
NULL != pTop, so,

do {
pTop = NULL
pNext = NULL.next =====> CRASH, BANG!

I did it a bit too fast, so, I may be wrong, but a quick step
through with a debugger will clear it up.

Alberto.

----- Original Message -----
From: “Loren Wilton”
To: “Windows System Software Devs Interest List”

Sent: Sunday, May 01, 2005 9:26 PM
Subject: Re: [ntdev] Stack-based memory corruption

> I’m feeling a little too foggy to analyze the code here, but
> my feeling is
> that if is the CMPXCHG8B that is doing it to you. The way
> this op words
> (ignoring the locking for simplicity) is:
>
> IF (EDX:EAX = DEST)
> ZF <- 1
> DESC <- ECX:EBX
> ELSE
> ZF <- 0
> EDX:EAX <- DEST
>
> Note that this basically says “if the comparand equals the
> destination, set
> the result to the destination. Otherwise set the comparand to
> the
> destination.”
>
> The manual says InterlockedCompareExchangePointer is
> implemented by inline
> code, which would be this op, and maybe a couple others.
>
> Now, what InterlockedCompareExchangePointer says it returns is
> “the pointer
> value pointed to by Destination”. But is this the value
> BEFORE the
> exchange, or the value AFTER the exchange? The documentation
> leaves that to
> your imagination. From the operation of cmpxchg8b, what has
> to be happening
> is this op is returning the Comparand field, which will be
> overloaded with
> the original source value if it was different (in which case
> the exchange
> store WILL NOT happen).
>
> So what this routine must be doing is:
>
> PVOID
> InterlockedCompareExchangePointer(
> IN OUT PVOID *Destination,
> IN PVOID Exchange,
> IN PVOID Comparand
> )
> {
> if (Comparand == *Destination)
> *Destination = Exchange;
> else
> Comparand = *Destination;
> return Comparand;
> }
>
> This makes your overall loop:
>
> do
> {
> pTop=pList->pFirst;
> if (pTop==NULL)
> return NULL;
> pNext=pTop->next;
> } while
> (
> //InterlockedCompareExchangePointer(
> //(PVOID *) &(pList->pFirst), pNext, pTop) != pTop);
>
> if (&(pList->pFirst) == pTop)
> {
> &(pList->pFirst) = pNext;
> return pTop;
> }
> else
> return &(pList->pFirst);
> }
>
>
>
> —
> Questions? First check the Kernel Driver FAQ at
> http://www.osronline.com/article.cfm?id=256
>
> You are currently subscribed to ntdev as: xxxxx@ieee.org
> To unsubscribe send a blank email to
> xxxxx@lists.osr.com

—
Questions? First check the Kernel Driver FAQ at http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as: xxxxx@rivin.net
To unsubscribe send a blank email to xxxxx@lists.osr.com

5

Asa Yeamans wrote:

I realize what InterlockedCompareExchange does, thats why i used it here. My eventual
goal is to create a platform independent InterlockedPopSList as i need the program to
run on Windows 2000, and that function is available only on XP+.

Ive stepped through it with WinDBG and the failure *looks* like it is occuring between
pTop=pList->pFirst and pNext=pTop->next;
I have windbg open with locals showing and everything, i click the + next to pList
and click the + next to pFirst and i see the *value* of pFirst. however the statement
it access violations at, pNext=pTop->next pTop now has some *bizarre* value. whereas before
it went through the if statement, it had the *correct* value.

im rather sure the issue doesnt involve any sort of side effect of InterlockedComp.Exg.
If anyone can come up with a better implementation of InterlockedPopSList, id be glad to take
it though :smiley:

asa

As Loren and Alberto pointed out, your while condition is flawed. The
loop will end only when pTop is 0.

Instead of Interlock…() != pTop use Interlock…() != pNext
You should know that InterlockedXXX routines are atomic only with
respect to other InterlockedXXX calls.
So, accessing your pointers like that may get you into trouble.

Andrei.

PGENERIC_ITEM POP_SLIST(PGENERIC_LIST pList)
{
PGENERIC_ITEM pTop, pNext;

do
{
pTop=pList->pFirst;
if(pTop==NULL) return NULL;

—>>>> pNext=pTop->next;
} while( InterlockedCompareExchangePointer( (PVOID *) &(pList->pFirst), pNext, pTop) != pTop);
InterlockedDecrement(&pList->dwNumItems);

return pTop;
}

–
This message was scanned for spam and viruses by BitDefender.
For more information please visit http://linux.bitdefender.com/

6

D’oh i knew they were saying something…

(never read emails late at night…)

Thanks, Asa

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of Andrei
Zlate-Podani
Sent: Tuesday, May 03, 2005 3:25 AM
To: Windows System Software Devs Interest List
Subject: Re: [ntdev] Stack-based memory corruption

Asa Yeamans wrote:

I realize what InterlockedCompareExchange does, thats why i used it here. My eventual
goal is to create a platform independent InterlockedPopSList as i need the program to
run on Windows 2000, and that function is available only on XP+.

Ive stepped through it with WinDBG and the failure *looks* like it is occuring between
pTop=pList->pFirst and pNext=pTop->next;
I have windbg open with locals showing and everything, i click the + next to pList
and click the + next to pFirst and i see the *value* of pFirst. however the statement
it access violations at, pNext=pTop->next pTop now has some *bizarre* value. whereas before
it went through the if statement, it had the *correct* value.

im rather sure the issue doesnt involve any sort of side effect of InterlockedComp.Exg.
If anyone can come up with a better implementation of InterlockedPopSList, id be glad to take
it though :smiley:

asa

As Loren and Alberto pointed out, your while condition is flawed. The
loop will end only when pTop is 0.

Instead of Interlock…() != pTop use Interlock…() != pNext
You should know that InterlockedXXX routines are atomic only with
respect to other InterlockedXXX calls.
So, accessing your pointers like that may get you into trouble.

Andrei.

PGENERIC_ITEM POP_SLIST(PGENERIC_LIST pList)
{
PGENERIC_ITEM pTop, pNext;

do
{
pTop=pList->pFirst;
if(pTop==NULL) return NULL;

—>>>> pNext=pTop->next;
} while( InterlockedCompareExchangePointer( (PVOID *) &(pList->pFirst), pNext, pTop) != pTop);
InterlockedDecrement(&pList->dwNumItems);

return pTop;
}

–
This message was scanned for spam and viruses by BitDefender.
For more information please visit http://linux.bitdefender.com/

Questions? First check the Kernel Driver FAQ at http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as: xxxxx@rivin.net
To unsubscribe send a blank email to xxxxx@lists.osr.com