Advanced management of a non-volatile memory

• US 9,396,106 B2
• Filed: 04/09/2013
• Issued: 07/19/2016
• Est. Priority Date: 05/12/2011
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Inventors: Katz, Michael, Weingarten, Hanan
• Primary Examiner(s): Yi, David X
• Assistant Examiner(s): Mercado, Ramon A
• Application Number:
  US13/859,497
• Publication Number:
  US 20130227207A1
• Time in Patent Office: 1,197 Days
• Field of Search: 711/103, 711/130, 711/148, 709/213
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/7203 Temporary buffering, e.g. using volatile buffer or dedicated buffer blocks

Abstract

A method of managing a non-volatile memory device, the method comprising: receiving data sectors; writing each data sector into a data block that is allocated to a memory space subset that is associated with the data sector; wherein the data block belongs to a buffer of the non-volatile memory device; maintaining a management data structure that comprises location metadata about a location of each data sector in the buffer; and merging, if a criterion is fulfilled and before the buffer becomes full, data sectors stored at different data blocks and belong to a same set of logical memory blocks into a sequential portion of the non-volatile memory device, wherein the sequential portion differs from the buffer.

Claims

1. A method of managing a non-volatile memory device, the method comprising:

computing, for each suggested number of memory space subsets out of multiple suggested numbers, a quantity thereby providing multiple quantities to the multiple suggested numbers;

wherein each quantity is calculated in response to;

(a) a number of transaction timeout durations required to perform a merge of a logical memory block;

(b) an instantaneous number of logical memory blocks which have at least one associated data sectors in a buffer;

(c) a number of data sectors in a data block of the buffer;

(d) the suggested number of memory space subsets;

(e) a time duration for writing a data sector;

(f) a number of data blocks in the buffer, and (g) a time duration for performing a merge of a logical memory block;

selecting, out of the multiple suggested numbers of memory space subsets, a selected suggested number that yields a highest value quantity out of the multiple quantities;

partitioning, in response to the selected suggested number, the memory space to multiple memory space subsets;

receiving data sectors;

wherein each data sector belongs to a memory space subset out of the multiple memory space subsets;

wherein the multiple memory space subsets comprise a plurality of logical memory blocks;

writing each data sector into a data block that is allocated to a memory space subset that is associated with the data sector;

wherein the data block belongs to a buffer of the non-volatile memory device;

maintaining a management data structure that comprises location metadata about a location of each data sector in the buffer; and

merging, if a criterion is fulfilled and before the buffer becomes full, data sectors stored at different data blocks and belong to a same set of logical memory blocks into a sequential portion of the non-volatile memory device, wherein the sequential portion differs from the buffer.

2. The method according to claim 1, wherein the set of logical memory blocks comprises a single logical memory block.

3. The method according to claim 1, comprising allocating data blocks to the multiple memory space subsets;

wherein the allocating comprises maintaining at least one non-full data block to each memory space subset.

4. The method according to claim 1, wherein the criterion is fulfilled when a number of free data block of the buffer falls below a predetermined threshold.

5. The method according to claim 4, comprising determining the predetermined threshold in response to:

(a) the number of transaction timeout durations required to perform the merge of data sectors that belong to the certain logical memory block;

(b) the instantaneous number of logical memory blocks which have the at least one associated data sector in the buffer;

(c) the number of memory sectors in the data block of the buffer, and (d) a number of memory space subsets.

6. The method according to claim 1, comprising selecting at least one logical memory blocks that form the set of logical memory blocks.

7. The method according to claim 6, comprises selecting the set so that the set comprises at least one logical memory blocks that is associated with a maximum amount of data blocks.

8. The method according to claim 1, wherein the merging of the data sectors into the sequential portion comprises:

merging data sectors into a plurality of erase block sections of data;

writing the plurality of erase block sections of data to a plurality of erase blocks of the sequential portion; and

creating for each data sector a pointer in the data management structure, the pointer corresponds to an associated logical address and to a location of an erase block in which the data sector is stored.

9. The method according to claim 1, further comprising performing a cleaning process that comprises writing data sectors that are associated with a group of one or more logical memory blocks and are stored at one or more data blocks to one or more other data blocks.

10. The method according to claim 1, comprising copying content of a first data block to a second data block.

11. A method of managing a non-volatile memory device, the method comprising:

receiving data sectors;

wherein each data sector belongs to a memory space subset out of multiple memory space subsets;

wherein the multiple memory space subsets comprise a plurality of logical memory blocks;

writing each data sector into a data block that is allocated to a memory space subset that is associated with the data sector;

wherein the data block belongs to a buffer of the non-volatile memory device;

maintaining a management data structure that comprises location metadata about a location of each data sector in the buffer;

if a criterion is fulfilled and before the buffer becomes full, then selecting a set of logical blocks to be merged and merging data sectors stored at different data blocks and belong to the selected set of logical memory blocks of logical blocks to be merged into a sequential portion of the non-volatile memory device, wherein the sequential portion differs from the buffer; and

wherein the selecting of the set of logical blocks to be merged comprises;

determining a permutation transformation on a set of logical block indices;

selecting a set of indices; and

computing the logical block indices by employing the permutation on the set of indices.

12. The method according to claim 11, comprising partitioning a memory space to the multiple memory space subsets;

and determining a number (n) of the multiple memory space subsets in response to at least one out of;

(a) an aggregate amount of data sectors received between consecutive merging operations;

(b) a time required to write to the sequential portion all data blocks stored in the buffer, and (c) an amount of gap required to prevent a loss of data sectors due to a temporary absence of data blocks ready to receive new data sectors.

13. A method of managing a non-volatile memory device, the method comprising:

receiving data sectors;

wherein each data sector belongs to a memory space subset out of multiple memory space subsets;

wherein the multiple memory space subsets comprise a plurality of logical memory blocks;

writing each data sector into a data block that is allocated to a memory space subset that is associated with the data sector;

wherein the data block belongs to a buffer of the non-volatile memory device;

maintaining a management data structure that comprises location metadata about a location of each data sector in the buffer;

merging, if a criterion is fulfilled and before the buffer becomes full, data sectors stored at different data blocks and belong to a same set of logical memory blocks into a sequential portion of the non-volatile memory device, wherein the sequential portion differs from the buffer;

performing a cleaning process that comprises writing data sectors that are associated with a group of one or more logical memory blocks and are stored at one or more data blocks to one or more currently open data blocks of the buffer;

determining the group of one or more logical memory blocks by;

computing a quantity in response to an instantaneous number of logical memory blocks which have at least one associated data sector in the buffer in response to a number of data blocks in the buffer, and in response to a predefined constant; and

computing, based on said quantity and on at least one previously computed quantity that was computed during at least one previous cleaning process that preceded the current cleaning process, an integer number of logical memory blocks to be cleaned.

14. The method according to claim 13, comprising selecting of the one or more currently open data blocks of the buffer comprises:

determining a permutation transformation on a set of logical memory block indices;

selecting a set of indices; and

computing logical memory block indices by employing the permutation on the set of indices.

15. The method according to claim 14, wherein the selecting of a set of indices comprises the selecting of a contiguous set of integers starting from a next index after an index which was last used for either merging or cleaning.

16. The method according to claim 15, wherein the selecting of a set of indices comprises the selecting of a contiguous set of integers starting from the next index after the index which was last used for either merging or cleaning, wherein indices which correspond to logical block indices which were never merged since they were last cleaned are omitted.

17. A non-transitory computer readable medium that stores instructions that once executed by a memory controller cause the memory controller to:

compute, for each suggested number of memory space subsets out of multiple suggested numbers, a quantity thereby providing multiple quantities to the multiple suggested numbers;

wherein each quantity is calculated in response to;

(a) a number of transaction timeout durations required to perform a merge of a logical memory block;

(b) an instantaneous number of logical memory blocks which have at least one associated data sectors in a buffer;

(c) a number of data sectors in a data block of the buffer;

(d) the suggested number of memory space subsets;

(e) a time duration for writing a data sector;

(f) a number of data blocks in the buffer, and (g) a time duration for performing a merge of a logical memory block;

select, out of the multiple suggested numbers of memory space subsets, a selected suggested number that yields a highest value quantity out of the multiple quantities;

partition, in response to the selected suggested number, the memory space to multiple memory space subsets;

receive data sectors;

wherein each data sector belongs to a memory space subset out of the multiple memory space subsets;

wherein the multiple memory space subsets comprise a plurality of logical memory blocks;

write each data sector into a data block that is allocated to a memory space subset that is associated with the data sector;

wherein the data block belongs to a buffer of the non-volatile memory device;

maintain a management data structure that comprises location metadata about a location of each data sector in the buffer; and

merge, if a criterion is fulfilled and before the buffer becomes full, data sectors stored at different data blocks and belong to a same set of logical memory blocks into a sequential portion of the non-volatile memory device, wherein the sequential portion differs from the buffer.

18. A non-transitory computer readable medium that stores instructions that once executed by a memory controller cause the memory controller to:

receive data sectors;

wherein each data sector belongs to a memory space subset out of multiple memory space subsets;

wherein the multiple memory space subsets comprise a plurality of logical memory blocks;

write each data sector into a data block that is allocated to a memory space subset that is associated with the data sector;

wherein the data block belongs to a buffer of the non-volatile memory device;

maintain a management data structure that comprises location metadata about a location of each data sector in the buffer;

if a criterion is fulfilled and before the buffer becomes full, then select a set of logical blocks to be merged and merge data sectors stored at different data blocks and belong to the selected set of logical memory blocks of logical blocks to be merged into a sequential portion of the non-volatile memory device, wherein the sequential portion differs from the buffer; and

wherein a selecting of the set of logical blocks to be merged comprises;

determining a permutation transformation on a set of logical block indices;

selecting a set of indices; and

computing the logical block indices by employing the permutation on the set of indices.

19. A non-transitory computer readable medium that stores instructions that once executed by a memory controller cause the memory controller to:

receive data sectors;

wherein each data sector belongs to a memory space subset out of multiple memory space subsets;

wherein the multiple memory space subsets comprise a plurality of logical memory blocks;

write each data sector into a data block that is allocated to a memory space subset that is associated with the data sector;

wherein the data block belongs to a buffer of the non-volatile memory device;

maintain a management data structure that comprises location metadata about a location of each data sector in the buffer;

merge, if a criterion is fulfilled and before the buffer becomes full, data sectors stored at different data blocks and belong to a same set of logical memory blocks into a sequential portion of the non-volatile memory device, wherein the sequential portion differs from the buffer;

perform a cleaning process that comprises writing data sectors that are associated with a group of one or more logical memory blocks and are stored at one or more data blocks to one or more currently open data blocks of the buffer;

determine the group of one or more logical memory blocks by;

computing a quantity in response to an instantaneous number of logical memory blocks which have at least one associated data sector in the buffer in response to a number of data blocks in the buffer, and in response to a predefined constant; and

compute, based on said quantity and on at least one previously computed quantity that was computed during at least one previous cleaning process that preceded the current cleaning process, an integer number of logical memory blocks to be cleaned.