WO2005093580A1 - Garbage collection for smart cards - Google Patents

Abstract

The invention relates to a method for searching a dynamically allocated heap space for referenced or non-referenced objects, during which a search of the heap space is carried out by means of an algorithm that operates without recursion. Said method can be used in particular for automatic garbage collection. For the recursion-free algorithm, the space requirement necessary to execute the algorithm can be determined before the run-time. The method is therefore particularly suitable for computer systems with limited memory resources, such as e.g. smart cards. The invention relates to a corresponding data carrier, in particular a smart card, e.g. Java card, for which the method is implemented.

Description

Garbage ( ^"garbage CoUection) for smart cards

The invention relates to a method for automatic garbage collection, in particular a tracing collector, and a method used to search dynamically allocated heap memory for referenced or non-referenced objects, in particular for computer systems with low system resources (data carriers), such as e.g. Smart cards (chip cards) and a corresponding data carrier.

A data carrier, in particular a smart card, in particular a Java card, typically has a microprocessor, several memories, e.g. ROM, EEPROM and RAM, whereby ROM and / or EEPROM can be partially or completely replaced by flash memory, and one or more interfaces.

A program running on a computer system (computer program) allocates memory, i.e. Allocates working memory in which the individual program code commands of the program are executed.

The working memory can be divided into a statically allocated memory and a dynamically allocated heap memory. The statically allocated memory is allocated before the program is run, e.g. while compiling or linking the program, whereas the dynamically allocated heap memory is allocated during the runtime of the program, i.e. while the program code is running.

Statically allocated memory includes - at least in part - the stack memory on which e.g. Variables are created when methods (e.g. algorithms) are called. Such methods can, for example, be methods that deal with automatic garbage collection (see below).

With object-oriented programming languages such as Java ™ from Sun Microsystems, the dynamic allocation of working memory is performed in such a way that objects are created in the heap memory (usually with Java Cards in the EEPROM or possibly flash memory).

Each object can contain one or more references to other objects, which in turn can have references to other objects. Due to the references of objects to other objects, the objects in the heap memory have a tree-like organizational structure (tree structure).

Such a tree-like organizational structure, which is also called a heap structure, is shown in FIG. 1. The root object is arranged at the root (Root) or in other words at the zero hierarchy level of the organizational structure, that is to say the object with the number one (1) in FIG. 1. In the case of differently designed heap structures, there can alternatively be several root objects, which are then also referred to as start objects, with each root object or start object starting from its own tree-like organizational structure. Each reference to an object starting from the root object represents the entrance to a branch of the tree structure. In the heap structure of FIG. 1, six objects 2, 20, 14, 26, 25 and 35 are referenced starting from the root object 1 so that the heap structure has six branches. All objects that are directly or indirectly connected to the root object (called referenced objects) via the tree-like organizational structure can be accessed from the root object. Objects not referenced, i.e. Objects that have no connection to the root object via references cannot be reached from the root object. In Fig. 1 e.g. objects 31, 32, 33, 29, 30, 23 and 24 not referenced and therefore not accessible from the root object.

The objects that are directly referenced from the root object form the objects of the first hierarchy level. The objects referenced by objects of the first hierarchy level form objects of a second hierarchy level etc. Each branch of the tree structure has a depth which is equal to the number of levels below the zero hierarchy level (root level) in this branch is. In Fig. 1 e.g. the depth of the

Branch from object 1 to object 5 is four, the depth of the branch from object 1 to Object 7 also four, the depth of the branch from object 1 to object 8 three etc.

With reference to FIG. 1, a forward-looking heap structure is organized in such a way that for every given object (for example, an object of an i-th hierarchy level), every object referenced by the given object (consequently an object of the (i + 1) -th hierarchy level ) has a larger index than the specified object of the i-th hierarchy level. Under certain circumstances, however, it can happen that a heap structure with backward references is created. A backward reference is characterized by the fact that an object (an i-th hierarchy level) has a higher index than an object referenced by this object (the underlying (i + l) -th hierarchy level). In the heap structure of FIG. 1, for example, there is a backward reference between the pair of objects (9, 6). Because object no. 9 of the second hierarchy level has a higher index than object no. 9 referenced by object no. 9 of the third hierarchy level below. Likewise, between the object pairs ((i), (i + 1)) = (9, 8), (40, 37), (40, 38), (38, 36), (35, 34) and ( 34, 19) of the referencing object (i) and referenced object (i + 1) each have a backward reference.

Heap memory that is no longer used (dynamically allocated working memory) must be released (deallocated) so that heap memory is available again for new objects. In the case of object-oriented programming languages, the storage space occupied by non-referenced objects can and should be released, since these objects are no longer accessible anyway and are therefore "garbage".

A number of object-oriented programming languages, for example Java, Smalltalk, Eiffel, Oberon, Perl, Python, Visual Basic and others, have an automatic garbage collection, in which non-referenced objects are recognized and the dynamically allocated heap occupied by them - Memory is automatically released again. The simplest form of automatic garbage collection is the Reference Counting Garbage CoUection or the Reference Counting Collector, in which each object contains a reference counter. The counter reading of the reference counter indicates how many references are directed to the object. The counter reading is incremented by one for each reference to the object generated, and the counter reading is counted down by one for each deleted reference to the object. Objects whose reference counter has a counter reading of zero are classified as garbage and deleted, or the memory space occupied by the garbage objects is allocated to the freely available heap memory.

In addition to reference counting collectors, there are tracing collectors in which references are traced from the root class of the heap memory ("traced").

The mark-and-sweep collector is the basic algorithm for garbage collections of the Tracing Collector type. With the mark-and-sweep collector, the heap memory is first searched for references in the so-called mark phase, whereby objects to which no references were found are identified and marked. The search for references begins at the root object of the heap memory and works from there hierarchically through the entire heap memory. The objects marked in the mark phase are deleted in the subsequent sweep phase.

With two other forms of automatic garbage collection (tracing collector), the compacting collectors and the copying collectors, the heap memory is additionally defragmented during the garbage collection.

Both Compacting Collectors and Copying Collectors start with one

Searching the heap memory for references, only that the non-refe- referenced "dead" objects are searched for, but the "living" objects to which references are still directed (referenced objects).

With Compacting Collectors, the referenced objects found ("living" objects) are moved to one end of the heap memory and compacted there. This creates a large contiguous memory area at the opposite end of the heap memory. Then all references to moved objects are updated.

With Copying Collectors, all found ("living") objects found are copied from their previous old storage area into a new storage area and are joined together without gaps. As a result, the new memory area is contiguous, i.e. defragmented. The old memory area is declared as a freely available memory area.

Up to now, automatic garbage collection procedures - with exceptions - have mainly been limited to extensive computer systems. For computer systems with low system resources such as Smart cards often do not have enough memory for automatic garbage collection.

In the current method for searching the heap memory for referenced objects, which is illustrated in FIG. 1, and which is used in the mark-and-sweep garbage coUection, the individual branches of the heap structure are successively started, starting from the root object Searched referenced objects, whereby each found referenced object is marked as a referenced (and therefore accessible) object. According to FIG. 1, a corresponding search and marking algorithm is first called for searching and marking for the root object and the root object (object 1 in FIG. 1) is marked. Then, one after the other for each branch, the search and marking algorithm is called recursively for all hierarchy levels below the zero hierarchy level (root level) until the end of the branch is reached. In Fig. 1, for example, the search for the first branch and marking algorithm called recursively for object 2 of the first hierarchy level, for object 3 of the second hierarchy level, for object 4 of the third hierarchy level and finally for object 5 of the fourth hierarchy level. Subsequently, in the example of FIG. 1, the sub-branch is searched, which extends from object 2 to object 7, the algorithm being called up recursively again. Finally, in the example of FIG. 1, the branch that extends from object 1 to object 19 is searched. The maximum depth of the tree of FIG. 1 is five and is realized in the branch that extends from object 1 to object 36.

In the example from FIG. 1, objects 31, 32, 33, 29, 30, 23 and 24 are not referenced and are therefore “garbage”.

The memory requirement for a recursive algorithm such as that described above, in which the algorithm is called up again and again within the algorithm, cannot be determined in advance, as is explained below. This is one of the reasons why the conventional recursive algorithm is usually not readily available on a computer system with low system resources, e.g. a smart card is transferable.

Each object in a tree structure requires a single bit, i.e. 1/8 byte, for a flag that indicates whether the object is referenced or not. A tree structure with n objects therefore requires n / 8 bytes of memory (statically allocated working memory) for marking the objects as referenced or not referenced. When the search and marking algorithm is applied to a branch of the tree structure, a number of v bytes is used for local variables for each call of the algorithm and thus for each hierarchy level. A branch of depth d 'therefore requires a number of d' * v bytes of memory for variables. It must be taken into account here that the variables of a branch that has already been completely searched can be overwritten again when the next branch of the tree structure is searched, since the individual objects of the searched branch are yes are already marked as referenced or not referenced. The depth of the branch of the tree structure with the maximum depth d is relevant for the memory requirement for variables.

So for a tree structure like the one shown in Fig. 1, let n: = number of objects in the tree structure d: = maximum depth of the tree structure v: = number of bytes used in the algorithm for local variables (constant per algorithm - Call) rc: = memory requirement in bytes.

Then for the memory requirement rc of the algorithm in bytes, rc - n / 8 + d * v (1)

The memory requirement of the recursive search and marking algorithm therefore depends on the maximum depth of the tree structure, which is still unknown until the tree structure has been completely searched. Consequently, the storage requirements of the conventional recursive search and marking algorithm, which e.g. When using conventional mark-and-sweep garbage coUection, do not determine in advance, before searching the tree structure and thus before the runtime of the algorithm.

For computer systems with generously dimensioned system resources (memory and / or computing power) such as PCs, workstations or servers are assigned a large amount of working memory, in particular stack memory, to a recursive search and marking algorithm when in doubt.

Especially for computer systems with low system resources, e.g. Smart

Cards, the total available memory may not be sufficient to Allocate plenty of memory when in doubt. Therefore, it is desirable to know in advance the memory requirements of an automatic garbage collection algorithm in order to determine whether the algorithm is executable on the computer system at all, that is to say it can be executed, and to prevent the memory from overflowing and consequently during Execute the algorithm.

Proceeding from this, the invention is based on the object of creating a method for automatic garbage collection and a method used for searching dynamically allocated heap memory for referenced or non-referenced objects, in which the memory requirement (memory requirement) for performing the garbage collection in advance, before executing the procedure.

The object is achieved by a method according to the independent method claim. Advantageous embodiments of the invention are specified in the dependent claims.

In the inventive method according to claim 1, objects are created in dynamically allocated heap memory. Objects on the heap memory that can no longer be reached are to be found using the method according to the invention, which systematically searches the heap memory for this purpose. According to independent claim 1, the search of the heap memory is carried out by means of an algorithm which works without recursion.

Because no recursion is carried out, the algorithm is only called once, without being called again within the algorithm in a nested manner. The number of v bytes that the algorithm for local variables requires is determined in advance as required and is therefore known even before the algorithm limit is called. Since the algorithm is called only once, the algorithm for local variables only needs a total of only exactly one time v bytes (instead of maximum depth of the tree structure times v bytes in the conventional recursive method). Therefore, in the method according to the invention, the memory requirement for executing the algorithm is known in advance.

Therefore, according to claim 1, a method is created in which the memory requirement (memory requirement), in particular the need for statically allocated or allocable memory (memory) for the method can be determined in advance, before the execution of the method, which is specifically for Systems with limited memory resources, such as Smart cards, is very beneficial.

Referenced objects found using the algorithm are preferably marked so that the remaining non-referenced objects can be deleted in a subsequent step, e.g. by declaring the space occupied by the non-referenced objects as freely available heap space. Deleting the non-referenced objects or releasing the memory occupied by them can be done in a sweep step, as with the mark-and-sweep procedure. Alternatively, the referenced objects found can be saved, as with the Compacting Collector or the Copying Collector, and the remaining memory can be declared as freely available heap memory. Optionally, the memory is additionally defragmented during the garbage collection.

Each object is preferably assigned a unique object index, the object indices of all objects in the heap memory specifying a unique sequence of the objects. According to the algorithm, the objects of the heap memory are searched in the order of their object indices, regardless of any underlying heap structure. The object index can e.g. be a number or an alphabet letter or a linear address or another index that forms a clear sequence with other numbers, alphabet letters etc.

The objects are preferably numbered in the heap memory and are searched in the order in which they are numbered. By numbering everyone Object is assigned a unique object index with which the object can be uniquely addressed. In addition, each object index has a unique successor, so that the object indices of all objects in the heap structure define a unique order of the objects.

In the case of the algorithm with objects with object index or numbering, the heap memory is searched strictly for the object index or numbering of the objects, regardless of whether a branch of the heap structure is searched to the end or not. In contrast, in the conventionally used conventional algorithm, the heap memory is searched in each

Branch of the heap structure according to which the heap memory is organized is carried out to the end of the respective branch before the search for the next branch is started, regardless of the numbering or indexing of the individual objects.

If the heap memory is free of backward references - or in other words if the heap memory is strictly forward-oriented - it is sufficient to search the memory once in the order of the object indexes or the numbering of the objects, preferably starting with as Start object used root object, for example in an embodiment like that shown in FIG. 3 with the number 1, up to a last object, according to FIG. 3 for example with the number 40. If the root object has the highest number, the search is e.g. Started at the highest number and continued to the object with the lowest number (e.g. one or zero). In this case, found referenced objects are preferably marked, so that the non-referenced objects remain. This can be followed by a cleanup step as described above.

Alternatively, a heap memory that is forward-oriented with respect to the object indexes or numbering is searched exactly twice according to the algorithm, the second time of the search being carried out to check that the algorithm limit can be ended. If the heap memory has one or more backward references, ie if the heap memory has at least one pair of referencing object (i) and referenced object (i + 1) with respect to the object indexes or numbering of its objects, which pair have a backward reference (backward-pointing) Reference relationship), the heap memory is preferably searched at least twice.

In the event that it has at least one backward reference, the heap memory is preferably searched in succession at least once forwards and once backwards.

Alternatively, a heap memory which has at least one pair of referencing object ((i)) and referenced object ((i + 1)) with respect to the object indices or numbering of its objects, which have a backward reference to one another, is at least three times searches, the last time (e.g. the third time) of the search being performed to check that the algorithm can be ended.

Each referenced current object found using the algorithm (current object in contrast to objects referenced by this current object) is preferably marked. It is further preferred that the method is ended as soon as a search of the entire heap memory has been carried out, in which no marking has been carried out. Optionally, after a run in which no marking has been carried out, the search is run again as a test run in order to check whether there are actually no more markings to be made. In both cases, in other words, from the fact that an idle operation has been carried out with no markings, it is recognized that the method can be ended. In the case of a strictly forward-oriented heap memory, the repeated run, ie the test run, is preferably that second pass. In the case of a heap memory with at least one backward reference, the repeated run, ie the test run, for example the third run of searching the heap memory, is more generally the last run. The heap memory is searched several times alternately forwards and backwards as required. The algorithm is called up only once each time a search is carried out, so that the memory requirement (need for statically allocated working memory, in particular stack memory) can be determined in advance for the algorithm. Each time the search is run through again, the memory space that the algorithm occupied during the previous run can be overwritten again. Therefore, the memory requirement does not increase with the number of memory search runs performed. In particular, backward references in heap memory, which require repeated searches of the heap memory, alternately forward and backward, do not lead to an increase in the memory requirement.

More preferably, the marking of an object is carried out in each case using a marking field provided in a memory which, for example, uses a predetermined number of bits or bytes in a memory which is accessible to the algorithm, e.g. in the statically assigned stack memory.

According to a preferred embodiment, the marking field for the current object has a first data field and a second data field, the first data field (valid) being marked if the current (found) object is referenced and the second data field (scanned) being marked , if all referenced objects originating from the current object are marked as referenced by marking the first data field (valid) for these referenced objects. Each data field can be designed as a flag, for example. The flag is switched to mark the object, i.e. set or deleted depending on the implementation. The marking field according to the invention is preferably provided in RAM (Random Access Memory), in contrast to conventional methods for searching a heap memory. In conventional methods for searching a heap memory, in order to mark an object as referenced, a flag is set (switched) in the header of the object, as is schematically illustrated by FIG. 2. Since the header of the object is usually provided in the EEPROM, the conventional flag is also provided in the EEPROM. As a result, the conventional flag is slow and burdensome for the memory resources of a data carrier (smart card, chip module, chip, etc.) in which the method is used (EEPROM can only be overwritten a limited number of times). The method with the preferred marking field according to the invention in RAM therefore has the additional advantage that it is particularly fast, since the writing time of a RAM is significantly shorter than that of an EEPROM. In addition, the method with the preferred marking field according to the invention in RAM is particularly gentle on the memory resources of a data carrier to which the method is used.

Further preferably, objects found by means of the algorithm, to which no or no reference has been found, are not marked. The algorithm simply skips each such object, possibly until it encounters the object again when the search is repeated.

The method is preferably used in a data carrier such as a smart card, in particular a Java card, or an arbitrarily shaped token or in a chip module for installation in a data carrier or other object or in a chip for installation in a chip module or a data carrier etc. The data carrier or the chip module or the chip preferably has a microprocessor and a plurality of memories (ROM, EEPROM, RAM, possibly flash). The algorithm is preferably implemented in the ROM, possibly alternatively in a flash memory. A working memory, in particular a stack memory in the RAM of the data carrier, is statically assigned to the algorithm, the required size of which is different can be calculated before the runtime in the method according to the invention. The marking field is preferably implemented in RAM, preferably in stack memory.

The invention is explained in more detail below on the basis of exemplary embodiments and with reference to the drawing, in which:

1 shows a tree-like organized heap structure, on the basis of which the mark phase of a garbage collection method (garbage coUection) according to the prior art is illustrated;

2 shows a schematic illustration of an object header stored in the EEPROM of a Java Card, in which references to data likewise stored in the EEPROM are stored, according to the prior art;

3 shows a heap structure organized in a tree-like manner similar to that shown in FIG. 1, on the basis of which the mark phase of a garbage collection method (garbage coUection) according to an embodiment of the invention is illustrated, relating to a first status of the process during the search of the heap memory;

FIG. 4 shows a marking field with two data fields “Valid” and “Scanned” for each object of the heap structure shown in FIG. 3, with markings that correspond to the process status shown in FIG. 3;

FIG. 5 shows the heap structure from FIG. 3 for a second process status during the search of the heap memory; FIG.

FIG. 6 shows the marking field from FIG. 4, with markings that correspond to the process status shown in FIG. 5; FIG. 7 shows the heap structure from FIG. 3 at a third status during the search of the heap memory; FIG.

8 shows the marking field from FIG. 4 with markings which correspond to the process status shown in FIG. 7.

3 shows a tree-like organized heap structure, by means of which the search of a heap memory for references, in particular during the mark phase of a garbage collection method (garbage coUection) according to one embodiment of the invention, is illustrated for a first status of the process during the search of heap memory.

The heap memory has 40 objects, which are numbered consecutively from 1 to 40, the object with the number "1" being the root object. Two data fields are provided for each object in order to mark the object , namely a "valid" data field and a "scanned" data field.

In the algorithm according to the preferred embodiment, in which the objects are searched in the order of their numbering, the memory requirement can be determined before the algorithm expires, as shown below.

For a tree structure like the one shown in Fig. 3, let n: = number of objects in the tree structure v: = number of bytes used in the algorithm for local variables (constant per algorithm call) rc: = memory requirement in bytes ,

Then for the memory requirement rc of the preferred algorithm according to the invention in bytes, rc = (2 * n + 8) / 8 + v (2)

The term (2 * n + 8) specifies the number of bits (1/8 bytes) required for the "valid" and "scanned" data fields (valid flags and scanned flags) for the n objects in the heap Structure are required. The term v specifies the memory requirement in bytes for local variables and appears only once, since the algorithm is called only once per pass through the search of the heap memory.

The maximum number n _ma χ of objects that can be accommodated in a memory of size rc can be determined in advance from equation (2):

An exemplary recursion-free algorithm 1 is given below, in which the method according to the invention for searching a heap memory and for marking found referenced objects is implemented. Let n be the number of objects in heap memory. In addition, let an object list be created in which a marking field (shown schematically in FIG. 4) with two data fields is provided for each object, namely a data field for a valid flag and a data field for a scanned flag. Then the exemplary search and marking algorithm is:

markValidObjects (int rootObjectlndex, int numberOfObjects)

{// reset all flags (valid and scanned) resetFlags (); // mark root object as valid setValid (rootObjectIndex); .11 scan all objects for (i = l; i <= numberOfObjects; i ++) {// is valid flag of object i set and scanned flag not yet set? // (is the valid flag of object i set and the scanned flag not yet?) if (isValid (i) && üsScanned (i)) {// mark all referenced objects of i as valid // (all referenced by object i Mark objects as valid) for (j = 0; j <object ist [i] .numberOfReferences (); j ++) {// mark referenced object j as valid // (mark referenced object j as valid) setValid (objectList [i] .getReferenceIndex (j)); } // all references of object i are scanned => set scanned flag of object i // (all references of object i have been scanned => // => set scanned flag of object i) setScanned (i); }

(Algorithm 1)

In the preceding algorithm 1, the two data fields of the marking field are designed as a valid flag and a scanned flag (cf. FIG. 4). The valid flag of an object is set when the object is referenced. The scanned flag is set when all references originating from this object have been searched. The objects are numbered from 1 to n, whereby the object numbered 1 is the root object (start object). After running the algorithm, the object list has the shape shown in FIG. 4 and the heap structure has the shape shown in FIG. 3.

In any case, the root object (i = 1) is considered referenced and is set to be valid as a confirmation. Optionally, there can be several root objects. In this case, all root objects are initially set as valid. Then, in the "loop, all objects referenced by the root object are set as valid to mark that these objects are referenced.

The scanned flag of the root object (i = 1) is then set to mark that all references originating from the root object have been scanned (searched).

Now algorithm 1 proceeds from the root object (i = 1, i.e. object index 1) to the object with the next higher object index, i.e. to object no.2, and checks whether object no.2 is valid, i.e. whether its valid flag is set. If the valid flag of object no. 2 (different from FIG. 3) is not set, algorithm 1 proceeds directly to object 3. If, on the other hand, the valid flag of object no. 2 is set (as in FIG. 3) all references going out from object 2 are searched and the objects referenced from object 2 are marked as valid. Finally, the scanned flag of object 2 is set, and then algorithm 1 proceeds to object 3.

The method is carried out up to the last object of the heap (in FIG. 3 object 40). FIG. 4 shows the assignment of the valid flags and scanned flags of the marking field for the heap structure from FIG. 3 after algorithm 1 has been applied to the heap structure.

In the example of FIG. 3, the heap structure has backward references, which means that not all objects of the heap structure can be checked if only a single pass through the search of the heap is carried out. For example, there is a backward reference between the pair of objects (6, 9). In other words, the object 9 of the second hierarchical level has a higher object index than the object 6 of the third hierarchical level. For this reason, when the algorithm 1 proceeds from object 5, which should already be marked as valid and scanned, to object 6, the object 6 is not yet marked as valid. Consequently, the references originating from the object are not scanned, but the algorithm 1 proceeds go straight to object 7, from there to object 8 and on to object 9. Objects 6, 7 and 8 remain unmarked, ie neither the valid flag nor the scanned flag is set. Only object 9 is valid again. Objects 6 and 8 are therefore marked as valid and then object 9 is marked as scanned. The scanned flags of objects 6 and 8 do not remain set (see also FIG. 4). In object 7, the valid flag and the scanned flag are both not set (see FIG. 4).

Objects in the heap structure that have backward references can be checked by alternating the heap memory forward as often as required (from 1 to 40 in FIG. 3) and backward (from 40 to FIG. 3) 1) is searched.

While FIG. 3 shows the heap structure after the heap has been searched forward once by applying algorithm 1 to it, FIG. 5 shows the same heap structure after the heap memory has additionally been searched backwards is. 5 shows the heap structure after an algorithm 2 has been applied to it, e.g. the following:

markValidObjjekte (int rootObjectlndex, int numberOfObjects) {// reset all flags (valid and scanned) resetFlags ();

// mark root object as valid setValid (rootObjectIndex);

// scan all objects forward for (i = l; i <= numberOfObjects; i ++) {// is valid flag of object i set and scanned flag not yet set? // (is the valid flag of object i set and the scanned flag not yet?) if (isValid (i) && üsScanned (i)) { // mark all referenced objects of i as valid // (mark all objects referenced by object i as valid) for (j = 0; j <objectList [i] .numberOfReferences (); j ++) {// mark referenced object j as valid // (mark referenced object j as valid) setValid (objectList [i] .getReferenceIndex (j)); } // all references of object i are scanned => set scanned flag of object i // (all references of object i have been scanned => // => set scanned flag of object i) setScanned (i);

}

// scan all objects backward for (i = numberOfObjects; i> 0; i ~)

{// is valid flag of object i set and scanned flag not yet set? // (is the valid flag of object i set and the scanned flag not yet?) if (isValid (i) && üsScanned (i)) {// mark all referenced objects of object i as valid // (all by object i mark referenced objects as valid) for (j = 0; j <objectList [i] .numberOfReferences (); j ++) {// mark referenced object j as valid // (mark referenced object j as valid) setValid (objectList [i] .getReferenceIndex (j)); } // all references of object i are scanned => set scanned flag of object i // (all references of object i have been scanned // => set scanned flag of object i) setScanned (i); }

} (Algorithm 2)

Algorithm 2 comprises a forward pass (forward scan) through the heap memory, which essentially corresponds to that of algorithm 1, and a backward pass (backward scan). When algorithm 2 was run backwards, the scanned flags were set in particular for objects 6 and 8 that had not yet been set after the forward run. The valid flag was set for object 7 during the reverse run. The flags set in addition to the forward pass during the reverse pass are also shown in FIG. 6, in which the check box of FIG. 4 is shown after a reverse pass has additionally been applied to the heap memory.

In a preferred algorithm 3 specified below, a binary third data field “end flag” is additionally used, which is switched as soon as a

Pass through the heap scan where no tag was made. After running through algorithm 3, the object list has the shape shown in FIG. 8 and the heap structure has the shape shown in FIG. 7.

markValidObjects (int rootObjectlndex, int numberOfObjects)

{// reset all flags (valid and scanned) resetFlags ();

// define endFlag (definition of the binary end flag) boolean endFlag;

// mark root object as valid setValid (rootObjectΙndex); do { // assume that this is the last scan endFlag = true;

// scan all objects forward for (i = l; i <= numberOfObjects; i ++)

{// is valid flag of object i set and scanned flag not yet set? // (is the valid flag of object i set and the scanned flag not yet?) if (isValid (i) && üsScanned (i)) {// mark all referenced objects of i as valid // (all referenced by object i Mark objects as valid) for (j = 0; j <objectList [i] .numberOfReferences (); j ++) {// mark referenced object j as valid // (mark referenced object j as valid) setValid (objectList [i]. getReferenceIndex (j));

// we have to do another run (scan) // (another pass is required because a // mark has been made) endFlag = false; } // all references of object i are scanned // => set scanned flag of object i // (all references of object i have been scanned // => set scanned flag of object i) setScanned (i); }} if (endFlag = true)

{// this was the last scan break; }

// assume that this is the last scan endFlag = true;

// scan all objects backward for (i = numberOfObjects; i> 0; i—) {// is valid flag of object i set and scanned flag not yet set? // (is the valid flag of object i set and the scanned flag not yet?) if (isValid (i) && ÜsScanned (i)) {// mark all referenced objects of object i as valid // (all by object i mark referenced objects as valid) for (j = 0; j <objectList [i] .numberOfReferences (); j ++) {// mark referenced object j as valid // (mark referenced object j as valid) setValid (objectList [i] .getReferenceIndex (j));

// we have to do another run (scan) // (another pass is required because a // mark has been made) endFlag = false; } // all references of object i are scanned // => set scanned flag of object i // (all references of object i have been scanned => // => set scanned flag of object i) setScanned (i); }}} while (endFlag = false)

(Algorithm 3) The above algorithm 3 searches the heap memory alternately forwards and backwards until a scan scan of the heap memory has been carried out in which no marking has been made. This is realized by the (do, while) loop, which has as a condition for the continuation that the end flag is switched to the boolean value "false". Only if no marking (valid flag) has been made in one run the end flag remains set to the Boolean value "true" and the (do, while) loop and thus the algorithm is ended.

FIG. 7 shows the heap structure from FIGS. 1 and 3 after algorithm 3 has been applied to the underlying heap memory, and FIG. 8 shows the associated object list. All objects in the heap structure are already marked as valid. The state according to FIGS. 7 and 8 is also the state at the start of the last run of the (do, while) loop of the algorithm 3. Since no marking is made on a valid flag during this run, the end flag remains set to true so that the (do, while) loop ends after this last pass.

With the method that is implemented by the algorithm 3, all (still) referenced objects can thus be found for a heap memory whose heap structure has backward references. 7 and 8, only the non-referenced objects 31, 32, 33, 29, 30, 23, 24 with an unmarked valid flag are left. All referenced objects are marked.

Claims

Patent claims 1. A method for searching dynamically allocated heap memory for referenced or non-referenced objects, in which a search of the heap memory is carried out by means of an algorithm which works without recursion. 2. The method of claim 1, wherein each object is assigned a unique object index, wherein a unique order of the objects is determined by the object indices of all objects of the heap memory, and wherein according to the algorithm, the objects of the heap memory in the order of their object indexes be searched. 3. The method of claim 1 or 2, wherein the objects in the heap memory are numbered, and wherein according to the algorithm, the objects of the heap memory are searched in the order of their numbering. 4. The method according to claim 2 or 3, wherein the heap memory is forward-oriented with respect to the object indexes or numbering, and wherein the heap memory is searched exactly once according to the algorithm. 5. The method of claim 2 or 3, wherein the heap memory is forwarded with respect to the object indexes or numbering, and wherein the heap memory is searched exactly two times according to the algorithm, the second time of the search being carried out to check that the algorithm can be ended. 6. The method according to claim 2 or 3, wherein the heap memory has at least one pair of referencing object ((i)) and referenced object ((i + 1)) with respect to the object indices or numbering of its objects, which have one another Have backward reference, and the heap is searched at least twice. 7. The method according to claim 2 or 3, wherein the heap memory with respect to the object indices or numbering of its objects has at least one pair of referencing object ((i)) and referenced object ((i + 1)), which have a backward reference to each other , and wherein the heap memory is searched at least three times, the last, in particular third, time of the search being carried out to check that the algorithm can be ended. 8. The method according to any one of claims 2 to 7, wherein the heap memory starting with a start object (1), which has a lowest object index (1), to an end object (40), which has a highest object index ( 40) is searched. 9. The method according to any one of claims 2 to 8, wherein the heap memory starting with an end object (40), which has a highest object index (40), to a start object (1), which has a lowest object index ( 1) is searched. 10. The method according to claims 8 and 9 in connection with each other, wherein the heap memory at least once from the start object (1) to the end object (40) and, in reverse order, from the end object (40) to Start object (1) is searched. 11. The method according to any one of claims 1 to 10, wherein each referenced current objects found by means of the algorithm is marked. 12. The method of claim 11, wherein the method is terminated once a full heap sweep has been performed that has not been marked. 13. The method according to claim 11 or 12, wherein the marking is carried out using a marking field accessible to the algorithm. 14. The method according to claim 13, wherein the marking field is provided in a volatile memory, in particular in a RAM memory. 15. The method according to claim 13 or 14, wherein a marking field is used for marking, which has a first data field (valid flag) and a second data field (scanned flag) for the current object, and wherein the first data field (valid flag ) is marked if the current object is referenced, and the second data field (scanned flag) is marked if all referenced objects originating from the current object are marked as referenced by the fact that the first data field (valid- Flag) is marked. 16. The method according to claim 15, wherein the method is ended as soon as a run through the search of the entire heap memory has been carried out, in which no marking of a first data field (valid flag) has been carried out. 17. The method according to any one of claims 1 to 16, wherein objects found by means of the algorithm, to which no or no reference has been found, are not marked and / or ignored. 18. The method according to any one of claims 1 to 17, wherein the heap memory is provided in a non-volatile memory, in particular EEPROM memory. 19. Data carrier, in particular chip card, in particular Java card, or chip module or chip for installation in a data carrier, with a microprocessor, at least one memory and a method implemented in the data carrier according to one of claims 1 to 18.