celltable.c

AMD公司官方版FLASH文件系统。有详细说明文档和Windows仿真测试环境。

/**
 * CellTable.c
 * Defines functions that keep track of the blocks in each cell.
 * The CellTable is a RAM based lookup table that is used for 
 *   finding the sector locations of each block in each cell.
 * Each CELL_TABLE_ELEMENT contains the block index, cell status,
 *   sector index, sector block index and pointer to the next block.
 *   Total of 12-bytes per block.
 *
 * CellTable is used at Initialization, Writing, Reading, and Cleanup.
 * CellTable uses BlockAlloc and CellInfo.  All functionality of 
 *   BlockAlloc and CellInfo is accessed by others through CellTable.
 *
 * Functions in this file do not read or write to the flash
 *   they only organize and store the data given to them.
 *
 * Usage is a follows:
 * dms_Initialize:
 *     dms_CellTableInitialize() is called at the beginning of the DMS
 *     initialization process.  It initializes BlockAlloc and CellInfo
 *     along with creating the empty cell table.
 *   Next dms_CellTableAddBlock(), dms_CellTableAddAvailableBlock(),
 *     or dms_CellTableAddGarbageBlock() are called called for each
 *     block in the device architecture.  This is done by 
 *     dms_SectorInitialize().
 *   Once all blocks have been read and added to the CellTable, 
 *     AvailableBlockList, or SectorGarbageCount, then 
 *     dms_CellTableCheckValidity() is called to check the basic integerity
 *     of each cell.  At this time any cells/blocks that were in process 
 *     when power was lost get separated and put in the InProcess list.
 *     MinimumAllowableBlocksFree is computed based on the sizes of the 
 *     cells and sectors.
 *   dms_CellTableDeleteBlockInProcess() and dms_CellTableDeleteCellInProcess()
 *     is called by dms_CellInitialize() to get the blocks that were InProcess
 *     and mark these blocks as garbage.
 *   At this time initialization of CellTable is complete.
 * dms_Write:
 *   For writing cells dms_CellTableSetCellInProcess is called.  This moves
 *     the CELL_TABLE_ENTRY's out of the CellTable and to the InProcess list.
 *   dms_CellTableGetAvailableBlock() is called for each new block that is
 *     needed.  It will return No_Available_Blocks if there is not enough
 *     free blocks otherwise it will provide the SectorIndex and 
 *     SectorBlockIndex for the  new block and add it to the CellTable.
 *   Once all New blocks have been written then
 *     dms_CellTableDeleteCellInProcess() is repetitively called untill all
 *     blocks in the cell in process (old cell) are deleted form the list and
 *     added to the GarbageCount.  dms_CellTableDeleteCellInProcess() also
 *     provides the SectorIndex and SectorBlockIndex of each block so
 *     BlockErase can be written in the blocks BlockStatus.
 *   dms_CellTableMoveBlock() called during Cleanups to move blocks.  It
 *     removes the specified block from the CellTable or CellInProcessList,
 *     gets a new block using dms_BlockAllocNoMinimum() inserts the new block
 *     in the CellTable or CellInProcessList, and provides the SectorIndex and 
 *     SectorBlockIndex of the new Block.
 * dms_Read:
 *   During a read dms_CellTableResetBlockPointer is called to assign an
 *     internal pointer to the beginning of the specified cell.
 *   dms_CellTableGetNextBlock() is repetitively called and provides the
 *     SectorIndex and SectorBlockIndex for each block in the cell.
 * dms_Shutdown:
 *   dms_CellTableFinalize() frees all blocks in the CellTable, CellInProcess,
 *     and BlockInProcess lists.  it also calles dms_CellInfoFinalize() and
 *     dms_BlockAllocFinalize().
 * 
 */

#include "CellTable.h"
#include "CellInfo.h"
#include "BlockAlloc.h"
#include "SectorInfo.h"
#include <malloc.h>

/* Locally used variables */
static CELL_TABLE_ENTRY **lpCellTable = NULL;
static CELL_TABLE_ENTRY *lpCellInProcess = NULL;
static CELL_TABLE_ENTRY *lpBlockInProcess = NULL;
static CELL_TABLE_ENTRY *lpCurrentBlockPointer = NULL;
static WORD lwCellIndexOfCellInProcess;
static WORD lwCellIndexOfBlockInProcess;

/*
 * Functions local to this file only.
 * Not to be used outside this file.
 */
DMS_STATUS dms_lCellTableInsertBlock(CELL_TABLE_ENTRY **ppFirstCell,CELL_TABLE_ENTRY *pNewEntry);
CELL_TABLE_ENTRY *dms_lCellTableCreateNewEntry(WORD awBlockIndex,
                                               BYTE abCellStatus,
                                               WORD awSectorIndex,
                                               WORD awSectorBlockIndex);
DMS_STATUS dms_lCellTableCountAndCheckBlocks(CELL_TABLE_ENTRY *apCellTable, WORD *apwBlockCount);
CELL_TABLE_ENTRY *dms_lCellTableRemoveBlock(CELL_TABLE_ENTRY **appCell, WORD awBlockIndex);
CELL_TABLE_ENTRY *dms_lCellTableRemoveExactBlock(CELL_TABLE_ENTRY **appCell, 
                                                 WORD awSectorIndex, 
                                                 WORD awSectorBlockIndex);
void dms_lCellTableCheckCellInProcess(void);

/**
 * dms_CellTableInitialize()
 * Prepares the cell table for storing blocks.
 * Initializes CellInfo and BlockAlloc
 * 
 * Prerequisites:
 *   dms_SectorInfoDefineArchitecture()
 * Uses:
 *   dms_CellInfoDefineCellCount()
 *   dms_CellInfoFinalize()
 *   dms_BlockAllocInitialize()
 *   dms_BlockAllocFinalize()
 *   dms_SectorInfoGetCount()
 *   dms_CellTableFinalize()
 *   malloc()
 * Used By:
 *   dms_CellInitialize()
 */
DMS_STATUS dms_CellTableInitialize(WORD awCellCount){
  DMS_STATUS eStatus;
  WORD wCellIndex;

  if (lpCellTable != NULL)  dms_CellTableFinalize();

  eStatus = dms_CellInfoDefineCellCount(awCellCount);
  if (eStatus != No_Error) {
    return eStatus;
  }

  eStatus = dms_BlockAllocInitialize(dms_SectorInfoGetCount());
  if (eStatus != No_Error){
    dms_CellInfoFinalize();
    return eStatus; 
  }

  lpCellTable = (CELL_TABLE_ENTRY**) malloc(sizeof(CELL_TABLE_ENTRY*) * awCellCount);
  if (lpCellTable == NULL) {
    dms_CellInfoFinalize();
    dms_BlockAllocFinalize();
    return Out_Of_Memory_Error;
  }

  /* Initialize the array */
  for (wCellIndex = 0; wCellIndex < awCellCount; wCellIndex++){
    lpCellTable[wCellIndex] = NULL;
  }

  lpCellInProcess = NULL;
  lpBlockInProcess = NULL;
  lpCurrentBlockPointer = NULL;

  return No_Error;
}

/**
 * dms_CellTableFinalize()
 * Frees memory used by CellTable and finalizes CellInfo and BlockAlloc.
 * This deletes all blocks in cell table.
 * This function also Finalizes CellInfo and BlockAlloc
 *
 * Prerequisites:
 *   dms_CellInfoDefineCellCount()
 *   NOTE: It is ok to call dms_CellTableFinalize() without CellInfo
 *     being initialized only if CellTable is also not initialized.
 *     dms_CellInfoGetCount() is needed to delete the CellTable.
 *     Repeated calles to dms_CellTableFinalize() is ok because the
 *     second time lpCellTable will equal NULL and dms_CellInfoGetCount()
 *     will not be needed.
 * Uses:
 *   dms_CellInfoGetCount()
 *   dms_CellInfoFinalize()
 *   dms_BlockAllocFinalize()
 * Used By:
 *   dms_CellTableInitialize()
 *   dms_CellInitialize ()
 *   dms_CellFinalize()
 */
void dms_CellTableFinalize(void){
  WORD wCellCount;
  WORD wCellIndex;
  CELL_TABLE_ENTRY *pTmpEntry;
  CELL_TABLE_ENTRY *pListEntry;

  /* Delete cell table */
  if (lpCellTable != NULL){
    wCellCount = dms_CellInfoGetCount();
    for (wCellIndex = 0; wCellIndex < wCellCount; wCellIndex++){
      pListEntry = lpCellTable[wCellIndex];
      /* delete all blocks in cell. */
      while (pListEntry != NULL){
        pTmpEntry = pListEntry->pNext;
        free(pListEntry);
        pListEntry = pTmpEntry;
      }
    }
    free(lpCellTable);
	lpCellTable = NULL;
  }
  /* delete all entries in cell in process */
  if (lpCellInProcess != NULL){
    pListEntry = lpCellInProcess;
    /* delete all blocks in cell. */
    while (pListEntry != NULL){
      pTmpEntry = pListEntry->pNext;
      free(pListEntry);
      pListEntry = pTmpEntry;
    }
	lpCellInProcess = NULL;
  }
  /* delete block in process */
  if (lpBlockInProcess != NULL){
    free(lpBlockInProcess);
    lpBlockInProcess = NULL; 
  }
  /*
   * Shut down other utilities that were started
   *   in dms_CellTableInitialize()
   */ 
  dms_CellInfoFinalize();
  dms_BlockAllocFinalize();
}

/**
 * dms_CellTableAddBlock
 * This function is only to be used when initializing the CellTable.
 * This function tries to add the block to the appropriate cell in the
 *   CellTable. If it cannot due to an existing block with the same BlockIndex
 *   then it tries to put the block in the CellInProcess list.  If that
 *   fails then it tries to put the block in the BlockInProcess.  If there 
 *   is already a block in the BlockInProcess then the add block fails and
 *   returns More_Than_Two_Dirty_Cells;
 * The theory is that there can be at most one whole cell in process and a
 *   single block from any cell (including the cell in process) in process.
 * There could be one or many cells that have a mix of CellValid1 and
 *   CellValid2 cell statuses.  This can be caused by loosing power while
 *   the dms was in process of changing cell statuses of a cell that is about
 *   ready to be written.  This mix of cell statuses will stay until a write
 *   is preformed on that cell.  At which time the cell statuses of the old
 *   cell will be all changed to CellValid2 and then be deleted upon completion
 *   of writing the new cell which will be set to CellValid1.
 * At the completion of adding all the blocks if there is a cell in process 
 *   then the blocks in this cell could be and probably are mixed.  i.e. some
 *   of the cells in lpCellTable[lwCellIndexOfCellInProcess] will have blocks
 *   with both CellValid1 and CellValid2 and so will the blocks on
 *   lpCellInProcess.  These blocks will be sorted and put together when
 *   dms_CellTableCheckValidity() is called.
 *
 * Prerequisites:
 *   dms_CellTableInitialize()
 * Uses:
 *   dms_lCellTableCreateNewEntry()
 *   dms_lCellTableInsertBlock()
 *   free()
 * Used By:
 *   dms_SectorInitialize()
 */
DMS_STATUS dms_CellTableAddBlock(WORD awCellIndex, 
                                 WORD awBlockIndex, 
                                 BYTE abCellStatus, 
                                 WORD awSectorIndex, 
                                 WORD awSectorBlockIndex){
  DMS_STATUS eStatus;
  CELL_TABLE_ENTRY *pTmpEntry;

  /* All cells that enter the CellTable must have a Valid status */
  if (abCellStatus != CellValid1 && abCellStatus != CellValid2) {
    return Invalid_Cell_Status;
  }
  pTmpEntry = dms_lCellTableCreateNewEntry(awBlockIndex,abCellStatus,awSectorIndex,awSectorBlockIndex);
  if (pTmpEntry == NULL) return Out_Of_Memory_Error;
  eStatus = dms_lCellTableInsertBlock(&lpCellTable[awCellIndex],pTmpEntry);
  if (eStatus == Duplicate_Block) {
    if (lpCellInProcess == NULL || lwCellIndexOfCellInProcess == awCellIndex) {
      /* try adding block to CellInProcess */
      eStatus = dms_lCellTableInsertBlock(&lpCellInProcess,pTmpEntry);
      if (eStatus == Duplicate_Block) {
        /*
         * Something is wrong where should not be 3 blocks with the
         *   same block number and all different cell statuses.
         */
        free(pTmpEntry);
        return More_Than_Two_Dirty_Cells;
      } else if (eStatus == Exact_Duplicate_Block) {
        /* try adding block to BlockInProcess */
        if (lpBlockInProcess == NULL){
          lwCellIndexOfBlockInProcess = awCellIndex;
          lpBlockInProcess = pTmpEntry;
        } else {
          free(pTmpEntry);
          return More_Than_Two_Dirty_Cells;
        }
      } else {
        /* block was sucessfully added to CellInProcess */
        lwCellIndexOfCellInProcess = awCellIndex;
      }
    } else {
      /* try adding block to BlockInProcess */
      if (lpBlockInProcess == NULL){
        lwCellIndexOfBlockInProcess = awCellIndex;
        lpBlockInProcess = pTmpEntry;
      } else {
        free(pTmpEntry);
        return More_Than_Two_Dirty_Cells;
      }
    }
  } else if (eStatus == Exact_Duplicate_Block) {
    /*
     * Both block number and cell status are the same.
     * This is a block in process due to a move.
     * Block data SHOULD be the same so one of them can be deleted.
     * For now put this block into the BlockInProcess.  This will