/*++

Copyright (c) 1992  Microsoft Corporation

Module Name:

    suballoc.c

Abstract:

    This module contains code for managing a paritially commited address
    space.  It handles allocation of chunks of memory smaller than the 
    commit granularity.  It commits and decommits memory as needed using
    the supplied function for committing and decommitting memory.  The 
    structures used for tracking the address space are allocated outside
    of the specified addresss space.

Author:

    Dave Hastings (daveh) creation-date 21-Jan-1994
    
Notes:

    Since this package does not actually access memory in the address space
    it is managing, it will work as well with real linear addresses or 
    "Intel Addresses" such as would be encountered with the Insignia Emulator
    on risc.

Revision History:


--*/

//
// Constants
// 

//
// Smallest chunk that will be sub allocated
// 1024 was chosen currently, because that is the
// smallest chunk XMS will allocate.
//
#define SUBALLOC_GRANULARITY        1024

//
// The size of the character array require to hold the 
// bits defining whether the individual allocation entities
// in the commited chunk are allocated or free
//
// BUGBUG Assert that COMMIT_GRANULARITY is a multiple of SUBALLOC_GRANULARITY
//
#define SUBALLOC_BITFIELD_SIZE      COMMIT_GRANULARITY / SUBALLOC_GRANULARITY

//
// Types
//

//
// Routine for committing a specific region of of the address
// space.  Although the return type is NTSTATUS, the only value
// that is checked is 0 (for STATUS_SUCCESS).  If STATUS_SUCCESS
// is returned, it is assumed that the function worked. If not,
// it is assumed that it failed.  No special meaning is attached to
// particular non-zero values.
//
typedef
NTSTATUS 
(*PSACOMMITROUTINE)(
    ULONG BaseAddress,
    ULONG Size
    );

//
// Structure for tracking the address space.  Each chunk of 
// memory of SUBALLOC_GRANULARITY in size is represented by
// a bit.  Each chunk of memory of COMMIT_GRANULARITY is 
// represented by one element of the array of bitfields.
// The FreeCheck array half of the union allows us to check
// whether the entire committed chunk is free more quickly.
//
// ?? Should we add a field to indicate whether the chunk is 
//    committed?  We can always check for all allocated bits
//    zero, and use that as an indication that the chunk is 
//    not committed.
//
// BUGBUG Assert that the bits fit into memory the way we think
// they do.
//
typedef struct _SubAllocation {
    PSACOMMITROUTINE CommitRoutine;
    ULONG BaseAddress;
    ULONG Size;
    union {
        //
        // bitfield with one bit per chunk.  Bit set indicates
        // allocated.  Bit clear indicates free.  All bits 
        // clear indicates un committed
        //
        UINT Allocated[SUBALLOC_BITFIELD_SIZE] : 1;
        //
        // Hopefully a faster way to check all bits.
        //
        UINT FreeCheck[SUBALLOC_BITFIELD_SIZE / sizeof(UINT)];
    } CommitedChunk;
} SUBALLOCATIONDATA, *PSUBALLOCATIONDATA


PVOID
SAInitialize(
    ULONG BaseAddress,
    ULONG Size,
    PSACOMMITROUTINE CommitRoutine
    )
/*++

Routine Description:

    This function performs initialization of the sub allocation package
    for the specified addresss range.  It allocates the data structures
    necessary to track the allocations

Arguments:

    BaseAddress -- Supplies the base address of the address space to
        sub allocate.
    Size -- Supplies the size in bytes of the address space to sub allocate.
    CommitRoutine -- Supplies a pointer to the routine used to commit regions
        of the address space.

Return Value:

    If the function was successful it returns a pointer to the sub-allocation
    data structures.  Otherwise it returns NULL.
    
--*/
{

}

BOOL 
SAQueryFree(
    PVOID SubAllocation,
    PULONG FreeBytes
    )    
/*++

Routine Description:

    This routine returns the number of free bytes in the 
    sub allocated address space.

Arguments:
    
    SubAllocation -- Supplies the pointer returned by SAInitialize
    FreeBytes -- Returns the number of free bytes
   
Return Value:

    TRUE -- if successful, and FreeBytes contains the number of free bytes.
    FALSE otherwise
    
--*/
{

}

BOOL
SAAllocate(
    PVOID SubAllocation,
    ULONG Size,
    PULONG Address
    )
/*++

Routine Description:

    This function allocates a portion of the address space described by 
    SubAllocation.  If necessary, it will commit additional blocks. Address is 
    rounded down to the next lower SUBALLOC_GRANULARITY boundary.
    size is rounded up to the next higher multiple of SUBALLOC_GRANULARITY.

Arguments:

    SubAllocation -- Supplies the pointer returned by SAInitialize.
    Size -- Supplies the size in bytes of the region to allocate.
    Address -- Returns the address of the region allocated.

Return Value:

    TRUE if successful.  If false is returned, no address is returned.
    
Notes:

    Zero is a valid value for the returned address.

--*/
{

}

BOOL
SAFree(
    PVOID SubAllocation,
    ULONG Size,
    ULONG Address
    )
/*++

Routine Description:

    This routine frees a sub-allocated chunk of memory.  If the 
    entire commited block (or blocks) that the specified chunk
    belongs to are free, the chunks are decommitted.  Address is 
    rounded down to the next lower SUBALLOC_GRANULARITY boundary.
    size is rounded up to the next higher multiple of SUBALLOC_GRANULARITY.

Arguments:

    SubAllocation -- Supplies the pointer returned by SAInitialize.
    Size -- Supplies the size in bytes of the region to free.
    Address -- Supplies the address of the region to free.

Return Value:

    TRUE if successful.
    
Notes:

    It is possible to free a different size at a particular 
    address than was allocated.  This will not cause the 
    SubAllocation package any problems.
    
--*/
{

}

BOOL
SAReallocate(
    PVOID SubAllocation,
    ULONG OriginalSize,
    ULONG OriginalAddress,
    ULONG NewSize,
    PULONG NewAddress
    )
/*++

Routine Description:

    This routine reallocates a sub allocated block of memory.
    The sizes are rounded up to the next SUBALLOC_GRANULARITY.
    The Original address is rounded down to the next SUBALLOC_GRANULARITY
    boundary.  Only min(OriginalSize, NewSize) bytes of data are copied to
    the new block.  The block changed in place if possible.

Arguments:

    SubAllocation -- Supplies the pointer returned by SAInitialize.
    OriginalSize -- Supplies the old size in bytes of the block.
    OriginalAddress -- Supplies the old address of the block.
    NewSize -- Supplies the new size in bytes of the block.
    NewAddress -- Returns the new address of the block.

Return Value:

    True if successful.  If unsucessful, no allocation is changed.
    
Notes:

    If the caller does not supply the correct original size for the block,
    some memory may be lost, and the block may be moved unnecessarily.
    
--*/
{

}