Method and system for managing bad areas in flash memory

• US 6,260,156 B1
• Filed: 12/04/1998
• Issued: 07/10/2001
• Est. Priority Date: 12/04/1998
• Status: Expired due to Term

• Current Assignee: Datalight Incorporated (Tuxera Oy)
• Original Assignee: Datalight Incorporated (Tuxera Oy)
• Inventors: Stanard, H. Duane, Garvin, P. Keith
• Primary Examiner(s): Ray, Gopal C.
• Application Number:
  US09/205,806
• Time in Patent Office: 949 Days
• Field of Search: 714/8, 714/710, 714/3, 714/5, 714/7, 714/711, 711/202, 711/205, 711/206, 711/207, 711/103, 711/170, 360/48, 360/53, 365/218
• US Class Current: 714/6.13
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory

Abstract

A method, system and computer-readable medium for managing bad areas in flash memory. The flash memory is initialized by formatting the flash memory into a spare area and a data area with the spare area and the data area including a plurality of spare blocks and data blocks, respectively. In addition, spare blocks are grouped together forming a chunk. A working chunk map is created for storing format information and re-mapping information. The working chunk map includes a BBM header and a plurality of BBM entries that correspond to the spare blocks in each chunk. The working chunk map is written to one of the plurality of spare blocks in a chunk, designated as a copy chunk map. The working chunk map is also written to another one of the plurality of spare blocks in a chunk, designated as an original chunk map.

Claims

1. A method for managing bad areas in flash memory, the method comprising:

(a) formatting the flash memory into a data area and a spare area, each area having a plurality of blocks, wherein the blocks in the data area are data blocks and the blocks in the spare area are spare blocks and wherein any data block and spare block having a bad area in flash memory is considered to be a bad block;

(b) grouping the spare blocks within the spare area into a plurality of chunks;

(c) for each of the plurality of chunks in the spare area,

(1) storing an original chunk map in at least one spare block within each chunk;

(2) storing a copy chunk map in at least one other spare block within each chunk; and

(d) for each bad block, mapping content of the bad block to an available spare block in an available chunk by updating the original chunk map and the copy chunk map associated with the available spare block.

2. The method of claim 1, wherein storing the original chunk map in the at least one spare block comprises:

(a) creating a working chunk map having a header, wherein the header includes a status field and a number representing the number of data blocks in the data area available for storing data; and

(b) writing the header of the working chunk map into the at least one spare block of at least one chunk on the flash memory.

3. The method of claim 2, wherein storing the original chunk map in the at least one spare block further comprises storing a first identifier in the status field before writing the header.

4. The method of claim 2, wherein storing the copy chunk map in the at least one other spare block comprises:

(a) storing a second identifier in the status field of the working chunk map; and

(b) writing the header of the working chunk map into the at least one other spare block on the flash memory.

5. The method of claim 2, wherein the copy chunk map and the original chunk map comprise a plurality of entries that correspond to the plurality of spare blocks in one of the plurality of chunks.

6. The method of claim 5, wherein mapping the content of the bad block to the available spare block comprises:

(a) finding an available free entry in the plurality of entries in the spare area;

(b) creating a free entry working chunk map; and

(c) updating the original chunk map and the copy chunk map associated with the available free entry.

7. The method of claim 6, wherein creating the free entry working chunk map comprises:

(a) reading the original chunk map associated with the available free entry; and

(b) copying content of the original chunk map associated with the available free entry into the free entry working chunk map.

8. The method of claim 6, wherein finding an available free entry in the plurality of entries comprises searching through the original chunk maps.

9. The method of claim 6, wherein finding an available free entry in the plurality of entries comprises searching through the copy chunk maps.

10. The method of claim 6, wherein updating the original chunk map and the copy chunk map associated with the available free entry comprises:

(a) writing a block number associated with the bad block into the available free entry of the free entry working chunk map;

(b) erasing the spare block storing the original chunk map associated with the available free entry, writing the free entry working chunk map as the original chunk map in the spare block that was previously erased and writing a first indicator to the original chunk map on the flash memory associated with the available free entry;

(c) erasing the spare block storing the copy chunk map associated with the available free entry, writing the free entry working chunk map into the spare block that was previously erased of the copy chunk map; and

(d) writing a second indicator to the original chunk map on the flash memory associated with the available free entry.

11. The method of claim 10, wherein writing the block number associated with the bad block into the available free entry of the working chunk map comprises determining whether the block number references one of the data blocks;

if so, writing a data block number into the available free entry that corresponds to the bad block;

otherwise, if the block number references a spare block number, writing into the available free entry the bad data block number corresponding to the bad data block that was previously mapped.

12. The method of claim 10, wherein if the bad block is in the spare area, the method further comprises:

(1) reading the original chunk map associated with the bad block;

(2) creating a second working chunk map containing contents of the original chunk map associated with the bad block;

(3) finding a first entry in the second working chunk map that corresponds to the bad block; and

(4) updating the original chunk map and copy chunk map associated with the bad block;

wherein (1)-(4) are completed before (c) and (d) of claim 10.

13. The method of claim 12, wherein updating the original chunk map and copy chunk map associated with the bad block comprises:

(a) writing a bad indicator in the first entry;

(b) erasing the spare block associated with the bad block and writing the second working chunk map as the original chunk map;

(c) writing a status copy invalid indicator in the original chunk map on the flash memory associated with the chunk containing the bad block;

(d) erasing the spare block containing the copy chunk map associated with the bad block and writing the second working chunk map as the copy chunk map; and

(e) writing a status copy valid indicator in the original chunk map on the flash memory associated with the bad block.

14. The method of claim 6, further comprising marking the entry associated with the bad block in the free entry working chunk map if the bad block is within the available chunk.

15. The method of claim 6, further comprising copying valid content of the bad block to the available spare block.

16. The method of claim 1, further comprising validating the original chunk map and the copy chunk map associated with the available spare block.

17. The method of claim 16, wherein validating the original chunk map and the copy chunk map associated with the available spare blocks comprises moving the original chunk map and the copy chunk map associated with the available spare chunk when either the original chunk map or the copy chunk map is in the bad block.

18. The method of claim 17, wherein moving the original chunk map and the copy chunk map associated with the available spare chunk comprises:

(a) if the copy chunk map is in the bad block, copying the contents of the original chunk map associated with the available spare block to a second working chunk map;

else, copying the contents of the copy chunk map associated with the available spare block to the second working chunk map;

(b) locating a first available spare block and a second available spare block within the available chunk;

(c) writing an allocated status in the second working chunk map that corresponds to the first available spare block and the second available spare block;

(d) writing the second working chunk map to one of the first and second available spare blocks and designating the written available spare block as the moved original chunk map;

(e) writing the second working chunk map to the other available spare block and designating the other available spare block as the moved copy chunk map; and

(f) updating status for the original chunk map and the copy chunk map.

19. The method of claim 18, wherein updating status for the original chunk map and the copy chunk map comprises:

(a) writing an invalid status in the original chunk map; and

(b) writing the invalid status in the copy chunk map.

20. The method of claim 18, wherein locating the first available spare block and the second available spare block comprises searching a predetermined number of consecutive spare blocks in the available chunk for the first available spare block.

21. The method of claim 1, wherein the original chunk map and the copy chunk map are stored in a next chunk when the available spare block does not exist in a current chunk.

22. The method of claim 1, further comprising providing a location to a flash file system for a requested data block.

23. The method of claim 22, wherein providing the location comprises:

(a) scanning content in the original chunk map for the block number associated with the requested data block; and

(b) if found, providing the spare block number that corresponds to the entry storing a requested block number;

otherwise, providing the requested data block number.

24. The method of claim 1, wherein the spare blocks and the data blocks are equally sized.

25. The method of claim 1, wherein the spare area is contiguous and sized smaller than the data area.

26. The method of claim 1, wherein the spare area is sized proportional to a reliability factor of the flash memory.

27. A computer-readable medium having computer executable components for managing bad areas in flash memory, the computer-readable medium having computer-executable components comprising:

(a) a formatting component for formatting the flash memory into a data area and a spare area, each area having a plurality of blocks, wherein the blocks in the data area are data blocks and the blocks in the spare area are spare blocks, wherein any data block and spare block having bad areas in flash memory are considered to be bad blocks and wherein the spare blocks within the spare area are grouped into a plurality of chunks; and

(b) a mapping component for mapping content of a bad block to an available spare block by updating an original chunk map and a copy chunk map associated with the available spare block.

28. The computer-readable medium of claim 27, wherein the formatting component formats the flash memory by storing the original chunk map in the at least one spare block within each chunk and storing a copy chunk map in at least one other spare block within each chunk.

29. The computer-readable medium of claim 28, wherein the formatting component stores the original chunk map by:

(a) creating a working chunk map having a header, wherein the header includes a status field and a number representing the number of data blocks in the data area available for storing data; and

(b) writing the header of the working chunk map into the at least one spare block of at least one chunk on the flash memory.

30. The computer-readable medium of claim 29, wherein the formatting component further stores the original chunk map in the at least one spare block by storing a first identifier in the status field before writing the header.

31. The computer-readable medium of claim 29, wherein the formatting component stores the copy chunk map in the at least one other spare block by:

(a) storing a second identifier in the status field of the working chunk map; and

(b) writing the header of the working chunk map into the at least one other spare block on the flash memory.

32. The computer-readable medium of claim 29, wherein the mapping component maps the content of the bad block to the available spare block by:

(a) finding an available free entry in the plurality of entries in the spare area;

(b) creating a free entry working chunk map; and

(c) updating the original chunk map and the copy chunk map associated with the available free entry by modifying the free entry working chunk map and writing the free entry working chunk map to the flash memory as the original chunk map and as the copy chunk map.

33. The computer-readable medium of claim 32, wherein the mapping component creates the free entry working chunk map by:

(a) reading the original chunk map associated with the available free entry; and

(b) copying content of the original chunk map associated with the available free entry into the free entry working chunk map.

34. The computer-readable medium of claim 32, wherein the mapping component updates the original chunk map and the copy chunk map associated with the available free entry by:

(a) writing a block number associated with the bad block into the available free entry of the free entry working chunk map;

(b) erasing the spare block storing the original chunk map associated with the available free entry, writing the free entry working chunk map as the original chunk map in the spare block that was previously erased and writing a first indicator to the original chunk map on the flash memory associated with the available free entry;

(c) erasing the spare block storing the copy chunk map associated with the available free entry, writing the free entry working chunk map into the spare block that was previously erased of the copy chunk map; and

(d) writing a second indicator to the original chunk map on the flash memory associated with the available free entry.

35. The computer-readable medium of claim 34, wherein the mapping component writes the block number associated with the bad block into the available free entry of the working chunk map by determining whether the block number references one of the data blocks;

if so, writing a data block number into the available free entry that corresponds to the bad block;

otherwise, if the block number references a spare block number, writing into the available free entry the bad data block number corresponding to the bad data block that was previously mapped.

36. The computer-readable medium of claim 34, wherein if the bad block is in the spare area, the mapping component further updates the original chunk map and the copy chunk map associated with the bad block by:

(1) reading the original chunk map associated with the bad block;

(2) creating a second working chunk map containing contents of the original chunk map associated with the bad block;

(3) finding a first entry in the second working chunk map that corresponds to the bad block; and

(4) updating the original chunk map and copy chunk map associated with the bad block;

wherein (1)-(4) are completed before (c) and (d) of claim 34.

37. The computer-readable medium of claim 36, wherein the mapping component updates the original chunk map and copy chunk map associated with the bad block by:

(a) writing a bad indicator in the first entry;

(b) erasing the spare block associated with the bad block and writing the second working chunk map as the original chunk map;

(c) writing a status copy invalid indicator in the original chunk map on the flash memory associated with the chunk containing the bad block;

(d) erasing the spare block containing the copy chunk map associated with the bad block and writing the second working chunk map as the copy chunk map; and

(e) writing a status copy valid indicator in the original chunk map on the flash memory associated with the bad block.

38. The computer-readable medium of claim 32, wherein the mapping component further maps the content of the bad block by marking the entry associated with the bad block in the free entry working chunk map if the bad block is within the available chunk.

39. The computer-readable medium of claim 32, wherein the mapping component further maps the content of the bad block by copying valid content of the bad block to the available spare block.

40. The computer-readable medium of claim 28, wherein the mapping component further maps the content of the bad block by validating the original chunk map and the copy chunk map associated with the available spare block.

41. The computer-readable medium of claim 40, wherein the mapping component validates the original chunk map and the copy chunk map associated with the available spare block by moving the original chunk map and the copy chunk map associated with the available spare chunk when either the original chunk map or the copy chunk map is in the bad block.

42. The computer-readable medium of claim 41, wherein the mapping component moves the original chunk map and the copy chunk map associated with the available spare chunk by:

(a) if the copy chunk map is in the bad block, copying the contents of the original chunk map associated with the available spare block to a second working chunk map;

else, copying the contents of the copy chunk map associated with the available spare block to the second working chunk map;

(b) locating a first available spare block and a second available spare block within the available chunk;

(c) writing an allocated status in the second working chunk map that corresponds to the first available spare block and the second available spare block;

(d) writing the second working chunk map to one of the first and second available spare blocks and designating the written available spare block as the moved original chunk map and writing the second working chunk map to the other available spare block and designating the other available spare block as the moved copy chunk map; and

(e) updating status for the original chunk map and the copy chunk map.

43. The computer-readable medium of claim 42, wherein the mapping component updates the status for the original chunk map and the copy chunk map by:

(a) writing an invalid status in the original chunk map; and

(b) writing the invalid status in the copy chunk map.

44. The computer-readable medium of claim 42, wherein locating the first available spare block and the second available spare block comprises searching a predetermined number of consecutive spare blocks in the available chunk for the first available spare block.

45. The computer-readable medium of claim 28, further comprising a locator component for providing a location to a flash file system for a requested data block.

46. The computer-readable medium of claim 45, wherein the locator component provides the location by:

(a) scanning content in the original chunk map for the block number associated with the requested data block; and

(b) if found, providing the spare block number that corresponds to the entry storing a requested block number;

otherwise, providing the requested data block number.

47. An apparatus for managing bad areas in flash memory, the apparatus comprising:

(a) a processing unit;

(b) a flash memory coupled to the processing unit, the flash memory comprising a data area and a spare area, wherein the data area includes a plurality of data blocks and the spare area includes a plurality of spare blocks, wherein any data block and spare block having a bad area in the flash memory is considered to be a bad block and wherein the spare blocks within the spare area are grouped into a plurality of chunks; and

(c) a primary memory coupled to the processing unit, the primary memory storing instructions that control, execution of the instructions on the processing unit comprising;

(i) storing an original chunk map in at least one spare block within each chunk;

(ii) storing a copy chunk map in at least one other spare block within each chunk; and

(iii) mapping content of the bad block to an available spare block in an available chunk by updating the original chunk map and the copy chunk map associated with the available spare block.

48. The apparatus of claim 47, wherein storing the original chunk map and the copy chunk map comprises:

(a) creating a working chunk map having a header, wherein the header includes a status field and a number representing the number of data blocks in the data area available for storing data;

(b) writing a portion of the working chunk map into the at least one spare block of the chunk on the flash memory; and

(c) writing a portion of the working chunk map into the at least one other spare block on the flash memory.

49. The method of claim 47, wherein the copy chunk map and the original chunk map comprise a plurality of entries that correspond to the plurality of spare blocks in one of the plurality of chunks.

50. The apparatus of claim 49, wherein mapping the content of the bad block to the available spare block comprises:

(a) finding an available free entry in the plurality of entries in the spare area;

(b) creating a free entry working chunk map; and

(c) updating the original chunk map and the copy chunk map associated with the available free entry.

51. The apparatus of claim 50, wherein creating the free entry working chunk map comprises:

(a) reading the original chunk map associated with the available free entry; and

(b) copying content of the original chunk map associated with the available free entry into the free entry working chunk map.

52. The apparatus of claim 51, wherein updating the original chunk map and the copy chunk map associated with the available free entry comprises:

(a) writing a block number associated with the bad block into the available free entry of the free entry working chunk map;

(b) erasing the spare block storing the original chunk map associated with the available free entry, writing the free entry working chunk map as the original chunk map in the spare block that was previously erased and writing a first indicator to the original chunk map on the flash memory associated with the available free entry;

(c) erasing the spare block storing the copy chunk map associated with the available free entry, writing the free entry working chunk map into the spare block that was previously erased of the copy chunk map; and

(d) writing a second indicator to the original chunk map on the flash memory associated with the available free entry.

53. The apparatus of claim 52, wherein writing the block number associated with the bad block into the available free entry of the working chunk map comprises determining whether the block number references one of the data blocks;

if so, writing a data block number into the available free entry that corresponds to the bad block;

otherwise, if the block number references a spare block number, writing into the available free entry the bad data block number corresponding to the bad data block that was previously mapped.

54. The apparatus of claim 53, wherein if the bad block is in the spare area, the method further comprises:

(1) reading the original chunk map associated with the bad block;

(2) creating a second working chunk map containing contents of the original chunk map associated with the bad block;

(3) finding a first entry in the second working chunk map that corresponds to the bad block; and

(4) updating the original chunk map and copy chunk map associated with the bad block;

wherein (1)-(4) are completed before (c) and (d) of claim 52.

55. The apparatus of claim 54, wherein updating the original chunk map and copy chunk map associated with the bad block comprises:

(a) writing a bad indicator in the first entry;

(b) erasing the spare block associated with the bad block and writing the second working chunk map as the original chunk map;

(c) writing a status copy invalid indicator in the original chunk map on the flash memory associated with the chunk containing the bad block;

(d) erasing the spare block containing the copy chunk map associated with the bad block and writing the second working chunk map as the copy chunk map; and

(e) writing a status copy valid indicator in the original chunk map on the flash memory associated with the bad block.

56. The apparatus of claim 55, further comprising marking the entry associated with the bad block in the free entry working chunk map if the bad block is within the available chunk.

57. The apparatus of claim 56, further comprising copying valid content of the bad block to the available spare block.