Method and apparatus for reclaiming and defragmenting a flash memory device

A method for reclaiming memory filled by invalid data on a flash memory device, comprising:

• accessing an individually erasable memory portion of a flash memory device;
• copying valid data from the accessed portion to a designated memory area having a memory capacity at least as large as the accessed memory portion and smaller than the total memory capacity of the flash memory device;
• erasing the accessed memory portion;
• writing the valid data from the designated memory area to the next available free space on the flash memory device such that the valid data is stored contiguously on the next available free space;
• and
• repeating the above steps on each successive individually erasable memory portion of the flash memory device, such that the flash memory device contains no invalid data and contains a plurality of contiguous memory portions which are free;
• wherein the memory portions have successive addresses from a first portion a last portion, wherein the steps are started at the first portion and repeated on each successive portion through the last portion in a continuous manner, such that all valid data becomes contiguous on a first contiguous on a first contiguous segment of the flash memory and all free space becomes contiguous on a second contiguous segment of the flash memory;
• and wherein the writing step comprises:
• determining whether a file in the designated memory area is in a blocked format or a contiguous format;
• and
• if the file is in a blocked format, writing all data for the blocked file in the designated memory area to the the flash memory device contiguous at the next available free space.

A computer-readable medium having encoded thereon a method for reclaiming invalid memory on a flash memory device, wherein the flash memory device includes a plurality of individually erasable memory portions ranging from a first portion to a last portion, the method comprising:

• accessing the first portion of the flash memory device;
• copying valid data from the accessed portion to a designated memory area having a memory capacity at least as large as the accessed portion and smaller than the total memory capacity of the flash memory device;
• erasing the accessed memory portion;
• writing the valid data from the designated memory area to the next available free space on the flash memory device such that the valid data is stored contiguously on the flash memory device;
• after the writing step, updating a pointer mechanism to indicate the location of the next available free space on the flash memory device;
• repeating the steps on each successive individually erasable memory portion through the last portion of the flash memory device in a continuous manner, such that no invalid data remains on the flash memory device and such that all valid data becomes contiguous on a first contiguous segment of the flash memory and all free space becomes contiguous on a second contiguous segment of the flash memory;
• when a new file is written from the memory area to the next available free space, updating a file pointer for the previous file written from the memory area to the next available free space, such that the file pointer points to the address of the file written;
• wherein the writing step comprises:
• determining whether a file in the designated memory area is in a blocked format or a contiguous format;
• and
• if the file is in a blocked format, writing all data for the blocked file in the designated memory area to the memory device contiguously at the next available free space.

A system for reclaiming memory filled by invalid data on a flash memory device, the system comprising:

• an erasable flash memory device in a printer;
• a designated memory area in said printer having a memory capacity smaller than the total memory capacity of the flash memory device;
• a memory reclamation mechanism in said printer configured to copy all valid data from a portion of the flash memory to the designated memory area, erase the flash memory portion that was copied, write the valid data from the memory area contiguously to the next available free space on the flash memory device, and repeat the copying, erasing, and writing on remaining portions of the flash memory such that no invalid data remains on the flash memory device, all valid data on the flash memory device becomes contiguous, and all free space on the flash memory device becomes contiguous;
• and
• a pointer configured for keeping track of the address of the next available free space on the flash device, wherein the reclamation mechanism updates the pointer after writing the valid data to the next available free space;
• wherein the designated memory area has a memory capacity at least as large as one of the memory portions, wherein the flesh memory portions have successive addresses from a first portion to a last portion, wherein the reclamation mechanism is configured to start the copying, erasing, and writing at the first portion and continue without interruption from portion consecutively through the last portion;
• wherein the next available free space comprises the erased location on the flash memory device beginning from the first portion on the device, and wherein the reclamation mechanism contiguously write the valid data from the designated memory area to the next available free space such that all valid data on the flash memory device becomes contiguous on a first contiguous segment of the flash memory device and all free memory on the flash memory device becomes contiguous on a second contiguous segment of the device after the reclamation mechanism has repeated the copying, erasing, and writing for each of the portions on the device.