Flash memory controller garbage collection operations performed independently in multiple flash memory groups

• US 8,533,384 B2
• Filed: 04/08/2008
• Issued: 09/10/2013
• Est. Priority Date: 12/27/2007
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Enterprise IP LLC (Western Digital Corporation)
• Inventors: Olbrich, Aaron K., Prins, Douglas A.
• Primary Examiner(s): Verbrugge, Kevin
• Application Number:
  US12/082,203
• Publication Number:
  US 20090172258A1
• Time in Patent Office: 1,981 Days
• Field of Search: None
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 13/1657 Access to multiple memories
• CPC Class Codes: G06F 13/28 using burst mode transfer, e.g. direct memory access DMA, cycle steal G06F13/32 takes precedence
• 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/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G11C 16/10 Programming or data input circuits
• CPC Class Codes: G11C 7/1051 Data output circuits, e.g. read-out amplifiers, data output buffers, data output registers, data output level conversion circuits
• CPC Class Codes: G11C 7/1063 Control signal output circuits, e.g. status or busy flags, feedback command signals

Abstract

A flash memory controller connected to multiple flash memory groups performs independent garbage collection operations in each group. For each group, the controller independently determines the amount of free space and performs garbage collection operations if the amount falls below a threshold.

Claims

1. A method of performing garbage collection operations in a system comprising a flash memory controller and a flash memory module made up of at least four groups of flash memory devices having a plurality of flash memory areas, including performing the following steps independently for each flash memory group:

determining the number of flash memory areas that do not contain valid data;

if the number is equal to or less than a first threshold, setting an indicator to a first state;

if the indicator is in the first state, copying data from a first flash memory area to a second flash memory area and erasing the first flash memory area;

further wherein

setting an indicator to a first state further includes;

if the number is equal to or less than a second threshold, setting the indicator to a second state, and the method further includes;

if the indicator is in the second state, determining whether a task list includes pending tasks and, if the list includes pending tasks, carrying out those tasks, and if the list does not include pending tasks, copying data from the first flash memory area to the second flash memory area and erasing the first flash memory area.

2. The method as in claim 1, in which:

in determining the number of flash memory areas that do not contain valid data the determination is based on the number of flash memory areas identified on a list.

3. The method as in claim 2, further including:

adding an identifier of the first area to the list.

4. The method as in claim 3, further including:

resetting the indicator based on the addition of the first area identifier to the list.

5. The method as in claim 1, in which:

each flash memory area consists of one block from each of a plurality of flash memory devices.

6. The method as in claim 5, in which:

copying data from a first flash memory area to a second flash memory area includes;

copying valid data from the first flash memory area to a volatile memory within the flash memory controller; and

copying the data from the volatile memory to the second flash memory area.

7. The method as in claim 1, further comprising:

copying valid data from a third flash memory area to the volatile memory, and

copying the third flash memory area data from the volatile memory to the second flash memory area.

8. The method as in claim 7, further comprising:

data copying consists of simultaneously copying data from a plurality of flash pages.

9. The method as in claim 8, further including:

selecting the second flash memory area as an area in which data collected during garbage collection will be stored, and selecting a third flash memory area as an area in which data received in connection with host write commands will be stored.

10. The method as in claim 9, in which:

the selection of the second flash memory area is based at least in part on the number of one or more types of flash operations that have taken place in the second flash memory area.

11. The method as in claim 1, further including:

prior to copying data from a first flash memory area to a second flash memory area and erasing the first flash memory area, selecting the first flash memory area, the selection being based at least in part on the amount of valid data stored in the first flash memory area.

12. The method as in claim 1, in which:

the selection is also based in part on the number of one or more types of operations that have been performed on the first group.

13. A flash memory controller connected to a group of flash memory-devices, the controller storing programming, the programming comprising:

first programming stored in a first memory, the first programming including

programming that checks the number of free memory areas in a first subgroup of flash memory devices and, if the number is below a threshold, triggers first garbage collection programming, the first garbage collection programming including

programming that selects a first memory area from the first subgroup of flash memory devices and copies the valid data from the first memory area to a first volatile memory within the flash memory controller; and

programming that copies the valid data from the first volatile memory to a second memory area from the first subgroup of flash memory devices; and

programming that erases at least a portion of the first memory area; and

second programming stored in a second memory, the second programming including

programming that checks the number of free memory areas in a second subgroup of flash memory devices and, if the number is below a threshold, triggers second garbage collection programming, the second garbage collection programming including

programming that selects a third memory area from the second subgroup of flash memory devices and copies the valid data from the third memory area to a second volatile memory within the flash memory controller;

programming that copies the valid data from the second volatile memory to a fourth memory area from the second subgroup of flash memory devices, and

programming that erases at least a portion of the third memory area;

wherein

the programming that checks the number of free memory areas in a first subgroup of flash memory devices and, if the number is below a threshold, triggers first garbage collection programming, includes programming that sets one or more first indicators to a first state if the number is below a first threshold or to a second state if the number is below a second threshold, and

the programming that checks the number of free memory areas in a second subgroup of flash memory devices and, if the number is below a threshold, triggers second garbage collection programming, includes programming that sets one or more second indicators to a first state if the number is below the first threshold or to a second state if the number is below the second threshold.

14. The flash memory controller as in claim 13, in which:

the programming that triggers the first garbage collection programming includes programming that checks the state of the one or more first indicators and, if the one or more first indicators are in the first state, defers triggering the first garbage collection programming until after tasks present on a first queue have been completed, but does not defer triggering the first garbage collection programming until after tasks present on the first queue have been completed if the one or more first indicators are in the second state; and

the programming that triggers the second garbage collection programming includes programming that checks the state of the one or more second indicators and, if the one or more second indicators are in the first state, defers triggering the second garbage collection programming until after tasks present on a second queue have been completed, but does not defer triggering the second garbage collection programming until after tasks present on the second queue have been completed if the one or more second indicators are in the second state.

15. The flash memory controller as in claim 13, in which:

the first memory is associated with a first processor contained within the storage controller and the second memory is associated with a second processor contained within the storage controller.

16. The flash memory controller as in claim 15, in which:

each memory area consists of one block from each of the flash memory devices in the subgroup of flash memory devices of which the memory area is a part.

17. The flash memory controller as in claim 16, in which:

the first programming includes programming that, after the erasure of the first memory area or first memory area portion, places an identifier of the first memory area on a first list of free memory areas; and

the second programming includes programming that, after the erasure of the third memory area or third memory area portion, places an identifier of the third memory area on a second list of free memory areas.

18. The flash memory controller as in claim 17, in which:

the programming that checks the number of free memory areas in the first subgroup of flash memory devices does so by checking the number of entries on the first list or by checking an indicator that relates to the number of such entries; and

the programming that checks the number of free memory areas in the second subgroup of flash memory devices does so by checking the number of entries on the second list or by checking an indicator that relates to the number of such entries.

19. The flash memory controller as in claim 16, in which

the programming that selects the first memory area does so at least in part based on the amount of valid data contained in the first memory area in relation to the amount of valid data contained in at least one other memory area in the first subgroup;

and

the programming that selects the third memory area does so at least in part based on the amount of valid data contained in the third memory area in relation to the amount of valid data contained in at least one other memory area in the second subgroup.

20. The flash memory controller as in claim 16, in which

the programming that selects the first memory area does so at least in part based on the number of times the first memory area has been erased in relation to the number of times at least one other memory area in the first subgroup has been erased;

and

the programming that selects the third memory area does so at least in part based on the number of times the third memory area has been erased in relation to the number of times at least one other memory area in the second subgroup has been erased.

21. The flash memory controller as in claim 16, in which:

the programming that selects the first memory area does so at least in part based on an indicator related to the number of data errors encountered or expected in the first memory area or a subpart thereof, and

the programming that selects the third memory area does so at least in part based on an indicator related to the number of data errors encountered or expected in the third memory area or a subpart thereof.