Showing posts with label Java. Show all posts
Showing posts with label Java. Show all posts

Monday, August 15, 2011

An Erlang-Java Interop Demo

Erlang is designed and used for distributed systems. As such, it is quite good at talking to itself. And as I'll show in the following, it is — at least in some cases — reasonably good at talking to other languages as well.

When would you want to do this?

(You can skip this section if you know.)

Interoperability between languages is useful when there's value to be had in the software in both ends. You might prefer to keep some functionality in Erlang because it's already written in that language; because it has better libraries for the task; or simply because the language supports that task better. The same goes for the other language: there are C libraries around for almost anything (and plenty of C/C++ legacy code), and for GUIs you might prefer e.g Java.

Or you have the same functionality implemented in both languages, and wish to do comparison tests on the two implementations.

Or the architecture is inherently distributed — e.g. a client-server configuration — so that there is no advantage to be had in building the two parts using the same language anyway.

In the following demonstration, we have a Java side with some freshly written software with interesting bugs, and an Erlang side with an interesting tool for discovering bugs and a nice-ish language for specifying tests.

The demo

What I intend to do:

  • Define an interface;
  • Write a Java function;
  • Make it accessible from Erlang;
  • Test it using Erlang.

Sounds like a lot of work? It needn't be. Not for you, anyway; most of the heavy lifting has already been done.

(If you don't care about exposition, and are just interested in the technical end result, here is the executable summary.)

An interface

First, we'll need to define an interface. For this, we use the IDL — Interface Description Language:

// File "foo.idl"
interface Foo {
  string quuxinate(in string s);
};

We translate this into Java using the Erlang compiler:

erlc '+{be,java}' foo.idl

This results in a Java interface in Foo.java, as well as some stub code we'll be using.

A function in Java

For an implementation, let's say that quuxinate() is to reverse the string. To add a twist, let's say that it breaks down under some rare, complex-ish circumstances, such as when there's a letter which occurs thrice in the input string — that'll be a bug we can find later, when we start testing it:

// File "FooImpl.java"
public class FooImpl extends _FooImplBase /* which implements Foo */ {
  public String quuxinate(String s) {
    int[] stats = new int[256];
    for (int i=0; i<s.length(); i++) {
      char c =  s.charAt(i);
      if (c<255 && ++stats[c] >= 3) throw new RuntimeException("WTF");
    }
    return new StringBuilder(s).reverse().toString();
  }
}

Making the function accessible from Erlang

You may have noticed that we don't implement Foo directly, but rather extend an stub class which implements it. This means that the class already knows how to talk to Erlang — specifically, it knows how to handle requests like a gen_server.

What is left is to establish connection to an Erlang node. There are two frameworks for this: CORBA and Erlang inter-node communication. CORBA is, I believe, the heavy-weight option, and I haven't worked with it; in the following, we'll use Erlang inter-node communication.

A runnning Erlang program (OS-level process) is often referred to as a 'node', because Erlang is designed for having multiple such programs be connected, in what is known as a 'cluster' of nodes.

It's not an exclusive club, either: nodes can be, and usually are, Erlang nodes, but other kinds can enter the mix — a C or Java node, for instance.

A bit of code is needed to run a Java program as a node; don't worry though, this is the only lengthy bit, and it can be generalized so that it doesn't have to refer to Foo:

// File "FooServer.java"
public class FooServer {
  // The following is based on the program in lib/ic/examples/java-client-server/server.java
  static java.lang.String snode = "javaserver";
  static java.lang.String cookie = "xyz";

  public static void main(String[] args) throws java.io.IOException, com.ericsson.otp.erlang.OtpAuthException {

    com.ericsson.otp.erlang.OtpServer self = new com.ericsson.otp.erlang.OtpServer(snode, cookie);

    System.err.print("Registering with EPMD...");
    boolean res = self.publishPort();
    if (!res) throw new RuntimeException("Node name was already taken.");
    System.err.println("done");

    do {
      try {
        com.ericsson.otp.erlang.OtpConnection connection = self.accept();
        System.err.println("Incoming connection.");
        try {
          handleConnection(connection);
        } catch (Exception e) {
          System.err.println("Server terminated: "+e);
        } finally {
          connection.close();
          System.err.println("Connection terminated.");
        }
      } catch (Exception e) {
        System.err.println("Error accepting connection: "+e);
      }
    } while (true);
  }

  static void handleConnection(com.ericsson.otp.erlang.OtpConnection connection) throws Exception {
    while (connection.isConnected() == true) {
      FooImpl srv = new FooImpl();
      com.ericsson.otp.erlang.OtpInputStream request= connection.receiveBuf();
      try {
        com.ericsson.otp.erlang.OtpOutputStream reply = srv.invoke(request);
        if (reply != null) {
          connection.sendBuf(srv.__getCallerPid(), reply);
        }
      } catch (Exception e) {
        System.err.println("Server exception: "+e);
        e.printStackTrace(System.err);
        handleException(e, connection, null);
      }
    }
  }

  static void handleException(Exception e, com.ericsson.otp.erlang.OtpConnection connection, com.ericsson.otp.ic.Environment env) throws Exception {
    // We'll improve on this later...
    throw e;
  }
}

Time to build and try out:

ERL_ROOT=`erl -noshell -eval 'io:format("~s\n", [code:root_dir()]), init:stop().'` # Or simply where Erlang is.
IC_JAR=`ls -1 $ERL_ROOT/lib/ic-*/priv/ic.jar`
JI_JAR=`ls -1 $ERL_ROOT/lib/jinterface-*/priv/OtpErlang.jar`
CLASSPATH=".:$IC_JAR:$JI_JAR"
javac -classpath "$CLASSPATH" *.java

epmd # Start Erlang port mapper daemon if it isn't already.
java -classpath "$CLASSPATH" FooServer

The Java node should now be running and registered as javaserver — ready to accept connections with the right cookie.

Let's test that:

erl -sname tester -setcookie xyz
> {ok,Host}=inet:gethostname().
> JavaServer = {dummy, list_to_atom("javaserver@"++Host)}.
> gen_server:call(JavaServer, {quuxinate, "Testing, 1-2-3"}).

The reply should be the reverse string:

"3-2-1 ,gnitseT"

And the bug we put there is working too:

> gen_server:call(JavaServer, {quuxinate, "Testing, 1 2 3"}).
** exception exit: {{nodedown,javaserver@flitwick},
                    {gen_server,call,
                                [{dummy,javaserver@flitwick},
                                 {quuxinate,"Testing, 1 2 3"}]}}
     in function  gen_server:call/2

Property testing of Java code

Now then, what can we do with this setup?

One interesting thing that we can do is to apply one of the property-based testing tools to our Java function. In the following, I'll be using Triq, but Quviq QuickCheck or PropEr could be substituted with only minor changes. First, assuming that you haven't got Triq, but have git:

git clone git://github.com/krestenkrab/triq.git
(cd triq && ./rebar compile)

Then we are ready to write our test — namely, that given any (ASCII) string, quuxinate() should return the reverse string:

// File "test.erl"
-module(test).
-include_lib("triq/include/triq.hrl").
-export([main/0]).

prop_reverse(JavaServer) ->                  % The property
  ?FORALL(S, ascii_string(),
      gen_server:call(JavaServer, {quuxinate, S})
      == lists:reverse(S)).

ascii_string() ->                            % A data generator
  list(choose(0,127)).

main() ->
  {ok,Host}=inet:gethostname(),
  JavaServer = {dummy, list_to_atom("javaserver@"++Host)},

  triq:check(prop_reverse(JavaServer), 100), % Do the magic
  init:stop().                               % Shut down cleanly

Compile and run the test:

erlc -I triq/include -pa triq/ebin test.erl

erl -noshell -sname tester -setcookie xyz -pa triq/ebin -run test main

Triq will now generate a hundred random test cases, and verify the property for each case. After a dozen such tests, the bug is triggered:

...........Failed with: {exit,
                 {{nodedown,javaserver@flitwick},
                  {gen_server,call,
                      [{dummy,javaserver@flitwick},
                       {quuxinate,
                           [79,84,75,110,3,42,73,14,1,53,76,42,126,40,118,122,
                            74,2,58,34,42,98]}]}},
                 [{gen_server,call,2},
                  {test,'-prop_reverse/1-fun-0-',2},
                  {triq,check_input,4},
                  {triq,check_forall,6},
                  {triq,check,3},
                  {test,main,0},
                  {init,start_it,1},
                  {init,start_em,1}]}

Failed after 12 tests with {'EXIT',
                            {{nodedown,javaserver@flitwick},
                             {gen_server,call,
                              [{dummy,javaserver@flitwick},
                               {quuxinate,
                                [79,84,75,110,3,42,73,14,1,53,76,42,126,40,
                                 118,122,74,2,58,34,42,98]}]}}}

The 22-character string has three '*'s (ascii value 42) in it, which was what triggered the bug.

Triq then proceeds to simplify the test case:

Simplified:
        S = [33,33,33]

concluding that the string "!!!" is a locally-minimal failing test case.

Quite useful, isn't it? — and the amount of non-reusable code has been quite manageable (3 lines of IDL, 14 lines of implementation, 14 lines of test code, 1 line of Foo-specific code in FooServer).
(Speaking of which: you're free to use these snippets as you see fit; provided as-is and with no guarantees of anything, of course.)

I should mention at this point that property testing tools exist within the Java world as well — there exists at least one for Scala. I didn't find it particularly satifying to use, though, although I may have been unlucky; in any case, this is an alternative.

Erlang, IDL and exceptions

The Guide (that is, the Erlang IC (IDL compiler) User Guide) has this to say about handling of Java exceptions:

While exception mapping is not implemented, the stubs will generate some Java exceptions in case of operation failure. No exceptions are propagated through the communication.

Which means that, out of the box, these are our options for handling Java-side exceptions:

  1. Convert exceptions into values within quuxinate().
  2. Return no result on exceptions — in which case the Erlang-side call will time out (after, as a default, 5 seconds).
  3. Close the connection — in which case the Erlang-side call will receive an error result immediately.

None of these options are especially satisfying.

So let's look at how to do this:

  1. Report exceptions to the caller as an {error, Reason} reply.

It's not too difficult. What we need to do (according to the gen_server call protocol) is send a {RequestRef, Reply} tuple to the caller, where RequestRef is a reference which was included in the request and must be included in the response as well.

The main difficulty is one of access: at the point of error handling, we will need access to (1) the caller's PID and (2) the request reference. I'd like to keep FooImpl and the connection-managing FooServer separate, so we need to add an accessor:

// File "FooImpl.java"
public class FooImpl extends _FooImplBase /* which implements Foo */ {
  ...
  /** The request environment is exposed for error handling reasons. */
  public com.ericsson.otp.ic.Environment getEnv() {
     return _env;
  }
}

That's it. We could instead have added one accessor for the caller PID and one for the request reference, but let's keep the complexity in the server class.

In the server class, instead of throwing an exception which causes the connection to be terminated, we will build and send an error reply:

// File "FooServer.java"
public class FooServer {
  ...
// in handleConnection(), replace
        // handleException(e, connection, null);
// with:
        handleException(e, connection, srv.getEnv());
  ...
// and replace handleException() with:
  static void handleException(Exception e, com.ericsson.otp.erlang.OtpConnection connection, com.ericsson.otp.ic.Environment env) throws Exception {
    // Write exception reply:
    com.ericsson.otp.erlang.OtpOutputStream err_reply = new com.ericsson.otp.erlang.OtpOutputStream();
    err_reply.write_tuple_head(2);
    err_reply.write_any(env.getSref());
    err_reply.write_tuple_head(2);  // Construct return value {error, ErrorText}
    err_reply.write_atom("error");
    err_reply.write_string(e.toString());
    connection.sendBuf(env.getScaller(), err_reply);
  }
}

There; that's all.

If we test it again, we get a nicer behaviour:

> gen_server:call(JavaServer, {quuxinate, "Testing, 1 2 3"}).
{error,"java.lang.RuntimeException: WTF"}

Disclaimer

I ought to mention that I have only just discovered this interoperability option (two days ago, in fact, when I stumbled upon this article); it is only a few months ago that I wrote a custom socket server test program in Java, and corresponding driver code in Erlang, just to achieve what could be had far more easily using Erlang's IDL compiler. It may therefore not be so easy to use in practice as the above make it seem. (For one thing, the only type that I've used is string.)

Even so, I hope to have inspired others to try this out.
One way to do so is to have a look at the executable summary referred to earlier; it is the demo as a shell script.

Happy inter-language hacking!


Further technical notes (and speculation)

The IDL compiler supports generating code for Java, C and Erlang. Here is its documentation.

If you're writing Erlang port programs (like an Erlang driver, but running in a separate process), but have an interface which is evolving quicḱly enough, or you yourself are lazy enough, that writing and maiintaining the serialization and deserialization code has quite lost its attraction, then it might be tempting to look into using IDL for that interface, and have the boring bits code-generated for you.

The IDL compiler and the code it generates does not seem to have been designed for this, but as far as I can tell it appears to be achieveable.

Monday, May 23, 2011

On concurrency issues

Concurrency issues — race conditions and the like — are the worst category of bugs. These are the bugs that cannot well be proven absent by unit tests; these are the kind of bugs that hide away, biding their time until the most inopportune moment, then rearing their ugly, non-deterministic head on your production system when it is at its busiest. And even then, they can continue to exist unlocated for quite a while, despite many hours being put into tracking them down. Elusive, hardly reproducible, yet ultimately expensive; I've seen it happen more than once.

What follows is some thoughts on the basis of the typical issues.

Your basic multi-threading bug
As any course on multi-threaded programming will tell you, when multiple threads of execution are to run concurrently, care needs to be taken or there will be a risk of data corruption and/or unintended results.

More specifially, the threat (a "race condition" or "data race") is present when:
  1. one thread modifies the state of an object
  2. at the same time as
  3. another thread accesses the object.
That is: it takes a coincidence, a conjunction of three conditions.
Let's analyze it...:

Analysis

Another way of stating the above is obtained by reversing the statement:
We can avoid concurrency issues by always making sure that any object either
  1. is never modified; or
  2. is never accessed by two threads simultaneously (or stronger: never written to while accessed otherwise); or
  3. can only ever be accessed by one thread.
Such objects are known as, respectively,
  1. Immutable objects.
  2. Objects with state protected by a mutex (synchronization lock; monitor)
and the one used less often:
  1. Single-thread objects — or even stronger: objects of linear type.
The first two options are well-known; personally, I'm increasingly coming to consider the strong third option — objects with enforced linear lifecycle — to be rather overlooked, language design space-wise.

"Concurrency-ready" metric
One possible metric for how well a programming language is designed to express complex concurrent systems is, then, how easy it is to enforce that all objects fall into one of the three categories.

Languages and concurrency

Let's apply this view to a few programming languages. The two languages I've used most recently are Java and Erlang:
Erlang
In Erlang, there are the following kinds of objects: terms, message queues, process dictionaries and other process metadata, ETS tables, ports (files and drivers).
  • Terms are immutable values. They may contains handles of other kinds of objects, but the handles themselves are also immutable.
  • Certain objects — private ETS tables, and to some extent ports — are single-thread objects.
  • The rest — message queues, public ETS tables, process metadata etc. — are mutex-protected.
Single-thread objects are enforced not to be used by other threads than the owning one.
In Erlang, low-level data races only occur if there's a bug in the Erlang run-time system, or if you write your own driver and include one.

Java
In Java, you could argue both that there are fewer kinds of object — just one, really, the class-file defined kind — and that there is a much wider range of object kinds.There are certainly thousands of classes, defined by one well-defined scheme, which includes just a few mechanisms relevant to concurrency.
But the problem here is the number of classes — because it is at the class level that it is ensured that the corresponding objects will be thread-safe. A well-designed and -implemented class may be thread-safe, in that it is either immutable or uses appropriate inter-thread synchronization (and encapsulation) to ensure thread-safety. A less well-written class may rely implicitly on details of the context in which it is used, and really be single-thread-use only, or multi-thread usable only in certain unstated conditions.
Java is one of the few languages actually designed for portable multi-threaded programs; in particular, it has explicitly stated semantics wrt. multi-threaded execution. However, as the above comparison is one indication of, it has its shortcomings. For a language to claim good concurrency support, it should provide mechanisms for good, usable guarantees to be derived from local context (e.g. "we know that this-and-this property always holds, because these few lines here ensure that it does").
I've expounded earlier on the importance of supporting local reasoning. As it happens, Java did also then get some criticism (sorry, Java, but you're the modern main-stream language I happen to know the best...).

A Java exercise
Imagine that you have in front of you the source code of a Java class.
A quick inspection reveals that all methods are declared "synchronized".
What kinds of thread-safety issues might the class yet have? Try to list at least three ways in which the class may be non-thread-safe.
I'll present my list at the end of this article.

Does it matter?

But building security against these issues into a language is not exactly trivial, you might argue. Is stricter language rules, additional compiler analysis, and/or costly run-time support just for preventing concurrency issues not just overkill?
Sure, the trend is towards increasing parallellism and so on, but we have done quite fine without such extra measures so far, haven't we?
And bondage-and-discipline languages have been out of fashion for a while. Dynamically typed languages are as popular as ever!

The difference is this:

You can easily live and work with the relative uncertainties of dynamic typing — but then, you can unit test and get some confidence that the types match. If something is broken, or breaks later, then there's a good chance it'll be caught.
For many concurrency issues, unit tests are not likely to catch any errors. Furthermore, the necessary invariants aren't local — they are often widely dispersed in the code. To convince yourself that the code is correct, you more or less need to keep it all in your head at once. That, combined with missing language support for documenting and/or enforcing vital non-local invariants, means that they will perhaps not be communicated to whoever makes the next change in the code, who will therefore not have the full picture necessary to keep things correct.

Rather than being caught at the next full test suite run, or at least quite soon after the rubber hits the road, here's what happens to a race-condition bug:
  • The program may appear to work most of the time.
  • The issue will tend to manifest itself at the most inopportune moment: Not during development or testing (unless explicit and considerable effort is taken to stress-test against such issues), but in production, when your servers are at their busiest, or on the desktop of your busiest client.
  • Often, what clues you have amount to little besides "There almost certainly is an issue, it presumably is a software bug, the issue is probably in our code — and it occurs seldomly, so it's likely to be a concurrency issue of some kind."
  • Replicating the issue may be difficult; under the exact same circumstances, the program may run just fine.
    Indeed, if the problem does manifest itself during development, it'll appear to have gone at the next run.
    The issue may even be technically impossible to reproduce on some machine architectures, because it requires multiple physical processors of the right kinds to manifest itself (and your servers or other production environment is less likely than the development machines to be thus bug-resistant).
  • Eliminating a tricky concurrency bug can be a drawn-out experience in all phases — detecting it, reproducing it, tracking down its root cause, verifying that it has gone — all steps tend to be markedly more difficult than for deterministic bugs.
  • With any kind of bug, tracking it down once is one thing; there may be even be a feeling of gratification once you've done it. Tracking the same bug down twice is another matter — it is deeply frustrating to realize that there's a reason for your feeling of déja-vu. This is one of the reasons for regression testing: bug hunting may be stimulating in its own way, but it'd better lead to a different bug each time.
    This goes doubly (well, even more than that) for the elusive non-deterministic bugs.
    Sadly, because of their nature it is at best difficult, and often near impossible, to write regression tests for these kinds of issues.

Conclusion

Languages differ in concurrency support. Nothing new about that, of course, but I think it likely that many developers using one of the  mainstream languages which have a relatively good level of support in that area may not know that there are alternatives which are significantly more concurrency-ready.
In the beginning of this text, the prerequisites for a race condition were broken down and three kinds of conditions for avoiding race condition were derived; based on this I suggested a qualitative metric for a language's level of support for concurrent programming. I hope to have demonstrated that it may be a useful way of looking at both languages and concrete programs or program designs.

In the absence of a programming language providing strong, local guarantees with respect to thread-safety, as a developer you need to be alert whenever there's a chance that two threads may be executing your code concurrently. The best way of doing this is probably through discipline — for instance, by clearly constructing each class so that it falls into one of the above categories: Immutable, thread-safe through synchronization, or single-thread use only — and then using them strictly according to this. That is one way of trying to restore local reasoning.

Do you write programs involving multiple threads? If so, are you familiar with which consistency guarantees your platform actually provides (e.g, the Java Memory Model)?
Do you regularly stress-test your program on a system with multiple physical processors? I hope you do.
Dealing with concurrent programs in general requires good global, combinatorial-temporal reasoning abilities. Probably not your best-developed cognitive mode... :-)
The solution? Keep things as simple as possible. Find rules that work, and follow them. Encapsulate the issues, so that you can deal with just one question at a time. If possible, let the rules be checked mechanically.


Answer to Java exercise
Some ways in which a Java class may be unsafe even though all methods are declared "synchronized":
  1. A field is public, and either
    1. Non-final (and non-volatile) or
    2. Referring to a non-thread-safe object.
  2. The superclass is non-thread-safe, and the current class does not or can not override the causes.
  3. An instance method modifies the value of a a static variable without proper synchronization.
  4. An instance method reads the value of a a static variable which is also modified by a static method, without proper synchronization.
  5. A method exposes a reference to a non-thread-safe object referred to directly or indirectly by the current object.
    1. By returning such a reference.
    2. By passing such a reference to some method which stores the reference somewhere accessible to another thread.
    3. By starting a new thread and giving it such a reference.
    (I.e., a non-thread-safe object becomes shared.)
  6. A field (which may be private) refers to a non-thread-safe object which may be shared because
    1. It originated as (or was extracted from) a parameter to a constructor
    2. It originated as (or was extracted from) a parameter to a method
    3. It was returned from a call
    (I.e., a non-thread-safe object is already unexpectedly shared.)
  7. An inner class accesses an instance variable of the surrounding class, but fails to synchronize on the right this.
  8. An instance method locks on another object which may be of the same class (this may result in a deadlock)
    1. Implicitly, by calling a (synchronized) method on the other object
    2. Explicitly, using "synchronized"
    (A plausible example of this is a synchronized equals() method.)
  9. A constructor leaks this to some place where it can be accessed by another thread, and the object has at least one (final) variable which is accessed without synchronization.
    (This is because the special rule for final fields, which allows them to be accessed without synchronization, only applies after the constructor has completed.)
  10. A method exposes a reference to a thread-safe object referred to directly or indirectly by the current object, and that thread-safe object allows mutation (of itself or of a contained object) in a way that the current class is not prepared for.
This list is quite likely not complete; it is not the result of a systematic analysis of the matter.

Friday, September 18, 2009

Programming Languages and Local Reasoning

Through time, there have been two interesting trends in programming languages: towards better guarantees and later binding.

With "guarantees", I mean facts and invariants which the language rules permit us to conclude from the code. Such as the following - you may or may not recognize them (and the language features which give rise to them):
  • "The value in this variable is of this type."
  • "The value in this variable can only come from one of these expressions."
  • "The value of this object field can not be changed once the object has been constructed."
  • "This variable can only be accessed from one thread."
  • "This method can not be redefined in subclasses."
  • "This process will always be notified when this other process disappears."
  • "If this code point is reached, then this other code point will eventually be reached."
The two trends, better guarantees and later binding, correspond to two desirable properties of software: the ability to reason about the behaviour of software, and flexibility.