Granted Patent B1

US 10,740,243 · App. 16/410,116 · Granted Aug 11, 2020

Abstract

Claims (61)

1. A storage system comprising:

a memory configured to store a data structure; and

a controller in communication with the memory, wherein the controller is configured to:

determine that a completion queue in a host is too full to store a completion entry;

in response to determining that the completion queue in the host is too full to store the completion entry, temporarily store the completion entry in the data structure in the storage system;

determine that space has become available in the completion queue in the host to store the completion entry; and

in response to determining that space has become available in the completion queue in the host to store the completion entry, store, in the completion queue in the host, the completion entry that was temporarily stored in the data structure in the storage system.

2. The storage system of claim 1 , wherein the controller is further configured to temporarily store the completion entry in the data structure in the storage system in response to there being available space in the data structure and/or in response to a threshold not being exceeded for the data structure.

3. The storage system of claim 1 , wherein the controller is further configured to stop fetching commands from a submission queue in the host until space is available in the completion queue and/or the data structure.

4. The storage system of claim 1 , wherein the controller is further configured to:

in response to receiving a doorbell update to the completion queue from the host:

block completion entries from being posted to the completion queue;

update a head pointer of the completion queue;

determine whether there are any pending completion entries in the data structure; and

in response to determining that there are no pending completion entries in the data structure, unblock completion entries from being posted to the completion queue.

5. The storage system of claim 1 , wherein the controller is further configured to:

in response to determining that there are pending completion entries in the data structure:

select a completion entry from the data structure;

update a tail pointer based on a number of completion entries in the data structure;

post aggregated completion entries to the completion queue;

enable fetching from a submission queue in the host; and

unblock completion entries from being posted to the completion queue.

6. The storage system of claim 1 , wherein the memory comprises a three-dimensional memory.

7. The storage system of claim 1 , wherein the storage system is embedded in the host.

8. The storage system of claim 1 , wherein the storage system is configured to be removably connected to the host.

9. A method for preventing head-of-line blocking in a completion path, the method comprising:

performing the following in a storage system in communication with a host, wherein the host comprises a submission queue and a completion queue:

determining whether a completion queue entry can be posted to the completion queue;

in response to determining that the completion queue entry can be posted to the completion queue:

allocating an entry in the completion queue; and

fetching a command from the submission queue; and

in response to determining that the completion queue entry cannot be posted to the completion queue:

allocating an entry in a completion data structure in the storage system; and

fetching a command from the submission queue.

10. The method of claim 9 , wherein the storage system allocates the entry in the completion queue by updating a tail pointer.

11. The method of claim 9 , further comprising:

determining whether there is available space in the completion data structure and/or whether a threshold is not exceeded for the completion data structure, wherein an entry is allocated in the completion data structure in response to there being available space in the completion data structure and/or in response to the threshold not being exceeded.

12. The method of claim 11 , further comprising:

in response to determining that there is no available space in the completion data structure and/or in response to determining that the threshold has been exceeded, stopping fetching commands from the submission queue until space is available in the completion queue and/or the completion data structure.

13. The method of claim 9 , further comprising:

in response to receiving a doorbell update to the completion queue from the host:

blocking completion entries from being posted to the completion queue;

updating a head pointer of the completion queue;

determining whether there are any pending completion entries in the completion data structure; and

in response to determining that there are no pending completion entries in the completion data structure, unblocking completion entries from being posted to the completion queue.

14. The method of claim 9 , further comprising:

in response to determining that there are pending completion entries in the completion data structure:

selecting a completion entry from the completion data structure;

updating a tail pointer based on a number of completion entries in the completion data structure;

posting aggregated completion entries to the completion queue;

enabling fetching from the submission queue; and

unblocking completion entries from being posted to the completion queue.

15. A storage system comprising:

means for determining that a completion queue in a host is too full to store a completion entry;

means for, in response to determining that the completion queue in the host is too full to store the completion entry, temporarily storing the completion entry in a data structure in the storage system; and

means for, in response to determining that space has become available in the completion queue in the host to store the completion entry, storing, in the completion queue in the host, the completion entry that was temporarily stored in the data structure in the storage system.

16. The storage system of claim 15 , further comprising means for temporarily storing the completion entry in the data structure in the storage system in response to determining that there is available space in the data structure and/or in response to determining that a threshold is not exceeded for the data structure.

17. The storage system of claim 15 , further comprising means for blocking completion entries from being posted to the completion queue in response to receiving a doorbell update to the completion queue from the host.

18. The storage system of claim 15 , further comprising a three-dimensional memory.

19. The storage system of claim 15 , wherein the storage system is embedded in the host.

20. The storage system of claim 15 , wherein the storage system is configured to be removably connected to the host.

Assignments (10)