Method and system for storage address re-mapping for a memory device

Patent metadata

Field	Value
Publication number	US-9396103-B2
Application number	US-3601408-A
Country	US
Kind code	B2
Filing date	Feb 22, 2008
Priority date	Jun 8, 2007
Publication date	Jul 19, 2016
Grant date	Jul 19, 2016

Abstract

A method and system for storage address re-mapping is disclosed. The method includes allocating logical addresses in blocks of clusters and re-mapping logical addresses into storage address space, where short runs of data dispersed in logical address space are mapped in a contiguous manner into blocks in storage address space. Valid data is flushed from blocks having both valid and obsolete data to make new blocks available for receiving data when an available number of new blocks falls below a desired threshold. The system includes a host file system, processor executable instructions residing on a host separately from the host file system or residing on a flash memory device such as an embedded solid state disk, or a backend memory manager of the flash memory device that is configured to map data from a logical address space to complete blocks in storage address space in a contiguous manner.

First claim

The invention claimed is:

1. A method of transferring data between a host system and a re-programmable non-volatile mass storage memory system, the method comprising:
in the mass storage memory system, the mass storage memory system having re-programmable non-volatile memory cells arranged in a plurality of blocks of memory cells that are erasable together and a controller in communication with the plurality of blocks of memory cells, the controller, for any data that is associated with host logical block address (LBA) addresses and that is received at the mass storage memory system from the host system:
allocating a block of contiguous storage LBA addresses for addressing the data associated with the host LBA addresses, the block of contiguous storage LBA addresses addressing only unwritten capacity upon allocation; and
re-mapping each of the host LBA addresses for the received data to the block of contiguous storage LBA addresses, wherein each storage LBA address is sequentially assigned in a contiguous manner to the received data in an order the received data is received regardless of the host LBA address.

2. The method of claim 1 , further comprising allocating a second block of contiguous storage LBA addresses for re-mapping additional received data in a contiguous manner, the second block of contiguous storage LBA addresses associated with only unwritten capacity upon allocation, wherein the allocation of the second block is made only upon completely assigning the block of contiguous storage LBA addresses.

3. The method of claim 1 , wherein allocating a block of contiguous storage LBA addresses comprises allocating a block of contiguous storage LBA addresses for each of a plurality of ranges of host LBA addresses, wherein each block of contiguous storage LBA addresses is associated with only unwritten capacity upon allocation.

4. The method of claim 3 , wherein re-mapping comprises re-mapping each of the host LBA addresses for the received data in a respective one of the plurality of ranges of host LBA addresses to a respective allocated block of storage LBA addresses, wherein each storage LBA address in an allocated block of contiguous storage LBA addresses is sequentially assigned in a contiguous manner to received data falling within a respective one of the plurality of ranges in an order that the data is received regardless of the host LBA address within the respective one of the plurality of ranges.

5. The method of claim 4 , further comprising, for each of the plurality of ranges, allocating a second block of contiguous storage LBA addresses for re-mapping additional received data in a contiguous manner, the second block of contiguous storage LBA addresses associated with only unwritten capacity upon allocation, wherein allocation of the second block of contiguous storage LBA addresses is made for a particular range of host LBA addresses only upon completely assigning the block of contiguous storage LBA addresses currently associated with the particular range of host LBA addresses.

6. The method of claim 1 , further comprising writing the data associated with the block of contiguous storage LBA addresses to contiguous physical address locations in a physical block of addresses currently associated with the block of contiguous storage LBA addresses.

7. The method of claim 1 , wherein the mass storage memory system receives the data associated with the host LBA addresses, re-maps the host LBA addresses and writes the data associated with the storage LBA addresses without ever initiating a garbage collection operation.

8. The method of claim 1 , wherein the re-mapping step further comprises generating correlation data correlating host LBA address and storage LBA address locations and assigning respective contiguous storage LBA addresses to the correlation data in a second block of contiguous storage LBA addresses.

9. The method of claim 8 , wherein the block of contiguous storage LBA addresses is exclusively associated with data from the host system and the second block of contiguous storage LBA addresses is exclusively associated with correlation data.

10. The method of claim 1 , further comprising:
identifying obsolete data associated with the block of contiguous storage LBA addresses, wherein the obsolete data represents host deallocated data;
selecting a relocation block of contiguous storage LBA addresses with which to contiguously re-map valid data from the block of contiguous storage LBA addresses; and
reassigning valid data associated with the block of contiguous storage LBA addresses to contiguous storage LBA addresses in the relocation block.

11. The method of claim 10 , further comprising:
identifying obsolete data associated with an additional block of contiguous storage LBA addresses;
reassigning storage LBA addresses for valid data from the additional block of contiguous storage LBA addresses to contiguous storage LBA addresses in the relocation block, wherein when the relocation block is full, a new relocation block having only unwritten capacity is selected and remaining valid data from the additional block is reassigned to contiguous storage LBA addresses in the new relocation block.

12. The method of claim 10 , wherein the relocation block of contiguous storage LBA addresses is exclusively associated with re-mapped valid host data.

13. The method of claim 9 , further comprising:
identifying obsolete correlation data associated with the second block of contiguous storage LBA addresses;
selecting a relocation block of contiguous storage LBA addresses with which to contiguously re-map valid correlation data from the second block of contiguous storage LBA addresses; and
reassigning valid correlation data from the second block of contiguous storage LBA addresses to contiguous storage LBA addresses in the relocation block.

14. The method of claim 13 , further comprising:
identifying obsolete correlation data associated with an additional block of contiguous storage LBA addresses exclusively associated with correlation data; and
reassigning storage LBA addresses for valid correlation data from the additional block of contiguous storage LBA addresses to contiguous storage LBA addresses in the relocation block, wherein when the relocation block is full, a new relocation block having only unwritten capacity is selected and remaining valid correlation data associated with the additional block is reassigned to contiguous storage LBA addresses in the new relocation block.

15. The method of claim 1 , further comprising tracking a status of a plurality of blocks of contiguous storage LBA addresses having a white or pink status, wherein white status identifies any blocks associated with only unwritten capacity and pink status identifies any blocks associated with both valid and obsolete data.

16. The method of claim 15 , wherein tracking the status comprises maintaining a block information table comprising an initial block of contiguous storage LBA addresses for exclusively addressing block information table data relating to the status of each of the plurality of blocks of contiguous storage LBA addresses.

17. The method of claim 16 , wherein maintaining the block information table comprises allocating an additional block of contiguous storage LBA addresses for use in addressing block information table data in a contiguous manner, the additional block of contiguous storage LBA addresses addressing only unwritten capacity upon allocation, wherein the allocation of the additional block is made only upon completely assigning the initial block of contiguous storage L

Assignees

• Sinclair Alan W
• Wright Barry
• Sandisk Technologies Llc

Inventors

• Sinclair Alan W
• Wright Barry

Classifications

• G06F2212/7205

  Cleaning, compaction, garbage collection, erase control · CPC title

• G06F12/0246 Primary

  in block erasable memory, e.g. flash memory · CPC title

• G06F2212/1016

  Performance improvement · CPC title

• G06F2212/7202

  Allocation control and policies · CPC title

• G06F12/0607

  Interleaved addressing · CPC title