Method and device for managing data in a non-volatile memory

The invention relates to the management of data and a nonvolatile in memory segmented data memory, and in particular the protection of transactions having at least a write operation in a trigger the memory segments.

In almost every system, there are data, whose presence in a non-volatile Memory and its contents leave the system can have. Such data should therefore always in a defined state being held.

Compact units, such as smart cards, USB tokens or other removable media rarely have an internal power supply. There is characterized the risk that during a write operation, the external Power supply is interrupted. The value of the field described can no longer be regarded as defined. It can in a unchanged, already amended or incompletely altered state be.

To data in a data store always in a defined state hold, write operations are a so-called atomic write operations executed. For an atomic write operation, it is ensured that either new data is completely written, or the corresponding older data is retained. After an interruption of a write operation the concerned field, for example to the state before the Write operation returned.

It is known to use for this purpose a feedback buffer, in which first the old data are backed up from the data memory. Subsequently, the old data is overwritten in the data store. A Status information shows whether the feedback buffer contains old data. After an interruption and restoration of power supply can reference the status information to decide whether old data in the data store are attributable.

For some types of data storage devices, such as flash EEPROM, can Bits singly to a single binary value -. Eg the value "0" - be set, but only one, all the bits of an entire storage site in the other binary value -. eg the value "1" - will be deleted. Deleting a Memory page is compared with the writing to the memory side of the temporally elaborate step. A method using a feedback buffer, but must both the memory page of the feedback buffer as well as the Erasing the memory page of the old data and is therefore time-consuming.

For flash memory, document US 5,832,493 discloses a method A, in which the sectors of memory managed through allocated addresses will. Old data in a first sector are assigned a Address addressable. You can now with new data in a second Sector to be replaced, which have the same assigned address. Thus, for an atomic write operation, only one memory page, namely the old data to delete. In a corresponding method "Overwriting" the old data of the first sector first as (prediscarded) in. After writing the new data into the new sector will be regarded as "erase" the old data in the old sector (Discarded) in.

It is the object of the present invention to provide a method and apparatus to secure data in a nonvolatile memory segments and in provide divided data storage, which demands the a high data security, and fast processing speed suffice.

According to another object of the present invention is an apparatus are provided, which the management of data in memory segments simplified.

These objects are achieved by methods according to claims 1 and 8 or Apparatus according to claim 15 and 18 dissolved. The dependent claims define preferred embodiments of the invention.

The present invention is based on the approach of a memory segment next to a state to provide another data element. For the That erasing the memory segment not run case fully was, the more data element allows the determination of the age ranges the data in the not completely erased memory segment against Data in a second memory segment. Using a another Element contradicts the conventional approach, the number of Data elements to minimize the management of user data. The insurance an atomic write operation is, however, improved.

According to a preferred embodiment of the method includes the data element for determining the relative age rank a reference to the old memory segment. Such a reference in the management of data new memory segment allows assignment of the new memory segment to an old memory segment by a data item with a comparatively small size.

According to a further embodiment of the method comprises the data element for determining the relative age rank seniority data so are chosen to be by an incomplete deletion in a state pass, which is recognized as incomplete erased state. This additional data item enables detection of the older memory segment also in the case where both the memory segments about their references each other as each indicate mature.

In a particularly advantageous embodiment, the seniority data three states code to whatever a level of seniority data an old memory segment, the new memory segment with a value provided to, which is classified as younger.

It is also advantageous to form the seniority data so that they in just a bit of an erased state of a data element in the Data storage differ. This configuration ensures that the seniority data even in an incomplete deletion of the corresponding Memory segment either in their original state remain or be set to a total of erased state.

According to a preferred embodiment, the method used to secure a process with a plurality of different memory segments irreplaceable data. It comprises a write new data, a first Changing the status of the data element and a step comprising a deletion of the old data and a second changing of the status data element. Each of these Steps is performed for each of all the data to be replaced before with proceeding to the next step.

According to a further aspect of the present invention includes a memory segment a non-volatile data memory each have an area for Management data and an area for user data, wherein the management data Status data for identifying a state of the respective Memory segment included. Means for activating the respective storage segment, activate the memory segment when a corresponding Address signal is addressed, evaluate the address of the memory segment and the status data from the memory segment to determine, whether the memory segment is activated. Such a wiring Data memory improves the access time to the corresponding data.

According to a preferred embodiment, the management data an assigned address of the memory segment used by the activation means is evaluated. Thus, additional administrative burdens be avoided for assigned addresses.

According to a further preferred embodiment, the means of adapted activation of the memory segment, selectively addressing via a physical or an assigned address of the memory segment make. A predicate is a function of a Address signal either the physical address or the assigned Address of the memory segment is supplied. A linked logic device the address signal and the result of evaluation of the status data. By such a structure of the data memory at an address and will be transparent about the physical address.

Further features and advantages of the invention will become apparent from the following Description of embodiments of the invention. The Embodiments are described with reference to the figures, which in the each show:<dl tsize="6"><dt>Fig.1</dt><dd>a schematic representation of a data structure in a Data storage;</dd><dt>FIG. 2</dt><dd>a flow chart for a method for securing a Write operation;</dd><dt>Fig. 3</dt><dd>a schematic representation of the memory contents of two Memory segments in the sequence of the changes made by a method shown in FIG. 2;</dd><dt>Fig. 4</dt><dd>a flowchart for a process for the recycling of Memory contents depend on administrative data in the Memory segments;</dd><dt>Fig. 5</dt><dd>a schematic representation of a mobile data carrier;</dd><dt>Fig. 6</dt><dd>a schematic representation of a data memory;</dd><dt>Fig. 7</dt><dd>a flow chart for a method for securing a complex transaction (with reference to FIG. 2); and</dd><dt>Fig. 8</dt><dd>a flow diagram for a method for recycling a Data memory for a complex transaction FIG. 7.</dd></dl>

In Fig. 1, the data elements of a data structure are shown schematically, as non-volatile for the procedure according to the present invention in Datastores used.

The data structure 10 contains management data 11 and user data 12. In the management data 11, a status data element 13, a seniority counter 14, a predecessor index 15 and a virtual address 16 included.

By using virtual addresses a memory segment may independently referenced by its physical address. The predecessor Index 15 contains a reference to the memory segment, which previously was provided with the virtual address 16th As reference example, uses the physical address of the old memory segment will.

The necessary space for the data elements 15,16 or their size in bits or bytes depending upon the number of used physical Addresses of the memory segments. This number may be limited by be that not all storage segments of a data memory for virtual addressing and / or atomic write to it be provided.

The seniority counter 14 is encoded by three bits. Only one bit of the Seniority counter 14 deviates from the erased state of the data elements where from data storage. is for the described embodiments starting from a flash memory page, identified by a fast writing a value of 1 to a value of 0 allows a hand and slower Delete needed to the value 1 of 0.

Between the three possible values ​​of seniority counter (1,1,0); (1,0,1) and (0,1,1) is a seniority of values ​​defined so that one value to be regarded as more than a corresponding comparison value. The age Ranking for example, can be defined as follows: (1,1,0) is older than (1,0,1), (1,0,1) is older than (0,1,1) and (0,1,1) is older than (1,1,0).

The state data element 13 is encoded by two bits S1 and S0. As values for a state are used in the following figures: (1.1) for a deleted memory segment (1.0) for a written storage segment, whose atomic write operation has not been completed, and (0.0) for a memory segment upon completion of atomic write operation.

A method for a secure writing of data in a memory segment with steps 20 to 28 will be described based on FIG. 2. The changes involved of values ​​within the data structures of the two Memory pages i and j is shown in by such a procedure FIG. 3.

In its initial state 301, the memory page i contains a status data element with the value (0,0). The memory page i also contains the currently valid Data that are addressable using the virtual address a. The data of Memory page j are deleted in the initial state 302 so that all the bits the memory page have the value 1.

The old data in the memory page i to be replaced by new data. As shown in Fig. 2, the counter C is initially (n) of the memory page i read in a step 21. In a ring buffer, the more detail will be described, in a step 22, a page index j to the next is any memory page read.

Starting from the seniority count C (n) of the old memory page with the i Value (1,1,0) is the next most recent value of the predetermined Ranking certainly. The value of seniority counter C (n + 1) of the new memory page, the reference to them as the older of the two memory pages involved, in this case is (1,0,1). In a step 23 the new data are j written into the memory page.

As shown in FIG. 3 can be seen, remain the old data of the memory page in the state i 303 unchanged. The new data of the memory page j included in the state 323 in the management data, a status data item with value (1.1) and the seniority counter with the value (1,0,1). The previous index in the management data in the state 323 refers i to the memory page. The virtual address of the memory page j is the virtual address of the previous memory page i equated, so also has the value a.

In a step 24 of the method according to FIG. 2, the status bit is S0 Memory page j is set to zero. In addition to continue unchanged values the memory page i in the state 304 is the change in the status of data item the memory page j in state 324 recognizable. is made in step 25 erasing the memory page i. In the state 325 of the memory page i all data already deleted.

The page index of the erased memory page i is in a step 26 the ring buffer written. In order to use the memory sides equally to distribute all available memory pages stores the ring buffer (FIFO), the indices of the available and erased memory pages. The Indices just deleted pages be pushed into the ring buffer and the indices a to be used for a write memory page removed at the other end of the ring buffer. The use of the memory pages is thus equally on all sides of the storage data memory distributed. Particularly in flash data storage that only a limited number permit of erase cycles in the overall life the data memory can be increased.

In the final step 27 of the method according to FIG. 2, the status is S1 of the memory page j is set to zero. The status of the memory page j indicates the state 327 that the atomic transaction completed and the To use memory page j as the current memory page for the virtual address A is.

In FIG. 4 is shown a process 400 to 450 for status check or to Repatriation of data after a power interruption, during a atomic transaction has occurred according to the procedure of FIG. 2. such a A method according normally after a restart of the smart card a reset (forced reboot) or a power outage performed to ensure that the data used in a consistent state are.

In a first step 401, the management data, in particular at least the status data, all read to be tested memory pages. A number n of pages for which the status data element has the value (1,0), is counted in one step 402nd According to the branches 410 and 420 the process is continued depending on the determined number n.

If an atomic write operation of FIG. 2 prior to step 24 of setting the S0 bit to 0 or after the step 27 of the setting bit S1 interrupted to the value 0, then there exists no memory page with the status (1.0). If an interruption occurs during the step 25, the deletion of the old Memory page occurs, Two memory pages with the status (1,0) present as a random shift from the state (0,0) to the state (1.0) by incomplete deletion is possible. In all other cases a Interruption of atomic write operation is exactly one memory page with the status (1.0) before.

If branch 410 in accordance with the number n = 1, is from the corresponding Memory page k in a step 411, a reference to the previous page k_alt Read. is k_alt From previous page in step 412, the Status data element in the old site read. Displays the status data element That the old memory page is not deleted according to branch 413 is the old memory page is the index k_alt in a step 424 deleted and the index k_alt in the ring buffer is written (step 425). Regardless of the branch 413, the status bit S1 of the page is in k a step 426 is set to zero.

Are there other hand, according to branch 420 Two memory pages with the value (1.0) in the status data item, both seniority counter Ci and Cj of Memory pages i and j read in a step 421st Based on the read Seniority counters Ci and Cj is determined in a step 422, which the two memory pages was last described. A seniority counter can thereby prove the Elder, when it corresponds to an erased state or if in accordance with the pre-established definition Older than is to be considered. In step 424 the older memory page is then deleted. The page index of the erased memory page, in the step 425 in the Ring buffer written. Finally, in turn, is to step 426, the Status S1 of the new memory page is set to zero.

If the evaluation of the number n by the branches 410 and 420, that no memory page with the value (1.0) detected in the status data element is, so can still get a break immediately after step 23 are present in Fig. 2. Therefore, it is checked in a step 431 whether a Memory Page n exists, with a status (1.1) and other administrative data is which are not deleted, respectively. Such side is n cleared in a step 432 and the page index n in a step 433 in the ring buffer written.

Since the management data of the memory pages already in step 401 at least be partially read, the steps 431-433 may alternatively take place in the step of reading out four hundred and first

Furthermore, it should be noted that steps 431-432 and 413 are optional Steps of the method. The indices of the treated through these steps Memory pages are no longer or not yet stored in the ring buffer and therefore can not be used further. A cleaning of Data storage by evaluating and treating these memory pages can Therefore, regardless of the return of data to atomic transactions done.

The method illustrated in Fig. 4 allows all the data through an interrupt affected during a simple hedged transaction could be, quickly and safely in a defined state back to to lead.

If there was an interrupt, in general, a memory page with a status data element (1.0) are present, since the step of erasing 25 a memory page according to Fig. 2 takes a relatively long time. This case can about the Evaluation of the previous reference are handled quickly (steps 411 to 413).

The rare event that happens to a second memory page also the status having (1,0), thereby complicating that theoretically, the predecessor references the two storage sites could refer randomly stacked. The seniority counter allows uniquely identifying and corresponding Delete the older memory page (steps 420-426).

In FIG. 5 are the basic functional elements of a portable data carrier 50 shown. As portable data carrier, for example, a Smart card, a USB token or a SIM card for a terminal of a mobile radio system present.

In addition to a CPU 51, an interface 52 is provided that contactlessly and / or with contact communication with external components or arranged in the mobile data carrier further components allows. A cryptographic unit 53 to perform cryptographic calculations as well as a detector or sensor 54 for detection of external Attacks against the mobile data carrier are also provided. As Memory elements are provided, a volatile memory (RAM) 56, a not of rewritable memory (ROM) 57 and a non-volatile and in segments organized memory (flash EEPROM) 58. The elements 51 to 54 and 56 to 58 are at least over a line 55, preferably a bus connected to each other. Optionally, the mobile data carrier a dedicated power supply on.

The memory segments of the data memory 58, as shown in Fig. 6, be adapted according to the invention and / or, as shown in Figs. 2, 4, 7 or 8 shown be used. A control software for executing a corresponding method, in one of the memory elements 56 to 58 be stored.

In Fig. 7 the process is according to an embodiment of the present invention shown for a complex transaction. The complex transaction summarizes a number of steps together, in each of which data in Memory segments can be written. The complex atomic Transaction of FIG. 7 is intended, together with the recirculation of FIG. 8 to make sure that are affected by the complex transaction memory segments either all or changed but all are unchanged.

In a corresponding process 70 to 74 is initially in a step 71 for each affected memory page the sequence of steps 21 to 23 of FIG. 2 executed. For each affected store page so is over the complex Transaction reading of the counter of the page i, reading a new page index from the ring buffer and the writing of new pages executed in the j page. Only when the necessary steps of the complex Transaction have been completed in itself, so also written all memory pages are, in a step 72, the complex atomic transaction the status bit S0 is set for each of the affected memory pages to zero. Finally, a parent step 73 with the partial steps 25 to 27 of Fig. 2 for each affected memory page executed individually. Step 73 includes a deletion of the old page, a letter from the old site in Index the ring buffer and set the status bit S1 to zero in the new page.

The method shown in Fig. 8800-850 for a complex status check or for the treatment of interruptions in a complex atomic transaction is adapted to the method according to Fig. 7.

The method begins with a loop 801, 823, 824, in which for all N memory pages the status in step 802 is read. It is with continued the next memory page in the loop when according to branch 810 of the status of the memory page has the value (1,1) and according Branch 811, the management data is already deleted. Has contrast the status of the memory page the value (0.1) or the management data not erased the memory page, then according to branch 820 and 811 a corresponding memory page deleted in step 821 and the Page index written in a step 822 in the ring buffer. If the Status of the memory page (1,0) is, at least the index n of the memory page stored in a list 831st

The list includes therefore for each memory page to be treated at least the index, the virtual preferably by physical or Address of the memory page is formed. Other already from the memory page read management data still used during the proceedings be so particular reference predecessor (k_alt) and the Seniority counters can also be stored in the list.

After all memory pages are checked for their status, is in a Branch 840, a check for conflicts in the list of memory pages with the status (1.0) is executed. A conflict occurs when two memory pages In the list mutually specify the respective previous page. For such a conflict is, in a step 841 the older memory page on the basis of seniority counters C1 and C2 of the conflicting memory pages certainly.

In a loop of steps 842-847 then the list entries individually processed. First, a pointer to the straight edited list entry shows set to the first list entry (Step 842). In a step 843 the older memory page is deleted k_alt and the page index k_alt written in a step 844 in the ring buffer. Thereafter, the status bit S1 of the new memory page, in a step 845 set to zero. Steps 843-845 are through the transition to the next entry in the list in step 846 and the branch 847, in the is checked for the end of the list, for all entries of the list processed.

The steps 810, 811 and 820-822 are optional steps of the method. The indices of the treated through these steps memory pages are not longer or not yet stored in the ring buffer, and are therefore also not used further. A cleanup of the data memory by evaluating and treating these memory pages can therefore independent of the Repatriation of data to atomic transactions take place.

can for the management of the virtual addresses of memory segments a table can be used.

Such a table can in volatile or non-volatile memory are held and assigns a virtual address used to index a memory page or its physical address. All Hits must then user data in the memory segments on the respective Table done. At power up of a mobile data carrier with a corresponding number of flash memory pages is this table generated in the RAM, by checking all flash memory pages.

If both status bits S1 and S0 of a memory page i is 0, then is it a allokkierte page based on their virtual address a registered with a reference to the physical address in the box becomes: <i>pBLOCK [a] = &amp;</i>(<i>page i</i>)<i>,</i>

If the status bit S1 and S0 of a memory page are both equal to 1, the Remainder of the administrative definition is deleted and also the entire user data area is deleted, then it is a free memory page. Of the corresponding page index is stored in a memory element or in an Ring buffer is stored in RAM.

All other conditions are by the methods described above recycled for handling interrupts on these two ground states.

However, such a mechanism behaves when read accesses to the memory pages not transparent, therefore requires a higher administrative burden on one level of the memory access and therefore leads to prolonged Access times.

Administrative expenses by an addressing table, by using of memory segments, as shown in Fig. 6, is avoided will.

In FIG. 6, control, address and data lines 611-618 are shown, with the a flash memory page 601 are connected. The memory page 601 has For example, 1x32 bit management data and 64x32 bits of useful data on. Only It is indicated that in addition to the page memory 601 further memory pages 602 are arranged in the corresponding data store, each are designed accordingly.

For the memory page 601 means for activating or releasing the Memory page 621-626 provided for access to the memory page. Before describing the details of the activation means 621 to 626, is first the basic behavior of the memory page in the activated state described as a function of the applied signals.

For the signal of a control line 611, indicating a read access, and the signal of a control line 612, indicating a write access, gives the Signal of a control line 615 whether the either the payload or Management data of the memory page to be accessed. When the signal is set on the control line 611, which are on the signal of the low address line 617 addressed data on the data line 618 output. If, however, the signal of the control line 612 is set, the Value that currently is on the data line 618 in the memory page written.

If the signal is set to a control line 613, as is the entire memory page 601 deleted, ie both the user data and the management data are set to 0xFF. The signal of a control line 614 indicates whether the addressing of a memory page of the physical Addresses (direct) or via the virtual addresses (associative) of Memory pages is done. A set signal on the data line 614 (~ Ass / dir) encoded direct addressing. Analog encodes the "1" on the Data line 615 (~ data / admin) to access the administrative data and the "0" to access the user data of the memory page.

The memory page 601 is disabled when the enable signal is equal Is "0". The signals of the control lines 611-613 will then have no effect. Is the enable signal for the memory page 601 is "1", Then, the control signals of the control lines 611-613 have the above-described Effect.

The means for activating the memory page 601 includes a read only memory 626, in which the physical address of the page memory 601 is filed. A multiplexer 625 selects according to the control signal 614 either the physical address 626 or the virtual address of the page memory a 601. The selected address is compared in a comparator 624 compared to the address on an address line 616th

If referenced by the address line 616, the memory page 601, so is an AND gate 621, an OR gate 622 and a NOR gate 623 determines whether the memory page for deletion, read or write is to 613 released or actuated according to the control signals 611th The memory page is enabled for access via the OR gate 622, when the control signal 614 direct addressing via a physical indicating address. Also enabled is the memory page when a status S1, S0 with the value (0,0), which is evaluated by the NOR gate 623, present.

Activation means are provided at least for each memory page that managed by an appropriate status and be virtually addressable should.

Below are some aspects of the described embodiments addressed to illustrate how these embodiments can be further modified.

The embodiments described with reference to the figures are adapted for a flash memory page, the fast writing of a "1" to a value "0" enables and contrast slower Delete to the value "1" is needed from the value "0". The solutions but are also readily to a memory with this inverse behavior (Fast writing of "0" to "1" and slow deletion of "1" transferable to "0").

To illustrate the access time is 60 microseconds for a write access and 8000 microseconds for erasing a memory page considered. After which at least the internal state of the art carried an atomic write operation using a recirculation buffer by securing the old data for a page with 64 * 32 bits data (64 * 60 microseconds), delete the page (8000 microseconds), writing the new data (64 * 60 microseconds) and deletion of the recycle buffer (8000 microseconds) in total 23680 microseconds.

By the procedure of FIG. 2, the duration of an atomic write operation be almost halved. After writing the new data ((64 + 1) * 60μs), clearing of the status S0 (60 microseconds), delete the old site (8000 microseconds) and clearing of the status S1 (60 microseconds) is the total duration of at 12020 microseconds.

While solutions of the invention achieve a greater benefit in Save such as flash EEPROM, which have a long erase time, However, they can also EEPROM, S-RAM or other nonvolatile Data storage are applied.

In the method of FIG. 4, 7 and 8, the steps must all memory pages to relate (see, for example, Read 401, Search 431) only for the memory pages are executed, for a corresponding method are provided. So a data store may include a first set of memory pages have provided for a secured letter, and a second set of memory pages that are not for atomic writes is provided. In such a data storage could for example only the memory pages of the first group with activating agents to Fig. 6 may be fitted.

While it is advantageous to a virtual address in the management data of a to store memory page, but not necessary. The methods described and devices can also be independent of a virtual Addressing, or a specific form of management of a virtual Address are used.

In portable data carriers without their own power supply is preferably erasure of the memory pages executed as described. For example To reduce the processing time of a complex transaction may the steps of erasing a memory page are initially omitted. The memory pages concerned must then, instead of being deleted, be provided with a status "to delete". For this, the state data element extended by a corresponding bit in the written Condition signals this status. At an appropriate later time to delete memory pages will be deleted.