Wear leveling with marching strategy

• US 9,501,396 B2
• Filed: 08/16/2013
• Issued: 11/22/2016
• Est. Priority Date: 01/03/2013
• Status: Active Grant

• Current Assignee: Macronix International Co., Ltd.
• Original Assignee: Macronix International Co., Ltd.
• Inventors: Chang, Hung-Sheng, Wang, Cheng-Yuan, Li, Hsiang-Pang, Chang, Yuan-Hao, Hsiu, Pi-Cheng, Kuo, Tei-Wei
• Primary Examiner(s): Yi, David X
• Assistant Examiner(s): Mercado, Ramon A
• Application Number:
  US13/969,462
• Publication Number:
  US 20140189286A1
• Time in Patent Office: 1,194 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0238 Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/109 for multiple virtual address spaces, e.g. segmentation G06F12/1036 takes precedence
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06
• CPC Class Codes: G06F 2212/1032 Reliability improvement, data loss prevention, degraded operation etc
• CPC Class Codes: G06F 2212/7204 Capacity control, e.g. partitioning, end-of-life degradation
• CPC Class Codes: G06F 2212/7211 Wear leveling

Abstract

A method for managing utilization of a memory including a physical address space comprises mapping logical addresses of data objects to locations within the physical address space, and defining a plurality of address segments in the space as an active window. The method comprises allowing writes of data objects having logical addresses mapped to locations within the plurality of address segments in the active window. The method comprises, upon detection of a request to write a data object having a logical address mapped to a location outside the active window, updating the mapping so that the logical address maps to a selected location within the active window, and then allowing the write to the selected location. The method comprises maintaining access data indicating utilization of the plurality of address segments in the active window, and adding and removing address segments from the active window in response to the access data.

Claims

1. A method for managing utilization of a memory including a physical address space, comprising:

mapping logical addresses of data objects to locations within the physical address space, wherein a plurality of address segments in the physical address space forms an active window, and the physical address space includes address segments outside the active window different than those of the plurality of address segments within the active window;

allowing writes of data objects having logical addresses mapped to locations within the plurality of address segments in the active window;

upon detection of a request to write a data object having a logical address mapped to a location outside the active window, updating the mapping so that the logical address maps to a selected location within the active window;

maintaining access data indicating utilization of the plurality of address segments in the active window; and

adding and removing address segments from the active window in response to the access data;

wherein the access data includes a second window count of accesses to the plurality of address segments in the active window, and a set of per-segment counts of accesses to corresponding address segments in the active window.

2. The method of claim 1, further comprising moving the active window in the physical address space.

3. The method of claim 1, wherein the access data includes a first window count of accesses to the plurality of address segments in the active window, including adding an address segment to the active window when the first window count reaches a first threshold for the window and the logical address of the data object is mapped to a selected location outside the active window.

4. The method of claim 3, wherein the step of maintaining access data includes incrementing the first window count upon detection of a request to write a data object, and resetting the first window count if the first window count reaches the first threshold for the window.

5. The method of claim 1, including, upon detection of a request to write a data object having a logical address mapped to a location inside the active window, removing an address segment including the location inside the active window from the active window when the second window count reaches a second threshold for the window and the per-segment count for the address segment reaches a per-segment threshold for the address segment.

6. The method of claim 5, wherein the plurality of address segments include respective sets of more than two containers for the data objects, including upon detection of a request to write a data object having a logical address mapped to a location inside the active window, swapping the data objects between two of the containers in the set of containers in a given address segment including the data object if the per-segment count of accesses to the given address segment is below the per-segment threshold and the second window count reaches the second threshold.

7. The method of claim 1, including upon said detection, moving a data object in the selected location to said location outside the active window and updating the mapping so that a logical address of the data object in the selected location is mapped to said location outside the active window, wherein the data object moved is one of the data objects having logical addresses mapped to locations within the plurality of address segments in the active window before said moving.

8. The method of claim 1, including identifying the selected location using a pointer, and incrementing the pointer to identify a next selected location to be used in case of another request to write to a location outside the active window.

9. The method of claim 1, wherein the mapping includes indirect pointers stored in the memory that includes the plurality of address segments.

10. An apparatus, comprising:

a memory including a physical address space; and

a memory controller coupled to the memory, including logic to map logical addresses of data objects to locations within the physical address space;

logic to define a plurality of address segments in the physical address space as an active window, wherein the physical address space includes address segments outside the active window different than those of the plurality of address segments within the active window;

logic to allow writes of data objects having logical addresses mapped to locations within the plurality of address segments in the active window;

logic, upon detection of a request to write a data object having a logical address mapped to a location outside the active window, to update mapping so that the logical address maps to a selected location within the active window;

logic to maintain access data indicating utilization of the plurality of address segments in the active window; and

logic to add and to remove address segments from the active window in response to the access data,

wherein the access data includes a second window count of accesses to the plurality of address segments in the active window, and a set of per-segment counts of accesses to corresponding address segments in the active window.

11. The apparatus of claim 10, wherein the memory controller further including logic to move the active window in the physical address space.

12. The apparatus of claim 10, wherein the access data includes a first window count of accesses to the plurality of address segments in the active window, and the memory controller includes logic to add an address segment to the active window when the first window count reaches a first threshold for the window and the logical address of the data object is mapped to a selected location outside the active window.

13. The apparatus of claim 12, wherein the logic to maintain access data includes logic to increment the first window count upon detection of a request to write a data object, and logic to reset the first window count if the first window count reaches the first threshold for the window.

14. The apparatus of claim 10, wherein the memory controller includes logic, upon detection of a request to write a data object having a logical address mapped to a location inside the active window, to remove an address segment including the location inside the active window from the active window when the second window count reaches a second threshold for the window and the per-segment count for the address segment reaches a per-segment threshold for the address segment.

15. The apparatus of claim 14, wherein the plurality of address segments include respective sets of more than two containers for the data objects, and the memory controller includes logic, upon detection of a request to write a data object having a logical address mapped to a location inside the active window, to swap the data objects between two of the containers in the set of containers in a given address segment including the data object if the per-segment count of accesses to the given address segment is below the per-segment threshold and the second window count reaches the second threshold.

16. The apparatus of claim 10, wherein the memory controller includes logic, upon said detection, to move a data object in the selected location to said location outside the active window and to update the mapping so that a logical address of the data object in the selected location is mapped to said location outside the active window, wherein the data object moved is one of the data objects having logical addresses mapped to locations within the plurality of address segments in the active window before the data object is moved.

17. The apparatus of claim 10, wherein the memory controller includes logic to identify the selected location using a pointer, and logic to increment the pointer to identify a next selected location to be used in case of another request to write to a location outside the active window.

18. The apparatus of claim 10, wherein the mapping includes indirect pointers stored in the memory that includes the plurality of address segments.