Programming an embedded flash storage device

Description

BACKGROUND OF THE INVENTION

An embedded flash storage device (such as an embedded flash storage device) is a flash storage device that is embedded in a computerized system that also includes a host computer and a flash memory controller. The embedded flash storage device may be activated only under the permission of the host computer.

Data units can be read from the embedded flash storage device during read transactions and can be written (programmed) to the embedded flash storage device during write transactions.

The read and write processes utilize one or more memory management tables that may map logical addresses of data units to physical addresses of flash memory cells that store the data units.

The embedded flash storage device are subjected to power failures but are expected to maintain the integrity of data units that were written during successfully completed write transactions despite such power failures.

In order to maintain this integrity a successfully completed write transaction should include the programming of (a) data unit, and of (b) one or more memory management tables that are updated to reflect the programming of the data unit.

The throughput of an embedded flash storage device is inversely proportional to the latency of a transaction.

Referring to a write transaction latency—this latency is defined by a period required to successfully complete a write transaction—including a programming of one or more data units and a programming updated memory management tables (after updating the memory management tables).

FIG. 1 illustrates a prior art timing diagram 10 and FIG. 2 illustrates a prior art method 20.

The method 20 includes the following sequence of stages starting (21) by a flash memory controller, a write transaction; programming (22), by the embedded flash storage device, a data unit to a flash memory unit of the embedded flash storage device; updating (23) by the flash memory controller, the memory management tables to reflect the programming of the data unit; programming (24) by the embedded flash storage device, the memory management tables (after being updated) to the flash memory unit; sending (25) to the host computer an acknowledgement of a successful completion of the write transaction—after a successful completion of stages 21-24; sending (26) the write transaction.

It is noted that stages 22 and 24 are relatively long in relation to other stages of method 20.

Timing diagram 10 illustrates the sequence of signals and stages a write transaction initialization signal 11 from the host computer to the flash memory controller. This starts a write transaction of duration 12; initial operations (13) executed by the flash memory controller before the programming of a data unit. This may include determining where to write the data unit, error correction encoding the data unit and the like; programming (14) by the embedded flash storage device, a data unit to the flash memory unit of the embedded flash storage device; intermediate operations (15) executed by the flash memory controller before programming the memory management tables—such as updating the memory management tables; programming (16) the memory management tables to the flash memory unit; final operations (17) executed by the flash memory controller. For example—checking the status of a program; sending (18) an acknowledgment to the host computer and thereby ending the transaction.

As illustrated above—the host computer can be notified that the write transaction succeeded only after the (entire) write transaction succeeded and thus the latency of write transaction is relatively high and the throughput of the embedded flash is low.

There is a need to provide a low latency and power failure tolerant method for programming data units to an embedded flash storage device.

SUMMARY

According to an embodiment of the invention a method may be provided and may include sending, by a flash memory controller, to an embedded flash storage device and during a transaction, a data unit and recovery metadata; wherein the recovery metadata differs from a flash memory unit memory management data structure; instructing the embedded flash storage device to program the data unit and the recovery metadata to a group of flash memory cells of a flash memory unit of the embedded flash storage device; sending, by the flash memory controller, to the host computer a transaction completion indication in response to a successful completion of the programming and before a completion of a management process that may include updating by the flash memory controller, the flash memory unit management data structure to reflect (a) the recovery metadata and (b) physical address information related to the group of the flash memory cells; and programming, by the embedded flash storage device, the flash memory management data structure to the flash memory unit; wherein the flash memory management data structure is reconstructible based upon the recovery metadata and the physical address information related to the group of the flash memory cells.

The method may include attempting by the embedded flash storage device to complete the management process.

The management process is assigned a lower priority than programming data units to the flash memory unit.

The method may include reconstructing, by the flash memory controller, the flash memory management data structure based upon the recovery metadata and the physical address information related to the group of the flash memory cells if the management process failed to be successfully completed. The failure may be contributed to a sudden power drop.

The method may include determining, by the flash memory controller, whether the management process failed by comparing (a) a content of a flash memory management data structure stored in the flash memory unit and (b) a combination of (i) the recovery metadata and (ii) the physical address information related to the group of the flash memory cells.

The method may include determining, by the flash memory controller, whether the management process failed by comparing (a) a first mapping between a logical address and a physical address of the data unit as reflected by a flash memory management data structure stored in the flash memory unit and (b) a second mapping between the logical address and the physical address of the data unit as reflected by the recovery metadata and the physical address information related to the group of the flash memory cells.

The method may include updating the flash memory unit management data structure in parallel to a programming of the data unit and the recovery metadata by the embedded flash storage device.

The method may include receiving multiple data units and performing multiple updates of the flash memory management data structure, each update related to a different data unit of the multiple data units to provide the flash memory management data structure before programming the flash memory management data structure to the flash memory unit.

The recovery metadata may represent a logical address of the data unit.

According to an embodiment of the invention there may be provided a non-transitory computer readable medium that includes instructions to be executed by a computerized system and may store instructions for sending to an embedded flash storage device and during a transaction, a data unit and recovery metadata; wherein the recovery metadata differs from a flash memory unit memory management data structure; instructing the embedded flash storage device to program the data unit and the recovery metadata to a group of flash memory cells of a flash memory unit of the embedded flash storage device; sending to the host computer a transaction completion indication in response to a successful completion of the programming and before a completion of a management process that may include updating the flash memory unit management data structure to reflect (a) the recovery metadata and (b) physical address information related to the group of the flash memory cells; and programming, by the embedded flash storage device, the flash memory management data structure to the flash memory unit; wherein the flash memory management data structure is reconstructible based upon the recovery metadata and the physical address information related to the group of the flash memory cells.

The non-transitory computer readable medium may store instructions for attempting by the embedded flash storage device to complete the management process.

The management process is assigned a lower priority than programming data units to the flash memory unit.

The non-transitory computer readable medium may store instructions for reconstructing, by the flash memory controller, the flash memory management data structure based upon the recovery metadata and the physical address information related to the group of the flash memory cells if the management process failed to be successfully completed.

The non-transitory computer readable medium may store instructions for determining, by the flash memory controller, whether the management process failed by comparing (a) a content of a flash memory management data structure stored in the flash memory unit and (b) a combination of (i) the recovery metadata and (ii) the physical address information related to the group of the flash memory cells.

The non-transitory computer readable medium may store instructions for determining, by the flash memory controller, whether the management process failed by comparing (a) a first mapping between a logical address and a physical address of the data unit as reflected by a flash memory management data structure stored in the flash memory unit and (b) a second mapping between the logical address and the physical address of the data unit as reflected by the recovery metadata and the physical address information related to the group of the flash memory cells.

The non-transitory computer readable medium may store instructions for updating the flash memory unit management data structure in parallel to a programming of the data unit and the recovery metadata by the embedded flash storage device.

The non-transitory computer readable medium may store instructions for receiving multiple data units and performing multiple updates of the flash memory management data structure, each update related to a different data unit of the multiple data units to provide the flash memory management data structure before programming the flash memory management data structure to the flash memory unit.

The recovery metadata represents a logical address of the data unit.

According to an embodiment of the invention there may be provided a flash memory controller, may include a write circuit that is arranged to send to embedded flash storage device and during a transaction, a data unit and recovery metadata; wherein the recovery metadata differs from a flash memory unit memory management data structure; instruct the embedded flash storage device to program the data unit and the recovery metadata to a group of flash memory cells of a flash memory unit of the embedded flash storage device; and an interface that is arranged to send to a host computer a transaction completion indication in response to a successful completion of the programming and before a completion of management process that may include updating the flash memory unit management data structure to reflect (a) the recovery metadata and (b) physical address information related to the group of the flash memory cells; and programming, by the embedded flash storage device, the flash memory management data structure to the flash memory unit; wherein the flash memory management data structure is reconstructible based upon the recovery metadata and the physical address information related to the group of the flash memory cells.

The flash memory controller may include a random access memory for storing the flash memory management data structure.

The flash memory controller may be arranged to attempt to complete the management process.

The management process may be assigned a lower priority than programming data units to the flash memory unit.

The flash memory controller may be arranged to reconstruct the flash memory management data structure based upon the recovery metadata and the physical address information related to the group of the flash memory cells if the management process failed to be successfully completed. The failure may be contributed to a sudden power drop.

The flash memory controller may be arranged to determine whether the management process failed by comparing (a) a content of a flash memory management data structure stored in the flash memory unit and (b) a combination of (i) the recovery metadata and (ii) the physical address information related to the group of the flash memory cells.

The flash memory controller may be arranged to determine whether the management process failed by comparing (a) a first mapping between a logical address and a physical address of the data unit as reflected by a flash memory management data structure stored in the flash memory unit and (b) a second mapping between the logical address and the physical address of the data unit as reflected by the recovery metadata and the physical address information related to the group of the flash memory cells.

The flash memory controller may be arranged to update the flash memory unit management data structure in parallel to a programming of the data unit and the recovery metadata by the embedded flash storage device.

The flash memory controller may be arranged to receive multiple data units and performing multiple updates of the flash memory management data structure, each update related to a different data unit of the multiple data units to provide the flash memory management data structure before programming the flash memory management data structure to the flash memory unit.

The recovery metadata may represent a logical address of the data unit.

BRIEF DESCRIPTION OF THE DRAWINGS

The subject matter regarded as the invention is particularly pointed out and distinctly claimed in the concluding portion of the specification. The invention, however, both as to organization and method of operation, together with objects, features, and advantages thereof, may best be understood by reference to the following detailed description when read with the accompanying drawings in which:

FIG. 1 illustrates a prior art method;

FIG. 2 illustrates a prior art timing diagram;

FIG. 3 illustrates a method according to an embodiment of the invention;

FIG. 4 illustrates a timing diagram according to an embodiment of the invention;

FIG. 5 illustrates a method according to an embodiment of the invention;

FIG. 6 illustrates recovery metadata, a flash memory unit memory management data structure and physical address information according to an embodiment of the invention;

FIG. 7 illustrates recovery metadata, a flash memory unit memory management data structure and physical address information according to an embodiment of the invention;

FIG. 8 illustrates recovery metadata, a flash memory unit memory management data structure and physical address information according to an embodiment of the invention;

FIG. 9 illustrates a device according to an embodiment of the invention.

It will be appreciated that for simplicity and clarity of illustration, elements shown in the figures have not necessarily been drawn to scale. For example, the dimensions of some of the elements may be exaggerated relative to other elements for clarity. Further, where considered appropriate, reference numerals may be repeated among the figures to indicate corresponding or analogous elements.

DETAILED DESCRIPTION OF THE DRAWINGS

In the following detailed description, numerous specific details are set forth in order to provide a thorough understanding of the invention. However, it will be understood by those skilled in the art that the present invention may be practiced without these specific details. In other instances, well-known methods, procedures, and components have not been described in detail so as not to obscure the present invention.

The subject matter regarded as the invention is particularly pointed out and distinctly claimed in the concluding portion of the specification. The invention, however, both as to organization and method of operation, together with objects, features, and advantages thereof, may best be understood by reference to the following detailed description when read with the accompanying drawings.

Because the illustrated embodiments of the present invention may for the most part, be implemented using electronic components and circuits known to those skilled in the art, details will not be explained in any greater extent than that considered necessary as illustrated above, for the understanding and appreciation of the underlying concepts of the present invention and in order not to obfuscate or distract from the teachings of the present invention.

Any reference in the specification to a method should be applied mutatis mutandis to a system capable of executing the method and should be applied mutatis mutandis to a non-transitory computer readable medium may store instructions that once executed by a computer result in the execution of the method.

Any reference in the specification to a system should be applied mutatis mutandis to a method that may be executed by the system and should be applied mutatis mutandis to a non-transitory computer readable medium may store instructions that may be executed by the system.

Any reference in the specification to a non-transitory computer readable medium should be applied mutatis mutandis to a system capable of executing the instructions stored in the non-transitory computer readable medium and should be applied mutatis mutandis to method that may be executed by a computer that reads the instructions stored in the non-transitory computer readable medium.

The term “data unit” may refer to multiple bits that convey information of any type and of any size. The data unit can be a byte, a word, a page, a block, a logical access unit and the like.

It is noted that programming of the flash memory unit management data structure can include programming the entire flash memory unit management data structure, programming portions of the flash memory unit management data structure and even programming only updates to the flash memory unit management data structure. Accordingly—any reference to each of these programming options should be applied mutatis mutandis to any other of these programming options.

FIG. 3 illustrates a method 100 according to an embodiment of the invention.

Method 100 may start by stage 110 of sending a data unit and recovery metadata, by a flash memory controller, to an embedded flash storage device and during a transaction.

The recovery metadata differs from a flash memory unit memory management data structure. It is usually much smaller than the flash memory unit memory management metadata. It may, for example, describe the logical address of the data unit and may not include information about the physical address of the data unit.

Stage 110 may be triggered by a reception by a flash memory controller of an instruction sent from the host computer—instructing the flash memory controller to initiate a write transaction or otherwise by an indication from the host computer that allows the flash memory controller to initiate a transaction.

The recovery metadata may be included at a spare area allocated for storing, for example, redundancy information. The recovery metadata may be included instead of redundancy bits. The recovery metadata may be much smaller than the data unit—for example 8 bytes of recovery metadata for 500 bytes of data unit. Other sizes and relationships between sizes of data unit and recovery metadata can be provided.

Stage 110 may be followed by stage 120 of instructing an embedded flash storage device to program the data unit and the recovery metadata to a flash memory unit of the embedded flash storage device.

Then data unit and the recovery metadata should be programmed to a group of flash memory cells of the flash memory unit. The group of flash memory cells may include a consecutive group of flash memory cells, a non-consecutive group of flash memory cells and the like.

Stage 120 may be followed by stage 130 of programming, by the embedded flash storage device, the data unit, and the recovery metadata to the group of flash memory cells of the flash memory unit.

The data unit and the recovery metadata may be written to a predefined location—or within a predefined memory region. The content (or at least a portion of the content) of the predefined location can be read during a power up process in order to allow to retrieve the recovery metadata upon power up.

The data units and recovery metadata may be written in a sequential manner in order to assist in determining the order of writing.

Alternatively, the data units and the recovery metadata may be written in a non-sequential manner but may include time stamps or any other indication about the order of programming. The order of programming can be useful, for example, when the flash memory management data structure also has a time stamp—which can assist in determining which data units were written after the last update of the flash memory management data structure.

According to other embodiments of the invention—the flash memory management data structure may store pointers to data units, such as a pointer to a last data unit that was used to update that flash memory management data structure.

Stage 130 may be followed (if successfully completed) by stage 140 of informing the flash memory controller by the embedded flash storage device that the programming of the data unit and the recovery metadata succeeded.

Stage 140 may be followed by stage 150 of sending to the host computer (by the flash memory controller) a transaction completion indication in response to a successful completion of the programming. At this point the host computer can be released from monitoring after the programming.

Method 100 also includes a management process 160. The management process 160 may start after either one of stages 120, 130, 140 and 150. The management process 160 is completed after the completion of stage 150.

The management process 160 may include stage 162 of updating by the flash memory controller, the flash memory unit management data structure to reflect (a) the recovery metadata and (b) physical address information related to the group of the flash memory cells; stage 164 of programming, by the embedded flash storage device, the flash memory management data structure to the flash memory unit. The flash memory management data structure can be reconstructed (is reconstructible) based upon the recovery metadata and the physical address information related to the group of the flash memory cells.

According to an embodiment of the invention the management process can be assigned a lower priority than programming data units to the flash memory unit. It can be executed as a background process.

Stage 164 may be executed, for example, in parallel to stages that do not require access to the flash memory unit. It may occur during a reception of data units from the host, while another flash memory die of the flash memory unit is programmed, and the like. For example—a write command can cause more than a single page program. Once a first page data received and program started, following data is being received on Host interface. In parallel controller can perform other non-flash operations. Alternatively or additionally, if there are multiple NANAD flash dies then different NAND operations can be done on different dies in parallel.

Method 100 may be repeated for each data unit. Alternatively, the method can include accumulating updates and programming only an accumulation of updates.

Thus—the programming of the flash memory management data structure (stage 164) can be executed once for each multiple data units (once for multiple updates)—thereby making the programming of the flash memory management data structure more efficient. Stage 164 may include counting whether the number of updates (the number of data units) received from the last programming reaches a threshold or not. If reaches-then programming.

The number of accumulated updates can provide a trade-off between programming efficiency (higher number) and reduction of reconstruction operations (lower number). This number can also be dictated or at least be limited by the allowable duration of a single programming iteration of the embedded flash storage device.

The size (number) of the accumulation may be limited by several factors; prior prepared Flash portion is limited and thus once reaching its fullness may cause boundary on flash memory management data structure updates accumulation. In order to have easy recovery process there may be provided a certain area for future incoming data. This area will be the only search location during recovery process instead of searching entire disk. This area is limited, thus once full, there is a need to allocate new one. In such case, all updates and full recovery information should be stored before going to new area; power up process (that includes the recovery process) time limitation may restrict the amount of unmapped data units (data units not mapped by the flash memory management data structure) that can be processed during power up time; power up process duration may be limited by system requirements; in addition to a possible limitation on the overall duration of the power up process—it should be noted that only a part of the power up process can be allocated to the recovery process. Rest of the time is used for other boot and maintenance operations; the reading of data units and recovery metadata has some latency. Metadata extraction and processing has latency. These latencies should also be taken into account; the recovery time of the flash memory management data structure divided by an effective recovery metadata extraction time can provide an upper limit on amount of accumulation; the flash memory management data structure updates are stored in a non-volatile memory and the non-volatile memory limitations (such as size, read latency) may limit the number of accumulations.

According to an embodiment of the invention the updates to the flash memory management data structure can be accumulated while transactions are incoming. These updates may be programmed only between transactions but this is not necessarily so.

As transactions behavior may be bursty, characterized by transactions bursts and idle periods alternatively—delaying the programming of the updates can allow the system to use the idle periods and eliminate impact on real time transactions.

According to an embodiment of the invention the host computer can control the idle times and the timing of execution of the programming of updates.

According to an embodiment of the invention flash memory management data structure updates are programmed using multiple (even all) flash memory dies of the embedded flash storage device in order to increase throughput and reduce latency.

Alternatively, the flash memory management data structure programming can be made to flash memory dies of the embedded flash storage device that are not used for programming data units and metadata.

FIG. 4 illustrates a timing diagram 200 according to an embodiment of the invention.

Timing diagram 200 illustrates the sequence of signals and stages a write transaction initialization signal 11 from the host computer to the flash memory controller. This starts a write transaction of duration 212; initial operations (213) executed by the flash memory controller before the programming of a data unit. This may include generating or receiving recovery metadata, determining where to write the data unit, error correction encoding the data unit and the like; programming (214) by the embedded flash storage device, a data unit and data unit reconstruction metadata to the flash memory unit of the embedded flash storage device; intermediate operations (215) executed by the flash memory controller before programming the memory management tables; sending (218) an acknowledgment to the host computer and thereby ending the transaction.

FIG. 5 illustrates a method 300 according to an embodiment of the invention.

Method 300 starts by stage 310 of initiating a power up process of a flash memory controller.

Stage 310 may be followed by stages 320 and 330.

Stage 320 includes retrieving from the embedded flash storage device a flash memory management data structure.

Stage 330 includes retrieving from the embedded flash storage device recovery metadata.

It is assumed that the data unit and the recovery metadata are stored in a known (physical) address range so that the physical address of the group of flash memory units that store the data unit is either known in advance (before reading the data unit) known or can be obtained when reading the data unit from the known physical address range.

Stages 320 and 330 are followed by stage 340 of determining whether the flash memory management data structure needs to be reconstructed (updated) or not, in response to (i) the flash memory management data structure (stage 320), (ii) the recovery metadata (stage 330) and the physical address of the group of flash memory units that store the data unit.

Stage 340 may include comparing (a) a first mapping between a logical address and a physical address of the data unit as reflected by the flash memory management data structure and (b) a second mapping between the logical address and the physical address of the data unit as reflected by the recovery metadata and the physical address information related to the group of the flash memory cells.

Stage 340 may be followed by stage 350 of reconstructing the flash memory management data structure if it is determined that it needs to be reconstructed.

Stage 340 may be followed by stage 360 of unchanging the flash memory management data structure if it is determined that it does should not be reconstructed.

If, for example, the data unit does not appear in the flash memory management data structure then the flash memory management data structure should be updated (stage 350) to reflect the programming of the data unit to the flash memory unit.

If, for example, the data unit appears in the flash memory management data structure but the first mapping differs from the second mapping then the flash memory management data structure should be updated (stage 350) to reflect the second mapping and not the first mapping.

FIG. 6-8 illustrate recovery metadata MD 46(1,1)-46(1,K), 46(R,1)-46(R,K), a flash memory unit memory management data structure 67 and physical address information ADD MD 46(1,1)-48(1,K), 48(R,1)-48(R,K) according to various embodiments of the invention.

Flash memory unit memory management data structure 67 provides a mapping between a logical address (LA) of a data unit and a physical address of the data unit (ADD 48(r,k)).

Flash memory unit memory management data structure 67 is illustrated as including a root mapping table 60 and multiple (R) second level mapping tables 70(1)-70(R).

The root mapping table 60 stores pointers to second level mapping tables 70(1)-70(R). The second level mapping tables 70(1)-70(R) stores pointers to the physical addresses of the data units—to the groups of flash memory cells that store the data units.

Each second level mapping table can store K or more pointers to K or more data units. The root mapping table can store R or more pointer to R or more second level mapping tables.

Second level mapping table 70(1) stores indexes to data units DU 44(1,1)-44(1,K), wherein each data unit is appended with recovery metadata MD 46(1,1)-46(1,K). Second level mapping table 70(R) stores indexes to data units DU 44(R,1)-44(R,K), wherein each data unit is appended with recovery metadata MD 46(R,1)-46(R,K).

This arrangement supports a two stage mapping—

a. The most significant part (MSB) of the LA is used as an index to an entry of the root mapping table—which entry points to a physical address of a selected second level mapping table 70(r). Entry 60(m) includes a mapping between the most significant part of the logical address “MSB of LA” 61(m) and the physical address of a selected second level mapping table “PA of 2MT” 62(m). The number of entries of the root mapping table can be the number of maximal different logical addresses to be assigned to the data units.
b. The least significant part (LSB) of the LA is used as an index to an entry of the selected second level mapping table 70(k) may store the pointer to the physical address of the data unit itself. Entry 70(k) includes a mapping between the least significant part of the logical address “LSB of LA” 71(K) and the physical address of the data unit ADD 48(R,k).

In FIG. 7 all the data units are properly mapped in the flash memory unit memory management data structure 67. If a power up process starts at that state there may be no need to update the flash memory unit memory management data structure 67.

In FIG. 7 a T'th data unit DU 44(T) is stored in the flash memory (within predefined memory region 42) but is not mapped by the flash memory unit memory management data structure 67. Accordingly—when powering up the flash memory controller will read the content of the predefined memory region 42 or a part of it (for example—a part that is not mapped) and find DU 44(T). In this case a recovery process s(update) will be triggered in which both root mapping table 60 and a second level mapping table (for example the R'th second level mapping table 70(R)) will be updated.

Although the example set forth in FIGS. 7-9 refers to an unmapped data unit it is noted that updates may also occur if a data unit was deleted or is mapped to a new physical address.

FIG. 8 illustrates that the new data unit (previously denoted DU 44(T)) is not pointer by entry the (K+1)'th entry of the R'th second level mapping table 70(R) and is now denoted DU 44(R,K+1). Entry 70(K+1) includes a mapping between the least significant part of the logical address “LSB of LA” 71(K+1) and the physical address of the data unit ADD 48(R,K+1). It is noted that the root mapping table is also updating by adding an entry that maps the most significant part of the logical address of DU 44(R,K+1) to the R'th second mapping table.

FIG. 9 illustrates a system 500 according to an embodiment of the invention.

System 500 includes a flash memory controller 510, an embedded flash storage device 520, and a host computer 530. The flash memory controller 510 is coupled to the embedded flash storage device 520 and to the host computer 530.

The embedded flash storage device 520 includes an internal controller 522 and a flash memory unit 524 that may include one or more dies.

The flash memory controller 510 includes a read circuit 512 for reading from the embedded flash storage device 520, a write circuit 514, a volatile memory 516, and an interface 518.

The write circuit 514 is arranged to send to the embedded flash storage device 520 and during a transaction, a data unit and recovery metadata. The recovery metadata differs from a flash memory unit memory management data structure; instruct the embedded flash storage device to program the data unit and the recovery metadata to a group of flash memory cells of a flash memory unit of the embedded flash storage device.

The interface 516 is arranged to send to a host computer a transaction completion indication in response to a successful completion of the programming and before a completion of management process that includes updating the flash memory unit management data structure to reflect (a) the recovery metadata and (b) physical address information related to the group of the flash memory cells; and programming, by the embedded flash storage device, the flash memory management data structure to the flash memory unit. The flash memory management data structure is reconstructible based upon the recovery metadata and the physical address information related to the group of the flash memory cells.

The invention may also be implemented in a computer program for running on a computer system, at least including code portions for performing steps of a method according to the invention when run on a programmable apparatus, such as a computer system or enabling a programmable apparatus to perform functions of a device or system according to the invention. The computer program may cause the storage system to allocate disk drives to disk drive groups.

A computer program is a list of instructions such as a particular application program and/or an operating system. The computer program may for instance include one or more of a subroutine, a function, a procedure, an object method, an object implementation, an executable, an applet, a servlet, a source code, an object code, a shared library/dynamic load library and/or other sequence of instructions designed for execution on a computer system.

The computer program may be stored internally on a non-transitory computer readable medium. All or some of the computer program may be provided on computer readable media permanently, removably or remotely coupled to an information processing system. The computer readable media may include, for example and without limitation, any number of the following magnetic storage media including disk and tape storage media; optical storage media such as compact disk media (e.g., CD-ROM, CD-R, etc.) and digital video disk storage media; nonvolatile memory storage media including semiconductor-based memory units such as FLASH memory, EEPROM, EPROM, ROM; ferromagnetic digital memories; MRAM; volatile storage media including registers, buffers or caches, main memory, RAM, etc.

A computer process typically includes an executing (running) program or portion of a program, current program values and state information, and the resources used by the operating system to manage the execution of the process. An operating system (OS) is the software that manages the sharing of the resources of a computer and provides programmers with an interface used to access those resources. An operating system processes system data and user input, and responds by allocating and managing tasks and internal system resources as a service to users and programs of the system.

The computer system may for instance include at least one processing unit, associated memory and a number of input/output (I/O) devices. When executing the computer program, the computer system processes information according to the computer program and produces resultant output information via I/O devices.

In the foregoing specification, the invention has been described with reference to specific examples of embodiments of the invention. It will, however, be evident that various modifications and changes may be made therein without departing from the broader spirit and scope of the invention as set forth in the appended claims.

Moreover, the terms “front,” “back,” “top,” “bottom,” “over,” “under” and the like in the description and in the claims, if any, are used for descriptive purposes and not necessarily for describing permanent relative positions. It is understood that the terms so used are interchangeable under appropriate circumstances such that the embodiments of the invention described herein are, for example, capable of operation in other orientations than those illustrated or otherwise described herein.

The connections as discussed herein may be any type of connection suitable to transfer signals from or to the respective nodes, units or devices, for example via intermediate devices. Accordingly, unless implied or stated otherwise, the connections may for example be direct connections or indirect connections. The connections may be illustrated or described in reference to being a single connection, a plurality of connections, unidirectional connections, or bidirectional connections. However, different embodiments may vary the implementation of the connections. For example, separate unidirectional connections may be used rather than bidirectional connections and vice versa. In addition, plurality of connections may be replaced with a single connection that transfers multiple signals serially or in a time multiplexed manner. Likewise, single connections carrying multiple signals may be separated out into various different connections carrying subsets of these signals. Therefore, many options exist for transferring signals.

Although specific conductivity types or polarity of potentials have been described in the examples, it will be appreciated that conductivity types and polarities of potentials may be reversed.

Each signal described herein may be designed as positive or negative logic. In the case of a negative logic signal, the signal is active low where the logically true state corresponds to a logic level zero. In the case of a positive logic signal, the signal is active high where the logically true state corresponds to a logic level one. Note that any of the signals described herein may be designed as either negative or positive logic signals. Therefore, in alternate embodiments, those signals described as positive logic signals may be implemented as negative logic signals, and those signals described as negative logic signals may be implemented as positive logic signals.

Furthermore, the terms “assert” or “set” and “negate” (or “deassert” or “clear”) are used herein when referring to the rendering of a signal, status bit, or similar apparatus into its logically true or logically false state, respectively. If the logically true state is a logic level one, the logically false state is a logic level zero. Moreover, if the logically true state is a logic level zero, the logically false state is a logic level one.

Those skilled in the art will recognize that the boundaries between logic blocks are merely illustrative and that alternative embodiments may merge logic blocks or circuit elements or impose an alternate decomposition of functionality upon various logic blocks or circuit elements. Thus, it is to be understood that the architectures depicted herein are merely exemplary, and that in fact many other architectures may be implemented which achieve the same functionality.

Any arrangement of components to achieve the same functionality is effectively “associated” such that the desired functionality is achieved. Hence, any two components herein combined to achieve a particular functionality may be seen as “associated with” each other such that the desired functionality is achieved, irrespective of architectures or intermedial components. Likewise, any two components so associated can also be viewed as being “operably connected,” or “operably coupled,” to each other to achieve the desired functionality.

Furthermore, those skilled in the art will recognize that boundaries between the above described operations merely illustrative. The multiple operations may be combined into a single operation, a single operation may be distributed in additional operations and operations may be executed at least partially overlapping in time. Moreover, alternative embodiments may include multiple instances of a particular operation, and the order of operations may be altered in various other embodiments.

Also for example, in one embodiment, the illustrated examples may be implemented as circuitry located on a single integrated circuit or within a same device. Alternatively, the examples may be implemented as any number of separate integrated circuits or separate devices interconnected with each other in a suitable manner.

Also for example, the examples, or portions thereof, may implemented as soft or code representations of physical circuitry or of logical representations convertible into physical circuitry, such as in a hardware description language of any appropriate type.

Also, the invention is not limited to physical devices or units implemented in non-programmable hardware but can also be applied in programmable devices or units able to perform the desired device functions by operating in accordance with suitable program code, such as mainframes, minicomputers, servers, workstations, personal computers, notepads, personal digital assistants, electronic games, automotive and other embedded systems, cell phones and various other wireless devices, commonly denoted in this application as ‘computer systems’.

However, other modifications, variations and alternatives are also possible. The specifications and drawings are, accordingly, to be regarded in an illustrative rather than in a restrictive sense.

In the claims, any reference signs placed between parentheses shall not be construed as limiting the claim. The word ‘comprising’ does not exclude the presence of other elements or steps then those listed in a claim. Furthermore, the terms “a” or “an,” as used herein, are defined as one or more than one. Also, the use of introductory phrases such as “at least one” and “one or more” in the claims should not be construed to imply that the introduction of another claim element by the indefinite articles “a” or “an” limits any particular claim containing such introduced claim element to inventions containing only one such element, even when the same claim includes the introductory phrases “one or more” or “at least one” and indefinite articles such as “a” or “an.” The same holds true for the use of definite articles. Unless stated otherwise, terms such as “first” and “second” are used to arbitrarily distinguish between the elements such terms describe. Thus, these terms are not necessarily intended to indicate temporal or other prioritization of such elements The mere fact that certain measures are recited in mutually different claims does not indicate that a combination of these measures cannot be used to advantage.

While certain features of the invention have been illustrated and described herein, many modifications, substitutions, changes, and equivalents will now occur to those of ordinary skill in the art. It is, therefore, to be understood that the appended claims are intended to cover all such modifications and changes as fall within the true spirit of the invention.