JC101-5C: Data management and transactions

The Java Card framework is very limited, and it does not include any container classes. A simple way to organize data is to use linked lists. This structure is very classical, so we will use this opportunity to discuss the way in which Java Card manages the atomicity of updates.

Atomicity in Java Card

Some of the Java Card data is persistent, and it is stored in some kind of mutable persistent memory, often EEPROM. Updating this memory requires energy, and the smart cards use an outside energy source. This means that an update operation may be interrupted unexpectedly, possibly yielding an undetermined result.

Since Java Card developers do not have access to low-level memory management primitives, the Java Card Runtime Environment (JCRE) needs to handle these issues. Therefore, all persistent memory updates performed in Java Card are guaranteed to be atomic: either an update is entirely performed, or it is not done at all; a memory cell is never left in an undetermined state. For the developer, this atomicity guarantees also implies that the write operations will always be performed in the order specified by the program execution.

In addition to this basic guarantee, Java Card includes a basic transaction mechanism. The transaction word can be misleading; what Java Card defines has nothing to do with a payment transaction, and it has very little to do with a database transaction. A Java Card transaction is simply a way to group several persistent memory updates in a single atomic operation: either all the updates in the transaction are performed, or none of them are performed.

The API is very simple. A transaction is started with JCSystem.beginTransaction, and it is ended with JCSystem.commitTransaction. There is also a way to abort a transaction, but it is strongly recommended not to use this, as transactions should simply encapsulate a sequence of persistent memory updates.

Transactions are used mostly for two reasons:

  • Ensuring the consistency of data structures. In complex data structures, several fields and/or values must be synchronized. For instance, if a value is associated to a checksum, it is crucial for the value and the checksum to be updated in a transaction; otherwise, an interruption in the middle of an update may lead to an invalid checksum, which can have dire consequences.
  • Protecting against memory leaks. Usually, when an object is allocated, it is initialized and then inserted in a larger data structure (in order to be reachable in the future). If the program is interrupted during the initialization of an object, and after its allocation, this may lead to a memory leak.

In practice, most transactions are related to the protection of the consistency of a data structure. Memory leaks are often not a big issue, because in most programs, all instantiations are performed in the install method, which is covered by a special system-managed transaction (if the method is interrupted, its effects on persistent memory are canceled.

Most developers refrain from using transactions because they believe that they will increase the cost of an individual write operation. Although this may be true on some platforms, it is not obvious. The main reason is that the default update mode, in which each single write is atomic, is itself very costly. There is therefore no particular reason to refrain from using transactions. The only limit should be that the transaction buffer necessarily has a size, and that it is recommended not to update too much memory in a single transaction.

Linked lists

We therefore need to declare some fields to manage the linked list: the reference to the next element, which is an instance field, and the first element and first deleted element, which are static fields (associated to the class).

  private PasswordEntry next ;
  private static PasswordEntry first ;
  private static PasswordEntry deleted ;

The first method is the private constructor, which allocates a password item:

  private PasswordEntry()
  {
    // Allocates all fields
    id = new byte[SIZE_ID] ;
    username = new byte[SIZE_USERNAME] ;
    password = new byte[SIZE_PASSWORD] ;
    // The new element is inserted in front of the list
    next = first ;
    first = this ;
  }

In this method, we insert an element in a list. This is done in two steps. First, the successor of the new element is set to the list’s first element; then, the new element is inserted as the first element. In that case, the atomicity provided by Java Card on all updates is sufficient to guarantee that the list will always remain consistent. This is possible because the operation that actually inserts the element in the list is the last one, and it is performed in a single write operation.

Since the class manages a list of deleted items, there also is a need for a static factory method, which will be the main entry point:

  static PasswordEntry getInstance()
  {
    if (deleted == null)
    {
      // There is no element to recycle
      return new PasswordEntry() ;
    }
    else
    {
      // Recycle the first available element
      PasswordEntry instance = deleted ;
      JCSystem.beginTransaction() ;
      deleted = instance.next ;
      first = instance ;
      instance.next = first ;
      JCSystem.commitTransaction() ;
      return instance ;
    }
  }

In this method, a transaction is required, whereas it was not required for the constructor. The main difference is here that there are two lists to be managed at once, and they must be kept consistent at all times. Without the transaction, an interruption at the wrong time could lead to the loss the entire list.

Finally, the last element required is a method that searches for an entry with a given identifier:

  static PasswordEntry search(byte[] buf, short ofs, byte len) {
    for(PasswordEntry pe = first ; pe != null ; pe = pe.next)
    {
      if (pe.idLength != len) continue ;
      if (Util.arrayCompare(pe.id, (short)0, buf, ofs, len)==0)
        return pe ;
    }
    return null ;
  }

The other required operation is deletion. The deletion method is a bit complex, because it first needs to locate the item to be deleted (using the search method defined above), and then to remove the element from the list and recycle it.
First, we need to define the method that removes an element from the list. This method looks for the element in the list and then removes it. It is a bit complicated, because it requires a special case for the first element:

  private void remove()
  {
    if (first==this)
      first = next ;
    else
    {
      for(PasswordEntry pe = first ; pe != null ; pe = pe.next)
        if (pe.next == this)
          pe.next = next ;
    }    
  }

Then, we will therefore define a method that does the actual recycling of the item:

  private void recycle()
  {
    next = deleted ;
    deleted = this ;
  }

Note that these two methods have been defined as instance methods. This means that a password entry object is able to remove itself from the list and recycle itself (by inserting itself in the list of deleted objects).
With these methods, combined with the previously defined search method, we can build a method that deletes the entry that matches a given identifier. Contrarily to the other methods, this method is static, since it does not know a priori to which element it should apply:

  static void delete(byte[] buf, short ofs, byte len)
  {
    PasswordEntry pe = search(buf, ofs, len) ;
    if (pe != null)
    {
      JCSystem.beginTransaction() ;
      pe.remove() ;
      pe.recycle() ;
      JCSystem.commitTransaction() ;
    }
  }

This method uses a transaction. In that case, the use of the transaction is not the same as for the factory method. The order of updates ensure that the main list will always be consistent. However, if the operation is interrupted between the remove and the recycle methods, then there will be a memory leak.

Note that the getInstance method is actually poorly written. By reordering the write operations, the transaction would only be needed for the same reason (avoiding a possible memory leak).

3 Comments

  • Very nice post Eric, thanks for your contribution for the Java Card Community

    rgds
    Igor

  • lexdabear wrote:

    Nice post, Eric. There is not much tutorial material for the Java Card technology. The only other good source I can think of is from Sun, but they did not contribute since many years.

    Some remarks:
    – Why is JC’s transaction mechanism not comparable with the database one? To me it’s pretty the same concept, but maybe I misunderstood something ..
    – Did you declare the constructor private on purpose? I thought it must be at least protected, otherwise it cannot called directly, and only usable from within the factory method getInstance().
    – In the PasswordEntry constructor you mention that the transaction mechanism is not required. What if there is a tear between next = first ; and first = this ;? Is the instance created? If yes, this instance is connected to the list, but not retrievable because ‘first’ is the only entry point.
    – In your deletion mechanism you take only the recycle scenario into account. Thus in case of a lot of deletion the memory space is always occupied. What if the user wants to free up memory space? It could be accomplished with e.g. a parameter for the delete method: boolean deleteObject –> in the delete method check if object deletion is supported, set pe == null and apply for the object deletion mechanism.
    – The search method uses the variable pe.idLength, but you do not initialize this field in the PasswordEntry constructor, not in the getInstance() method.

  • Well, lots of questions here …

    About transactions, you are right to notice that there is a similarity between Java Card transactions and database transactions. However, persistence in Java Card is embedded in the VM, and it is much simpler than for databases. Just look at a definition of ACID on wikipedia, and you will notice that the guarantees are quite complex.

    The constructor is private on purpose, because I have defined a factory, and I want all allocations to go through it (mostly because there is a recycling mechanism).

    About the constructor, you are right about the fact that a tear at the wrong time could lead to an unreachable object (the object is created before the invocation of its constructor, in all cases). What I mean by saying that the transaction is not mandatory is that there is no risk of inconcistency.

    Overall, I must admit that this example is too simple to correctly explain transactions. Better examples should come when we will cover the protection of the data’s integrity, a few weeks or months from now.

    About deletion, you are right. However, I will cover this in a separate post.

    Finally, about the search method, yes, there is an issue about the initialization of the field, because the code presented in the JC101-4C post is incomplete. I will fix that.

Leave a Reply

Your email is never shared.Required fields are marked *