Block reuse for memory operations

• US 10,698,621 B2
• Filed: 04/23/2018
• Issued: 06/30/2020
• Est. Priority Date: 04/23/2018
• Status: Active Grant

• Current Assignee: JP Morgan Chase Bank, N.A. (JP Morgan Chase & Co)
• Original Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Inventors: Widder, Eyal
• Primary Examiner(s): Warren, Tracy A
• Application Number:
  US15/959,852
• Publication Number:
  US 20190324669A1
• Time in Patent Office: 799 Days
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/1009 using page tables, e.g. page table structures
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 2212/657 Virtual address space management
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7203 Temporary buffering, e.g. using volatile buffer or dedicated buffer blocks
• CPC Class Codes: G06F 2212/7207 management of metadata or control data
• CPC Class Codes: G06F 2212/7208 Multiple device management, e.g. distributing data over multiple flash devices
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/0673 Single storage device
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

Apparatuses, systems, and methods are disclosed for block reuse for memory operations. An apparatus may include one or more storage elements and a controller. A controller may be configured to manage a metadata structure and a metadata change structure. In certain embodiments, the metadata structure stores metadata relating to the one or more storage regions and the metadata change structure stores changes to be made to the metadata structure. A controller may be configured to perform an availability check to determine if one or more presently allocated storage regions identified in a metadata change structure are reusable. A controller may be configured to allocate one of a storage region from one or more presently allocated storage regions and a free storage region from a free memory group based on an availability check.

Claims

1. An apparatus comprising:

one or more storage elements comprising one or more storage regions; and

a controller configured to;

manage a metadata structure and a metadata change structure, wherein the metadata structure stores metadata relating to the one or more storage regions, the metadata describing mappings of physical addresses to logical addresses, and the metadata change structure comprises a queue of changes to be made to the metadata structure;

perform an availability check that determines whether to reallocate one or more presently allocated storage regions identified in the metadata change structure, wherein reallocation of presently allocated storage regions identified in the metadata change structure does not release reallocated storage regions to a free memory group of storage regions that are not identified in the metadata change structure; and

reallocate a storage region from the one or more presently allocated storage regions based on the availability check.

2. The apparatus of claim 1, wherein the availability check determines if the storage region in the one or more presently allocated storage regions is erasable.

3. The apparatus of claim 2, wherein the storage region is erasable in response to the availability check determining that there is no valid data stored on the storage region.

4. The apparatus of claim 2, wherein the storage region is erasable in response to the availability check determining that an amount of valid data stored on the storage region is less than an amount specified by a valid data threshold.

5. The apparatus of claim 4, wherein the controller relocates valid data stored on the storage region to another storage region in response to the availability check determining that the amount of valid data stored on the storage region is less than the amount specified by the valid data threshold.

6. The apparatus of claim 2, wherein the storage region is a least recently used storage region in response to the availability check determining that a plurality of storage regions in the one or more presently allocated storage regions are erasable.

7. The apparatus of claim 1, wherein the controller increments a reuse counter associated with a storage region based on the storage region being reallocated from the one or more presently allocated storage regions.

8. The apparatus of claim 7, wherein the availability check determines to reallocate the storage region based on the reuse counter being less than a reallocation threshold.

9. The apparatus of claim 1, wherein the controller erases the storage region.

10. The apparatus of claim 1, where the controller is further configured to allocate a free storage region from the free memory group in response to the availability check determining not to reallocate one or more presently allocated storage regions.

11. A method comprising:

handling a plurality of memory requests, wherein changes to be made to a metadata structure that stores metadata relating to the plurality of memory requests are queued by a metadata change structure, the metadata describing mappings of physical addresses to logical addresses;

reallocating a presently allocated storage region without releasing the reallocated storage region to a free memory group of storage regions that are not identified in the metadata change structure, in response to a first memory request in the plurality of memory requests, based on the presently allocated storage region satisfying a validity threshold and a reallocation threshold, wherein the presently allocated storage region is identified in the metadata change structure; and

allocating a free storage region from the free memory group in response to a second memory request in the plurality of memory requests based on a determination that no presently allocated storage regions satisfy the validity threshold and the reallocation threshold.

12. The method of claim 11, wherein the presently allocated storage region satisfies the reallocation threshold based on a reuse counter for the presently allocated storage region being less than the reallocation threshold, wherein the reuse counter for the presently allocated storage region is incremented upon a reallocation of the presently allocated storage region.

13. The method of claim 11, wherein the presently allocated storage region satisfies the validity threshold based on the amount of valid data stored on the presently allocated storage region being less than the validity threshold.

14. The method of claim 11, wherein reallocating the presently allocated storage region comprises erasing data stored on the presently allocated storage region.

15. The method of claim 11, wherein reallocating the presently allocated storage region comprises relocating valid data stored on the presently allocated storage region to one or more other allocated storage regions.

16. The method of claim 11, further comprising selecting a least recently used presently allocated storage region in response to multiple presently allocated storage regions satisfying the validity threshold and the reallocation threshold.

17. The method of claim 11, further comprising incrementing a re-use counter associated with the presently allocated storage region in response to the reallocation of the presently allocated storage region.

18. An apparatus comprising:

means for storing changes to a metadata structure, wherein metadata in the metadata structure describes a mapping of physical addresses to logical addresses, and the means for storing changes to the metadata structure comprises a queue of changes to be made to the metadata structure;

means for comparing an amount of data stored on a previously allocated storage region against a validity threshold;

means for wear leveling for the previously allocated storage region based on a reuse counter associated with the previously allocated storage region being less than a reallocation threshold, the reallocation threshold defining a limit for how many times a presently allocated storage region can be reallocated; and

means for reallocating the presently allocated storage region without releasing the presently allocated storage region to a free memory group of storage regions that are not identified in the metadata change structure, based on the comparison of the presently allocated storage region against the validity threshold and the reallocation threshold, wherein the presently allocated storage region is identified in the means for storing changes to the metadata structure, prior to reallocating the presently allocated storage region.