Optimized fragmented block compaction with a bitmap

摘要

A memory system may include an optimized data compaction algorithm. The compaction may include transferring only valid data from a source block to a destination block. A compaction bitmap that is maintained in random access memory (“RAM”) may be populated during the compaction process. The populated bitmap may be used to copy valid fragments to the destination block.

主权项

1. A flash memory device comprising:
a non-volatile storage having an array of memory blocks storing data; and a controller in communication with the non-volatile storage, wherein the controller is configured to:
maintain a compaction bitmap that comprises a plurality of entries that represent corresponding fragments of a source block;populate a first row of the bitmap by processing a first row of the source block, wherein for the processing of the first row, the controller is further configured to:
select a fragment from the first row of the source block, wherein for the fragment selected, the corresponding entry of the bitmap has not been populated;identify a control page associated with the selected fragment; populate each entry in the bitmap that corresponds with the identified control page; andrepeat the processing for a next selected fragment from the first row of the source block until the first row of the bitmap has been populated; andselect an additional row of the source block, wherein the additional row selected for processing corresponds with a row from the bitmap that is least populated.