structuremanager.c

Nand Flash Translation Layer 用于nandflash的操作。 bad block memory map garbage collection average er

#include "OSModule_MemoryManagement.h"

#include"Common.h"
#include"WearLeveling.h"
#include"HardwareAdaptationLayer.h"
#include"BadBlockManagement.h"
#include"FALUserDirective.h"
#include"StructureManager.h"
#include"LLD.h" 


/************************ DATA STRUCTURE ***********************/


//data structure used to store the translation 

typedef struct M
{
	UINT16 PhysicalBlockNumber1;
	UINT16 PhysicalBlockNumber2;
	UINT8 Info;					//0x00=default,0x01=root,0x02=root+figlio
	UINT8 LastWrite;
}TreeNode;

static UINT16 UsedBlocks = 0;

/* --------------------  Cache --------------------------*/
static SectorMap Cache[MAX_ENTRY_CACHE];
static UINT8 FreeCache[MAX_ENTRY_CACHE] =
{
	0
}; //0 is OS_Free 1 is occuped
static INT32 IndexCache = -1;


/* --------------------  Cache --------------------------*/



/************************ END DATA STRUCTURE ***********************/

NFTL_Return GetSectorOffset(SectorMap Map, UINT8 Sector, UINT8 *OffSet);
NFTL_Return CreateSectorMap(UINT16 PhysicalBlockNumber, SectorMap *Map, UINT8 *LastWrite);
NFTL_Return SetSectorOffset(INT32 Map, UINT8 Sector, UINT8 OffSet);
NFTL_Return CopySectorMapFromCache(SectorMap *Origin, INT32 Destination);


/***********************  GetValidPagePosition **********************************
* Search the valid sector (the last update of sector)in the tree data structure *
* and return the physical position of it			   							*
*----------------------------------------------------------------------------   *
*   Node : is the pointer to the root node of tree data structure   			*
*   Sector: is the sector number to search  		  							*
*	PhysicalBlockNumber:is the physical block where the valid sector is written * 
*	PhysicalPage: is the physical page where the valid sector is written		*
*	Position: indicate the position in the of valid sector						*
*   flag: indicates if this function is called for Read or Write operations 	*
*	return values:																*
*   			PAGENOTFOUND: the sector in not found   					 	*
*				SUCCESS:the sector is founded   		 					 	*
*				FAILURE:the fail is occured 								 	*
*********************************************************************************/
NFTL_Return GetValidPagePosition(void *Node, UINT16 *PhysicalBlockNumber,
	UINT16 *PhysicalPage, UINT8 Sector, UINT8 *Position, UINT8 flag)
{
	UINT8 OffSet;
	UINT16 j=0;
	SectorMap Map, MapTemp;
	NFTL_Return Result;
	INT32 cacheChecked = 0;
	UINT8 LastApp = 0;

	if (flag == WRITE_OPERATION)
	{
		if (((TreeNode *) Node)->LastWrite + 1 == MAX_SECTOR_NUMBER)
		{
			*PhysicalPage = MAX_SECTOR_NUMBER;
		}
		else
		{
			*PhysicalPage = ((TreeNode *) Node)->LastWrite + 1;
		}


		if (GetNodeByPosition(Node,PhysicalBlockNumber) != SUCCESS)
		{	
			return FAILURE;
		}  			
		*Position = ((TreeNode *) Node)->Info;


		if ((*PhysicalPage >= MAX_SECTOR_NUMBER) && (((TreeNode *) Node)->Info == 0x02))
		{	
			return DATA_STRUCTURE_FULL;
		}


		if ((*PhysicalPage >= MAX_SECTOR_NUMBER) && (((TreeNode *) Node)->Info == 0x01))
		{	
			return PAGENOTFOUND;
		}  	
		
		return SUCCESS;
	} 


	if (flag == READ_OPERATION)
	{
		if (((TreeNode *) Node)->Info == 0x2)
		{
			*Position = 0x02;
			for (j = 0; j < MAX_ENTRY_CACHE; j++)
			{
				if ((GetSMCachePhysicalBlockNumber(j) ==
					((TreeNode *) Node)->PhysicalBlockNumber2) &&
					(GetSMFreeCache(j)))
				{
					CopySectorMapFromCache(&MapTemp,j);

					Result = GetSectorOffset(MapTemp,Sector,&OffSet);

					if (Result == SUCCESS)
					{
						*PhysicalPage = OffSet;
						*PhysicalBlockNumber = ((TreeNode *) Node)->PhysicalBlockNumber2;
					
						return SUCCESS;
					} 

					if (Result == PAGENOTFOUND)
					{
						cacheChecked = 1; 
						break;
					}
				}
			}//end for j


			if (cacheChecked == 0) //physicalblock mapped to a logical block not in the cache
			{
				CreateSectorMap(((TreeNode *) Node)->PhysicalBlockNumber2,&Map,
						&LastApp) ;
				

				IncrementIndexCache();

				SetSMFreeCache(GetSMIndexCache(),1); 
				CopySectorMap(Map,GetSMIndexCache());


				if (GetSectorOffset(Map,Sector,&OffSet) == SUCCESS)
				{
					*PhysicalPage = OffSet;
					*PhysicalBlockNumber = ((TreeNode *) Node)->PhysicalBlockNumber2;
					
					return SUCCESS;
				}
			} 

			cacheChecked = 0;
		}
		*Position = 0x01;
		for (j = 0; j < MAX_ENTRY_CACHE; j++)
		{
			if ((GetSMCachePhysicalBlockNumber(j) ==
				((TreeNode *) Node)->PhysicalBlockNumber1) &&
				(GetSMFreeCache(j)))
			{
				CopySectorMapFromCache(&MapTemp,j);

				Result = GetSectorOffset(MapTemp,Sector,&OffSet);

				if (Result == SUCCESS)
				{
					*PhysicalPage = OffSet;
					*PhysicalBlockNumber = ((TreeNode *) Node)->PhysicalBlockNumber1;
					
					return SUCCESS;
				} 

				if (Result == PAGENOTFOUND)
				{
					cacheChecked = 1; 
					break;
				}
			}
		}


		if (cacheChecked == 0)
		{
			CreateSectorMap(((TreeNode *) Node)->PhysicalBlockNumber1,&Map,&LastApp) ;
		
			IncrementIndexCache();

			SetSMFreeCache(GetSMIndexCache(),1); 
			CopySectorMap(Map,GetSMIndexCache());



			if (GetSectorOffset(Map,Sector,&OffSet) == SUCCESS)
			{
				*PhysicalPage = OffSet;
				*PhysicalBlockNumber = ((TreeNode *) Node)->PhysicalBlockNumber1;
				
				return SUCCESS;
			}
		}
	}
	
	return PAGENOTFOUND;
}



/***********************  AddBlock **********************************************
* Add in tree data structure saved in RAM the new node  						*
*  													   							*
*----------------------------------------------------------------------------   *
*   Node : is the pointer to the root node of tree data structure   			*
*	PhysicalBlockNumber:is the physical block in flash of new node of tree  	* 
*	SpareBuffer: indicate the position of new node and 							*
*   			 																*
*	return values:																*
*				SUCCESS:the node is added in tree data structure with success  	*
*				FAILURE:the fail is occured 								 	*
*********************************************************************************/

//angelo bug added parameter newblock
NFTL_Return AddBlock(UINT16 PhysicalBlockNumber, UINT8 *SpareBuffer, void **Node,
	UINT8 *Conflict, UINT16 *ConflictPhyBlockNum, UINT8 newblock)
{
	UINT8 CurrentLevel;
	UINT8 LastWrite = 0;

	CurrentLevel = SpareBuffer[TREE_POSITION_BYTE]; 


	if (CurrentLevel == ROOT_POSITION)
	{
		if (*Node == NULL)
		{
			CalculateLastWrite(PhysicalBlockNumber,&LastWrite) ;
			
			if (AddNode(Node,0x01,LastWrite,PhysicalBlockNumber) != SUCCESS)
			{
				return FAILURE;
			}
		}
		else
		{
			if (((TreeNode *) *Node)->PhysicalBlockNumber1 != 0)  // A conflict has occured
			{
				*Conflict = 1;
				*ConflictPhyBlockNum = PhysicalBlockNumber;
			}
			else 	//The Root in RAM already exist (it is founded after a Leaf)
			{
				((TreeNode *) *Node)->PhysicalBlockNumber1 = PhysicalBlockNumber;
				CalculateLastWrite(PhysicalBlockNumber,&LastWrite);
				
				if (AddNode(Node,0x01,LastWrite,PhysicalBlockNumber) != SUCCESS)
				{
					return FAILURE;
				}
			}
		}
	}
	else
	{
		if (*Node == NULL)
		{
			LastWrite = 0; 		
			CalculateLastWrite(PhysicalBlockNumber,&LastWrite) ;
			
			if (AddNode(Node,0x02,LastWrite,PhysicalBlockNumber) != SUCCESS)
			{
				return FAILURE;
			}

			return SUCCESS;
		}			
		CalculateLastWrite(PhysicalBlockNumber,&LastWrite) ;
		
		if (AddNode(Node,0x02,LastWrite,PhysicalBlockNumber) != SUCCESS)
		{
			return FAILURE;
		}
	}


	return SUCCESS;
}


/**********************    AddNode   ********************************
*   																*
* Allocare new mode in the tree 									*
*-------------------------------------------------------------------*
*   																*
*   																*
*	PARAMETER:  													* 
*   		   Root: is the Root of tree							*
*   																*   								 
*   		  Information: indicate the Info on Node  in the Tree   *
*      		  PhyBlockNum :Physical Block Number associated by Node *
*	return values:													*
*																	*
*				SUCCESS:no problems is occurred 		   			*
*				FAILURE: the operation is failed					*
*********************************************************************/

NFTL_Return AddNode(void **Root, UINT8 information, UINT8 LastWrite,
	UINT16 PhyBlockNumber)
{
	if (*Root == NULL)
	{
		*Root = (TreeNode *) OS_DRIVER_Malloc(sizeof(TreeNode));
		if (*Root == NULL)
		{
			return FAILURE;
		}

		if (information == 0x02)
		{
			((TreeNode *) (*Root))->Info = 0x02; 
			((TreeNode *) (*Root))->PhysicalBlockNumber1 = 0;
			((TreeNode *) (*Root))->PhysicalBlockNumber2 = PhyBlockNumber;
			((TreeNode *) (*Root))->LastWrite = LastWrite;
		}
		if (information == 0x01)
		{
			((TreeNode *) (*Root))->Info = 0x01; 
			((TreeNode *) (*Root))->PhysicalBlockNumber1 = PhyBlockNumber;
			((TreeNode *) (*Root))->LastWrite = LastWrite;
		}
		SetSMUsedBlocks(GetSMUsedBlocks() + 1);
		return SUCCESS;
	}
	else
	{
		if (information == 0x02)
		{
			((TreeNode *) (*Root))->Info = 0x02; 
			((TreeNode *) (*Root))->PhysicalBlockNumber2 = PhyBlockNumber;
			((TreeNode *) (*Root))->LastWrite = LastWrite;
		}
		if (information == 0x01)
		{
			((TreeNode *) (*Root))->Info = 0x02; 
			((TreeNode *) (*Root))->PhysicalBlockNumber1 = PhyBlockNumber;
		}
		SetSMUsedBlocks(GetSMUsedBlocks() + 1);	
		return SUCCESS;
	}

	return SUCCESS;
}


NFTL_Return CalculateLastWrite(UINT16 PhyBlockNumber, UINT8 *LastWrite)
{
	UINT8 SpareBuffer[BUFFER_SPARE_SIZE];
	INT16 i,LastVaule;
	UINT16 mid1,mid2;

	ReadSpare528(PhyBlockNumber, 0, SpareBuffer);
	if (SpareBuffer[PAGE_STATUS_BYTE] !=WRITTEN)
	{
		*LastWrite = 255;/*empty*/
		return SUCCESS;
	}
	
	
	ReadSpare528(PhyBlockNumber, 31, SpareBuffer);
	if (SpareBuffer[PAGE_STATUS_BYTE]  ==WRITTEN)
	{
		*LastWrite = 32;/*full*/
		return SUCCESS;
	}


	mid1 = PAGES_OF_BLOCK>>1;

	ReadSpare528(PhyBlockNumber, mid1, SpareBuffer);
	if (SpareBuffer[PAGE_STATUS_BYTE]== WRITTEN)/*Written*/
	{  
	       mid2= (mid1+1+PAGES_OF_BLOCK)>>1;
		ReadSpare528(PhyBlockNumber, mid2, SpareBuffer);
	     if (SpareBuffer[PAGE_STATUS_BYTE] == WRITTEN)/*Written*/ 
	    {
		       for ( i = PAGES_OF_BLOCK-2; i > mid2;i--)
		     {
				ReadSpare528(PhyBlockNumber, i, SpareBuffer);
				if (SpareBuffer[PAGE_STATUS_BYTE]  == WRITTEN)
				{
				     *LastWrite = i ;
					return SUCCESS;
				
				}
			}
			
			 *LastWrite = mid2; //all sector are written
			 return SUCCESS;
	     }
	     else
	     {
			for (i = mid2-1; i>mid1; i--)
	      		{       
		      		LastVaule = i;
				ReadSpare528(PhyBlockNumber, i, SpareBuffer);
				if (SpareBuffer[PAGE_STATUS_BYTE]  == WRITTEN)
				{
					*LastWrite = i ;
					return SUCCESS;
				}
			}
			
			*LastWrite=mid1;
			return SUCCESS;
		}
	}
	else /*Not Written*/
	{
	        mid2= (mid1-1)>>1;
		ReadSpare528(PhyBlockNumber, mid2, SpareBuffer);
		if (SpareBuffer[PAGE_STATUS_BYTE]  == WRITTEN)
	       {
		       for (i = mid2+1; i < mid1; i++)
		     {
				ReadSpare528(PhyBlockNumber, i, SpareBuffer);
				if (SpareBuffer[PAGE_STATUS_BYTE]  != WRITTEN)
				{
					*LastWrite = i - 1;
					return SUCCESS;
				}
			}
		       *LastWrite = mid1-1; //all sector are written
			return SUCCESS;
	     	}
	     	else
	     	{
			for (i=1;i < mid2; i++)
	      		{       
		      		LastVaule = i;
				ReadSpare528(PhyBlockNumber, i, SpareBuffer);
				if (SpareBuffer[PAGE_STATUS_BYTE]!= WRITTEN)
				{
					*LastWrite = i - 1;
					return SUCCESS;
				}
			
			}
				*LastWrite = mid2-1;
			return SUCCESS;
		}
	}
	
}


/*********************** SM_WritePage **********************************************
* Calculate the correct position in flash where the sector must be written and     *
* write in the spare area buffer the tree information  							   *
*--------------------------------------------------------------------------------- *
*   Node : is the pointer to the root node of tree data structure   			   *
*	Buffer_data: indicate the data to write in flash							   *
*	VirtualBlock: is the Virtual Block number of sector to write				   *  
*	Sector: is the sector number to write   									   *
*   			 																   *
*	return values:  															   *
*				DATA_STRUCTURE_FULL: the write operation in no possible in tree    *
*   								  data structure because it is full 		   *  
*				SUCCESS:the write operation is executed with success			   *
*				FAILURE:the fail is occured 								 	   *
************************************************************************************/