Thursday, November 22, 2007

Double-Checked Locking found in JVM

I just found an implementation of the broken double checked locking in the java 6 runtime library!

Here is a snippet of the offending code:

package java.lang; import java.util.Random; public final class Math { private static Random randomNumberGenerator; private static synchronized void initRNG() { if (randomNumberGenerator == null) randomNumberGenerator = new Random(); } public static double random() { if (randomNumberGenerator == null) initRNG(); return randomNumberGenerator.nextDouble(); } }

Amazingly, it used to work correctly, but the extra synchronization was removed in java 1.3. You can track the progress of this bug in report 6470700 and report 6633229.

Friday, November 16, 2007

Howto extend LDAP in java with JLDAP

LDAP is a protocol that is wonderfully extensible. You can augment existing messages by adding 'controls', and you can define complete new messages. Extensions are identified by a universal OID, so that even code that does not know about an extensions can still work properly. For this each extension has a criticality flag to indicate whether the receiver may ignore unknown extensions. As a bonus, the content of controls and messages are all defined by a common syntax (ASN.1) and common encoding (which is BER with restrictions).

Writing you own controls and messages is a kind of under documented thing. In addition, not all LDAP libraries support all kinds of messages. In this small howto I show how to implement custom controls and messages based on my experiences with implementing a RFC4533 (synchronization) client. I used JLDAP as it is the only java library I could find that supports IntermediateMessages, a requirement for RFC4533. And before you ask: no sorry, I can not open source the results.

In case you actually want to start with JLDAP, you get a lot of knowledge from at the examples that are provided by Novel. You can find them through the JLDAP site. The javadoc is also useful at times.

Decoding a control

Lets take a look at the SyncDoneControl from RFC4533. The control's OID is 1.3.6.1.4.1.4203.1.9.1.3 and its content value is defined with ASN.1 as:

syncDoneValue ::= SEQUENCE { cookie OCTET STRING OPTIONAL, refreshDeletes BOOLEAN DEFAULT FALSE }

Read this as: the value is a sequence that contains 2 other values. The first, named cookie is optional and has binary content. The second is named refreshDeletes and has boolean content. The default of refreshDeletes is false. See RFC4533 for the semantics.

Lets map this to java. All controls must have the same constructor signature so that JLDAP can instantiate it. We'll start with:

public class SyncDoneControl extends LDAPControl { public static final String OID = "1.3.6.1.4.1.4203.1.9.1.3"; private byte[] cookie; private boolean refreshDeletes; // add getters for cookie and refresDeletes public SyncDoneControl(String oid, boolean critical, byte[] value) { super(oid, critical, value); ...see below } }

The byte array value contains the BER encoded value of the control. The LDAP restriction put on the BER encoding mean that optional values and values that are equal to the default value must be omitted. With other words: when there is no cookie (allowed because it is declared OPTIONAL), and refreshDeletes is FALSE (which is the default), constructor argument value is null! Just to be robust we'll check for the empty array as well:

if (value == null || value.lenght == 0) { cookie = null; refreshDeletes = false; } else { ...see below }

If it is not null/empty, we'll use the decoder as provided by JLDAP to decode the bytes. As the ASN.1 value is defined to start with a SEQUENCE (one of the native ASN.1 types), the LBERDecoder will instantiate an object of type ASN1Sequence:

ASN1Sequence asn1 = (ASN1Sequence) new LBERDecoder().decode(value);
The decoder can decode all native ASN.1 types. These native types are called "universal". Other important universal types are BOOLEAN, OCTET STRING, CHOICE and SET. Type information is available on every ASN1Object through the ASN1Object#getIdentifier() method.

We can examine the sequence further by calling the ASN1Sequence#size() and ASN1Sequence#get(int) methods. Again, we must take into account that each element may be omitted. You can do this by examining the type of ASN.1 value you get out of the sequence. First, extract a value from the sequence:

ASN1Object asn1Obj = asn1.get(0);
When this is the cookie, the value must be from the type-class UNIVERSAL, with as type OCTET STRING:
boolean isCookie = asn1Obj.getIdentifier().getASN1Class() == ASN1Identifier.UNIVERSAL && asn1Obj.getIdentifier().getTag() == ASN1OctetString.TAG;
If it is, we can safely cast the object to an ASN1OctetString and extract the cookie:
cookie = ((ASN1OctetString) asn1Obj).byteValue()

We can do the same for the value refreshDeletes and JLPAP class ASN1Boolean. After we have moved this very verbose code to the utility class Asn1Util (exercise for the reader) we'll get the following code:

ASN1Sequence asn1 = (ASN1Sequence) new LBERDecoder().decode(value); for (int i = 0; i < asn1.size(); i++) { ASN1Object asnSeqObj = asn1.get(i); if (i == 0 && Asn1Util.isOctetString(asnSeqObj)) { cookie = Asn1Util.getByteValue(asnSeqObj); } else if (i == (cookie == null ? 0 : 1) && Asn1Util.isBoolean(asnSeqObj)) { refreshDeletes = Asn1Util.getBooleanValue(asnSeqObj); } else { throw new IllegalArgumentException("Parse error at index " + i + ", parsing: " + asnSeqObj); } }

Tada! Your first JLDAP extension. All we have to do is make JLDAP aware of the extension and it will be parsed automatically when the control is present in a received LDAP message.

LDAPControl.register(SyncDoneControl.OID, SyncDoneControl.class);

One small warning: when there is an exception in the control's constructor, JLDAP will silently ignore your class and do its default thing.

Encoding a control

To start a sync operation, one must add a SyncRequestControl to the search constraints. Here is the ASN.1 definition of the control value:

syncRequestValue ::= SEQUENCE { mode ENUMERATED { refreshOnly (1), refreshAndPersist (3) }, cookie OCTET STRING OPTIONAL, reloadHint BOOLEAN DEFAULT FALSE }

First the ASN.1 enumeration is translated into a Java enumeration:

public enum SyncRequestMode { REFRESH_ONLY, REFRESH_AND_PERSIST }

The we'll start the control with

public class SyncRequestControl extends LDAPControl { public static final String OID = "1.3.6.1.4.1.4203.1.9.1.1"; private SyncRequestMode mode; private byte cookie[]; boolean reloadHint = false;

As we will construct this control ourself, and not JLDAP, we can give it any constructor we like. For example:

public SyncRequestControl(SyncRequestMode mode, byte cookie[], boolean reloadHint) { super(OID, true, null); this.mode = mode; this.cookie = cookie; this.reloadHint = reloadHint; setValue(encodedValue()); }

In the last line we set the BER encoded value. Here is a complete implementation of the encode method. Note how we follow the ASN.1 definition, but skip optional values and values that have the default value.

private byte[] encodedValue() throws IOException { ASN1Sequence asn1 = new ASN1Sequence(); asn1.add(new ASN1Enumerated(mode == REFRESH_ONLY ? 1 : 3)); if (cookie != null) { asn1.add(new ASN1OctetString(cookie)); } if (reloadHint) { asn1.add(new ASN1Boolean(reloadHint)); } ByteArrayOutputStream baos = new ByteArrayOutputStream(); new LBEREncoder().encode(asn1, baos); return baos.toByteArray(); }

More complex example, decoding a message

The JLDAP BER decoder can only decode ASN.1 universal types. As soon as you define your own types, you must help the decoder. Lets look at the decoding of the SyncInfoMessage to see how this works. The value of SyncInfoMessage is defined with the following ASN.1:

syncInfoValue ::= CHOICE { newcookie [0] OCTET STRING, refreshDelete [1] SEQUENCE { cookie OCTET STRING OPTIONAL, refreshDone BOOLEAN DEFAULT TRUE }, refreshPresent [2] SEQUENCE { cookie OCTET STRING OPTIONAL, refreshDone BOOLEAN DEFAULT TRUE }, syncIdSet [3] SEQUENCE { cookie OCTET STRING OPTIONAL, refreshDeletes BOOLEAN DEFAULT FALSE, syncUUIDs SET OF OCTET STRING (SIZE)16)) } }

The ASN.1 defines that the value can have one or four values. We'll represent the chosen value with a Java enumeration. By defining the enum values in order, we can abuse that the ordinal value of the enum values corresponds to the tag (defined between brackets []) value.
public static enum SyncInfoMessageChoiceType { // Note: order is important NEW_COOKIE, REFRESH_DELETE, REFRESH_PRESENT, SYNC_ID_SET }

As SyncInfoMessage is an intermediate response, we'll start the message implementation as:

public class SyncInfoMessage extends LDAPIntermediateResponse { public static final String OID = "1.3.6.1.4.1.4203.1.9.1.4"; private SyncInfoMessageChoiceType syncInfoMessageChoiceType; private byte[] cookie; private Boolean refreshDone; private Boolean refreshDeletes; private List syncUuids; // add getters ...

Not all fields will always get a value. For example field syncUuids will only be set when syncInfoMessageChoiceType == SYNC_ID_SET. This is the most simple implementation, and the user of this class must know about the CHOICE type anyway.

Intermediate messages must always have the same constructor, so that JLDAP can construct it for us:

public SyncInfoMessage(RfcLDAPMessage message) { super(message); ...

The choice is represented by an instance of type ASN1Tagged. The identifier of the tag indicates the choice. Instantiate field syncInfoMessageChoiceType so:

ASN1Tagged asn1Choice = (ASN1Tagged) new LBERDecoder().decode(getValue()); int tag = asn1Choice.getIdentifier().getTag(); syncInfoMessageChoiceType = SyncInfoMessageChoiceType.values()[tag];

Now comes the tricky part. As JLDAP has no clue about the ASN.1 definition, it does not know about the choice, and it can not decode any further. What we can do is get the contents of asn1Choice as an OCTET STRING, get its byte array, and decode that again with the JLDAP decoder.

So for most choice types we need to decode the tag's contents to a SEQUENCE. Here is a utility method we can add to the AsnUtil class:

public static ASN1Sequence parseContentAsSequence(ASN1Tagged asn1Choice) throws IOException { ASN1OctetString taggedValue = (ASN1OctetString) asn1Choice.taggedValue(); byte[] taggedContent = taggedValue.byteValue(); return new ASN1Sequence(new LBERDecoder(), new ByteArrayInputStream(taggedContent), taggedContent.length); }

With this tool we'll decode the choice refreshPresent. Notice how we decode the contents of the tag, and how refreshDone is set to its default value when we did not see it in the sequence.

if (syncInfoMessageChoiceType == SyncInfoMessageChoiceType.REFRESH_PRESENT) { ASN1Sequence asn1Seq = Asn1Util.parseContentAsSequence(asn1Choice); for (int i = 0; i < asn1Seq.size(); i++) { ASN1Object asnSeqObj = asn1Seq.get(i); if (i == 0 && Asn1Util.isOctetString(asnSeqObj)) { cookie = Asn1Util.getByteValue(asnSeqObj); } else if ((i == (cookie == null ? 0 : 1)) && Asn1Util.isBoolean(asnSeqObj)) { refreshDone = Asn1Util.getBooleanValue(asnSeqObj); } else { throw new RuntimeException("Parse error"); } } if (refreshDone == null) { refreshDone = Boolean.TRUE; } }

When the choice is newCookie things are a bit simpler. The content of asnChoice is already an OCTET_STRING, so we can use that directly:

if (syncInfoMessageChoiceType == SyncInfoMessageChoiceType.NEW_COOKIE) { ASN1OctetString taggedValue = (ASN1OctetString) asn1Choice.taggedValue(); cookie = taggedValue.byteValue(); }

Again, we have to make JLDAP aware of the new message. it will be parsed automatically when the control is present in a received LDAP message.

LDAPIntermediateResponse.register(SyncInfoMessage.OID, SyncInfoMessage.class);

Conclusion

In this article I showed how to get started with extending JLDAP. The example are functional but not always complete. Nor are they always according to best practices (for example, I would normally not declare so many exceptions). I shared some of the pitfalls you will encounter when encoding and decoding messages and controls.