blockalloc.c

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

/**
 * BlockAlloc.c
 * Contains functions that keep track of available blocks and
 *   garbage blocks.  It maintains an available block FIFO
 *   in the form of a linked list of CELL_TABLE_ENTRY's.
 *   It also keeps an array containing the number of garbage
 *   blocks in each sector.
 * Determines which sector is the best sector to erase for a
 *   cleanup.
 *
 * BlockAlloc functions are to be initialized and used by
 *   CellTable functions only.
 *
 * 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_BlockAllocInitialize() is called at the beginning of
 *     the flash initialization process.  At this time the memory
 *     and data structures are allocated and initialized.
 *   dms_BlockAddAvailable() and dms_BlockIncrememtGarbageCount()
 *     are called for each block found in each sector durring a 
 *     dms_SectorInitialize() (Through CellTable).
 *   At the end of initialization dms_BlockAllocComputeMinimum-
 *     AllowableBlocksFree() is called with the needed cell
 *     information that was collected by CellInfo.
 *   Durring a block write dms_BlockAlloc() is called to get a
 *     CELL_TABLE_ENTRY to the next available cell.  If the
 *     number of free blocks are less than the computed allowable
 *     minimum the the function returns NULL.  At this time
 *     a cleanup should be called.
 *   The cleanup operation uses dms_BlockGetBestSectorToErase() to
 *     determine which sector to erase.  This function also deletes
 *     all blocks in the  available block list which belong to that
 *     sector and clears the garbage count for that sector. 
 *   Durring a cleanup dms_BlockAllocNoMinimum() is used to get
 *     available blocks for moving blocks out of old sectors.
 *   dms_BlockFree() is called for each old block it frees the 
 *     CELL_TABLE_ENTRY memory and increments the garbage count
 *     for the sector of the block.
 *   dms_BlockAllocFinalize() is called durring a shutdown.  It
 *     frees all dynamic memory used by these functions.
 */

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

/* localy used variables */
static CELL_TABLE_ENTRY *lpAvailableBlockList = NULL;     /* pointer to the head of the list */
static CELL_TABLE_ENTRY **lpAvailableBlockListEnd = NULL; /* pointer to the pointer (*pNext)      */
                                                          /* of the last node for quick additions */
                                                          /* to end of list                       */
static WORD lwAvailableBlockListSize;
static WORD *lwSectorGarbageBlockCountList = NULL;
static WORD lwSectorGarbageBlockCountListSize;
static WORD lwMinimumAllowableBlocksFree;

/* localy used functions */
void dms_lBlockAllocRemoveAvailableInSector(WORD awSectorIndex);

/**
 * dms_BlockAllocInitialize()
 * Must be called before any other functions in these file.
 * Creates and initializes memory for lwSectorGarbageBlockCountList.
 * Does not have any requirements of predefined/calculated globals.
 *
 * Prerequisites:
 *   None. 
 * Uses:
 *   malloc()
 * Used By:
 *   dms_CellTableInitialize()
 *   
 */
DMS_STATUS dms_BlockAllocInitialize(WORD awSectorCount){
  WORD wIndex;
   
  /* This will free existing memory if any */
  dms_BlockAllocFinalize();

  /* Initialize AvailableBlockList */
  lpAvailableBlockList = NULL;
  lwAvailableBlockListSize = 0;
  lpAvailableBlockListEnd = &lpAvailableBlockList; /* the first added not will be added to the head */

  /* Create array */
  lwSectorGarbageBlockCountList = (WORD*)malloc(sizeof(WORD) * awSectorCount);
  if (lwSectorGarbageBlockCountList == NULL) {
    return Out_Of_Memory_Error;
  }
  /* Initialize array */
  for (wIndex = 0; wIndex < awSectorCount; wIndex++){
    lwSectorGarbageBlockCountList[wIndex] = 0;
  }
  lwSectorGarbageBlockCountListSize = awSectorCount;

  /*
   * Set minimum allowable free data blocks to MAX_WORD.
   * It will be computed later when the largest cell size is known.
   */
  lwMinimumAllowableBlocksFree = MAX_WORD;

  return No_Error;
}

/**
 * dms_BlockAllocComputeMinimumAllowableBlocksFree()
 * This must be called before dms_BlockAlloc() is called otherwise 
 *   dms_BlockAlloc will always return NULL because
 *   lwMinimumAllowableBlocksFree will be set to MAX_WORD 0xFFFF.
 * Computes the value of the minimum allowable blocks free and stores
 *   it in a file local variable to be used by dms_BlockAlloc().
 * 
 * Returns:
 *   The computed value of the minimum allowable blocks free.
 * Prerequisites:
 *   dms_BlockAllocInitialize() 
 * Uses:
 *   Nothing other than provided arguments.
 * Used By:
 *   dms_CellTableCheckValidity()
 *   
 */
WORD dms_BlockAllocComputeMinimumAllowableBlocksFree(WORD awLargestSectorBlockCount, WORD awLargestCellBlockCount){
  /* compute the minimum allowable free data blocks */
  return lwMinimumAllowableBlocksFree = (WORD) (awLargestSectorBlockCount + 1);
}

/**
 * dms_BlockAlloc()
 * Gets pointer to next available block.
 * The block returned is the oldest block in the list.  ie. FIFO.
 * Returns NULL if number of available blocks less than or equal
 *   to minimum allowable blocks.
 *
 * Prerequisites:
 *   dms_BlockAllocInitialize() 
 *   dms_BlockAllocComputeMinumumAllowableBlocksFree() 
 * Uses:
 *   Nothing outside this file.
 *   dms_BlockAllocNoMinimum()
 * Used By:
 *   dms_CellTableCheckValidity()
 */
CELL_TABLE_ENTRY *dms_BlockAlloc(void){
  if (dms_BlockAllocIsAvailable()){ 
    return dms_BlockAllocNoMinimum();
  } else {
    return NULL;
  }
}

/**
 * dms_BlockAllocIsAvailable()
 * Returns non-zero if the number of available blocks is above the minimum
 *   allowable free blocks.
 * 
 * Prerequisites:
 *   dms_BlockAllocInitialize() 
 *   dms_BlockAllocComputeMinumumAllowableBlocksFree() 
 * Uses:
 *   Nothing outside this file.
 * Used By:
 *   dms_CellTableIsBlockAvailable()
 */
BYTE dms_BlockAllocIsAvailable(void){
  return ((BYTE) (lwAvailableBlockListSize > lwMinimumAllowableBlocksFree));
}

/**
 * dms_BlockAllocNoMinimum()
 * Returns a pointer to an available block and deletes the
 *   block from the available list.
 * The block returned is the oldest block in the list.  ie. FIFO.
 *   Blocks are inserted at the end of the list by dms_BlockAddAvailable()
 *   and removed from the front of the list.
 * This function is intended to be called ONLY by cleanup 
 *   while moving blocks to erase a sector.
 *
 * Prerequisites:
 *   dms_BlockAllocInitialize() 
 * Uses:
 *   Nothing outside this file.
 * Used By:
 *   dms_CellTableMoveBlock()
 *   dms_BlockAlloc()
 */
CELL_TABLE_ENTRY *dms_BlockAllocNoMinimum(void){
  CELL_TABLE_ENTRY *pBlockNode;
  /* Check if list is empty */
  if (lpAvailableBlockList == NULL) {
    return NULL;
  }
  /* Allocate first block in list */
  pBlockNode = lpAvailableBlockList; 
  lpAvailableBlockList = lpAvailableBlockList->pNext;
  pBlockNode->pNext = NULL;
  lwAvailableBlockListSize--;

  /* If the last block was taken then lpAvailableBlockListEnd must be set to  */
  /* the address of lpAvailableBlockList so that BlockAddAvailable() will */
  /* add the next block correctly */
  if (lpAvailableBlockList == NULL) {
    lpAvailableBlockListEnd = &lpAvailableBlockList;
  }
  return pBlockNode;
}

/**
 * dms_BlockFree()
 * Increments the garbage block count in the sector containing the
 * block and then frees the memory used by the CELL_TABLE_ENTRY.
 *
 * Prerequisites:
 *   dms_BlockAllocInitialize() 
 * Uses:
 *   dms_BlockIncrementGarbageCount()
 *   free()
 * Used By:
 *   dms_CellTableDeleteCellInProcess()
 *   dms_CellTableDeleteBlockInProcess()
 */
void dms_BlockFree(CELL_TABLE_ENTRY *apBlockEntry){
  if (apBlockEntry != NULL){
    dms_BlockIncrementGarbageCount(apBlockEntry->wSectorIndex);
    free(apBlockEntry);
  }
} 

/**
 * dms_BlockIncrementGarbageCount()
 * Increments the garbage block count in the sector.
 *
 * Prerequisites:
 *   dms_BlockAllocInitialize() 
 * Uses:
 *   Nothing outside this file.
 * Used By:
 *   dms_CellTableAddGarbageBlock()
 */
void dms_BlockIncrementGarbageCount(WORD awSectorIndex){
  lwSectorGarbageBlockCountList[awSectorIndex]++;
} 

/**
 * dms_BlockAddAvailable()
 * Allocates memory for new CELL_TABLE_ENTRY structure
 *   and adds to list of available to be used by BlockAlloc().
 * NOTE: This function is to be called durring a sector initialize.
 *
 * Prerequisites:
 *   dms_BlockAllocInitialize() 
 * Uses:
 *   malloc()
 * Used By:
 *   dms_CellTableAddAvailableBlock()
 */
DMS_STATUS dms_BlockAddAvailable(WORD awSectorIndex, WORD awSectorBlockIndex){
  CELL_TABLE_ENTRY *pNewEntry;

  pNewEntry = (CELL_TABLE_ENTRY*) malloc(sizeof(CELL_TABLE_ENTRY));				
  if (pNewEntry == NULL) {
    return Out_Of_Memory_Error; 
  }
  /* Initialize structure */
  pNewEntry->wBlockIndex = 0;
  pNewEntry->bCellStatus = CellErase;
  pNewEntry->wSectorIndex = awSectorIndex;
  pNewEntry->wSectorBlockIndex = awSectorBlockIndex;
  pNewEntry->pNext = NULL;
  /* Add block to end of list */
  *lpAvailableBlockListEnd = pNewEntry;
  lpAvailableBlockListEnd = &(pNewEntry->pNext);
  lwAvailableBlockListSize++;
  return No_Error;
}


/**
 * dms_BlockGetBestSectorToErase()
 * Chooses which sector should be erased for a cleanup.
 * Also assumes that the sector is getting erased and 
 *   calls dms_BlockAllocRemoveAvailableInSector and
 *   zeros out the garbage block count for that sector.
 *
 * Returns:
 *   No_Garbage_Blocks if all sector are clean and have no
 *     dirty blocks.
 *   No_Error if it has sector to erase and assignes the
 *     sector number to apwSectorIndex.
 * Prerequisites:
 *   dms_BlockAllocInitialize() 
 *   dms_SectorInfoDefineArchitecture()
 * Uses:
 *   dms_BlockAllocRemoveAvailableInSector()
     dms_SectorInfoGetBlockCount()
 * Used By:
 *   dms_CellTableGetBestSectorToErase()
 */
DMS_STATUS dms_BlockGetBestSectorToErase(WORD *apwSectorIndex){
  static WORD wSectorOffset = 0;
  WORD wSectorIndex, wIndex;
  WORD wLargestSectorIndex;
  WORD wLargestGarbageCount;
  /*
   * The best sector is the first one with the most
   * garbage blocks or the last one with all garbage blocks.
   * The search starts at the sSectorOffset'th sector and
   *   wSectorOffset is incremented each time this function
   *   is called.  This will allow for better distribution
   *   of sector erases for all sectors in the system.
   */
  wLargestSectorIndex = 0;
  wLargestGarbageCount = 0;
  for (wIndex = 0; wIndex < lwSectorGarbageBlockCountListSize; wIndex++){
    wSectorIndex = (WORD)((wIndex + wSectorOffset) % lwSectorGarbageBlockCountListSize);
    if (lwSectorGarbageBlockCountList[wSectorIndex] == dms_SectorInfoGetBlockCount(wSectorIndex)){
      wLargestGarbageCount = MAX_WORD;
      wLargestSectorIndex = wSectorIndex;
    } else if (lwSectorGarbageBlockCountList[wSectorIndex] > wLargestGarbageCount){
      wLargestGarbageCount = lwSectorGarbageBlockCountList[wSectorIndex];
      wLargestSectorIndex = wSectorIndex;
    }
  }
  /* Increment the starting sector for the next time */
  wSectorOffset = (WORD)((wSectorOffset + 1) % lwSectorGarbageBlockCountListSize);

  if (wLargestGarbageCount == 0) {
    return No_Garbage_Blocks;
  }
  /* remove all available blocks from the list that are in the sector */
  dms_lBlockAllocRemoveAvailableInSector(wLargestSectorIndex);
  /* reset the garbage count to zero */
  lwSectorGarbageBlockCountList[wLargestSectorIndex] = 0;
  /* set the result */
  *apwSectorIndex = wLargestSectorIndex;
  return No_Error; 
}

/**
 * dms_BlockAllocFinalize
 * Must be called when shutting down DMS software.
 * Frees list CELL_TABLE_ENTRY
 *
 * Prerequisites:
 *   None.
 * Uses:
 *   free()
 * Used By:
 *   dms_BlockAllocInitialize() 
 *   dms_CellTableInitialize()
 *   dms_CellTableFinalize()
 */
DMS_STATUS dms_BlockAllocFinalize(void){
  CELL_TABLE_ENTRY *pTmpEntry;
  if (lwSectorGarbageBlockCountList != NULL){
    free(lwSectorGarbageBlockCountList);
  }
  lwSectorGarbageBlockCountList = NULL;
  while (lpAvailableBlockList != NULL){
    pTmpEntry = lpAvailableBlockList;
    lpAvailableBlockList = lpAvailableBlockList->pNext;
    free(pTmpEntry);
  }
  lpAvailableBlockList = NULL;
  lpAvailableBlockListEnd = NULL;
  lwMinimumAllowableBlocksFree = MAX_WORD;
  return No_Error;
}

/**
 * dms_lBlockAllocRemoveAvailableInSector()
 * Traverses through the list and removes the entry whose wBlockIndex
 *   matches the provided awSectorIndex.
 *
 * Prerequisites:
 *   dms_BlockAllocInitialize() 
 * Uses:
 *   Nothing outside this file.
 * Used By:
 *   dms_BlockGetBestSectorToErase();
 */
void dms_lBlockAllocRemoveAvailableInSector(WORD awSectorIndex){
  CELL_TABLE_ENTRY **ppCell;
  CELL_TABLE_ENTRY *pTmpEntry;
  CELL_TABLE_ENTRY **pLastEntry = &lpAvailableBlockList;
  ppCell = &lpAvailableBlockList;
  while (*ppCell != NULL){
    if ((*ppCell)->wSectorIndex == awSectorIndex){
      pTmpEntry = (*ppCell);
      (*ppCell) = (*ppCell)->pNext;
      free(pTmpEntry);
      lwAvailableBlockListSize--;
    } else {
      /*
       *  Keep a pointer to the pNext of the last undeleted block in the list.
       */
      ppCell = &((*ppCell)->pNext);
      pLastEntry = ppCell;
    }
  }
  lpAvailableBlockListEnd = pLastEntry;
}