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

p0001The invention relates to managing data of a non-volatile and divided into memory segments data memory and in particular the hedging transactions that trigger at least one write operation in one of the memory segments.

p0002In almost every system, there are data on their presence in non-volatile memory and its contents may exit the system must. Such data should be thus kept in a defined state.

p0003Compact units, such as smart cards, USB tokens or other removable media rarely have an internal power supply. Thus, there is 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. He may be in an unchanged, already amended or incompletely altered state.

p0004In order to keep data in a data storage in a defined state, write operations are carried out as so-called atomic write operations. For an atomic write operation, it is ensured that either new data is completely written or remain obtain the corresponding old data. After a termination of a write operation, the data field concerned, for example, returned to the state before the write operation.

p0005It 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. Status information shows whether the feedback buffer contains old data. After an interruption and restoration of power supply can be decided on the basis of status information, whether old data can be traced back to the data store.

p0006For some types of data storage devices, such as flash EEPROM, bits can singly to a single binary value - are set, but only one, all the bits of an entire memory page to the other binary value - - the value "0" for example. Eg. the value "1" - to be deleted. Deleting a memory page is compared to describe the storage side of the time-consuming step. A method using a feedback buffer, but must remove both the memory page of the feedback buffer as well as the memory page of the old data and is therefore time consuming.

p0007For flash memory disclosed the document <patcit id="pcit0001" dnum="US5832493A"><text>US 5,832,493 A</text></patcit> a method in which the sectors of a memory via assigned addresses to be managed. Old data in a first sector can be addressed with an assigned address. They can now be replaced by new data in a second sector, which have the same assigned address. Thus, only a memory page for an atomic write operation, namely to erase the old data. In a corresponding process, the old data of the first sector to be "override" first as (prediscarded) in. After writing the new data into the new sector, the old data in the old sector are then used as "delete" (discarded) in.

p0008<patcit id="pcit0002" dnum="WO0301067A1"><text>WO 03/01067 A1</text></patcit> on which the preamble of the independent claims is based, discloses a method for protecting memory segments, in which before and after erasing an old memory segment of the status of the new memory segment is changed. A reference to the old memory segment is included in the new memory segment to the old memory segment for a - possibly required after an incomplete deletion - to identify new deletion can.

p0009In <patcit id="pcit0003" dnum="US5437012A1"><text>US 5,437,012 A1</text></patcit> is created on a PC and used for writing changed data to the memory card, a virtual image of the memory of an optical memory card. To restore data after a power failure, administrative data are that ltersrangdaten such. B. "revision numbers", with enrolled.

p0010It is the object of the present invention to provide a method and apparatus for securing data in a non-volatile and is divided into memory segments data memory which satisfy increased requirements for a data security.

p0011This object is achieved by a method and a device according to the independent claims. The dependent claims define preferred embodiments of the invention.

p0012The present invention is based on the approach to provide in addition to a status one more item on a memory segment. In the event that a deletion of the memory segment was not completed, the additional data element allows the determination of the age ranges of the data in the not completely erased memory segment relative to data in a second memory segment. The use of another data element contradicts the conventional approach to minimize the number of data elements to manage user data. The protection of an atomic write operation is, however, improved.

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

p0014According to a further embodiment of the method the data item comprises determining the relative age rank seniority data, which are selected such that they pass through an incomplete deletion in a state which is recognized as incomplete erased state. This additional data item enables detection of the older memory segment even in the case when both memory segments to specify each other as each mature on their references.

p0015In a particularly advantageous embodiment, the seniority data can encode three states to whatever a level of seniority of an old data storage segment, the new memory segment with a value versehe n to which is classified as younger.

p0016It is also advantageous to the seniority data in such a way that they differ in only one bit of an erased state of a data element in the data store. This configuration ensures that the seniority data is set even with an incomplete deletion of the corresponding memory segment either remain in their original state or to a total erased state.

p0017According to a preferred embodiment, the method with a variety of different memory segments used to secure an operation irreplaceable data. It comprises a write new data, a first changing the status data element and a step containing a deletion of the old data and a second changing of the status data element. Each of these steps is carried out respectively for all of the data to be replaced before continuing with the next step.

p0018According to a further aspect of the present invention, a memory segment of a non-volatile data memory in each case contains an area for management data and an area for user data, wherein the management data includes status data for identifying a state of the respective memory segment. Means for activation of the particular memory segment that activate the memory segment, if it is addressed via a corresponding address signal, evaluate the address of the memory segment and the status data of the memory segment to determine whether the memory segment is activated. Such a connection of a data memory improves the access time to the corresponding data.

p0019According to a preferred embodiment, the management data includes an assigned address of the memory segment which is evaluated by the activation means. Thus, additional administrative burdens for assigned addresses are avoided.

p0020According to a further preferred embodiment, the means for activating the memory segment are adapted to make either an addressing via a physical or an assigned address of the memory segment. Comparing member is supplied to a function of an address signal, either the physical address or the address assigned to the memory segment. A linking member links the address signal and the result of an evaluation of the status data. By such a structure, the data memory can be operated in a transparent addressing via the physical address.

p0021Further 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 show:<dl id="dl0001"><dt>Fig.1</dt><dd>a schematic representation of a data structure in a data memory;</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 changes by a method according <figref idrefs="f0001">FIG. 2</figref>;</dd><dt>Fig. 4</dt><dd>a flow chart of a method for recycling 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 <figref idrefs="f0001">FIG. 2</figref>); and</dd><dt>Fig. 8</dt><dd>a flowchart of a method for recirculation of a data memory according to a complex transaction <figref idrefs="f0004">Fig. 7</figref>,</dd></dl>

p0022In <figref idrefs="f0001">Fig. 1</figref> are shown schematically, the data elements of a data structure, such as is used for the procedure according to the present invention in non-volatile data storage devices.

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

p0024By using virtual addresses a memory segment can be referenced regardless of its physical address. The previous index 15 contains a reference to the memory segment, which was previously provided with the virtual address 16th As reference can be used for example, the physical address of the old memory segment.

p0025The necessary space for the data elements 15,16 or its size in bits or bytes depends on the number of physical addresses used of the memory segments. This number can be limited so that not all storage segments of a data memory for a virtual addressing and / or atomic write operations are provided.

p0026The seniority counter 14 is encoded by three bits. Only one bit of the age rank counter 14 deviates from the erased state of the data elements in the data memory. For the embodiments described it is assumed that a flash memory page, which allows fast writing a value of 1 to a value 0 and on the other hand slower deleting from the value 0 to the value 1 needed.

p0027Between 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 is 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).

p0028The state data element 13 is encoded by two bits S1 and S0. The values ​​of 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 by completed atomic write operation.

p0029A method for a secure writing of data in a memory segment with steps 20 to 28 is based on <figref idrefs="f0001">FIG. 2</figref> described. The changes of values ​​within the data structures of the two memory pages involved i and j by such process sequence is shown in<figref idrefs="f0002">Fig. 3</figref>,

p0030In its initial state 301, the memory page contains i a status data element with the value (0.0). The memory page i also contains the currently valid data that can be addressed via the virtual address a. The data of the memory page j are deleted in the initial state 302, so that all the bits of the memory page have the value 1.

p0031The old data in the memory page i to be replaced by new data. As in<figref idrefs="f0001">FIG. 2</figref> shown, the counter C (s), first the memory page i is read in a step 21 of a ring buffer, which is described in more detail, in a step 22, a page index j of the next to be used memory page is read out.

p0032Starting from the seniority count C (n) of the old memory page with the value (1,1,0) the next most recent value is determined according to the predetermined ranking i. The value of seniority counter C (n + 1) of the new memory page featuring them as the older of the two memory pages involved is, in this case, (1,0,1). In a step 23, the new data is written in the memory page j.

p0033As in <figref idrefs="f0002">Fig. 3</figref> recognizable, the old data of the memory page in the state 303 remain unchanged i. The new data of the memory page j included in the state 323 in the management data, a status data element with the 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 to the memory page i. The virtual address of the memory page j the virtual address of the previous memory page i is equated, has therefore also the value of a.

p0034In a step 24 of the method according <figref idrefs="f0001">FIG. 2</figref> the status bit S0 of the memory page j is set to zero. In addition to continue unchanged values ​​of the memory page i in the state 304 this change in status data element of the memory page j recognizable in the state 324th In a step 25, the erasing of the memory page is done i. In the state 325 of the storage side i all data is already deleted.

p0035The page index of the erased memory page i is written in a step 26 in the ring buffer. To spread the use of memory pages evenly across all available memory pages, the ring buffer (FIFO) stores the indices of available and erased memory pages. The indices just deleted pages be pushed into the ring buffer and removed the indexes of a to be used for a write memory page at the other end of the ring buffer. The use of memory pages is evenly distributed on all memory pages of data memory. Particularly in the case of Flash data storage, which allow only a limited number of erase cycles, thereby the total lifetime of the data memory can be increased.

p0036In the final step 27 of the method according <figref idrefs="f0001">FIG. 2</figref> the status bit S1 of the memory page j is set to zero. The status of the memory page j denotes the state 327 that the atomic transaction is completed and the memory page j is to use as current memory page for the virtual address a.

p0037In <figref idrefs="f0003">Fig. 4</figref> is shown a method 400 to 450 to the state examination or for the return of data after a power interruption, the out during an atomic transaction after the method <figref idrefs="f0001">FIG. 2</figref> occured. Such a process is usually performed at a restart of the chip card after a reset (forced reboot) or a power failure is performed to ensure that the data used are in a consistent state.

p0038In a first step 401, the management data, in particular at least the status data of all read out to be tested memory pages. A number n of pages for which the status data element has a value of (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.

p0039If an atomic write operation after <figref idrefs="f0001">FIG. 2</figref> interrupted prior to the step 24 of the setting bit S0 to 0 or after the step 27 of the setting bit S1 to the value 0, so no memory page exists at the level (1.0). If an interruption occurs during the step 25 of deleting the old memory page, two pages of memory with the status (1.0) may be present as a random shift from the state (0,0) to the state (1.0) by incomplete deletion is possible. In all other cases, an interruption of the atomic write operation is exactly in front of a storage site to the state (1.0).

p0040If branch 410 is in accordance with the number n = 1, from the corresponding memory page in a step 411 k, a reference k_alt read on the previous page. the status data element in the old site is k_alt From previous page in step 412 is read. Displays the status data element according to branch 413 that the old memory page has not yet been cleared, the old memory page is the index k_alt in step 424 is cleared and the index k_alt in the ring buffer is written (step 425). Regardless of the branch 413, the status bit S1 of the side k is set in step 426 to zero.

p0041Are 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 are read in a step 421st Based on the read seniority counters Ci and Cj is determined in a step 422, which has the two memory pages recently described. A seniority counter can thereby prove the Elder, when it corresponds to an erased state or if he is to be regarded as the elder according to the pre-established definition. In step 424 the older memory page is then deleted. The page index of the erased memory page is written in the step 425 in the ring buffer. Finally, turn the status bit S1 of the new memory page is set to zero with the step 426th

p0042If the evaluation of the number n by the branches 410 and 420 that no memory page with the value (1.0) is found in the status information element, so can still get a break immediately after step 23 from <figref idrefs="f0001">FIG. 2</figref> present. Therefore, it is checked in step 431 whether a memory page n exists, which is a state (1.1) and other management data, which are not deleted, respectively. Such side n is deleted in step 432 and the page index n in a step 433 in the ring buffer is written.

p0043Since the management data of the memory pages are read already in the step 401, at least partially, steps 431-433 alternatively in the step of reading out the four hundred and first

p0044Furthermore, it is to be noted that the steps 413 and 431-432 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 cleanup of the data memory by evaluating and treating these memory pages can therefore be independent of the return of data to atomic transactions.

p0045This in <figref idrefs="f0003">Fig. 4</figref> Illustrated method allows all the information that could be affected by an interruption during a simple hedged transaction, quickly and safely be attributed to a defined state.

p0046If there was an interrupt, usually a memory page is present with a status data element (1.0), since the step of erasing a memory 25 page by <figref idrefs="f0001">FIG. 2</figref> relatively long takes. This case can be dealt with quickly by evaluating the previous reference (steps 411-413).

p0047The rare event that happens to a second memory page also has the status of (1.0), thereby complicating that theoretically, the previous references of the two memory pages could refer randomly stacked. The seniority counter allows uniquely identifying and corresponding deletion of older memory page (steps 420-426).

p0048In <figref idrefs="f0004">Fig. 5</figref> the basic functional elements of a portable data carrier 50 are shown. As portable data carriers may for example be a smart card, a USB token or a SIM card for a terminal of a mobile radio system.

p0049In addition to a CPU 51, an interface 52 is provided that allows a contactless and / or contact-type communication to external components or, in the mobile data carrier which is arranged further components. A cryptographic unit 53 to perform cryptographic calculations and a detector or sensor 54 to detect external attacks against the mobile data carrier are also provided. As memory elements are provided, a volatile memory (RAM) 56, a not 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 via a line 55, preferably a bus, connected to each other. Optionally, the mobile data carrier on its own power supply.

p0050The memory segments of the data memory 58, as shown in <figref idrefs="f0005">Fig. 6</figref> shown, to be adapted according to the invention and / or, as in the <figref idrefs="f0001">FIG. 2</figref>. <figref idrefs="f0003">4</figref>. <figref idrefs="f0004">7</figref> or <figref idrefs="f0006">8th</figref> be used shown. A control software for executing a corresponding process can be stored in one of the memory elements 56 to 58.

p0051In <figref idrefs="f0004">Fig. 7</figref> is shown according to an embodiment of the present invention for a complex transaction sequence. The complex transaction summarizes a plurality of steps in which data can be written into memory segments in each case. The complex atomic transaction by<figref idrefs="f0004">Fig. 7</figref> is to, together with the return <figref idrefs="f0006">Fig. 8</figref> ensure that those affected by the complex transaction memory segments are either all or changed but all are unchanged.

p0052In a corresponding process 70 to 74 is first in a step 71 for each affected memory page the sequence of steps 21 to 23 from <figref idrefs="f0001">FIG. 2</figref> executed. For each affected store page so the reading of the counter of the page i, reading a new page index from the ring buffer and writing the new pages in the page runs j over the complex transaction. Only when the necessary steps have been completed the complex transaction itself, including all memory pages are written, the status bit S0 is set to zero in a step 72, the complex atomic transaction for each of the affected memory pages. Finally, a parent step 73 with the partial steps 25 to 27 of<figref idrefs="f0001">FIG. 2</figref> carried out for each affected memory page. The step 73 comprises a deletion of the old page, a letter from the old site index in the ring buffer and set the status bit S1 to zero in the new page.

p0053This in <figref idrefs="f0006">Fig. 8</figref> Method shown 800 to 850 for a complex status verification or for the treatment of interruptions in a complex atomic transaction is the procedure by <figref idrefs="f0004">Fig. 7</figref> adapted.

p0054The method begins with a loop 801, 823, 824, in which for all n memory pages of the status in step 802 is read out. Proceed to 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 to branch 811, the management information is already deleted. on the other hand has the status of the memory page the value (0.1) or the management data of the memory page is deleted, then 820 and 811 a corresponding memory page deleted according to branching in a step 821 and written to the page index in a step 822 in the ring buffer. If the status of the memory page (1,0), the index n of the memory page is stored at least in a list 831st

p0055The list thus comprises, for each memory page to be treated, at least the index, which is preferably formed by the physical or virtual address of the memory page. Other already read from the memory page management data, which are still used during the procedure, ie in particular of the previous reference (k_alt) and the seniority counters can also be stored in the list.

p0056After all of the memory pages are checked for their status 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 themselves as respective previous page. For such a case of conflict, the older memory page is determined by the seniority counters C1 and C2 of the conflicting memory pages in one step 841st

p0057In a loop of steps 842-847 then the list entries are processed individually. First, a pointer that points to the list entry to be currently processed is set to the first entry in the list (step 842). In a step 843 the older memory page is deleted and the page k_alt Index k_alt in a step 844 to the ring buffer written. Thereafter, the status S1 of the new memory page is set in a step 845 to zero. Steps 843-845 are processed by the transition to the next entry in the list in step 846 and the branch 847, is in the checked the bottom of the list for all entries in the list.

p0058The steps 810, 811 and 820-822 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 cleanup of the data memory by evaluating and treating these memory pages can therefore be independent of the return of data to atomic transactions.

p0059To manage the virtual addresses of memory segments a table can be used.

p0060Such a table can be kept in the volatile or non-volatile memory, and assigns a virtual address used to index a memory page or the physical address. All access to user data in the memory segments must then be carried out on the corresponding table. At power up of a mobile data carrier with a corresponding number of flash memory pages, this table is generated in the RAM, by checking all flash memory pages.

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

p0062If 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, it is a free memory page. The corresponding page index is stored in a memory element or in a ring buffer in the RAM.

p0063All other conditions are fed back through the process for handling interrupts on these two basic conditions described above.

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

p0065Administrative expenses by an addressing table, by using memory segments, as in <figref idrefs="f0005">Fig. 6</figref> are shown to be avoided.

p0066In <figref idrefs="f0005">Fig. 6</figref> are control, address and data lines 611-618 shown, which are connected to a flash memory page six hundred and first The memory page 601 has, for example 1x32 Bit administrative data and 64x32-bit payload. is merely indicated that in addition to the page memory 601 further memory pages 602 are arranged in the corresponding data store, which are each formed accordingly.

p0067For the memory page 601 means for activating or releasing the memory page 621 are provided to 626 for access to the storage site. Before describing the details of the activation means 621 to 626, first, the basic behavior of the memory page is described in the activated state in response to the applied signals.

p0068For the signal to a control line 611, which indicates a read access, and the signal of a control circuit 612, indicating a write access, specifies the signal to a control line 615 if you want to access the user data or the management data of the memory page either. If the signal is asserted on the control line 611, the addressed via the address line 617 to the low signal data is output to the data line 618th If, however, the signal of the control line 612 is set, the value which is currently on the data line 618 is written to the memory page.

p0069If the signal is set to a control line 613, the entire memory page 601 is 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 address (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 encoding 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.

p0070The memory page 601 is disabled when the enable signal "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 effect described above.

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

p0072Is referenced by the address line 616, the memory page 601, so an OR gate 622 and a NOR gate 623 is an AND gate 621, determines whether the memory page for erasing, reading or writing in accordance with one of the control signals 611 to 613 enabled and activated. The memory page is enabled for access via the OR gate 622, when the control signal 614 indicates a direct addressing via a physical 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 is present.

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

p0074In the following individual aspects of the described embodiments are addressed in order to illustrate how these embodiments can be further modified.

p0075The embodiments described with reference to the figures are adapted for a flash memory page, which allows fast writing a value "1" to a value "0" and on the other hand slower deleting from the value "0" to the value "1" is required , However, the solutions specified are also readily on a memory having to inverse behavior (fast writing of "0" to "1" and slow deletion of "1" to "0") transferable.

p0076To illustrate the access times starting from 60 microseconds for a write access and 8000 microseconds for erasing a memory page. After at least the internal state of the art, an atomic write operation using a recirculation buffer is done by backing up 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.

p0077By the procedure according to <figref idrefs="f0001">FIG. 2</figref> the duration of an atomic write operation will 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 time in 12020 microseconds.

p0078While solutions of the invention achieve a greater benefit in saving such as flash EEPROM, which have a long erase time, but they can also be applied to EEPROM, S-RAM or other non-volatile data storage.

p0079In the method according to <figref idrefs="f0003">Fig. 4</figref>. <figref idrefs="f0004">7</figref> and <figref idrefs="f0006">8th</figref> must follow the steps to apply to all memory pages (for example, see Read 401 Search 431) are performed only for the memory pages that are provided for a corresponding method. A data store can thus comprise a first set of memory pages is provided for a secured letter, and a second set of memory pages, which is not intended for atomic writes. In such a data store, for example, could only the memory pages of the first group with activating agents to<figref idrefs="f0005">Fig. 6</figref> be equipped.

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

p0081In portable data carriers unpowered erasure of memory pages is preferably carried out as described. reduce example, by the processing time of a complex transaction, the steps of erasing a memory page can be initially omitted. The memory pages concerned must then, instead of being deleted, with a status "to delete" are provided. Given the status of data is extended to a corresponding bit, which signals this status in the written state. At an appropriate later date to delete memory pages will be deleted.