WO2012062233A1 - Method for deallocating memory areas no longer needed on non-volatile memory media - Google Patents

Abstract

The invention relates to a method for deallocating memory areas no longer needed on a non-volatile memory medium, which is connected by means of a host bus to a host system, in the file system of which data are marked for deallocation, wherein in the non-volatile memory medium the data are managed by a memory management program in a memory controller in physical memory blocks each having a writing structure and logical data blocks are associated with physical memory blocks by an association table. The method comprises the following steps: the host system informs the memory management program of the possible deletion of logical data blocks by means of a TRIM command; the memory management program forms TRIM clusters from the memory areas associated with the logical data blocks; incorporates into the writing structure of the physical memory blocks a TRIM mask having elements for the TRIM clusters of the memory block, to which the deletion information of the TRIM command is associated by means of the association table; and updates the TRIM masks continually in all updating operations and garbage collections of the memory blocks.

Description

 Method for releasing storage areas no longer required

Nonvolatile Storage Media The invention describes a method for releasing no longer needed

 Storage areas on a non-volatile storage medium, which is connected via a host bus to a host system in whose file system data for release are marked, and in the non-volatile storage medium, the data from a memory management program in a memory controller in physical

Memory blocks are each managed with a description structure and an assignment of logical data blocks to physical memory blocks is carried out by a mapping table.

Widely used nonvolatile storage media (flash memories) are semiconductor memories that do not require a voltage source to retain their information. Flash memories are used as memory cards for digital cameras,

Mobile phones, PDAs and multi-media players. In addition, today they are increasingly used in computer systems as mass storage media, in particular in the form of so-called solid state drives (SSD), which are opposite to the

Computer system as the conventional magnetic hard drives behave and can be addressed by the operating system of the computer. Internally, the SSD essentially consists of a memory controller and a number of flash memory elements depending on the memory size. The memory controller controls how the data is read from the cells of the flash memory devices and manages the flash memory cells. The flash memory cells are organized into blocks of memory, and these in turn are organized into pages, with pages of 4 KB size that can be read and written individually, and

Memory blocks between 128 KB and 512 KB in size that can be deleted. The flash memory possess the technical property that

Information can only be written page by page to previously deleted pages. The deletion is done for a whole block of memory for all pages together.

Operating systems do not delete the file contents of a deleted file itself, but only remove the entry of the file in the table of contents of the file system. The speeds up the deletion process, which can erase large amounts of data very quickly, but also allows recovery of the deleted file. Heretofore, the SSD's memory controller has received no information about such erased or otherwise freed memory areas that are no longer used by the file system. As a result, each time the memory blocks are updated or garbage cleaned, the pages occupied by the contents of the file fragments actually deleted must still be written, even if the data is never reused by the computer system. To remedy this situation, the operating system can be standardized by the new TREVI command, which is part of the ATA standard by the TITS Technical Committee standard body of the INCITS under the ATA8-ACS-2 specification

(http://tl3.org/Documents/MinutesDefault.aspx?keyword=TRIM), informing the SSD when deleting files that it can mark the space occupied by them as invalid instead of keeping their data. The contents continue to be written along with more, which accelerates the write access to the drive and also reduces the wear effects of the flash memory. The memory blocks that have been invalidated are then freed the next time they erase their memory block. For example, the operating systems Windows 7, Windows Server 2008 R2 and Linux from version 2.6.33 currently support the TREVI command.

The TRIM command itself is not responsible for clearing the flash memory cells, but simply provides additional status about the use of the memory blocks. The management of the memory blocks is then via the

Memory controller via the appropriate garbage collection or wear-leveling algorithms directly through the storage medium. The functioning of the

 TRIM. For example, commands can be found in the documents "From write () down to the flash chips" by Louis Gerbarg (http://www.devwhy.com/blog/2009/8/4/from-write-down-to-the-flash chips.html) and "Windows 7 Enhancements for Solid-State Drives" by Frank Shu, Microsoft Corporation

(http://download.microsoft.com/download/5/e/6/5e66b27b-988b-4f50-af3a-c2ffle62180f/cor- t558_wh08.pptx).

In the patent US 2009/0010066 AI a flash memory device is described which comprises a memory cell array "Trim Information Area", in the data and Ordnungs information stored, which are used for the control of the programming, the deletion and the read modes of the memory element. In operation, when the memory element is turned on, a control logic reads in the trim information from the memory cell array, and optimizes it by means of the stored there

Operating periods include programming, deleting and reading modes of the

 Memory element. The trim information is based on its own intelligence of the control logic of the internal memory controller and are not communicated to the memory element from the outside by a host system by means of a TRIM command. It is an object of the invention to disclose a method which allows the

 Information of the TRIM command which data is no longer needed to make inheritable by a plurality of physical memory block generations and to keep this information available even after writing data into this memory block.

This object is solved by the features of claim 1.

Embodiments of the invention are described in the subclaims.

An embodiment of the invention provides a nonvolatile storage medium connected to a host system via a host bus. Such a storage medium is usually equipped with an S-ATA or ATA interface, so that it can be used as a flash drive mainly in mobile computer systems. This interface is an ATA-based software protocol for the

Data transfer between the storage medium or drive and the host system or computer used. This allows the file system of the host system via the host bus to communicate with the storage medium as with a conventional magnetic hard disks and respond using ATA commands. With the current extension of the ATA standard, it is now possible that the host system can tell the storage medium by means of the TRIM command which files in the file system were deleted by the user and are therefore no longer needed.

The storage medium essentially comprises a memory controller and a plurality of flash memory elements that depend on the memory size of the memory controller

Storage medium depends. It manages a memory management program in the Memory controller, the physical memory blocks of the flash memory elements each having a description structure in the memory block. In each of the memory blocks themselves, in turn, a plurality of pages are organized, which are read and written individually. The deletion, however, is technically conditional for a whole block of memory. After the initialization of the storage medium, the

Write memory controller at full speed into free blocks. However, as the storage medium becomes more useful, the available free blocks dwindle. The memory controller must then more often before each write

Read memory blocks and check if the data is still in use before it can be erased, which takes extra time and reduces the number of free memory blocks.

The TRIM command takes over this task in advance of the write operations and informs the storage medium of unused or invalid data blocks that can be marked for the purpose of subsequent re-description. It sets the

 Memory controller to the communicated in the TRIM command logical data blocks by an assignment table in the physical memory blocks of the storage medium. In this case, TRIM clusters are formed which represent a subset of a memory block. A TRIM cluster includes one or more pages, with a current memory block size of 64 or 128 pages, this is 2 or 4 pages per TRIM cluster. This divides a physical memory block into multiple TRIM clusters. An advantageous embodiment of the invention defines a TREVI mask with elements to the TRIM clusters of the memory block and stores the TRIM mask within the respective description structure of the memory block. The memory controller uses the assignment table to convert the deletion information of the TRIM command into the elements of the TREVI mask, whereby the TREVI mask contains one TREVI bit for each TRIM cluster. The position of the TRIM bit in the TRIM mask implicitly defines a pointer to the TRIM cluster. How many pages belong to a TRIM cluster depends on the number of pages per block of memory and the length in bits of the TREVI mask. Advantageously, the whole

Clearing information of the TREVI command compacted, converted into memory block based information and for all deletion elements of the TRIM command inheriting written in the description structure of the memory block. In addition, a log file is written on the flash memory medium, which contains the data from the Trace information obtained and permanently provided for use after a possible unexpected shutdown.

The TRIM masks are continually updated in all update operations and garbage collection operations of the memory blocks. Thus, after receiving the TRIM command, which contains a list of logical data blocks, the TRIM bit is set to 1 for all converted TRIM clusters. When updating the data in the memory block, the corresponding TRIM bits are cleared at the TRIM cluster where the new data was written. This will make the contents of already updated pages permanent. Particularly advantageous, the invention provides that in a garbage collection only the pages of an old memory block are copied into a new physical memory block whose TRIM bit is set to 0 in the TRIM mask. On the other hand, pages of a TRIM cluster whose corresponding TRIM bit is set to 1 are not included in the new one

Transfer memory block. After deleting the old memory block, for example via a garbage collection or wear-leveling algorithm, these pages are free for re-description. All unnecessary pages become advantageous

Avoiding programming, which increases the life and writing speed of the flash memory devices.

At the time of production, all the TRIM bits in all memory blocks provided for user data are set to 1 during the initialization of the flash memory medium.

The embodiment of the invention will be explained by way of example with reference to FIGS.

Fig. 1 shows a block diagram of the system connected to a host system

storage medium

 Fig. 2 shows a block diagram of the structure of the TRIM command

3 shows a block diagram of the implementation of the deletion information of the TRIM command

Fig. 4 shows a block diagram of the organization of the physical memory blocks. Fig. 5 shows a block diagram of the structure of the TRIM mask

6 shows a flowchart for processing the TRIM command

Fig. 7 shows a flow chart for processing the data update 1 shows an overview of a nonvolatile storage medium SM connected to a host system HS, which are connected to one another via a host bus HB. Via the host bus HB, the file system FS of the host system HS communicates with the memory controller MC in the storage medium SM, the storage medium SM being informed by means of the TRIM command TR which data is no longer needed. The memory controller MC can then reset based on the information obtained the vacant flash memory cells in the memory elements FM and thus speed up the writing process for new data. FIG. 2 shows the structure of the TREVI command TR as described in the currently current ATA8-ACS-2 specification. Currently, only the TREVI feature (bit 0) is specified in the Request Command. The TRIM request data area contains one or more logical data blocks as entry entries in a list, each comprising a logical block address LBA and an area length. The data blocks may overlap and they do not have to be sorted.

In Fig. 3, the conversion of the deletion information of the TRIM command TR in the physical memory block structure of the storage medium SM by the

Memory controller MC shown. Above the double arrows, the logical level LL of the file system is shown on the host system HS. Below the double arrows, physical level PL of the memory controller MC is shown on the storage medium SM.

A file of the file system FS is organized in one or more logical blocks LB0..x, which are each addressed by a logical block address LBA0..X. When a file is deleted by the file system, the TRIM command TR contains a list of entry entries EN0..X of the logical data blocks LB0..X

transferred, which contain the data of the file that are no longer needed. About the allocation table AT are the memory management program of the memory controller MC, the logical data blocks LB0..X in the physical

Memory blocks PB0..n implemented, which are each addressed by a physical block address PBA0..n. In this case, a physical memory block PB0..n comprises one or more pages PG0..y, which in turn are advantageously combined to form one or more TREVI clusters TCO.i with in each case 2 or 4 pages PG0..y. For each TRIM cluster TC0..i has an associated TRIM bit stored in the TRIM mask, whereby the pointers to the TRIM clusters TPO.i are identified by the position of the TRIM bit. 4 shows an overview of the organization of the physical memory blocks PB0..n within the storage medium SM. In this case, the storage medium SM contains one or more physical memory blocks PB0..n, which are addressed via a physical block address PBACLn. In each of the memory blocks PB0..n are in turn several pages PG0..y organized, which can be read and written individually.

Each memory block PB0..n has a description structure DS in which the memory management of the memory controller MC stores its data for managing the pages PG0..y, such as the mapping table AT. The respective description structure DS of the physical memory blocks PB0..n also includes the inventive TRIM mask TM, which contains TRIM bits TBO.i and thus pointer to TRIM cluster TPO.i. In this case, the respective physical memory block PB0..n is subdivided into a plurality of TRIM clusters TCO.i, wherein a TRIM cluster TCO.i comprises one or more pages PG0..y, the data or data fragments of the file of the host system HS to be deleted contain. The description structure DS is advantageously arranged as part of the address assignment table AT.

FIG. 5 shows an embodiment of the inventive TRIM mask TM. The TRIM mask TM contains a TRIM bit TBO.i for each TRIM cluster TCO.i. The TRIM clusters TCO.i are identified by the position of the TRIM bit TBO.i in the TRIM mask TM. The number of pages belonging to a TRIM cluster TCO.i depends on the number of pages per memory block PB0..n and the length in bits of the TRIM mask TM. As a result, the pointer defines the associated TRIM cluster TPO.i.

A TRIM bit TBO.i set to 1 indicates that the pages PG0..y of the associated TRIM cluster TCO.i are not transmitted during the next memory cleaning process of the physical memory block PB0..n and are therefore deleted or released for deletion become. On the other hand, a TRIM bit TBO.i set to 0 causes copying of the pages PG0..y of the associated memory block PB0..n. FIG. 6 shows the sequence of the TRIM operation for processing the TRIM command TR in the memory controller MC of the storage medium SM. After this

Receiving the ATA command "TRIM" from the host system, the information from the ATA command is read in. First, it is checked whether bit 0 is set to 1 in the feature element, whereby the use of this ATA command is defined as a TRIM command.

If a TRIM command is sent, all logical block addresses contained in the entry list of the TRIM command and the respective range lengths are converted into memory block based TRIM mask information. If it contains at least one complete TRIM cluster, this TRIM cluster is written into the TRIM mask of the physical memory block descriptor structure by setting the associated TREVI bit of the TRIM cluster in the TRIM mask.

In Fig. 7, the flow of data updating is in the physical

Memory blocks PB0..n shown. For this purpose, a freshly deleted buffer block is reserved for use first. Thereafter, the description structure of the memory block to be updated is read. The new data update data is written to the buffer block, with the corresponding TRIM bits cleared at the TRIM cluster where new data was written.

If, later in the data update, the buffer block is resolved, all pages that do not have a corresponding TREVI bit set in the TRIM mask and that are updated with new data are copied to a new physical memory block. On the other hand, all other pages where one

corresponding TRIM bit is set, not transferred to the new memory block. Subsequently, the release of the old memory block takes place for deletion. reference numeral

AT assignment table

 DS descriptive structure of the memory block

EN Entry

 EN0..X Entry 0 to x

 FM flash memory elements

 FS file system

 HB host bus

 HS host system

 LB logical data block

 LB0..X Logical data block 0 to x

 LBA logical block address

 LBA0..X logical block address 0 to x

 LL Logical level

 MC memory controller

 PB Physical memory block

 PB0..n Physical memory block 0 to n

PBA Physical block address

 PBA0..n Physical block address 0 to n

PG Page

 PGO..y Page 0 to y

 PL Physical level

 SM storage medium

 TB TRIM bit for TRIM cluster

 TBO..i TRIM bit for TRIM cluster 0 to i

TC TRIM cluster

 TCO.i TRIM cluster 0 to i

 TCS set of TREVI clusters

 TM TREVI mask

 TP Pointer to TRIM cluster

 ΤΡΟ..Ϊ Pointer to TRIM cluster 0 to i

 TR TREVI command

Claims

claims 1. A method for releasing storage areas no longer needed on a non-volatile storage medium (SM), which is connected via a host bus (HB) to a host system (HS), in whose file system (FS) data for release are marked, and in the non-volatile storage medium ( SM) the data from one Memory management program in a memory controller (MC) in physical memory blocks (PB) are each managed with a description structure (DS) and an assignment of logical data blocks (LB) to physical Memory blocks (PB) through an allocation table (AT), with the steps,  the host system (HS) informs the memory management program about the possible deletion of logical data blocks (LB) by means of a TRIM command (TR),  the memory management program forms TRIM clusters (TC) from the memory areas assigned to the logical data blocks (LB),  - And in the description structure (DS) of the physical memory blocks (PB) a TRIM mask (TM) with elements to the TREVl clusters (TC) of the Memory block (PB), to which the deletion information of the TRIM command (TR) is assigned via the allocation table (AT),  - and continuously updates the TRIM masks (TM) in all Update operations and garbage collections of memory blocks (PB). 2. The method according to claim 1, characterized the memory areas of the physical data block (PB) are Pages (PG). 3. The method according to claim 2, characterized one or more pages (PG) are grouped into a TRIM cluster (TC). 4. The method according to claim 3, characterized the elements of the TRIM mask (TM) contain a TRIM bit (TB) for each TRIM cluster (TC), whereby a pointer to the TRIM cluster (TP) is identified via the position of the TRIM bit in the TRIM mask becomes. 5. The method according to claim 1, characterized in that the information of the TRIM command (TR) comprises a list of one or more logical block addresses (LBA) which are assigned to TREVI clusters (TC) via the allocation table (AT) and for the respective TRIM cluster (TC) the associated TRIM bit (TB) is set to 1. 6. The method according to claim 1, characterized when updating the data of the memory block (PB), the TRIM bits (TB) for the respectively changed TRIM cluster (TC) are cleared to zero. 7. The method according to claim 1, characterized in the case of a garbage collection of the memory block (PB), only the pages (PG) of an old memory block (PB) are copied to a new memory block whose TRIM bits (TB) in the TRIM mask (TM) are set to 0. 8. The method according to claim 1, characterized in the initialization of the flash memory medium (SM) all TRIM bits (TB) are set to 1 in all memory blocks (PB) provided for user data.