sectormgr.cpp

基于WINCE的文件系统FAL驱动

//
// Copyright (c) Microsoft Corporation.  All rights reserved.
//
//
// Use of this source code is subject to the terms of the Microsoft shared
// source or premium shared source license agreement under which you licensed
// this source code. If you did not accept the terms of the license agreement,
// you are not authorized to use this source code. For the terms of the license,
// please see the license agreement between you and Microsoft or, if applicable,
// see the SOURCE.RTF on your install media or the root of your tools installation.
// THE SOURCE CODE IS PROVIDED "AS IS", WITH NO WARRANTIES.
//
/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
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.

Module Name:    SECTORMGR.C

Abstract:       Sector Manager module

Notes:          The following module is responsible for managing the FREE and
                DIRTY sectors on the FLASH media.

                To store the list of FREE sectors on the media, a form of compression 
                called Consecutive Item Compression (CIC) is used.  CIC is data structure
                that lends itself to data that appears consecutively (a.k.a. a "run" of
                items) but that may have "holes" in it.  A run of data is represented by 
                a node that stores the first number in the run, the last number in the run,
                and a pointer to the next node.  Notice that if we use a DWORD for storing
                the first/last number, a "run" of 2^64 numbers can be represented (assuming
                wrap-around) by using only one node.
                
                As an example, consider the number sequence 

                    0,1,2,3,4,5,6,7,8,12,13,14,15,16,17,18,20,21,400,401,402...1082,23576,etc.  

                In this example, we can see that there are 3 distinct sets of "runs" in the 
                data and 2 holes.  Using CIC, this data stream could be represented as follows:

                     --------------       ---------------       -----------------
                    | firstNum = 0 |     | firstNum = 12 |     | firstNum = 400  |
                    | lastNum  = 8 | --> | lastNum  = 21 | --> | lastNum  = 1082 | --> etc.
                     --------------       ---------------       -----------------

                The *reason* that CIC works so well for representing the FREE sector list
                is because the compactor ALWAYS compacts blocks in consecutive order AND
                frees an entire block of sectors at a time.  Practically, this means that after
                a compaction process a block's worth of sectors can almost always be just added 
                to the last node (the only exception is if BAD blocks occur).  For example, if 
                we suppose that there are 32 sectors in a block (and the blocks are good), then
                the compactor can add a block of FREE sectors to the Sector Manager by just 
                incrementing the lastNum variable in the last node by 32.  Note that no extra
                memory was needed to account for these 32 new FREE sectors.

                Using this argument, one can quickly see that ALL free sectors on the media can
                be represented in CIC by just one node!  That is, no matter how large the underlying
                FLASH media, all of the FREE sectors (barring BAD blocks) can be represented by
                just 12 bytes (the size of one node).  In reality, however, there are typically a few
                BAD blocks on the device (i.e. NAND devices) and a couple of nodes (around 24-36 bytes)
                are needed to represent the FREE sector list.
                
                The last important point to note about CIC is that it allows O(1) insertion and O(1)
                deletion from the FREE sector list.  Again, insertion is simply incrementing the lastNum
                variable of the last node in the list (following the tail pointer) and deletion is simply
                incrementing the firstNum variable in the first node in the list (following the head pointer).
                Note that even if a new node must be allocated (to account for a BAD block), the worst case
                insertion/deletion times are still constant time (a.k.a. O(1)).


-----------------------------------------------------------------------------*/

#include "sectormgr.h"

//------------------------------ GLOBALS -------------------------------------------


extern DWORD g_dwCompactionPrio256;
extern DWORD g_dwCompactionCritPrio256;

//----------------------------------------------------------------------------------

BOOL DirtyList::Init (PFlashRegion pRegion)
{
    m_pRegion = pRegion;
    m_cbDirtyCountEntry = (pRegion->dwSectorsPerBlock > 0xff) ? 2 : 1;    
    
    m_pDirtyList = (LPBYTE) LocalAlloc (LPTR, pRegion->dwNumPhysBlocks * m_cbDirtyCountEntry);

    return (m_pDirtyList != NULL);
}

BOOL DirtyList::Deinit()
{
    LocalFree (m_pDirtyList);
    return TRUE;
}

VOID DirtyList::AddDirtySectors(DWORD dwBlock, DWORD dwNumSectors)
{
    DWORD dwIndex = dwBlock - m_pRegion->dwStartPhysBlock;

//	RETAILMSG(1,(TEXT("AddDirtySectors block:%d numsec:%d\r\n"), dwBlock, dwNumSectors));
    
    if (m_cbDirtyCountEntry == 1)
    {
        m_pDirtyList[dwIndex] += (BYTE)dwNumSectors;
        ASSERT (m_pDirtyList[dwIndex] <= m_pRegion->dwSectorsPerBlock);
    }
    else 
    {
        LPWORD pwList = (LPWORD)m_pDirtyList;
        pwList[dwIndex] += (WORD)dwNumSectors;
        ASSERT (pwList[dwIndex] <= m_pRegion->dwSectorsPerBlock);
    }
}    

BOOL DirtyList::RemoveDirtySectors (DWORD dwBlock, DWORD dwNumSectors)
{
    DWORD dwIndex = dwBlock - m_pRegion->dwStartPhysBlock;
    
//	RETAILMSG(1,(TEXT("RemoveDirtySectors block:%d numsec:%d\r\n"), dwBlock, dwNumSectors));

    if (m_cbDirtyCountEntry == 1)
    {
        if (m_pDirtyList[dwIndex] < (BYTE)dwNumSectors)
        {
            RETAILMSG (1, (TEXT("SectorMgr::UnmarkSectorsAsDirty: Error, Invalid dirty sector count")));
            return FALSE;
        }
        
        m_pDirtyList[dwIndex] -= (BYTE)dwNumSectors;
    }
    else 
    {
        LPWORD pwList = (LPWORD)m_pDirtyList;
        if (pwList[dwIndex] < (WORD)dwNumSectors)
        {
            RETAILMSG (1, (TEXT("SectorMgr::UnmarkSectorsAsDirty: Error, Invalid dirty sector count")));
            return FALSE; 
        }
        
        pwList[dwIndex] -= (WORD)dwNumSectors;
    }
    return TRUE;
}

DWORD DirtyList::GetDirtyCount(BLOCK_ID blockID)
{
    DWORD dwIndex = blockID - m_pRegion->dwStartPhysBlock;
    return (m_cbDirtyCountEntry == 1) ? m_pDirtyList[dwIndex] : ((LPWORD)m_pDirtyList)[dwIndex];          
}


VOID SMList::Init()
{
    m_head = NULL; 
    m_cursor = NULL; 
    m_tail = NULL; 
    m_dwNumSectors = 0;    
}

VOID SMList::Deinit()
{
    //----- 1. Traverse the free sector linked-list and free all the nodes -----
    while(m_head != NULL)
    {
        m_cursor = m_head;                            // Set cursor to front of list
        m_head = m_head->pNext;                       // Advance head pointer

        //----- 2. Free the node.  If LocalFree() fails, just keep going anyway -----
        if(LocalFree(m_cursor) != NULL)
        {
            ReportError((TEXT("FLASHDRV.DLL:DeinitMapper() - Unable to deallocate node!\r\n")));
        }
    }
}

/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Function:       SectorMgr::AddSectorsToList()

Description:    Marks the specified  sectors to the list.

Returns:        Boolean indicating success.
------------------------------------------------------------------------------*/

BOOL SMList::AddSectors (SECTOR_ADDR startingSectorAddr, DWORD dwNumSectors)
{
    static DWORD i = 0;
    
    //----- 1. Can we put these physical sector addresses into the last node in the list? -----
    if((m_tail != NULL) && ((m_tail->lastSectorAddr+1) == startingSectorAddr))
    {
        m_tail->lastSectorAddr += dwNumSectors;
    
    }else
    {
        //----- 2. We can NOT add these physical sector address to the last node, let's create a new node -----
        if((m_cursor = (PSMNode)LocalAlloc(LPTR, sizeof(SMNode))) == NULL)
        {
            ReportError((TEXT("FLASHDRV.DLL:SectorMgr::MarkSectorAsFree() Unable to create node for sector %x!\r\n"), startingSectorAddr+i));
            goto MARK_ERROR;
        }

        //----- 3. Copy in physical sector address -----
        m_cursor->startSectorAddr = startingSectorAddr;
        m_cursor->lastSectorAddr  = (startingSectorAddr + dwNumSectors - 1);
        m_cursor->pNext                   = NULL;

        //----- 4. Add to the end of free sector list -----
        if(m_tail == NULL)
        {
            m_tail = m_cursor;
            m_head = m_cursor;
        }else
        {
            m_tail->pNext = m_cursor;
            m_tail = m_cursor;
        }
    }
    
    //----- 5. Increase the number of free sectors -----
    m_dwNumSectors += dwNumSectors;

    return TRUE;

MARK_ERROR:
    return FALSE;
    
}


DWORD SMList::AreSectorsInList (DWORD dwStartSector, DWORD dwNumSectors)
{
    PSMNode tempNode = m_head;
    DWORD dwEndSector = dwStartSector + dwNumSectors - 1;
    
    while(tempNode != NULL)
    {
        if ((dwStartSector >= tempNode->startSectorAddr) && (dwEndSector <= tempNode->lastSectorAddr))
        {
            return SectorMgr::EntirelyInList;        
        }
        else if ((dwStartSector <= tempNode->lastSectorAddr) && (dwEndSector >= tempNode->startSectorAddr))
        {
            return SectorMgr::PartiallyInList;
        }
        tempNode = tempNode->pNext;
    }

    return SectorMgr::NotInList;
}

/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Function:       SectorMgr::InitSectorManager()

Description:    Initializes the Sector Manager.

Notes:          This function should be called at driver initialization.

Returns:        Boolean indicating success.
------------------------------------------------------------------------------*/
BOOL SectorMgr::Init(PFlashRegion pRegion, Fal* pFal, Compactor* pCompactor)
{
    m_pFal = pFal;
    m_pCompactor = pCompactor;
    m_pRegion = pRegion;
    
    //----- 1. Initialize the free sector linked list -----
    for (int i = 0; i < NUM_LIST_TYPES; i++) {
        m_lists[i].Init();
    }
    //m_freeList.Init();
    //m_readOnlyList.Init();
    //m_XIPList.Init();
   
    //----- 2. Initialize the number of DIRTY sectors -----
    m_dwNumDirtySectors = 0;

    m_dwNumUnusableBlocks = 0;

    //----- 3. Compute the compaction thresholds. -----
    m_dwCritCompactThreshold = 2 * pRegion->dwSectorsPerBlock;

    if (!m_dirtyList.Init(pRegion)) {
        return FALSE;
    }

    return TRUE;
}



/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Function:       SectorMgr::DeinitSectorManager()

Description:    Determines if the specified physical sector is free for use.

Returns:        Boolean indicating success.
------------------------------------------------------------------------------*/
BOOL SectorMgr::Deinit()
{   
    for (int i = 0; i < NUM_LIST_TYPES; i++) {
        m_lists[i].Deinit();
    }