Efficient enforcement of command execution order in solid state drives

• US 10,019,196 B2
• Filed: 07/30/2015
• Issued: 07/10/2018
• Est. Priority Date: 08/23/2012
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Zaltsman, Etai, Golov, Oren, Stern, Ori Moshe, Ojalvo, Shai
• Primary Examiner(s): Wong, Nanci N
• Application Number:
  US14/813,436
• Publication Number:
  US 20150331638A1
• Time in Patent Office: 1,076 Days
• CPC Class Codes: G06F 13/28 using burst mode transfer, e.g. direct memory access DMA, cycle steal G06F13/32 takes precedence
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0623 in relation to content
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]

Abstract

A method in a storage device includes receiving from a host storage commands for execution in a non-volatile memory of the storage device. At least a subset of the storage commands are to be executed in accordance with an order-of-arrival in which the storage commands in the subset are received. The received storage commands are executed in the non-volatile memory in accordance with internal scheduling criteria of the storage device, which permit deviations from the order-of-arrival, but such that execution of the storage commands in the subset reflects the order-of-arrival to the host.

Claims

1. A method, comprising:

receiving, by a memory system, a plurality of commands from a host, the plurality of commands including corresponding data;

storing a subset of the plurality of commands that are to be executed in an order in which they are received into an in-order queue;

assigning a respective sequence number to each command of the subset, wherein the respective sequence number corresponds to an order in which each command of the subset is received by the memory system;

executing, by a processor included in the memory system, commands of the subset in accordance with internal scheduling criteria that allows commands to be executed in an order different than the order in which the commands were received;

storing, in the memory system, the corresponding data and the respective sequence number for executed commands;

recording, in the memory system, the respective sequence number for a last command of a series of commands that have executed successfully in an order in which each command of the series was received by the memory system;

sending a message to the host indicating that a given command of the subset has been executed in response to determining that each command of the subset with a respective sequence number less than the respective sequence number assigned to the given command has been successfully executed; and

in response to determining that the memory system is recovering from a power disruption;

skipping stored sequence numbers less than the recorded sequence number; and

scanning the stored sequence numbers, beginning at the recorded sequence number, to identify a gap in the respective sequence numbers stored in the memory system.

2. The method of claim 1, further comprising invalidating data stored in the memory system corresponding to each command of the subset with a respective sequence number greater than a sequence number in the gap.

3. The method of claim 2, wherein invalidating the data stored in the memory system comprises ignoring each command of the subset with a respective sequence number greater than the sequence number in the gap.

4. The method of claim 1, further comprising sending, to the host, an indication of a corresponding command of the subset with a respective sequence number immediately preceding a lowest sequence number in the gap.

5. The method of claim 1, wherein recording the respective sequence number for the last command of the series that executed successfully in the order in which each command of the series was received further comprises:

storing the respective sequence number for the last command of the series of commands into a particular location in the memory system; and

in response to determining that the memory system is recovering from the power disruption, reading the respective sequence number for the last command from the particular location.

6. The method of claim 5, wherein recording the respective sequence number for the last command of the series that executed successfully in the order in which each command of the series was received comprises periodically recording a respective sequence number for a last command of a current series of commands that have executed in order.

7. The method of claim 1, further comprising sending a message to the host indicating that a command of a different subset has been executed in response to determining that the command of the different subset has been executed wherein commands of the different subset are to be executed in any order.

8. An apparatus, comprising:

a memory;

a host interface configured to receive a plurality of commands for execution on the memory, the plurality of commands including corresponding data;

an in-order queue configured to receive a subset of the plurality of commands, wherein commands of the subset are to be executed in an order in which they are received;

a processor configured to;

assign a respective sequence number to each command of the subset, wherein the respective sequence number corresponds to an order in which each command of the subset is received;

execute commands of the subset in accordance with internal scheduling criteria that allows commands to be executed in an order different than the order in which the commands were received;

store, in the memory, the corresponding data and the respective sequence number for each executed commands of the subset;

record, in the memory, the respective sequence number for a last command of a series of commands that have executed successfully in an order in which each command of the series was received by the host interface;

send, via the host interface, an acknowledgement that a given command of the subset has been executed in response to a determination that each command of the subset with a respective sequence number less than the respective sequence number for the given command has been successfully executed; and

in response to a determination that the processor is recovering from a power disruption;

skipping stored sequence numbers less than the recorded sequence number; and

scanning stored sequence numbers, beginning at the recorded sequence number, to identify a gap in the respective sequence numbers stored in the memory.

9. The apparatus of claim 8, wherein the processor is further configured to invalidate data stored in the memory that corresponds to each command of the subset with a respective sequence number that is greater than a sequence number in the gap.

10. The apparatus of claim 9, wherein to invalidate the data stored in the memory, the processor is further configured to ignore each command of the subset with a respective sequence number greater than the sequence number in the gap.

11. The apparatus of claim 8, wherein the processor is further configured to send, via the host interface, an indication of a respective command of the subset with a respective sequence number immediately preceding a lowest sequence number in the gap.

12. The apparatus of claim 8, wherein to record the respective sequence number for the last command of the series that executed successfully in the order in which each command of the series was received, the processor is further configured to:

store the respective sequence number for the last command of the series into a particular location in the memory; and

in response to the determination that the processor is recovering from the power disruption, read the respective sequence number for the last command from the particular location.

13. The apparatus of claim 12, wherein to record the respective sequence number for the last command of the series that executed successfully in the order in which each command of the series was received, the processor is further configured to periodically record a respective sequence number for a last command of a current series of commands that have executed in order.

14. The apparatus of claim 8, wherein the processor is further configured to send, via the host interface, an acknowledgement that a command of a different subset has been executed in response to a determination that the command of the different subset has been executed, wherein commands of the different subset are to be executed in any order.

15. A system, comprising:

a memory device; and

a host configured to send a plurality of commands to the memory device;

wherein the memory device is configured to;

store a subset of the plurality of commands that are to be executed in an order in which they are received into an in-order queue;

assign a respective sequence number to each command of the subset, wherein the respective sequence number corresponds to an order in which each command of the subset is sent by the host;

execute commands of the subset in accordance with internal scheduling criteria that allows commands to be executed in an order different than the order in which the commands were sent;

store the corresponding data and the respective sequence number for executed commands;

send a message to the host indicating that a given command of the subset has been executed in response to a determination that each command of the subset with a respective sequence number less than the respective sequence number for the given command has been successfully executed;

record the respective sequence number for a last command of a series of commands that have executed successfully in an order in which each of the series of commands was received;

upon recovery from a power disruption;

skip stored sequence numbers less than the recorded sequence number; and

search for a gap the store respective sequence numbers beginning at the respective sequence number for the last command of the series of commands.

16. The system of claim 15, wherein to execute each command of the subset, the memory device is further configured to store data corresponding to each executed command.

17. The system of claim 16, wherein the memory device is further configured to, invalidate stored data that corresponds to each command of the subset with a respective sequence number greater than a sequence number in the gap.

18. The system of claim 15, wherein the memory device is further configured send, to the host, an indication of a respective command of the subset with a respective sequence number immediately preceding a lowest sequence number in the gap.

19. The system of claim 15, wherein the memory device is further configured to send a message to the host indicating that a command in of a different subset has been executed, wherein commands of the different subset are to be executed in any order.

20. The system of claim 15, wherein record the respective sequence number for the last command of the series of commands that have executed successfully in the order in which each of the series was received, the memory device is further configured to:

store the respective sequence number for the last command of the series into a particular location in the memory device; and

in response to the determination that the memory device is recovering from the power disruption, read the respective sequence number for the last command from the particular location.