Cluster auto-alignment for storing addressable data packets in a non-volatile memory array

• US 7,395,404 B2
• Filed: 12/16/2004
• Issued: 07/01/2008
• Est. Priority Date: 12/16/2004
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Corporation (Western Digital Corporation)
• Inventors: Bennett, Alan David, Gorobets, Sergey Anatolievich
• Primary Examiner(s): Peikari; B. James
• Application Number:
  US11/015,211
• Publication Number:
  US 20060136655A1
• Time in Patent Office: 1,293 Days
• Field of Search: 711/201
• US Class Current: 711/201
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/7202 Allocation control and policies

Abstract

Alignment of clusters to pages is provided in a non-volatile memory system that receives data from a host in clusters and writes data to a memory array in units of a page. Alignment is implemented within each block using offsets in logical-to-physical mapping of data. Different blocks may have different offsets. When a host sends data with different cluster boundary locations, the data may be written with different offsets so that data maintains alignment.

Claims

1. A method of storing addressable data packets in a non-volatile memory array that is connected to a host, the memory array having units of erase of a block, where each block of the memory array holds one logical block of data, each logical block formed of addressable data packets extending sequentially from a first addressable data packet to a last addressable data packet, data allocated by the host in units of a cluster, each cluster including multiple addressable data packets, comprising:

determining an offset between a logical block boundary and a cluster boundary for data received from a host for storage in a predetermined block;

selecting physical locations in the predetermined block for writing a plurality of clusters of the received data according to the offset, such that an individual cluster boundary is located at a predetermined page boundary; and

writing a first partial cluster that includes the first addressable data packet of a logical block of the received data and a last partial cluster that includes the last addressable data packet of the logical block of the received data to a page of the predetermined block.

2. The method of claim 1 wherein the first partial cluster and the last partial cluster are written to a sequentially last page of a plurality of sequential pages that form the predetermined block.

3. The method of claim 2 wherein the first partial cluster is stored outside the predetermined block prior to writing to the last page of the plurality of sequential pages that form the predetermined block.

4. The method of claim 1 wherein the first partial cluster and the last partial cluster are written to a sequentially first page of a plurality of sequential pages that form the predetermined block.

5. The method of claim 4 wherein the first partial cluster is directly stored in the sequentially first page of the predetermined block and subsequently the last partial cluster is also stored in the sequentially first page of the predetermined block.

6. The method of claim 1 wherein the predetermined block consists of a plurality of pages and all pages of the predetermined block, except the page containing the first and last partial clusters, contain clusters stored with a cluster boundary at a page boundary.

7. The method of claim 1 wherein the memory array consists of a plurality of blocks, each black of the plurality of blocks being a minimum unit of erase and wherein data packets of the first partial cluster and data packets of the second data cluster are stored out of logical sequence in the page.

8. The method of claim 7 where the predetermined block consists of a plurality of pages and each of the plurality of pages, except for the page, contain addressable packets of data that are stored in logical sequence.

9. A method of storing clusters of data received from a host, each cluster containing multiple addressable units of data allocated together by a host, in a non-volatile memory array having a unit of programming of a page and a unit of erase of a block, each block containing multiple pages, comprising:

receiving a plurality of clusters of data from a host;

mapping the plurality of clusters to blocks of the memory array without regard to the locations of cluster boundaries;

deriving an offset between cluster boundaries and mapped block boundaries; and

storing clusters and portions of clusters that are mapped to a predetermined block in pages within the predetermined block, in a manner dependent on the derived offset, so that boundaries between clusters occur at page boundaries, the clusters and portions of clusters that are mapped to the predetermined block having a logical address range, the logical address range being independent of the offset so that the predetermined block is filled with identical sectors regardless of the offset.

10. The method of claim 9 wherein the portions of clusters that are mapped to the predetermined block are a first portion of a first cluster and a second portion of a second cluster, the first and second portion stored together in a page of the predetermined block.

11. The method of claim 10 wherein the clusters and portions of clusters tat are mapped to the predetermined block are sequential data extending from a first logical address to a last logical address, the first portion including the first logical address and the second portion including the last logical address.

12. The method of claim 9 wherein a value is recorded that indicates the offset for the predetermined block.

13. A method of storing data that contains predefined cluster boundaries in metablocks of a non-volatile memory array, each metablock consisting of two or more erase blocks that are programmed and erased in parallel, erase blocks being the minimum unit of erase of the non-volatile memory array, each logical block consisting of data equal to the data in one metablock, each logical group consisting of data equal to the data in one erase block, comprising:

receiving data for storage in a non-volatile memory, the data consisting of multiple sequential addressable data packets;

storing a first one or more addressable data packets from a first cluster in a first location, the first cluster containing the first one or more addressable data packets from a first logical group and also containing a second one or more addressable data packets from a second logical group;

storing subsequent sequential addressable data packets in pages of a first metablock, such that page boundaries occur at cluster boundaries;

storing a third one or more addressable data packets from a last cluster with the first one or more addressable data packets in a predetermined page of the first metablock, the last cluster containing the third one or more addressable data packets from the first logical group and also containing a fourth one or more addressable data packets from a third logical group.

14. The method of claim 13 wherein the first location is in a second metablock.

15. The method of claim 13 wherein the first location is the predetermined page of the first metablock and the third one or more addressable data packets are written to the predetermined page of the first metablock subsequent to writing the first one or more addressable data packets to the predetermined page of the first metablock.

16. The method of claim 13 wherein the data in the first logical group is sequential to the data in the second logical group and the data in the third logical group is sequential to the data in the first logical group.

17. The method of claim 13 wherein the first, second and third logical groups are in a logical block that is stored in the first metablock.

18. The method of claim 13 wherein each metablock of the non-volatile memory array consists of a plurality of erase blocks, each of the plurality of erase blocks from a different plane of the memory array, each plane of the memory array having its own dedicated control circuits.

19. A memory system for storing addressable data packets sent by a host in a non-volatile storage medium, comprising:

a controller that receives addressable data packets from the host, the received addressable data packets forming clusters that are allocated to files by the host, each cluster containing multiple addressable data packets, a sequential range of the received addressable data packets mapped to a logical unit by the controller without regard to cluster locations;

a non-volatile memory array in communication with the controller, the non-volatile memory array having multiple erase blocks, erase blocks being the minimum unit of erase of the memory array, one or more erase blocks assigned to store the logical unit, the one or more erase blocks being programmable and erasable together, the one or more erase blocks containing physical locations for storage of addressable data packets, the physical locations for storage of individual ones of the range of addressable data packets selected to provide cluster-to-page alignment for clusters within the logical unit, without modifying the range of addressable data packets that are mapped to the logical unit; and

wherein clusters that individually include a portion within the logical unit and a portion outside the logical unit have the portions within the logical unit stored together in a page of the logical unit without cluster-to-page alignment.

20. The memory system of claim 19 wherein cluster size is equal to page size and the portions within the logical unit occupy a complete page of the one or more erase blocks.

21. The memory system of claim 19 wherein the one or more erase blocks consists of a metablock of two or more erase blocks and the logical unit consists of an amount of data that fits exactly within the metablock.

22. The memory system of claim 19 wherein the one or more erase blocks consists of one erase block and the logical unit consists of data that fits exactly within the one erase block.

23. The memory system of claim 19 wherein the memory system is encapsulated in a memory card that is removably connected to a host.