Page based management of flash storage

• US 20110055458A1
• Filed: 09/03/2009
• Published: 03/03/2011
• Est. Priority Date: 09/03/2009
• Status: Active Grant

• Current Assignee: Pioneer Chip Technology, Ltd.
• Original Assignee: 248 Solid State, Inc.
• Inventors: Kuehne, Reinhard
• Granted Patent: US 8,688,894 B2
• Time in Patent Office: Days
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/123 with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
• CPC Class Codes: G06F 2212/7203 Temporary buffering, e.g. using volatile buffer or dedicated buffer blocks
• CPC Class Codes: G06F 2212/7208 Multiple device management, e.g. distributing data over multiple flash devices

Abstract

Methods and circuits for page based management of an array of Flash RAM nonvolatile memory devices provide paged base reading and writing and block erasure of a flash storage system. The memory management system includes a management processor, a page buffer, and a logical-to-physical translation table. The management processor is in communication with an array of nonvolatile memory devices within the flash storage system to provide control signals for the programming of selected pages, erasing selected blocks, and reading selected pages of the array of nonvolatile memory devices.

Claims

1. A data storage system comprising:

an array of nonvolatile memory devices comprising multiple blocks of sub-arrays that are comprising a plurality of sub-blocks where each sub-block comprises a plurality of sectors and each sectors comprising a plurality of bytes of memory cells;

a management processor in communication with the array of nonvolatile memory devices to provide control signals for the programming of selected sub-blocks, erasing selected blocks, and reading selected sub-blocks of the array of nonvolatile memory devices;

a sub-block buffer in communication with the array of nonvolatile memory devices and the management processor and partitioned into sub-block segments for temporarily storing sub-blocks of data that is read from or to be transferred to the array of nonvolatile memory devices as determined by control signals received from the management processor; and

a logical-to-physical translation table that receives a requested logical sub-block address and translates the logical sub-block address to a physical sub-block address and in communication with the management processor to transfer the physical sub-block address to the management processor for identifying a physical location of a desired sub-block within the array of nonvolatile memory devices, wherein the logical-to-physical translation table comprises a cache flag table identifying if the requested logical sub-block address is present in the sub-block buffer.

2. The data storage system of claim 1 wherein the sub-block is a page, a super-page composed of single blocks within multiple array of nonvolatile memory devices, or super page composed of multiple pages with a block.

3. The data storage system of claim 1 further comprising an input/output adapter connected between an external port and the sub-block buffer and the management processor to receive the logical address, control, and sectors of data encoded in a communication format and translating the logical address, control, and data encoded in the communication format to a format acceptable by the array of nonvolatile memory devices.

4. The data storage system of claim 3 further comprising a physical address decoder in communication with the input/output adapter to receive the logical address, in communication with the logical-to-physical translation table to transmit the logical address to the logical-to-physical translation table and receive the physical address from the logical-to-physical translation table, and in communication with the management processor to identify that a requested sub-block of data is resident in the sub-block buffer or the array of nonvolatile memory devices.

5. The data storage system of claim 4 further comprising sub-block buffer cache table in communication the management processor and comprising a physical sub-block number identifying a physical location within the array of nonvolatile memory devices associated with a sub-block location within the sub-block buffer, a cache type entry designating a cache type occupied by the physical location, and a status entry classifying the sectors of the sub-block of data according to a validity status.

6. The data storage system of claim 5 wherein the cache types comprise a read cache, streaming cache, write cache, and free list.

7. The data storage system of claim 5 further comprising a least-recently-used table comprising chaining pointers for determining a least recently used sub-block of data resident in the sub-block buffer.

8. The data storage system of claim 7 where during an eviction process of the sub-block buffer by the management processor, the least recently used sub-block of data resident in the sub-block buffer is evicted from the sub-block buffer and written to its designated sub-block within the array of nonvolatile memory devices and the sub-block location within the sub-block buffer is added to the free list of the sub-block buffer cache table.

9. The data storage system of claim 1 further comprising an invalid sub-block table indicating which sub-blocks with selected block of the array of nonvolatile memory devices are valid.

10. The data storage system of claim 1 further comprising a physical-to-logical table for mapping the physical location of the array of nonvolatile memory devices to the logical location wherein an illegal sub-block number indicates that the physical location is erased or invalid.

11. The data storage system of claim 1 further comprising an erase count table in communication with the management processor to maintain an erase count for each block of the array of nonvolatile memory devices.

12. The data storage system of claim 1 further comprising a physical block chain table in communication with the management processor and comprising a linked listing containing pointers for each block of the array of nonvolatile memory devices containing an anchor pointer defining the number of invalid sub-blocks within the block.

13. The data storage system of claim 11 wherein during a garbage collection process of the array of nonvolatile memory devices executed by the management processor, the anchor pointer indicates the block of the array of nonvolatile memory devices having the highest number of invalid sub-blocks and thus permits selection of the block with the highest number of invalid sub-blocks for erasure.

14. The data storage system of claim 13 wherein during a wearleveling process an erased block has its erasure count compared to a maximum count and if the maximum count is exceeded, a block having a lowest erased count is selected and all valid sub-blocks are copied to the low order sub-blocks of the erased block, the block with the lowest erase count is erased, and the newly erased block has its erasure count incremented and it becomes a new spare block available for writing.

15. A memory management circuit for sub-blocked base reading and writing and block erasure of a flash storage system, wherein the memory management circuit comprises:

a management processor in communication with an array of nonvolatile memory devices within the flash storage system to provide control signals for the programming of selected sub-blocks, erasing selected blocks, and reading selected sub-blocks of the array of nonvolatile memory devices;

a sub-block buffer in communication with the array of nonvolatile memory devices and the management processor and partitioned into sub-block segments for temporarily storing sub-blocks of data that are read from or to be transferred to the array of nonvolatile memory devices as determined by control signals received from the management processor; and

a logical-to-physical translation table that receives a requested logical sub-block address and translates the logical sub-block address to a physical sub-block address and in communication with the management processor to transfer the physical sub-block address to the management processor for identifying a physical location of a desired sub-block within the array of nonvolatile memory devices, wherein the logical-to-physical translation table comprises a cache flag table identifying if the requested logical sub-block address is present in the sub-block buffer.

16. The memory management circuit of claim 15 wherein the sub-block is a page, a super-page composed of single blocks within multiple array of nonvolatile memory devices, or super page composed of multiple pages with a block.

17. The memory management circuit of claim 15 further comprising an input/output adapter connected between an external port and the sub-block buffer and the management processor to receive the logical address, control, and sectors of data encoded in a communication format and translating the logical address, control, and data encoded in the communication format to a format acceptable by the array of nonvolatile memory devices.

18. The memory management circuit of claim 16 further comprising a physical address decoder in communication with the input/output adapter to receive the logical address, in communication with the logical-to-physical translation table to transmit the logical address to the logical-to-physical translation table and receive the physical address from the logical-to-physical translation table, and in communication with the management processor to identify that a requested sub-block of data is resident in the sub-block buffer or the array of nonvolatile memory devices.

19. The memory management circuit of claim 18 further comprising a sub-block buffer cache table in communication the management processor and comprising a physical sub-block number identifying a physical location within the array of nonvolatile memory devices associated with a sub-block location within the sub-block buffer, a cache type entry designating a cache type occupied by the physical location, and a status entry classifying the sectors of the sub-block of data according to a validity status.

20. The memory management circuit of claim 19 wherein the cache types comprise a read cache, streaming cache, write cache, and free list.

21. The memory management circuit of claim 19 further comprising a least-recently-used table comprising chaining pointers for determining a least recently used sub-block of data resident in the sub-block buffer.

22. The memory management circuit of claim 21 where during an eviction process of the sub-block buffer by the management processor, the least recently used sub-block of data resident in the sub-block buffer is evicted from the sub-block buffer and written to its designated sub-block within the array of nonvolatile memory devices and the sub-block location within the sub-block buffer is added to the free list of the sub-block buffer cache table.

23. The memory management circuit of claim 16 further comprising an invalid sub-block table indicating which sub-blocks with selected block of the array of nonvolatile memory devices are valid.

24. The memory management circuit of claim 16 further comprising a physical-to-logical table for mapping the physical location of the array of nonvolatile memory devices to the logical location wherein an illegal sub-block number indicates that the physical location is erased or invalid.

25. The memory management circuit of claim 16 further comprising an erase count table in communication with the management processor to maintain an erase count for each block of the array of nonvolatile memory devices.

26. The memory management circuit of claim 16 further comprising a physical block chain table in communication with the management processor and comprising a linked listing containing pointers for each block of the array of nonvolatile memory devices containing an anchor pointer defining the number of invalid sub-blocks within the block.

27. The memory management circuit of claim 25 wherein during a garbage collection process of the array of nonvolatile memory devices executed by the management processor, the anchor pointer indicates the block of the array of nonvolatile memory devices having the highest number of invalid sub-blocks and thus permits selection of the block with the highest number of invalid sub-blocks for erasure.

28. The memory management circuit of claim 27 wherein during a wearleveling process an erased block has its erasure count compared to a sliding window erase count and if the sliding window erase count is exceeded, a block having a lowest block erase count is selected and all valid sub-blocks are copied to the low order sub-blocks of the erased block, the block with the lowest block erase count is erased, and the newly erased block has its erasure count incremented and it becomes a new spare block available for writing.

29. The memory management circuit of claim 28 wherein during the wearleveling process the sliding window erase count is calculated as the lowest block erase count plus a block erase count threshold value.

30. A method for managing a flash storage system that is comprised of an array of nonvolatile memory devices, wherein the method for managing the flash storage system comprises the steps of:

reading or writing a sub-block from or to an array of nonvolatile memory devices within the flash storage system by the steps of;

a) decoding a logical address of the sub-block,

b) accessing the logical address in a logical-to-physical translation table to determine if the sub-block is resident in a sub-block buffer cache,

c) if the sub-block is resident in the sub-block buffer cache, reading or writing the sub-block from or to the sub-block buffer cache,

d) if the sub-block is not resident in the sub-block buffer cache, determining if the sub-block buffer cache has a free sub-block,

e) if there is a free sub-block, assigning the logical address to be read or written to the free sub-block of the sub-block buffer cache,

reading the sub-block from the array of nonvolatile devices to the assigned free sub-block and reading assigned free sub-block;

or

writing the sub-block to the assigned free sub-block,

f) if there is not a free sub-block, evicting a least recently used sub-block from the sub-block buffer cache to create a free sub-block, and

g) performing step e) to read or write the sub-block from or to the assigned free sub-block.

31. The method for managing a flash storage of claim 30 wherein the sub-block is a page, a super-page composed of single blocks within multiple array of nonvolatile memory devices, or super page composed of multiple pages with a block.

32. The method for managing a flash storage of claim 30 further comprising steps of:

receiving the logical address, control data, and the sub-block as sectors of data encoded in a communication format; and

translating the logical address, control, and data encoded in the communication format to a format acceptable by the array of nonvolatile memory devices.

33. The method for managing a flash storage of claim 32 further comprising step of maintaining sub-block buffer cache table comprising a physical sub-block number identifying a physical location within the array of nonvolatile memory devices associated with a sub-block location within the sub-block buffer, a cache type entry designating a cache type occupied by the physical location, and a status entry classifying the sectors of the sub-block of data according to a validity status.

34. The method for managing a flash storage of claim 33 wherein the cache types comprise a read cache, streaming cache, write cache, and free list.

35. The method for managing a flash storage of claim 33 wherein evicting the least recently used sub-block from the sub-block buffer cache to create a free sub-block comprises the steps of:

querying a least-recently-used table comprising chaining pointers; and

from the chaining pointers, determining a least recently used sub-block of data resident in the sub-block buffer.

36. The method for managing a flash storage of claim 35 wherein evicting the least recently used sub-block from the sub-block buffer cache to create a free sub-block further comprises the step of:

writing the least recently used sub-block to its designated sub-block within the array of nonvolatile memory devices and the sub-block location within the sub-block buffer is added to the free list of the sub-block buffer cache table.

37. The method for managing a flash storage of claim 36 wherein writing the sub-block to the assigned free sub-block of the sub-block buffer cache comprises the step of:

setting a sub-block bit of the block of the sub-block being written as invalid in an invalid sub-block table indicating which sub-blocks with selected block of the array of nonvolatile memory devices are valid or invalid.

38. The method for managing a flash storage of claim 35 wherein the evicting the least recently used sub-block from the sub-block buffer cache comprises the step of garbage collecting to create at least one free sub-block.

39. The method for managing a flash storage of claim 35 wherein garbage collecting to create at least one free sub-block comprises the steps of:

determining whether a number erased sub-blocks available within the array of nonvolatile devices has fallen below an erase sub-block threshold;

searching physical block chain table including a linked listing containing pointers for each block of the array of nonvolatile memory devices containing an anchor pointer defining the number of invalid sub-blocks within the block to find a block with maximum invalid sub-blocks;

determining whether all sub-blocks within the block with the maximum invalid sub-blocks are invalid;

if all the sub-blocks are not invalid, copying the valid sub-blocks to at least one other block in the array of nonvolatile memory devices and setting the sub-blocks as invalid in the invalid sub-block table;

when all the sub-blocks are invalid, erasing the block with the maximum invalid sub-blocks.

40. The method for managing a flash storage of claim 39 wherein garbage collecting to create at least one free sub-block further comprises the step of setting an illegal sub-block number to indicate that the physical location of the erased block is erased the physical location within a physical-to-logical table that maps the physical location of the array of nonvolatile memory devices to the logical location.

41. The method for managing a flash storage of claim 35 wherein evicting a least recently used sub-block from the sub-block buffer cache further comprises the step of wearleveling an erased block.

42. The method for managing a flash storage of claim 41 wherein wearleveling an erased block comprises the steps of:

determining a sliding window erase count as a function of a lowest block erase count;

determining if an erased block count of the erased block exceeds the sliding window erase count;

if the sliding window erase count is exceeded, searching an erasure count table to determine a block having the lowest block erase count;

selecting the block with the lowest block erase count; and

copying all valid sub-blocks of the block with the lowest block erase count to the low order sub-blocks of the erased block;

erasing the block with the lowest block erase count to become a newly erased block;

incrementing the erasure count in the erasure count table for the newly erased block; and

assigning the newly erase block as a new spare block available for writing.

43. The method for managing a flash storage of claim 42 wherein in wearleveling, the step of determining the sliding window erase count comprises a step of adding an erase count threshold value to the lowest block erase count.

44. A computer readable medium for retaining a computer program code which, when executed on a control processor, performs a computer program process for managing a flash storage, wherein the computer program process comprises the steps of:

reading or writing a sub-block from or to an array of nonvolatile memory devices within the flash storage system by the steps of;

a) decoding a logical address of the sub-block,

b) accessing the logical address in a logical-to-physical translation table to determine if the sub-block is resident in a sub-block buffer cache,

c) if the sub-block is resident in the sub-block buffer cache, reading or writing the sub-block from or to the sub-block buffer cache,

d) if the sub-block is not resident in the sub-block buffer cache, determining if the sub-block buffer cache has a free sub-block,

e) if there is a free sub-block, assigning the logical address to be read or written to the free sub-block of the sub-block buffer cache,

reading the sub-block from the array of nonvolatile devices to the assigned free sub-block and reading assigned free sub-block;

or

writing the sub-block to the assigned free sub-block,

f) if there is not a free sub-block, evicting a least recently used sub-block from the sub-block buffer cache to create a free sub-block, and

g) performing step e) to read or write the sub-block from or to the assigned free sub-block.

45. The computer readable medium for retaining a computer program code of claim 44 wherein the sub-block is a page, a super-page composed of single blocks within multiple array of nonvolatile memory devices, or super page composed of multiple pages with a block.

46. The computer readable medium for retaining a computer program code of claim 44 further comprising steps of:

receiving the logical address, control data, and the sub-block as sectors of data encoded in a communication format; and

translating the logical address, control, and data encoded in the communication format to a format acceptable by the array of nonvolatile memory devices.

47. The computer readable medium for retaining a computer program code of claim 46 wherein the computer program process further comprises the step of maintaining sub-block buffer cache table in communication the management processor and comprising a physical sub-block number identifying a physical location within the array of nonvolatile memory devices associated with a sub-block location within the sub-block buffer, a cache type entry designating a cache type occupied by the physical location, and a status entry classifying the sectors of the sub-block of data according to a validity status.

48. The computer readable medium for retaining a computer program code of claim 47 wherein the cache types comprise a read cache, streaming cache, write cache, and free list.

49. The computer readable medium for retaining a computer program code of claim 47 wherein evicting a least recently used sub-block from the sub-block buffer cache to create a free sub-block comprises the steps of:

querying a least-recently-used table comprising chaining pointers; and

from the chaining pointers, determining a least recently used sub-block of data resident in the sub-block buffer.

50. The computer readable medium for retaining a computer program code of claim 45 wherein evicting the least recently used sub-block from the sub-block buffer cache to create a free sub-block further comprises the step of:

writing the least recently used sub-block to its designated sub-block within the array of nonvolatile memory devices and the sub-block location within the sub-block buffer is added to the free list of the sub-block buffer cache table.

51. The computer readable medium for retaining a computer program code of claim 49 wherein writing the sub-block to the assigned free sub-block of the sub-block buffer cache comprises the step of:

setting a sub-block bit of the block of the sub-block being written as invalid in an invalid sub-block table indicating which sub-blocks with selected block of the array of nonvolatile memory devices are valid or invalid.

52. The computer readable medium for retaining a computer program code of claim 51 wherein the evicting a least recently used sub-block from the sub-block buffer cache comprises the step of garbage collecting to create at least one free sub-block.

53. The computer readable medium for retaining a computer program code of claim 52 wherein garbage collecting to create at least one free sub-block comprises the steps of:

determining whether a number erased sub-blocks available within the array of nonvolatile devices has fallen below an erase sub-block threshold;

searching physical block chain table including a linked listing containing pointers for each block of the array of nonvolatile memory devices containing an anchor pointer defining the number of invalid sub-blocks within the block to find a block with maximum invalid sub-blocks;

determining whether all sub-blocks within the block with the maximum invalid sub-blocks are invalid;

if all the sub-blocks are not invalid, copying the valid sub-blocks to at least one other block in the array of nonvolatile memory devices and setting the sub-blocks as invalid in the invalid sub-block table;

when all the sub-blocks are invalid, erasing the block with the maximum invalid sub-blocks.

54. The computer readable medium for retaining a computer program code of claim 53 wherein garbage collecting to create at least one free sub-block further comprises the step of setting an illegal sub-block number to indicate that the physical location of the erased block is erased the physical location within a physical-to-logical table that maps the physical location of the array of nonvolatile memory devices to the logical location.

55. The computer readable medium for retaining a computer program code of claim 49 wherein evicting the least recently used sub-block from the sub-block buffer cache further comprises the step of wearleveling an erased block.

56. The computer readable medium for retaining a computer program code of claim 55 wherein wearleveling an erased block comprises the steps of:

determining a sliding window erase count as a function of a lowest block erase count;

determining if an erased block count of the erased block exceeds the sliding window erase count;

if the sliding window erase count is exceeded, searching an erasure count table to determine a block having a lowest block erase count;

selecting the block with the lowest block erase count; and

copying all valid sub-blocks of the block with the lowest block erase count to the low order sub-blocks of the erased block;

erasing the block with the lowest block erase count to become a newly erased block;

incrementing the erasure count in the erasure count table for the newly erased block; and

assigning the newly erase block as a new spare block available for writing.

57. The computer readable medium for retaining a computer program code of claim 56 wherein in wearleveling, the step of determining the sliding window erase count comprises a step of adding an erase count threshold value to the lowest block erase count.

58. A method for wearleveling an erased block of a flash storage system that is comprised of an array of nonvolatile memory devices divided into multiple blocks of sub-arrays, wherein the method for wearleveling comprises the steps of:

determining a sliding window erase count as a function of a lowest block erase count;

determining if an erased block count of the erased block exceeds the sliding window erase count;

if the sliding window erase count is exceeded, searching an erasure count table to determine a block having the lowest block erase count;

selecting the block with the lowest block erase count; and

copying all valid sub-blocks of the block with the lowest block erase count to the low order sub-blocks of the erased block;

erasing the block with the lowest block erase count to become a newly erased block;

incrementing the erasure count in the erasure count table for the newly erased block; and

assigning the newly erase block as a new spare block available for writing.

59. The method for wearleveling of claim 58 wherein the step of determining the sliding window erase count comprises a step of adding an erase count threshold value to the lowest block erase count.

60. The method for wearleveling of claim 58 wherein the sub-block is a page, a super-page composed of single blocks within multiple array of nonvolatile memory devices, or super page composed of multiple pages with a block.

61. An apparatus for wearleveling an erased block of a flash storage system that is comprised of an array of nonvolatile memory devices divided into multiple blocks of sub-arrays, wherein the method for wearleveling comprises the steps of:

means for determining a sliding window erase count as a function of a lowest block erase count;

means for determining if an erased block count of the erased block exceeds the sliding window erase count;

means for searching an erasure count table to determine a block having the lowest block erase count, if the sliding window erase count is exceeded;

means for selecting the block with the lowest block erase count; and

means for copying all valid sub-blocks of the block with the lowest block erase count to the low order sub-blocks of the erased block;

means for erasing the block with the lowest block erase count to become a newly erased block;

means for incrementing the erasure count in the erasure count table for the newly erased block; and

means for assigning the newly erase block as a new spare block available for writing.

62. The apparatus for wearleveling of claim 61 wherein the means for determining the sliding window erase count comprises means for adding an erase count threshold value to the lowest block erase count.

63. The apparatus for wearleveling of claim 61 wherein the sub-block is a page, a super-page composed of single blocks within multiple array of nonvolatile memory devices, or super page composed of multiple pages with a block.