Maintaining ordering via a multi-level map of a solid-state media

1. A media controller for a solid-state media, the media controller in communication with a host device, the media controller comprising:

a control processor configured to, in response to receiving a request from the host device, the request including at least one logical address and address range:

determine, by a map of the media controller coupled to the control processor, one or more physical addresses of the solid-state media associated with the at least one logical address and address range, the map comprising a multi-level map having a plurality of leaf-level map pages, the plurality of leaf-level map pages stored in the solid-state media, and a subset of the plurality of leaf-level map pages stored in a map cache coupled to the control processor, each leaf-level map page comprising a plurality of map entries, each entry associated with one or more physical addresses of the solid-state media;

determine a type of the received request;

determine, based on the at least one logical address and address range, whether a corresponding leaf-level map page is stored in the map cache;

if the corresponding leaf-level map page is stored in the map cache, the map cache is configured to return a cache index and one or more control indicators of the map cache entry storing the corresponding leaf-level map page; and

enforce a set of ordering rules that selectively enable access to a corresponding leaf-level map page based on the one or more control indicators and the determined request type.

2. The media controller of claim 1 , wherein if the corresponding leaf-level map page is not stored in the map cache, the control processor is further configured to:

allocate, if available, an empty entry of the map cache;

retrieve the currently accessed leaf-level map page from the solid-state media; and

store the retrieved leaf-level map page to the allocated entry of the map cache.

3. The media controller of claim 1 , wherein the one or more control indicators comprise a leaf-level map page lock indicator and a plurality of leaf-level map entry lock indicators.

4. The media controller of claim 3 , wherein the control processor is configured to set the leaf-level map page lock indicator of a corresponding leaf-level map page when the corresponding leaf-level map page is being retrieved from the solid-state media to the map cache.

5. The media controller of claim 4 , wherein:

the type of the received request comprises a write request and a read request;

if the determined type of the received request is a write request, the control processor is further configured to:

set one or more of the plurality of leaf-level map entry lock indicators corresponding to the at least one logical address and address range accessed by the write request.

6. The media controller of claim 5 , wherein:

independent of the type of the received request, if at least one of the plurality of leaf-level map entry lock indicators is set, the control processor is configured to queue the received request on an associated queue.

7. The media controller of claim 6 , wherein the assigned queue is one of a plurality of queues assigned dynamically according to detecting that the leaf-level map page lock indicator or one of the plurality of leaf-level map entry lock indicators is set.

8. The media controller of claim 5 , wherein, upon completion of the write request, the control processor is configured to clear the one or more of the plurality of leaf-level map entry lock indicators corresponding to the physical addresses accessed by the write request.

9. The media controller of claim 5 , wherein each of the leaf-level map entries are configured to have the lock indicators set independently.

10. The media controller of claim 3 , wherein the control processor is configured to clear the leaf-level map page lock indicator of a corresponding leaf-level map page when the corresponding leaf-level map page is stored in the solid-state media to the map cache.

11. The media controller of claim 1 , wherein the control processor is configured to, based on the control indicators of the leaf-level map page, queue the received request.

12. The media controller of claim 1 , wherein the map is a multi-level map, the multi-level map comprising:

a second-level map having a plurality of second-level map pages, each of the second-level map pages having a plurality of entries, each entry configured to store a physical address of the solid state media; and

a first-level map having a plurality of entries, each entry associated with a second-level map page, the first-level map configured to associate the at least one logical address and address range to at least one of the second-level map pages.

13. The media controller of claim 12 , wherein the first-level map is stored in a map memory of the media controller, all of the second-level map pages are stored in the solid state media, and at least a subset of the second-level map pages are temporarily stored in a map cache coupled to the control processor of the media controller.

14. The media controller of claim 1 , wherein the control processor is further configured to:

maintain a sequential access tracking structure for each of the leaf-level map pages stored in the map cache, the sequential access tracking structure maintaining a count of accesses to each leaf-level map page;

update the sequential access tracking structure of a given leaf-level map page stored in the map cache when the at least one logical address and address range of the received request correspond to the given leaf-level map page;

wherein the control processor is configured to detect, based on the sequential access tracking structure, one or more interleaved streams of sequential accesses, each of the interleaved streams corresponding to a given one of the leaf-level map pages.

15. The media controller of claim 14 , wherein the control processor is configured to increment the count of accesses associated with a given leaf-level map page stored in the map cache when a subsequent request accesses a logical address range contiguous with the logical address range of a previous received request.

16. The media controller of claim 15 , wherein the control processor is further configured to:

if the count of accesses of the sequential access tracking structure reaches a threshold:

prefetch leaf-level map pages corresponding to one or more logical address ranges sequential to the logical address range of the subsequent request.

17. A method of processing, by media controller for a solid-state media, a request received from a host device, the request including at least one logical address and address range, the method comprising:

determining, by a map of the media controller coupled to a control processor of the media controller, one or more physical addresses of the solid-state media associated with the at least one logical address and address range, the map comprising a multi-level map having a plurality of leaf-level map pages, the plurality of leaf-level map pages stored in the solid-state media, and a subset of the plurality of leaf-level map pages stored in a map cache coupled to the control processor, each leaf-level map page comprising a plurality of map entries, each entry associated with one or more physical addresses of the solid-state media;

determining a type of the received request;

determining, based on the at least one logical address and address range, whether a corresponding leaf-level map page is stored in the map cache;

if the corresponding leaf-level map page is stored in the map cache, returning a cache index and one or more control indicators of the map cache entry storing the corresponding leaf-level map page; and

enforcing a set of ordering rules that selectively enable access to a corresponding leaf-level map page based on the one or more control indicators and the determined request type.

18. The method of claim 17 , wherein if the corresponding leaf-level map page is not stored in the map cache, the method further comprises:

allocating, if available, an empty entry of the map cache;

retrieving the currently accessed leaf-level map page from the solid-state media; and

storing the retrieved leaf-level map page to the allocated entry of the map cache.

19. The method of claim 17 , wherein the one or more control indicators comprise a leaf-level map page lock indicator and a plurality of leaf-level map entry lock indicators, the method further comprising:

setting, by the control processor, the leaf-level map page lock indicator of a corresponding leaf-level map page when the corresponding leaf-level map page is being retrieved from the solid-state media to the map cache.

20. The method of claim 19 , wherein the type of the received request comprises a write request and a read request, the method further comprising:

if the determined type of the received request is a write request:

setting, by the control processor, one or more of the plurality of leaf-level map entry lock indicators corresponding to the at least one logical address and address range accessed by the write request.

21. The method of claim 20 , wherein, if at least one of the plurality of leaf-level map entry lock indicators is set, the method further comprises:

queuing, by the control processor, independent of the type of the received request, the received request on an associated queue.

22. The method of claim 20 , further comprising:

dynamically assigning, by the control processor, one of a plurality of queues based on whether the leaf-level map page lock indicator or one of the plurality of leaf-level map entry lock indicators is set.

23. The method of claim 20 , wherein, upon completion of the write request, the method further comprises:

clearing, by the control processor, the one or more of the plurality of leaf-level map entry lock indicators corresponding to the physical addresses accessed by the write request.

24. The method of claim 20 , comprising:

independently setting, by the control processor, the lock indicators for each of the leaf-level map entries.

25. The method of claim 19 , further comprising:

clearing, by the control processor, the leaf-level map page lock indicator of a corresponding leaf-level map page when the corresponding leaf-level map page is stored in the solid-state media to the map cache.

26. The method of claim 17 , wherein the map is a multi-level map, the multi-level map comprising:

a second-level map having a plurality of second-level map pages, each of the second-level map pages having a plurality of entries, each entry configured to store a physical address of the solid state media; and

a first-level map having a plurality of entries, each entry associated with a second-level map page, the first-level map configured to associate the at least one logical address and address range to at least one of the second-level map pages.

27. The method of claim 26 , further comprising:

storing the first-level map in a map memory of the media controller;

storing all of the second-level map pages in the solid state media; and

temporarily storing at least a subset of the second-level map pages in a map cache coupled to the control processor of the media controller.

28. The method of claim 17 , further comprising, by the control processor:

maintaining a sequential access tracking structure for each of the leaf-level map pages stored in the map cache, the sequential access tracking structure maintaining a count of accesses to each leaf-level map page;

updating the sequential access tracking structure of a given leaf-level map page stored in the map cache when the at least one logical address and address range of the received request correspond to the given leaf-level map page; and

detecting, based on the sequential access tracking structure, one or more interleaved streams of sequential accesses, each of the interleaved streams corresponding to a given one of the leaf-level map pages.

29. The method of claim 28 , further comprising, by the control processor:

incrementing the count of accesses associated with a given leaf-level map page stored in the map cache when a subsequent request accesses a logical address range contiguous with the logical address range of a previous received request.

30. The method of claim 29 , further comprising, by the control processor:

if the count of accesses of the sequential access tracking structure reaches a threshold:

prefetching leaf-level map pages corresponding to one or more logical address ranges sequential to the logical address range of the subsequent request.

31. The method of claim 17 , wherein the method is implemented by a machine executing program code encoded on a non-transitory machine-readable storage medium.