Map recycling acceleration

• US 9,405,672 B2
• Filed: 07/15/2013
• Issued: 08/02/2016
• Est. Priority Date: 06/25/2013
• Status: Active Grant

• Current Assignee: Seagate Technology LLC (Seagate Technology Holdings Plc)
• Original Assignee: Seagate Technology LLC (Seagate Technology Holdings Plc)
• Inventors: Canepa, Timothy, Baryudin, Leonid, Hanna, Stephen D., Tang, Alex G.
• Primary Examiner(s): Rutz, Jared
• Assistant Examiner(s): CHOI, CHARLES J
• Application Number:
  US13/941,820
• Publication Number:
  US 20140379959A1
• Time in Patent Office: 1,114 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash 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 2212/1032 Reliability improvement, data loss prevention, degraded operation etc
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 2212/214 Solid state disk
• CPC Class Codes: G06F 2212/281 Single cache
• CPC Class Codes: G06F 2212/312 In storage controller
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0613 in relation to throughput
• 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/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/0656 Data buffering arrangements
• CPC Class Codes: G06F 3/0658 Controller construction arrangements
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]

Abstract

An apparatus having a processor and a circuit is disclosed. The processor is generally configured to initiate an operation to recycle a plurality of source blocks in a memory that is nonvolatile. The circuit is generally configured to (i) search through a first of a plurality of levels in a map that defines a plurality of translations between a plurality of logical addresses used at an interface to a computer and a plurality of physical addresses used in the memory and (ii) notify the processor in response to a detection in the first level of one or more of the source blocks to be recycled that contain valid data.

Claims

1. An apparatus comprising:

a memory configured to store data; and

a controller configured to process a plurality of input/output requests to read/write to/from the memory, the controller comprising a processor configured to initiate a recycle operation by generation of a start index and a search range, and a hardware assist circuit configured to store the start index and the search range in a queue, search exclusively through a first level in a map in response to the start index and the search range, notify the processor in response to a detection in the first level of the map that one or more of the source blocks to be recycled contain valid data, and suspend the recycle operation while servicing a new command to access the memory, wherein the start index and the search range identify a plurality of source blocks in the memory to be recycled in the recycle operation, the map defines a plurality of translations between a plurality of logical addresses used at a host interface and a plurality of physical addresses used in the memory, the map has a plurality of pages in a second level, the first level in the map indicates if data in the source blocks is valid or not, and all of the first level and a portion less than all, of the second level in the map are buffered in a cache while the first level is searched.

2. The apparatus according to claim 1, wherein the processor is further configured to update the map in response to the notification.

3. The apparatus according to claim 2, wherein the search of the first level is implemented in dedicated hardware.

4. The apparatus according to claim 1, wherein the recycle operation moves the valid data from the source blocks to one or more destination blocks in the memory, and updates the map.

5. The apparatus according to claim 1, wherein the hardware assist circuit is further configured to lock one or more of the pages in the second level of the map during the recycle operation to prevent changes to the first level of the map during the recycle operation, and the pages that are locked correspond to the source blocks to be recycled.

6. The apparatus according to claim 1, wherein the processor is further configured to copy the portion of the second level of the map from the cache to the memory in response to an update to the map.

7. The apparatus according to claim 1, wherein the detection is performed independently of a plurality of headers in the Source blocks.

8. The apparatus according to claim 1, wherein the memory and the controller form part of a solid-state drive.

9. The apparatus according to claim 1, wherein the hardware assist circuit is further configured to check the second level in the cache for a page slot that matches a map index found in the first level during the search, and install a preassigned free page slot in the second level in the cache in response to not finding the page slot that matches the map index in the second level in the cache.

10. A method for map recycling acceleration, comprising the steps of:

processing a plurality of input/output requests to read/write to/from a memory;

initiating a recycle operation by generation of a start index and a search range using a processor;

storing the start index and the search range in a queue;

searching exclusively through a first level in a map in response to the start index and the search range;

notifying the processor in response to a detection in the first level of the map that one or more of the source blocks to be recycled contain valid data; and

suspending the recycle operation while servicing a new command to access the memory, wherein the start index and the search range identify a plurality of source blocks in the memory to be recycled in the recycle operation, the map defines a plurality of translations between a plurality of logical addresses used at a host interface and a plurality of physical addresses used in the memory, the map has a plurality of pages in a second level, the first level in the map indicates if data in the source blocks is valid or not, and all of the first level and a portion less than all of the second level in the map are buffered in a cache while the first level is searched.

11. The method according to claim 10, further comprising the step of:

updating the map using the processor in response to the notification.

12. The method according to claim 11, wherein the search of the first level is implemented in dedicated hardware.

13. The method according to claim 10, wherein the recycle operation moves the valid data from the source blocks to one or more destination blocks in the memory, and updates the map.

14. The method according to claim 10, farther comprising the step of:

locking one or more of the pages in the second level of the map during the recycle operation to prevent changes to the first level of the map during the recycle operation, wherein the pages that are locked correspond to the source blocks to be recycled.

15. The method according to claim 10, further comprising the step of:

copying the portion of the second level of the map from the cache to the memory in response to an update to the map.

16. The method according to claim 10, wherein the detection is performed independently of a plurality of headers in the source blocks.

17. The method according to claim 10, wherein the method is implemented in a solid-state drive.

18. The method according to claim 10, further comprising the steps of:

checking the second level in the cache for a page slot that matches a map index found in the first level during the search; and

installing a preassigned free page slot in the second level in the cache in response to not finding the page slot that matches the map index in the second level in the cache.

19. An apparatus comprising:

are interface configured to process a plurality of read/write operations to/from a memory; and

a control circuit configured to process a plurality of input/output requests to read/write to/from the memory, initiate a recycle operation by generation of a start index and a search range, store the start index and the search range in a queue, search exclusively through a first level in a map in response to the start index and the search range, generate a notification in response to a detection in the first level of the map that one or more of the source blocks to be recycled contain valid data, and suspend the recycle operation while servicing a new command to access the memory, wherein the start index and the search range identify a plurality of source blocks in the memory to be recycled in the recycle operation, the map defines a plurality of translations between a plurality of logical addresses used at a host interface and a plurality of physical addresses used in the memory, the map has a plurality of pages in a second level, the first level in the map indicates if data in the source blocks is valid or not, and all of the first level and a portion less than all of the second level in the map are buffered in a cache while the first level is searched.

20. The apparatus according to claim 19, wherein the interface and the control circuit form part of a solid-state drive controller.