METHOD AND APPARATUS FOR STORING DATA IN NON-VOLATILE MEMORY

Apparatus and methods implemented therein are disclosed for storing data in flash memories. The apparatus comprises a flash memory having several physical blocks, a logical to virtual mapping table, a virtual to physical mapping table and a memory controller. The memory controller retrieves a virtual block address from the logical to virtual mapping table. The virtual block address corresponds to an entry in the virtual to physical mapping table. The entry in the virtual to physical mapping table contains a reference to a physical block. The memory controller uses the virtual block address to retrieve the reference to the physical block and stores data in the physical block. The memory controller copies the stored data from the physical block to a second physical block. The memory controller then replaces the reference to the physical block contained in the entry of the virtual to physical mapping table with a reference to the second physical block.

TECHNICAL FIELD

This application relates generally to managing data in a memory system. More specifically, this application relates to copying data between physical storage blocks in a solid state storage device and remapping references to the physical storage blocks.

BACKGROUND

Non-volatile memory systems, such as flash memory, are used in digital computing systems as a means to store data and have been widely adopted for use in consumer products. Flash memory may be found in different forms, for example in the form of a portable memory card that can be carried between host devices or as a solid state disk (SSD) embedded in a host device. These memory systems typically work with data units called “pages” that can be written, and groups of pages called “blocks” that can be read and erased, by a storage manager often residing in the memory system. Each of the blocks may be associated with a physical address.

In a SSD there is a logical to physical mapping table or other data structure that typically stores a map of all logical addresses to physical addresses in the SSD. When data is written to a flash memory, the mapping table or other data structure that tracks the location of data in the flash memory must be updated. The time involved in updating data structures for file systems to reflect changes to files and directories, and accessing these data structures, may affect the performance of the storage device.

SUMMARY

According to one aspect, a method for storing data in non-volatile memory by a memory controller is disclosed. In one embodiment, the memory controller receives information from a host. The information includes data that is to be stored and a logical block address. Based on the logical block address, a virtual block address corresponding to the logical block address is retrieved from a logical to virtual mapping table. The retrieved virtual block address corresponds to an entry in a virtual to physical mapping table. The entry includes a reference to a first physical block. The data in the first physical block based on the reference. The stored data is copied from the first physical block to a second physical block. The reference to the first physical block in the entry is replaced with a reference to the second physical block without changing the virtual block address associated with the logical block address.

According to another aspect, a method for copying data stored in a first physical block of a flash device to a second physical block of the flash device is disclosed. In an embodiment, the first physical block has a cell density different from a cell density of the second physical block. After data is copied, a reference to the first storage block contained in an entry of a virtual to physical block address is replaced with a reference to the second storage block. The entry corresponds to a respective logical block address stored in a logical to virtual mapping table.

DETAILED DESCRIPTION

A flash memory system suitable for use in implementing aspects of the invention is shown inFIG. 1. A host system100stores data into, and retrieves data from, a storage device102. The storage device102may be embedded in the host system100or may exist in the form of a card or other removable drive, such as a solid state disk (SSD) that is removably connected to the host system100through a mechanical and electrical connector. The host system100may be any of a number of fixed or portable data generating devices, such as a personal computer, a mobile telephone, a personal digital assistant (PDA), or the like. The host system100communicates with the storage device over an input/output interface104.

The storage device102contains a memory controller106and a memory108. As shown inFIG. 1, memory controller106includes a processor110and a controller memory112. The processor110may comprise a microprocessor, a microcontroller, an application specific integrated circuit (ASIC), a field programmable gate array, a logical digital circuit, or other now known or later developed logical processing capability. The controller memory112may include volatile memory such as random access memory (RAM) and/or non-volatile memory such as read only memory (ROM).

As discussed in more detail below, the storage device102may include functions for memory management. In operation, the processor110may execute memory management instructions (which may be resident in controller memory112) for operation of memory management functions. The memory management functions may control the assignment of the one or more portions of the memory108within storage device102.

The memory108may include non-volatile memory (such as flash memory). One or more memory types may be included in memory108. For example, the intermediate memory118may be configured in a single level cell (SLC) type of flash configuration having a one bit per cell capacity while the main memory120may consist of a multi-level cell (MLC) type flash memory configuration having two or more bit per cell capacity to take advantage of the higher write speed of SLC flash and the higher density of MLC flash. As an example, if a physical block in the intermediate memory is capable of storing 1024 bits and if a physical block in the main memory consists of cells having a 4 bit per cell capacity, a block of data having a size of 1024 bits may be stored in the main memory in a physical block with 256 cells (1024/4).

Generally, writing data to a SLC type flash memory takes less time than writing the same data to an MLC type flash memory. Therefore, it may be desirable to first store data into an SLC type flash memory and then subsequently move the data to a MLC type flash memory. Different combinations of flash memory types are also contemplated for the intermediate storage118and main memory120.

The intermediate memory118and the main memory120include physical blocks of flash memory that each consists of a group of pages, where a block is a group of pages and a page is a smallest unit of writing in the memory. The physical blocks in the memory include operative blocks that are represented as logical blocks to the file system128. The storage device102may be in the form of a portable flash drive, an integrated solid state drive or any of a number of known flash drive formats. In yet other embodiments, the storage device102may include only a single type of flash memory having one or more partitions.

Referring toFIG. 2A, the intermediate and main memories118,120(e.g. SLC and MLC flash respectively) may be arranged in blocks of memory cells. In the example ofFIG. 2, four planes or sub-arrays200,202,204and206memory cells are shown that may be on a single integrated memory cell chip, on two chips (two of the planes on each chip) or on four separate chips. The specific arrangement is not important to the discussion below and other numbers of planes may exist in a system. The planes are individually divided into blocks of memory cells shown inFIG. 2Aby rectangles, such as blocks208,210,212and214, located in respective planes200,202,204and206. There may be dozens or hundreds of blocks in each plane. Blocks may be logically linked together to form a metablock that may be erased as a single unit. For example, blocks208,210,212and214may form a first metablock216. The blocks used to form a metablock need not be restricted to the same relative locations within their respective planes, as is shown in the second metablock218made up of blocks220,222,224and226.

The individual blocks are in turn divided for operational purposes into pages of memory cells, as illustrated inFIG. 2B. The memory cells of each of blocks208,210,212and214, for example, are each divided into eight pages P0-P7. Alternately, there may be 16, 32 or more pages of memory cells within each block. A page is the unit of data programming and reading within a block, containing the minimum amount of data that are programmed or read at one time. A metapage302is illustrated inFIG. 2Bis formed of one physical page for each of the four blocks208,210,212and214. The metapage302includes the page P2in each of the four blocks but the pages of a metapage need not necessarily have the same relative position within each of the blocks. A metapage is the maximum unit of programming. The blocks disclosed inFIGS. 2A-2Bare referred to herein as physical blocks because they relate to groups of physical memory cells as discussed above. As used herein, a logical block is a virtual unit of address space defined to have the same size as a physical block. Each logical block includes a range of logical block addresses (LBAs) that are associated with data received from a host100. The LBAs are then mapped to one or more physical blocks in the storage device102where the data is physically stored.

In an exemplary embodiment discussed herein, an LBA may be mapped to an intermediary virtual block address and the virtual block address in turn may be mapped to a physical block. In this embodiment, data stored in one physical block, an SLC type physical block for example, may be copied to an MLC type physical block. After copying the data, virtual block address may be remapped to point to the MLC type physical block. One advantage of performing the remapping using the intermediate virtual block address is that the logical block address associated with the data is not changed. Because the logical block address associated with the data is not changed, the host system may be agnostic to the remapping of the logical block address and the copying of the data from one physical block to a second physical block.

Referring again toFIG. 1, the host100may include a processor122that runs one or more application programs124. The application programs124, when data is to be stored on or retrieved from the storage device102, communicate through one or more operating system application programming interfaces (APIs)126with the file system128. The file system128may be a software module executed on the processor122and manages the files in the storage device102. The file system128manages clusters of data in logical address space. Common operations executed by a file system128include operations to create, open, write (store) data, read (retrieve) data, seek a specific location in a file, move, copy, and delete files. The file system128may be circuitry, software, or a combination of circuitry and software.

Accordingly, the file system128may be a stand-alone chip or software executable by the processor of the host100. A storage device driver130on the host100translates instructions from the file system128for transmission over a communication channel104between the host100and storage device102. The interface for communicating over the communication channel may be any of a number of known interfaces, such as SD, MMC, USB storage device, SATA and SCSI interfaces. A file system data structure132, such as a file allocation table (FAT), may be stored in the memory108of the storage device102. Although shown as residing in the binary intermediate portion118of the memory108, the file system data structure132may be located in the main memory120or in another memory location on the storage device102.

In addition to the user data and host-generated file system tables that may be stored in flash memory on the storage device, the storage device itself stores and maintains a mapping table114or other data structure that tracks the logical addresses supplied by the host file system and the physical addresses where the storage device is keeping the data. One way to maintain a primary mapping table of all logical to physical address relationships (a logical to physical mapping table) in the storage device is to maintain the entire table in flash memory (such as NAND flash) and to then copy the entire table into mapping table114in the controller106of the storage device102.

In a preferred embodiment described herein the primary mapping table is replaced with a logical to virtual mapping table and a virtual to physical mapping table. In this embodiment, one or more entries in the logical to virtual mapping table may include a reference to an entry in the virtual to physical to mapping table. The entry in virtual to physical mapping table may include a reference to a physical block where the memory controller may store data received from the host system100.

FIG. 3is a block diagram of a preferred embodiment of the mapping table114and memory108ofFIG. 1. The mapping table114comprises a logical to virtual mapping table304and a virtual to physical mapping table306. The number of entries in the logical to virtual mapping table304is an integer multiple of the number of entries in the virtual to physical mapping table306. In this embodiment, an entry in the logical to virtual mapping table304corresponds to a logical block address. Separately, the integer number of entries in the logical to virtual mapping table304may include a reference to a single entry in the virtual to physical mapping table306. An entry in the virtual to physical mapping table306may include a reference to a single physical block or a reference to the start of a group of contiguous physical blocks.

In this embodiment, the memory108comprises intermediate memory118and main memory120. By way of example and without limitation, intermediate memory118comprises physical blocks consisting of SLC. Main memory120comprises physical blocks consisting of MLC. By way of example and without limitation, an MLC in a physical block in main memory120is capable of storing 4 bits of information, in contrast to an SLC in a physical block in intermediate memory118is capable of storing 1 bit of information. Thus, data stored in four physical blocks,308-1for example, in intermediate memory118may be copied and stored in one physical block,310-1, of main memory120. Correspondingly, in this example, four entries in the logical to virtual mapping table304may include a reference to a single entry in the virtual to physical mapping table306.

A memory controller such as memory controller106ofFIG. 1may operate to copy data stored in four contiguous physical blocks308-1of intermediate memory118to a single physical block310-1in main memory120. Before the copying of data, an entry in the virtual to physical mapping table306may reference the first of four contiguous physical blocks308-1in intermediate memory118. In this embodiment, in response to copying data to a single physical block310-1in main memory120, memory controller106may remap the entry in the virtual to physical mapping table306to reference the single physical block in main memory120. The entries in the logical to virtual mapping table304that reference the entry in the virtual to physical mapping table306need not be updated after the copying operation.

FIG. 4is a block diagram of an example device400that may implement methods described herein to cause the storage, copying and reading of data and to perform the remapping described with reference toFIG. 3. Device400may correspond to storage device102ofFIG. 1. Device400comprises a memory controller,106ofFIG. 1for example, mapping table114and memory108. Memory controller106comprises processor402, ROM404, RAM406, and input/output (I/O) interface408. Mapping table114includes logical to virtual mapping table410, and virtual to physical mapping table412. Memory108comprises physical blocks414-1. . .414-N, in an embodiment. The physical blocks may include a combination of intermediate memory118(SLC) physical blocks and main memory120(MLC) physical blocks. A physical block in intermediate memory118,414-1for example, may have a size corresponding to 1 Megabytes (Mbytes). A physical block in main memory120,414-7for example, may have a size corresponding to 3 Mbytes. Because the physical block414-7in main memory120is three times the size of a physical block,414-1for example, in intermediate memory118, data stored in three physical blocks in intermediate memory118may be copied and stored in a single physical block in main memory120.

In this embodiment, the processor402may copy software instructions from ROM404to RAM406. The processor402may execute the software instructions to perform the steps of storing data received from the host via I/O interface408to one or more of the physical blocks414-1. . .414-N, copying data from one or more physical blocks to another physical block and reading data from one or more physical blocks in response to receiving a request from the host. The I/O interface408may correspond to a serial interface such as the universal serial bus (USB) interface, a memory mapped interface or any other interface suitable for interfacing with the host.

Logical to virtual mapping table410may correspond to a series of entries410-1. . .410-N, where N corresponds to the number of entries. Each entry may correspond to a register or a memory location. Similarly virtual to physical mapping table412may correspond to a series of entries412-1. . .412-M, where M corresponds to the number of entries in the virtual to physical mapping table412. Each entry in the virtual to physical mapping table412may correspond to a register or a memory location.

Each entry in the logical to virtual mapping table410corresponds to a logical block address. Thus, entry410-1may correspond to LBA 0; entry410-2may correspond to LBA 1 and so on. Each LBA corresponds to a cluster of non-volatile memory in a physical block in intermediate memory118or main memory120. In one example, the size of a cluster may be 4096 bytes or 4 Kilobytes (Kbyte). In this example, each entry is associated with a 4 Kb cluster of non-volatile memory in a physical block.

In an exemplary embodiment, an entry in the virtual to physical mapping table412may include a reference to a physical block in intermediate memory118or main memory120. For example, entry412-1may include a reference to physical block414-1in intermediate memory. In this embodiment, an entry in the logical to virtual mapping table410may include a reference to an entry in the virtual to physical mapping table412if data associated with the LBA corresponding to the entry in the in the logical to virtual mapping table410is stored in a storage block that is referenced by the entry in the virtual to physical mapping table412. For example, if data associated with LBA 0 corresponding to entry410-1is stored in physical block414-1and if entry412-1includes a reference to physical block414-1, the entry410-1may include a reference to entry412-1.

The entry410-1may also include an offset into the physical block414-1where the 4 Kb cluster of data associated with LBA 0 is stored. If for example, the physical block414-1in intermediate memory is configured to store 1 Mb of data, 256 4-Kb clusters may be stored in one physical block (1 Mb/4 Kb=256). In this example, depending on where in the physical block414-1the 4 Kb cluster associated with the LBA 0 is stored, the offset included with entry410-1may have a value ranging from 0 to 255. For example, if the 4 Kb cluster is stored at the start of the physical block414-1, the offset is 0. If the 4 Kb cluster is stored at the end of the physical block414-1, the offset is 255.

In operation, in response to receiving a command from a host system to write data associated with a logical block address, memory controller106may locate an entry in the logical to virtual mapping table410based on the logical block address. In an embodiment, memory controller106may determine if the entry includes a reference to an entry in virtual to physical mapping table412and if the entry includes an offset into a physical block. If the entry includes a reference to an entry in virtual to physical mapping table412, memory controller106may utilize the reference to retrieve the reference to the physical block that is stored in the entry in the virtual to physical mapping table412. Based on the reference to the physical block and the offset into the physical block included in the located entry in the logical to virtual mapping table entry410, memory controller106may store the data the physical block at the offset.

In another embodiment, in response to receiving the command from the host system to write data to a logical block address, memory controller106may identify a cluster in a physical block that is available to be written i.e. no data corresponding to another logical block address is stored at the offset corresponding to the cluster in the physical block. Memory controller106may write the received data to the cluster in the physical block. The physical block may be part of the intermediate memory118or main memory120.

As previously mentioned, the logical block address received with the write command corresponds to an entry in the logical to virtual mapping table410. After completion of the write, memory controller106may update the entry in the logical to virtual mapping table410with the offset of the cluster in the physical block to where the data was written. If an entry in the virtual to physical mapping table412already contains a reference to the identified physical block, the entry in the logical to virtual mapping table410may be updated with the reference to the entry in the virtual to physical mapping table412. If none of the entries in the virtual to physical mapping table contain a reference to the identified physical block, an unused entry in the virtual to physical mapping table412may be updated with a reference to the identified physical block. The entry in the logical to virtual mapping table410may be updated with a reference to entry in the virtual to physical mapping table412. In an embodiment, any cluster associated with the logical address block before the write command was received may be reclaimed and marked as unused by the memory controller106. The order of the steps described above is not critical.

In the scenario where the logical block address has never been written to, the entry in the logical to virtual mapping table410corresponding to the logical block address may not include a reference to an entry in the virtual to physical mapping table412. In this scenario, memory controller106may locate an offset in a physical block where a cluster is free and may store the data in the physical block at the located offset. Additionally, memory controller106may identify an entry in the virtual to physical mapping table412that includes a reference to the physical block. If an entry is located in the virtual to physical mapping table412, memory controller106may store the reference in the entry in the logical to virtual mapping table410corresponding to the logical block address. The entry may also be updated with the offset in the physical block where the data was stored.

In the case where no entry is located in the virtual to physical mapping table412with a reference corresponding to physical block where the data was stored, the memory controller106may store the reference to the physical block in an unused entry in the virtual to physical mapping table412. The memory controller106may then store a reference to this entry in the logical to virtual mapping table410corresponding to the logical block address along with an offset to the location in the physical block where the data was stored.

As was previously explained, a physical block in intermediate memory118,414-1for example, may have a size corresponding to 1 Megabytes (Mbytes). A physical block in main memory120comprised of MLCs capable of storing 3 bits of information per MLC,414-7for example, may have a size corresponding to 3 Mbytes. Because the physical block414-7in main memory120is three times the size of a physical block,414-1for example, in intermediate memory118, data stored in three physical blocks in intermediate memory118may be copied and stored in a single physical block in main memory120.

In an exemplary embodiment, memory controller106may determine that all offsets in several physical blocks in intermediate memory118contain stored data. In this embodiment, memory controller106may copy the stored data from several physical blocks in intermediate memory to a single physical block in main memory120. For example, in response to determining that all offsets in physical blocks414-1,414-2and414-3contain stored data, memory controller106may copy data from physical blocks414-1,414-2and414-3and store the data into physical block in414-7. Data from physical block414-1may be copied to the lower third portion of block417-1, data from physical block414-2may be copied to the middle third portion and data from physical block414-3may be copied to the top third portion of physical block414-7.

In response to copying the data to physical block414-7, memory controller106may update the entries412-1,412-3and412-4with a reference to physical block414-7. Separately, entry412-1may be updated with an index,1for example, to indicate that data from414-1was copied to the lower third portion of physical block414-7, entry412-3may be updated with an index,2for example, to indicate that data from414-2was copied to the middle third portion of physical block414-7and entry412-4may be updated with an index,3for example, to indicate that data from physical block414-3was copied to the top third portion of physical block414-7. This process of copying data from several storage blocks to a single storage block with a corresponding update to entries in the virtual to physical mapping table412may be referred to as remapping. The process of remapping does not include updating entries in the fine granularity (4 Kbyte) logical to virtual mapping table410and only includes updating the coarse granularity virtual to physical mapping table412.

The host ofFIG. 1may command the memory controller106to read data for a logical block address. In response to receiving a request to read data, memory controller106may utilize the logical block address to retrieve an entry from the logical to virtual mapping table410corresponding to the logical block address. Memory controller106may retrieve an entry from the virtual to physical mapping table412corresponding to the reference stored in the entry retrieved from the logical to virtual mapping table410. Based on the entry retrieved from the virtual to physical mapping table412, the memory controller106may identify a physical block. As previously explained, the entry in the logical to virtual mapping table410includes an offset corresponding to where in the physical block, data associated with the logical block address was previously stored. Memory controller106may utilize this offset in conjunction with the identified physical block to read data associated with the logical block address. In scenarios where the data is stored in a physical block corresponding to main memory120,414-7for example, memory controller106may use the identified physical block and the index described above to index into the appropriate portion of the physical block414-7and then use the offset in the entry retrieved from the logical to physical mapping table to read data associated with the logical block address from the appropriate portion.

In the above described scheme, the number of entries in the virtual to physical mapping table412is an order of magnitude less than the number of entries in the logical to virtual mapping table410. For example, if the total size of all the physical blocks is 16 Mbytes, if each physical block has a size of 1 Mbytes and if a cluster of data associated with a logical block address is 4096 Kbytes, the logical to virtual mapping table410may be comprised of ((1048576*16)/4096) entries or 4096 entries. In contrast, the virtual to physical mapping table412may be comprised of only 16 entries or the number of physical blocks. Additionally, in this scheme when data is copied from several physical blocks having a lower density to another physical block with a higher density only one entry in the virtual to physical mapping table412needs to be updated.

FIG. 5is a flow diagram of an example method500that may be implemented in the memory controller ofFIG. 4. In an embodiment, at block510, information including data and a logical block address (LBA) may be received from the host system102(FIG. 1). Generally, the information may be a part of a command to write or store the data at a storage location corresponding to the LBA. The information may be received via the I/O interface104. At block520, the LBA may be utilized to retrieve a virtual block address from a logical to virtual mapping table410(FIG. 4), in an embodiment. The LBA may correspond to an index into the logical to virtual mapping table410, in this embodiment. In this embodiment, the index may be utilized to retrieve information stored in the entry in the logical to virtual mapping table410corresponding to the index. The retrieved information may represent the virtual block address.

At block530, the virtual block address retrieved from the logical to virtual mapping table410may be used to identify an entry in a virtual to physical mapping table412. The virtual block address may represent a pointer to a memory location in the virtual to physical mapping table412. Alternatively, the virtual block address may represent an index into the virtual to physical mapping table412.

At block540, a reference to a physical block stored in the entry identified from the virtual to physical mapping table412may be retrieved. At block550, the data received at block510may be stored in the physical block corresponding to the reference stored in entry identified at block540. In an embodiment, at block550after storing the data in the physical block, an indication may be communicated to the host system that the data has been stored.

At block560, another physical block may be identified. For example, a physical block from main memory120may be selected. Selecting the physical block may include determining that the selected physical block is empty or not being used to store data associated with another LBA. Data may be copied to the identified physical block from the original physical block used at block550.

At block570, the entry in the virtual to physical table412identified at block530may be updated with a reference to the physical block selected at block560. The physical block used to store data at block550may be tagged as being available for storing other data.

FIG. 6is a flow diagram of another example method600that may be implemented to facilitate the copying of data from one physical block to another physical block and the remapping of the virtual block address without changing the logical block address associated with the data.

In an embodiment, at block610, one or more physical block(s) may be identified. The physical block(s) may be identified in response to receiving a command to write data to a physical location. In an embodiment, the command to write data may also include the data and a logical block address (LBA). Identification of the physical block at block610may be based on the characteristics of the physical block. For example, in an embodiment a SLC type physical block may be identified from the intermediate memory118(FIG. 1). An SLC type physical block such as414-1(FIG. 4) may be selected because writing to an SLC type physical block takes lesser time than writing to an MLC type block414-7(FIG. 4). Additionally, in an embodiment, at block610only a physical block not being presently used for storage may be selected. In an embodiment, a table may be maintained that includes references to unused physical blocks. After identifying an unused SLC type storage block, the table may be adjusted to indicate that the identified block is being used.

At block620, the data received at block610may be stored in the SLC type storage block(s) identified at block610, in an embodiment. Referring toFIG. 4, at block630, a virtual block address may be identified in the logical to virtual mapping table based on the logical block address (LBA) received at block610. As previously explained the LBA may be utilized to index into the logical to virtual mapping table410and retrieve the virtual block address stored in an entry in the logical to virtual mapping table410corresponding to the LBA. For example if the LBA received is ‘5,’ the virtual block address stored at entry number 5 i.e.410-5in the logical to virtual mapping table410may be retrieved at block630.

At block630, the entry in the virtual to physical mapping table412corresponding to the virtual block address may be updated with a reference to the identified physical block(s). As previously explained, the virtual block address retrieved from the logical to physical mapping table may be used as an index into the virtual to physical mapping table412to retrieve the corresponding entry,412-5for example. In an embodiment, if the entry412-5contains a reference to another physical block, this physical block may be reclaimed and marked as being available.

At block640, an unused MLC type physical block may be identified from the main memory120,414-7for example, in an embodiment. The data stored in the SLC type physical block at block620may be copied to the MLC type physical block identified at block640. At block650, the reference to the SLC type physical block stored in the entry in the virtual to physical mapping table at block630may be updated with a reference to the MLC type physical block. The SLC type physical block may be reclaimed for future use.

FIG. 7is an example flow diagram of a method700for performing remapping of references to physical blocks after copying data for a first set of physical blocks to one or more second physical blocks. Method700may be implemented in the memory controller106ofFIG. 1and may utilize the logical to virtual mapping table and the virtual to physical mapping table discussed in the preceding paragraphs with reference toFIGS. 3 and 4.

At block710, memory controller106may receive data to be stored. The received data may be associated with several logical block addresses. The data for all of the logical block addresses may be received at the same time, consecutively and in any order. With reference toFIG. 4, each logical block address may correspond to an entry in logical to physical mapping table410,410-1for example.

At block720, data associated with each of the logical block addresses may be stored in a plurality of contiguous physical blocks. For example, in response to receiving data to be stored in logical block addresses corresponding to entries410-1,410-2and410-3of the logical to virtual mapping table410, the data may be stored in physical blocks414-1,414-2and414-3. As was previously discussed with reference toFIG. 4each of the entries410-1,410-2and410-3may reference a single entry in the virtual to physical mapping table412, entry412-1for example. The physical blocks may be contiguous in one embodiment. The physical blocks may each be comprised of SLCs.

At block730, the entry in the virtual to physical mapping table412, entry412-1for example, may be updated with one or more references to the physical blocks414-1,414-2and414-3for example. In the embodiment where the physical blocks414-1,414-2and414-3are contiguous, at block730, entry412-1may be updated with a reference to first physical block,414-1for example.

Data from the physical blocks may be copied to a single physical block at block740. In an embodiment, the single physical block may be comprised of MLCs.414-7for example. The single physical block may be capable of storing the data from multiple SLC type physical blocks. In another embodiment, the single physical block may be comprised of SLCs.

At block750, the entry412-1in virtual to physical mapping table412is updated with a reference to the single physical block414-7. However, the entries410-1,410-2and410-3need not be updated and may continue to reference entry412-1.

Although in foregoing discussion, the first physical block is described as comprising SLC type cells and the second physical block is described as comprising MLC type cells, in other embodiments, both the first and second physical blocks may correspond to physical blocks comprising either SLC type cells or MLC type cells.

A system and method that implements a block remapping layer in a mapping table of a memory system is provided. The block remapping layer is a virtual block to physical block remapping layer that may avoid the need to remap each cluster associated with a virtual block. The block remapping scheme discussed herein allows for the efficient copying of data stored in large physically contiguous storage blocks of data from one layer to another. In an exemplary embodiment, storage blocks in the two layers may be comprised of different type of flash memory cells (e.g., one layer might be SLC and one layer might be MLC).

As described in the foregoing logical block addresses are mapped via a fine granularity logical to virtual mapping table410to virtual physical blocks in the SLC layer. Virtual physical blocks are remapped to physical blocks in the MLC layer by the virtual to physical mapping table412. Typically the virtual physical block size is a common multiple of the physical block sizes (of which several may exist if multiple layers of flash technology are used). When data is moved between physical blocks in large contiguous chunks of size a multiple of the virtual physical block size, rather than update multiple entries in the logical to physical fine granularity mapping table, a single (or few) entries in the block remap table may be adjusted to remap the virtual physical block to its new physical block location. This is typically the case when data is being moved between intermediate memory118in a storage device108to main memory120in the storage device108.

Further embodiments can be envisioned by one of ordinary skill in the art after reading the foregoing. In other embodiments, combinations or sub-combinations of the above disclosed invention can be advantageously made. The block diagrams of the architecture and flow diagrams are grouped for ease of understanding. However it should be understood that combinations of blocks, additions of new blocks, re-arrangement of blocks, and the like are contemplated in alternative embodiments of the present invention.