fil_wear.c

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

#ifndef _FIL_WEAR_C_
#define _FIL_WEAR_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]
 *
 ***************************************************************************/

/****************************************************************************
 *
 * Wear leveling for allocations
 *
 ***************************************************************************/

#include "mlayer.h"
#include "fil_wear.h"

/****************************************************************************
 *
 * variable for wear_alloc function
 *
 ***************************************************************************/

WEAR_ALLOCSTRUCT gl_wear_allocstruct; //this structure is filled when wear_alloc returns

/****************************************************************************
 *
 * dynamic wear leveling variable
 *
 ***************************************************************************/

unsigned long gl_dynamic_wear_info[MAX_FREE_BLOCK]; //dynamic wear info is here       //用于在程序运行过程中记录空闲块的wear
static unsigned char gl_dynamic_lock[(MAX_FREE_BLOCK+7) >> 3];//bitfield for locking mechanism //每位代表其对应的空闲块是否在使用。1：使用，0：空闲
                                                              //标示空闲块中暂时的非空闲块
static const unsigned char gl_lookup_mask[8]= //optimalized table for fast masking
	{0x01,0x02,0x04,0x08,0x10,0x20,0x40,0x80};

/****************************************************************************
 *
 * static wear leveling structure and variable
 *
 ***************************************************************************/

typedef struct {
	unsigned short logblock;
	unsigned long wear;
} STATIC_WEAR_INFO;  //用于缓存当前block上wear最小的8个逻辑block

#define MAXSTATICWEAR 8    //maximum deep of static wear leveling

static STATIC_WEAR_INFO gl_static_wear_info[MAXSTATICWEAR];

static unsigned long gl_static_cnt;	 //counter for static wearing

/****************************************************************************
 *
 * wear_init
 *
 * initiate wear leveling, this function must be called at power on
 *
 ***************************************************************************/

void wear_init() {   //初始化wear全局变量
unsigned short a;
   for (a=0; a<MAXSTATICWEAR; a++) {  
      gl_static_wear_info[a].logblock=BLK_NA;
      gl_static_wear_info[a].wear=WEAR_NA;
   }

   for (a=0; a<MAX_FREE_BLOCK; a++) {   
      gl_dynamic_wear_info[a]=WEAR_NA;
   }

   gl_static_cnt=2; //wait cycle after power on

   for (a=0; a<sizeof (gl_dynamic_lock); a++) {
      gl_dynamic_lock[a]=0xff; //set all bits to 1 means no free block available
   }
}


/****************************************************************************
 *
 * wear_check_static
 *
 * checking if static wear is needed
 *
 * RETURN
 *
 * 0 - if not needed
 * 1 - if static wear necessary
 *
 ***************************************************************************/

t_bit wear_check_static() {
unsigned short static_logblock=BLK_NA,a;
unsigned long static_wear=WEAR_NA;
   if (!gl_static_cnt) {
      //在gl_static_wear_info[8]中找出wear最小的logblock
      for (a=0; a<MAXSTATICWEAR; a++) {  
         unsigned long wear=gl_static_wear_info[a].wear;
         unsigned short logblock=gl_static_wear_info[a].logblock;

         if ((wear!=WEAR_NA) && (logblock!=BLK_NA)) {  
            if (static_logblock==BLK_NA) {
               static_logblock=logblock;
               static_wear=wear;
            }
            else if (wear<static_wear) {
               static_logblock=logblock;
               static_wear=wear;
            }
         }
      }

      if (static_logblock!=BLK_NA) {
		 unsigned char *lookup_mask=(unsigned char *)gl_lookup_mask;
		 unsigned char *dynamic_lock=gl_dynamic_lock;
		 t_ba *free_table=gl_freetable;
		 unsigned char b;

         for (b=0; b<MAX_FREE_BLOCK; b++) {   //search for limit
			if (!( (*dynamic_lock) & (*lookup_mask) ) ) { //check if locked
				if (!((*free_table) & FT_BAD)) {	//if it is realy free
            				unsigned long wear=gl_dynamic_wear_info[b];
   
            				if (wear!=WEAR_NA) {
             					  if (wear>static_wear+WEAR_STATIC_LIMIT) {
                 					 gl_wear_allocstruct.free_index=b;
                 					 gl_wear_allocstruct.free_wear=wear+1; //incremented by 1!
   
                  					gl_wear_allocstruct.static_logblock=static_logblock;
                  					gl_wear_allocstruct.static_wear=static_wear;

                  					gl_static_cnt=WEAR_STATIC_COUNT;
                  					return 1;	 //static wear successfully
              				 }                   //此空闲块的wear超出界限
					}
				}
			}

			free_table++;
			lookup_mask++;

			if ((b&7)==7) {
				lookup_mask=(unsigned char*)gl_lookup_mask; //reset look up
				dynamic_lock++;				//goto next bitfield;
			}
         }
      }
   }
   else {
	   gl_static_cnt--;
   }

   gl_wear_allocstruct.free_index=INDEX_NA; 

   gl_wear_allocstruct.static_logblock=BLK_NA;   
   gl_wear_allocstruct.static_wear=WEAR_NA;

   return 0;  //no static wear needed
}

/****************************************************************************
 *
 * wear_alloc
 *
 * allocates a block from free table list according to theirs wear level info
 * datas will be unchanged in all table (calling twice it returns with same
 * values) if static_logblock is not equal with BLK_NA then static wear heandler
 * has to be called immediately. gl_wear_allocstruct holds all the 
 * information
 *
 ***************************************************************************/

void wear_alloc() { //在空闲块中分配wear最小的块，结果保存在gl_wear_allocstruct中
unsigned char free_index=INDEX_NA,a;
unsigned long free_wear=WEAR_NA;
unsigned char *lookup_mask=(unsigned char *)gl_lookup_mask;
unsigned char *dynamic_lock=gl_dynamic_lock;
t_ba *free_table=gl_freetable;

	for (a=0; a<MAX_FREE_BLOCK; a++) {   //search for the less used free blk
		if (!( (*dynamic_lock) & (*lookup_mask) ) ) { //check if locked
			if (!((*free_table) & FT_BAD)) {	//if it is realy free
				unsigned long wear=gl_dynamic_wear_info[a];

					if (wear!=WEAR_NA) {
						if (free_index==INDEX_NA) {
							free_index=a;
							free_wear=wear;
						}
						else if (wear<free_wear) {
							free_index=a;
							free_wear=wear;
					}
				}
			}
		}

		lookup_mask++;
		free_table++;

		if ((a&7)==7) {
			lookup_mask=(unsigned char*)gl_lookup_mask; //reset look up
			dynamic_lock++;				//goto next bitfield;
		}
	}

	if ((free_index==INDEX_NA) || (free_wear==WEAR_NA)) {
 		gl_wear_allocstruct.free_index=INDEX_NA;
 		gl_wear_allocstruct.free_wear=WEAR_NA;
		return; //fatal error! no free block in the table
	}

	gl_wear_allocstruct.free_index=free_index;
	gl_wear_allocstruct.free_wear=free_wear+1; //store increased value of wear
}

/****************************************************************************
 *
 * wear_updatedynamicinfo
 *
 * updating dynamic wear level info of an indexed block (free block) 
 *
 * INPUTS
 *
 * index - index of the block in free table entry
 * wear - wear info of given block
 *
 ***************************************************************************/

void wear_updatedynamicinfo(unsigned char index, unsigned long wear) {
   if (index<MAX_FREE_BLOCK) {

		if (wear<WEAR_NA) { //keep original data inside <e.g. for log,map blocks>
//			if (wear==WEAR_AUTO) gl_dynamic_wear_info[index]=gl_wear_average;
//			else gl_dynamic_wear_info[index]=wear;
			gl_dynamic_wear_info[index]=wear;
		}

		gl_dynamic_lock[index>>3]|=gl_lookup_mask[index&7]; //optimalized!
	}
}


/****************************************************************************
 *
 * wear_releasedynamiclock
 *
 * Releasing newly added free blocks (enabled for allocation)
 * Must be called when a MAP dir or entry is stored
 *
 ***************************************************************************/

void wear_releasedynamiclock() {
unsigned char a;
	for (a=0; a<sizeof (gl_dynamic_lock); a++) {
		gl_dynamic_lock[a]=0; //set all bits to 0
	}
}

/****************************************************************************
 *
 * wear_updatestaticinfo
 *
 * updating static wear info of a static block (used block)
 *
 * INPUTS
 *
 * logblock - logical block number 
 * wear - wear info of the given block
 *
 ***************************************************************************/

void wear_updatestaticinfo(unsigned short logblock, unsigned long wear) {
unsigned long max_wear=WEAR_NA;
unsigned char a,max_index=INDEX_NA;

   if (logblock==BLK_NA) return;
//   if (wear==WEAR_AUTO) wear=gl_wear_average;
//   if (gl_wear_ave_block!=BLK_NA) { //check if average calculation is needed
//	   if (logblock>=gl_wear_ave_block) { //check if startup cycle finished
//		   gl_wear_count++;					//increase counts
//		   gl_wear_sum+=wear;				//add to summary
//		   gl_wear_average=gl_wear_sum/gl_wear_count; //calculate current average
//		   gl_wear_ave_block=logblock;
//	   }
//	   else gl_wear_ave_block=BLK_NA; //end of average calculation
//   }


   for (a=0; a<MAXSTATICWEAR; a++) {   //check if its already existed
      if (gl_static_wear_info[a].logblock==logblock) {
         gl_static_wear_info[a].wear=wear;
         return;
      }
   }

   for (a=0; a<MAXSTATICWEAR; a++) {   //search maximum or empty entry
      unsigned long twear=gl_static_wear_info[a].wear;
      if (twear!=WEAR_NA) {
         if (max_wear==WEAR_NA) {
            max_wear=twear;    
            max_index=a;        
         }
         else if (twear>max_wear) {
            max_wear=twear;    
            max_index=a;        
         }
      }
      else {
         gl_static_wear_info[a].wear=wear;
         gl_static_wear_info[a].logblock=logblock;
         return;
      }
   }

  if (max_index!=INDEX_NA) {             //替换掉静态wear最大的逻辑块
      if (wear<max_wear) {
         gl_static_wear_info[max_index].wear=wear;
         gl_static_wear_info[max_index].logblock=logblock;         
      }
   } 
}

/****************************************************************************
 *
 * end of fil_wear.c
 *
 ***************************************************************************/

#endif	//_FIL_WEAR_C_