Object based extent mapping for flash memory

1. In a flash memory system comprising a controller and flash memory that stores object data of a plurality of executing applications as a plurality of managed units (“MUs”) of object data distributed non-contiguously in a plurality of erase blocks of said flash memory, a MU comprising an addressable storage location in said flash memory containing a unit of object data of a single one application of said plurality of applications, and an erase block comprising a block said flash memory sized to contain a plurality of MUs of object data of different ones of said applications, a method of managing the flash memory by rearranging valid MUs of valid object data in consecutive order of creation in free erase blocks to empty an erase block of valid object data and reclaim that empty erase block for new object data of said executing applications, comprising:

selecting as a candidate erase block for reclamation an erase block in said flash memory;

determining costs to move directly from said selected candidate erase block to one or more free erase blocks valid MUs of all objects present in said selected candidate erase block and to move directly to said free erase blocks other valid MUs of the same applications which produced said valid MUs present in said selected candidate erase block that are distributed among other ones of said plurality of erase blocks, said determining comprising determining for all of said valid MUs a number and a sequence of said valid MUs of said objects that must be moved to said free erase block from said selected candidate erase block and from said other ones of said plurality of erase blocks in said flash memory to arrange all valid MUs of each application moved to said free erase block in contiguous order of creation by such application in said free erase block to form an extent of contiguous valid MUs of said each object in said free erase block;

repeating said selecting and determining steps for other candidate erase blocks;

selecting from among candidate erase blocks a selected erase block for movement of valid MUs requiring the fewest moves to move all of said valid MUs in said selected erase block and all valid MUs produced by the same executing applications in other erase blocks to a free erase block;

moving from said selected erase block and from said other erase blocks directly to said free erase block said valid MUs in said contiguous order of creation to contiguous storage locations of said free erase block to form said extent without intermediate moves of said valid MUs to a memory external to said flash memory;

determining whether said moving leaves said selected erase block empty of valid MUs; and

if not, repeating said foregoing steps until at least one selected erase block is empty of valid MUs.

2. The method of claim 1 wherein said moving comprises reorganizing a selected object into said free erase block by writing individual valid MUs of the selected object directly from one or more of said other ones of said plurality of erase blocks in said contiguous order of creation as said extent of MUs into said free erase block of the flash memory.

3. The method of claim 2 , wherein said reorganizing is performed as part of refreshing the contents of said flash memory.

4. The method of claim 1 , wherein, upon there being two or more erase blocks having valid MUs of objects of different applications, the movement of which MUs results in said two or more of said blocks being equally less full, the method further comprises selecting first the object to move that has the least cost to move.

5. The method of claim 4 , wherein selecting the object that has the least cost to move comprises selecting that object that has the fewest valid MUs to move.

6. The method of claim 4 further comprising erasing said empty erase block for reuse.

7. In a flash memory system comprising a controller and flash memory that stores object data of executing applications as a plurality of managed units (“MUs”) of object data distributed non-contiguously in a one or more physical erase blocks of said flash memory, a MU comprising an addressable storage location in said flash memory containing a unit of object data of a single one executing application, and an erase block comprising a block of said flash memory sized to contain a plurality of MUs, a method of managing the flash memory by rearranging valid MUs of valid object data into consecutive order of creation in a free erase block directly without the need for intermediate moves of said valid MUs to a memory external to said flash memory to reclaim erase blocks for new object data of said executing applications, comprising:

inspecting a plurality of erase blocks containing MUs of object data for a candidate erase block for movement of MUs of objects to a free erase block, and selecting as a candidate erase block an erase block having valid MUs of the fewest number of objects;

determining costs to move to said free erase block valid MUs of all said objects that have valid MUs present in said selected candidate erase block and to move to said free erase block other valid MUs of such objects distributed among other ones of said plurality of erase blocks, said determining comprising determining for all said valid MUs a number and a sequence of said valid MUs of such objects that must be moved to said free erase block from said selected erase block and from said other ones of said plurality of erase blocks to arrange all valid MUs of such objects that are moved to said free erase block in contiguous order of creation in said free erase block to form an extent of contiguous valid MUs of said object in said free erase block;

said selected candidate erase block having the least cost to move all valid MUs of objects in said selected candidate erase block and all valid MUs of said objects in said other ones of said plurality of erase blocks in said flash memory; and

moving directly from said selected candidate erase block and from said plurality of other erase blocks valid non-contiguous MUs of an object, in order of creation by one application, to the free erase block without intermediate moves of said valid MUs to a memory external to said flash memory such that after movement said MUs are stored in said order of creation in contiguous locations in said free erase block.

8. The method of claim 7 , wherein upon there being two or more erase blocks having valid MUs, the movement of which results in more than one erase block being equally less full, selecting for movement MUs in an erase block that has the fewest valid MUs.

9. The method of claim 8 , wherein said moving comprises moving valid MUs in an order that results in the greatest reductions in the number of MUs in said selected erase block.

10. The method of claim 7 , wherein said moving comprises moving a plurality of individual valid MUs in order of creation from said selected and said plurality of erase blocks of said flash memory to said free erase block of said flash memory to create an extent of contiguous MUs, and storing in an extent tree mapping data comprising a starting address and a length for said extent.

11. The method of claim 7 , wherein said flash memory system further comprises program memory that stores computer readable executable instructions for controlling said controller to perform said method.

12. The method of claim 11 , wherein said computer readable executable instructions further control said controller to select objects asynchronously with applications writing MUs to said flash memory by iteratively moving in order of creation individual MUs of said objects from source erase blocks to one or more free erase blocks to create extents of contiguous MUs in said free erase blocks, and to erase a source erase block for reuse upon all valid MUs being moved from said source erase block.

13. The method of claim 7 further comprising erasing said selected erase block if said selected erase block is empty following movement of said valid MUs.