Efficient selection of memory blocks for compaction

• US 8,856,475 B1
• Filed: 06/29/2011
• Issued: 10/07/2014
• Est. Priority Date: 08/01/2010
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Meir, Avraham, Shachar, Michael
• Primary Examiner(s): Bragdon, Reginald
• Assistant Examiner(s): VO, THANH DUC
• Application Number:
  US13/171,467
• Time in Patent Office: 1,196 Days
• US Class Current: 711/165
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 12/0261 using reference counting

Abstract

A method for storing data in a memory that includes multiple memory blocks, includes running a compaction process that selects one or more memory blocks containing both valid data and invalid data, copies the valid data from the selected memory blocks to other storage locations, and then erases the selected memory blocks. At least one memory block, which meets a criterion predictive of imminent invalidation of at least some of the data in the block, is identified. Selection of the identified memory block in the compaction process is inhibited.

Claims

1. A method for storing data in a memory that includes multiple memory blocks, the method comprising:

selecting one or more memory blocks for compaction, wherein each one of the one or more memory blocks includes both valid data and invalid data;

determining a number of accesses of each logical address for each memory block of the one or more memory blocks;

determining one or more frequently-accessed logical addresses of each memory block of the one or more memory blocks dependent upon the number of accesses of each logical address;

identifying at least one of the one or more memory blocks responsive to a determination that a ratio of a number of the one or more frequently-accessed logical addresses of the at least one of one or more memory blocks and a total number of valid logical addresses in the at least one of the one or more memory blocks is greater than a predetermined threshold; and

compacting the selected one or more memory blocks excluding the identified at least one of the one or more memory blocks.

2. The method according to claim 1, wherein the at least one memory block comprises data currently being invalidated.

3. The method according to claim 1, wherein the at least one of the one or more memory blocks comprises data wherein invalidation occurred more recently than a predefined time out period.

4. The method according to claim 1, wherein the at least one of the one or more memory blocks comprises multiple addresses that have been invalidated sequentially.

5. The method according to claim 1, wherein the at least one of the one or more memory blocks comprises an amount of frequently-accessed data greater than a predefined amount.

6. A data storage apparatus, comprising:

an interface for communicating with a memory that includes multiple memory blocks; and

a processor, which is configured to;

select one or more memory blocks for compaction, wherein each one of the one or more memory blocks includes both valid data and invalid data;

determine a number of accesses of each logical address for each memory block of the one or more memory blocks;

determine one or more frequently-accessed logical addresses of each memory block of the one or more memory blocks dependent upon the number of accesses of each logical address;

identify at least one of the one or more memory blocks responsive to a determination that a ratio of a number of the one or more frequently-accessed logical addresses of the at least one of the one or more memory blocks and a total number of valid logical addresses in the at least one of the one or more memory blocks is greater than a predetermined threshold; and

compact the selected one or more memory blocks excluding the identified at least one of the one or more memory blocks.

7. The apparatus according to claim 6, wherein the at least one of the one or more memory blocks includes data which is currently being invalidated.

8. The apparatus according to claim 6, wherein the at least one of the one or more memory blocks includes data wherein invalidation occurred more recently than a predefined time out period.

9. The apparatus according to claim 6, wherein the at least one of the one or more memory blocks includes multiple addresses that have been invalidated sequentially.

10. The apparatus according to claim 6, wherein the at least one of the one or more memory blocks includes an amount of frequently-accessed data greater than a predefined amount.

11. A data storage apparatus, comprising:

a memory comprising multiple memory blocks; and

a processor, which is configured to;

select one or more memory blocks for compaction, wherein each one of the one or more memory blocks includes both valid data and invalid data;

determine a number of accesses of each logical address for each memory block of the one or more memory blocks;

determine one or more frequently-accessed logical addresses of each memory block of the one or more memory blocks dependent upon the number of accesses of each logical address;

identify at least one of the one or more memory blocks responsive to a determination that a ratio of a number of the one or more frequently-accessed logical addresses of the at least one of the one or more memory blocks and a total number of valid logical addresses in the at least one block of the one or more memory blocks is greater than a predetermined threshold; and

compact each memory block of the selected one or more memory blocks excluding the identified at least one of the one or more memory blocks.