Flash management techniques

• US 8,667,213 B2
• Filed: 09/14/2012
• Issued: 03/04/2014
• Est. Priority Date: 06/23/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Rogers, Andrew, Patel, Sachin C., Gopalan, Yadhu N.
• Primary Examiner(s): DUDEK JR, EDWARD J
• Application Number:
  US13/618,268
• Publication Number:
  US 20130013856A1
• Time in Patent Office: 536 Days
• Field of Search: None
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0292 using tables or multilevel address translation means G06F12/023 takes precedence; address translation in virtual memory systems G06F12/10
• CPC Class Codes: G06F 2212/2022 Flash memory

Abstract

Various flash management techniques may be described. An apparatus may comprise a processor, a flash memory coupled to the processor, and a flash management module. The flash management module may be executed by the processor to receive a write request to write data to the flash memory, write a first control sector with a sequence number to the flash memory, and write the sequence number, an address for a logical sector, and data to at least one physical sector corresponding to the logical sector of the flash memory. Other embodiments are described and claimed.

Claims

1. A method, comprising:

performing a write transaction comprising;

writing a first control sector with a sequence number to a flash memory, wherein the control sector is not a data sector and wherein the sequence number is determined using bidirectional counting, wherein a most significant bit of the sequence number is used to designate a current direction of the bidirectional counting;

writing a checksum to the first control sector; and

writing the sequence number, an address for a logical sector, and data to at least one physical sector mapped to the logical sector;

determining whether the physical sector corresponding to the logical sector is dirty using the sequence number;

validating a checksum of a last write sector; and

compacting all blocks on the flash memory that contain the data written to the at least one physical sector, when the checksum of the last write sector fails, so that the write transaction is rolled back.

2. The method of claim 1, the compacting comprising:

determining that an idle threshold has been reached; and

determining a number of free sectors to be reclaimed from the failed write transaction.

3. The method of claim 2, comprising:

performing compaction for a block having at least one of;

the highest number of dirty sectors and the lowest sequence number, when the idle threshold is reached, wherein compaction is complete when the number of free sectors to be reclaimed are reclaimed.

4. The method of claim 2, comprising:

determining that the idle threshold has been reached when a number of dirty sectors exceeds a number of free sectors.

5. The method of claim 1, the compacting comprising:

determining whether a block to be compacted has any mapped sectors;

indicating that a mapped sector needs to be copied when the block has mapped sectors;

requesting a new free block to copy mapped sectors to;

updating a logical-to-physical mapping table with the new free block information; and

requesting a sequence number for the new free block.

6. The method of claim 5, comprising:

creating a new compaction control sector having the requested sequence number, the new compaction control sector having a source sector run and a destination sector run that describes a copy operation and the blocks that are to be erased;

writing the compaction control sector to the new free block;

copying the mapped sectors from a source location to a destination location in the new free block; and

erasing all blocks containing sectors to be deleted when the copying is complete.

7. The method of claim 5, comprising:

resuming an interrupted compaction operation by;

determining that a checksum of a last copy sector is invalid; and

determining where a destination copy starts with respect to the block.

8. The method of claim 7, wherein the destination copy starts in the middle of the block, the method comprising:

copying all of the sectors with their same sequence number;

writing a write sector to invalidate the mapping table for the copied sectors; and

starting a new compaction operation including the sectors in the interrupted compaction and new sectors in the destination block that need to be copied, where the blocks to be erased comprise the same blocks to erase as in the interrupted compaction and all of the destination blocks in the interrupted compaction.

9. The method of claim 7, wherein the destination copy starts in the beginning of the block, the method comprising:

erasing all destination blocks from the interrupted compaction;

resuming copy operations from the interrupted compaction; and

erasing the blocks to be erased from the interrupted compaction again.

10. An apparatus, comprising:

a processor;

a flash memory coupled to the processor; and

a flash management module that when executed by the processor is arranged to;

perform a write transaction comprising;

write a first control sector with a sequence number to the flash memory, wherein the control sector is not a data sector and wherein the sequence number is determined using bidirectional counting, wherein a most significant bit of the sequence number is used to designate a current direction of the bidirectional counting;

write a checksum to the first control sector; and

write the sequence number, an address for a logical sector, and data to at least one physical sector mapped to the logical sector;

determine whether the physical sector corresponding to the logical sector is dirty using the sequence number;

validate a checksum of a last write sector; and

compact all blocks on the flash memory that contain the data written to the at least one physical sector, when the checksum of the last write sector fails, so that the write transaction is rolled back.

11. The apparatus of claim 10, the flash management module having a compactor module to recycle dirty sectors into free sectors, the compactor module arranged to:

determine that an idle threshold has been reached; and

determine a number of free sectors to be reclaimed from the failed write transaction.

12. The apparatus of claim 11, the compactor module arranged to:

perform compaction for a block having at least one of;

the highest number of dirty sectors and the lowest sequence number, when the idle threshold is reached, wherein compaction is complete when the number of free sectors to be reclaimed are reclaimed.

13. The apparatus of claim 11, the compactor module arranged to:

determine that the idle threshold has been reached when a number of dirty sectors exceeds a number of free sectors.

14. The apparatus of claim 10, the compactor module arranged to:

determine whether a block to be compacted has any mapped sectors;

indicate that a mapped sector needs to be copied when the block has mapped sectors;

request a new free block to copy mapped sectors to;

update a logical-to-physical mapping table with the new free block information; and

request a sequence number for the new free block.

15. The apparatus of claim 14, the compactor module arranged to:

create a new compaction control sector having the requested sequence number, the new compaction control sector having a source sector run and a destination sector run that describes a copy operation and the blocks that are to be erased;

write the compaction control sector to the new free block;

copy the mapped sectors from a source location to a destination location in the new free block; and

erase all blocks containing sectors to be deleted when the copying is complete.

16. The apparatus of claim 14, the compactor module arranged to:

resume an interrupted compaction operation by;

determine that a checksum of a last copy sector is invalid; and

determine where a destination copy starts with respect to the block.

17. The apparatus of claim 16, wherein the destination copy starts in the middle of the block, the compactor module arranged to:

copying all of the sectors with their same sequence number;

write a write sector to invalidate the mapping table for the copied sectors; and

start a new compaction operation including the sectors in the interrupted compaction and new sectors in the destination block that need to be copied, where the blocks to be erased comprise the same blocks to erase as in the interrupted compaction and all of the destination blocks in the interrupted compaction.

18. The apparatus of claim 16, wherein the destination copy starts in the beginning of the block, the compactor module arranged to:

erase all destination blocks from the interrupted compaction;

resume copy operations from the interrupted compaction; and

erasing the blocks to be erased from the interrupted compaction again.