mlayer.c

一个nand flash管理的算法（匈牙利算法）

#ifndef _MLAYER_C_
#define _MLAYER_C_

/****************************************************************************
 *
 *            Copyright (c) 2005 by HCC Embedded 
 *
 * This software is copyrighted by and is the sole property of 
 * HCC.  All rights, title, ownership, or other interests
 * in the software remain the property of HCC.  This
 * software may only be used in accordance with the corresponding
 * license agreement.  Any unauthorized use, duplication, transmission,  
 * distribution, or disclosure of this software is expressly forbidden.
 *
 * This Copyright notice may not be removed or modified without prior
 * written consent of HCC.
 *
 * HCC reserves the right to modify this software without notice.
 *
 * HCC Embedded
 * Budapest 1132
 * Victor Hugo Utca 11-15
 * Hungary
 *
 * Tel:  [phone]
 * Fax:  [phone]
 * http: www.hcc-embedded.com
 * email: [e-mail]
 *
 ***************************************************************************/

#include "llayer.h"
#include "mlayer.h"
#include "fil_wear.h"
#include "fil_bad.h"
#include "prgmacro.h"
#include "string.h"
#include "mdebug.h"

/****************************************************************************
 *
 *	global Variables
 *
 ***************************************************************************/

t_ba *gl_freetable;
ST_MAPDIR ml_mapdir[MAX_FRAGNUM];//标示8个映射表存放的具体位置

/****************************************************************************
 *
 *	static Variables
 *
 ***************************************************************************/

static unsigned char ml_buffer[MAX_PAGE_SIZE];
static unsigned char ml_buffer2[MAX_PAGE_SIZE];

static unsigned char ml_basebuff[MAX_PAGE_SIZE];       // freelogtable mapinfo block
                   //包含三部分信息：前256字节存放当前操作映射表的信息
                   //                接着存放空闲块表信息:gl_freetable
                   //                最后存放ml_mapinfo
static unsigned char ml_fragbuff[MAX_PAGE_SIZE*MAX_CACHEFRAG];  //内存中映射表的具体位置

static ST_LOG ml_log[MAX_LOG_BLOCK];
static ST_LOG *ml_curlog;
static unsigned char ml_logblocknum;
static unsigned char ml_logmerge;

static t_ba ml_lba;
static t_po ml_lpo;
static t_ba ml_pba;

static unsigned long ml_seccou;

static ST_FRAG ml_frag;

static unsigned char ml_state;
static t_ba ml_lbastatic;

static ST_MAPINFO *ml_mapinfo;

static unsigned char ml_save_map_need;

static unsigned long ml_max_mappagecou_lo;
static unsigned long ml_max_mappagecou_hi; //for searching the maximum!

static ST_MAPBLOCK ml_mapblocks[MAX_NUM_OF_DIF_MAP];

static ST_MAPBLOCK *ml_stepback;
static unsigned long ml_data_blk_count;


/****************************************************************************
 *
 * ml_chk_frag
 *
 * function checks if requested fragment is in the cache area
 * and set ppba pointer its start address if found
 *
 * RETURNS
 *
 * 1 - if cached
 * 0 - if not
 *
 ***************************************************************************/
//检查此映射表是否在cache中
static t_bit ml_chk_frag(unsigned char frag) {
unsigned char idx; 

	for (idx=0; idx<MAX_CACHEFRAG; idx++) {
		if (ml_frag.indexes[idx]==frag) {
			ml_frag.ppba=ml_frag.ppbas[idx];
			return 1;
		}
	}
	return 0;
}

/****************************************************************************
 *
 * ml_get_log2phy
 *
 * convert logical address to physical
 *
 * INPUTS
 *
 * lba - logical block address
 *
 * RETURNS
 *
 * physical address or BLK_NA if address is invalid
 *
 ***************************************************************************/

static t_ba ml_get_log2phy(t_ba lba) {
unsigned short index; 
unsigned char *buff;
	if (lba>=(MAX_BLOCK-MAX_FREE_BLOCK)) return BLK_NA;

	ml_frag.current=(unsigned char)(lba/MAX_FRAGSIZE);
	index=(unsigned short)(lba%MAX_FRAGSIZE);

	if (ml_chk_frag(ml_frag.current)) return ml_frag.ppba[index];

	ml_frag.pos++;                                    //简单的循环算法,替换cache
	if (ml_frag.pos>=MAX_CACHEFRAG) ml_frag.pos=0;    

	buff=ml_fragbuff+MAX_PAGE_SIZE*((unsigned short)(ml_frag.pos));

	if (ll_read(ml_mapdir[ml_frag.current].pba,ml_mapdir[ml_frag.current].ppo,buff)) {
		ml_frag.indexes[ml_frag.pos]=INDEX_NA;
		return BLK_NA;
	}

	if (ml_mapdir[ml_frag.current].index) ml_frag.ppbas[ml_frag.pos]=(t_ba *)buff;
	else ml_frag.ppbas[ml_frag.pos]=(t_ba *)(buff+MAX_DATA_SIZE/2);

	ml_frag.ppba=ml_frag.ppbas[ml_frag.pos];
	ml_frag.indexes[ml_frag.pos]=ml_frag.current;

	return ml_frag.ppba[index];
}

/****************************************************************************
 *
 * ml_set_log2phy
 *
 * set logical block's physical address, 1st ml_get_log2phy function has to
 * be called to get the fragments into the cached area and ppba must be set
 *
 * INPUTS
 *
 * lba - logical block address
 * pba - physical block address
 *
 * RETURNS
 *
 * 0 - if success
 * other if any error
 *
 ***************************************************************************/

static t_bit ml_set_log2phy(t_ba lba,t_ba pba) {
unsigned short index; 
	if (lba>=(MAX_BLOCK-MAX_FREE_BLOCK)) return 1;

	index=(unsigned short)(lba%MAX_FRAGSIZE);
	ml_frag.ppba[index]=pba;

	return 0;
}


/****************************************************************************
 *
 * ml_createmap
 *
 * Creates complete mapdir information for a given block address
 *
 * INPUTS
 *
 * map - which map is used to 
 * ppo - physical page offset, where to start this information
 *
 ***************************************************************************/

static void ml_createmap(ST_MAPBLOCK  *map,unsigned char ppo) {
unsigned char frag;
	for (frag=0; frag<MAX_FRAG_PER_BLK;) {
		map->mapdir[frag].pba=map->pba;
		map->mapdir[frag].ppo=ppo;
		map->mapdir[frag].index=1;
		frag++;

		map->mapdir[frag].pba=map->pba;
		map->mapdir[frag].ppo=ppo;
		map->mapdir[frag].index=0;
		frag++;
		ppo++;
	}
}

/****************************************************************************
 *
 * ml_lowinit
 *
 * low level initialization, this must be called from ml_init and ml_format
 *
 * RETURN
 *
 * 0 - if ok
 * other if error
 *
 ***************************************************************************/

static t_bit ml_lowinit() {
int a;

	ml_state=ML_INIT;

	if (ll_init()) return 1;

	DEBOPEN;

	wear_init();

	ml_curlog=0;
	ml_logblocknum=0;
	ml_logmerge=0;

	memset (ml_log,0xff,sizeof(ml_log)); //reset all entries

	gl_freetable=(t_ba *)(ml_basebuff+MAX_DATA_SIZE/2);
	ml_mapinfo = (ST_MAPINFO *)(&gl_freetable[MAX_FREE_BLOCK]);

	ml_frag.pos=0;
	memset(ml_frag.indexes,INDEX_NA,sizeof(ml_frag.indexes));
	ml_frag.current=INDEX_NA;

	for (a=0; a<MAX_NUM_OF_DIF_MAP; a++) {
		ST_MAPBLOCK *map=&ml_mapblocks[a];

		map->last_pba=BLK_NA;
		map->last_ppo=INDEX_NA;

		map->block_type=(unsigned char)(BLK_TYPE_MAP_00+a);
		map->mapdir=&ml_mapdir[a*MAX_FRAG_PER_BLK];
		map->pba=BLK_NA;
		map->ppo=INDEX_NA;
		map->ref_count=0;
		map->start_frag=(unsigned char)(a*MAX_FRAG_PER_BLK);
		map->end_frag=(unsigned char)(map->start_frag+MAX_FRAG_PER_BLK);

		map->indexcou=0;
		memset(map->index,INDEX_NA,MAX_MAP_BLK);
	}

	ml_max_mappagecou_lo=0;
	ml_max_mappagecou_hi=0;
	
	gl_badblock=&ml_mapinfo->badblock;

	gl_badblock->index=INDEX_NA;
	gl_badblock->pba=BLK_NA;
	gl_badblock->ppo=INDEX_NA;

	bb_init(MAX_RESERVED_BLOCK); //here the BB page is not loaded!!! 
	//We should call this function again later if we have the MAP-PAGE

	ml_save_map_need=0;

	memset(ml_mapdir,0xff,sizeof(ml_mapdir));
	ml_data_blk_count=0;

	return 0;
}									   

/****************************************************************************
 *
 * ml_buildmap
 *
 * function for rebuilding mapdir from a given index from free block table
 *
 * INPUTS
 *
 * idx  - mapinfo index, to be built from
 *
 * RETURNS
 *
 * 0 - if ok
 * other if any error
 *
 ***************************************************************************/

static t_bit ml_buildmap(ST_MAPBLOCK *map,unsigned char idx) {
t_ba pba;
t_po ppo;
unsigned char index;
ST_SPARE *sptr=GET_SPARE_AREA(ml_buffer);
unsigned char frag;
unsigned char afrm=0;
again:
	map->index[idx]=ml_mapinfo->index[idx];
	index=ml_mapinfo->index[idx];

	if (index!=INDEX_NA) {
		map->indexcou=(unsigned char)(idx+1); //update indexcou
	}

	DEBPR0("ml_buildmap\n");

	if (idx==0) {
		if (index==INDEX_NA) return 1; //fatal

		map->mappagecou_hi=ml_mapinfo->mappagecou_hi;
		map->mappagecou_lo=ml_mapinfo->mappagecou_lo; /* get the counter, if step back then it is also ok */


		if (ml_mapinfo->mappagecou_hi>ml_max_mappagecou_hi) {
			ml_max_mappagecou_lo=ml_mapinfo->mappagecou_lo;
			ml_max_mappagecou_hi=ml_mapinfo->mappagecou_hi; 
		}
		else if (ml_mapinfo->mappagecou_hi==ml_max_mappagecou_hi && ml_mapinfo->mappagecou_lo>ml_max_mappagecou_lo) {
			ml_max_mappagecou_lo=ml_mapinfo->mappagecou_lo;
			ml_max_mappagecou_hi=ml_mapinfo->mappagecou_hi; 	
		}

		pba=(t_ba)(gl_freetable[index]&FT_ADDRMASK);
		ppo=0;

		if (!ll_read(pba,ppo,ml_buffer)) {
			if (sptr->page_state==STA_MAPPAGE) {
				frag=sptr->frag;
				ml_mapdir[frag].pba=pba;
				ml_mapdir[frag].ppo=ppo;
				ml_mapdir[frag].index=1;
				ppo=1;
			}
			else if (sptr->page_state!=STA_ORIGFRAG) {
				DEBPR1("sptr->page_state %d\n",sptr->page_state);
				return 1; //only mappage can be here, or origfrag after format
			}
			else afrm=1; //we are after format
		}
		else return 1; //must be ok!

		for (frag=0;frag<MAX_FRAG_PER_BLK; ppo++) {
			if (!ll_read(pba,ppo,ml_buffer)) {
				if (sptr->page_state==STA_ORIGFRAG) {
					map->mapdir[frag].pba=pba;
					map->mapdir[frag].ppo=ppo;
					map->mapdir[frag].index=1;
					frag++;

					map->mapdir[frag].pba=pba;
					map->mapdir[frag].ppo=ppo;
					map->mapdir[frag].index=0;
					frag++;
				}
				else {
					return 1; //only mappage can be here
				}
			}
			else {
				//broken mapdir, so step back
				if (ml_stepback) return 1; //only once is allowed
				ml_stepback=map;

				if (ml_mapinfo->last_pba==BLK_NA || ml_mapinfo->last_ppo==INDEX_NA) return 1; //cant

				map->pba=ml_mapinfo->last_pba;
				map->ppo=ml_mapinfo->last_ppo;

				if (ll_read(map->pba,map->ppo,ml_basebuff)) return 1; //fatal

				map->last_pba=map->pba; //update last information
				map->last_ppo=map->ppo;

				map->ppo++; //set next position

				goto again;
			}
		}
	}
	else {
		if (index==INDEX_NA) return 0; //nothing to do
		pba=(t_ba)(gl_freetable[index]&FT_ADDRMASK);
		ppo=0;
	}

	for (;ppo<MAX_PAGE_PER_BLOCK; ppo++) {
		int ret=ll_read(pba,ppo,ml_buffer);
		if (ret==LL_OK) {
			if (sptr->page_state==STA_MAPPAGE) {
				frag=sptr->frag;
				ml_mapdir[frag].pba=pba;
				ml_mapdir[frag].ppo=ppo;
				ml_mapdir[frag].index=1;
			}
			else {
				return 1; //only mappage can be here
			}
		}
		else if (ret==LL_ERASED) continue; //maybe flashfail happened
	}

	if (afrm) {
		//we are after format
		if (ppo<MAX_FRAG_PER_BLK/2) return 1; //flt missing after format
	}

	return 0;
}


/****************************************************************************
 *
 * check_reference_count
 *
 * function check and set the latest map reference counter
 *
 * INPUTS
 *
 * mapnum - which map need to be checked
 * refcount - current reference counter
 * pba - current block physical address
 *
 ***************************************************************************/

static void check_reference_count(unsigned char mapnum,unsigned long ref_count,t_ba pba) {
ST_MAPBLOCK *map=&ml_mapblocks[mapnum];

	if (map->pba==BLK_NA) { /* we have found the 1st map block */
		map->pba=pba;
		map->ref_count=ref_count;
	} 
	else {
		if (map->ref_count<ref_count) {
			map->pba=pba;
            map->ref_count=ref_count;
		}
	}
}

/****************************************************************************
 *
 * ml_alloc
 *
 * allocate a block from free table and erases it
 *
 * RETURNS
 *
 * index in free table or INDEX_NA if any error
 *
 ***************************************************************************/

static unsigned char ml_alloc() {
unsigned char index;

	for (;;) {	   //loop for wear alloc
		t_ba pba;

		wear_alloc();
		index=gl_wear_allocstruct.free_index;

		DEBPR1("ml_alloc index %d\n",index);

	    	if (index==INDEX_NA) {
			return INDEX_NA; //FATAL error no free blocks are available
	    	}


		pba=gl_freetable[index];

		for (;;) { //internal loop for pba changing                                     //***********************************
                                                                                        //*从空闲块中分配一个wear最小的块
			DEBPR2("ml_alloc pba %d, %04x\n", pba,pba);                                 //*擦除   成功返回
                                                                                        //*失败：寻找替代坏块
			if (wll_erase(100,pba) == LL_OK) {                                          //*找到则擦除返回
				return index; //erase is ok, so return with the index                   //*找不到则从新分配空闲块
			}                                                                           //***********************************

	        DEBPR1("ml_alloc: Erase of block %d failed\n", pba);

			pba=bb_setasbb(pba); //change pba, set current as BAD
			if (pba==BLK_NA) {	 //check if success
				gl_freetable[index] |= FT_BAD;     //signal it as locked BAD
				break; //get a new index
			}

			gl_freetable[index] = pba; //write back new pba
			gl_wear_allocstruct.free_wear=1; //set new wear info
			wear_updatedynamicinfo(index,1); //update wear info
		}
	}

}

/****************************************************************************
 *
 * get_mapblock
 *
 * Function for retreiving the map according fragment counter
 *
 * INPUTS
 *
 * frag_num - fragment number
 *
 * RETURNS
 *
 * map pointer where the fragment is or NULL if any error
 *
 ***************************************************************************/

ST_MAPBLOCK *get_mapblock(unsigned char frag_num) {
ST_MAPBLOCK *map=ml_mapblocks;

	if (frag_num<map->end_frag) return map;

	map++; 
	if (frag_num<map->end_frag) return map;

	map++; 
	if (frag_num<map->end_frag) return map;

	map++; 
	if (frag_num<map->end_frag) return map;