Patent Description:
Memory devices are typically provided as internal, semiconductor, integrated circuits and/or external removable devices in computers or other electronic devices. There are many different types of memory including volatile and non-volatile memory. Volatile memory can require power to maintain its data and can include random-access memory (RAM), dynamic random access memory (DRAM), and synchronous dynamic random access memory (SDRAM), among others. Non-volatile memory can retain stored data when not powered and can include NAND flash memory, NOR flash memory, phase change random access memory (PCRAM), resistive random access memory (RRAM), and magnetic random access memory (MRAM), among others.

Memory devices can be combined together to form a solid state drive (SSD). An SSD can include non-volatile memory (e.g., NAND flash memory and/or NOR flash memory), and/or can include volatile memory (e.g., DRAM and/or SRAM), among various other types of non-volatile and volatile memory. An SSD can be used to replace hard disk drives as the main storage volume for a computer, as the solid state drive can have advantages over hard drives in terms of performance, size, weight, ruggedness, operating temperature range, and power consumption. For example, SSDs can have superior performance when compared to magnetic disk drives due to their lack of moving parts, which may avoid seek time, latency, and other electro-mechanical delays associated with magnetic disk drives.

In various instances, it can be beneficial and/or desirable to erase data stored in memory (e.g., to delete files or portions thereof that may contain sensitive and/or private information). Some deletion mechanisms may not involve actual physical erasure of the data such that it is possible for the data to be recovered from the memory. For instance, a deletion mechanism might involve physical erasure of memory locations currently storing a particular file, but memory locations which may have previously stored the particular file, or portions thereof, may not be physically erased. Other deletion mechanisms might involve physical erasure of all data stored in memory, which ensures deletion of data targeted for deletion, but also erases data that may not be targeted for deletion.

<CIT> describes a file system for effectively using a flash memory including a meta block, a data block and an info block. <CIT> describes a method of formatting a data storage device and garbage collection for failure prediction and repartitioning. <CIT> describes a random access memory assembly which is a key component of an object space manager which in turn is a key circuit in a garbage-collecting control unit for a computer system. D5= <CIT> discloses a data sanitize command issued by a host to a data storage device along with the designation of a selected range of logical block addresses to be removed.

In a first aspect of the invention there is provided a method according to independent claim <NUM>. In a second aspect of the invention there is provided an apparatus according to independent claim <NUM>. Further optional features of the invention are defined in the dependent claims. Embodiments in the following description that do not fall in the scope of the independent claims are not according to the invention, but provide helpful context or highlight specific features of the invention.

The present disclosure includes apparatuses and methods for directed sanitization associated with memory. One example method comprises, responsive to receiving a sanitization command, performing a deterministic garbage collection operation on a memory, wherein performing the deterministic garbage collection operation results in physical erasure of all invalid data stored on the memory without losing valid data stored on the memory.

Embodiments of the present disclosure can provide various benefits such as providing for secure erasure (e.g., of data targeted by the host for deletion) in a deterministic manner. For instance, a number of embodiments of the present disclosure provide a mechanism for host-initiated secure erasure of data corresponding to specific logical block addresses (LBAs) as well as previous copies of the data that might reside in memory. A number of embodiments can implement secure erasure using a deterministic garbage collection operation, as opposed to a typical garbage collection operation that might be associated with wear leveling operations performed in the background. Such background garbage collection is often non-deterministic in that it is often not initiated by a host and is not performed on demand but rather at some non-deterministic time in the future (e.g., as directed by a controller, such as an SSD controller, in association with wear leveling).

A number of embodiments provide directed sanitization that ensures that all copies (e.g., current and past) of data corresponding to a particular file, for example, are physically erased from memory, as opposed to being only logically erased (e.g., marked as invalid while still being physically stored in memory). The directed sanitization (e.g., secure erasure) can be performed using a deterministic garbage collection operation, which can provide a guaranty that no valid data (e.g., "live" data being tracked by a host) is erased.

In the following detailed description of the present disclosure, reference is made to the accompanying drawings that form a part hereof, and in which is shown by way of illustration how one or more embodiments of the disclosure may be practiced. These embodiments are described in sufficient detail to enable those of ordinary skill in the art to practice the embodiments of this disclosure, and it is to be understood that other embodiments may be utilized and that process, electrical, and/or structural changes may be made without departing from the scope of the present disclosure. As used herein, the designators "N," "B," "R," and "S", particularly with respect to reference numerals in the drawings, indicate that a number of the particular feature so designated can be included. As used herein, "a number of" a particular thing can refer to one or more of such things (e.g., a number of blocks can refer to one or more blocks).

As will be appreciated, elements shown in the various embodiments herein can be added, exchanged, and/or eliminated so as to provide a number of additional embodiments of the present disclosure. In addition, as will be appreciated, the proportion and the relative scale of the elements provided in the figures are intended to illustrate certain embodiments of the present invention, and should not be taken in a limiting sense.

<FIG> is a block diagram of an apparatus in the form of a computing system <NUM> including a memory system <NUM> comprising a controller <NUM> configured to perform directed sanitization in accordance with a number of embodiments of the present disclosure. As used herein, a memory system <NUM>, a controller <NUM>, or a memory <NUM> might also be separately considered an "apparatus. " The memory system <NUM> is a solid state drive (SSD), and does include a host interface <NUM>, a controller <NUM> (e.g., a sequencer and/or other control circuitry), and a memory <NUM>. Although not shown in <FIG>, the memory <NUM> comprises a number of solid state memory devices, such as NAND flash devices, which provide a storage volume for the memory system <NUM>.

The controller <NUM> can be coupled to the host interface <NUM> and to the memory <NUM> via a plurality of channels and is used to transfer data between the memory <NUM> and a host <NUM>. The interface <NUM> can be in the form of a standardized interface. For example, when the memory system <NUM> is used for data storage in a computing system <NUM>, the interface <NUM> is a serial advanced technology attachment (SATA), peripheral component interconnect express (PCIe), or a universal serial bus (USB), among other connectors and interfaces. In general, however, interface <NUM> can provide an interface for passing control, address, data, and other signals between the memory system <NUM> and a host <NUM> having compatible receptors for the interface <NUM>.

A host <NUM> can be a host system such as a personal laptop computer, a desktop computer, a digital camera, a mobile telephone, or a memory card reader, among various other types of hosts. The host <NUM> can include a system motherboard and/or backplane and can include a number of memory access devices (e.g., a number of processors). The host <NUM> can also be a controller, such as where the memory system <NUM> is a memory device having an on-die controller. The host <NUM> can be configured to provide various commands to the memory system <NUM> (e.g., to the controller <NUM>) to direct the memory system <NUM> to perform various operations in accordance with the received command. For example, the host <NUM> can be configured to provide a sanitization command to the controller <NUM> such that the controller <NUM> initiates a deterministic garbage collection operation responsive to receiving the sanitization command, as further described herein, In a number of embodiments, the sanitization command can be sent as an interrupt signal such that, for instance, the controller <NUM> performs the deterministic garbage collection operation "on demand" upon receiving the command. For example, upon receiving the sanitization command, the controller <NUM> can suspend its current activities, save its state, and perform the deterministic garbage collection operation.

The host <NUM> can include a trimming queue <NUM> (TRIM QUEUE), which can be used in association with an operating system (OS) trimming feature. The trimming queue <NUM> can be configured to store logical block addresses (LBAs) corresponding to data no longer in use and/or being tracked by host <NUM>, for example, such that the data may be marked as invalid and erased from memory <NUM>. The LBAs in the trimming queue <NUM> can be sent to the controller <NUM> in association with a trimming command. As used herein, a trimming command can be a TRIM command, UNMAP command, or DEALLOCATE command, among other commands, which can depend on a particular interface type and/or protocol (e.g., ATA, SCSI, etc.). As described further herein, in a number of embodiments, the host <NUM><NUM> can initiate a forced flush of the trimming queue in association with providing a host-initiated sanitization command to the controller <NUM>, which can initiate a deterministic garbage collection operation that results in secure erasure of at least the data corresponding to the LBA list provided from the trimming queue <NUM>.

The controller <NUM> can control performance of various operations (read, write, erase, etc.) on the memory <NUM>, which can comprise a number of memory dies (e.g., NAND dies), for example. The controller <NUM> can be on a same die or a different die than memory <NUM>. Although not specifically illustrated, the controller <NUM> can include a discrete memory channel controller for each channel coupling the controller <NUM> to the memory <NUM>. The controller <NUM> can include, for example, a number of components in the form of hardware and/or firmware (e.g., one or more integrated circuits) and/or software for controlling access to the memory <NUM> and/or for facilitating data transfer between the host <NUM> and memory <NUM>.

As illustrated in <FIG>, the controller <NUM> can include a wear-leveling component <NUM>, a garbage collection component <NUM>, and a mapping component <NUM>. The wear-leveling component <NUM> can include, for example, circuitry configured to reduce the number of process cycles (e.g., program and/or erase cycles) performed on a particular group of cells (e.g., block) by spreading the cycles more evenly over an entire array and/or device. The wear leveling component <NUM> can be configured to perform dynamic wear leveling, which can include garbage collection performed via garbage collection component <NUM>. Garbage collection can include reclaiming (e.g., erasing and making available for programming) blocks that have the most invalid pages (e.g., according to a "greedy algorithm"). Alternatively, garbage collection can include reclaiming blocks with more than a threshold amount (e.g., quantity) of invalid pages. If sufficient free blocks exist for a programming operation, then a garbage collection operation may not occur. An invalid page, for example, can refer to a page whose corresponding logical to physical address mapping has been updated (e.g., such that the data corresponding to the previous mapping is stale). Component <NUM> can also perform static wear leveling, which can include writing static data to blocks that have high program/erase counts to prolong the life of the block.

In a number of unclaimed embodiments, in the absence of a sanitization command from host <NUM>, the garbage collection component <NUM> can be configured to perform garbage collection on memory <NUM> as a background operation. For example, performing garbage collection during idle time (e.g., when controller <NUM> is not executing host commands), can prevent such operations from negatively effecting latency. As described further herein, in a number of embodiments, the component <NUM> is configured to, responsive to a sanitization command, perform a deterministic garbage collection operation. For instance, responsive to controller <NUM> receiving the sanitization command, the component <NUM> can identify those blocks containing invalid data (e.g., invalid pages), relocate valid data (e.g., valid pages) contained in those blocks to different blocks, and physically erase the identified blocks to result in physical erasure of invalid data without losing the valid data stored on the memory <NUM>. In a number of embodiments, performing a deterministic garbage collection operation includes performing a complete garbage collection operation, which can refer to a garbage collection operation that is executed until no blocks of the memory (e.g., <NUM>) contain both valid pages and invalid pages (e.g., all the physical blocks have either been physically erased or contain only valid data).

The mapping component <NUM> does include a logical to physical address map (e.g., table) as well as indicators regarding page status (e.g., valid, invalid, erased, etc.). The address map and/or page status can be updated in various manners. For example, the mapping can be updated by controller <NUM> as valid data is relocated as part of garbage collection and/or wear leveling. Additionally, the address mapping and/or page status can be updated based on trimming commands from host <NUM> (e.g., responsive to a flushing of trimming queue <NUM>).

The components <NUM>, <NUM>, <NUM> can be discrete components such as an application specific integrated circuit (ASIC), or the components may reflect functionally provided by circuitry within the controller <NUM> that does not necessarily have a discrete physical form separate from other portions of the controller <NUM>. Although illustrated as components within the controller <NUM> in <FIG>, the components <NUM>, <NUM>, and <NUM> can be external to the controller <NUM> or can have a number of components located within the controller <NUM> and a number of components located external to the controller <NUM>. Additionally, components <NUM>, <NUM>, and <NUM> are not limited to circuitry (e.g., hardware) implementations (e.g., the can be implemented in hardware, firmware, and/or software).

In operation, data can be written to and/or read from memory <NUM> as a page of data, for example. As such, a page of data can be referred to as a data transfer size of the memory system. Data can be sent to/from a host (e.g., host <NUM>) in data segments referred to as sectors (e.g., host sectors). As such, a sector of data can be referred to as a data transfer size of the host.

<FIG> illustrates a diagram of a portion of a memory <NUM> having a number of physical blocks <NUM>-<NUM> (BLOCK <NUM>), <NUM>-<NUM> (BLOCK <NUM>),. , <NUM>-B (BLOCK B) in accordance with a number of embodiments of the present disclosure. Memory <NUM> can be, for example, a NAND flash memory. However, embodiments of the present disclosure are not limited to a particular type of memory or memory. For example, memory <NUM> can be a DRAM array, an RRAM array, or a PCRAM array, among other types of memory. Further, although not shown in <FIG>, memory <NUM> can be located on a particular semiconductor die along with various peripheral circuitry associated with the operation thereof.

The blocks <NUM>-<NUM> (BLOCK <NUM>), <NUM>-<NUM> (BLOCK <NUM>),. , <NUM>-B (BLOCK B) can be referred to collectively as blocks <NUM>. The blocks <NUM> can comprise single level cells (SLCs) and/or multilevel cells (MLCs). As an example, the number of physical blocks <NUM> in memory <NUM> may be <NUM> blocks, <NUM> blocks, or <NUM>,<NUM> blocks, but embodiments are not limited to a particular number of physical blocks in memory <NUM>.

Each block <NUM> can include memory cells that are erased together as a unit. As shown in <FIG>, each physical block <NUM> can comprise a number of physical rows <NUM>-<NUM>, <NUM>-<NUM>,. , <NUM>-R of memory cells that can each be coupled to a respective access line (e.g., word line). The number of rows in each physical block can be <NUM>, but embodiments are not limited to a particular number of rows <NUM> per physical block.

As one of ordinary skill in the art will appreciate, each row <NUM> can comprise a number of physical pages of cells. A physical page of cells can refer to a number of memory cells that are programmed and/or read together or as a functional group. In the embodiment shown in <FIG>, each row <NUM> can comprise one physical page of cells. However, embodiments of the present disclosure are not so limited. For instance, each row <NUM> can comprise multiple physical pages of cells (e.g., an even page associated with cells coupled to even-numbered bit lines, and an odd page associated with cells coupled to odd numbered bit lines). Additionally, for embodiments including multilevel cells, a physical page can store multiple logical pages of data with each cell in a physical page contributing a bit toward a logical lower page, a bit toward a logical upper page, and one or more bits toward a respective number of logical intermediate pages.

In the example shown in <FIG>, a physical page corresponding to a row <NUM> can store a number of sectors <NUM>-<NUM>, <NUM>-<NUM>,. , <NUM>-S of data (e.g., an amount of data corresponding to a host sector, such as <NUM> bytes). The sectors <NUM> may comprise user data as well as overhead data, such as error correction code (ECC) data and LBA data. It is noted that other configurations for the physical blocks <NUM>, rows <NUM>, and sectors <NUM> are possible. For example, rows <NUM> can each store data corresponding to a single sector which can include, for example, more or less than <NUM> bytes of data.

<FIG> illustrates a timing diagram associated with performing a garbage collection operation. The garbage collection operation described in <FIG> can be a non-deterministic garbage collection operation that can be performed (e.g., as a background operation) by a controller <NUM>, which can be a controller such as controller <NUM> described in <FIG>. In this example, at a time t<NUM>, a host <NUM> provides a number of logical addresses corresponding to invalid data to controller <NUM>. As an example, arrow <NUM>-<NUM> can represent a trimming command.

At time t<NUM>, the controller <NUM> can update its page mapping responsive to the logical addresses received from the host <NUM> to reflect those logical pages no longer corresponding to valid data (e.g., those logical pages to be marked as invalid) and mark those pages as such (e.g., as indicated by arrow <NUM>-<NUM>). Accordingly, the updated mappings and page status can be accounted for (e.g., by controller <NUM>) when garbage collection occurs. However, since the garbage collection is performed as a background operation, it is performed at some non-deterministic time tN in the future (e.g., as indicated by arrow <NUM>-N). As such, the data corresponding to the logical addresses received from host <NUM>, which may be sensitive data targeted for erasure, is not be physically removed from memory <NUM> until some later time when the block(s) in which the invalid data resides is erased. Additionally, due to the nature of logical block addressing, other copies of data targeted for deletion (e.g., previous copies) may exist on memory <NUM> even after the data corresponding to the current mapping is physically erased.

<FIG> illustrates a timing diagram associated with directed sanitization of a memory <NUM> in accordance with a number of embodiments of the present disclosure. In this example, at a time t<NUM>, a host <NUM> provides a number of logical addresses (e.g., LBAs) corresponding to invalid data to controller <NUM>. As an example, arrow <NUM>-<NUM> can represent a trimming command sent in association with a forced flush of a trimming queue initiated by the host <NUM>. At time t<NUM>, a host-initiated sanitization command <NUM>-<NUM> is sent to controller <NUM>. Although shown as occurring at separate times in <FIG>, the forced flush of the trimming queue may be provided in parallel with the sanitization command in association with a directed sanitization operation.

Responsive to the sanitization command <NUM>-<NUM>, the controller <NUM> can initiate a deterministic garbage collection operation. The deterministic garbage collection operation can be a complete garbage collection operation as opposed to a partial garbage collection operation. A partial garbage collection operation can refer to a garbage collection operation in which some blocks containing invalid pages are erased (e.g., subsequent to relocating any valid pages in the blocks). A complete garbage collection operation can refer to a garbage collection operation that results in no physical block containing invalid pages (e.g., all physical blocks previously containing invalid data have been physically erased and any valid pages previously stored in blocks containing both valid pages and invalid pages have been relocated to different physical blocks), such that all blocks of the memory <NUM> either contain only valid pages or a combination of valid pages and physically erased cells.

In the example shown in <FIG>, arrow <NUM>-<NUM> represents relocation of all valid pages contained in a block storing both valid and invalid pages to a different (e.g., free) block, and arrow <NUM>-<NUM> represents physical erasure of all blocks containing invalid pages. The garbage collection performed in response to the sanitization command <NUM>-<NUM> is deterministic in that it is performed on demand (e.g., by host <NUM>) and can guarantee that all data corresponding to the invalidated LBAs from host <NUM> is physically erased from memory <NUM> between time t<NUM> and t<NUM>, without losing valid data stored in memory <NUM>. Also, unlike the garbage collection operation described in <FIG>, which is performed in the background in a non-deterministic manner by controller <NUM>, execution of the deterministic garbage collection operation shown in <FIG> occurs responsive to the sanitization command <NUM>-<NUM>.

Additionally, although not shown in <FIG>, the controller <NUM> can be configured to report a completion status of the deterministic garbage collection operation to host <NUM>. As an example, the completion status may simply indicate a pass/fail of the garbage collection operation. However, the completion status may also, or instead, indicate a completion amount (e.g., percentage) associated with the deterministic garbage collection operation. The host <NUM> may poll the memory system (e.g., via controller <NUM>) for the completion status, and/or the controller <NUM> may send the completion status unsolicited.

<FIG> illustrates block status of a memory <NUM> prior to directed sanitization, and <FIG> illustrates block status of the memory <NUM> shown in <FIG> subsequent to directed sanitization in accordance with a number of embodiments of the present disclosure. In <FIG>, the memory <NUM> is shown as including two physical blocks <NUM> and <NUM> for purposes of illustrating the example; however, embodiments are not limited to a particular number of blocks. Although embodiments described in <FIG> involve deterministic executions of garbage collection operations on blocks of NAND memory cells, embodiments are not so limited.

In <FIG>, the designator "V" (e.g., Vi to V<NUM>) represents valid data (e.g., a valid page), and the designator "I" (e.g., I<NUM> to I<NUM>) represents invalid data (e.g., an invalid page) stored in a corresponding block. The designator "FREE" shown in <FIG> represents a physically erased page.

In this example, each block <NUM> and <NUM> of memory <NUM> comprises nine pages; however, one of ordinary skill in the art will appreciate that a block can comprise more or fewer than nine pages. As shown in <FIG>, prior to execution of a deterministic garbage collection, block <NUM> contains both valid and invalid data. For instance, pages <NUM>-<NUM> (I<NUM>), <NUM>-<NUM> (I<NUM>), <NUM>-<NUM> (I<NUM>), and <NUM>-<NUM> (I<NUM>) are invalid pages, and pages <NUM>-<NUM> (V<NUM>), <NUM>-<NUM> (V<NUM>), <NUM>-<NUM> (V<NUM>), <NUM>-<NUM> (V<NUM>), and <NUM>-<NUM> (V<NUM>) are valid pages of the block <NUM>. In <FIG>, block <NUM> represents a physically erased block (e.g., a block containing only unprogrammed free pages). Accordingly, all pages <NUM>-<NUM> to <NUM>-<NUM> of block <NUM> are designated "FREE" as shown in <FIG>.

As shown in <FIG>, upon a successful completion of the deterministic garbage collection operation, none of the blocks <NUM> and <NUM> of memory <NUM> contain both valid and invalid pages. The garbage collection operation involves physically erasing all blocks containing invalid pages, and for those blocks containing both valid and invalid pages, relocating the valid pages to a different (e.g., free) physical block prior to erasing the block from which the valid pages were relocated. For instance, in this example, subsequent to the garbage collection operation, block <NUM> is in a physically erased state (e.g., all pages <NUM>-<NUM> to <NUM>-<NUM> have been physically erased such that their status is "FREE"). Also, the valid pages of block <NUM> (e.g., pages <NUM>-<NUM> to <NUM>-<NUM>) have been relocated to physical pages (e.g., pages <NUM>-<NUM> to <NUM>-<NUM>) of block <NUM>, such that no valid pages were lost as a result of the deterministic garbage collection operation.

<FIG> is a flow diagram illustrating a method <NUM> for directed sanitization of memory in accordance with a number of embodiments of the present disclosure. At step <NUM>, the method <NUM> includes receiving a directed sanitization command from a host (e.g., host <NUM>). At step <NUM>, the method <NUM> includes obtaining, from the host, updates regarding addresses (e.g., LBAs) corresponding to invalid data, and updating a logical to physical address map responsive to the updates received from the host. The address updates can be provided as command parameters of the directed sanitization command, for example. At step <NUM>, the method <NUM> can also include identifying, from the updating of the logical to physical address map, physical addresses (e.g., physical pages) corresponding to logical addresses received from the host. As an example, the invalid LBAs received from the host can correspond to a file targeted for deletion, which may comprise sensitive information.

At step <NUM>, the method <NUM> includes determining whether blocks containing invalid pages targeted for erasure also contain valid data. If it is determined that any of the identified physical blocks contain valid data, the valid pages are relocated to different (e.g., free) physical blocks prior to physical erasure of the identified blocks, as shown at <NUM>. If it is determined that the identified physical blocks do not contain valid data, the identified blocks are physically erased, as shown at <NUM>.

At step <NUM>, a determination is made regarding whether the garbage collection operation is completed (e.g., successful) or not (e.g., failed). At step <NUM>, a completion status (e.g., PASS) is provided to the host responsive to successful completion of the deterministic garbage collection operation. At step <NUM>, a completion status (e.g., FAIL) is provided to the host responsive to unsuccessful completion of the deterministic garbage collection operation.

Claim 1:
A method for directed sanitization of memory, comprising:
receiving, from a host (<NUM>, <NUM>) external to a memory (<NUM>, <NUM>, <NUM>, <NUM>) that is a solid state drive, SSD:
logical block addresses, LBAs, associated with a file targeted for deletion; and
a sanitization command (<NUM>-<NUM>); and
responsive to receiving the sanitization command (<NUM>-<NUM>), initiating performing a deterministic garbage collection operation on the memory (<NUM>, <NUM>, <NUM>, <NUM>);
wherein performing the deterministic garbage collection operation results in physical erasure of all invalid data stored on the memory (<NUM>, <NUM>, <NUM>, <NUM>) corresponding to the LBAs received from the host (<NUM>, <NUM>) without losing valid data stored on the memory (<NUM>, <NUM>, <NUM>, <NUM>);
wherein the memory (<NUM>, <NUM>, <NUM>, <NUM>) is coupled to a controller (<NUM>, <NUM>) of the solid state drive, and wherein receiving the sanitization command (<NUM>-<NUM>) further comprises receiving a host-initiated sanitization command (<NUM>-<NUM>) at the controller (<NUM>, <NUM>) from the host (<NUM>, <NUM>); and
wherein the method includes, prior to initiating performing the deterministic garbage collection operation, obtaining, from the host (<NUM>, <NUM>), updates regarding addresses corresponding to invalid data.