Method and apparatus for reclaiming and defragmenting a flash memory device

• US 6,038,636 A
• Filed: 04/27/1998
• Issued: 03/14/2000
• Est. Priority Date: 04/27/1998
• Status: Expired due to Term

• Current Assignee: Lexmark International Incorporated (Ninestar Corporation)
• Original Assignee: Lexmark International Incorporated (Ninestar Corporation)
• Inventors: Keith, Matthew Scott, Brown, John Knox III
• Primary Examiner(s): Cabeca, John W.
• Assistant Examiner(s): TZENG, FRED
• Application Number:
  US09/067,495
• Time in Patent Office: 687 Days
• Field of Search: 711/103, 711/159, 711/104, 711/102, 711/139, 711/165, 711/133, 711/170
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2206/1004 Defragmentation
• CPC Class Codes: G06F 2212/7202 Allocation control and policies
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0643 Management of files
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]

Abstract

A method and apparatus for reclaiming space on a flash memory device is provided in which valid data is copied from an individually erasable sector on the flash device to a designated memory location. The sector is then formatted or erased and the valid data is returned to the flash device at the next available free space contiguously. A pointer is updated to keep track of the location of the next available recently formatted free space on the flash device. The process is then repeated on each consecutive sector on the flash memory device until all valid data becomes contiguous on one contiguous segment of the device and all free space becomes contiguous on a second contiguous segment of the device. In this manner, the flash memory is defragmented and the largest possible contiguous file can be written to the device. Files can be saved on the flash memory device in contiguous file formats and blocked file formats. During the reclamation and defragmentation routine, the file format of the valid data is preserved. Also, file blocks on a sector which are originally non-contiguous become contiguous after the routine is performed.

Claims

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

a flash memory device divided into a plurality of individually erasable memory portions;

a designated memory area;

a memory reclamation mechanism configured to copy all valid data from one of the memory portions of the flash memory to the designated memory area, erase the memory portion that was copied, write the valid data from the designated memory area contiguously to the next available free space on the flash memory device, and to repeat the copying, erasing, and writing for each of the plurality of memory portions on the flash memory device in a consecutive order, such that the flash memory device contains no invalid data and contains a plurality of contiguous memory portions which are free;

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 area a memory capacity at least as large as one of the memory portions, wherein the plurality or 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 to portion consecutively through the last portion;

wherein the next available free space comprises the next erased location on the flash memory device beginning from the first portion on the device, and wherein the reclamation mechanism contiguously writes the valid 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 reclamation mechanism has repeated the copying, erasing, and writing for each of the portion on the device.

2. The system as recited in claim 1, wherein each of the memory portions comprises a sector and each sector comprises a plurality of individually readable and writable blocks.

3. The system as recited in claim 1, wherein each of the memory portions comprises a sector and each sector comprises a plurality of individually readable and writable blocks, and wherein the system further comprises:

a file management mechanism configured to store files in the flash memory device in both contiguous formats and blocked formats.

4. The system as recited in claim 1, wherein the valid data on the memory area has a file format associated therewith, and wherein the reclamation mechanism is configured to write the valid data to the next available free space in a manner which maintains the file format of the valid data.

5. The system as recited in claim 1, wherein the designated memory area comprises random access memory external to the flash memory device.

6. The system as recited in claim 1, wherein the valid data comprises at least one file, wherein the at least one file includes a pointer for pointing to the address of the next file on the flash memory;

and wherein the reclamation mechanism is configured to update the pointer of the at least one file header after it is written from the memory area to the next available free space.

7. The system as recited in claim 1, wherein valid data comprises a plurality of files, each file being stored in either a contiguous file format or a blocked file format having at least one block, wherein each block of a blocked file includes a pointer which points to the address of the next block for the file, and wherein the reclamation mechanism is configured to update the pointer of each block of a blocked file after it is written to the next available free space.

8. The system as recited in claim 1, wherein the pointer comprises a bitmap saved on the flash memory device for keeping track of the available free space on the device, wherein reclamation mechanism updates the bitmap after writing the valid data to the next available free space.

9. The system as recited in claim 1, wherein each portion comprises a plurality of physical sectors on at least one flash memory chip.

10. The system as recited in claim 1, wherein the designated memory area has a total memory capacity which is less than the total memory capacity of the flash memory device.

11. 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.

12. The method as recited in claim 11, further comprising:

after the writing step, updating a pointer mechanism to indicate the location of the next available free space on the flash memory device.

13. The method as recited in claim 11, wherein each memory portion comprises a sector and each sector comprises a plurality of individually readable and writable blocks, the method further comprising:

prior to all other steps;

storing the valid data to the flash memory device in either a contiguous file format or a blocked file format as desired;

when a new file is stored to the flash memory device, updating a file pointer for the previously stored file such that the file pointer points to the address of the new file; and

when a new block of a blocked file is stored to the memory device, updating a block pointer for the previously stored block of the blocked file, such that the block pointer points to the address of the new block.

14. The method as recited in claim 13, wherein the file format is preserved during the writing step.

15. The method as recited in claim 13, further comprising:

when a new block of a blocked file is written from the memory area to the next available free space, updating the block pointer for the block previously written from the memory area to the next available free space for the blocked file, such that the updated block pointer points to the address of the new block written.

16. The method as recited in claim 11, further comprising:

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 updated file pointer points to the address of the new file written.

17. The method as recited in claim 11, wherein the writing step further comprises:

if the file is in a contiguous format, writing all data for the contiguous file in the designated memory area to the flash memory device at the next available free space.

18. 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.

19. The method as recited in claim 18, wherein the valid data may be in one of a plurality of file formats, and wherein the file format of the valid data is preserved during the writing step.

20. 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.