Apparatus and method to protect metadata against unexpected power down

A system includes first memory configured to store first metadata to associate logical addresses with physical addresses. Second memory is configured to include the physical addresses, to store first data based on the physical addresses, and to store portions of the first metadata when a status of a predetermined group of the physical addresses is changed. A recovery module is configured to update the first metadata based on the portions of the first metadata stored in the second memory.

FIELD

The present disclosure relates to protecting and rebuilding metadata.

BACKGROUND

A computing device may include various removable and non-removable storage devices that store data. The storage devices may include both volatile and non-volatile storage devices including, but not limited to, a hard disk drive (HDD), an optical storage drive, random access memory (RAM), read only memory (ROM), and removable memory. For example, the removable memory may include flash memory.

The flash memory may include a flash drive that is used to emulate an HDD. For example, the computing device may store data to the flash memory as if the flash memory is an HDD. The flash drive may store metadata that indicates how user data is stored to the flash drive. For example, the metadata may indicate how logical addresses correspond to actual physical addresses of the flash drive that contain the user data.

During operation of the computing device, the metadata is updated and stored in volatile memory when user data is read from and written to the flash drive. The metadata is transferred to the flash drive when the computing device is powered down.

SUMMARY

A system includes first memory configured to store first metadata to associate logical addresses with physical addresses. Second memory is configured to include the physical addresses, to store first data based on the physical addresses, and to store portions of the first metadata when a status of a predetermined group of the physical addresses is changed. A recovery module is configured to update the first metadata based on the portions of the first metadata stored in the second memory.

In other features, the first metadata includes a first lookup table to associate the logical address with the physical addresses. The first metadata includes a second lookup table to associate the physical addresses with the logical addresses. The predetermined group of the physical addresses is a wide erase block unit (WERU). The first metadata includes identifiers for a plurality of WERUs and the identifiers correspond to respective bins. The first metadata includes an activity log to indicate when a first identifier for one of the plurality of WERUs is changed. The second memory stores the portions of the first metadata when the first identifier is changed.

In other features, the portions of the first metadata include portions of the second lookup table associated with the one of the plurality of WERUs. The recovery module updates the first lookup table based on the portions of the second lookup table and the activity log. The recovery module retrieves the portions of the second lookup table and the activity log from the second memory when the system powers up.

A method includes storing first metadata in a first memory to associate logical addresses with physical addresses, storing first data based on the physical addresses in a second memory that includes the physical address, storing portions of the first metadata in the second memory when a status of a predetermined group of the physical addresses is changed, and updating the first metadata based on the portions of the first metadata stored in the second memory.

In other features, the method further includes associating the logical address with the physical addresses using a first lookup table included in the first metadata. The method further includes associating the physical addresses with the logical addresses using a second lookup table included in the first metadata. The predetermined group of the physical addresses is a wide erase block unit (WERU). The first metadata includes identifiers for a plurality of WERUs, and the identifiers correspond to respective bins. The method further includes indicating when a first identifier for one of the plurality of WERUs is changed using an activity log included in the first metadata.

In other features, the method further includes storing the portions of the first metadata in the second memory when the first identifier is changed. The portions of the first metadata include portions of the second lookup table associated with the one of the plurality of WERUs. The method further includes updating the first lookup table based on the portions of the second lookup table and the activity log. The method further includes retrieving the portions of the second lookup table and the activity log from the second memory when the system powers up.

In still other features, the systems and methods described above are implemented by a computer program executed by one or more processors. The computer program can reside on a computer readable medium such as but not limited to memory, nonvolatile data storage, and/or other suitable tangible storage mediums.

DESCRIPTION

Referring now toFIG. 1, a computing device10includes a flash memory module12. The computing device10may include, but is not limited to, a computer, media player, mobile phone, personal digital assistant, or any other device that may include the flash memory module12. The flash memory module12may be a removable memory module such as a memory card or a USB flash drive.

The flash memory module12includes a processor module14, flash memory16, non-volatile memory18, and main memory20. The processor module14executes instructions of software and firmware of the flash memory module12. For example, the processor module14may execute instructions of firmware stored in the non-volatile memory18. The processor module14may also read and execute instructions stored in the main memory20. For example, the main memory20may include volatile memory such as random access memory (RAM).

The flash memory module12communicates with a host22of the computing device10. The host22communicates with input devices24and output devices26, and may communicate with secondary storage such as HDD28. The input devices24include, but are not limited to, a keyboard or keypad, a mouse, a touch screen, a touch pad, a microphone, and/or other input devices. The output devices26include, but are not limited to, a display, a speaker, and/or other output devices.

The computing device10stores data in the flash memory module12. The flash memory module12may emulate an HDD. For example, data is stored in the HDD28according to a logical block address (LBA), which corresponds to a physical block address (PBA) of the HDD28. Typically, an HDD LBA is 512 bytes. In other words, the host22references the data in the HDD28according to the LBA, while the HDD28references the data according to the PBA.

Conversely, data is stored in the flash memory module12(i.e. in the flash memory16) according to a logical allocation address (LAA), which corresponds to a physical allocation address (PAA) of the flash memory16. For example only, the LAA is 4096 bytes. A flash allocation unit (AU) corresponds to a read or write unit of the flash memory16and may be equivalent to one LAA. A wide erase block unit (WERU) is an erase operation unit and corresponds to multiple (e.g. 2048) PAAs.

When the computing device10writes data to an LAA, the flash memory module12(e.g. firmware of the flash memory module12) selects a corresponding PAA, which is referred to as “allocation.” For example, the processor module14processes commands according to firmware stored in the non-volatile memory18to read and write data to the flash memory16. The flash memory module12stores the data to the PAA of the flash memory16and stores metadata in the main memory20that indicates the relationship between the LAA and the corresponding PAA. For example, the metadata may include a lookup table (LUT) that associates LAAs with PAAs. The LUT associates each allocated LAA with a PAA. If a particular LAA is not allocated, the LAA may be associated with a recognizable invalid PAA value.

The metadata also includes WERU description data, including, but not limited to a PAA validity map, WERUs link information, and erase information. Each WERU includes an identifier that associates the WERU with a particular bin. For example, a WERU may be associated with a free bin, a valid bin, a partial bin, or a working bin. Free bins include WERUs whose PAAs are all ready to be written to. Valid bins include WERUs whose PAAS are all valid data. Partial bins include WERUs that include both PAAs with valid data and PAAs with invalid data (i.e. PAAs whose LAA data is subsequently written elsewhere). Working bins include WERUs that are currently being written to.

The metadata also includes data that corresponds to internal operations of the flash memory module12, which includes, for example only, wear leveling, cleanup, and static management data.

When the computing device10reads from an LAA, the lookup table stored in the main memory20indicates which PAA to read the data from and the flash memory module retrieves the data accordingly. Conversely, when the computing device10writes to a previously written LAA, the flash memory module12allocates an unused PAA to the LAA. The data is stored in the new PAA and the LUT is updated accordingly. Thus, the metadata stored in the main memory20enables allocation and retrieval of data from the proper PAAs in the flash memory16.

The metadata stored in the main memory20is updated as data is written to the flash memory module12. Before the computing device10(and therefore the flash memory module12) is powered down, the metadata is transferred from the main memory20to the flash memory16. When the computing device10is powered up, the metadata is transferred from the flash memory16to the main memory20to establish proper associations between the LAAs and the PAAs. For example, the metadata may be transferred to the main memory20during a power up procedure of the computing device10.

Any changes made to the metadata stored in the main memory20during operation of the computing device10after power up are not made to the flash memory module12until power down, or in response to internal metadata save commands that may be generated periodically by the firmware of the flash memory module12. When power is lost unexpectedly during operation of the computing device10, the changes made to the metadata stored in the main memory20may be lost. Accordingly, the metadata stored in the flash memory16is not updated (i.e. the metadata is old) and corresponds to a previous proper power down of the computing device10. At a subsequent power up, the old metadata is transferred from the flash memory16to the main memory20, leading to improper allocation and retrieval of the data in the flash memory16.

Referring now toFIG. 2, a metadata LUT100stored in the main memory20associates LAAs102with PAAs104of the flash memory module12. For example, when a read command requests data associated with LAA106, the data is actually retrieved from a corresponding PAA108. For example only, as shown inFIG. 2, solid blocks indicate the LAAs102that are associated with one of the PAAs104and empty blocks indicate the LAAs102that are not associated with one of the PAAs104. Similarly, with respect to the PAAs104, solid blocks indicate the PAAs104that store data and are allocated to one of the LAAs102. Empty blocks indicate the PAAs104that do not contain data.

For example, LAA106corresponds to PAA108. Accordingly, data requested from the LAA106will be retrieved from the PAA108. Similarly, data requested from LAA110will be retrieved from PAA112. Conversely, when data is to be written to an empty LAA114, a PAA (e.g. PAA116) that is empty or does not contain valid data is selected during allocation. Accordingly, the data written to the LAA114will actually be written to the PAA116or another one of the PAAs104in a working WERU.

For example only, each of WERUs A-G may include a group of three of the PAAs104. For example, the WERUs A and E are working WERUs (i.e. WERUs that are currently being written to). The WERUs B and D are partial WERUs. The WERU C is a valid WERU. The WERUs F and G are free WERUs.

When data is written to an LAA120that already is associated with a PAA122, a second PAA124is allocated to the LAA120. When data is again written to the LAA120, a third PAA126is allocated to the LAA120. In other words, the PAAs122and124store old or stale data previously associated with the LAA120and the PAA126stores new data.

LUT130represents, the lookup table stored in the flash memory16. The LUT130is transferred to the main memory20as the lookup table102during power up. Any changes made to the LUT102are not reflected in the LUT130stored in the flash memory16. For example, the LUT130may not indicate subsequent changes made to LAAs132and134.

As shown inFIG. 2, the metadata including the LUT100stored in the main memory20is updated as data is written to the PAAs104but is not updated in the flash memory16. For example, the metadata stored in the flash memory16is indicative of a status of the LUT100at a most recent power up of the computing device10. Accordingly, the metadata stored in the flash memory16may indicate that the LAA120is still associated with the PAA122.

If the computing device10loses power unexpectedly, the metadata stored in the main memory20is lost. At the next power up, the metadata stored in the flash memory16is transferred to the main memory20. Accordingly, requests to read data from one of the LAAs102that was written to before the loss of power will retrieve old data from one of the PAAS104. For example, for a request to read data from the LAA120, data will be retrieved from the PAA122instead of from the PAA126.

Referring now toFIG. 3, the metadata stored in the main memory20includes data that associates each WERU with a particular one of bins200. For example, the WERUs A and E are associated with a working bin202. The WERUs B and D are associated with a partial bin204. The WERU C is associated with a valid bin206. The WERUs F and G are associated with a free bin208.

The metadata stored in the main memory20includes a WERU activity log (WAL). The WAL indicates when a particular WERU changes status. For example, the WAL indicates when a WERU moves from one of the bins200to another of the bins200. For example, as data is written to the free WERU F, the free WERU F moves to the working bin202, and then to the partial bin204. When the WERU F is filled with valid data, the WERU F moves to the valid bin206.

Referring now toFIG. 4, the metadata stored in the main memory20includes a reverse lookup table (RLUT)300. The RLUT300associates PAAs302of the flash memory with LAAs304. A portion of the RLUT300is periodically stored in the flash memory16. For example, when a particular WERU moves from the working bin202to the valid bin206, a portion of the RLUT300corresponding to the WERU that moved to the working bin202is stored in the flash memory16. The most recent (i.e. correct) associations between the PAAs302and the LAAs304(and the LAAs102and the PAAs104as shown inFIG. 2) can be recovered after an unexpected power loss using the LUT100, the RLUT300, and the WAL.

For example only, as shown inFIG. 4, solid blocks indicate PAAs302that store data and are allocated to one of the LAAs304. Empty blocks indicate the PAAs302that do not contain data. With respect to the LAAs304, solid blocks indicate the LAAs304that are associated with one of the PAAs302and empty blocks indicate the LAAs304that are not associated with one of the PAAs302.

Referring now toFIG. 5, the processor module14includes a recovery module400. For example only, the recovery module400may include or execute firmware stored in non-volatile memory18. At power up, the computing device10transfers the metadata stored in the flash memory to the main memory20and the recovery module400determines whether to perform metadata recovery. For example, after a normal (i.e. scheduled or intentional) power down, the metadata may indicate that a user initiated a power down. If the metadata does not indicate that the user initiated a power down, the recovery module400may determine that an unexpected loss of power occurred and therefore perform the metadata recovery.

During metadata recovery, the recovery module400identifies WERUs that were written to and/or erased prior to the power loss based on the WAL. The WAL indicates when a particular WERU moves from one of the bins200to another of the bins200. The WAL includes a time (e.g. a timestamp) for each WERU that indicates when the WERU was written to or erased. Therefore, the WAL indicates which of the WERUs were written to (i.e. moved to the working bin202) and/or erased (i.e. moved to the free bin208).

The recovery module400updates the metadata stored in the main memory20based on the WAL and the RLUT300. For example, the recovery module400updates the WERU bins and the LUT100. The recovery module400moves each of the WERUs to the proper bin. In other words, if the metadata indicates that a WERU is in the free bin208and the WAL indicates that the WERU was written to and is filled with valid data, the recovery module400moves the WERU to the valid bin206. The recovery module400moves each WERU to an appropriate one of the bins200based on the WAL.

When the WERUs are in the proper bins, the recovery module400updates the LUT100based on the RLUT300. Beginning with the WERUs having the most recent activity (i.e. the WERUs that were most recently written to and/or erased based on the timestamp), the recovery module400performs reverse allocation for each of the WERUs.

Referring again toFIG. 4, only portions of the RLUT300corresponding to WERUs that moved from one bin to another are stored to the flash memory16. For example, no data was written to the WERUs F and G. Accordingly, the WERUs F and G remain associated with the free bin208and the portion of the RLUT300corresponding to the WERUs F and G are not written to the flash memory16. During metadata recovery, the recovery module400does not need to update the portions of the LUT100that correspond to the WERUs F and G.

Conversely, the WERUs A and D moved, for example, from the free bin208to the partial bin204and the RLUT300stored in the flash memory16is updated accordingly. Therefore, the data in the LUT100stored in the main memory20may not reflect changes made to the WERUs A and D before the unexpected power loss. For example, each of PAAs310,312, and314may be associated with a single LAA316.

During metadata recovery, the recovery module400identifies the WERUs A and D as WERUs that moved from one of the bins200to another based on the WAL. The recovery module400further determines that the most recent changes were made to the WERU A based on the WAL. Consequently, the recovery module400determines that the PAA310includes the newest data and is properly associated with the LAA316based on the WAL, the RLUT300, and reverse allocation. The recovery module400updates the LUT100with the proper association for each WERU.

In some circumstances, the recovery module400may be unable to determine which of the LAAs304that one of the PAAs302is associated with. Each of the PAAs in the flash memory16includes data that indicates which LAA that the PAA is associated with. The recovery module400may read the data stored in the PAA to determine the proper LAA association.

The recovery module400also updates WERU description data including, but not limited to, a WERU validity map, link information, and erase information (e.g. a number of times each WERU is erased). The WERU description data may include an allocation map that indicates each time a PAA is read for WERUs in the working bin202.

Referring now toFIG. 6, a metadata recovery method500is shown. At502, the computing device10is powered on. At504, the recovery module400transfers the metadata from the flash memory16to the main memory20. At506, the recovery module400determines whether the computing device10was properly powered down. If true, the method500continues to508. If false, the method500continues to510. At508the computing device10proceeds to normal operation without performing metadata recovery.

At510, the recovery module400moves each WERU to the proper bin based on the WAL. At512, the recovery module400updates the LUT100based on the WAL and the RLUT300. At514, the recovery module400updates the LUT100based on LAA association data stored in any remaining PAAs. At516, the recovery module400updates WERU description data and the computing device10proceeds to normal operation.

The broad teachings of the disclosure can be implemented in a variety of forms. Therefore, while this disclosure includes particular examples, the true scope of the disclosure should not be so limited since other modifications will become apparent upon a study of the drawings, the specification, and the following claims.