mlayer.c

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

	return 0;
}

/****************************************************************************
 *
 * ml_save_map
 *
 * Save map informations (fragments, free table modification)
 *
 * RETURNS
 *
 * 0 - if success
 * other if any error
 *
 ***************************************************************************/

static t_bit ml_save_map() {
ST_MAPBLOCK  *map=get_mapblock(ml_frag.current);
ST_SPARE *sptr;
char domap=0;
unsigned char cou;

	DEBPR0("ml_save_map\n")

	if (!map) return 1; //fatal

	for (;;) {
again:
		if (map->ppo==MAX_PAGE_PER_BLOCK || domap) {

			unsigned char index = ml_alloc();
			if (index==INDEX_NA) return 1; //fatal

			map->pba=gl_freetable[index];
			map->ppo=0;
			wear_updatedynamicinfo(index,gl_wear_allocstruct.free_wear);

			map->ref_count++;   //以ref_count来区分最新的map block

			if (map->indexcou==MAX_MAP_BLK) {
				domap=1;
			}

			if (domap) {
				unsigned char idx;
				for (idx=0; idx<MAX_MAP_BLK;idx++) {
					unsigned char midx=map->index[idx];
					if (midx!=INDEX_NA) {
						gl_freetable[midx]&=~FT_MAP;
						wear_updatedynamicinfo(midx,WEAR_NA); //still locked
						map->index[idx]=INDEX_NA;				
					}
				}
				map->indexcou=0;
			}

			map->index[map->indexcou++]=index;
			gl_freetable[index]|=FT_MAP;

			DEBPR3("map_pba %d flt %04x domap %d\n",map->pba,gl_freetable[index],domap)
		}

		if (bb_flush()) return 1; //fatal

		sptr=GET_SPARE_AREA(ml_basebuff);

		if (!map->ppo) {
			sptr->wear=gl_wear_allocstruct.free_wear;
			sptr->u.map.ref_count=map->ref_count;
			sptr->block_type=map->block_type;
			sptr->bad_tag=0xff;
		}

		sptr->page_state=STA_MAPPAGE;
		sptr->frag=ml_frag.current;
	
		for (cou=0; cou<MAX_MAP_BLK; cou++) {
			ml_mapinfo->index[cou]=map->index[cou]; //copy history
		}

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

		ml_mapinfo->mappagecou_lo++;
		if (!ml_mapinfo->mappagecou_lo)	ml_mapinfo->mappagecou_hi++; /* 64bit counter */

		if (!ml_chk_frag(ml_frag.current)) {
			return 1; //fatal
		}

		if (!wll_writedouble(30,map->pba,map->ppo,(unsigned char*)ml_frag.ppba,(unsigned char*)gl_freetable)) {

			if (!domap) {
				map->last_pba=map->pba;
				map->last_ppo=map->ppo;

				ml_mapdir[ml_frag.current].pba=map->pba;
				ml_mapdir[ml_frag.current].ppo=map->ppo;
				ml_mapdir[ml_frag.current].index=1;

				map->ppo++;
			}
			else {
				unsigned char frag;
				unsigned char *sou,*dest;

				map->ppo++;
	
				sptr=GET_SPARE_AREA(ml_buffer);

				for (frag=0;frag<MAX_FRAG_PER_BLK;) {
	
					dest=ml_buffer;
					if (ml_chk_frag((unsigned char)(frag+map->start_frag))) {
						memcpy(dest,ml_frag.ppba,MAX_DATA_SIZE/2);
					}
					else {
						if (!ll_read(map->mapdir[frag].pba,map->mapdir[frag].ppo,ml_buffer2)) {
							sou=ml_buffer2;
							if (!map->mapdir[frag].index) sou+=MAX_DATA_SIZE/2;
							memcpy(dest,sou,MAX_DATA_SIZE/2);
						}
						else memset(dest,0xff,MAX_DATA_SIZE);
					}
					frag++;
	
					dest+=MAX_DATA_SIZE/2;
					if (ml_chk_frag((unsigned char)(frag+map->start_frag))) {
						memcpy(dest,ml_frag.ppba,MAX_DATA_SIZE/2);
					}
					else {
						if (!ll_read(map->mapdir[frag].pba,map->mapdir[frag].ppo,ml_buffer2)) {
							sou=ml_buffer2;
							if (!map->mapdir[frag].index) sou+=MAX_DATA_SIZE/2;
							memcpy(dest,sou,MAX_DATA_SIZE/2);
						}
						else memset(dest,0xff,MAX_DATA_SIZE);
					}
					frag++;

					sptr->page_state=STA_ORIGFRAG;

					if (wll_write(31,map->pba,map->ppo,ml_buffer)) goto again;

					map->ppo++;
				}
	
				ml_createmap(map,1);

				map->last_pba=map->pba;
				map->last_ppo=0;  //because of domap!

			}

			wear_releasedynamiclock();
			ml_save_map_need=0;
			return 0;
		}
		else {
			if (!map->ppo) {
				domap=1;
			}
			else {
				map->ppo++;
			}
		}
	}
}

/****************************************************************************
 *
 * ml_init
 *
 * Initialize this layer, this function must be called at the begining
 *
 * RETURNS
 *
 * 0 - if ok
 * other if any error
 *
 ***************************************************************************/

t_bit ml_init() {
unsigned long wear_sum=0;	//summary of wears
unsigned long wear_count=0;	//counting number of wears 
unsigned long wear_average=0;
unsigned char idx;
unsigned char cou;
t_ba pba,lba;
t_po po,lastpo;
ST_SPARE *sptr;
ST_LOG *log;

	DEBPR0("ml_init\n");

	if (ml_lowinit()) return 1;

	sptr=GET_SPARE_AREA(ml_buffer);

//search last map blk
	for (pba=0; pba<MAX_BLOCK; pba++) {

		wear_count++; //increase counts

		if (!ll_read(pba,0,ml_buffer)) {

			if (sptr->wear<WEAR_NA) wear_sum+=sptr->wear;				//add to summary


		    switch (sptr->block_type) {
			case BLK_TYPE_MAP_00: 
	        	case BLK_TYPE_MAP_01: 
		    	case BLK_TYPE_MAP_02: 
			case BLK_TYPE_MAP_03: check_reference_count(
								  (unsigned char)(sptr->block_type-BLK_TYPE_MAP_00),
								  sptr->u.map.ref_count,pba
								  ); 
			}
		}
	}

	ml_stepback=0;

	for (cou=0; cou<MAX_NUM_OF_DIF_MAP; cou++) {
		ST_MAPBLOCK *map=&ml_mapblocks[cou];
		if (map->pba==BLK_NA) return 1; //fatal, no map blk found

//search last erased only page
		lastpo=MAX_PAGE_PER_BLOCK;
		for (po=0;po<MAX_PAGE_PER_BLOCK;po++) {
			int ret=ll_read(map->pba,(unsigned char)(MAX_PAGE_PER_BLOCK-po-1),ml_buffer);
			if (ret==LL_ERASED) lastpo=(unsigned char)(MAX_PAGE_PER_BLOCK-po-1);
			else break;
		}

//search last po in block
		map->ppo=INDEX_NA;
		for (po=0;po<lastpo;po++) {
			int ret=ll_read(map->pba,po,ml_buffer);
			if (ret==LL_OK) {
				if (sptr->page_state==STA_MAPPAGE) {
					map->ppo=po;
				}
			}
		}

		if (map->ppo==INDEX_NA) return 1; //fatal, no map blk found

//read it
		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=lastpo;

		for (idx=0; idx<MAX_MAP_BLK; idx++) {
			if (ml_buildmap(map,idx)) {
				DEBPR1("ERROR: ml_buildmap at idx %d\n",idx);
				return 1; //fatal
			}
		}
	}


	{
//finding last fltable
		ST_MAPBLOCK *mapcur=ml_mapblocks;
		unsigned long mappagecou_lo=mapcur->mappagecou_lo;
		unsigned long mappagecou_hi=mapcur->mappagecou_hi;
		ST_MAPBLOCK *map=mapcur;

		for (cou=1,mapcur++; cou<MAX_NUM_OF_DIF_MAP;cou++,mapcur++) {
			if (mapcur->mappagecou_hi>mappagecou_hi) {
				mappagecou_lo=mapcur->mappagecou_lo;
				mappagecou_hi=mapcur->mappagecou_hi; 
				map=mapcur;				
			}
			else if (mapcur->mappagecou_hi==mappagecou_hi && mapcur->mappagecou_lo>mappagecou_lo) {
				mappagecou_lo=mapcur->mappagecou_lo;
				mappagecou_hi=mapcur->mappagecou_hi; 	
				map=mapcur;				
			}
		}

		if (ll_read(map->last_pba,map->last_ppo,ml_basebuff)) return 1; //fatal

		ml_mapinfo->mappagecou_lo=ml_max_mappagecou_lo;
		ml_mapinfo->mappagecou_hi=ml_max_mappagecou_hi; //write back the maximum found
	}

	if (bb_init(MAX_RESERVED_BLOCK)) return 1; //here the BB page is loaded!!! 

//building log blocks
	ml_logblocknum=0;
	log=ml_log;
	for (idx=0; idx<MAX_FREE_BLOCK; idx++) {
		if ((gl_freetable[idx]&(FT_MAP|FT_LOG))==FT_LOG) {
			pba=(t_ba)(gl_freetable[idx]&FT_ADDRMASK);

			log->lastppo=MAX_PAGE_PER_BLOCK;
			log->pba=pba;
			log->switchable=1;
			log->index=idx;

			lastpo=MAX_PAGE_PER_BLOCK;
			for (po=0;po<MAX_PAGE_PER_BLOCK;po++) { //searching the last page from top
				int ret=ll_read(pba,(unsigned char)(MAX_PAGE_PER_BLOCK-po-1),ml_buffer);
				if (ret==LL_ERASED) lastpo=(unsigned char)(MAX_PAGE_PER_BLOCK-po-1);
				else break;
			}

			log->lastppo=lastpo;
			for (po=0; po<lastpo; po++) {	//building log blk
				int ret=ll_read(pba,po,ml_buffer);
				if (ret==LL_OK) {
					log->ppo[sptr->u.log.lpo]=po;
					log->lba=sptr->u.log.lba;
					if (po!=sptr->u.log.lpo) log->switchable=0;
					if (!po) log->wear=sptr->wear;
				}
				else log->switchable=0; //if error or hole in the log block
			}

			if (log->lastppo!=0) { 
				log++;
				ml_logblocknum++;
			}
			else {
				gl_freetable[idx]&=~FT_LOG; //nothing was written, so remove log block flag
				log->lastppo=INDEX_NA;		//reset data in not used log blk
				log->pba=BLK_NA;
			}
		}
	}

   if (wear_count) wear_average=wear_sum/wear_count; //calculate current average

//fill dynamic wear info table
	for (idx=0; idx<MAX_FREE_BLOCK; idx++) {
		if ((gl_freetable[idx]&FT_BAD)!=FT_BAD) {
		 	pba=(t_ba)(gl_freetable[idx]&FT_ADDRMASK);
			if (ll_read(pba,0,ml_buffer)==LL_OK) {
				wear_updatedynamicinfo(idx,sptr->wear);
			}
			else {
                wear_updatedynamicinfo(idx,wear_average);
			}
		}
	}

	wear_releasedynamiclock();

//fill static wear info
    for(lba=0; lba<MAX_BLOCK; lba++) {
		pba=ml_get_log2phy(lba);
        if (pba==BLK_NA) break;

        if (ll_read(pba,0,ml_buffer)) {
            wear_updatestaticinfo(lba, 0);  
        } else {
            wear_updatestaticinfo(lba, sptr->wear);  /* only data block could be updated */
        }
        ml_data_blk_count++;
	}

	if (ml_stepback) {
		t_ba lba=ml_stepback->start_frag;

		lba*=MAX_FRAGSIZE;

		ml_stepback->ppo=MAX_PAGE_PER_BLOCK;
		ml_stepback->indexcou=MAX_MAP_BLK; //force map merge

		if (ml_get_log2phy(lba)==BLK_NA) return 1;
		if (ml_save_map()) return 1;
	}

	ml_state=ML_CLOSE;

	return 0;
}


/****************************************************************************
 *
 * write_frags
 *
 * subfunction for formatting to write current fragments in fragbuff
 *
 * INPUTS
 *
 * frag - current frag number
 *
 * RETURNS
 *
 * 0 - if successfuly
 * other if any error
 *
 ***************************************************************************/

static t_bit write_frags(unsigned char frag) {
ST_SPARE *sptr=GET_SPARE_AREA(ml_fragbuff);
ST_MAPBLOCK  *map=get_mapblock(frag);

	if (!map->ppo) {
		sptr->wear=1;//gl_wear_allocstruct.free_wear;
		sptr->u.map.ref_count=map->ref_count;
		sptr->block_type=map->block_type;
		sptr->bad_tag=0xff;
	}

	sptr->page_state=STA_ORIGFRAG;

	if (wll_write(1,map->pba,map->ppo,ml_fragbuff)) return 1; //fatal
	map->ppo++;
	return 0;
}

/****************************************************************************
 *
 * ml_getmaxsector
 *
 * retreives the maximum number of sectors can be used in the system
 *
 * RETURNS
 *
 * maximum number of sectors
 *
 ***************************************************************************/

unsigned long ml_getmaxsector() {
	return ml_data_blk_count;
}

/****************************************************************************
 *
 * ml_format
 *
 * Formatting the layer, this function must be called once at manufacturing
 *
 * RETURNS
 *
 * 0 - if success
 * other if any error
 *
 ***************************************************************************/

t_bit ml_format() {
unsigned long lbacou;
unsigned short fidx;
unsigned char index;
unsigned char cou;
unsigned char frag;
t_ba pba;
t_ba *ppba;
ST_SPARE *sptr=GET_SPARE_AREA(ml_buffer);

	if (ml_lowinit()) return 1;

	for (index=0,pba=0;index<MAX_FREE_BLOCK+MAX_RESERVED_BLOCK; pba++,index++) {
		int ret=ll_read(pba,0,ml_buffer);
		if (ret==LL_OK || ret==LL_ERROR) {
			if (sptr->bad_tag!=0xff) {
				DEBPR2("Bad Block found (badtag) pba %d [%4x]",pba,pba);
				continue; //bad block
			}
			if (ll_erase(pba)) {
				sptr->bad_tag=0; //signalling bad block
				ll_write(pba,0,ml_buffer);
				DEBPR2("Bad Block found (erased) pba %d [%4x]",pba,pba);
				continue; //cannot be erased so bad block
			}
		}

		if (index<MAX_FREE_BLOCK) {
			gl_freetable[index]=pba;
			wear_updatedynamicinfo((unsigned char)index,0);
		}
		else {
			if (bb_addreserved(pba)) {
				return 1;
			}
		}
	}

	wear_releasedynamiclock();

//allocate MAP block
	for (cou=0; cou<MAX_NUM_OF_DIF_MAP; cou++) {
		ST_MAPBLOCK *map=&ml_mapblocks[cou];

		index = ml_alloc();
		if (index==INDEX_NA) return 1; //fatal
		map->pba=gl_freetable[index];
		map->ppo=0;
		gl_freetable[index]|=FT_MAP;
		wear_updatedynamicinfo(index,gl_wear_allocstruct.free_wear);

		map->indexcou=0;
		map->index[map->indexcou++]=index;
		map->ref_count=1;
	}

	memset (ml_mapinfo,0xff,sizeof(ST_MAPINFO));

//create MAP dir from remaining blocks
	ppba=(t_ba *)ml_fragbuff;
	fidx=0;
	frag=0;
	lbacou=0;

	for (;pba<MAX_BLOCK;pba++) {
		int ret=ll_read(pba,0,ml_buffer);

		lbacou++;

		if (ret==LL_OK || ret==LL_ERROR) {
			if (sptr->bad_tag!=0xff) {
				DEBPR2("Bad Block found (badtag) pba %d [%4x]",pba,pba);
				continue; //bad block
			}
			if (ll_erase(pba)) {
				sptr->bad_tag=0; //signalling bad block
				ll_write(pba,0,ml_buffer);
				DEBPR2("Bad Block found (erased) pba %d [%4x]",pba,pba);
				continue; //cannot be erased so bad block
			}
		}

		ml_data_blk_count++;

		ppba[fidx++]=pba;
		if (fidx==MAX_FRAGSIZE*2) {
			if (write_frags(frag)) return 1; //fatal
			fidx=0;
			frag+=2;
		}
	}

	for (;lbacou<MAX_BLOCK;lbacou++) { //fill remaining with BLK_NA
		ppba[fidx++]=BLK_NA;		
		if (fidx==MAX_FRAGSIZE*2) {
			if (write_frags(frag)) return 1; //fatal
			fidx=0;
			frag+=2;
		}
	}