/*++
THIS CODE AND INFORMATION IS PROVIDED "AS IS" WITHOUT WARRANTY OF
ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING BUT NOT LIMITED TO
THE IMPLIED WARRANTIES OF MERCHANTABILITY AND/OR FITNESS FOR A
PARTICULAR PURPOSE.
Copyright (c) 1995-1998  Microsoft Corporation

Module Name:  
    mem.cpp

Abstract:  
    Memory management routines for OHCD driver.
    
Notes: 

--*/

// There are four warnings that I like from Warning level 4.  Since we build
// at warning level 3, I'm setting these four down to level 3 so I still get
// them.
// C4100 unrefrenced formal parameter
// C4101 unrefrenced local variable
// C4705 statement has no effect
// C4706 assignment in conditional
#pragma warning (3 : 4100 4101 4705 4706)

#include <windows.h>
#include <nkintr.h>
#include <ohcdddsi.h>
#include <ceddk.h>

#include "usbtypes.h"
#include "globals.hpp"
#include "mem.hpp"

typedef unsigned long FAR * LPULONG;
typedef LPVOID * LPLPVOID;


//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
CPhysMem::CPhysMem(
    DWORD   cbSize, 
    DWORD   cbHighPrioritySize, 
    PUCHAR  pVirtAddr, 
    PUCHAR  pPhysAddr
    )
{
    PMEMLIST pNode;

    //
    // The PDD can pass in a physical buffer, or we'll try to allocate one from 
    // system RAM.
    //
    if (pVirtAddr && pPhysAddr) 
	{
        DEBUGMSG(ZONE_INIT,(TEXT("DMA buffer passed in from PDD\r\n")));
        m_pPhysicalBufferAddr = pVirtAddr;
        m_dwNormalVA = (DWORD) pVirtAddr;
        m_dwNormalPA = (DWORD) pPhysAddr;
    }
    else 
	{
        DEBUGMSG(ZONE_INIT,(TEXT("Allocating DMA buffer from system RAM\r\n")));
        m_pPhysicalBufferAddr = (PUCHAR)AllocatePhysicalMemory(cbSize,
                                                               &m_dwNormalPA);
        m_dwNormalVA = (DWORD) m_pPhysicalBufferAddr;
    }
    
    m_dwTotalPhysMemSize = cbSize;
    m_PaVaConversion = m_dwNormalPA - m_dwNormalVA;
    
    DEBUGMSG(ZONE_INIT || ZONE_ALLOC,
        (TEXT("OHCD :   Total Alloc Region PhysAddr = 0x%08X, VirtAddr = 0x%08X, size = %d\r\n"),
        m_dwNormalPA, m_dwNormalVA, m_dwTotalPhysMemSize));

    //
    // Set aside a page for the special request.
    //
    m_dwSpecialVA = (DWORD) m_dwNormalVA;
    m_dwSpecialPA = (DWORD) m_dwNormalPA;
    m_dwNormalVA += USBPAGESIZE;
    m_dwNormalPA += USBPAGESIZE;
    cbSize -= USBPAGESIZE;
    m_bSpecialTaken = FALSE;
    memset((PVOID) m_dwSpecialVA, 0x00, USBPAGESIZE);

    DEBUGMSG(ZONE_INIT || ZONE_ALLOC,
        (TEXT("OHCD : Special Alloc Region PhysAddr = 0x%08X, VirtAddr = 0x%08X, size = %d\r\n"),
        m_dwSpecialPA, m_dwSpecialVA, USBPAGESIZE));

    //
    // Set aside the High Priority region.
    //
    m_dwHighPriorityVA = (DWORD) m_dwNormalVA;
    m_dwHighPriorityPA = (DWORD) m_dwNormalPA;
    m_dwNormalVA += cbHighPrioritySize;
    m_dwNormalPA += cbHighPrioritySize;
    cbSize -= cbHighPrioritySize;
    m_dwHighPrioritySize = cbHighPrioritySize;
    memset((PVOID) m_dwHighPriorityVA, 0x00, m_dwHighPrioritySize);

    DEBUGMSG(ZONE_INIT || ZONE_ALLOC,
        (TEXT("OHCD : HighPri Alloc Region PhysAddr = 0x%08X, VirtAddr = 0x%08X, size = %d\r\n"),
        m_dwHighPriorityPA, m_dwHighPriorityVA, m_dwHighPrioritySize));

    //
    // And the rest is for normal allocations.
    //
    m_dwNormalSize = cbSize;
    memset((PVOID) m_dwNormalVA, 0x00, m_dwNormalSize);
    
    DEBUGMSG(ZONE_INIT || ZONE_ALLOC,
        (TEXT("OHCD :  Normal Alloc Region PhysAddr = 0x%08X, VirtAddr = 0x%08X, size = %d\r\n"),
        m_dwNormalPA, m_dwNormalVA, m_dwNormalSize));

    m_hFreeMemEvent = CreateEvent(NULL, TRUE, FALSE, NULL);
    m_fHaveWaited = FALSE;

    InitializeCriticalSection(&m_csLock);
    EnterCriticalSection(&m_csLock);
    //
    // Create dummy entries for the list head (simpler linked list code)
    //
    m_pNodeFreeListHead = CreateNewNode(0, 0, 0);
    InitializeListHead(m_pNodeFreeListHead);

    DEBUGMSG(ZONE_ALLOC, (TEXT("OHCD : Init : NodeFreeListHead = 0x%08X\r\n"),
                          m_pNodeFreeListHead));
    
    m_pFreeListHead = CreateNewNode(0, 0, 0);
    InitializeListHead(m_pFreeListHead);

    m_pInUseListHead = CreateNewNode(0, 0, 0);
    InitializeListHead(m_pInUseListHead);
    
    DEBUGMSG(ZONE_ALLOC, (TEXT("OHCD : Init : FreeListHead = 0x%08X, InUseListHead = 0x%08X\r\n"),
                          m_pFreeListHead, m_pInUseListHead));

    m_pHighPriorityFreeListHead = CreateNewNode(0, 0, 0);
    InitializeListHead(m_pHighPriorityFreeListHead);

    m_pHighPriorityInUseListHead = CreateNewNode(0, 0, 0);
    InitializeListHead(m_pHighPriorityInUseListHead);

    DEBUGMSG(ZONE_ALLOC, (TEXT("OHCD : Init : HighPriFreeListHead = 0x%08X, HighPriInUseListHead = 0x%08X\r\n"),
                          m_pHighPriorityFreeListHead, m_pHighPriorityInUseListHead));
    
    //
    // One big chunk on the free list to start things off.
    //
    pNode = CreateNewNode(m_dwNormalSize, m_dwNormalVA, m_dwNormalPA);
    
    DEBUGMSG(ZONE_ALLOC, (TEXT("OHCD : Init : Main Free Heap Node = 0x%08X\r\n"),
                          pNode));
    
    InsertNodeBefore(pNode, FirstNode(m_pFreeListHead));

    VALIDATE_HEAPS(FALSE);
    
    //
    // Same thing for High Priority Region
    //
    pNode = CreateNewNode(m_dwHighPrioritySize, m_dwHighPriorityVA, m_dwHighPriorityPA);
    
    DEBUGMSG(ZONE_ALLOC, (TEXT("OHCD : Init : HighPri Free Heap Node = 0x%08X\r\n"),
                          pNode));
    
    InsertNodeBefore(pNode, FirstNode(m_pHighPriorityFreeListHead));
    
    VALIDATE_HEAPS(TRUE);

    LeaveCriticalSection(&m_csLock);
}


//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
#ifdef DEBUG
BOOL
CPhysMem::ValidateHeaps(BOOL fHighPri)
{
    PMEMLIST pNode = FirstNode(FREELIST(fHighPri));
    DWORD dwSizeTotal = 0;
    DWORD dwSizePrev = 0;
    DWORD dwSizeFree = 0;
    DWORD dwNodesFree = 0;

    while (!EndOfList(FREELIST(fHighPri), pNode)) {
        
        DEBUGMSG(ZONE_VERBOSE && ZONE_ALLOC, (TEXT("FL : pNode = 0x%08X, size = %4d, VA = 0x%08X\r\n"),
                              pNode, pNode->dwSize, pNode->dwVirtAddr));

        dwSizeTotal += pNode->dwSize;
        dwSizeFree  += pNode->dwSize;
        
        if (dwSizePrev > pNode->dwSize) {
            DEBUGMSG(1, (TEXT("OHCD : ValidateHeaps : Free List not sorted (%d > %d)\r\n"), 
                         dwSizePrev, pNode->dwSize));
            DEBUGCHK(0);
            return(FALSE);
        }

        if ((pNode->next->prev != pNode) || (pNode->prev->next != pNode)) {
            DEBUGMSG(1, (TEXT("OHCD : ValidateHeaps : Invalid linked list (free)\r\n")));
            DEBUGCHK(0);
            return(FALSE);
        }

        dwSizePrev = pNode->dwSize;
        pNode = pNode->next;
    }
    
    pNode = FirstNode(INUSELIST(fHighPri));

    while (!EndOfList(INUSELIST(fHighPri), pNode)) {
        
        DEBUGMSG(ZONE_VERBOSE && ZONE_ALLOC, (TEXT("IL : pNode = 0x%08X, size = %4d, VA = 0x%08X\r\n"),
                              pNode, pNode->dwSize, pNode->dwVirtAddr));

        dwSizeTotal += pNode->dwSize;
        
        if ((pNode->next->prev != pNode) || (pNode->prev->next != pNode)) {
            DEBUGMSG(1, (TEXT("OHCD : ValidateHeaps : Invalid linked list (inuse)\r\n")));
            DEBUGCHK(0);
            return(FALSE);
        }

        pNode = pNode->next;
    }
    
    DEBUGMSG(ZONE_VERBOSE, (TEXT("OHCD : ValidateHeaps : FreeSize = %d bytes; TotalSize = %d bytes\r\n"),
                          dwSizeFree, dwSizeTotal));

    if (dwSizeTotal != (fHighPri ? m_dwHighPrioritySize : m_dwNormalSize)) {
        DEBUGMSG(1, (TEXT("OHCD : ValidateHeaps : We've lost some memory somewhere\r\n")));
        DEBUGCHK(0);
        return(FALSE);
    }
    
    //
    // Validate the NODES free list.
    //
    pNode = FirstNode(m_pNodeFreeListHead);
    while (!EndOfList(m_pNodeFreeListHead, pNode)) {
        
        DEBUGMSG(ZONE_VERBOSE && ZONE_ALLOC, (TEXT("FL : pNode = 0x%08X, size = %4d, VA = 0x%08X\r\n"),
                              pNode, pNode->dwSize, pNode->dwVirtAddr));
        dwNodesFree++;
        
        if ((pNode->next->prev != pNode) || (pNode->prev->next != pNode)) {
            DEBUGMSG(1, (TEXT("OHCD : ValidateHeaps : Invalid linked list (nodefree)\r\n")));
            DEBUGCHK(0);
            return(FALSE);
        }
        pNode = pNode->next;
    }
    DEBUGMSG(ZONE_VERBOSE, (TEXT("OHCD : ValidateHeaps : Nodes Free = %d\r\n"),dwNodesFree));
    
    return (TRUE);
}
#endif


//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
PMEMLIST 
CPhysMem::CreateNewNode(
    DWORD   dwSize,
    DWORD   dwVirtAddr,
    DWORD   dwPhysAddr
    )
{
    PMEMLIST pNode;
    //
    // If we already have a node allocated and sitting around, use it.
    //
    if ((dwSize == 0) || IsListEmpty(m_pNodeFreeListHead)) {
        pNode = (PMEMLIST) OHCD_Alloc(LPTR, sizeof(MEMLIST));
    } else {
        pNode = FirstNode(m_pNodeFreeListHead);
        RemoveNode(pNode);
    }

    if (pNode != NULL) {
        pNode->dwVirtAddr = dwVirtAddr;
        pNode->dwPhysAddr = dwPhysAddr;
        pNode->dwSize = dwSize;
        pNode->next = NULL;
        pNode->prev = NULL;
    }
    
    return (pNode);
}



//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
EError
CPhysMem::DeleteNode(
    PMEMLIST pNode
    )
{
    //
    // We don't actually delete any of the nodes. We just keep them on our
    // free list to use later. Keeps us from thrashing on the heap.
    //
    InsertNodeBefore(pNode, FirstNode(m_pNodeFreeListHead));
    return(successful);
}



//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
PMEMLIST 
CPhysMem::FindFreeBlock(
    DWORD   dwSize,
    BOOL    fHighPri
    )
{
    //
    // The free list is sorted by increasing block sizes, so just find the 
    // first block that's at least DWSIZE big.
    //
    PMEMLIST pNode = FirstNode(FREELIST(fHighPri));
    
    while (!EndOfList(FREELIST(fHighPri), pNode)) {
        if (dwSize <= pNode->dwSize) {
            RemoveNode(pNode);
            return (pNode);
        }
        pNode = pNode->next;
    }
    
    return (NULL);
}



//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
EError
CPhysMem::AddNodeToFreeList(
    PMEMLIST pNode,
    BOOL     fHighPri
    )
{
    //
    // The free list is sorted by increasing block sizes, not by increasing
    // address so we must scan the list for any possible connecting free blocks,
    // and then coalesce them into a single free block. There will be at most
    // two blocks to find (one on either end) so scan for both of them.
    //
    PMEMLIST pNodeTraverse = FirstNode(FREELIST(fHighPri));
    
    PMEMLIST pNodePrevious = NULL; // Points to the previous connecting free block
    PMEMLIST pNodeNext = NULL;     // Points to the next connecting free block
    //
    // The endpoints that we are trying to match up to.
    //
    DWORD dwThisPA = pNode->dwPhysAddr;
    DWORD dwNextPA = MEMLIST_NEXT_PA(pNode);

    //
    // Walk the list looking for blocks that are next to this one.
    //
    while (!EndOfList(FREELIST(fHighPri), pNodeTraverse)) {

        if (dwThisPA == MEMLIST_NEXT_PA(pNodeTraverse)) {
            //
            // We've found the block just ahead of this one. Remember it.
            //
            pNodePrevious = pNodeTraverse;

        } else if (dwNextPA == pNodeTraverse->dwPhysAddr) {
            //
            // We've found the block just after of this one.
            //
            pNodeNext = pNodeTraverse;
        }

        if ((pNodePrevious == NULL) || (pNodeNext == NULL)) {
            //
            // We haven't connected both ends, so keep on looking...
            //
            pNodeTraverse = pNodeTraverse->next;
        } else {
            //
            // We've found blocks to connect on both ends, let's get on with it.
            //
            break;
        }
    }
    

    if (pNodePrevious != NULL) {
        //
        // Combine with the previous block.
        //
        RemoveNode(pNodePrevious);
        //
        // Grow pNode to hold both.
        //
        pNode->dwSize = pNode->dwSize + pNodePrevious->dwSize;
        pNode->dwVirtAddr = pNodePrevious->dwVirtAddr;
        pNode->dwPhysAddr = pNodePrevious->dwPhysAddr;
        DeleteNode(pNodePrevious);
    }

    if (pNodeNext != NULL) {
        //
        // Combine with the next block.
        //
        RemoveNode(pNodeNext);
        //
        // Grow pNode to hold both.
        //
        pNode->dwSize = pNode->dwSize + pNodeNext->dwSize;
        DeleteNode(pNodeNext);
    }

    //
    // Add pNode to the free list in sorted size order.
    //
    pNodeTraverse = FirstNode(FREELIST(fHighPri));
    
    while (!EndOfList(FREELIST(fHighPri), pNodeTraverse)) {

        if (pNode->dwSize <= pNodeTraverse->dwSize) {
            break;
        }
        pNodeTraverse = pNodeTraverse->next;
    }

    //
    // Insert this node before the traverse node.
    //
    InsertNodeBefore(pNode, pNodeTraverse);

    return (successful);
}