457 lines
8.6 KiB
C
457 lines
8.6 KiB
C
/*++
|
||
|
||
Copyright (c) 1997 Microsoft Corporation
|
||
|
||
Module Name:
|
||
|
||
stack.c
|
||
|
||
Abstract:
|
||
|
||
This provides a generic stack handler to push/pop things onto it
|
||
|
||
Author:
|
||
|
||
Stephane Plante (splante)
|
||
|
||
Environment:
|
||
|
||
User, Kernel
|
||
|
||
--*/
|
||
|
||
#include "pch.h"
|
||
|
||
NTSTATUS
|
||
StackAllocate(
|
||
OUT PSTACK *Stack,
|
||
IN ULONG StackElementSize
|
||
)
|
||
/*++
|
||
|
||
Routine Description:
|
||
|
||
This routine allocates memory and returns a stack object
|
||
|
||
Arguments:
|
||
|
||
Stack - Where to store a pointer to the stack
|
||
StackElementSize - How much space on the stack a single element takes
|
||
up
|
||
|
||
Return Value:
|
||
|
||
NTSTATUS
|
||
|
||
--*/
|
||
{
|
||
PSTACK tempStack;
|
||
NTSTATUS status = STATUS_SUCCESS;
|
||
|
||
//
|
||
// Make sure that we have some place to store the stack pointer
|
||
//
|
||
ASSERT( Stack != NULL );
|
||
ASSERT( StackElementSize != 0 );
|
||
|
||
//
|
||
// Allocate a block of memory for the stack
|
||
//
|
||
tempStack = MEMORY_ALLOCATE(
|
||
sizeof(STACK) + ( (STACK_GROWTH_RATE * StackElementSize) - 1)
|
||
);
|
||
if (tempStack == NULL) {
|
||
|
||
status = STATUS_INSUFFICIENT_RESOURCES;
|
||
goto StackAllocateExit;
|
||
}
|
||
|
||
//
|
||
// Setup the control block of the stack
|
||
//
|
||
tempStack->Signature = (ULONG) STACK_SIGNATURE;
|
||
tempStack->StackSize = STACK_GROWTH_RATE * StackElementSize;
|
||
tempStack->StackElementSize = StackElementSize;
|
||
tempStack->TopOfStack = 0;
|
||
|
||
//
|
||
// Zero out the current elements on the stack
|
||
//
|
||
MEMORY_ZERO(
|
||
&(tempStack->Stack[0]),
|
||
STACK_GROWTH_RATE * StackElementSize
|
||
);
|
||
|
||
//
|
||
// Return the stack pointer
|
||
//
|
||
StackAllocateExit:
|
||
*Stack = tempStack;
|
||
return status;
|
||
|
||
}
|
||
|
||
NTSTATUS
|
||
StackFree(
|
||
IN OUT PSTACK *Stack
|
||
)
|
||
/*++
|
||
|
||
Routine Description:
|
||
|
||
This routine frees the stack
|
||
|
||
Arguments:
|
||
|
||
Stack - Where to find a pointer to the stack
|
||
|
||
Return Value:
|
||
|
||
NTSTATUS
|
||
|
||
--*/
|
||
{
|
||
//
|
||
// Make sure that we point to something
|
||
//
|
||
ASSERT( Stack != NULL );
|
||
ASSERT( (*Stack)->Signature == STACK_SIGNATURE );
|
||
|
||
//
|
||
// Free the stack
|
||
//
|
||
MEMORY_FREE( *Stack );
|
||
|
||
//
|
||
// Point the stack to nowhere
|
||
//
|
||
*Stack = NULL;
|
||
|
||
return STATUS_SUCCESS;
|
||
}
|
||
|
||
NTSTATUS
|
||
StackParent(
|
||
IN OUT PSTACK *Stack,
|
||
IN PVOID Child,
|
||
OUT PVOID Parent
|
||
)
|
||
/*++
|
||
|
||
Routine Description:
|
||
|
||
This routine returns a pointer to the stack location that is before
|
||
the given Child.
|
||
|
||
Arguments:
|
||
|
||
Stack - The stack to operate on
|
||
Child - This is the node whose parent we want
|
||
Parent - This is where we store a pointer to the parent stack loc
|
||
|
||
Return Value:
|
||
|
||
NTSTATUS
|
||
|
||
--*/
|
||
{
|
||
PSTACK localStack;
|
||
ULONG Addr = (ULONG) Child;
|
||
|
||
//
|
||
// Make sure that we point to something
|
||
//
|
||
ASSERT( Stack != NULL );
|
||
ASSERT( (*Stack)->Signature == STACK_SIGNATURE );
|
||
ASSERT( Parent != NULL );
|
||
|
||
//
|
||
// make sure that the child node actually lies on the stack
|
||
//
|
||
localStack = *Stack;
|
||
if ( Addr < (ULONG) localStack->Stack ||
|
||
Addr > (ULONG) &(localStack->Stack[localStack->TopOfStack + 1]) -
|
||
localStack->StackElementSize ) {
|
||
|
||
*( (PULONG *)Parent) = NULL;
|
||
return STATUS_FAIL_CHECK;
|
||
|
||
}
|
||
|
||
//
|
||
// Make sure that the child node isn't the first element
|
||
//
|
||
if (Addr < (ULONG) &(localStack->Stack[localStack->StackElementSize]) ) {
|
||
|
||
*( (PULONG *)Parent) = NULL;
|
||
return STATUS_SUCCESS;
|
||
|
||
}
|
||
|
||
//
|
||
// Set the parent to be one before the child
|
||
//
|
||
*( (PULONG *)Parent) = (PULONG) (Addr - localStack->StackElementSize);
|
||
|
||
//
|
||
// Done
|
||
//
|
||
return STATUS_SUCCESS;
|
||
}
|
||
|
||
NTSTATUS
|
||
StackPop(
|
||
IN OUT PSTACK *Stack
|
||
)
|
||
/*++
|
||
|
||
Routine Description:
|
||
|
||
This routine reclaims the memory used for a stack location
|
||
and wipes out whatever data existed in the reclaimed area
|
||
|
||
Arguments:
|
||
|
||
Stack - Where to find a pointer to the stack
|
||
|
||
Return Value:
|
||
|
||
NTSTATUS
|
||
|
||
--*/
|
||
{
|
||
PSTACK localStack;
|
||
|
||
//
|
||
// Make sure that we point to something
|
||
//
|
||
ASSERT( Stack != NULL );
|
||
ASSERT( (*Stack)->Signature == STACK_SIGNATURE );
|
||
|
||
//
|
||
// Is there an item that we can remove from the stack?
|
||
//
|
||
localStack = *Stack;
|
||
if ( localStack->TopOfStack == 0) {
|
||
|
||
return STATUS_FAIL_CHECK;
|
||
|
||
}
|
||
|
||
//
|
||
// Wipe out the top-most element on the stack
|
||
//
|
||
localStack->TopOfStack -= localStack->StackElementSize;
|
||
MEMORY_ZERO(
|
||
&( localStack->Stack[ localStack->TopOfStack ] ),
|
||
localStack->StackElementSize
|
||
);
|
||
|
||
return STATUS_SUCCESS;
|
||
}
|
||
|
||
NTSTATUS
|
||
StackPush(
|
||
IN OUT PSTACK *Stack,
|
||
OUT PVOID StackElement
|
||
)
|
||
/*++
|
||
|
||
Routine Description:
|
||
|
||
This routine obtains a pointer for an object on the top of the stack
|
||
and increments the top to point to something that can be then be used
|
||
again.
|
||
|
||
Arguments:
|
||
|
||
Stack - Where to find a pointer to the stack
|
||
StackElement - Pointer to the element to be added to the stack
|
||
|
||
Return Value:
|
||
|
||
NTSTATUS
|
||
|
||
--*/
|
||
{
|
||
PSTACK localStack;
|
||
PSTACK tempStack;
|
||
ULONG newSize;
|
||
ULONG deltaSize;
|
||
|
||
//
|
||
// Make sure that we point to something
|
||
//
|
||
ASSERT( Stack != NULL );
|
||
ASSERT( StackElement != NULL );
|
||
|
||
//
|
||
// Find the stack pointer and make sure that the signature is still
|
||
// valid
|
||
//
|
||
localStack = *Stack;
|
||
ASSERT( localStack->Signature == STACK_SIGNATURE );
|
||
|
||
//
|
||
// Do we have enough space on the stack?
|
||
//
|
||
if ( localStack->TopOfStack >= localStack->StackSize ) {
|
||
|
||
//
|
||
// Figure out how many bytes by which to grow the stack and how
|
||
// large the total stack should be
|
||
//
|
||
deltaSize = (STACK_GROWTH_RATE * localStack->StackElementSize);
|
||
newSize = sizeof(STACK) + localStack->StackSize + deltaSize - 1;
|
||
|
||
//
|
||
// Grow the stack
|
||
//
|
||
tempStack = MEMORY_ALLOCATE( newSize );
|
||
if (tempStack == NULL) {
|
||
|
||
return STATUS_INSUFFICIENT_RESOURCES;
|
||
|
||
}
|
||
|
||
//
|
||
// Empty the new stack and copy the old one to it
|
||
//
|
||
MEMORY_ZERO( &(tempStack->Stack[0]), newSize - sizeof(STACK) + 1);
|
||
MEMORY_COPY( tempStack, localStack , newSize - deltaSize);
|
||
|
||
//
|
||
// Make sure that the new stack has the correct size
|
||
//
|
||
tempStack->StackSize += deltaSize;
|
||
|
||
//
|
||
// Free the old stack
|
||
//
|
||
StackFree( Stack );
|
||
|
||
//
|
||
// Set the stack to point to the new one
|
||
//
|
||
*Stack = localStack = tempStack;
|
||
|
||
}
|
||
|
||
//
|
||
// Grab a pointer to the part that we will return to the caller
|
||
//
|
||
*( (PUCHAR *)StackElement) = &(localStack->Stack[ localStack->TopOfStack ]);
|
||
|
||
//
|
||
// Find the new Top of Stack
|
||
//
|
||
localStack->TopOfStack += localStack->StackElementSize;
|
||
|
||
//
|
||
// Done
|
||
//
|
||
return STATUS_SUCCESS;
|
||
}
|
||
|
||
NTSTATUS
|
||
StackRoot(
|
||
IN OUT PSTACK *Stack,
|
||
OUT PVOID RootElement
|
||
)
|
||
/*++
|
||
|
||
Routine Description:
|
||
|
||
This routine returns the first element on the stack
|
||
|
||
Arguments:
|
||
|
||
Stack - Where the stack is located
|
||
RootElement - Where to store the pointer to the root stack element
|
||
|
||
Return Value:
|
||
|
||
NTSTATUS
|
||
|
||
--*/
|
||
{
|
||
PSTACK localStack;
|
||
|
||
ASSERT( Stack != NULL && *Stack != NULL );
|
||
ASSERT( (*Stack)->Signature == STACK_SIGNATURE );
|
||
|
||
localStack = *Stack;
|
||
if (localStack->TopOfStack < localStack->StackElementSize) {
|
||
|
||
//
|
||
// There is no stack location we can use
|
||
//
|
||
*( (PUCHAR *)RootElement) = NULL;
|
||
return STATUS_UNSUCCESSFUL;
|
||
|
||
}
|
||
|
||
//
|
||
// Grab the root element
|
||
//
|
||
*( (PUCHAR *)RootElement) = localStack->Stack;
|
||
|
||
//
|
||
// Done
|
||
//
|
||
return STATUS_SUCCESS;
|
||
}
|
||
|
||
NTSTATUS
|
||
StackTop(
|
||
IN OUT PSTACK *Stack,
|
||
OUT PVOID TopElement
|
||
)
|
||
/*++
|
||
|
||
Routine Description:
|
||
|
||
This routine returns the topmost stack location that is in current use
|
||
|
||
Arguments:
|
||
|
||
Stack - Where the stack is located
|
||
TopElement - Where to store the pointer to the top stack element
|
||
|
||
Return Value:
|
||
|
||
NTSTATUS
|
||
|
||
--*/
|
||
{
|
||
PSTACK localStack;
|
||
ULONG offset;
|
||
|
||
ASSERT( Stack != NULL );
|
||
ASSERT( (*Stack)->Signature == STACK_SIGNATURE );
|
||
|
||
localStack = *Stack;
|
||
if (localStack->TopOfStack < localStack->StackElementSize) {
|
||
|
||
//
|
||
// No stack locations are in current use
|
||
//
|
||
*( (PUCHAR *)TopElement) = NULL;
|
||
return STATUS_UNSUCCESSFUL;
|
||
|
||
} else {
|
||
|
||
offset = localStack->TopOfStack - localStack->StackElementSize;
|
||
}
|
||
|
||
//
|
||
// Grab the top stack location
|
||
//
|
||
*( (PUCHAR *)TopElement) = &(localStack->Stack[ offset ]);
|
||
|
||
//
|
||
// Done
|
||
//
|
||
return STATUS_SUCCESS;
|
||
}
|