Memory system with a non-volatile memory, having address translating function

• US 6,377,500 B1
• Filed: 11/09/2000
• Issued: 04/23/2002
• Est. Priority Date: 11/11/1999
• Status: Expired due to Term

• Current Assignee: Toshiba Memory Corporation (Kioxia Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Fujimoto, Akihisa, Nomura, Katsuyuki
• Primary Examiner(s): Fears, Terrell W.
• Application Number:
  US09/708,423
• Time in Patent Office: 530 Days
• Field of Search: 365/189.01, 365/189.04, 365/230.03, 365/230.01
• US Class Current: 365/230.01
• 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
• CPC Class Codes: G11C 15/00 Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores
• CPC Class Codes: G11C 15/046 using non-volatile storage elements

Abstract

Logical block addresses are allocated to the blocks provided on a flash memory, respectively. Address translation tables (LTPb'"'"'s) are provided on the flash memory, each for a group of blocks. Groups of logical block addresses are provided, each group for one group of blocks provided on the flash memory. The logical block addresses of each group have a specific field each. The same data item is contained in the specific fields of the logical block addresses of any group. The data item designates all blocks of the group corresponding to the group of the logical block addresses. Each table has a group of entries storing physical address information indicating the locations that the blocks take in the flash memory. At least one of the tables is stored on a RAM. When a logical address is given from a host system, a microprocessor determines whether a table corresponding to the logical address exists on the RAM. If such table does not exist, the table is copied from the flash memory to the RAM. The microprocessor refers to the corresponding entry in the table on the RAM in accordance with the logical block address contained in the logical address, thereby performing translation from a logical address to a physical address.

Claims

1. A memory storing a plurality of address translation tables to translate into a physical address a logical address given to access said non-volatile memory, said plurality of address translation tables being associated with respective different logical address ranges;

a volatile memory having an address translation table area for storing at least one table fewer than the total number of the tables of said plurality of address translation tables on said non-volatile memory; and

means for translating a logical address into a physical address by utilizing said address translation table on said volatile memory.

2. The memory system according to claim 1, further comprising:

means for, when a logical address is given for accessing said non-volatile memory, determining whether said address translation table corresponding to the logical address range to which the logical addresses belong exists on said volatile memory; and

means for, when it is determined by said determining means that said corresponding address translation table does not exist on said volatile memory, copying the address translation table from said non-volatile memory to the address translation table area on said volatile memory, thereby replacing an original address translation table on the address translation table area with the address translation table.

3. The memory system according to claim 2, further comprising a pointer table in which pointer information indicating each storage position of said plurality of address translation tables on said non-volatile memory is registered to be associated with the logical address range specific to each of the address translation tables, wherein, when it is determined by said determining means that said corresponding address translation table does not exist on said volatile memory, said copying means acquires the corresponding pointer information by referring to said pointer table, and copies the address translation table on said non-volatile memory indicated by the pointer information to the address translation table area on said volatile memory.

4. The memory system according to claim 2, further comprising specifying means for specifying that any of said plurality of address translation tables is stored in said volatile memory, wherein said determining means determines whether said address translation tables corresponding to the logical address range to which the given logical addresses belong exist on said volatile memory in accordance with the specification contents of said specifying means.

5. The memory system according to claim 2, wherein:

said non-volatile memory is a rewritable non-volatile memory and consists of a plurality of blocks in which a specific logical block addresses are allocated;

said address translation tables are provided, each for a group of blocks to which logical block addresses are allocated, respectively, which belong to a logical address range and which have each a specific field containing the same data item;

each of the address translation tables has a group of entries that can be designated by the logic block addresses allocated to the blocks of the group corresponding to the group of entries;

each entry is provided for registering physical address information that represents a location which a block takes in the non-volatile memory;

when a logical address range to which the given logical address belongs is defined as a logical address range indicated by the contents of the specific field of a logical block address contained in the logical address, said determining means determines whether said address translation table corresponding to this logical address range exists on said volatile memory;

when it is determined by said determining means that said corresponding address translation table exists on said volatile memory, said translating means refers to the corresponding entries in said address translation table on the volatile memory by the logical block address contained in the given logical address, and thereby translates the given logical address to the corresponding physical address, and otherwise, said translating means waits the address translation table has been copied to said volatile memory by said copying means, and then, refers to the corresponding entries of said address translation table on the volatile memory according to the logical block addresses contained in the assigned logical addresses, and thereby translates the given logical address to the corresponding physical address.

6. The memory system according to claim 5, further comprising:

allocating means for, when physical address information is not registered in the entry of said address translation table referred to by said translating means, searching for an empty block on said non-volatile memory, thereby allocating a logical block address in the given logical address to the block; and

registering means for writing physical address information on a block in which the logical block address is allocated by said allocating means into an entry referred to in said address translation table on said volatile memory and entry in the address translation table on said non-volatile memory corresponding to the entry referred to.

7. The memory system according to claim 5, further comprising:

means for, when writing into said non-volatile memory is performed based on the physical address translated by said translating means, detecting whether or not a block error occurs; and

substituting means for, when an occurrence of said block error is detected by said detecting means, searching an empty block on said non-volatile memory to allocate a logical block address contained in the given logical address to the block, thereby updating, to physical address information of the block, an entry referred to in said address translation table on said volatile memory and an entry in address translation table on said non-volatile memory corresponding to the entry referred to.

8. The memory system according to claim 5, wherein said copying means copies, during startup of said memory system, at least one table fewer than the total number of the tables of said plurality of address translation tables on said non-volatile memory to said address translation table area on said volatile memory.

9. The memory system according to claim 5, wherein:

a pointer table area for storing a pointer table is secured on said volatile memory;

pointer information indicating each storage position on said non-volatile memory of said plurality of address translation tables is registered on said pointer table to be associated with the contents of a specific filed of a logical block address specific to each of the address translation tables; and

when it is determined by said determining means that said corresponding address translation table does not exist on said volatile memory, said copying means refers to said pointer table in accordance with the contents of said specific field of a logic block address contained in the given logical address to acquire the corresponding pointer information, and copies said address translation table on said non-volatile memory indicated by the pointer information to the address translation area table on said volatile memory.

10. The memory card according to claim 9, further comprising generating means for, during startup of said memory system, generating said pointer table to be stored in said pointer table area of said volatile memory.

11. The memory system according to claim 5, wherein:

said non-volatile memory is managed in units of zones each consisting of a group of blocks to which logical block addresses are allocated, respectively, which belong to a logical address range and which have each a specific field containing the same data item;

any one of the zones is allocated to a system area including a management area storing system management information;

said each address translation table is stored in any one block included in the corresponding zone of said non-volatile memory;

said copying means copying, at the time of starting up the memory system, an address translation table stored in at least one of zones of said non-volatile memory, excluding the zone allocated to the system area and an address translation table stored in the zone allocated to the system area to the address translation table area of said volatile memory; and

when said determining means determines that said corresponding address translation table does not exist on said volatile memory, the copying means substitutes for said corresponding address translation table any one address translation table excluding an address translation table corresponding to said system area from among the address translation tables on the address translation table area.

12. The memory system according to claim 11, wherein:

a pointer table area for storing a pointer table is secured on said volatile memory;

pointer information indicating each storage position in said non-volatile memory of said address translation tables is registered in said pointer table and associated with the contents of the specific field of a logical block address specific to each of the address translation table;

each block on said non-volatile memory consists of a plurality of sectors having a predetermined size that is a minimum unit of access to the memory;

each of said sectors comprises a logical block address field in which a logical block address allocated to a block to which the sector belongs is set and a flag field in which flag information indicating a use state of the block is set;

said flag information indicates one of three use states of the blocks, in the first of which the blocks are used to store a valid address translation table, in the second of which the blocks are used to store an invalidated address translation table, and in the third of which the blocks are used to store valid data other than an address translation table;

said memory system further comprises means for generating said pointer table having registered pointer information acquired by said each zone of said non-volatile memory during startup of said memory system;

said generating means sequentially refers to blocks in the zone by said each zone of said non-volatile memory, and detects a sector indicated to be employed for storing a valid address translation table by a flag field of said redundant section, thereby acquiring said pointer information;

said copying means acquires, when it is determined by said determining means that said corresponding address translation table does not exist on said volatile memory, the corresponding pointer information by referring to said pointer table in accordance with the contents of the specific field of the logical block address included in the given logical address, and thereby copies to said address translation table area on said volatile memory said address translation table on said non-volatile memory indicated by the pointer information.

13. The memory system according to claim 12, further comprising:

allocating means for, when physical address information is not registered in an entry for said address translation table on said volatile memory, said entry having been referred to by said translating means, searching for an empty block provided in a zone in which an address translation table on said non-volatile memory corresponding to the address conversion table on said volatile memory is stored, and allocating to the block a logical block address contained in the given logical address;

registering means for writing physical address information of the block in which the logical block address is allocated by said allocating means into the entry for said address translation table on said volatile memory refereed to by said translating means; and

update means for searching an empty block targeted for a zone in which an address translation table on said non-volatile memory is stored, the table corresponding to said address translation table on said volatile memory refereed to by said translating means, and writing said address translation table in which physical address information written by said registering means into a predetermined area included in the block, wherein said update means is adopted to set flag information indicating the first state to a flag field of the redundant section of each sector in the predetermined area in which said address translation table is written, and to set flag information indicating the second state to a flag field of the redundant section of each sector in an area in which an original address translation table on said non-volatile memory is stored.

14. The memory system according to claim 13, further comprising:

detecting means for, when writing into said non-volatile memory is performed based on a physical address translated by said translating means, detecting whether a block error occurs or not; and

substituting means for, when an occurrence of a block error is detected by said detecting means, searching an empty block targeted for a zone in which an address translation table on said non-volatile memory is stored, the table corresponding to said address translation table on said volatile memory referred to by said translating means, allocating a logical block address in the given logical address to the block, and updating the entry referred to in said address translation table on said volatile memory based on physical address information of the block, wherein said update means is adopted to search an empty block targeted for a zone in which an address translation table on said non-volatile memory is stored, the table corresponding to said address translation table on said volatile memory refereed to by said translating means, to write said address translation table in which the entry referred to is updated in a predetermined area included in the block by said substituting means, to set flag information indicating the first state to a flag field of the redundant section of each sector in the predetermined area in which the address translation table is written, and to set flag information indicating the second state to a flag field of the redundant section of each sector in an area in which an original address translation table on said non-volatile memory, corresponding to the table is stored.

15. The memory system according to claim 14, further comprising:

assignment table stored to be paired with said address translation table in a block in which the address translation table is stored by each zone of said non-volatile memory, wherein;

said assignment table contains flag information indicating whether the blocks in said corresponding zone are used;

an assignment table area for storing said assignment table paired with said plurality of address translation tables on said non-volatile memory stored in said address translation table area is secured on said volatile memory; and

any of said allocating means, said update means and substituting means are adopted to search said empty block by referring to, in a predetermined direction, said assignment table on the volatile memory paired with said address translation table on said volatile memory referred to by said translating means.

16. The memory system according to claim 15, wherein:

a pointer specifying a reference position in said assignment table is added to each said assignment table; and

any of said allocating means, said update means and said substituting means are adopted to refer to said assignment table while said pointer added to said assignment table is advanced in a predetermined direction.

17. The memory system according to claim 16, wherein:

any of said allocating means, said update means and said substituting means are adopted to update said assignment table when said empty block is searched by referring to said assignment table on said volatile memory, and

said update means writes into said empty block said assignment table provided on said volatile memory and paired with the table when said address translation table on said volatile memory is written into said empty block.

18. A method of translating a logical address given to access a non-volatile memory, into a physical address, said non-volatile memory storing a plurality of address translation tables employed for translating into a physical address a logical address given to access said non-volatile memory, said address translation tables being associated with the respective different logical address ranges, said method comprising the steps of:

storing in an address translation table area secured on a volatile memory a plurality of tables fewer than the total number of the tables of said plurality of address translation tables stored in said non-volatile memory; and

when a logical address for accessing said non-volatile memory is given, translating the logical address into a physical address by utilizing one of said plurality of address translation tables on said volatile memory.

19. A method of translating into a physical address a logical address given to access a non-volatile memory, which is managed in units of zones each consisting of group of blocks to which logical block addresses are allocated, respectively, which belong to a logical address range and which have each a specific field containing the same data item, one of said zones having been allocated to a system area in which system management information is to be stored, said method comprising the steps of:

preparing address translation tables for groups of blocks, each address translation table having a group on entries for registering physical address information indicating the positions at which the blocks are stored on the non-volatile memory, said blocks each having a specific field containing the same data item and being to be designated by the logical block address contained in a logical address;

storing each address translation table, thus prepared, into one of blocks provided in that zone of the non-volatile memory which corresponds to the address translation table;

copying an address translation table stored in at least one zone other than the zone allocated to the system area, to an address translation table area secured on a volatile memory;

copying an address translation table stored in the zone allocated to the system area, to the address translation table area secured on the volatile memory;

when a logical address for accessing said non-volatile memory is given, determining whether said address translation table corresponding to the contents of the specific field of the logical address exists on said volatile memory;

when it is determined said corresponding address translation table does not exist on said volatile memory, copying the address translation table from said non-volatile memory to said address translation table area on said volatile memory, replacing with the address translation table any one of the address translation tables other than the address translation table corresponding to the system area, said address translation table being included in a plurality of address translation tables on said address translation table area, and thereafter, referring to the corresponding entry of the copied address translation table on said volatile memory based on a logical block address contained in the given logical address, thereby translating the given logical address into a corresponding physical address; and

when it is determined that the corresponding address translation table exists on said volatile memory, referring to the corresponding entry of said address translation table that exists on the volatile memory based on a logical block address contained in the given logical address, thereby translating the given logical address into a corresponding physical address.