Moving sectors within a block of information in a flash memory mass storage architecture

• US 6,145,051 A
• Filed: 03/08/1999
• Issued: 11/07/2000
• Est. Priority Date: 07/31/1995
• Status: Expired due to Term

• Current Assignee: Micron Technology, Inc.
• Original Assignee: Lexar Media Incorporated (Micron Technology, Inc.)
• Inventors: Ganjuei, Ali R., Estakhri, Petro, Iman, Berhau
• Primary Examiner(s): BRAGDON, REGINALD GLENWOOD
• Application Number:
  US09/264,340
• Time in Patent Office: 610 Days
• Field of Search: 711/103, 711/156, 711/165, 711/203, 711/206
• US Class Current: 711/103
• CPC Class Codes: G06F 11/1008 in individual solid state devices G06F11/1004 takes precedence
• CPC Class Codes: G06F 11/1068 in sector programmable memories, e.g. flash disk G06F11/1072 takes precedence
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2211/109 Sector level checksum or ECC, i.e. sector or stripe level checksum or ECC in addition to the RAID parity calculation
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G11C 16/08 Address circuits; Decoders; Word-line control circuits
• CPC Class Codes: G11C 16/102 External programming circuits, e.g. EPROM programmers; In-circuit programming or reprogramming; EPROM emulators
• CPC Class Codes: G11C 29/765 in solid state disks
• CPC Class Codes: G11C 29/82 for EEPROMs
• CPC Class Codes: G11C 8/12 Group selection circuits, e.g. for memory block selection, chip selection, array selection

Abstract

A device is disclosed for storing mapping information for mapping a logical block address identifying a block being accessed by a host to a physical block address, identifying a free area of nonvolatile memory, the block being selectively erasable and having one or more sectors that may be individually moved. The mapping information including a virtual physical block address for identifying an "original" location, within the nonvolatile memory, wherein a block is stored and a moved virtual physical block address for identifying a "moved" location, within the nonvolatile memory, wherein one or more sectors of the stored block are moved. The mapping information further including status information for use of the "original" physical block address and the "moved" physical block address and for providing information regarding "moved" sectors within the block being accessed.

Claims

1. A memory controller for use with a host requiring access to a nonvolatile memory, the controller being responsive to commands and logical block addresses (LBA'"'"'s) received from the host, a group of LBAs for identifying one or more information blocks to be accessed in the nonvolatile memory, each of the information blocks including a plurality of N sectors, the nonvolatile memory including a plurality of selectively erasable block locations, each of the block locations having a plurality of physical block address locations (PBA locations), each of the PBA locations for storing a portion of an information block, the controller being operative to develop physical block addresses (PBA'"'"'s) for addressing corresponding ones of the PBA locations, the controller also being operative to access portions of an information block stored in more than one of the block locations, whereby the controller avoids transfer of a particular information block from one block location to another block location each time the host requests that a portion of the particular information block be rewritten.

2. A memory controller as recited in claim 1 further comprising mapping means responsive to the LBA'"'"'s provided by the host, and operative to generate mapping information for each of the information blocks, the mapping information for identifying and accessing portions of the information blocks, the mapping information for a stored information block including:

a first virtual block address indicating a first block location storing original information of the stored information block;

a second virtual block address for indicating a second block location for storing a moved portion of the stored information block, the moved portion including rewritten information of the stored information block, the moved portion superseding a corresponding superseded portion of the original information; and

status information for indicating whether a portion of the original information has been superseded.

3. A memory controller as recited in claim 1 further comprising mapping means responsive to the LBA'"'"'s provided by the host, and operative to generate mapping information for each of the information blocks, the mapping information for identifying and accessing portions of the information blocks, the mapping information for a stored information block including:

a first virtual block address indicating a first block location storing original sectors of the stored information block;

a second virtual block address for indicating a second block location for storing moved sectors of the stored information block, the moved sectors including rewritten information of the stored information block, the moved sectors superseding corresponding ones of the original sectors of the stored information block; and

status information for indicating whether any of the original sectors of the stored information block have been superseded.

4. A memory controller as recited in claim 3 wherein each of the block locations includes N PBA locations, and wherein each of the PBA locations provides storage space for one of the sectors.

5. A memory controller as recited in claim 4 wherein the mapping means includes a volatile memory unit for storing a table including a plurality of LBA rows each being uniquely addressable by a corresponding one of the LBA'"'"'s, each of the LBA rows for storing the mapping information associated with a information block indicated by the corresponding LBA.

6. A memory controller as recited in claim 5 wherein the status information further comprises sector move status information indicating which of the original sectors have been superseded by moved sectors.

7. A memory controller as recited in claim 6 wherein the table further comprises a plurality of PBA rows each being uniquely addressable by a corresponding one of the PBA'"'"'s, each of the PBA rows for storing the mapping information associated with a corresponding one of the sectors.

8. A memory controller as recited in claim 7 wherein the mapping information stored in each of the PBA rows further includes a used flag for indicating whether the corresponding PBA location is currently being used to store a portion of an information block.

9. A memory controller as recited in claim 6 wherein if the sector move status information associated with a particular one of the information blocks indicates that a predetermined number of the original sectors of the particular information block have been superseded and therefore moved to the second block location, the controller transfers the unsuperseded original sectors of the stored information block to the second block location, and an old flag corresponding with the first block location is set to indicate that the entire first block location is superseded.

10. A memory controller as recited in claim 5 further comprising one or more nonvolatile memory devices, each device including a plurality of the block locations, each block location being uniquely addressable by a corresponding one of the PBAs.

11. A memory controller as recited in claim 10 wherein each of the block locations of the devices provides for storing the mapping information associated with a information block stored in a block location, and wherein the controller further includes means for copying the mapping information from the volatile memory unit to the nonvolatile memory devices.

12. A memory controller as recited in claim 11 wherein upon power-up, the mapping information associated with each of the PBA'"'"'s is read from the nonvolatile memory devices and stored in the corresponding LBA row of the table in the volatile memory unit.

13. A memory controller as recited in claim 5 wherein the volatile memory unit comprises a random access memory (RAM).

14. A memory controller as recited in claim 4 wherein N is equal to sixteen.

15. A memory controller as recited in claim 4 wherein N is equal to thirty two.

16. A memory controller as recited in claim 4 wherein N is equal to sixty four.

17. A memory controller as recited in claim 3 wherein the status information further comprises sector move status information for indicating which of the original sectors have been superseded by moved sectors.

18. In a memory controller for use with a host requiring access to a nonvolatile memory, the controller being responsive to a logical block addresses (LBAs) received from the host, a group of LBAs for identifying one or more information blocks to be accessed in the nonvolatile memory, each of the information blocks including a plurality of N sectors, the nonvolatile memory including a plurality of selectively erasable block locations, each of the block locations having a plurality of physical block address locations (PBA locations), each of the PBA locations for storing a portion of an information block, the controller being operative to develop physical block addresses (PBA'"'"'s) for addressing corresponding ones of the PBA locations, a method for storing and retrieving portions of an information block to and from more than one of the block locations, the method comprising the steps of:

receiving a first write command indicating a particular LBA, and receiving an information block indicated by the particular LBA from the host, the information block including a plurality of original sectors, the first write command requesting the controller to store the information block in the nonvolatile memory;

determining a first block location which is free;

storing the information block in the first block location;

receiving a second write command indicating the particular LBA, and receiving at least one rewrite sector superseding corresponding superseded ones of the original sectors of the stored information block, the second write command requesting the controller to rewrite the at least one rewrite sector to the nonvolatile memory;

determining a second block location which is free;

storing the at least one rewrite sector in the second block location;

generating and storing mapping information associated with the particular LBA, the mapping information including,

a first virtual block address indicating the first block location,

a second virtual block address indicating the second block location, and

status information indicating whether any of the original sectors of the stored information block have been superseded;

whereby the controller avoids transfer of the entire particular information block to another block location each time the host requests that a portion of the particular information block be re-written.

19. In a memory controller as recited in claim 18 wherein the status information further comprises move status information indicating which of the original sectors have been superseded by rewritten sectors.

20. In a memory controller as recited in claim 19 wherein the controller further comprises a volatile memory unit, and wherein the step of generating and storing mapping information associated with the particular LBA further comprises allocating a table within the volatile memory unit, the table including a plurality of LBA rows each being uniquely addressable by a corresponding one of the LBA'"'"'s, and being configured to store the mapping information associated with the corresponding one of the LBA'"'"'s.

21. In a memory controller as recited in claim 20 further comprising the steps of:

receiving a read command indicating the particular LBA from the host, the read command requesting the controller to read the stored information block from the nonvolatile memory;

accessing the table within the volatile memory unit, and reading the mapping information associated with the particular LBA to determine the first block location, the second block location, and the superseded sectors associated with the particular LBA;

reading all original sectors except the superseded sectors from the first block location; and

reading the superseded sectors from the second block location.

22. In a memory controller as recited in claim 20 wherein each of the block locations provides for storing the mapping information associated with the information blocks, the method further comprising the step of copying the mapping information from the volatile memory unit to the nonvolatile memory.

23. In a memory controller as recited in claim 20 wherein the block locations provide for storing the mapping information associated with the LBA'"'"'s, the method further comprising the steps of:

upon power-up, reading the mapping information associated with each of the LBA'"'"'s from the nonvolatile memory; and

storing the mapping information associated with each of the LBA'"'"'s in the corresponding LBA row of the table in the volatile memory unit.

24. In a memory controller as recited in claim 20 further comprising the steps of:

if the move status information associated with the stored information block indicates that a predetermined number of the original sectors have been superseded and moved to the second block location,

transferring unsuperseded original sectors of the stored information block to the second block location, and

setting an old flag corresponding with the first block location to indicate that the entire contents of the first block location is superseded.

25. In a memory controller as recited in claim 20 wherein the table further comprises a plurality of PBA rows each being uniquely addressable by a corresponding one of the PBA'"'"'s, each of the PBA rows for storing the mapping information associated with a corresponding one of the sectors.

26. In a memory controller as recited in claim 25 wherein the mapping information stored in each of the PBA rows further includes a used flag indicating whether the corresponding PBA location is currently being used to store a sector.