Flash file system

• US 5,404,485 A
• Filed: 03/08/1993
• Issued: 04/04/1995
• Est. Priority Date: 03/08/1993
• 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): Dixon, Joseph L.
• Assistant Examiner(s): Nguyen, Hiep T.
• Application Number:
  US08/027,131
• Time in Patent Office: 757 Days
• Field of Search: 395/400, 395/425, 364/200 MS File, 364/900 MS File
• US Class Current: 711/202
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 3/0601 Interfaces specially adapted for storage systems
• CPC Class Codes: G06F 3/0664 at device level, e.g. emulation of a storage device or system

Abstract

The provision of a flash memory, virtual mapping system that allows data to be continuously written to unwritten physical address locations. The virtual memory map relates flash memory physical location addresses in order to track the location of data in the memory.

Claims

1. A memory management method for a memory in which data can be written only in unwritten physical memory locations and in which a zone of contiguous memory locations can be simultaneously erased, comprising the steps of:

organizing the memory into a plurality of units;

organizing each unit into a plurality of blocks, each of said blocks made up of a plurality of contiguous physical memory locations;

establishing an allocation map for each unit which indicates the status of each block in a unit as written, unwritten or deleted;

establishing a virtual map to map virtual addresses to physical addresses;

in writing data to said memory at a virtual address;

(a) mapping said virtual address to a physical block address using said virtual map;

(b) examining said allocation map for said unit to which said virtual address has been mapped in step (a) to determine the status of a block at said physical block address as written, unwritten or deleted;

(c) if said block at said physical block address is in written or deleted status;

(1) examining said allocation map for at least one of said units to identify an unwritten block address;

(2) writing said data into said memory to said unwritten block address;

(3) changing said allocation map for a block in a unit in which said data have been written in paragraph (c)(2) to indicate as written said previously unwritten block address where said data have been written;

(4) changing said virtual map to map virtual addresses to physical addresses within a unit so that said virtual map maps said virtual address to the physical address of said previously unwritten block in which said data have been written in step (c)(2);

establishing a transfer unit in said memory in which all blocks are in unwritten status, said transfer unit including a transfer unit allocation map;

periodically identifying a selected unit, other than said transfer unit, to be erased;

reading each written block in said selected unit;

writing each written block in said selected unit into said transfer unit;

updating said transfer unit allocation map to indicate as written the status of blocks that have been written in the just previous writing step;

erasing said selected unit;

updating said virtual map to reflect the above-described movement of said written blocks.

2. A memory management method for a memory in which data can be written only in unwritten physical memory locations and in which a zone of contiguous memory locations can be simultaneously erased, comprising the steps of:

storing in said memory a first virtual map which maps virtual addresses to physical addresses;

organizing said first virtual map stored in said memory in segments of page addressable blocks;

storing in a random access memory a second virtual map which maps page addresses to physical addresses of said page addressable blocks in said memory;

changing a page addressable block in said first virtual map stored in said memory by writing a changed page addressable block in an unwritten physical block location; and

updating said second virtual map stored in said random access memory so that it maps the page address of the changed page addressable block to the unwritten physical block location in which said changed page addressable block has been written.

3. A memory management method for a memory in which data can be written only in unwritten physical memory locations and in which a zone of contiguous memory locations can be simultaneously erased, comprising the steps of:

organizing the memory into a plurality of units;

organizing each unit into a plurality of blocks, each of said blocks made up of a plurality of contiguous physical memory locations;

establishing a first virtual map to map virtual addresses to physical addresses within a unit;

storing in said memory said first virtual map organized in segments of page addressable blocks;

storing in a random access memory a second virtual map which maps pages to physical address of said page addressable blocks stored in said memory; and

in writing data to said memory at a virtual address;

(a) deriving a page address from said virtual address;

(b) mapping said page address to a page addressable block in said memory;

(c) reading a segment of said first virtual map which maps virtual address to physical address at said page addressable block in said memory;

(d) mapping said virtual address to a physical address;

(e) if said block at said physical address is in written or deleted status;

(1) writing said data into said memory to an unwritten block address;

(2) changing said first virtual map segment so that said first virtual map maps said virtual address to the physical address of the unwritten block in which said data have been written in step (e)(1);

(3) writing the changed first virtual map segment from step (e)(2) in an unwritten physical block location in said memory;

(4) updating said second virtual map stored in said random access memory so that it maps the page address of the changed first virtual map segment of said unwritten physical block location.

4. A memory management method for a memory in which data can be written only in unwritten :

physical memory locations and in which a zone of contiguous memory locations can be simultaneously erased, comprising the steps of;

organizing the memory into a plurality of units;

organizing each unit into a plurality of blocks, each of said blocks made up of a plurality of contiguous physical memory locations;

establishing an allocation map for each unit which indicates the status of each block in a unit as written, unwritten or deleted;

establishing a virtual map to map virtual addresses to physical addresses within a unit;

in writing data to said memory at a virtual address;

(a) mapping said virtual address to a physical block address using said virtual map;

(b) examining said allocation map for said unit to which said virtual address has been mapped in step (a) to determine the status of a block at said physical block address as written, unwritten or deleted;

(c) if said block at said physical block address is in written or deleted status;

(1) examining said allocation map for at least one of said units to identify an unwritten block address;

(2) writing said data to said unwritten block address;

(3) changing said allocation map for a block in a unit in which said data have been written in step (c)(2) to indicate as written said previously unwritten block address where said data have been written;

(4) changing said virtual map to map virtual addresses to physical addresses within a unit so that said virtual map maps said virtual address to the physical address of said previously unwritten block in which said data have been written in step (c)(2); and

in reading data from said memory at a virtual address;

(d) mapping said virtual address to a physical block address using said virtual map;

(e) reading said data from said memory at said physical address;

establishing a transfer unit in said memory in which all blocks are in unwritten status, said transfer unit including a transfer unit allocation map;

periodically identifying a selected unit, other than said transfer unit, to be erased;

reading each written block in said selected unit;

writing each written block in said selected unit into said transfer unit;

updating said transfer unit allocation map to indicate as written the status of blocks that have been written in the just previous writing step;

erasing said selected unit;

updating said virtual map to reflect the above-described movement of said written blocks.

5. A memory management method for a memory in which data can be written only in unwritten physical memory locations and in which a zone of contiguous memory locations can be simultaneously erased, comprising the steps of:

organizing the memory into a plurality of units;

organizing each unit into a plurality of blocks, each of said blocks made up of a plurality of contiguous physical memory locations;

establishing a first virtual map to map virtual addresses to physical addresses within a unit;

storing in said memory said first virtual map organized in segments of page addressable blocks;

storing in a random access memory a second virtual map which maps pages to physical address of said page addressable blocks stored in said memory; and

in writing data to said memory at a virtual address;

(a) deriving a page address from said virtual address;

(b) mapping said page address to page addressable block in said memory;

(c) reading a segment of said first virtual map which maps virtual address to physical address at said page addressable block in said memory;

(d) mapping said virtual address to a physical address;

(e) if said block at said physical address is in an active written status;

(1) writing said data into said memory to an unwritten block address;

(2) changing said first virtual map segment so that said first virtual map maps said virtual address to the physical address of the unwritten block in which said data has been written in step (e)(1);

(3) writing the changed first virtual map segment from step (e)(2) in an unwritten physical block location in said memory;

(4) updating said second virtual map stored in said random access memory so that maps the page address of the changed first virtual map segment of said unwritten physical block location;

in reading data from said memory at a virtual address;

(f) deriving a page address from said virtual address;

(g) mapping said page address to page addressable block in said memory;

(h) reading a segment of said first virtual map that maps virtual address to physical address at said page addressable block in said memory;

(i) mapping said virtual address to a physical address;

(j) reading said data from said memory at said physical address.

6. A memory management method as in claim 5, including the further steps of:

establishing a transfer unit in said memory in which all blocks are in unwritten status, said transfer unit including a transfer unit allocation map;

periodically identifying a selected unit, other than said transfer unit, to be erased;

reading each written block in said selected unit;

writing each written block in said selected unit into said transfer unit;

updating said transfer unit allocation map to indicate as written the status of blocks that have been written in the just previous writing step;

erasing said selected unit;

updating said virtual map to reflect the above-described movement of said written blocks.