JP2009503745A - Nonvolatile memory with block management - Google Patents

Abstract

  In a non-volatile memory system that includes a block erasable memory array, records for a particular class of blocks are individually maintained. One or more lists can be maintained for a block, and individual lists are ordered according to descriptor values. Such an ordered list allows for rapid identification of blocks by descriptor value.

Description

  The present application relates to the operation of a reprogrammable non-volatile memory system such as a semiconductor flash memory, and more specifically to the management of individually erasable blocks of a memory array.

  There are two main approaches to addressing data communicated through external interfaces of host systems, memory systems, and other electronic systems. In one approach, the address of a data file generated or received by the system is mapped to a separate continuous logical address space range set as a logical block of data (hereinafter referred to as the “LBA interface”). The size of the address space usually covers enough of the entire address that can be handled by the system. In one example, the magnetic disk storage drive communicates with a host system, such as a computer, through such a logical address space. This address space is large enough to address the entire data storage capacity of the disk drive.

  Flash memory systems are often provided in the form of memory cards or flash drives that are detachably connected to various hosts such as personal computers and cameras, but can also be embedded in such host systems. is there. When writing data to the memory, the host normally assigns a unique logical address to a sector, cluster, or other data unit within the contiguous virtual address space of the memory system. The host, like a disk operating system (DOS), writes data to and reads data from addresses in the logical address space of the memory system. The controller in the memory system translates the logical address received from the host into a physical address where the data in the memory array is actually stored, and grasps the history of the address translation. The data storage capacity of the memory system corresponds at least to the amount of data that can be addressed over the entire logical address space defined for the memory system.

  The size of the erase unit in the current commercial flash memory system has been expanded to a memory cell block that sufficiently stores data of a plurality of sectors. In fact, many data pages are stored in one block, and one page can store data of a plurality of sectors. Further, in many cases, two or more blocks are collectively treated as metablocks, and pages of such blocks are logically linked together as metapages. The parallelism of the operation is enhanced by collectively reading and writing data pages or metapages including data of a large number of sectors. Such large capacity operation units have the problem of operating them efficiently.

  For simplicity of explanation, unless otherwise noted, the term “block” as used herein refers to a block erase unit or multiple block “metablock” depending on whether the metablock is used in a particular system. Is intended to point to Similarly, a “page” referred to herein may refer to a unit of programming within a “metapage” within a single block or metablock, depending on the system configuration.

When the LBA interface of the currently popular memory system is used, a unique address in the logical address space of the interface is assigned to the file generated by the host to which the memory is connected. The memory system then typically maps data between the logical address space and the pages of the physical block of memory. The memory system keeps track of the mapping from logical address space to physical memory, but the host does not know this. The host keeps track of the address of the data file in the logical address space, but the memory system operates ignorant or nearly ignorant about this mapping.
US patent application Ser. No. 11 / 382,224 US patent application Ser. No. 11 / 382,228 US patent application Ser. No. 11 / 382,232 US patent application Ser. No. 11 / 382,235

  In the second of the two system interface approaches used, a data file generated or received by the electronic system is uniquely identified and the data is logically addressed by an offset within the file. This form of addressing is used between other host systems such as computers and removable memory cards known as “smart cards”. Smart cards are typically used by consumers for identification, banking, point-of-sale purchases, ATM access, etc. and contain a small amount of memory compared to flash memory cards and flash drives.

  In a previously cross-referenced patent application, a large flash memory system identifies a data file by a file name assigned by the host, and the data in this file is accessed by an offset address within the file (hereinafter “direct data file” Interface)). The memory system then knows the host file to which each sector or other data unit belongs. The file unit discussed here is, for example, a set of data ordered by successive logical offset addresses, and is created and uniquely identified by an application program that operates in a host computing system that is a connection destination of the memory system.

  Four previously incorporated US patent applications (US patent applications 11 / 382,224 (patent document 1) and 11 / 382,228 filed on May 8, 2006). 11 / 382,232 (Patent Document 3) and 11 / 382,235 (Patent Document 4)) describe a technique for maintaining a list of blocks accessed during operation of a memory system. . Each item on the list includes memory block parameters and respective addresses. An item in the list can be selected according to either the physical address of the corresponding block or the value of the block parameter recorded in this item. This specification is based on storing one or more lists of data blocks in a specified block of flash memory, and on a particular item in the list, based on the information content of the field in this item. Related to access.

  That approach uses some of the logical pages in the specified block to store unordered records that contain information for all blocks on more than one list. The other pages are used for lists of items that contain only block content addressable parameters and pointers to complete records of the block. In these lists, items are stored in the order of parameter values, and items having a specific parameter value can be quickly accessed. These lists serve as a kind of directory for unordered block records.

  In a block erasable nonvolatile memory, efficient memory management becomes possible if the latest information is maintained for each block and the data contained therein. In the case of a block in which valid data of one or more files, used data, and erased space are mixed, this is very complicated. However, if such data is grasped in units of blocks, certain types of memory system operations can be performed efficiently, especially the reproduction of unused space in the memory array. Reproduction of unused space (a space for storing used data or an unused erased space) is performed in units of blocks (here, a block is an erase unit). In order to reduce the copy of valid data, it is desirable to perform block playback operations on blocks in an efficient order. To determine the order of block playback, it is beneficial to rank the blocks in the order of one or more descriptor values, where the descriptor values describe at least one aspect of the data stored in the block. . For example, the blocks can be ordered according to the amount of valid data contained therein, and thus the block with the least amount of valid data contained can be quickly identified for first playback.

  In the first example, records are maintained for various blocks of the memory array, but not necessarily all blocks. Blocks that contain valid data depend on whether they contain erased space (incomplete blocks), and if they do not, they contain whether they contain used data (used blocks), being classified. Separately, a block that contains only used data (invalid block) and a block that contains only erased space (erased block) are classified. Records are maintained for each block that falls into any one of these categories. Records are maintained in dedicated record blocks. In addition, the classified blocks are listed in a list, which is ordered by descriptor value. The descriptor value may be the amount of valid data in the block, the address of the block, or some other descriptor value. The list item contains the pointer of the corresponding record in the first example.

  In the second example, records for blocks corresponding to various classifications are also maintained. A classification “complete common block” is added for blocks that contain data for more than one file and that do not contain used data or erased space. Records are maintained on a dedicated record page in a dedicated record block. A record can contain various information about the corresponding block including the block address of the block, the amount of valid data contained in the block, the position of the write pointer, and the like.

  A directory is provided to allow individual records to be found quickly. Items in the directory identify the record page and the position of the corresponding record on the record page. Directories are maintained on a dedicated directory page within the directory block, and directory entries are ordered by block address. Directory pages contain non-overlapping block address ranges. One directory page can accommodate pointers of a plurality of record pages. However, the record indicated by the item of one directory page is only the record accommodated in one record page. Therefore, when a record is updated in a record page, only one directory page needs to be updated.

  A directory block can also contain one or more lists. Items in the list contain block addresses and descriptor values, and items in the list are ordered by descriptor values. The amount of valid data in the block is a typical descriptor value. The list provides a convenient means for selecting a block based on the data in the block for playback or other purposes. For example, in the list of used blocks that use the effective data amount as the descriptor value, the used block with the smallest effective data amount becomes the first item. This block can be quickly identified from the list for playback, thus the list provides a queue for playback operations. In another example, a block with a certain descriptor value can be looked for. This can be quickly identified by performing a binary search on the appropriate list page.

  In the third example, a record is always maintained for each block of the nonvolatile memory array. The directory page in this case contains items in the fixed block address range, and the items are sequentially ordered by block address. This provides an item of a specific block at a predetermined offset in the directory page, so there is no need to accommodate the block address of the block that is the reference destination of the item in the item.

  Although techniques are described here for managing and accessing lists used in flash memory that operates with the flash data file interface, these techniques can also be used for different types of lists in various applications.

Detailed First Example The direct data file storage method described in the aforementioned patent application creates a list of blocks from which items with predetermined values for the use of individual blocks are selected. Here, a technique for searching for the addressable contents of these block lists will be described. In this specification, reference is made to the accompanying FIGS.

  FIG. 1 is a table showing the classification of memory cell blocks based on this content. Virtually all blocks of the memory system are classified as shown in the figure. In this example, three separate lists are maintained: a list of incomplete blocks, a list of used blocks, and a list of erased blocks.

The types of blocks recognized in this example are as follows.
A “program block” is partially programmed and contains valid data for only one file. Some erased capacity remains in this block. This may contain some used data.
A “common block” is partially programmed and contains valid data for two or more files. Some erased capacity remains. Some used data may be accommodated.
A “full common block” is completely programmed and contains valid data for two or more files. Some used data may be accommodated.
A “file block” is completely programmed and contains valid data for one file. Some used data may be accommodated.
An “invalid block” does not contain valid data. An invalid block contains at least some used data and may contain erased capacity, but it does not contain valid data.
The “erased block” can receive data because the entire capacity of the block is not programmed. There is no data in the erased block. When memory is full or nearly full of data, it typically maintains a pool of a specific minimum number of erased blocks by continuously reclaiming unused space in the blocks in use To do.

For the purpose of this example, blocks having the types described above are classified into the following three categories.
An “incomplete block” contains some unprogrammed capacity, contains valid data for one or more files, and may contain some used data. Program blocks and common blocks are examples of incomplete blocks.
A “used block” is a file block or a full common block that contains a certain amount of used block. Used blocks do not contain erased capacity, but contain both valid data and used data.
The definition of “erased block” is the same as the block type with the same name, that is, a block without data.

  Note that not all blocks in the memory array fall into these categories, some blocks may fall out of these categories, and such blocks will not appear in this example list. Should.

  When selecting a block for reproducing the storage capacity, the main factor is the effective data amount (effective data capacity) in the block. Since it is necessary to copy this valid data to another block in the reproduction operation for the block, the block having the smallest valid data amount is selected first. This is because data copying takes time and may hinder the efficient operation of the memory system when programming and reading data. The advantage of blocks that can be used to store data with most of the capacity erased is somewhat contradictory. Such blocks are undesirable for playback operations because the increase in storage space obtained by playing back blocks with useful erased storage capacity is not very large. This particular example incomplete and used block list is used to classify blocks based on the amount of valid data (number of pages) contained in the block and the amount of erased (number of pages). The purpose of these lists described here is to select one block at a time for playback operations.

Block List Type and Access Incomplete Block List (P List) contains entries for every incomplete block in the system, ie for every block that contains both some valid data and some erased capacity. . Some used data may be accommodated.

  The used block list (O list) contains items for all blocks in the system that contain used data that has no items in the incomplete block list.

  The erased block list (E list) contains entries for all erased blocks in the system.

In one example of flash memory operation, the next block list is maintained.
P (V) list: Incomplete block list in which items are ordered according to the effective data capacity stored in the block P (A) list: Incomplete block list in which items are ordered according to the block address of the block O (V) list: Used block list in which items are ordered according to the effective data capacity stored in the block O (A) list: Used block list in which items are ordered according to the block address of the block E list: Erased block list

  The P (V) list, O (V) list, P (A) list, and O (A) list serve as a “directory” for a common set of block records. In order to select a reproduction block, the item having the lowest effective data capacity value is read from the P (V) list and the O (V) list. To select an active block, the item with the highest valid data capacity value less than or equal to the target value is read from the P (V) list. To select an erased block, the first item on the E list is read and deleted from the list.

  To update an item in the P list or O list, the item having the target block address is read from the P (A) list or O (A) list.

Block List Storage One or more blocks or metablocks are assigned to store information related to the blocks on the block list identified in the previous section. These are known as record blocks, and writing or updating is performed in units of one page. Content addressing is used for information in the record block.

  Each record block contains a certain number of logical pages, and each of the logical pages can be updated by rewriting it to the next available physical page. A plurality of logical pages are allocated to store records containing information about the blocks in the list. These are known as record pages.

  A record exists for every block in the block list. The record page and the records within it can be in any order. There is no need to separate records for blocks in different block lists. There may be a obsolete record in the record page, which can be replaced with a new record for the block added to the block list. The record contains the physical address of the block and a value that determines the effective data amount (effective data capacity) in the block, together with other information.

  One or more logical pages are allocated to store items identifying the blocks in one block list of the individual block lists. These are known as list pages. Separate list pages are used for different block lists. Each item in the list page contains a descriptor value, together with a pointer to a block record in the record page. The descriptor value is either the physical address of the corresponding block or the value of the effective data capacity in the block ( Or some other value related to the data in the block). When a block corresponding to a record appears in two block lists, two list items on different list pages of different block lists indicate the same record.

  Items in the block list serve as “directory items” for the common set of records in the block.

In the list page of the incomplete block list or the used block list, items are stored in the order of their descriptors. Items are written in a dense format, and the unwritten item position in the list page is usually after the last item written. List pages store non-overlapping descriptor ranges. When the list page is full, the item can be split into two list pages by assigning a new logical page as the list page. Similarly, when the number of items in two list pages adjacent to each other in the descriptor range is lower than the threshold value, the two list pages can be combined into one. The record block index contains the descriptor of the first item of each list page.

  In the incomplete block list or the used block list, an item having a block address or effective data capacity target value is flushed by identifying the list page having the corresponding descriptor range from the record block index. Can be found by reading from and then performing a linear or binary search for the target item in the page. Then, the record of the target block can be read from the record page identified from this item.

  Items of blocks in the erased block list can be stored on the list page, where they keep the order in which they were written. The erased block is always selected as the oldest item in the list.

All items and index information of blocks referred to in the structure block list of the record block are accommodated in one or more record blocks of the flash memory. A record block is a metablock and is updated in units of pages.
A record block has the following characteristics:
1. All types of block lists can be stored together in one record block.
2. Multiple record blocks can be used as needed.
3. A record block has a certain number of logical pages, which in this example is defined as 25% of the number of physical pages in the block.
4). The record block index section of the last written page provides a mapping from each logical page to the physical page.
5. The logical page can be updated by rewriting it to the next available physical page.
6). A logical page can be assigned to any type of page used for a block list or for a record of a block.
7). Record blocks are compressed when full and rewritten into erased blocks.

  FIG. 2 shows an example of the structure of the record block.

Record block index The record block index exists as one section of each page in the record block. This is only valid for the last page written. The record block index contains an entry for each possible logical page and is ordered according to the logical page number. Each item has the following three fields.
1. Numeric code identifying page type a. P (V) list page b. P (A) list page c. O (V) list page d. O (A) list page e. E list page f. Record page g. 1. Unassigned logical page The value of the first item in the page (this allows the range of values to be set and cached for each type of P (V), P (A), O (V), O (A) list page)
3. Pointer to the physical page to which the logical page is mapped

The record page record contains all the necessary information related to the block in one item of the list and is stored in the record page. The record page is subdivided into three sections:
1. Item status Record 3. Common block record

The item status section comprises a bitmap that indicates whether the record is in use or can be assigned to a new block. The record section has a fixed size item for every block in the list, and the field defines the attributes of the block as follows.
1. Block address 2. Effective data capacity in block 3. position of page write pointer in block File ID of the first data group in the block
5. 5. Total number of files with data in the block Offset to common block record of the block (a value of 0 means no common block record exists)

The size of the item in the common block record section is indefinite, and the field defines other file IDs in the common block as follows.
1. File ID of subsequent data group in common block
2. Record end indicator

  When a block is deleted from the block list, the record page contains a used item. Such records can be reassigned to new blocks that are added to the list.

  The logical page number in the record block assigned to the block and the record number in that page are not normally changed because they are used by the list page to refer to the record. However, it is permissible to move a block of records to another record number, another list page, or another record block within the same list page. If a block record is moved, the pointer must be updated accordingly in any list item.

  If the record page is modified and rewritten, the common block record can be compressed to eliminate used space, and the record can be updated to reflect the change in offset to the common block record.

  The boundary between records and common block records is dynamic.

  FIG. 3 shows an exemplary structure of a block record page.

List page The list page contains a set of items of blocks in the order defined by the descriptor values. Descriptors in items in the P (V) list and O (V) list are valid data capacities, and descriptors in items in the P (A) list and O (A) list are block addresses.

  A valid item occupies a series of item positions in a list page, but does not need to fill the entire page. There are no obsolete items in this, and the descriptor values do not have to be contiguous.

  Items in the list page are arranged in the order of the values in the descriptor field. The range of descriptor values does not overlap with the range of descriptor values in other list pages.

  When it is necessary to insert an entry for a block added to the block list, a list page is identified that includes the descriptor value of the new block in the descriptor range. The new item is inserted at the appropriate location within the descriptor range and the list page is rewritten. If an item has to be deleted, the list page is compressed and rewritten, omitting the item.

  If an addition must be made to a full list page, a free logical page is allocated as a new list page, and the full list page descriptor range is divided into two approximately equal non-overlapping ranges, which are 2 Written to one available list page.

  If the total number of valid items falls below a threshold (in this example, 70% of the number of item positions in the list page) on two list pages with adjacent descriptor ranges, the two list page ranges are merged and Written on one of the list pages. The other unused page then becomes a free logical page.

For P (V) lists and O (V) lists, the fields in the items in the list page are as follows:
1. 1. Effective data capacity in block Pointer to the record of the block in the record page (the record page may not be in the same record block as the list page)

For P (A) and O (A) lists, the fields in the items in the list page are as follows:
1. Block address Pointer to the record of the block in the record page (the record page may not be in the same record block as the list page)

For the E list, the fields in the items in the list page are as follows:
1. Block address

Access sequence of records To access the records of the target block in the P list or O list, a sequence consisting of the following steps is used.
1. A P (V) list, O (V) list, P (A) list, or O (A) list is set as the target list.
2. The record block index is read from the page written last in the record block. This information may already exist in the cache.
3. The logical page number assigned to the list page of the target descriptor value in the target list defined in step 1 is determined.
4). The logical page number determined in step 3 is read from the record block.
5. In order to read the item of the target block, the list page read in step 4 is searched.
6). A record page is read from the record block defined by the item read in step 5.
7). The record of the target block is read from the record page read in step 6.

Detailed Second Example In the second example, like the first example described above, specific blocks are classified according to the data contained therein, and records for these blocks are maintained. The list is ordered and maintained according to descriptor values related to the data stored in the block. The amount of valid data in a block is an example of such a descriptor value. However, in this second example, some of the structures and methods used for block management are different. The structures and methods of the first and second examples are to be considered as alternatives, and various combinations of the structures and / or techniques of both examples are also considered part of this disclosure. The second example will be described focusing on the difference from the first example. Thus, elements common to both examples may not be detailed again with respect to the second example.

  The block classification of the second example is the same as the block classification of the first example, and “complete common block classification” is added. FIG. 4 shows a block classification table that is almost the same as FIG. 1 except for the additional classification “complete common block”. A record entry is maintained for each block having a block classification of “incomplete block”, “used block”, “erased block”, or “complete common block”. The classification “complete common block” is used for a common block that does not contain erased capacity and does not contain used data. A complete common block (CCB) record is maintained by a block record of all complete common blocks. Complete common blocks that do not have space available for playback (no erased or used space) are typically not subjected to playback operations. However, when a certain amount of data is used up in the complete common block, the block may be reclassified as a used block and may be subjected to a reproduction operation. When such reclassification is performed, a block record that contains relevant information of data stored in the block is required. This information is available from the block's existing CCB record entry. Therefore, if a complete common block record is maintained, a transition from a complete common block to a used block can be achieved without the heavy burden of searching for information to generate a block record.

  The classification schemes of FIGS. 1 and 4 are exemplary, and other schemes are anticipated. In one example (discussed in detail below), records are always maintained for all blocks in the memory array. In this case, additional block classifications for file blocks that do not have used data can be added to the table of FIG. In another example, some of the classifications of FIG. 4 are not required. For example, records of erased blocks and invalid blocks need not be maintained. In yet another example, the blocks can be divided into different block types than in FIG. It will be appreciated that the block type of FIG. 4 is convenient for a particular memory management scheme, but that different block types can be used with other memory management schemes.

  Records are maintained for all blocks corresponding to any one of the block classifications described in the table of FIG. Records of blocks with different block classifications can be stored together on the same page. In this example, a dedicated block record block that stores only block records is maintained. Maintain a block directory to facilitate access to individual record items within a record block. The block directory and block record are stored in a separate set of blocks in the flash memory (unlike the first example, where both the block directory and block record pages are contained in a single block). FIG. 5 shows a block directory entry 501 in the directory block 503 that includes a pointer 505 that points to the location of the corresponding block record 507 in the block record block 509. Block directory entry 501 also includes a block address 506.

  The block directory contains one block directory item for each block that has an item in the block record. Block directory entries are stored in non-overlapping block address value ranges, each range being assigned to a separate block directory page. Within the range, items are ordered according to block address values. The block directory entry for the target block address can be found by reading one block directory page and performing a binary search within that page. In this way, the block directory provides a convenient means of finding a particular block record item according to the block address.

  Depending on the application, it is desirable to search for blocks based on criteria other than block addresses. In some cases, descriptor values associated with the data stored in the block can be used for such searches. For example, for playback purposes, it may be desirable to identify incomplete blocks with the least valid data. As a method for finding such a block, the record items of all the blocks are searched in order to determine which block has the smallest effective data amount accommodated. However, such a search may add significant burden. In one alternative, a list of blocks is maintained in which the blocks are ordered according to the amount of valid data contained (effective data capacity). In this case, since the blocks are listed in the order of the contained effective data amount, in order to identify the block having the smallest effective data amount, it is only necessary to read the first (or last) item in the list. Similarly, if a block with a certain amount of valid data is required, such a block can be quickly identified by a binary search. The amount of valid data stored in the block is given by the descriptor value in the list item. Such descriptor values describe the data stored in the block. This contrasts with the block address (used as a descriptor value in the first example) that describes the physical location of the block.

  A mechanism incorporating a two-stage search process is provided for accessing block records according to the descriptor value of the amount of valid data in the block defined in the field of the record. For block classifications that can use this content addressing mechanism, items containing valid data capacity values are stored in separate list pages in the block directory. These block list items are stored in valid data capacity value ranges that do not overlap, and each range is assigned to a separate block list page. Within the range, items are ordered according to valid data capacity values. Each block list item contains a block address, which clearly identifies the block directory item. Block list entry 511 contains block address 513, which is the same as block address 506, and thus identifies block directory entry 501. Block list item 511 also contains the effective data capacity 515 of the block having block address 513. The block directory item of the target effective data capacity value is obtained by reading one list page, performing a binary search in the page to find an item having the target effective data capacity value, and adding one more directory page. By reading, it can then be found by performing a binary search in the directory page to find the item with the target block address.

  A binary search may simply mean looking at an item that is in the middle of the page's descriptor value range. Based on a comparison of the descriptor value of this item with the descriptor value that is being searched, the search is limited to half the page. The items in the middle of this half page are examined in the same manner, and the search is limited to a quarter of the page. After successive steps, one or more items with the descriptor value you are looking for are found. In another example, a binary search is not necessary because the descriptor value you are looking for is the lowest (or highest) in the list. Therefore, the first (or last) item in the list is selected.

  Block records can be addressed directly by entries in the block directory. The block record page is updated by a read / modify / write operation that moves the page to an unprogrammed location in the same or another block record block. Every block record in a page must correspond to an item in the same block directory page. However, one directory page can accommodate a plurality of block record page items. Therefore, when updating the block record page, only one block directory page needs to be modified.

Block Directory A block directory is a group of ordered items that identify a block by a block address and indicate the location of the corresponding block record. There is one entry in the block directory for each block for which block records are maintained. In this example, there is one entry for each of the incomplete block, the used block, the complete common block, and the erased block. Block directories are contained in one or more directory blocks.

  FIG. 6 shows a directory block 621 that contains a list page of used blocks and incomplete blocks. FIG. 6 also shows a directory page in the directory block. Each directory block contains a fixed number of logical pages, each of which can be updated by rewriting it to the next available physical page. A logical page number is assigned to a page containing a valid item. In this example, the number of logical pages in the directory block is specified as 25% of the number of physical pages in the block. Other examples can specify other restrictions. After the last page of the directory block has been written, the block is compressed by writing all of the valid pages to the erased block and by erasing the original directory block.

Block Directory Page The block directory page contains a set of block directory items in order of their block address values. FIG. 7A shows an example of the block directory page 731. The valid block directory item 733 occupies a series of item positions in the block directory page 731, but it is not necessary to fill the entire page, so an erased space may remain. Each block directory page contains a record index (described below). Here, the block directory page 731 contains a record index 735. There are no used items in the block directory item 733, and the block address values may not be continuous. The range of block address values in one block directory page does not overlap with the range of block address values in another block directory page.

  If a block entry needs to be inserted, a block directory page that includes the block address value of the new block in the block address range is identified from the directory index information. A new entry is inserted at the appropriate location in the block address range and the block directory page is rewritten. If an item must be deleted, the block directory page is compressed and rewritten, omitting the item.

  If an addition must be made to a full block directory page, a free logical page is allocated as the new block directory page, and the block address range of the full block directory page is divided into two approximately equal non-overlapping ranges. They are written to two available block directory pages.

  When the total number of valid items in two block directory pages adjacent to each other in the block address range falls below a threshold value (70% of the number of item positions in one block directory page in this example), the ranges of the two block directory pages are merged. And written to one of the two block directory pages. Next, the other unused page becomes a free logical page.

  The block directory entry 737 in this example contains two fields: (1) a block address and (2) a pointer to the corresponding block record. This pointer identifies the logical identifier of the block record page and the byte offset of a particular block record within the page. The block record page logical identifier identifies one of up to 16 block record pages referenced by items in the same block directory page. This is converted into a physical block address and a page number by the record index field in the block directory page containing the item. The byte offset identifies the position of the block record within the identified block record page.

  There is a single valid record index field in each valid block directory page and block list page. This is used to convert the logical identifier of the block record page into the page number and physical block address where the block record page is located. The record index 735 contains one item (eg, item 739) for each logical identifier used in any item on the block directory page 731. A block directory entry references up to 16 block record pages within a block directory page. Therefore, a 4-bit logical identifier is used. Thus, each block directory entry can use a 4-bit identifier instead of the long physical page position of the corresponding block record page. The record index field serves to translate these logical identifiers for all items in the block directory page.

The valid directory index field 741 exists only in the last written block directory or block list page. Previously written information in the directory index field in the page has been used. The purpose is to support the ordering of block directory items and block list items and the mapping from logical pages to physical pages. In the structure it provides, the latest data for individual pages in the block directory block is stored. The directory index contains items such as items 743 ordered according to logical page number for each possible logical page. Each item has four fields.
(1) Logical page allocation status flag (2) Page type, eg, block directory, PB list, or OB list (3) Block address of first item in block directory page, or in list page (PB or OB) Valid data capacity value of the first item of (this allows each logical page to establish a block address or valid data value range and cache it)
(4) Pointer to physical page in block directory corresponding to logical page mapping

Block List Page The block list page contains one set of block list items per block classification, in the order of descriptor values that describe the data contained in the block (for example, the amount of valid data contained in the block). FIG. 7B shows an example of the block list page 751. In this example, the block list page is a PB list page or an OB list page. FIG. 7B shows an OB list page 751. The valid block list item 753 occupies a series of item positions in the block list page 751, but it is not necessary to fill the entire page. There are usually no used items in the block list page. Although block list items 753 are ordered by descriptor values, the descriptor values need not be contiguous and can be repeated. In this example, the valid data capacity values need not be continuous and can be repeated. The descriptor value range of one block list page does not overlap with the descriptor value range of another block list page of the same block classification.

  The descriptor value used in this example is the effective data capacity, but other descriptor values can be used. For example, the erased capacity in a block can be used as a descriptor value. To list the blocks for playback in the desired order, a descriptor value can be derived from a combination of valid data volume and erased capacity. The lists may overlap in some cases. In this case, the same block may appear in two different lists. For example, blocks may be listed according to the amount of valid data contained therein, while at the same time (according to another list) the amount of erased space contained therein.

  When it is necessary to insert an item of a block, a block list page including the effective data capacity value of the new block in the effective data capacity range is identified from the directory index information. The block list page is rewritten and new items are inserted at the appropriate location on the page according to this valid data capacity value. If the item must be deleted, the block list page is rewritten at the new physical location, omitting the item.

  If an addition must be made to a full block list page, a free logical page is allocated as the new block list page, and the valid data range of the full block list page is divided into two approximately equal non-overlapping ranges. , They are written to two available block list pages.

  When the total number of valid items in two adjacent block list pages with a range falls below a predetermined threshold (in this example, 70% of the number of item positions in one block list page), the ranges of the two block list pages are merged. And written to one of the two block list pages. The other unused page becomes a free logical page.

  Block list entry 755 contains two fields: (1) block address and (2) descriptor value, which in this example is a value indicating the amount of valid data in the block. Unlike the first example, there is no list ordered by block address (but directories are ordered by block address). In this example, the list includes a block address, a directory entry is found from this block address, and further indicates the position of the record to which this directory entry corresponds. Therefore, in this example, the list item 753 does not directly indicate a record. The block list can contain a directory index, but only the last written page contains a valid directory index. The OB list page of FIG. 7B contains a used directory index 757.

Block record A block record is a collection of records, and each record contains information of a block identified by a block address. There is one record for each block directory entry. Block records are addressed by block directory entries, and the block directory page must be modified when the block record page is modified.

  Block records are contained in one or more dedicated record blocks, such as record block 861 shown in FIG. Unlike the first example, the block list and the block record are not stored together in the same block. A single block record block contains a non-programmed page and a block record can be written here. Any block record information is programmed to the next unprogrammed page position in this block identified by the block record write pointer. When the last page in the block is programmed, the block record write pointer is moved to the first page of the erased block. A block record block can contain used pages when a block record page is rewritten. In some embodiments, a valid block record page does not contain a used record when the block record page is rewritten and the records in the page are always used. In another embodiment, used records may remain on valid block record pages. However, the used record is not accessed because the directory item of the used record is deleted or replaced with an item indicating a valid record. Spent records in the record page are not copied when the record page is rewritten.

  The block record page contains a set of block records referenced by block directory items within a block directory page in the same order as the items in the block directory page. FIG. 9 shows an example of the block record page 965. A block directory page can reference multiple block record pages. To modify a block record page, only one block directory page needs to be modified. Unlike the first example, the block record page in this example does not include a block record index because the block record page is identified directly by the block directory entry.

  The block record page can be modified by reading it and updating or adding one or more block records. Any obsolete block records are deleted by page compression, and the page is programmed to the location identified by the block record write pointer.

  The block record page header stores a reference to the block directory page associated with the block record page and the length of the block record information in this block record page. The block record page header also stores a record of the number of used pages present in each of the block record blocks when the block record page is written. This information is valid only in the last written block record page header.

The size of each block record item is indefinite. Thus, the complete common block record may be larger than the erased block record. Unlike the first example, a separate common block record area is not required. The record block in this example has the following fields that define the attributes of the block.
(1) Block address (2) Block type, PB, OB, CCB, or EB
(3) Effective data capacity in block (4) Position of page write pointer in block (5) Total number of files in which data exists in block (6) File ID of each file in which data exists in block

  In other examples, the record may contain different fields containing different descriptor values.

Block record playback process in the second example The block record is contained in one or more record blocks and is directly addressed by a block directory entry. Erased pages that can be used in programming a new or updated block record are contained in a single record block. Even if all pages are programmed in all other record blocks, completely used or partially used pages may be contained in the block. Playing back the capacity occupied by a used block record is done by designating one record block as the next block to be played, and gradually moving the page from this play block to the page currently specified by the block record write pointer. This is accomplished by copying and subsequently erasing the playback block.

  When the previous playback process for the record block is completed and the previous playback block is erased, the playback block is selected. The record block with the highest number of used pages is selected as the playback block. The number of used pages in each record block is recorded in the block record page header of the last written block record page. The record block containing the block record write pointer may not be selected for playback. The selected record block remains a playback block until the playback process is complete and the block is erased. The erased block is then added to the pool of erased blocks and can be used again to store any kind of data, including host data. Thus, the block remains a dedicated record block for some time, but is not permanently designated as a record block.

  In the process of replaying block record blocks containing used pages, a small number of pages containing valid block records are copied step by step from the block to the page specified by the block record write pointer at scheduled intervals. . For good performance, the number of pages copied in one stage is the number of pages accommodated in the metapage. However, in some cases, fewer pages are written. Programming the page at the block record write pointer can be accomplished as a single programming operation on the metapage. The stepwise copy operation of pages in the playback block can be scheduled at intervals defined by the progress of the block record write pointer passing through the number of page positions contained in the four metapages. To program a metapage, the write pointer must point to the first page of the physical metapage when a staged copy operation is scheduled.

  In contrast to the block record block playback process described above, the directory block playback process only needs to compress the block directory block when no erased space remains in the directory block. Compressing a block directory block with valid pages that are always at most 25% (logical capacity in this example is 25% of physical capacity) will result in a block with at least 75% erased space. When compression is performed, the block corresponding to the data copy source becomes an invalid block and is erased to become an erased block. This block is then added to the pool of erased blocks and can be used to store any kind of data, including host data. Thus, the block remains a dedicated directory block for some time, but is not permanently designated as a directory block.

One or more block records need to be updated when data is written to a block or when a file is deleted in the update memory array of the second example structure . It is also necessary to update the corresponding block directory and list items. The next process shown in FIG. 10 illustrates the updating of the various structures of the second example, where additional valid data is present in an incomplete block (which already contains some used data). Stored, the block becomes a obsolete block.
(1) Receive an address of a block storing additional data.
(2) In order to determine the physical page position of the directory page 173 containing the directory item 175 of this block, the directory index 171 is examined on the last written page of the block directory block 170.
(3) Perform a binary search in the directory page 173 to find the block entry 175.
(4) Based on the information of the record index 177 from the logical identifier of the item 175, the physical page 179 that accommodates the record 183 of this block in the block record block 181 is determined. The offset in the directory entry 175 is used to find the correct record 183 corresponding to the received address.
(5) The block classification is determined from the record 183. It is determined whether or not the classification is changed by storing additional data. Here, the block is an incomplete block, and the space left in this block is filled with additional data, so this block becomes a obsolete block.
(6) The contents of the record page 183 are copied to the position indicated by the write pointer 185, and the record 183 of the target block is updated to reflect different types of blocks, valid data, the position of the page write pointer, etc. The
(7) Copy directory page 173 to the next available physical page in block directory block 170. Write the updated item and record index to the new directory page to reflect the new physical location of the record page. It also updates the directory index with new physical pages.
(8) Examine the directory index again to determine the physical page position of the incomplete block list page 187 containing the block item 189 (in some cases, check multiple lists).
(9) Perform a binary search in page 187 to find a list item 189 whose descriptor value is equal to that of the target block. If multiple list items have descriptor values, search for all items that match by block address.
(10) The incomplete block list page 187 is copied to a new position, and the target block item 189 is deleted. The new incomplete block page includes the directory index updated with the new physical location of the incomplete block page.
(11) In order to determine the physical page position of the used block list page covering the valid data per block range including the valid data amount of the target block, the directory index is checked again (not shown).
(12) Copy the used block list page and add a new entry for the target block at the appropriate offset based on the current amount of valid data in the block. The new used block list page includes an updated directory index (not shown) that indicates the new location of the used block list.

  The steps described above are not necessarily performed in the order shown. Several steps can be performed in parallel. For example, the updated used block list page and the updated incomplete block list page may be written in parallel as part of the metablock writing.

Detailed Third Example In the third example, a record is always maintained for each block of the memory array. This involves one or more additional block classifications, for example, additional classifications for file blocks that do not contain used data can be added to the second example classification shown in FIG. Maintaining records for each block increases the total number of records maintained, but a simpler structure can be used. The third example proceeds in the same manner as the second example except that a record is prepared for each block.

  For example, if records are maintained for all blocks, directory entries are also maintained for all blocks. Directory items have a uniform size. Therefore, the directory page can accommodate a fixed number of items that are sequentially ordered by block addresses. Thus, each directory page covers a certain block address range. Since the items in such a page have a predetermined offset according to their block addresses, there is no need to record the block addresses separately in each item. To find a directory entry for a particular block, find the directory page that covers the block address range that contains the block, and within that page, the difference between the block address of the first entry on the directory page and the desired block address. You can proceed to the item that is at the offset determined by. Thus, a binary search of the directory page is not necessary. In contrast, the size of a record is usually indeterminate, and a fixed number of items are not always maintained in a record page. Unlike the previous examples, this example maintains a record for blocks that have no items in the list.

  Maintaining records for each block in memory is convenient for some applications. For example, descriptors can be maintained for the physical characteristics of the block. An example of such a descriptor is an erasure count. The erase count indicates the number of erases of a specific block that is erased and can be used for wear leveling purposes. Blocks can be ordered in one or more lists according to the block erase count. Also, the time stamp when the block was last erased can be included in the record, so that the blocks can be ordered in the list according to the time elapsed since the last erase.

  While various aspects of the present invention have been described in connection with exemplary embodiments thereof, it will be understood that the rights should be protected within the full scope of the appended claims.

2 shows a table of block classification according to a first example. 2 shows a page of record blocks according to a first example. 3 shows a detailed view of individual pages of the record block of FIG. The table of the block classification by the 2nd example is shown. A block directory entry in a block directory block indicating a corresponding block record in the block record block. Details of the page structure of the directory block. FIG. 7 shows the structure of the block directory page of FIG. 6 including a record index and a directory index. The structure of the used block list page of FIG. 6 is shown. Details of the page structure of the record block are shown. The structure of the record page of FIG. 8 is shown in more detail. The directory block and the record block in the process of updating the structure related to the block record are shown.

Claims (34)

A memory system,
A non-volatile memory array including a first plurality of individually erasable blocks each containing data;
A list containing items for each of the first plurality of blocks, wherein the items in the list are ordered according to the amount of valid data stored in each of the first plurality of blocks;
A memory system comprising: The memory system of claim 1, wherein
A plurality of records, each of the plurality of records corresponding to one of the first plurality of individually erasable blocks, each of the plurality of records containing information about the corresponding block; Memory system. The memory system of claim 2, wherein
The memory system wherein the list items are maintained on a plurality of list pages in a first block, and the plurality of records are maintained on a record page in a second block. The memory system of claim 1, wherein
The plurality of blocks are memory systems comprising all blocks of a nonvolatile memory array that accommodates both erased space and valid data. The memory system of claim 1, wherein
The plurality of blocks is a memory system including all of the blocks of the nonvolatile memory array that contains used data and does not contain erased space. A non-volatile memory array,
Multiple individually erasable blocks;
A plurality of records for the plurality of blocks, wherein each of the plurality of records includes a plurality of records containing information on one block of the plurality of blocks;
A directory containing a plurality of directory items, wherein each of the plurality of directory items includes a directory including a position of one record of the plurality of records;
A list containing a plurality of list items, wherein each of the plurality of list items describes data stored in one individual block of the plurality of blocks; A list ordered by descriptor values;
A non-volatile memory array comprising: The non-volatile memory array of claim 6,
The plurality of records are placed in a first block, and the directory and the list are maintained in a second block. The non-volatile memory array of claim 6,
The descriptor value is a non-volatile memory array that represents an effective data amount stored in each of the plurality of blocks. The non-volatile memory array of claim 6,
The plurality of blocks are non-volatile memory arrays including all of the blocks in the non-volatile memory array that individually accommodates both erased space and valid data. The non-volatile memory array of claim 6,
The plurality of blocks are non-volatile memory arrays comprising all the blocks of the non-volatile memory array that individually store used data and do not store erased spaces. The non-volatile memory array of claim 6,
The plurality of blocks are nonvolatile memory arrays including all blocks of the nonvolatile memory array. The non-volatile memory array of claim 6,
The list is a non-volatile memory array maintained on a plurality of pages each storing a separate list item range. A non-volatile memory system comprising storage cells grouped into blocks of memory cells and erased prior to reprogramming data in a page of the block,
A first plurality of blocks for storing data;
A first plurality of pages containing a plurality of records at least individually including descriptor values describing data stored in a corresponding one of the first plurality of blocks;
A second plurality of pages containing pointers to record positions in the first plurality of pages, wherein the valid records in one individual page of the first plurality of pages are the second record A second plurality of pages limited to a record indicated by a pointer stored in one of the plurality of pages;
A non-volatile memory system comprising: The non-volatile memory system according to claim 13.
The non-volatile memory system, wherein the first plurality of pages are placed in a first group of one or more blocks, and the second plurality of pages are placed in a second group of one or more blocks. The non-volatile memory system according to claim 13.
The first plurality of pages are placed in a first block that is not one block of the first plurality of blocks, and the second plurality of pages are included in the first plurality of blocks. A non-volatile memory system placed in a second block that is not one block. The non-volatile memory system according to claim 13.
A list placed on a third plurality of pages, the list containing a plurality of items individually corresponding to each of the first plurality of blocks, wherein the item contains a descriptor value of the corresponding block; Accommodates non-volatile memory system. A method of operating a block erasable non-volatile memory array comprising:
Maintaining a list containing list items for each of a plurality of blocks of the non-volatile memory array, wherein the list items are ordered according to the amount of valid data stored in each of the plurality of blocks. The method of claim 17, wherein
Maintaining a record for each of the plurality of blocks of the non-volatile memory array, wherein an individual record for one of the plurality of blocks includes a physical address of the block, and each list item is How to link to record fields. The method of claim 18, wherein:
A method wherein list items are maintained on a list page in a first block and the record is maintained on a record page in a second block. The method of claim 17, wherein
The plurality of blocks comprising all blocks of the non-volatile memory array containing both erased space and valid data. The method of claim 17, wherein
The plurality of blocks are made up of all the blocks of the non-volatile memory array that contain used data and do not contain erased space. A method of operating a block erasable non-volatile memory array comprising:
Maintaining a plurality of records for a plurality of blocks in the memory array, each of the plurality of records containing information relating to one block of the plurality of blocks;
Maintaining a directory containing a plurality of directory items, each of the plurality of directory items including position information relating to one record of the plurality of records;
Maintaining a list containing a plurality of list items, each of the plurality of list items describing data stored in one individual block of the plurality of blocks, wherein the plurality of lists Items are ordered by their descriptor values,
Including methods. The method of claim 22, wherein
The plurality of records are maintained in a first block, and the directory and the list are maintained in a second block. The method of claim 22, wherein
The descriptor value represents a valid data amount stored in each of the plurality of blocks. The method of claim 22, wherein
The plurality of blocks comprising all of the blocks in the non-volatile memory array that individually contain both erased space and valid data. The method of claim 22, wherein
The plurality of blocks comprising all of the blocks in the non-volatile memory array that contain used data and do not contain erased space. The method of claim 22, wherein
The method wherein the plurality of blocks comprise all of the blocks in the non-volatile memory array. The method of claim 22, wherein
The list is maintained on a plurality of pages each storing a separate list item range. 30. The method of claim 28, wherein
A method further comprising searching for a block having a predetermined descriptor value by searching the list for a list item that matches the predetermined characteristic. 30. The method of claim 29.
The method wherein the predetermined characteristic is a minimum valid data amount of a list item in the list. A method of operating a non-volatile memory system comprising storage cells that are grouped into blocks of memory cells and that are erased prior to reprogramming data in a page of the blocks,
Storing data in a first plurality of blocks;
Maintaining a record in the first plurality of pages that includes at least individually descriptor values describing data stored in a corresponding one of the first plurality of blocks;
Maintaining a pointer to a record position in the first plurality of pages in a second plurality of pages, wherein valid records in one individual page of the first plurality of pages are: A step limited to a record pointed to by a pointer stored in one of the second plurality of pages;
Including methods. 32. The method of claim 31, wherein
The method wherein the first plurality of pages are placed in a first group of one or more blocks and the second plurality of pages are placed in a second group of one or more blocks. 32. The method of claim 31, wherein
The first plurality of pages are placed in a first block that is not one block of the first plurality of blocks, and the second plurality of pages are included in the first plurality of blocks. A method that is placed in a second block that is not one block. 32. The method of claim 31, wherein
The method further comprises maintaining a list of descriptor values corresponding to each of the first plurality of blocks in a third plurality of pages, wherein the list items are ordered by descriptor values.

Images