Flash file system optimized for page-mode flash technologies
First Claim
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.
3 Assignments
0 Petitions
Accused Products
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.
-
Citations
17 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 10, 11)
-
-
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. - View Dependent Claims (13, 14)
-
-
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. - View Dependent Claims (16)
-
-
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.
-
Specification