Two Java Gotchas that Keep Tripping me

I have a principle that if I make the same mistake twice, I put it on my blog to remind myself. The two that tripped me up recently are:

1. Java Regex

If you try to search for some text that's broken over two lines, you need to tell java.util.regex.Pattern. For instance, given the text:


This is a piece of text
with multiple lines and this text:
string to find

Then you might find a regular expression looking for the pattern text:.string (not the wild card after the colon) would find the end of the second and beginning of the third line. This is not the default behaviour. In fact, this test fails:


        String toFind = "text:.string";
        String toSearch = "This is a piece of text\nwith multiple lines and this text:\nstring to find\n";
        Pattern pattern = Pattern.compile(toFind);
        Matcher matcher = pattern.matcher(toSearch);
        Assert.assertTrue(String.format("Can't find [%s] in [%s]", toFind, toSearch), matcher.find());

You need to enable DOTALL mode with:

        Pattern pattern = Pattern.compile(toFind, Pattern.DOTALL);

Now, your regex will match.

2. XML Namespace and Java Parsers

I wasted most of a day this week wondering what was wrong with my XML when I tried to validate it against what looked like a perfectly good piece of XSD. It seems that the default behaviour of a parser is to ignore namespaces. I don't know why. Presumably it's due to historical reasons. Anyway, you need to add:

aSAXParserFactory.setNamespaceAware(true);

to your code (see the JavaDocs).

It was a colleague who told me about this. When I asked how he knew that, he said I had told him a few months before. Hence this blog entry.

ThreadPoolExecutor and RTFM

Take a look at the constructors for ThreadPoolExector. All of them take a maximumPoolSize argument. If you thought this was necessarily the maximum size of the thread pool, you'd be wrong.

To be fair, the documentation does say this might not necessarily be the case. But although we should have RTFM, we were in a hurry.

Basically, the pool size is partly determined by the type of BlockingQueue you use in the constructor. The rule is that if the BlockingQueue in question can take another task, it will rather save it for later rather than start a new thread.

So, if for you pass the constructor a LinkedBlockingQueue that in turn was instantiated without a limit, no new threads are created no matter what the maximum size of the pool. So, a conservative programmer may instantiate the thread pool with an initial size of 1 and a much larger maximum pool size. But if he passes in an unbound queue then it is all to no avail. The executor will not be multi-threaded.

Furthermore, if you pass the constructor an ArrayBlockingQueue (that is by its nature bounded) to a ThreadPoolExecutor with a core pool size of 1 and a maximum pool size much bigger, the executor won't be multi-threaded until the number of tasks to be executed exceeds the size of the ArrayBlockingQueue.

And if you use the a SynchronousQueue (where "each insert operation must wait for a corresponding remove operation by another thread"), don't be surprised when it throws a RejectedExecutionException as soon as there are no other threads to do any work.

How the executor differentiates between the various queue types happens in ThreadPoolExecutor.execute:


    public void execute(Runnable command) {
        if (command == null)
            throw new NullPointerException();
        for (;;) {
            if (runState != RUNNING) {
                reject(command);
                return;
            }
            if (poolSize < corePoolSize && addIfUnderCorePoolSize(command))
                return;
            if (workQueue.offer(command))
                return;
            Runnable r = addIfUnderMaximumPoolSize(command);
            if (r == command)
                return;
            if (r == null) {
                reject(command);
                return;
            }
            // else retry
        }
    }


Queue.offer returns true it was possible to add something (the happy path of this method). This is determined by the type of queue and how it was instantiated as mentioned above. Only if the task was not added does the ThreadPoolExecutor code attempt to start another thread.

There were two other things that confused us. The first was that the timeout mentioned in ThreadPoolExecutor's method:

invokeAll(Collection<Callable<T>> tasks, long timeout, TimeUnit unit)

It refers to the total time it will wait not the the time for each Callable. During this time, it will poll the futures (by calling get())to see if they have anything to return. If it times out while polling, it will call cancel() on all futures.

The final gotcha we experienced was that isDone() on all the futures returned from invokeAll will return true. However, a call to get() will lead to a CancellationException being thrown. Not what we expected.

The long and short of it is that although these Java classes are beautifully crafted, they are not without their somewhat counterintuitive peculiarities.

Why System Calls are Slow

Java is an abstraction around the underlying operating system. Normally, you wouldn't have to worry about what calls the JVM makes to the OS on your behalf. But these system calls can be expensive as the girls and buys down at LMAX know. They've put together a framework that tries to minimize them.

As with any other process, Linux allows you to see what underlying operating system calls the JVM is making with the strace command. When threads vie for synchronized blocks, for instance, you'll see  output like:


futex(0xb7651344, FUTEX_WAIT_PRIVATE, 1, {0, 999854465}) = 0

where the futex system call is asking for the operating system to arbitrate the contention.

When a call is made the following steps are executed (from the excellent The Linux Programming Interface):

1. Although your C code may look like you're calling a system call as if it were any other function, it actually "invokes a wrapper function in the C library".
2. "Argument are passed to the wrapper via the stack [as with any C function call], but the kernel expects them in specific registers. The wrapper function copies the arguments to these registers".
3. "Since all system calls enter the kernel in the same way, the kernel needs some method of identifying the system call. To permit this, the wrapper function copies the system call into a specific register (%eax)"
4. The "machine instruction (int 0x80), which causes the processor to switch from user mode to kernel mode and execute code pointed to be location 0x80" is run.
5. In response to this, "the kernel invokes its system_call() routine". This is covered in the next section.
6. "If the return value of the system call service routine indicated an error, the wrapper function sets the global variable errno ... using this value. The wrapper function then returns to the caller, providing an integer return value indication the success or failure of the system call"

Step #5 mentions the "system_call() routine". This does the following:

1. "Saves the register values onto the kernel stack".
2. "Checks the validity of the system call number."
3. "Invokes the appropriate system call routine, which is found by using the system call number to index a table of all system call services (the kernel variable sys_call_table). If the system call service routine has any arguments, it first checks their validity". The list of kernel calls and their memory addresses can be found at /proc/kallsyms. [1]
4. Restores registers from the stack and places the return value on the stack.
5. Drops back to user mode and returns to the wrapper function.

If this looks like a lot of work, it's because it is. This is why system calls are largely avoided in the Disruptor where even the smallest delay is to be avoided.

[1] The Ksplice Blog.

How do I remember thee? Let me count the ways...

With apologies to poetess, Elizabeth Barrett Browning, this post is about all ways a Java process can hold on to memory.

When people talk about how much memory a Java process has, most people only think of heap size. But there's more.

Firstly, there's obviously the stack. When we create a new thread and then start it, memory usage increases. Instantiating a thread - or indeed any object - in Java does not in itself use any additional system memory.

Secondly, there are direct byte buffers.

Thirdly, there are memory mapped files and there also may be OS specific means of sharing data between processes.

1. The Heap

Memory usage of processes share similar characteristics and the concept of heap space is not unique to the JVM.

In C, allocating memory is usually done with the malloc call. Note that in Linux, this is not a kernel call but a library call. It can be found in the glibc library. If you're using the GNU C compiler, this is the code that will be executed. But you can use any memory manager you like. You can even write your own.

"A memory manager is a set of routines that takes care of the dirty work of getting your program memory for you. Most memory managers have two basic functions - allocate and deallocate. Whenever you need a certain amount of memory, you can simply tell allocate how much you need, and it will give you back an address to the memory. When you’re done with it, you tell deallocate that you are through with it. allocate will then be able to reuse the memory. This pattern of memory management is called dynamic memory allocation. This minimizes the number of "holes" in your memory, making sure that you are making the best use of it you can. The pool of memory used by memory managers is commonly referred to as the heap.

"The way memory managers work is that they keep track of where the system break is, and where the memory that you have allocated is. They mark each block of memory in the heap as being used or unused. When you request memory, the memory manager checks to see if there are any unused blocks of the appropriate size. If not, it calls the brk system call to request more memory. When you free memory it marks the block as unused so that future requests can retrieve it." - Programming from the Ground Up.

This is what malloc does.

"When a process needs memory, some room is created by moving the upper bound of the heap forward, using the brk() or sbrk() system calls. Because a system call is expensive in terms of CPU usage, a better strategy is to call brk() to grab a large chunk of memory and then split it as needed to get smaller chunks. This is exactly what malloc() does. It aggregates a lot of smaller malloc() requests into fewer large brk() calls. Doing so yields a significant performance improvement. " - Linux Journal.

So, creating an object in Java does not appear to in itself appear to demand any memory from the OS. That is, using Linux's strace on the process doesn't show any system calls to brk or mmap. Nor does the pmap command indicate that any more memory is being used (from the point of view of the OS).


2. The Stack

However, upon starting a Java Thread, the pmap command shows increased memory usage - about 312k on my system. Repeatedly running pmap and diffing the results between the JVM calling Thread.start() shows this:


00eb8000    312K rwx--    [ stack ]


3. Direct Byte Buffers

"Operating systems perform I/O operations on memory areas. These memory areas, as far as the operating system is concerned, are contiguous sequences of bytes.  It's no surprise then that only byte buffers are eligible to participate in I/O operations. Also recall that the operating system will directly access the address space of the process, in this case the JVM process, to transfer the data. This means that memory areas that are targets of I/O operations must be contiguous sequences of bytes. In the JVM, an array of bytes may not be stored contiguously in memory, or the Garbage Collector could move it at any time. Arrays are objects in Java, and the way data is stored inside that object could vary from one JVM implementation to another.

"For this reason, the notion of a direct buffer was introduced. Direct buffers are intended for interaction with channels and native I/O routines." - Java NIO.

Direct buffer memory is allocated with the call:

ByteBuffer.allocateDirect(capacity);

If you keep allocating memory like this, you won't see any changes to the memory usage as reported by calls to:

Runtime.getRuntime().freeMemory();

However, you will be using memory. In Linux, you can prove this by comparing the /proc/PID/smaps file between calls (where PID is the ID of the thread allocating memory). Typically diff will show something like:


< b49fc000-b4e00000 rw-p 00000000 00:00 0
< Size:               4112 kB
< Rss:                4112 kB
< Pss:                4112 kB
---
> b48fb000-b4e00000 rw-p 00000000 00:00 0
> Size:               5140 kB
> Rss:                5140 kB
> Pss:                5140 kB
824,825c824,825
< Private_Dirty:      4112 kB
< Referenced:         4112 kB
---
> Private_Dirty:      5140 kB
> Referenced:         5140 kB



These addresses correspond to the kernel calls the JVM is making. From strace:


mmap2(NULL, 1052672, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0xb49fc000
.
.
.
mmap2(NULL, 1052672, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0xb48fb000


This is when I am allocating a 1MiB of memory at a time. Why this is slightly more than 1MiB is currently a mystery to me.

4. Memory Mapped Files

"Calling map( ) on a FileChannel creates a virtual memory mapping backed by a disk file and wraps a MappedByteBuffer object around that virtual memory space. " - Java NIO.


This allows your JVM to use much more memory than the machine physically has. Peter Lawrey on his blog demonstrates "8,000,000,000,000 bytes or ~7.3 TB in virtual memory, in a Java process! This works because it only allocates or pages in the pages which you use. So while the file size is almost 8 TB, the actual disk space and memory used is 4 GB."


5. OS Specific Tempfs


There is a RamDisk-like functionality on most Linux distros called tmpfs (Note: most Unix-like systems have this). You can use this shared memory out-of-the-box by reading/writing to a virtual filesystem at /dev/shm.


The advantages of using this memory are outlined in Michael Kerrisk's The Linux Progamming Interface:

"Linux also support the notion of virtual file systems that reside in memory... file operations are much faster since no disk access is involved.


"This file system has kernel persistence--the shared memory objects that it contains will persist even if no process currently has them open, but they will be lost if the system is shut down". 


[Disclaimer: I am a Java engineer by trade but have an interest in Linux. I have tried my best to be accurate when talking about Linux but cannot guarantee what I write is error free]

Low level interrupts

[Disclaimer: I don't make my living from writing C so the following should all be taken with a pinch of salt. I am a lowly Java programmer who is interested in what is going on in the low-level Linux world].

In my last post, I showed that Java interrupts are not achieved by Linux kernel calls even though Linux does allow such an "interrupt()".

Take this C code (SignalHandling.c):

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <errno.h>
#include <string.h>
#include <netdb.h>
#include <sys/types.h>
#include <netinet/in.h>
#include <sys/socket.h>
#include <signal.h>



void sig_handler(int signum)
{
    fprintf(stdout, "\n=============\nReceived signal %d\n==============\n", signum);
}


void addSigAction() {
    struct sigaction sa;
    sa.sa_handler = sig_handler;
    sigemptyset(&sa.sa_mask);
    sa.sa_flags = SA_INTERRUPT; /* Restart functions if
                                 interrupted by handler */
    if (sigaction(SIGINT, &sa, NULL) == -1) {
        fprintf(stderr, "Could not install signal handler\n");
    } else {
        fprintf(stdout, "addSigAction: registered handler\n");
    }
}



void* runSleep(void* object)
{
    addSigAction();
    printf("runSleep: about to sleep\n");
    sleep(100);
    printf("runSleep: finished sleeping\n");
}




int main(int argc, char *argv[])
{
    pid_t pid = getpid();
  fprintf(stdout, "Main: Started. PID = %d\n", pid);


  pthread_t otherThread; 


  int error = pthread_create(&otherThread, NULL, runSleep, NULL);


  printf("Hit return...\n");
  getchar();
  pthread_kill(otherThread, SIGINT);


  pthread_join(otherThread, NULL);
  fprintf(stdout, "Finished\n");
}

Forget rogue includes for now - we'll be needing them later.

Compile it with:


gcc -O0 -g3 -Wall -c -fmessage-length=0 -MMD -MP -MF"src/SignalHandling.d" -MT"src/SignalHandling.d" -o"src/SignalHandling.o" "../src/SignalHandling.c"


gcc  -o"SignalHandling"  ./src/SignalHandling.o   -lpthread -lrt


(Note the -lpthread switch to use the thread library).

This code starts a new thread (pthread_create) - the equivalent of instantiating a new java.lang.Thread with a Runnable that is actually the runSleep method.

(The first NULL is the thread attributes and the second is the argument passed to runSleep - that is: nothing as runSleep doesn't take an argument).

This new thread registers a signal handler (sig_handler method) and then sleeps for 100s.

Meanwhile, the main thread that waits for the user to hit return before sending a message to the first thread (pthread_kill).

Don't be fooled by this method name. The documentation in the GLIBC sigthread.h file says it will:

Send signal SIGNO to the given thread.

Indeed, using strace to see what kernel calls are being made shows that this method delegates to tgkill. The man docs say:

tgkill() sends the signal sig to the thread with the thread ID tid in the thread group tgid. (By contrast, kill(2) can only be used to send a signal to a process (i.e., thread group) as a whole, and the signal will be delivered to an arbitrary thread within that process.)

The use of the word kill is historic. The Linux Programming Interface says:

The term kill was chosen because the default action of most of the signals that were available on early UNIX implementations was to terminate the process.

Anyway, the point is that a kernel call is made to tell the other thread when an interrupt signal (SIGINT in the GLIBC signum.h) is sent. This does not appear to be the case in the Linux Java implementation that I am using (1.7.0-ea-b125 on Linux 2.6.32.9-70.fc12.i686).

My next post should (hopefully) be about what happens if a thread is waiting on a stream.

A Polite Interruption

We thought we were being clever when unit testing some IO code using PipedInputStreams instead of an implementation of InputStream that used system resources. Oops.

No less an expert than Brian Goetz is somewhat misleading when he says:

"The input and output stream classes may block waiting for an I/O to complete, but they do not throw InterruptedException, and they do not return early if they are interrupted." [1]

PipedInputStream behaves differently (from what I can tell) to all other implementations of InputStream when the thread blocking on its read method is interrupted. It returns immediately with an InterruptedIOException (basically, an InterruptedException that fits into the IOException class hierarchy).

From the JDK (1.6) source code:

    /**

     * The index of the position in the circular buffer at which the

     * next byte of data will be stored when received from the connected

     * piped output stream. in<0 implies the buffer is empty,

     * in==out implies the buffer is full

     * @since   JDK1.1

     */

    protected int in = -1;

.

.

    public synchronized int read()  throws IOException {

.
.

  while (in < 0) {

    if (closedByWriter) {

      /* closed by writer, return EOF */

      return -1;

    }

    if ((writeSide != null) && (!writeSide.isAlive()) && (--trials < 0)) {

      throw new IOException("Pipe broken");

    }

            /* might be a writer waiting */

    notifyAll();

    try {

        wait(1000);

    } catch (InterruptedException ex) {

      throw new java.io.InterruptedIOException();

    }

  }

The read() method it just checking to see if anybody called interrupt() on the Thread running this code and if they had then the exception is thrown.

Although a call to Thread.interrupt() ultimately hits a native method, using strace I could not see any kernel calls being made (JDK build 1.7.0-ea-b125, Linux 2.6.32.9-70.fc12.i686). It appears that interrupt() just sets a flag. That is all.

So, how do you stop a thread that's blocking on reading from a stream? One way is to close the underlying resource (eg, by calling Socket.setSoTimeout() if the stream is associated with a socket).

But another way is to use Java NIO. If you look at the Thread.interrupt() method, you'll see this code:

.
.

    /* The object in which this thread is blocked in an interruptible I/O

     * operation, if any.  The blocker's interrupt method should be invoked

     * after setting this thread's interrupt status.

     */

    private volatile Interruptible blocker;

.

.

    public void interrupt() {

.

.

    Interruptible b = blocker;

    if (b != null) {

      interrupt0(); // Just to set the interrupt flag

      b.interrupt();

      return;

    }

The object on which Thread.interrupt in turn calls interrupt is an instance of sun.nio.ch.Interruptible. This instance is set in the package protected blockedOn method and the call tree of this looks like:

blockedOn(Interruptible) : void - java.lang.Thread

blockedOn(Thread, Interruptible) : void - java.lang.new JavaLangAccess() {...}

[constructor] new JavaLangAccess() {...} - java.lang 

[callers]

blockedOn(Interruptible) : void - java.nio.channels.spi.AbstractInterruptibleChannel

begin() : void - java.nio.channels.spi.AbstractInterruptibleChannel

begin() : void - java.nio.channels.spi.AbstractSelector

Looking at java.nio.channels.spi.AbstractInterruptibleChannel, for instance, we find that the Interruptible is being used as a callback:

    interruptor = new Interruptible() {

    public void interrupt() {

      synchronized (closeLock) {

        if (!open)

          return;

        interrupted = true;

        open = false;

        try {

          AbstractInterruptibleChannel.this.implCloseChannel();

        } catch (IOException x) { }

      }

    }};

Whereupon:

"An implementation of this method must arrange for any other thread that is blocked in an I/O operation upon this channel to return immediately, either by throwing an exception or by returning normally." [2]

And this is how NIO works: the Thread class needed to be changed to accommodate the ability to interrupt a thread blocking on input. It also closes the underlying resource as explained in Java NIO:

"[T]he blocked thread will be sent a ClosedByInterruptException.  Additionally, if a thread's interrupt status is set, and that thread attempts to access a channel, the channel will immediately be closed, and the same exception will be thrown... It may seem rather draconian to shut down a channel just because a thread sleeping on that channel was interrupted. But this is an explicit design decision made by the NIO architects. Experience has shown that it's impossible to reliably handle interrupted I/O operations consistently across all operating systems. The requirement to provide deterministic channel behavior on all platforms led to the design choice of always closing channels when I/O operations are interrupted. This was deemed acceptable, because a thread is most often interrupted so it can be told to shut down. The java.nio package mandates this behavior to avoid the quagmire of operating-system peculiarities, which is especially treacherous in this area. This is a classic trade-off of features for robustness." [3]

[1] http://www.ibm.com/developerworks/java/library/j-jtp05236/index.html
[2] http://docs.oracle.com/javase/6/docs/api/java/nio/channels/spi/AbstractInterruptibleChannel.html
[3] Java NIO (O'Reilly) - Ron Hitchens

Freaky Leaks

In my last post, I described problems with sending ICMP packets in Java. As the lesser of the evils, we instead spawned a new process that used the command line ping. We did this using java.lang.ProcessBuilder. But when we had to fire off hundreds of requests per second, we ran into problems.

Firstly, on a Sun box it was slow. Firing up a new process was expensive as (so I am told) SunOS must initiate the memory for ping every time.

[Apparently, you can hope to improve this by setting the sticky bit on the file (eg, with chmod 1755 /tmp/test.sh). The sticky bit is "one of the status flags on a file that tells UNIX to load a copy of the file into the page file the first time it is executed. This is done for programs that are commonly used so the bytes are available quickly" (Unix Unleashed p1270). This is quite an old book and the Linux chmod man pages say "on some older systems, the bit saves  the program’s text image on the swap device so it will load more quickly when run".]

Anyway, it turns out that our software was to run on Linux which was much faster at repeatedly starting new processes anyway. However, under heavy load (but non-deterministically) we started seeing java.io.Exceptions saying Bad file descriptor and Too many open files.

Sure enough, running lsof -p PID showed lots of open pipes for our Java process. Hitting the Garbage Collection button on JConsole seemed to help but was didn't solve the mystery.

We were draining the stream from the Process (as outlined in a previous blog post) using a Stream Gobbler but we closed it after use. By trial and error, we looked at the other streams associated with this Process - the error and output streams. Although we never got the reference for them from the Process, we discovered that these need closing too. Why - we have no idea.

[The reason forcing Garbage Collection helped was that the particular instance of the abstract Process (UNIXProcess) for our environment creates a java.io.FileInputStream that has a finalize() method that closes an associated Channel (if there is one) as well as calling the native method to close the stream.]

This is one of those conditions where increasing the memory actually makes things worse. Without the Garbage Collecting reaping these references, the operating system eventually hits its limit for open files (see /proc/PID/limits).