Method And System For Storage Address Re-Mapping For A Memory Device

• US 20080307192A1
• Filed: 02/22/2008
• Published: 12/11/2008
• Est. Priority Date: 06/08/2007
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Inventors: Sinclair, Alan W., Wright, Barry
• Granted Patent: US 9,396,103 B2
• Time in Patent Office: Days
• US Class Current: 711/218
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0607 Interleaved addressing
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: G06F 2212/7202 Allocation control and policies
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 2212/7208 Multiple device management, e.g. distributing data over multiple flash devices

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.

Claims

1. A method of transferring data between a host system and a re-programmable non-volatile mass storage system, the method comprising:

receiving data associated with host logical block address (LBA) addresses at the mass storage 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 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 LBA addresses.

18. A method of transferring data between a host system and a re-programmable non-volatile mass storage system, the method comprising:

receiving data associated with host logical block address (LBA) addresses at the mass storage system from the host system;

re-mapping the received host LBA addresses in an order received to a block of contiguous storage LBA addresses;

allocating an additional block of contiguous storage LBA addresses, the additional block addressing only unwritten capacity upon allocation, and contiguously re-mapping remaining received host LBA addresses to the additional block only after the block of contiguous storage LBA addresses is fully programmed; and

creating new blocks of contiguous storage LBA addresses addressing only unwritten capacity.

19. The method of claim 18, wherein creating new blocks of contiguous storage LBA addresses comprises:

identifying blocks of storage LBA addresses previously fully associated with re-mapped host LBA addresses and currently addressing one or more pages of obsolete data; and

contiguously relocating addresses for valid data in an order of occurrence from a first identified block into a relocation block until the first identified block addresses only obsolete data.

20. The method of claim 19, wherein if the relocation block is fully written, a second relocation block addressing only unwritten capacity is allocated to continue receiving any additional addresses for valid data from the first identified block in a contiguous manner.

21. A method of transferring data between a host system and a re-programmable non-volatile mass storage system, the method comprising:

receiving data associated with host logical block address (LBA) addresses at the mass storage system from the host system;

contiguously re-mapping the received host LBA addresses in an order received to a block of contiguous storage LBA addresses;

allocating an additional block of contiguous storage LBA addresses, the additional block addressing only unwritten capacity upon allocation, and contiguously re-mapping remaining received host LBA addresses to the additional block when the block of contiguous storage LBA addresses is full; and

generating a storage address table (SAT) mapping host LBA addresses to storage LBA addresses as the data associated with the host LBA addresses is re-mapped to contiguous storage LBA addresses.

22. The method of claim 21, wherein generating the SAT comprises writing information relating to a mapping of host LBA addresses to storage LBA addresses in a contiguous manner to a block of contiguous storage LBA addresses.

23. The method of claim 21, further comprising generating a block information table identifying a status of each of a plurality of blocks of storage LBA addresses having a white or a pink status, wherein white status identifies blocks addressing only unwritten capacity and pink status identifies blocks addressing both obsolete and valid data.

24. The method of claim 23, wherein generating a block information table comprises writing the status of each of the plurality of blocks to a block of contiguous storage LBA addresses.

25. A method of transferring data between a host system and a re-programmable non-volatile mass storage system, the method comprising:

receiving data associated with host logical block address (LBA) addresses from the host system at an application on the mass storage system;

contiguously re-mapping the received host LBA addresses in an order received to a block of contiguous storage LBA addresses;

allocating an additional block of contiguous storage LBA addresses, the additional block addressing only unwritten capacity upon allocation, and contiguously re-mapping additional received host LBA addresses to the additional block when the block of contiguous storage LBA addresses is fully programmed; and

identifying previously fully programmed blocks of contiguous storage LBA addresses presently addressing valid and obsolete data prior to receiving new data associated with previously received host LBA addresses; and

creating new blocks of contiguous storage LBA addresses addressing only unwritten capacity from the identified previously fully programmed blocks of contiguous storage LBA addresses presently addressing valid and obsolete data.

26. The method of claim 25, wherein creating new blocks of contiguous storage LBA addresses comprises:

ranking the identified previously filled blocks of contiguous storage LBA addresses by an amount of obsolete data addressed in each previously filled block;

selecting a relocation block of contiguous storage LBA addresses within which to contiguously re-map valid data from the ranked previously filled blocks;

re-mapping storage LBA addresses for valid data from a selected one of the ranked previously filled blocks to contiguous storage LBA addresses in the relocation block; and

selecting a new relocation block addressing only unwritten capacity once the relocation block is fully written.

27. The method of claim 25, wherein identifying previously filled blocks of contiguous storage LBA addresses addressing obsolete data comprises scanning a cluster allocation map at the mass storage device.

28. The method of claim 27, wherein the host system comprises a NTFS file system and the cluster allocation map comprises a $bitmap file.

29. The method of claim 27, wherein the host system comprises a FAT file system.

30. The method of claim 25, wherein identifying previously filled blocks of contiguous storage LBA addresses addressing obsolete data comprises receiving a host system command at the mass storage, the host system command identifying obsolete data addresses.

31-140. -140. (canceled)