Map recycling acceleration

• US 10,303,598 B2
• Filed: 06/29/2016
• Issued: 05/28/2019
• 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): Rossiter, Sean D
• Assistant Examiner(s): Choi, Charles J
• Application Number:
  US15/196,363
• Publication Number:
  US 20160306577A1
• Time in Patent Office: 1,063 Days
• Field of Search: None
• 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 includes a memory and a controller. The memory may be configured to store data. The controller may be configured to process a plurality of input/output requests to read/write to/from the memory. The controller generally includes a processor, a cache and a hardware assist circuit. The processor may be configured to initiate a recycle operation by generation of a start index. The cache may be configured to buffer a first level of a map and less than all of a second level of the map. The hardware assist circuit may be configured to search through the first level or any portions of the second level of the map in the cache in response to the start index, and notify the processor in response to the search detecting one or more blocks in the memory that contain valid data to be recycled.

Claims

1. An apparatus comprising:

a memory configured to store data; and

a controller circuit configured to process a plurality of input/output requests to read/write to/from the memory, the controller circuit comprising

a processor configured to initiate a recycle operation by generation of a start index,

a cache

having a plurality of cache slots, and

configured to buffer a first level of a map and less than all of a second level of the map copied from the memory, and

a hardware assist circuit configured to

search through the first level of the map in the cache to identify one or more first level indices in the first level of the map that correspond to erasure candidate blocks in the memory that contain valid data in response to the start index providing one or more identified first level indices,

search through the second level of the map in the cache to identify one or more of the cache slots holding a cached second level page of the second level of the map that corresponds to the one or more identified first level indices,

install in the cache a preassigned cached second level page corresponding to each of the one or more identified first level indices in response to finding no corresponding cached second level pages,

lock the one or more of the cache slots holding the cached second level pages that correspond to the one or more identified first level indices providing one or more locked cache slots;

notify the processor of the erasure candidate blocks to move during the recycle operation in response to detecting one or more blocks in the memory that contain the valid data to be recycled, and

unlock the one or more locked cache slots holding the cached second level pages after the second level pages in the erasure candidate blocks have been moved to different locations in the memory.

2. The apparatus according to claim 1, wherein the valid data includes map data to be recycled in response to the notification.

3. The apparatus according to claim 2, wherein the map data to be recycled is from the second level of the map.

4. The apparatus according to claim 2, wherein the map data to be recycled is from a third level of the map.

5. The apparatus according to claim 1, wherein the hardware assist circuit is implemented solely in dedicated hardware.

6. The apparatus according to claim 1, wherein the processor is further configured to lock one or more of the cache slots in the cache that buffer the one or more identified first level indices during the recycle operation.

7. The apparatus according to claim 1, wherein the hardware assist circuit is further configured to suspend the recycle operation while servicing a new command to access the memory.

8. The apparatus according to claim 1, wherein the processor is further configured to

update one or more pages of the second level in the cache in response to the recycle operation, and

copy the one or more pages of the second level as updated from the cache to the memory.

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

10. A method for map recycling acceleration, comprising:

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

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

buffering a first level of a map and less than all of a second level of the map copied from the memory in a cache having a plurality of cache slots;

searching through the first level of the map in the cache to identify one or more first level indices in the first level of the map that correspond to erasure candidate blocks in the memory that contain valid data using a hardware assist circuit in response to the start index providing one or more identified first level indices;

searching through the second level of the map in the cache to identify one or more of the cache slots holding a cached second level page of the second level of the map that corresponds to the one or more identified first level indices using the hardware assist circuit;

installing in the cache a preassigned cached second level page corresponding to each of the one or more identified first level indices in response to finding no corresponding cached second level pages using the hardware assist circuit;

locking the one or more of the cache slots holding the cached second level pages that correspond to the one or more identified first level indices providing one or more locked cache slots using the hardware assist circuit;

notifying the processor of the erasure candidate blocks to move during the recycle operation in response to detecting one or more blocks in the memory that contain the valid data to be recycled using the hardware assist circuit; and

unlocking the one or more locked cache slots holding the cached second level pages after the second level pages in the erasure candidate blocks have been moved to different locations in the memory using the hardware assist circuit.

11. The method according to claim 10, wherein the valid data includes map data to be recycled in response to the notification.

12. The method according to claim 11, wherein the map data to be recycled is from the second level of the map.

13. The method according to claim 11, wherein the map data to be recycled is from a third level of the map.

14. The method according to claim 10, wherein the searching is implemented solely in dedicated hardware.

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

locking one or more of the cache slots in the cache that buffer the one or more identified first level indices during the recycle operation.

16. The method according to claim 10, further comprising:

suspending the recycle operation while servicing a new command to access the memory.

17. The method according to claim 10, further comprising:

updating one or more pages of the second level in the cache in response to the recycle operation; and

copying the one or more pages of the second level as updated from the cache to the memory.

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

19. An apparatus comprising:

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

a control circuit comprising

a processor configured to initiate a recycle operation by generation of a start index,

a cache

having a plurality of cache slots, and

configured to buffer a first level of a map and less than all of a second level of the map copied from the memory, and

a hardware assist circuit configured to

search through the first level of the map in the cache to identify one or more first level indices in the first level of the map that correspond to erasure candidate blocks in the memory that contain valid data in response to the start index providing one or more identified first level indices,

search through the second level of the map in the cache to identify one or more of the cache slots holding a cached second level page of the second level of the map that corresponds to the one or more identified first level indices,

install in the cache a preassigned cached second level page corresponding to each of the one or more identified first level indices in response to finding no corresponding cached second level pages,

lock the one or more of the cache slots holding the cached second level pages that correspond to the one or more identified first level indices providing one or more locked cache slots;

notify the processor of the erasure candidate blocks to move during the recycle operation in response to detecting one or more blocks in the memory that contain the valid data to be recycled, and

unlock the one or more locked cache slots holding the cached second level pages after the second level pages in the erasure candidate blocks have been moved to different locations in the memory.

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