Block cleanup: page reclamation process to reduce garbage collection overhead in dual-programmable NAND flash devices

1. An apparatus comprising:

a memory to store a mapping table, wherein the mapping table indicates a rewriteable state of a plurality of memory addresses;

an erasure-based, non-volatile memory configured to store information, at respective memory addresses, in an encoded format, wherein the encoded format includes more bits than the an unencoded version of the information and wherein the encoded format allows the information be over-written, at least once, without an intervening erase operation; and

a processor configured to perform garbage collection based, at least in part upon, the rewriteable state associated with the respective memory addresses, wherein the processor is configured to, as part of the garbage collection, determine that at least one memory address is associated with an erasure-free rewriteable state.

2. The apparatus of claim 1 , wherein the processor is configured to:

select a victim block of memory addresses; and

copy the information stored at the at least one memory address to a memory address outside of the victim block.

3. The apparatus of claim 2 , wherein the mapping table within the memory is configured to, in response to the copying of the information from the at least one memory address, indicate that the at least one memory address is free.

4. The apparatus of claim 3 , wherein the processor is configured to:

receive a write command, wherein the write command includes information in a format other than the encoded format; and

store the information, in the encoded format, in at least one of the at least one memory addresses.

5. The apparatus of claim 2 , wherein the processor is configured to:

copy the information stored at the at least one memory address to a memory address that is associated with a rewriteable state that does not require an intervening erase operation.

6. The apparatus of claim 2 , wherein the processor is configured to:

select a target memory address based upon the target memory addresses rewriteable state, wherein the processor prefers a target memory address associated with a rewriteable state that does not require an intervening erase operation; and

copy the information stored at the at least one memory address to the target memory address.

7. The apparatus of claim 2 , wherein the processor is configured to:

erase the memory addresses included within the victim block.

8. The apparatus of claim 1 , wherein the processor is configured to:

select a victim block of memory addresses;

determine that partial garbage collection may be performed on at least a portion of the victim block;

marking the portion of the victim block as free, based on the determination that the partial garbage collection may be performed; and

erasing the entire victim block, based on the determination that the partial garbage collection may be performed.

9. A system comprising:

a processor configured to transmit memory commands to an erasure-based, non-volatile memory device; and

the erasure-based, non-volatile memory device is configured to perform, to a single target physical memory address, a first and at least a second write commands without an intervening erase operation,

wherein the erasure-based, non-volatile memory device comprises:

a non-volatile memory configured to:

store the information, at respective memory addresses, in an encoded format, wherein the encoded format includes more bits than an unencoded version of the information and wherein the encoded format allows the information to be over written, at least once, without an intervening erase operation, and

update, as part of performing each write command, a rewritable state associated with a respective physical memory address; and

an internal processor configured to:

perform garbage collection based, at least in part upon, the rewriteable state associated with the respective memory addresses, wherein the internal processor is configured to, as part of the garbage collection, determine if the respective memory address is associated with an erasure-free rewriteable state.

10. The system of claim 9 , wherein the internal processor is configured to:

select a victim block of memory addresses; and

copy the information stored at the at least one memory address to a memory address outside of the victim block.

11. The system of claim 10 , wherein the non-volatile memory is configured to, in response to the copying of the information from the victim block's at least one memory address, indicate that the at least one memory address is free.

12. The system of claim 11 , wherein the erasure-based, non-volatile memory device is configured to:

receive a write command, wherein the write command includes information in a format other than the encoded format; and

store the information, in the encoded format, in at least one of the victim block's at least one memory addresses.

13. The system of claim 10 , wherein the erasure-based, non-volatile memory device is configured to:

copy the information stored at the at least one memory address to a memory address that is associated with a rewriteable state that does not require an intervening erase operation.

14. The system of claim 10 , wherein the erasure-based, non-volatile memory device is configured to:

select a target memory address based upon the target memory addresses rewriteable state, wherein the processor prefers a target memory address associated with a rewriteable state that does not require an intervening erase operation; and

copy the information stored at the at least one memory address to the target memory address.

15. The system of claim 10 , wherein the erasure-based, non-volatile memory device is configured to:

erase the memory addresses included within the victim block.

16. The system of claim 9 , wherein the erasure-based, non-volatile memory device is configured to:

select a victim block of memory addresses;

determine that partial garbage collection may be performed on at least a portion of the victim block;

mark the portion of the victim block as free, based upon the determination that the partial garbage collection may be performed; and

erase the entire victim block, based upon the determination that the partial garbage collection may be performed.

17. A method comprising:

storing information, at respective memory addresses within erasure-based, non-volatile memory, in an encoded format, wherein the encoded format includes more bits than the an unencoded version of the information and wherein the encoded format allows the information be over-written, at least once, without an intervening erase operation;

selecting a victim block of memory addresses to perform at least partial garbage collection upon;

determining, within the victim block, that at least one memory address is associated with an erasure-free rewriteable state; and

copying the information stored at the victim block's at least one memory address to a second memory address outside of the victim block.

18. The method of claim 17 , wherein the encoded format allows the information be over-written according to a binary tree that dictates that the information may be over-written from a first encoded value to one of either the first encoded value or a predefined, based upon the first encoded value, second encoded value; and

in response to the copying of the information, indicating that the at least one memory address is free.

19. The method of claim 17 , further comprising:

receiving a write command, wherein the write command includes information in a format other than the encoded format; and

storing the information, in the encoded format, in at least one of the victim block's at least one memory addresses.

20. The method of claim 17 , wherein copying comprises copying the information stored at the at least one memory address to a memory address that is associated with a rewriteable state that does not require an intervening erase operation.