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

• US 7,831,783 B2
• Filed: 12/22/2005
• Issued: 11/09/2010
• Est. Priority Date: 12/22/2005
• Status: Expired due to Fees

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Sampath, Sridhar, Pandit, Anil Kumar
• Primary Examiner(s): Elmore; Stephen C
• Assistant Examiner(s): Rojas; Midys
• Application Number:
  US11/317,467
• Publication Number:
  US 20070150689A1
• Time in Patent Office: 1,783 Days
• Field of Search: 711/59, 711/6, 711/103, 711/113, 711/133, 711/156, 711/159, 711/165
• US Class Current: 711/159
• 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 reclaiming targeted Erase Units from a plurality of erase units of a flash memory comprising:

when there are free erase units in the plurality of erase units, identifying the targeted Erase Units based on the number of erasures of an Erase Unit and a wear-leveling threshold, the targeted Erase Units having a number of erasures that exceed the wear-leveling threshold, wherein the wear-leveling threshold is a maximum difference in the number of erasures between the Erase Unit having the most erasures and the Erase Unit having the least erasures; and

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

2. The method of claim 1 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 at least one of a semaphore and a 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 Block 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 at least one of a semaphore and a mutex and updating free, dirty, and bad block map data for the new state of the one targeted Erase Unit.

3. The method of claim 1 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 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 relocated;

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 to mark all Blocks within the To-Be-Next Master Control Erase Unite as used to prevent storing file data in the blocks of the to-be-next Master Control Erase Unit.

4. The method of claim 3 wherein the reclaiming of the targeted Erase Units comprises:

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

b) acquiring at least one of a semaphore and a mutex and locking a file containing the file data by setting a variable in an Incore Inode stored in 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 reqRileReadWrite 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 at least one of a semaphore and a mutex and updating free, dirty, and bad block map data for the new state of the one targeted Erase Unit.

5. The method of claim 1 wherein the identifying of the targeted Erase Units comprises:

creating an Erase Unit Information table in a RAM, 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.

6. The method of claim 5 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 at least one of a semaphore and a 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 on after another until all block of the file in the one targeted Erase Unite 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 Unite, erasing the one targeted Erase Unit, and,

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

7. The method of claim 5 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-Be-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 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 relocated;

e) locking the semaphore, updating partition information to change the Master Control Erase Unit form the targeted 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 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.

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.

8. The method of claim 7 wherein the reclaiming of the targeted Erase Units comprises:

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

b) acquiring at least one of a semaphore and a 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 on after another until all blocks of the file in the one targeted Erase Unite 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 form the one targeted Erase Unit, erasing the one targeted Erase Unit; and

,

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

9. 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, wherein an Erase Unit is selected as the Erase Unit to be reclaimed if there are free Erase Units and a number of erasures of the Erase Unit has exceeded a threshold, wherein the threshold is a maximum difference between the number of erasures of the Erase Unit having the most erasures and the number of erasures of the Erase Unit having the least erasures; and

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

10. The method of claim 9 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.

11. The method of claim 9 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 on 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 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.