Flash file system optimized for page-mode flash technologies

• US 5,937,425 A
• Filed: 10/16/1997
• Issued: 08/10/1999
• Est. Priority Date: 10/16/1997
• Status: Expired due to Term

• Current Assignee: SanDisk IL Ltd. (Western Digital Corporation)
• Original Assignee: M-Systems Flash Disk Pioneers Ltd. (Western Digital Corporation)
• Inventors: Ban, Amir
• Primary Examiner(s): Chan, Eddie P.
• Assistant Examiner(s): Portka, Gary J.
• Application Number:
  US08/951,644
• Time in Patent Office: 663 Days
• Field of Search: 711/103, 711/165, 711/209, 711/202, 365/185.29, 365/185.33, 365/185.22, 365/218
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages

Abstract

A method for organizing a flash memory in which the size of the memory portion for reading or writing data, such as a block, differs from the size of the smallest portion for erasing, such as a unit. The method of the present invention is particularly useful for page-mode devices exemplified by the NAND and AND technologies, in order to enable these devices to be reorganized when no more unwritten physical units are available.

Claims

1. A memory organization method for a memory in which data can only be written to an unwritten portion of the memory, such that a written portion of the memory must be erased to become unwritten, and in which the size of the memory portion for reading or writing data differs from the size of the smallest memory portion for erasing, the method comprising the steps of:

(a) providing a plurality of physical units of the memory, each of said physical units being the size of the smallest memory portion for erasing, each of said physical units being designated by a physical unit number and each of said physical units being divided into a plurality of physical blocks, each of said plurality of physical blocks being the size of the memory portion for reading or writing data and each of said physical blocks being designated by a physical block offset within said physical unit;

(b) providing a plurality of virtual units of the memory, each virtual unit being designated by a virtual unit number and each of said virtual units featuring a plurality of virtual blocks, each of said virtual blocks being designated by a virtual block offset within said virtual unit;

(c) mapping each virtual unit to at least one physical unit to form a virtual map; and

(d) mapping each virtual block within said virtual unit to one physical block within said at least one physical unit according to said virtual map.

2. The method of claim 1, further comprising the steps of:

(e) receiving a write command to write data at a virtual block;

(f) locating a virtual unit containing said virtual block;

(g) locating a writable block within a physical unit mapped to said virtual unit; and

(h) writing said data to said writable physical block to form a written physical unit.

3. The method of claim 2, further comprising the steps of:

(i) if an unwritten physical block in said written physical unit cannot be located, locating a second physical unit;

(j) writing said data to a writable physical block of said second physical unit; and

(k) updating said virtual map by additionally mapping said virtual unit to said second physical unit, such that said virtual unit corresponds to said second physical unit and to said written physical unit, said second physical unit and said written physical unit forming a chain of physical units.

4. The method of claim 3, wherein said writable physical block of said second physical unit has a physical block offset, and said physical block offset corresponds to said virtual block offset of said mapped virtual unit.

5. The method of claim 3, further comprising the steps of:

(l) if an unwritten physical block cannot be located in any physical unit, locating a second virtual unit corresponding to a plurality of physical units in a chain;

(m) locating said last physical unit in said chain;

(n) moving data from each of said physical blocks of said written physical unit to a writable physical block of said last physical unit, said writable physical block having the same block offset as said physical block of said written physical unit; and

(o) updating said virtual map by mapping said virtual unit to said last physical unit, such that said virtual unit corresponds only to said last physical unit.

6. The method of claim 5, further comprising the step of:

(p) erasing all of said written physical units in said chain, with the exception of said last physical unit.

7. The method of claim 3, further comprising the steps of:

(l) if no unwritten physical unit is available for allocation for said chain, allocating an unwritten physical unit for reorganization;

(m) moving data from each of said physical blocks of said written physical unit to a writable physical block of said unwritten physical unit; and

(n) updating said virtual map by mapping said virtual unit to said unwritten physical unit, such that said virtual unit corresponds only to said unwritten physical unit.

8. The method of claim 7, further comprising the step of:

(o) erasing all of said written physical units.

10. The method of claim 1, further comprising the step of:

(e) altering said virtual map to reflect a change in the memory by changing a correspondence between at least one of said plurality of virtual units of the memory and at least one of said plurality of physical units of the memory.

11. The method of claim 3, wherein said writable physical block of said second physical unit has a physical block offset, and said physical block offset is different than said virtual block offset of said mapped virtual unit.

9. A memory organization method for a memory in which data can only be written to an unwritten portion of the memory, such that a written portion of the memory must be erased to become unwritten, and in which the size of the memory portion for reading or writing data differs from the size of the smallest memory portion for erasing, the method comprising the steps of:

(a) providing a plurality of physical units of the memory each of said physical units being the smallest memory portion for erasing, each of said physical units being designated by a physical unit number and each of said physical units being divided into a plurality of physical blocks, each of said plurality of physical blocks being the memory portion for reading or writing data and each of said physical blocks being designated by a physical block offset within said physical unit;

(b) providing a plurality of virtual units of the memory, each virtual unit being designated by a virtual unit number and each of said virtual units featuring a plurality of virtual blocks, each of said virtual blocks being designated by a virtual block offset within said virtual unit;

(c) providing a virtual map for mapping each virtual unit to at least one physical unit;

(d) mapping each virtual block within said virtual unit to one physical block within said at least one physical unit;

(e) receiving a write command to write data at a virtual block;

(f) locating a virtual unit containing said virtual block;

(g) locating a writable block within a physical unit mapped to said virtual unit;

(h) writing said data to said writable physical block;

(i) if an unwritten physical block in a written physical unit cannot be located, allocating an unwritten physical unit to form a chain of physical units, such that said unwritten physical unit is a last physical unit in said chain;

(j) writing said data to an unwritten physical block in said last physical unit;

(k) moving data from each of said plurality of physical blocks to a writable physical block of said last physical unit, except data written in step (j); and

(l) updating said virtual map by mapping said virtual unit to said written physical unit, such that said virtual unit corresponds to said written physical unit.

12. A method of writing data for a memory in which data can only be written to an unwritten portion of the memory, such that a written portion of the memory must be erased to become unwritten, the method comprising the steps of:

(a) providing a plurality of physical units being divided into a plurality of physical blocks, each of said physical units having a physical unit number and each of said physical blocks having a physical block offset within said physical unit;

(b) providing a plurality of virtual units being divided into a plurality of virtual blocks, each of said virtual units having a virtual unit number and each of said virtual blocks having a virtual block offset within said virtual unit, each virtual unit being mapped to at least one physical unit;

(c) receiving a write command to write data at a virtual block;

(d) determining a virtual unit containing said virtual block having a virtual block offset;

(e) locating a physical unit corresponding to said virtual unit;

(f) locating a physical block within said physical unit;

(g) determining if said physical block is unwritten;

(h) writing said data to said physical block only if said physical block is unwritten;

(i) alternatively, if said physical block is not unwritten, allocating second physical unit;

(j) locating a writable physical block within said second physical unit, said writable physical block having a physical block offset;

(k) writing said data to said writable physical block;

(l) additionally mapping said virtual unit to said second physical unit containing said writable physical block, such that said virtual unit is additionally mapped to said second physical unit to form a chain of physical units;

(m) if an unwritten physical block in a written physical unit cannot be located, locating a second virtual unit corresponding to a plurality of physical units in a chain;

(n) locating a last physical unit in said chain;

(o) transferring all data within said physical blocks of said written physical unit to said physical blocks of said last physical unit; and

(p) updating said virtual map such that said virtual unit corresponds only to said last physical unit.

13. The method of claim 12, wherein said physical block offset of said writable physical block has an identical block offset number as said virtual block offset.

14. The method of claim 12, further comprising the step of:

(q) erasing all of said written physical units.

15. A method of writing data for a memory in which data can only be written to an unwritten portion of the memory, such that a written portion of the memory must be erased to become unwritten, the method comprising the steps of:

(a) providing a plurality of physical units being divided into a plurality of physical blocks, each of said physical units having a physical unit number and each of said physical blocks having a physical block offset within said physical unit;

(b) providing a plurality of virtual units being divided into a plurality of virtual blocks, each of said virtual units having a virtual unit number and each of said virtual blocks having a virtual block offset within said virtual unit, each virtual unit being mapped to at least one physical unit;

(c) receiving a write command to write data at a virtual block;

(d) determining a virtual unit containing said virtual block having a virtual block offset;

(e) locating a physical unit corresponding to said virtual unit;

(f) locating a physical block within said physical unit;

(g) determining if said physical block is unwritten;

(h) writing said data to said physical block only if said physical block is unwritten;

(i) alternatively, if said physical block is not unwritten, allocating a second physical unit;

(j) locating a writable physical block within said second physical unit, said writable physical block having a physical block offset;

(k) writing said data to said writable physical block; and

(l) additionally mapping said virtual unit to said second physical unit containing said writable physical block, such that said virtual unit is additionally mapped to said second physical unit to form a chain of physical units;

(m) if no unwritten physical unit is available for allocation, locating a last physical unit in said chain;

(n) transferring all data within said physical blocks of said written physical units to said physical blocks of said last physical unit; and

(o) updating said virtual map such that said virtual unit corresponds only to said last physical unit.

16. The method of claim 15, further comprising the step of:

(p) erasing all of said written physical units, with the exception of said last physical unit.

17. A memory organization method for a memory in which data can only be written to an unwritten portion of the memory, such that a written portion of the memory must be erased to become unwritten, and in which the size of the memory portion for reading or writing data differs from the size of the smallest memory portion for erasing, the method comprising the steps of:

(a) providing a plurality of physical units of the memory, each of said physical units being the size of the smallest memory portion for erasing, each of said physical units being designated by a physical unit number and each of said physical units being divided into a plurality of physical blocks, each of said plurality of physical blocks being the size of the memory portion for reading or writing data and each of said physical blocks being designated by a physical block offset within said physical unit;

(b) providing a plurality of virtual units of the memory, each virtual unit being designated by a virtual unit number and each of said virtual units featuring a plurality of virtual blocks, each of said virtual blocks being designated by a virtual block offset within said virtual unit;

(c) providing a virtual map for mapping each virtual unit to at least one physical unit;

(d) mapping each virtual block within said virtual unit to one physical block within said at least one physical unit;

(e) receiving a write command to write data at a virtual block;

(f) locating a virtual unit containing said virtual block;

(g) locating a writable block within a physical unit mapped to said virtual unit;

(h) writing said data to said writable physical block to form a written physical unit;

(i) if an unwritten physical block in said written physical unit cannot be located, locating a second physical unit with a writable physical block;

(i) writing said data to said writable physical block of said second physical unit;

(k) updating said virtual map by additionally mapping said virtual unit to said second physical unit, such that said virtual unit corresponds to said second physical unit and to said written physical unit, said second physical unit and said written physical unit forming a chain of physical units;

(l) if an unwritten physical block in any physical unit cannot be located, locating a second virtual unit corresponding to a plurality of physical units in a chain;

(m) locating a last physical unit in said chain;

(n) moving data from each of said physical blocks of said written physical unit to a writable physical block of said last physical unit, said writable physical block having substantially the same block offset as said physical block of said written physical unit; and

(o) updating said virtual map by mapping said virtual unit to said last physical unit, such that said virtual unit corresponds only to said last physical unit.