Effective wear-leveling and concurrent reclamation method for embedded linear flash file systems

• US 20070150689A1
• Filed: 12/22/2005
• Published: 06/28/2007
• Est. Priority Date: 12/22/2005
• Status: Active Grant

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Sampath, Sridhar, Pandit, Anil
• Granted Patent: US 7,831,783 B2
• Time in Patent Office: Days
• US Class Current: 711/170
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/1036 Life time enhancement
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 2212/7211 Wear leveling
• CPC Class Codes: G06F 3/0616 in relation to life time, e.g. increasing Mean Time Between Failures [MTBF]
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]

Abstract

Reclamation of an Erase Unit of a flash memory is performed concurrently with a file operation on the flash memory by initiating a reclamation operation on the individually erasable portion of the memory, by suspending the reclamation operation for the file operation, by performing the file operation, and by resuming the reclamation operation.

Claims

1. A method for concurrently reclaiming an individually erasable portion of a memory and performing a file operation on the memory comprising:

initiating a reclamation operation on the individually erasable portion of the memory;

suspending the reclamation operation for the file operation;

performing the file operation; and

,

resuming the reclamation operation.

2. The method of claim 1 wherein the performing of the file operation comprises suspending the file operation if the memory contains insufficient free memory space for the file operation.

3. The method of claim 1 wherein the initiating of a reclamation operation and the resuming of the reclamation operation comprises moving file data from the individually erasable portion of the memory being reclaimed to a free memory space of the memory.

4. The method of claim 3 wherein the moving of file data comprises updating master control information associated with the individually erasable portion of the memory being reclaimed.

5. The method of claim 3 wherein the moving of file data comprises updating master control information associated with the free Erase Unit to which the file data is moved.

6. The method of claim 5 wherein the moving of file data comprises updating master control information associated with the individually erasable portion of the memory being reclaimed.

7. The method of claim 1 wherein the initiating of a reclamation operation and the resuming of the reclamation operation comprises moving master control information from the individually erasable portion of the memory being reclaimed to a to-be-next master control information portion on the memory.

8. The method of claim 7 wherein the moving of master control information comprises updating the master control information being moved so that the updating reflects the recovery of dirty blocks used up by maps and so that the updating simultaneously helps in maintaining wear-leveling of the memory.

9. The method of claim 1 wherein the initiating of a reclamation operation comprises initiating the reclamation of a master control information portion if the master control information portion is full.

10. The method of claim 1 wherein the initiating of a reclamation operation comprises initiating the reclamation if there is no free memory.

11. The method of claim 1 wherein the initiating of a reclamation operation comprises initiating the reclamation if the individually erasable portion has exceeded a threshold of minimum to maximum erasures.

12. The method of claim 1 wherein the initiating of a reclamation operation comprises initiating the reclamation if more than 75% of the individually erasable portion is dirty.

14. The method of claim 12 wherein the reclaiming of the targeted Erase Units comprises:

a) locating files in one of the targeted Erase Units on an Extent by Extent basis by use of Erase Unit Information contained in a Master Control Erase Unit;

b) acquiring a semaphore/mutex and locking a file containing the file data by setting a variable in an Incore Inode stored on a RAM;

c) moving one file block from the one targeted Erase Unit to a free Erase Unit and determining if a file operation on the file is to be performed by checking a reqFileReadWrite variable in the Incore Inode;

d) if an Inode is present in the one targeted Erase Unit, updating the Incore Inode after relocation of the Inode before releasing a file lock in the Incore Inode;

e) if the variable reqFileReadWrite is set, releasing the file lock to allow the file operation to be performed provided there are sufficient free Blocks available in the flash memory;

f) if the variable reqFileReadWrite is set and if there is insufficient free Blocks on the flash memory, suspending the file operation until the reclamation is finished;

g) if the variable reqFileReadWrite is not set, continuing the relocation of the file blocks one after another until all blocks of the file in the one targeted Erase Unit have been relocated to the free Erase Unit;

h) repeating b) to e) for all files in the one targeted Erase Unit;

i) when all file blocks have been re-located from the one targeted Erase Unit, erasing the one targeted Erase Unit; and

,

j) after the erasure, locking the semaphore and updating free, dirty, and bad block map data for the new state of the one targeted Erase Unit.

13. A method for reclaiming targeted Erase Units of a flash memory comprising:

identifying the targeted Erase Units based on fitness for reclamation; and

,

reclaiming the targeted Erase Units even if the targeted Erase Units do not contain dirty Blocks of the flash memory.

15. The method of claim 13 wherein the reclaiming of the targeted Erase Units comprises:

a) locating a Master Control Erase Unit targeted for reclamation;

b) relocating Erase Unit related data in the targeted Master Control Erase Unit after linking the targeted Master Control Erase Unit to a To-B-Next Master Control Erase Unit, wherein the relocated Erase Unit related data includes free, dirty, and bad block maps, and an Erase Unit Health map on the flash memory, wherein the Erase Unit related data comprises;

struct stEuInfoOnFlash{DWORD dEuNo;

DWORD dEUHealth;

BYTE 

 

bEuMap[MAP_SIZE];

}

wherein MAP_SIZE comprises a macro assigned with a value to represent the free Block map, the dirty Block map, and the bad Block map, wherein the relocating of Erase Unit related data includes relocating a Master Block of the targeted Master Control Erase Unit, and wherein the Master Block contains file system information;

c) acquiring a semaphore, moving one block corresponding to the Erase Unit related data from the target Master Control Erase Unit to the To-Be-Next Master Control Erase Unit, updating the Erase Unit related data in the Master Control Erase Unit so that any updates due to file operations involve changes to the relocated Blocks in the To-Be-Next Master Control Erase Unit, and releasing the semaphore;

d) repeating c) until all Blocks have been re-located;

e) locking the semaphore, updating partition information to change the Master Control Erase Unit from the targeted Master Control Erase Unit to the To-Be-Next Master Control Erase Unit, and releasing the semaphore;

f) erasing the targeted Master Control Erase Unit and updating free, dirty, Erase Unit Health, and bad maps appropriately;

g) identifying a free Erase Unit to act as the To-Be-Next Master Control Erase Unit and updating the partition information for the new To-Be-Next Master Control Erase Unit; and

,

h) updating the free map corresponding to the To-Be-Next Master Control Erase Unit to mark all Blocks within the To-Be-Next Master Control Erase Unit as used to prevent storing file data in the blocks of the to-be-next Master Control Erase Unit.

16. The method of claim 15 wherein the reclaiming of the targeted Erase Units comprises:

a) locating files in one of the targeted Erase Units on an Extent by Extent basis by use of Erase Unit Information contained in a Master Control Erase Unit;

b) acquiring a semaphore/mutex and locking a file containing the file data by setting a variable in an Incore Inode stored on a RAM;

c) moving one file Block from the one targeted Erase Unit to a free Erase Unit and determining if a file operation on the file is to be performed by checking a reqFileReadWrite variable in the Incore Inode;

d) if an Inode is present in the one targeted Erase Unit, updating the Incore Inode after relocation of the Inode before releasing a file lock in the Incore Inode;

e) if the variable reqFileReadwrite is set, releasing the file lock to allow the file operation to be performed provided there are sufficient free Blocks available in the flash memory;

f) if the variable reqFileReadWrite is set and if there is insufficient free Blocks on the flash memory, suspending the file operation until the reclamation is finished;

g) if the variable reqFileReadWrite is not set, continuing the relocation of the file blocks one after another until all blocks of the file in the one targeted Erase Unit have been relocated to the free Erase Unit;

h) repeating b) to e) for all files in the one targeted Erase Unit;

i) when all file blocks have been re-located from the one targeted Erase Unit, erasing the one targeted Erase Unit; and

,

j) after the erasure, locking the semaphore and updating free, dirty, and bad block map data for the new state of the one targeted Erase Unit.

17. The method of claim 13 wherein the identifying of the targeted Erase Units comprises:

a) creating an Erase Unit Information table in a RAM containing records in the following format;

struct EU_INFO{DWORD dEuNo;

DWORD dEuHealth;

DWORD dNoOfFreeBlocks;

DWORD dNoOfDirtyBlocks;

DWORD dNoOfBadBlocks;

DWORD pMapStart;

struct stIncoreInode pFileIncores [x];

// NOTE;

Based on the block, extent and// EU size there are‘

x’

number of// files that could potentially bepresent// in an EU};

wherein the Erase Unit Information table is created at file system startup by scanning Erase Unit related data on the flash memory;

creating a reclamation thread at the startup, wherein the reclamation thread maintains a list of Erase Units that are totally unused (free Erase Units) and also a list of Erase Units that are probable candidates for reclamation by scanning the Erase Unit Information table;

targeting a Master Control Erase Unit for reclamation if the Master Control Erase Unit is full;

targeting a dirtiest Erase Unit for reclamation if there are no free Erase Units;

targeting a most worn Erase Unit for reclamation if there are free Erase Units and the most worn Erase Unit has exceeded a threshold of minimum to maximum erasures; and

,

targeting a dirty Erase Unit for reclamation if the dirty Erase Unit is more than 75% dirty.

18. The method of claim 17 wherein the reclaiming of the targeted Erase Units comprises:

a) locating files in one of the targeted Erase Units on an Extent by Extent basis by use of Erase Unit Information contained in a Master Control Erase Unit;

b) acquiring a semaphore/mutex and locking a file containing the file data by setting a variable in an Incore Inode stored in the RAM;

c) moving one file block from a targeted Erase Unit to a free Erase Unit and determining if a file operation on the file is to be performed by checking a reqFileReadWrite variable in the Incore Inode;

d) if an Inode is present in the one targeted Erase Unit, updating the Incore Inode after relocation of the Inode before releasing a file lock in the Incore Inode;

e) if the variable reqFileReadWrite is set, releasing the file lock to allow the file operation to be performed provided there are sufficient free Blocks available in the flash memory;

f) if the variable reqFileReadWrite is set and if there is insufficient free Blocks on the flash memory, suspending the file operation until the reclamation is finished;

g) if the variable reqFileReadWrite is not set, continuing the relocation of the file blocks one after another until all blocks of the file in the one targeted Erase Unit have been relocated to the free Erase Unit;

h) repeating b) to e) for all files in the one targeted Erase Unit;

i) when all file blocks have been re-located from the one targeted Erase Unit, erasing the one targeted Erase Unit; and

,

j) after the erasure, locking the semaphore and updating free, dirty, and bad block map data for the new state of the one targeted Erase Unit.

19. The method of claim 17 wherein the reclaiming of the targeted Erase Units comprises:

a) locating a Master Control Erase Unit targeted for reclamation;

b) relocating Erase Unit related data in the targeted Master Control Erase Unit after linking the targeted Master Control Erase Unit to a To-B-Next Master Control Erase Unit, wherein the relocated Erase Unit related data includes free, dirty, and bad block maps, and an Erase Unit Health map on the flash memory, wherein the Erase Unit related data comprises;

struct stEuInfoOnFlash{DWORD dEuNo;

DWORD dEUHealth;

BYTE 

 

bEuMap[MAP_SIZE];

}

wherein MAP_SIZE comprises a macro assigned with a value to represent the free Block map, the dirty Block map, and the bad Block map, wherein the relocating of Erase Unit related data includes relocating a Master Block of the targeted Master Control Erase Unit, and wherein the Master Block contains file system information;

c) acquiring a semaphore, moving one block corresponding to the Erase Unit related data from the target Master Control Erase Unit to the To-Be-Next Master Control Erase Unit, updating the Erase Unit related data in the Master Control Erase Unit so that any updates due to file operations involve changes to the relocated Blocks in the To-Be-Next Master Control Erase Unit, and releasing the semaphore;

d) repeating c) until all Blocks have been re-located;

e) locking the semaphore, updating partition information to change the Master Control Erase Unit from the targeted Master Control Erase Unit to the To-Be-Next Master Control Erase Unit, and releasing the semaphore;

f) erasing the targeted Master Control Erase Unit and updating free, dirty, Erase Unit Health, and bad maps appropriately;

g) identifying a free Erase Unit to act as the To-Be-Next Master Control Erase Unit and updating the partition information; and

,

h) updating the free map corresponding to the To-Be-Next Master Control Erase Unit to mark all Blocks within the To-Be-Next Master Control Erase Unit as used to prevent storing file data in the Blocks of the To-Be-Next Master Control Erase Unit.

20. The method of claim 19 wherein the reclaiming of the targeted Erase Units comprises:

a) locating files in one of the targeted Erase Units on an Extent by Extent basis by use of Erase Unit Information contained in a Master Control Erase Unit;

b) acquiring a semaphore/mutex and locking a file containing the file data by setting a variable in an Incore Inode stored in the RAM;

c) moving one file block from the one targeted Erase Unit to a free Erase Unit and determining if a file operation on the file is to be performed by checking a reqFileReadWrite variable in the Incore Inode;

d) if an Inode is present in the one targeted Erase Unit, updating the Incore Inode after relocation of the Inode before releasing a file lock in the Incore Inode;

e) if the variable reqFileReadwrite is set, releasing the file lock to allow the file operation to be performed provided there are sufficient free Blocks available in the flash memory;

f) if the variable reqFileReadWrite is set and if there is insufficient free Blocks on the flash memory, suspending the file operation until the reclamation is finished;

g) if the variable reqFileReadWrite is not set, continuing the relocation of the file blocks one after another until all blocks of the file in the one targeted Erase Unit have been relocated to the free Erase Unit;

h) repeating b) to e) for all files in the one targeted Erase Unit;

i) when all file blocks have been re-located from the one targeted Erase Unit, erasing the one targeted Erase Unit; and

,

j) after the erasure, locking the semaphore and updating free, dirty, and bad block map data for the new state of the one targeted Erase Unit.

21. A method of selecting for reclamation an Erase Unit from among a plurality of Erase Units of a flash memory comprising:

inspecting information of a Master Control Erase Unit;

selecting the Erase Unit for reclamation based on the inspected information; and

,

reclaiming the Erase Unit selected for reclamation even though free Erase Units exist on the flash memory sufficient to support a file operation.

22. The method of claim 21 wherein the selecting of the Erase Unit for reclamation comprises selecting a most worn one of the Erase Units as the Erase to be reclaimed if there are free Erase Units and the most worn Erase Unit has exceeded a threshold of minimum to maximum limit of erasures.

23. The method of claim 21 wherein the selecting of the Erase Unit for reclamation comprises selecting a dirtiest one of the Erase Units as the Erase to be reclaimed if the Erase to be reclaimed is more than 75% dirty.

24. The method of claim 23 wherein the selecting of the Erase Unit for reclamation comprises selecting a most worn one of the Erase Units as the Erase to be reclaimed if there are free Erase Units and the most worn Erase Unit has exceeded a threshold of minimum to maximum limit of erasures.

25. The method of claim 21 wherein the selecting of the Erase Unit for reclamation comprises:

selecting a Master Control Erase Unit of the flash memory for reclamation if the Master Control Erase Unit is full;

selecting a dirtiest one of the Erase Units as the Erase Unit to be reclaimed if there are no free Erase Units;

selecting a most worn one of the Erase Units as the Erase to be reclaimed if there are free Erase Units and the most worn Erase Unit has exceeded a threshold of minimum to maximum limit of erasures; and

,

selecting a dirtiest one of the Erase Units as the Erase to be reclaimed if the Erase to be reclaimed is more than 75% dirty.