Device controller and method for performing a plurality of write transactions atomically within a nonvolatile data storage device

• US 10,445,000 B2
• Filed: 05/19/2015
• Issued: 10/15/2019
• Est. Priority Date: 06/24/2014
• Status: Active Grant

• Current Assignee: Arm Limited (SoftBank Group Corp.)
• Original Assignee: Arm Limited (SoftBank Group Corp.)
• Inventors: De Jong, Ireneus Johannes, Hansson, Andreas
• Primary Examiner(s): Giardino, Jr., Mark A
• Application Number:
  US15/320,380
• Publication Number:
  US 20170160933A1
• Time in Patent Office: 1,610 Days
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 12/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: G06F 12/10 Address translation
• CPC Class Codes: G06F 13/16 for access to memory bus G06F13/28 takes precedence
• CPC Class Codes: G06F 2212/222 Non-volatile memory
• CPC Class Codes: G06F 2212/65 Details of virtual memory and virtual address translation
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 3/06 Digital input from, or digital output to, record carriers , e.g. RAID, emulated record carriers or networked record carriers
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0656 Data buffering arrangements
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G06F 9/467 Transactional memory G06F9/528 takes precedence

Abstract

A device controller and method are provided for performing a plurality of write transactions atomically within a non-volatile data storage device. Each transaction specifies a logical address and the method comprises creating an address translation map for the logical addresses specified by the plurality of write transactions, by referencing an address translation record within the non-volatile data storage device to determine for each logical address a corresponding physical address within the data storage device. Further, if the corresponding physical address indicated in the address translation record already contains valid data, the logical address is remapped to a new physical address in the address translation map. However, at this point the address translation record as stored in the data storage device is not updated. Instead, the plurality of write transactions are performed using the logical address to physical address mapping in the address translation map. Then, only once the plurality of write transactions have been performed is the address translation record updated in the non-volatile data storage device in order to identify the logical address to physical address mapping in the address translation map. Since, at the time of performing the write transactions, any new data that updates data already stored in the data storage device is written into a different physical address location, and hence the previous version of the data is still stored on the data storage device, and given that the address translation record is not updated unless the plurality of write transactions are actually performed atomically, then this enables the state held on the data storage device to be rolled back to the state that existed prior to performing the plurality of write transactions, if any event prevents that plurality of write transactions being performed atomically.

Claims

1. A method of operating a device controller to perform a plurality of write transactions atomically within a non-volatile data storage device, each transaction specifying a logical address, the method comprising:

creating an address translation map for the logical addresses specified by said plurality of write transactions, by referencing an address translation record in the non-volatile data storage device to determine for each logical address a corresponding physical address within the data storage device, and if the corresponding physical address indicated in the address translation record already contains valid data, remapping the logical address to a new physical address in said address translation map;

performing said plurality of write transactions using the logical address to physical address mapping in said address translation map; and

updating the address translation record in the non-volatile data storage device to identify the logical address to physical address mapping in said address translation map only once said plurality of write transactions have been performed in said non-volatile storage device.

2. A method as claimed in claim 1, further comprising:

prior to performing the plurality of write transactions, performing an intent save operation to store within an area of the non-volatile data storage device intent information identifying the plurality of write transactions to be performed atomically and the logical address to physical address mapping in said address translation map.

3. A method as claimed in claim 2, wherein the intent save operation is performed as a write transaction having a higher priority than the plurality of write transactions to be performed atomically.

4. A method as claimed in claim 2, wherein said non-volatile data storage device comprises a main non-volatile storage unit and a non-volatile cache configured to buffer data prior to writing of that data into the main non-volatile storage unit, and said area of the non-volatile data storage device where the intent information is stored is within said non-volatile cache.

5. A method as claimed in claim 1, further comprising storing the address translation map in volatile storage associated with the device controller for reference by the device controller when performing said plurality of write transactions.

6. A method as claimed in claim 1, further comprising:

activating a garbage collection process following the step of updating the address translation record in the non-volatile storage device, in order to invalidate any physical addresses no longer mapped to logical addresses by the updated translation record.

7. A method as claimed in claim 1, wherein the device controller receives the plurality of write transactions from a host entity, the host entity identifying to the device controller that the plurality of write transactions are to be handled atomically.

8. A method as claimed in claim 2, wherein in response to a trigger condition, performing the following steps:

obtaining the address translation table and the intent information from the non-volatile storage device; and

determining, for each write transaction identified in the intent information, whether the logical address to physical address mapping indicated by the intent information matches the logical address to physical address mapping in the address translation table.

9. A method as claimed in claim 8, wherein if, for any write transaction identified in the intent information, the logical address to physical address mapping indicated by the intent information does not match the logical address to physical address mapping in the address translation table, the method further comprises the step of invalidating the data at the physical address identified for every write transaction in the intent information.

10. A method as claimed in claim 9, further comprising issuing a notification to a host entity providing an indication that the plurality of write transactions have not been performed.

11. A method as claimed in claim 1, wherein

said non-volatile data storage device comprises a main non-volatile storage unit and a non-volatile cache configured to buffer data prior to writing of that data into the main non-volatile storage unit;

the step of performing said plurality of write transactions comprises initially writing the data of each write transaction to the non-volatile cache and then subsequently storing the data of each write transaction from the non-volatile cache into the main non-volatile storage unit at the physical address specified by the address translation map.

12. A method as claimed in claim 11, wherein said plurality of write transactions form a first atomic write sequence;

following writing of the first atomic write sequence to the non-volatile cache, the device controller is requested to perform a second atomic write sequence comprising a second plurality of write transactions; and

if at least one of said second plurality of write transactions specifies a logical address associated with a write transaction of the first atomic write sequence whose data has not yet been stored within the main non-volatile storage unit, merging the first and second atomic write sequences into a single atomic write sequence such that the data written to the non-volatile cache represents the single atomic write sequence.

13. A method as claimed in claim 12, further comprising:

prior to performing the plurality of write transactions, performing an intent save operation to store within an area of the non-volatile data storage device intent information identifying the plurality of write transactions to be performed atomically and the logical address to physical address mapping in said address translation map; and

updating within the area of the non-volatile data storage device the intent information identifying the plurality of write transactions to be performed atomically and the logical address to physical address mapping in said address translation map, so that the intent information reflects the single atomic write sequence.

14. A method as claimed in claim 12, wherein the step of updating the address translation record in the non-volatile data storage device is performed only after the write transactions of the merged single atomic write sequence have been performed.

15. A method as claimed in claim 12, wherein an upper bound is placed on the number of atomic write sequences that can be merged, and on reaching the upper bound the device controller causes the current merged atomic write sequence to complete, and the update to the address translation record in the non-volatile data storage device to be performed, before allowing a further atomic write sequence to be performed.

16. A method as claimed in claim 12, wherein in response to a predetermined command, the device controller causes a current merged atomic write sequence to complete, and the update to the address translation record in the non-volatile data storage device to be performed, before allowing a further atomic write sequence to be performed.

17. A method as claimed in claim 1, wherein the non-volatile data storage device is a flash storage device comprising a number of storage blocks, each storage block comprising one or more storage pages.

19. A computer program product comprising a computer program embodied on a non-transitory computer readable storage medium which when executed on a computer causes the computer to perform the method of claim 1.

18. A device controller for performing a plurality of write transactions atomically within a non-volatile data storage device, each transaction specifying a logical address, the device controller comprising:

address translation map generation circuitry configured to create an address translation map for the logical addresses specified by said plurality of write transactions, by referencing an address translation record in the non-volatile data storage device to determine for each logical address a corresponding physical address within the data storage device, if the corresponding physical address indicated in the address translation record already contains valid data, the address translation map generation circuitry being further configured to remap the logical address to a new physical address in said address translation map;

transaction control circuitry configured to perform said plurality of write transactions using the logical address to physical address mapping in said address translation map; and

address translation record update circuitry configured to update the address translation record in the non-volatile data storage device to identify the logical address to physical address mapping in said address translation map only once said plurality of write transactions have been performed in said non-volatile data storage device.

20. A device controller for performing a plurality of write transactions atomically within a non-volatile data storage device, each transaction specifying a logical address, the device controller comprising:

address translation map generation means for creating an address translation map for the logical addresses specified by said plurality of write transactions, by referencing an address translation record in the non-volatile data storage device to determine for each logical address a corresponding physical address within the data storage device, if the corresponding physical address indicated in the address translation record already contains valid data, the address translation map generation means further for remapping the logical address to a new physical address in said address translation map;

transaction control means for performing said plurality of write transactions using the logical address to physical address mapping in said address translation map; and

address translation record update means for updating the address translation record in the non-volatile data storage device to identify the logical address to physical address mapping in said address translation map only once said plurality of write transactions have been performed in said non-volatile data storage device.