Method and non-volatile memory device for improving latency together with write protection

A data storage device includes a write protection data structure that includes a first set of entries corresponding to a first set of ranges of memory addresses. A first indication stored in an entry, in the first set of entries, corresponds to an absence of write-protected data between a lowest address of the range of addresses corresponding to the entry and a highest address of a memory. A second indication stored in the entry corresponds to write-protected data within the range of addresses. The data storage device also includes a write protection map that includes a second set of entries corresponding to a second set of ranges of the memory addresses. The device is configured to locate, in the write protection data structure, an entry corresponding to a range of memory addresses.

FIELD OF THE DISCLOSURE

The present disclosure is generally related to write protection in memory devices.

BACKGROUND

Non-volatile data storage devices, such as universal serial bus (USB) flash memory devices or removable storage cards, have allowed for increased portability of data and software applications. Such devices may enable data to be stored by a host device and later retrieved from a memory in the data storage device. For example, a host device may send a write command to a data storage device and specify a memory address. The data storage device may store data to a memory location indicated by the memory address.

When a write command is received from a host device, the data storage device may be responsible for ensuring that write-protected data stored in the memory is not overwritten by the host device. The data storage device may maintain a write protection map that identifies whether write protection is enabled for each memory address that maps to a location in the memory. For example, a write protection map may have a write protection indicator for each group of memory addresses, such as sector-sized groups (e.g., 512 bytes), page-sized groups (e.g., 2 kilobytes), or other-sized groups of memory addresses. Starting at the address provided by the host device, the data storage device may “walk” through the write protection map, in response to receiving a write command, to identify a total amount of sequentially addressed space that is not write-protected to determine a largest amount of data that may be stored in response to the write command.

However, because memory capacity increases with advances in storage technologies, a size of the write protection map may also increase. An amount of time expended walking through the write protection map creates write latency experienced by the host device. For example, when a first address following the write address is write protected, the write protection map search may be completed in a few microseconds. However, when the write address is near a beginning of an address space and a first address of write protected data is near an end of the address space, the write protection map search may take tens of microseconds to complete.

SUMMARY

A data storage device includes a write protection data structure that includes a first set of entries corresponding to a first set of ranges of memory addresses. Each entry includes a memory address of write-protected data, a first indication, or a second indication. The first indication corresponds to an absence of write-protected data between a lowest address of the range of addresses and a highest address of a memory. The second indication corresponds to write-protected data within the range of addresses. Write protection information may be retrieved by accessing the write protection data structure and may reduce or eliminate latency associated with searching a write protection map.

DETAILED DESCRIPTION

Referring toFIG. 1, a particular embodiment of a system100includes a data storage device102coupled to a host device130. The data storage device102is configured to maintain a write protection data structure170that enables faster access to identify non-protected areas of a memory104, as compared to searching a write protection map160.

The host device130may be configured to provide data, such as the user data132, to be stored at the memory104or to request data to be read from the memory104. For example, the host device130may include a mobile telephone, a music player, a video player, a gaming console, an electronic book reader, a personal digital assistant (PDA), a computer, such as a laptop computer or notebook computer, any other electronic device, or any combination thereof. The host device130communicates via a memory interface that enables reading from the memory104and writing to the memory104. For example, the host device130may operate in compliance with a Joint Electron Devices Engineering Council (JEDEC) industry specification, such as a Universal Flash Storage (UFS) Host Controller Interface specification. As other examples, the host device130may operate in compliance with one or more other specifications, such as a Secure Digital (SD) Host Controller specification as an illustrative example. The host device130may communicate with the memory104in accordance with any other suitable communication protocol.

The data storage device102includes the memory104on a memory die103that is coupled to a controller120on a controller die121. The memory104is a non-volatile memory, such as a NAND flash memory. The memory104may include groups of storage elements, such as a word line of a multi-level cell (MLC) flash memory. For example, the data storage device102may be a memory card, such as a Secure Digital SD® card, a microSD® card, a miniSD™ card (trademarks of SD-3C LLC, Wilmington, Del.), a MultiMediaCard™ (MMC™) card (trademark of JEDEC Solid State Technology Association, Arlington, Va.), or a CompactFlash® (CF) card (trademark of SanDisk Corporation, Milpitas, Calif.). As another example, the data storage device102may be configured to be coupled to the host device130as embedded memory, such as eMMC® (trademark of JEDEC Solid State Technology Association, Arlington, Va.) and eSD, as illustrative examples. To illustrate, the data storage device102may correspond to an eMMC (embedded MultiMedia Card) device. The data storage device102may operate in compliance with a JEDEC industry specification. For example, the data storage device102may operate in compliance with a JEDEC eMMC specification, a JEDEC Universal Flash Storage (UFS) specification, one or more other specifications, or a combination thereof.

The memory104may include a system data portion106and a user data portion108. The system data portion106may include one or more sets of data that may be used by the controller120or the host device130to store information. For example, the system data portion106may include file and directory information, such as file management tables for a file system that may be used by the host device130and/or by the controller120. The system data portion106includes a write protection map160and a write protection data structure170. The user data portion108is configured to store user data, such as in response to requests for write access from the host device130. Portions of the user data portion108may be configured to be write protected or non-write protected. For example, the user data portion108may store write-protected data110. The write protected data110may correspond to data that has been stored in the memory104and that is not permitted to be overwritten or erased. The write protection map160includes a mapping of addresses to data stored in the memory104and an indication of whether or not addresses (or ranges of addresses) correspond to write protected regions or non-write protected regions of the memory104.

The controller120is configured to receive data and instructions from and to send data to the host device130while the data storage device102is operatively coupled to the host device130. For example, the controller120is configured to send data and a write command to instruct the memory104to store the data to a memory location that is identified by a specified address. As another example, the controller120is configured to send a read command to read data from a memory location that is identified by a specified address.

The controller120includes a write-protected data locator150, a copy of the write protection map160, and a copy of the write protection data structure170. For example, the write protection map160may be read from the system data portion106of the memory104upon initialization of the controller120and stored in controller memory (e.g., a random access memory (RAM) embedded within or coupled to the controller die121). The write protection data structure170may be read from the memory104upon initialization of the controller120and stored into a controller memory. However, in other implementations, the write protection data structure170may not be stored in the memory104and may instead be generated by the controller120and populated based on information in the write protection map160.

The write protection data structure170includes a set of entries172corresponding to a set of ranges174of memory addresses. Each entry of the set of entries172includes a value, illustrated as a first value in a first entry, a second value in a second entry, to an Nth value in an Nth entry. Each value may correspond to a first indication, a second indication, or a memory address. As explained in further detail with respect toFIG. 2, the first indication may correspond to an absence of write protected data between the lowest address of a range of addresses corresponding to the entry and the highest address of the memory104. As used herein, comparisons between memory addresses are described with respect to numerical values of the addresses, so that an address with a larger numerical value is “greater” or “higher” than an address with a smaller numerical value. The second indication may correspond to write protected data being within the range of addresses corresponding to the entry. A memory address stored in an entry indicates an address of write protected data that is stored in the memory104.

The write protection data structure170may be formed according to a table format and may be indexed by the write protected data locator150using an index122. For example, the index122may be formed according to a set of most significant bits of the write address133. To illustrate, when each of the ranges of the set of ranges174corresponds to a one gigabyte range, a low order (i.e., least significant) 30 bits of the write address133may be ignored, and higher order bits (e.g., the 3 most significant bits of a 33-bit address corresponding to an 8 gigabyte address range) of the write address133may be used to form the index122to select a particular entry of the write protection data structure170. In response to providing the index122to the write protection data structure170, a corresponding value124may be read from the indexed entry and received at the write protected data locator150. The value124may include a first indication154, a second indication156, or a memory address.

The write protected data locator150may be configured to receive the value124from the write protection data structure170and to perform one or more comparisons at a comparator152. To illustrate, the comparator152may compare the value124to the first indication154to determine whether the value124matches the first indication154. The comparator152may be configured to compare the value124to the second indication156to determine whether the value124matches the second indication156. The indications154,156may be bit patterns that may be stored at the controller120, such as in a read-only memory. In response to the value124matching the first indication154, the write protected data locator150may determine that no write protected data exists between the address specified in the write address133and a highest address of the memory104. In response to the comparator152determining that the value124matches the second indication156, the write protected data locator150may determine that write protected data exists within the range of addresses corresponding to the index122. In response to the value124not matching the first indication154and also not matching the second indication156, the write protected data locator150may determine that the value124corresponds to a memory address of write-protected data in the memory104that has a lowest address (that is greater than the write address133) of any other write-protected data in the memory104.

When the value124matches the first indication154or is a memory address, the write protected data locator150does not search the write protection map160. However, in response to determining that the value124matches the second indication156, the write protected data locator150may be configured to initiate a map search126of the write protection map160. To illustrate, upon determining that the value124matches the second indication156, the write protected data locator150may be configured to search the write protection map160in a range from the write address133to a highest address within the range corresponding to the index122because at least one memory address within the range corresponds to write protected data. The map search126may be performed by the write protected data locator150reading a data value from a map entry of the write protection map160that corresponds to a group of addresses that includes the write address133. The write protected data locator150may compare the value read from the write protection map160to a write protected indicator to determine whether the map entry includes an indication of write protection. In response to determining that the map entry does not store the indication of write protection for the write address133, the write protected data locator150may increment an index into the write protection map160to identify a next sequential entry corresponding to a next sequential range of addresses in the write protection map160and may determine whether the identified entry includes an indication of write protection. In this manner, the write protected data locator150may repeatedly increment an index to the write protection map160and evaluate a value stored at an entry corresponding to the incremented index until an indication of write protection is determined. Upon determination of the indication of write protection, a memory address128corresponding to the entry indicating write protection may be returned by the write protection map160or otherwise identified by the write protected data locator150.

During operation, the controller120may receive the write request132from the host device130as a request for write access to the memory104. The write request132may include the write address133or may otherwise provide an indication to enable the controller120to determine the write address133(e.g., by incrementing a previously received write address). In response to determining that the received request is a request for write access and determining the write address133, the controller120may be configured to determine a range of non-protected memory addresses by locating a next address following the write address133that is non-writable, such as due to storing write protected data or due to being a highest address of the memory104. The write protected data locator150may generate the index122from a set of most significant bits of the write address133and may provide the index122to the write protection data structure170. In response to reading the write protection data structure170using the index122, the write protected data locator150receives the value124corresponding to the index122and may perform one or more comparisons at the comparator152.

The write protected data locator150may compare the first indication154to the value124to determine whether the value124matches the first indication154. For example, the comparator152may be configured to compare bits of the value124to stored bits of the first indication154. As another example, the first indication154may correspond to an all-zeroes value, and the comparator152may be configured to perform a bitwise OR operation on the value124to compare the value to the first indication154. The write protected data locator150may compare the second indication156to the value124to determine whether the value124matches the second indication156. For example, the comparator152may be configured to compare bits of the value124to stored bits of the second indication156. As another example, the second indication156may be an all-ones value, and the comparator152may be configured to perform a bitwise AND operation on the value124to compare the value124to the second indication156. In response to determining that the value124matches the first indication154, the write protected data locator150may determine that no write protected data regions exist in the memory104with an address higher than the write address133. In response to determining that the value124does not match the first indication154and does not match the second indication156, the write protected data locator150may generate an indication that the value124is a memory address of a closest memory address that is greater than the write address133and that stores write protected data.

However, when the value124is determined to match the second indication156, the write protected data locator150may initiate the map search126to sequentially search consecutive entries of the write protection map160, starting with the entry corresponding to the write address133, to identify a first entry in the write protection map160that corresponds to an address larger than the write address133and that indicates write-protected data. The map search126may determine the write protection memory address128that represents a first non-writable memory address that is larger than the write address133and that may limit the amount of data that may be written in response to the write request132.

By first accessing the write protection data structure170and determining whether the value124indicates the first indication154or an address, in certain scenarios, the map search126may be avoided. For example, the write protection data structure170may include a relatively small number of entries172as compared to a number of map entries in the write protection map160. To illustrate, the write protection data structure170may have eight entries, such as described with respect toFIG. 2, while the write protection map160may include thousands of entries. As a result, a latency of writing data corresponding to the write request132may be reduced by reducing or eliminating a search of the write protection map160that would otherwise be performed to determine an upper boundary of memory addresses that are accessible for writing data beginning with the write address133, such as described in further detail with respect toFIG. 2.

Referring toFIG. 2, further detail of a particular embodiment of the write protection data structure170and the write protection map160is shown. The write protection data structure170is illustrated as including eight entries202-216for an 8 gigabyte implementation of the memory104, with each of the entries202-216corresponding to a 1 gigabyte range of addresses. For example, the first entry202corresponds to a 1 gigabyte range of addresses beginning with memory address 0, and the second entry204corresponds to a next consecutive 1 gigabyte range of addresses. As illustrated, the first entry202corresponds to a range of addresses matching the first row of the write protection map160. The first row of the write protection map160includes three entries, such as a map entry222, that correspond to write protection regions and that are illustrated as hatched entries. The first row of the write protection map160also includes multiple other entries that correspond to non-write protection regions and that are illustrated as non-hatched entries. The first entry202of the write protection data structure170stores the second indication156which may be set to an all-ones value (“0xFFFFFFFF” in hexadecimal notation). The first entry202includes the second indication156because one or more write protection regions are identified within the corresponding range of addresses of the write protection map160(e.g., within a 1 gigabyte range of addresses starting at address 0).

The second entry204of the protection data structure170corresponds to a range of addresses that, as illustrated in the write protection map160, do not include any write protected data (i.e., no hatched entries are in the second row of the write protection map160). However, the write protection map160illustrates that one or more additional write protected data areas exist at memory addresses higher than the second range corresponding to the second entry204. For example, a next write protected region occurs at an address range corresponding to a map entry224. As a result, the second entry204includes an address “A” having a value corresponding to an address of the write protected data area indicated by the map entry224, illustrated as “0x00210000”.

The third entry206of the write protection data structure170corresponds to a range of memory addresses that includes one or more write protected regions (e.g., corresponding to the map entry224), and therefore the third entry206stores the second indication156.

The fourth entry208of the write protection data structure170corresponds to a range of addresses that does not include memory addresses of write protected data. A next lowest memory address of write protected data occurs at an address corresponding to a region indicated by a map entry226of the write protection map160. As a result, the fourth entry208of the write protection data structure170stores an address “B” (illustrated as “0x00A20000”) of the write protected data corresponding to the map entry226. The fifth entry210of the write protection data structure170also corresponds to a range of memory addresses that do not correspond to write protected data. Therefore, the value stored in the fifth entry210of the write protection data structure170also corresponds to the next lowest address of write protected data, address B.

The sixth entry212of the write protection data structure170corresponds to a range of memory addresses that includes address B. As a result, the sixth entry212includes the second indication156(e.g., the all-ones value). The seventh entry214and the eighth entry216of the write protection data structure170each map to a respective range of addresses that do not correspond to write protected data. Further, no write protected data exists in addresses between the range of addresses of the seventh and eighth entries214,216and the highest address of the memory104. As a result, the seventh entry214and the eighth entry216each stores the first indication154(e.g., the all-zeroes value).

The controller120ofFIG. 1may be configured to generate the write protection data structure170upon initialization by accessing the write protection map160and by walking sequentially through entries of the write protection map160to determine whether write protected data is stored at memory addresses corresponding to each of the entries202-216of the write protection data structure170. As a result, the controller120may traverse the entire write protection map160a single time upon initialization to generate the write protection data structure170. After generating the write protection data structure170, the controller120may be configured to determine an address of write protected data either by performing a single access to the write protection data structure170or by performing the single access to the write protection data structure170and performing an abbreviated search of the write protection map160. The abbreviated search may be constrained to be within an address range that corresponds to an address range of the entry that is read from the write protection data structure170.

For example, if the write address133ofFIG. 1corresponds to a first address in the range of memory addresses corresponding to the third entry206(e.g., the memory address from 2 GB to 3 GB), the value124returned to the write protected data locator150may be the second indication156(as inFIG. 2). The write protected data locator150may determine, by accessing the write protection data structure170, that one or more write protected data addresses exist within the 1 gigabyte range of addresses corresponding to the third entry206. Thus, the write protected data locator150may initiate a map search to sequentially access each of the map entries beginning with the write address133and continuing along the third row (as illustrated inFIG. 2) of the write protection map160to find an address of write protected data, illustrated as the map entry224of the write protection map160. The search of the write protection map160ends when an address of write protected data is found. If the search of the write protection map160reaches the largest memory address corresponding to the third entry206without locating an address of write protected data, then the next entry208of the write protection data structure170is accessed to identify a next address of write protected data (address B). Therefore, a longest search of the write protection map160that may be conducted by the write protected data locator150in response to a write request is a search of entries corresponding to address regions that, when combined, span a range of memory addresses corresponding to two entries of the write protection data structure170.

The controller120ofFIG. 1may further be configured to update the entries of the write protection data structure170in response to a command from the host device130. For example, in response to the host device130instructing the controller120to set a particular memory address as a write protected memory address, the controller120may update the write protection map160to indicate the change in write protection for the particular memory address and may further update one or more of the entries of the write protection data structure170based on the change in write protection.

FIG. 3illustrates an example300of operations that may be performed at the host device130and operations that may be performed at the data storage device102ofFIG. 1. For example, the data storage device102may correspond to an eMMC (embedded MultiMedia Card) device and may operate in compliance with a Joint Electron Devices Engineering Council (JEDEC) industry specification, such as an eMMC specification or a Universal Flash Storage (UFS) specification. The host device130may send a set write protection (SetWP) command302to the data storage device102while the host device130is operatively coupled to the data storage device102. For example, the SetWP command302may correspond to a set write protection command or a clear write protection command. The Set WP command302may indicate whether write protection is to be set or to be cleared and may indicate a memory address, or a range of memory addresses, to which the write protection is to be applied. The data storage device102may receive the set write protection command302and in response may perform a map update operation304to update the write protection map160. Updating the write protection map160may include locating a map entry in the write protection map160corresponding to the memory address indicated by the set write protection command302and modifying a value in the located map entry. After updating the write protection map, the data storage device102may perform an update write protection data structure operation306. The update write protection data structure operation306may include modifying one or more entries of the write protection data structure170to indicate whether the designated write address or range of write addresses correspond to write protected data.

The host device130may further be configured to send a write command320, such as the request for write access132ofFIG. 1, to the data storage device102while the host device130is operatively coupled to the data storage device102. In response to receiving the write command320, the data storage device102may perform a next write protection check operation322. For example, the next write protection check operation322may include accessing the write protection data structure170and receiving the returned value124. In response to the returned value124matching the first indication154, the next write protection check operation322may return a value indicating that no write protected data is stored at addresses higher than the write address. In response to the returned value124matching a memory address, the next write protection check operation322may return the memory address. In response to the returned value124matching the second indication156, the next write protection check operation322may include performing the abbreviated map search126to identify a next write protection address. The next write protection check operation322may return the identified next write protection address.

Referring toFIG. 4, a particular embodiment of a method400is depicted. The method400may be performed in a data storage device, such as the data storage device102ofFIG. 1, that includes a controller and a non-volatile memory and that contains a write protection data structure and a write protection map that are accessible to the controller. The method400may be performed in response to receiving a request for write access to the non-volatile memory. The request (e.g., the write request132ofFIG. 1) may be received from a host device while the data storage device is operatively coupled to the host device.

The method400includes locating, in the write protection data structure, an entry corresponding to a range of memory addresses in response to the range of memory addresses including a first address received with the request, at402. For example, the write protection data structure170may include a table of entries, and locating the entry in the write protection data structure may include using a set of most significant bits of the first address as an index to the table. The entry may correspond to the index, such as the index122ofFIG. 1that corresponds to a set of most significant bits of the write address133.

A determination is made whether the entry includes a second memory address of write-protected data, a first indication, or a second indication, at404. The first indication, such as the first indication154, corresponds to an absence of write-protected data between a lowest address of the range of addresses and a highest address of the non-volatile memory. The second indication, such as the second indication156, corresponds to an indication that write-protected data is within the range of addresses.

In response to the entry including the second indication, the write protection map is accessed to locate a lowest address in the range that is greater than the first address and that stores write-protected data, at406. For example, accessing the write protection map to locate the lowest address in the range that is greater than the first address and that stores write-protected data may correspond to the abbreviated search126ofFIG. 1and may include accessing a first map entry (corresponding to the first address) of the write protection map160ofFIG. 1and reading the first map entry to determine whether the first map entry includes a write-protection indicator. In response to the first map entry not including the write-protection indicator, one or more other map entries may be accessed according to sequential order of the one or more other map entries until an accessed map entry includes the write-protection indicator (e.g., map entry224) or corresponds to a highest address of the range of addresses.

Determining whether the entry includes the second memory address, the first indication, or the second indication enables the controller to determine, without the controller accessing the write protection map, a highest address of writable memory that may be accessed via the request in response to the entry including the second memory address or the first indication. For example, determining whether the entry includes the second memory address of write-protected data, the first indication, or the second indication may include reading a value, such as the value124ofFIG. 1that corresponds to the entry. The value may be compared to the first indication to determine whether the value matches the first indication and may be compared to the second indication to determine whether the value matches the second indication. In response to the value not matching the first indication and not matching the second indication, a determination may be made that the entry includes the second address. For example, the first indication may be an all-zeros value and a bitwise OR operation may be performed on the value to compare the value to the first indication, and the second indication may be an all-ones value and a bitwise AND operation may be performed on the value to compare the value to the second indication.

Because each entry in the write protection data structure may correspond to a larger range of memory addresses than each map entry in the write protection map, a fewer number of accesses may be performed to determine a non-protected area of memory by locating a nearest write-protected region of memory in the write protection data structure. As described with respect toFIGS. 1 and 2, when an entry includes the first indication154or an address, accessing the write protection map160(and the latency of performing a search of the write protection map160) may be avoided. Otherwise, when an entry includes the second indication156, the map search126may be performed over a subset of the write protection map160. As described with respect toFIG. 2, the map search126may terminate upon reaching an end of an address range corresponding to the entry, which may result in reduced latency as compared to continuing the search until a next write protection address, or an end of memory addresses, is reached.

Although various components depicted herein are illustrated as block components and described in general terms, such components may include one or more microprocessors, state machines, or other circuits configured to enable the write-protected data locator150ofFIG. 1to access the write protection data structure170to locate an address of write-protected data. For example, the write-protected data locator150may represent physical components, such as hardware controllers, state machines, logic circuits, or other structures, to enable the write-protected data locator150ofFIG. 1to generate the index122from the write address133, to read the value124corresponding to the index122, and to selectively perform the map search126based on a comparison of the value124to the first indication154and/or to the second indication156.

The write-protected data locator150may be implemented using a microprocessor or microcontroller programmed to generate the index122from the write address133, read the value124corresponding to the index122, compare the value124to the first indication154and/or to the second indication156, and selectively perform the map search126in response to the value124matching the second indication156. In a particular embodiment, the write-protected data locator150includes a processor executing instructions that are stored at the memory104. Alternatively, or in addition, executable instructions that are executed by the processor may be stored at a separate memory location that is not part of the memory104, such as at a read-only memory (ROM).

In a particular embodiment, the data storage device102may be implemented in a portable device configured to be selectively coupled to one or more external devices. However, in other embodiments, the data storage device102may be attached or embedded within one or more host devices, such as within a housing of a host communication device. For example, the data storage device102may be within a packaged apparatus such as a wireless telephone, a personal digital assistant (PDA), a gaming device or console, a portable navigation device, or other device that uses internal non-volatile memory. In a particular embodiment, the data storage device102may be coupled to a non-volatile memory, such as a three-dimensional (3D) memory, a flash memory (e.g., NAND, NOR, Multi-Level Cell (MLC), a Divided bit-line NOR (DINOR) memory, an AND memory, a high capacitive coupling ratio (HiCR), asymmetrical contactless transistor (ACT), or other flash memories), an erasable programmable read-only memory (EPROM), an electrically-erasable programmable read-only memory (EEPROM), a read-only memory (ROM), a one-time programmable memory (OTP), or any other type of memory.

The illustrations of the embodiments described herein are intended to provide a general understanding of the various embodiments. Other embodiments may be utilized and derived from the disclosure, such that structural and logical substitutions and changes may be made without departing from the scope of the disclosure. This disclosure is intended to cover any and all subsequent adaptations or variations of various embodiments.