My IntelliJ IDEA 'wow' Moments

I've been using Eclipse for years. It's been my IDE #1. But lately it got slow. Very slow. Especially when switching branches and Eclipse tried to catch up with the changes. At some point it annoyed me so much, that I decided to give IntelliJ IDEA a try. I had several team mates using IDEA and being totally excited about it
Well, I switched, and I didn't regret this. While there are a lot of good features (like type suggestions which very often suggest exactly what you need, or search by typing everywhere in the UI), here are some features which really made me 'wow'.

Intentions

Intentions is a way to quickly modify code. ALT-ENTER is you shortcut to access intentions. Depending on the context IntelliJ will suggest you to do different things. F.e.: invert a if-clause condition, create JavaDoc, initialize a field by adding a constructor parameter. You can quickly create a lot of boilerplate code by pressing ALT-ENTER and ALT-INSERT (create code) in turn.

Structural Search

Ever wanted to find a interface which complies to a specific structure? Well, I did. Back in my Eclipse times I wondered if there is a public interface which has exactly one void method expecting exactly one generic parameter. The idea was to implement a call back which will receive one value. Sure, I could have written the interface myself, but this requirement appeared so common to me, that I suspected, that there is some public interface already doing exactly this. Well, with features provided by Eclipse I was stuck.

Until I switched to IntelliJ and discovered Structural Search (CTRL-SHIFT-S). It allows you to search for, well...., structures. You specify something like a multi line template, and let IntelliJ search for everything which matches this template. For my specific needs, the template looked like:

interface $Class$ {   void $MethodName$($ParameterType$ $Parameter$); }

Each parameter is configurable by constraints like pattern, min count, max count, if it's read from or written to, etc.... For my purpose I set $MethodName$ name and $Parameter$ to be exactly one. This led to too many interfaces having this exact structure I was looking for, but they didn't match quite well. Eventually I discovered one interface which looked exactly like what I was looking for. The method was named 'execute'. So I modified it in the search and I also changed the type to a common generic type name to see how many of this kind are there:

interface $Class$ {   void execute(T $Parameter$); }

This yielded exactly one match. Sadly a inner class, but luckily a public static one. So I just used it.

public class ActionCell<C> extends AbstractCell<C> {  public static interface Delegate<T> {  void execute(T object);  }    ... }

Inspections

Inspections is the IntelliJ way of static code analysis. The fact that there is static code analysis itself is probably not so 'wow', after all there are a lot of tools out there providing exactly this. But since it's integrated into the IDE in the tightest way I experienced until now, it gives you an awesome coding experience. What it makes even more 'wow' is that nearly each inspection has an associated quick fix. Press ALT-Enter and let IntelliJ convert the code for you. Additionally IntelliJ features inspection rules I haven't seen in other products yet. For example it will offer you to generalize List parameters to Collection or even Iterable if you don't use features of the sub interfaces. IntelliJ features 632 inspections for several languages: Java, HTML, CSS, JS, XML.

Mighty Break Points

I love this! I know conditional break points already from Eclipse. But check this out:

• Chose whether you want to suspend all threads if a break point is hit, or only the thread which hit the break point.
  
• Log a message to a console when a break point is hit
  
• Log a evaluated expression to console when a break point is hit
  
• Limit break point triggering to only one single instance of a class (you can chose the instance at run time)
  
• Limit break point triggering to only one class implementation of the base class.
  
• Automatically disable the break point once it was hit.
  
• Automatically re-enable the break point after another break point was hit.
  
• Create 'method break' points. This allows you to create break points based on class name and method name patterns. They will be triggered on entry and on exit of the method. This way you can super easy track (log lines) enter and exit of methods.
  
• Create breakpoints which will trigger if a field is accessed or modified (for fairness: Eclipse also supports field break points).
  

Live Templates

Live Templates are a way to generate code in IntelliJ. The trick is: it allows variables, which will be filled depending on the context. Live Template suggestions will appear whenever you type the configured abbreviation, or when you press CTRL-J. Type 'psf' in class context, and the 'public static final' template will be suggested. Live Templates are context aware. You won't get this suggestion if you're in a method body. Type "iter" and hit enter. IntelliJ will create a for-each block and automatically pick an iterable variable from the current context and prefill the for declaration. Additionally it will correctly choose the item type and create a meaningful item name. The cursor will be placed on the iteratable variable. If you don't like the automatic selection, type what you want to have iterated. IntelliJ will automatically update the item type and the item name. Fancy, eh? Next example: I had problems when writing JavaDoc because in IntelliJ you have to type {@link until the IDE starts suggesting classes (in Eclipse you directly start typing the class name). So I fixed this myself using Live Templates:

{@link $LINK$}

The variable $LINK is configured to be the result of the complete() function, which will open the type suggestion box. Whenever I type @link and hit enter, IntelliJ will complete the expression and offer a type selection for me. Next: Creating a Logger declaration:

private static final java.util.logging.Logger LOG = java.util.logging.Logger.getLogger($CURRENT_CLASS$.class.getName());

$CURRENT_CLASS$ is configured to be className(), which returns the current class name. Packages will be automatically converted to imports if possible, which creates this nice code (for class MyClass):

private static final Logger LOG = Logger.getLogger(MyClass.class.getName());

Analyze Stacktrace

You received a stack trace and want to examine the code places in the project. Stop! Don't look up the classes manually. Hit CTRL-SHIFT-A ('Enter action') and type "stacktrace". This will suggest you: "Analyze Stacktrace...". Paste the stack trace there. A tool window opens containing the stack trace with links which directly jump into code. Great time saver!

Do we need to synchronize everything?

Evaluation of ThreadSafe made me think about the Java Memory Model and it's implications on threaded programs. In tech jibberish the Java Language Specifications states that a thread is only guaranteed to see memory values modified by other threads if it synchronizes to them. It is not enough if only the writing thread uses a synchronize statement. Each thread which needs to see up to date values, needs to synchronize (enter the synchronized statement). Even more restrictive: thread T1 is only guaranteed to see all changes T2 did, before releasing monitor L, when it also acquires monitor L before reading the values (in JLS language: "An unlock action on monitor m synchronizes-with all subsequent lock actions on m (where 'subsequent' is defined according to the synchronization order)", chapter 17.4.4 Java Language Specification).

Example: (globalInt == 0 at the beginning)

T1	T2
globalInt = 3;
	int x = globalInt; // may be 0 or 3

The Java Memory Model does not define what T2 is going to see. Now with synchronization but different monitors:

T1	T2
synchronized (L1) { globalInt = 3; }
	int x; synchronized (L2) { x = globalInt; // may be 0 or 3 }

Even though it uses synchronization and even if T2 runs after T1 finished, T2 is not guaranteed to see the new value. The Java Memory Model guarantees this only for this case, synchronizing to the same monitor (volatile and final are also possible, they will be discussed later):

T1	T2
synchronized (L1) { globalInt = 3; }
	int x; synchronized (L1) { x = globalInt; // will see 3, if executed after T1 }

If that's true, what does this mean to a real case scenario like "initialize once, use multiple times":

private static volatile Map<String> map;
 
public Map<String> getMap() {
 if (map == null) {
  synchronized (this) {
   if (map == null) {
    Map<String> newMap = new HashMap<>();
    fillMap(newMap);
    map = newMap;
   }
  }
 }
 return map;
}

This is a map lazily initialized by a classic double-checked idiom. It is correctly implemented as of Java 1.5. This example uses a HashMap instead of a ConcurrentMap for optimization purposes. Since the map is used read-only after initialization, this is save. volatile makes sure other threads are going to see the new reference written to the variable map. But what happens to the elements of the map? The map reference is volatile, but the map elements are not. You learned previously that two threads need to synchronize to the same monitor if they want to make sure to see the same values. But in this case some readers may never reach the synchronize statement if the initialization was finished already. So what are the readers guaranteed to see?

Java Memory Model - Enlightened

Volatile

The promise the Java Memory Model makes for locks also goes for volatile reads and writes. It defines, that all writes to a volatile variable synchronize-with all reads of the same variable (JLS 17.4.4). This means, once the reader threads read the variable map, they are guaranteed to see all changes the writer thread did before writing to map. This means, assigning the new HashMap instance to a local variable (newMap) first and then assigning it to the field (only after it is fully initialized), is crucial for two reasons:

1. Assigning map before fillMap() would reveal the reference to the newly created map to other threads before initialization is finished. This means other threads could see inconsistent data. Additionally this might lead to serious problems when get() and put() are executed concurrently (HashMap is not thread safe).
2. The Java Memory Model guarantees visibility only for writes which happened before the write to a volatile field. This means all writes after assignment of map are not guaranteed to be visible to other threads.

Non-Volatile

There is another way to make it work according to the Java Memory Model if the object doesn't has to be created lazily. The Java Language Specification says: "An object is considered to be completely initialized when its constructor finishes. A thread that can only see a reference to an object after that object has been completely initialized is guaranteed to see the correctly initialized values for that object's final fields." (JLS 17.5). So can you rewrite the example above in this way?:

private static final Map<String> map = new HashMap<>();
 
public Map<String> getMap() {
 if (map.size() == 0) {
  synchronized (this) {
   if (map.size() == 0) {
    fillMap(map);
   }
  }
 }
 return map;
}

No, you cannot rewrite it like this. Apart from the obvious problem that, the map could be modified while it is being read (once one element was added), there are no data visibility guarantees according to the Java Memory Model regarding the map elements. Since the map field is not volatile any more, there is no synchronizes-with relationship between threads any more. But this will work:

private static final Map<String> map = new HashMap<>();
private static volatile initialized = false;

public Map<String> getMap() {
 if (!initialized) {
  synchronized (this) {
   if (!initialized) {
    fillMap(map);
    initialized = true;
   }
  }
 }
 return map;
}

Now reading of initialized synchronizes-with the write of initialized variable and thus all other writes happened until that moment. But then we're back at using volatile fields. The following approach works the best, when you can go completely without lazy initialization:

private static final Map<String> map = createAndFillMap();

public Map<String> getMap() {
 return map;
}

The next sample will work also AND is lazy initialized, but it tries to be smart and thus should not be your first choice (Don't Be Too Smart).

public Map<String> getMap() {
 return MapHolder.map;
}
 
private static class MapHolder {
 private static final Map<String> map = createAndFillMap();
}

This implementation relies on the Java Language Specification guarantee, that classes are loaded when they are used for the first time (JLS 5.3).


But we're still not done talking about finals. If you read the Java Language Specification guarantee for final fields carefully you noticed this part: "... after that object has been completely initialized is guaranteed to see the correctly initialized values for that object's final fields.". Completely initialized is defined by finishing the constructor. Thus if the constructor leaks the reference to the object being constructed, there are no guarantees about thread visibility of the final field.

public class Counter {
 private final AtomicInteger counter;
 
 public Counter(int startValue) {
  counter = new AtomicInteger(startValue);
  CounterRegistry.register(this);
 }
}

The constructor above leaks the reference before the constructor is finished. If a foreign thread picks up the reference (before the constructor finished) it may or may not see correct values. In general: avoid leaking this from constructors.

ReadWriteLock Implementation

Just out of curiosity: how is ReadWriteLock implemented? After all this lock features distinct handling of write-locking and read-locking. If these are separate locks, how does this comply to the Java Memory Model, which states that the same monitor has to be used?

The ReentrantReadWriteLock implementation of ReadWriteLock uses two local fields readerLock and writerLock which internally use the same Sync object. Sync is a implementation of AbstractQueuedSynchronizer. And AbstractQueuedSynchronizer in turn uses a internal volatile field. So it boils down to: ReentrantReadWriteLock is implemented - in perfect harmony with the Java Memory Model - using one volatile int field (using LockSupport.park() to wait if acquiring write lock doesn't succeed immediately).

Compiler Optimizations Allowed By the Java Memory Model

The Java Memory Model preserves great freedom for optimizations of compilers. The whole JMM guarantees build around "happens-before", "synchronizes-with" relationships and "well-formed execution" rules. The definitions go like "a read has to see the effects of a write, if that write came before the read in program order, and there was no other write in between". It doesn't say that the write actually has to happen when the write command is encountered in program order. It only states that the read has to see the effects. So it's completely valid for the compiler to move the write just immediately before the reading line. Or: let the write happen only to processor registers and write it back to memory much later when the compiler thinks is's appropriate. Or even: remove the write completely if there is no read which needs to see the write effects.

If you take a look at this simple code snippet:

x = 0;
y = 1;

It wouldn't surprise anyone if the compiler would reorder the two statements. There is probably no optimization benefit, but there is also no obvious reason why the compiler shouldn't. But take this code:

// double-checked idiom wrongly implemented
private Object instance;
Object getInstance() {
  if (instance == null) {
    synchronized(this) {
       if (instance == null) {
          Object helper;
          synchronized (this) {
             helper = new Object();
          }
          instance = helper;
       }
    }
  }
  return instance;
}

(the code is discussed in Bidirectional Memory Barrier as a attempt to implement the double-checked idiom without volatile keyword) The Java Memory Model does not prevent the compiler to change the code to:

private Object instance;
Object getInstance() {
  if (instance == null) {
    synchronized(this) {
       if (instance == null) {
          synchronized (this) {
           Object helper;
           helper = new Object();
           instance = helper;
          }
       }
    }
  }
  return instance;
}

And then in the next step:

private Object instance;
Object getInstance() {
  if (instance == null) {
    synchronized(this) {
       if (instance == null) {
          synchronized (this) {
             instance = new Object();
          }
       }
    }
  }
  return instance;
}

There are rules which prevent the compiler to move lines inside a synchronized block out of the block. But there is no rule which forbids to move lines inside the synchronized block. Surprising, isn't it?

The lesson from this is: don't try to be too smart. Stick to this basic rules of the Java Memory Model which are: If there is something which can be accessed by multiple threads, then:

• make it final, OR
• make it volatile, OR
• use the same monitor to coordinate access to the data

Hard Side of Live (Hardware)

Until now I talked only about theoretical guarantees the JMM offers. This gives the freedom to the Java developer to code against one memory model. Remember: Java is designed to run everywhere. If Java wouldn't offer something like a JMM, the developers would need to bother themselves with all the difficulties and pitfalls of different architectures. But how is the JMM applied to a specific architecture, let's say: x86?

To recapitulate: we were concerned with 'visibility' of updated memory values. We talked about threads not seeing new values, because they still use their (old) cache. The cure in terms of JMM was to use volatile or synchronized.

A lot of people think when volatile is written to, or when a synchronized block is left, CPU caches are flushed, so updated values will be read. But in fact there is no CPU operation like "flush the cache". All modern x86 CPUs try very hard to keep the CPU caches transparent and make the memory appear consistent to the developer. They do this by implementing cache coherency. So memory writes are automatically detected and updated in all caches. And: this also only applies to multi processor systems, or processors having a memory cache for each core. For a single CPU, single core system each thread ultimately sees the newest values.

So does this mean for x86 architecture the JMM is not necessary? Does it add unnecessary synchronization statements or is it NOPed out (replaced by "no operation" instructions) when compiled? Far from it! Even with cache coherency the JMM is required. Required to:

• guarantee read/write order
• atomicy when writing/reading values which cannot be written/read atomically
• get "caches" in line you probably even didn't think of: registers
• offer guarantees even in case of optimizations applied on top of the memory cache.

Memory Access Reorderings

Memory access can be reordered by multiple instances. It can be reordered by the compiler. This was already noted earlier. There are some restrictions to reordering introduced by the JMM, but compilers still have a lot of freedom to change the execution order compared to program order (as in the source). So when we have code like

x = 3;
written = true;

nothing prevents the compiler to reorder these statements making this code fail:

while (!written) wait();
assert x == 3;

But even when the compiler did not change the order, the CPU might change it. Modern CPUs try to parallelize as much as possible. When code is executed in parallel it may appear to run out of order. Take for example a floating point calculation, a store of the calculation result to memory, and a subsequent load of another variable from memory:

float f2 = f1 * 4.38473723;
if (x == 3) { ... }

The load of x might be executed in parallel to the floating point calculation. So the value of x might be read from memory while f2 is still not written to memory yet.

Atomic Writing/Reading of Values

Some Java datatypes can be written and read by the processor in one operation. For example a int on a 32 bit system. While other datatypes require multiple operations. For example a long (64 bit) on a 32 bit system. Having two operations to write a value allows other processors to observe a half written (thus inconsistent) value. For variables declared volatile Java needs to make sure the variable appears to be written and read atomically.

Registers

There are more types of "cache" than the usual CPU memory cache everyone thinks of when someone says "cache". The Java compiler could optimize code by moving variables temporary to CPU registers. This can be considered a cache too. Take this code:

for (int i = 0; i < 1000; i++) {
 j = j + 10
}

It is almost certain that the variable i will only exist in CPU registers. It's also very likely that j will be loaded to a CPU register at the beginning of the loop, and only written back to memory when the loop finishes. No other threads will be able to observe the intermediate steps applied to j. If one needs to make sure other threads will observe the changes, he needs to tell this explicitly to Java.

Optimizations of the Cache

In their effort to speed up CPU memory access CPU designers applied even optimizations to the cache, which is actually a optimization on itself. There are so called store buffers. They are used to queue stores to memory applied by the processor. Using those the processor can continue it's work without to have to wait for the store operation to complete. With store buffers in use, a couple of things can happen:

• The store operation itself is delayed.This means some writes/reads may appear out of order.
• There are no guarantees in which order values in the store buffer are going to be written to memory. It's possible that, if two variables lie next to each other in memory, they are written in one operation, even if there were other store operations in between.

And there are invalidation queues. A little background on this: One way how CPUs implement cache coherency is to use the MESI cache coherency protocol. MESI stands for Modified Exclusive Shared Invalid and names the states cache entries may have. When a CPU needs to modify a variable it sends a invalidation message to other CPUs. The others mark the entries in their caches as invalid (if they store the entry in their cache at all). The modifying CPU needs to wait until all CPUs confirmed the invalidation message. This takes time. A lot of time in CPU processing terms. So invalidation queues were introduced. Each CPU immediately acknowledges a invalidation message and stores a entry in its invalidation queue. The queue is processed later on. This means there is some time between a invalidation message and the message beeing applied in all caches. So it's possible for CPU0 to process it's store buffers and update all values in memory, while CPU1 still has not yet processed the invalidation queue. So CPU1 could read a old value for a variable from it's cache while the invalidation queue is still not yet processed.

So what does Java do to guarantee consistency in all those cases? Java utilizes so called memory barriers. In simple terms a memory barrier forces those queues (store buffers, read buffers, invalidation queue) to run dry before execution can continue. When a volatile variable is written, a single cache entry is invalidated and the invalidation queue and store buffers are processed.

Lessons we learned

Consistency and performance are conflicting. ;) But you knew this already, right? There are a lot of subtle things going on. And the magic spell for the Java developer to handle all this is the Java Memory Model. The JMM is a nice thing to rely on, facing the amount of architectures the code could be executed on.

Is the Double-Check Idiom really *really* fixed?

The double-check idiom is a way to reduce lock contention for a lazy initialized thread safe class. Unfortunately it used not to work. Luckily it was fixed. But under which conditions is it to be considered fixed?

Preface: There is a magnificent article covering this topic: Double Check Locking by Bill Pugh et al.. This article tries to rephrase the facts from the linked resource in a simpler way. Anyone interessted in the deep core details should read the article by Bill Pugh et al.

When Java 1.4 was the most recent release the so called Double-Check Idiom was considered broken. Due to the Java memory model specifications it was not guaranteed to work as one would expect. This is the double-check idiom in it's pure form:

piblic class Boss {
  private String name;
  
  public Boss() {
    this.name = "";
  }
}

public class Company {
  private Boss boss = null;
  
  public Boss getBoss() {
    if (boss == null) {
      synchronized (this) {
        if (boss == null) {
          boss = new Boss();
        }
      }
    }
    return boss;
  }
}

There are two major reasons why this could fail: 1. operation reordering; 2. memory caches.

Operation Order:
The Java memory model guarantees that all memory operations will be finished before the synchronized block is left. But it doesn't say anything about the order of the memory operations inside the synchonized block. A compiler might change the order of memory operations. If the constructor of Boss is inlined, the assignment of boss field (pointing to memory holding boss instance) could be executed before the instance fields of the Boss class are assigned by the constructor code. This means a concurrent thread could see boss!=null while the initialization is still not finished.

Memory Caches:
Each thread may have it's own local cache of the main memory. So even if the initializing thread did finish all memory write operations, a concurrent thread might see the new value of the Company.boss field but the old (uninitialized) memory values for the Boss class fields. This is what the Java Language Specification (Java 1.7) says about memory effects of the synchronized block:

JLS 17.4.4. Synchronization Order
... An unlock action on monitor m synchronizes-with all subsequent lock actions on m (where "subsequent" is defined according to the synchronization order). ...

So it guarantees that everything what thread A did before it left the synchronized block will be visible to thread B when it enters a synchronized block which locks on the same mutex. Note that it doesn't state anything about what is visible to threads which do not enter a synchronized block! So the changes from the double-checked idiom might be visible, might be partially visible or might be not visible to other threads.

Changes to the Java Memory Model in 1.5

Java 1.5 implements a more recent memory model specification. The modification which is interesting in this context is the change to access to volatile variables. The read or write of a volatile variable is not allowed to be reordered with respect to any previous or following read or writes. This means the compiler is not allowed to reorder the write of Company.boss field if it is declared volatile.

The fixed example from above would look like this:

public class Company {
  private volatile Boss boss = null;
  
  ....
}

Concluding: the double-checked idiom was really really broken before Java 1.5. It is really really fixed with Java >= 1.5 only when the the field being checked in the double-checked idom is declared volatile. If it is not, it's still broken.

Java polymorphism and equals()

Let's start by having a small introduction. The mother of all Java classes - Object - does define a equals() method, which is meant to return true if the passed instance is equal to the current instance. The default implementation is limited to comparing references. So it will only return true when the current and the passed object are the same. The equals() method is meant to be overridden by extending classes with meaningful logic. The implementation has to obey some requirements (from javadoc on Object.equals()):
The equals() method guarantees that...

• It is reflexive: for any non-null reference value x, x.equals(x) should return true.
• It is symmetric: for any non-null reference values x and y, x.equals(y) should return true if and only if y.equals(x) returns true.
• It is transitive: for any non-null reference values x, y, and z, if x.equals(y) returns true and y.equals(z) returns true, then x.equals(z) should return true.
• It is consistent: for any non-null reference values x and y, multiple invocations of x.equals(y) consistently return true or consistently return false, provided no information used in equals comparisons on the objects is modified.
• For any non-null reference value x, x.equals(null) should return false.

Quite a bunch. Luckily those requirements are often easy to achieve. Let's create a simple class and equip it with a equals method.

A Drink

public class Drink {
  private final int size;

  public Drink(final int size) {
    this.size = size;
  }

  @Override
  public boolean equals(final Object obj) {
    if (!(obj instanceof Drink)) return false;
    return equals((Drink) obj);
  }

  public boolean equals(final Drink other) {
    return this.size == other.size;
  }
}

This equals() implementation obeys all the requirements above. And I added a convenience method with the exact type. Note that equals(Drink) does overload Object.equals(Object) but it does not override it! The difference between those two will be important later.

A Drink? A Coffee? A Coke?

Now let's introduce polymorphism. We add two classes Coffee and Coke which extend the Drink class:

public class Coffee extends Drink {
  private final int coffeine;

  public Coffee(final int size, final int coffeine) {
    super(size);
    this.coffeine = coffeine;
  }

  @Override
  public boolean equals(final Object obj) {
    if (!(obj instanceof Coffee)) return false;
    return equals((Coffee) obj);
  }

  public boolean equals(final Coffee other) {
    if (!super.equals(other)) return false;
    return coffeine == other.coffeine;
  }
}

public class Coke extends Drink {
  private final int sugar;

  public Coke(final int size, final int sugar) {
    super(size);
    this.sugar = sugar;
  }

  @Override
  public boolean equals(final Object obj) {
    if (!(obj instanceof Coke)) return false;
    return equals((Coke) obj);
  }

  public boolean equals(final Coke other) {
    if (!super.equals(other)) return false;
    return sugar == other.sugar;
  }
}

The equals() methods are implemented here in a similar way. Everything looks fine, doesn't it? Let's see how the equals() methods behave:

final Drink drink = new Drink(15);
final Drink secondDrink = new Drink(15);

System.out.println("drink.equals(secondDrink): " + drink.equals(secondDrink));
System.out.println("secondDrink.equals(drink): " + secondDrink.equals(drink));

final Coffee coffee = new Coffee(15, 3);
final Coke coke = new Coke(15, 42);

System.out.println("coffee.equals(drink): " + coffee.equals(drink);
System.out.println("drink.equals(coffee): " + drink.equals(coffee));
System.out.println("coke.equals(coffee): " + coke.equals(coffee));

What’s the output? Your brain might tell you something like this:

drink.equals(secondDrink): true
secondDrink.equals(drink): true
coffee.equals(drink): false
drink.equals(coffee): false
coke.equals(coffee): false

But what’s the actual output? This:

drink.equals(secondDrink): true
secondDrink.equals(drink): true
coffee.equals(drink): true
drink.equals(coffee): true
coke.equals(coffee): true

Wow! What's happening? drink.equals(coffee) is passed a parameter of type Coffee. The best method match for this type is Drink.equals(Drink). This method does only compare the size field. Since it's equal it returns true. coffee.equals(drink) is passed a parameter of type Drink. The best method match for this type is.... Drink.equals(Drink)! Not Coffee.equals(Object)! So again only the size field is compared. The same goes for coke.equals(coffee): Drink.equals(Drink) is invoked.
First lesson: it’s a bad idea to implement convenience public equals() methods with different types than Object. Or in other words: do not overload equals(), override it.

Now let’s “fix” this problem by making the overloaded methods private. What will be the output this time? This:

drink.equals(secondDrink): true
secondDrink.equals(drink): true
coffee.equals(drink): false
drink.equals(coffee): true
coffee.equals(coke): false

Still not quite the output we're expecting. What’s happening now? When coffee.equals(drink) is invoked, the Coffee.equals(Object) method is executed, Drink instance is checked against “instanceof Coffee” and this evaluates to false. But when we invoke drink.equals(coffee) the equals() implementation in Drink is executed and the passed instance is checked against “instanceof Drink”. Since Coffee is a extension of Drink, this evaluates to true.

Not all Drinks are Coffees

So is polymorphism broken in Java? Not quite. It seems like instanceof is not the check you should use per default in equals(). It's sometimes important, we'll see in a minute, but usually what you'd like to do is to use Object.getClass() and compare the class of the passed instance to the class of the current instance:

public class Drink {
  ...

  @Override
  public boolean equals(final Object obj) {
    if (obj == null) return false;
    if (this.getClass() != obj.getClass()) return false;
    return equals((Drink) obj);
  }

  private boolean equals(final Drink other) {
    return this.size == other.size;
  }
}

// changes in Coffee and Coke similar

As specified by documentation of getClass(), it is guaranteed to return the same Class instance for the same class. So it is save to use the == operator. Note that obj.getClass() is compared against this.getClass() and not against Drink.class! If we'd compare against the hard coded class super.equals() invocations from extending classes would always fail for non Drink instances.

Second lesson: use Object.getClass() in equals() if unsure. Only use instanceof if you know what you do. ;)

Instanceof

Now when would one want to use instanceof in equals() implementations? The semantics of equals() implementations are actually up to you (as long you follow the restrictions stated at the beginning). In my example above I wanted to have Drink!=Coffee!=Coke. But that's just a definition thing. Sometimes you want to have a set of types behave like one type. The Java class library does this for lists and maps for example. A TreeMap and a HashMap are considered equal if they contain the same objects. Even though a TreeMap has an element order which a HashMap does not have. The types achieve this by having a AbstractMap class implement a equals() method which checks against "instanceof Map" and checks only Map properties. All extensions of AbstractMap do not override (and do not overload) equals().

One more thing

Don't forget to implement hashCode() if you override equals(). Both methods have a tight relationship. Whenever a.equals(b) returns true, also a.hashCode() has to be equal to b.hashCode()!

Memory leaks even with WeakReferences

A crash report arrived at my desk the other day. The system crashed because it ran out of memory. And the major memory consumer was a WeakHashMap. Very interesting, since WeakHashMaps are usually used to allow to free memory when it's needed.

First some background. Imagine you've build a JSP page which generates a HTML page with a lot of URLs on it. You construct those URLs from different parameters. You use URLEncoder since you need valid URLs independent of the URL parameter contents you print. Once everything works fine, you realize that your URLs share may strings. So URLEncoder is called very often unnecessarily. You try to optimize the situation by creating a cache for URLEncoder:

class CachedUrlEncoder {
 static private Map<String, String> encodedMap = new HashMap<String,String>();

 public String encode(String str) {
  String encodedStr = encodedMap.get(str);
  if (encodedStr == null) {
   encodedStr = URLEncoder.encode(str);
   encodedMap.put(str, encodedStr);
  }
  return encodedStr;
 }
}

(The example is not thread save by purpose. We are not talking about concurrency, are we? ;) Also notice, that the one parameter encode method is now deprecated, because it uses system default encoding to encode the string.)

This cache would fill up the memory very quickly. It's never cleared after all. But there is also no special point in time when the cache should be cleared. The cached data never becomes outdated. Actually a cache should use a lot of memory if memory is not required by other subsystems, and free the memory if it becomes required. For this purpose the Java runtime has the SoftReference, WeakReference and the utility classes which use them. WeakHashMap f.e. is the perfect match for this scenario. A WeakHashMap references the values using normal hard references, and the keys using weak references. As soon as the key is not referenced any more (soft or hard) the whole entry will be freed. Here's the example rewritten to use WeakHashMap:

class CachedUrlEncoder {
 private static Map<String, String> encodedMap = new WeakHashMap<String,String>();

 public String encode(String str) {
  String encodedStr = encodedMap.get(str);
  if (encodedStr == null) {
   encodedStr = URLEncoder.encode(str);
   encodedMap.put(str, encodedStr);
  }
  return encodedStr;
 }
}

That was easy. Sadly you will notice at runtime that this code contains a memory leak. A not so obvious one. Let's analyse the situation.

As I mentioned already the map entries will be freed as soon as the key is not referenced by hard or soft references any more. In our case this should be immediately. After we've written the encoded string to the output stream of the JSP page, the string is not referenced any more. Still we're experiencing a memory leak. As so often the devil is in the details. The Sun implementation of URLEncoder.encode() tries to optimize by returning the reference to the string it received, if there is no encoding work to do. This is clever. It saves resources. But in this case this bit us really bad. If encode() returns the same reference the code will call Map.put() with the same reference as key and value. It'd look like:

encodedMap.put(str, str);

After that line the map has an entry with a weak reference to str and a hard reference to str. The entry itself prevents that it is garbage collected!

That's mean.

The fix is simple, once one knows the cause. We render the optimization of URLEncoder useless:

class CachedUrlEncoder {
 private static Map<String, String> encodedMap = new WeakHashMap<String,String>();

 public String encode(String str) {
  String encodedStr = encodedMap.get(str);
  if (encodedStr == null) {
   encodedStr = URLEncoder.encode(str);
   if (str == encodedStr) {
    encodedStr = new String(encodedStr);
   }
   encodedMap.put(str, encodedStr);
  }
  return encodedStr;
 }
}

Luckily the implementation of the string constructor is also smart. It does not copy the char data. A new string object is created and references the same char array as the old string. This is safe since strings are immutable. So the fix does create some overhead but not that much.

A Executor is not a Thread - or: correct ThreadPoolExecutor error handling

Java 1.5 introduced the Executor framework. In summery: if you have some tasks (let's say: 20) and you want them to be processed in parallel by a couple of threads (let's say: 6), then a Executor is the solution you want to look for. But there are some surprising caveats which may lead to problems. And they are hard to diagnose.

Introduction

Executor is a interface. The ExecutorService interface extends Executor. One of the standard implementations of ExecutorService is ThreadPoolExecutor. This one manages some threads in a pool and executes the tasks you give it. You do this in form of a list of Runnable instances. A typical Runnable implementation looks like this:

public class MyWorker implements Runnable {
    private final Object data;

    public MyWorker(final Object data) {
        this.data = data;
    }

    @Override
    public void run() {
        process();
    }

    private void process() {
        // process data
    }
}

You initialize a ThreadPoolExecutor like this:

int nThreads = 8;
Executor executor = new ThreadPoolExecutor(nThread, nThreads, 0, TimeUnit.SECONDS, new LinkedBlockingQueue<Runnable>());

And since this is so cumbersome, there is a helper class for that:

int nThreads = 8;
Executor executor = Executors.newFixedThreadPool(nThreads);

This is how to use a Executor wrapped in a method:

public void executeRunnables(final List<Runnable> runnables) {
    int nThreads = 8;
    Executor executor = Executors.newFixedThreadPool(nThreads);
    for (final Runnable command : runnables) {
        executor.execute(command);
    }
}

This method would return to the caller immediately after creating the executor. But usually you want to wait until all the tasks have been processed before returning to the caller. For this purpose ExecutorService defines the methods shutdown() and awaitTermination():

public void executeRunnables(final List<Runnable> runnables) throws InterruptedException {
    final int nThreads = 8;
    final ExecutorService executor = Executors.newFixedThreadPool(nThreads);

    for (final Runnable command : runnables) {
        executor.execute(command);
    }

    executor.shutdown();

    executor.awaitTermination(2, TimeUnit.SECONDS);
}

(notice the change of executor type from Executor to ExecutorService) shutdown() puts the executor in "finish your work" mode. In this mode the executor will not accept new tasks. awaitTermination() waits until all threads processed all tasks. The time out takes care that your program doesn't wait forever if something goes wrong.

Error handling

So what if something goes wrong? What if one of your tasks throws an exception? How do you handle that? How do you even know something gone wrong? One possible approach is to catch and collect all exception inside the Runnable implementation:

public class MyRunnable implements Runnable {
    private final Object            data;
    private final List<Exception>   exceptions;

    public MyRunnable(final Object data, final List<Throwable> exceptions) {
        this.data = data;
        this.exceptions = exceptions;
    }

    @Override
    public void run() {
        try {
            process();
        } catch (final Exception ex) {
            exceptions.add(ex);
        }
    }

    private void process() {
        // process data
    }
}

But this approach has two major drawbacks: First, it would also catch the InterruptedException which may be used to control the thread under normal conditions. And second, the responsibility of error handling is moved to each Runnable implementation. You are going to implement a lot of Runnables and it's easy to forget something. Executor error handling calls for a generic solution.

Java 1.5 adds a method to register exception handlers for exactly this purpose: Thread.setUncaughtExceptionHandler(). Exceptions which are not handled by the run() method of the Thread implementation, will be forwarded to this handler. Let's modify the above example to use a exception handler:

/**
 * Implementation of a UncaughtExceptionHandler, which stores all exceptions in a List.
 */
private static class ExceptionCollector implements UncaughtExceptionHandler {
    final List<Throwable> exceptions = Collections.synchronizedList(new LinkedList<Throwable>());

    @Override
    public void uncaughtException(final Thread t, final Throwable e) {
        exceptions.add(e);
    }
}

/**
 * A ThreadFactory, which registers a UncaughtExceptionHandler.
 */
private static class ThreadWithUncaughtExHandlerFactory implements ThreadFactory {
    private final UncaughtExceptionHandler    exHandler;

    public ThreadWithUncaughtExHandlerFactory(final UncaughtExceptionHandler exHandler) {
        this.exHandler = exHandler;
    }

    @Override
    public Thread newThread(final Runnable r) {
        final Thread t = new Thread(r);
        t.setUncaughtExceptionHandler(exHandler);
        return t;
    }
}

public void executeRunnables(final List<Runnable> runnables) throws InterruptedException {
    final int nThreads = 8;
    // UnhandledExceptionHandler which will collect Exceptions:
    final ExceptionCollector exHandler = new ExceptionCollector();
    // create a executor with a custom Thread factory:
    final ExecutorService executor = Executors.newFixedThreadPool(nThreads,
                                       new ThreadWithUncaughtExHandlerFactory(exHandler));

    for (final Runnable command : runnables) {
        executor.execute(command);
    }

    executor.shutdown();

    executor.awaitTermination(2, TimeUnit.SECONDS);

    if (exHandler.exceptions.size() > 0) {
        // rethrow first of the collected exceptions
        throw new RuntimeException(exHandler.exceptions.size() +
                    " exceptions occured. First exception:", exHandler.exceptions.get(0));
    }
}

Now this looks good! If a exception is not handled by the Runnable implementations the Thread will get it and the Thread will pass it on to the uncaught exception handler. The handler will store it in the list for later usage. executeRunnables() waits until all Threads are done with work and checks the exception list then. If there is a entry it will be wrapped in a RuntimeException and rethrown. Instead of just passing the first exception, it's also possible to append the whole exception list to the thrown exception. This way the caller will be notified.

Or won't it?

Well, this article would probably not exist if everything would be that simple like it looks. The truth is: it doesn't work. At least not always. Which makes it even worse. Sometimes it works and sometimes it doesn't.

Problem analysis

A Thread is capable of processing only one Runable in general. When the Thread.run() method exits the Thread dies. The ThreadPoolExecutor implements a trick to make a Thread process multiple Runnables: it uses a own Runnable implementation. The threads are being started with a Runnable implementation which fetches other Runanbles (your Runnables) from the ExecutorService and executes them: ThreadPoolExecutor -> Thread -> Worker -> YourRunnable. When a uncaught exception occurs in your Runnable implementation it ends up in the finally block of Worker.run(). In this finally block the Worker class tells the ThreadPoolExecutor that it "finished" the work. The exception not yet arrived at the Thread class but ThreadPoolExecutor already registered the worker as idle.

And here's where the fun begins. The awaitTermination() method will be invoked when all Runnables have been passed to the Executor. This happens very quickly so that probably not any of the Runnables finished their work. A Worker will switch to "idle" if a exception occurs, before the Exception reaches the Thread class. If the situation is similar for the other threads (or if they finished their work), all Workers signal "idle" and awaitTermination() returns. The main thread reaches the code line where it checks the size of the collected exception list. And this may happen before any (or some) of the Threads had the chance to call the UncaughtExceptionHandler. It depends on the order of execution if or how many exceptions will be added to the list of uncaught exceptions, before the main thread reads it.

A very unexpected behaviour. But I won't leave you without a working solution. So let's make it work.

Correct solution

We are lucky that the ThreadPoolExecutor class was designed for extendibility. There is a empty protected method afterExecute(Runnable r, Throwable t). This will be invoked directly after the run() method of our Runnable before the worker signals that it finished the work. The correct solution is to extend the ThreadPoolExecutor to handle uncaught exceptions:

public class ExceptionAwareThreadPoolExecutor extends ThreadPoolExecutor {
    private final List<Throwable> uncaughtExceptions = 
                    Collections.synchronizedList(new LinkedList<Throwable>());

    @Override
    protected void afterExecute(final Runnable r, final Throwable t) {
        if (t != null) uncaughtExceptions.add(t);
    }

    public List<Throwable> getUncaughtExceptions() {
        return Collections.unmodifiableList(uncaughtExceptions);
    }
}

Linux Process Memory Layout

This article describes how the memory structure of each Linux process does look like.
Each Linux process starts with several memory blocks. A code block to hold the executable code of the program, stack blocks (one for each thread) and several data blocks (one for constants of the program, one for dynamic usage). Sometimes those blocks are called segments. In case of the data blocks we'll call them arenas in this article. This initial arena block is called the main arena. You'll see it named as "[heap]" in the contents of /proc/xxx/maps of any Linux process (replace xxx by PID).

Basics

A Linux program can use the system functions brk()/sbrk() to change the size of it's main arena. It can also use mmap() to get new arenas from the system. But usually progams will use a memory management library instead of the system functions. The memory management library which is used by default is the libc library. One can override this, but usually all linux processes use this library. It exports functions like malloc(), realloc(), calloc(), free() to the program. The program uses those to allocate and free memory. And the memory management library itself uses brk(), sbrk(), mmap() to allocate the memory from the system.

libc creates data structures inside of the arenas to split the arena in smaller blocks. We'll call this structures "heap". So arenas are huge blocks issued by the system to libc. Heaps are the data structures inside this arenas (yes, there are several heaps) to manage smaller blocks.

Java/JNI memory layout

But a process doesn't have to use the libc functions. Java for example has it's own memory management functions. Java starts just like every other linux process. But then it uses mmap() to allocate memory for it's own Java heap (and for the other Java memory areas, like PermGenSpace for classes or code cache for the JIT compiler) according to the size settings ("-Xmx" and others). All the memory which is used by Java objects and classes is *not* managed by libc. But Java has also parts which are implemented in native (JNI) code. If this native code requires memory it will use libc functions. Also (JNI) libraries loaded by Java are just like the Java native part, they also use libc functions.

Difference vss/rss

When using several Linux tools, which do report memory usage (ps/top), you will stumble upon the two TLAs: vss, rss. (aliases are: vsz, rsz) They mean:

• Virtual Set Size 
• Resident Set Size 

They exist to name two different memory allocation types. vss names the reserved address space. Rss names the physical allocated memory (simplefied, see Details For The Hard Core Developer 1). One could (theoretically) allocate 16.777.216 terabytes of address space without using even one byte of physical memory. Only when the program asks the system to allocate physical memory, physical memory is allocated (simplified, see Dnowledge For The Hard Core Developer 2). How does the system tell between address space allocation and physical memory allocation? When the process allocates memory from the system it passes access permission to mmap():

// mmap() syntax: void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);

void *block1;
// this will allocate 200 bytes without any access permissions at a starting address choosen by the system
block1 = mmap(NULL, 200, PROT_NONE, MAP_PRIVATE, 0, 0);

This is just a address space reservation. The address space starting at block1 and spanning 200 bytes will not be issued at any other mmap() call. How does a process allocate physical memory? By changing the access permissions:

// syntax of mprotect(): int mprotect(const void *addr, size_t len, int prot);
mprotect(block1, 100, PROT_READ | PROT_WRITE); 

After this invocation the first 100 bytes will be available for read and write. The remaining 100 bytes will still be just reserved address space.

But why we need to reserve address space anyway? If you are curious, see "Details For The Hard Core Developer 3".

How libc Manages Memory

As already said, the system allocates the main arena block for each process at process start up. libc creates a heap data structure inside of this main arena block. This is the main heap. libc supports multi threaded programs. So invoking the memory functions in parallel is possible. Like any other program, libc has to use locking to guarantee data structure integrity while several threads call libc functions at the same time. To increase performance, libc tries to reduce lock contention (lock blocking) by having one lock per heap and by creating more heaps. When a memory request arrives at libc, it tries to lock the heap which was last used by the thread. If the thread did not use any heap yet, libc tries to lock the main heap. If locking fails, libc tries the next existing heap. If all heaps have been tested, libc creates a new heap. A heap is created by requesting a new arena from the system (mmap()) and writing heap structures into it:

void *arena;
// reserves 64MB address space. libc heaps start always at 64MB size.
arena = mmap(NULL, 64*1024*1024, PROT_NONE, MAP_PRIVATE, 0, 0);
// allocate necessary memory at the beginning of heap
mprotect(arena, 1000, PROT_READ | PROT_WRITE);
// after this invocation libc can use the first 1000 bytes of the reserved address space 

When a heap was successfully locked, libc tries to find a free block which does satisfy the requested size. If a block was found, it is returned. If no block was found, libc tries to increase the size of the heap. It can do this in two ways.

1. Allocating bytes in the reserved address space (by calling mprotect() and increasing the area which has read/write permissions in the arena). This can only succeed if there is still room to expand.
2. Increasing address space and allocating bytes there (By calling mremap(), which will assign more address space. Heaps are resized in 64MB steps.). This can only succeed if the address space bordering the end of the current arena is still free.

If both fail (arena is full, arena cannot be resized) a new heap will be created. So heaps are created in two cases: to satisfy memory needs, to reduce lock contention.

How can we use this knowledge to optimize the memory footprint of our program? Let's assume we have a process with 100 threads. And let's assume there is heavy load, so all 100 threads call libc at the same time. In this case libc will create 100 heaps, each of 64MB in size. (vss will instantly increase to 6,4GB, but rss will remain low, because the physical memory is not allocated yet.) This sounds not so bad yet (rss is still low). But let's continue this horror scenario. Let's assume this heavy load led to full exhaustion of the available memory. All 100 heaps are full. But the load stopped and the used memory is freed. Nearly everything is freed just some small blocks remain (which for example are used as a thread local buffer). Unluckily these buffers were allocated late, so that they lay at the "end" of the heap. The heap is nearly empty, just at the end there is this small block. libc is capable of shrinking the heaps to return memory to the system. If the free block at the end of the heap is big enough, libc shrinks the heap. But since there is a used block, libc cannot do this. The heap cannot have gaps. So even if the memory is not used by the program the rss and vss of the program will remain at 6,4GB.

So what do we learn from this? Don't use more threads than necessary. After all not all of those threads can run truly parallel. The system is limited to a much smaller number of CPU cores. Often waiting for resources is compensated by having more threads. If it's network resources, try to switch to asynchronous processing so the thread can do some other work, while the network interface is processing data. This way you will be able to reduce the number of required threads. The other thing we learned: If you use buffers, do free those buffers sometimes (This only applies for unmanaged languages like C. Java is able to move it's memory blocks to reduce fragmentation.).

/proc/xxx/maps

Everyone can have a look at the blocks issued by the sytem to the program. The file maps in the proc folder of each process contains this information. the contents look like this (example of bash process):

00400000-004e1000 r-xp 00000000 fc:00 524291                             /bin/bash
006e0000-006e1000 r--p 000e0000 fc:00 524291                             /bin/bash
006e1000-006ea000 rw-p 000e1000 fc:00 524291                             /bin/bash
006ea000-006f0000 rw-p 00000000 00:00 0
00ec7000-01224000 rw-p 00000000 00:00 0                                  [heap]
7fc285b08000-7fc285b14000 r-xp 00000000 fc:00 6419                       /lib/x86_64-linux-gnu/libnss_files-2.15.so
7fc285b14000-7fc285d13000 ---p 0000c000 fc:00 6419                       /lib/x86_64-linux-gnu/libnss_files-2.15.so
7fc285d13000-7fc285d14000 r--p 0000b000 fc:00 6419                       /lib/x86_64-linux-gnu/libnss_files-2.15.so
7fc285d14000-7fc285d15000 rw-p 0000c000 fc:00 6419                       /lib/x86_64-linux-gnu/libnss_files-2.15.so
7fc285d15000-7fc285d1f000 r-xp 00000000 fc:00 5919                       /lib/x86_64-linux-gnu/libnss_nis-2.15.so
7fc285d1f000-7fc285f1f000 ---p 0000a000 fc:00 5919                       /lib/x86_64-linux-gnu/libnss_nis-2.15.so
7fc285f1f000-7fc285f20000 r--p 0000a000 fc:00 5919                       /lib/x86_64-linux-gnu/libnss_nis-2.15.so
7fc285f20000-7fc285f21000 rw-p 0000b000 fc:00 5919                       /lib/x86_64-linux-gnu/libnss_nis-2.15.so
7fc285f21000-7fc285f38000 r-xp 00000000 fc:00 6429                       /lib/x86_64-linux-gnu/libnsl-2.15.so
7fc285f38000-7fc286137000 ---p 00017000 fc:00 6429                       /lib/x86_64-linux-gnu/libnsl-2.15.so
7fc286137000-7fc286138000 r--p 00016000 fc:00 6429                       /lib/x86_64-linux-gnu/libnsl-2.15.so
7fc286138000-7fc286139000 rw-p 00017000 fc:00 6429                       /lib/x86_64-linux-gnu/libnsl-2.15.so
7fc286139000-7fc28613b000 rw-p 00000000 00:00 0
7fc28613b000-7fc286143000 r-xp 00000000 fc:00 6433                       /lib/x86_64-linux-gnu/libnss_compat-2.15.so
7fc286143000-7fc286342000 ---p 00008000 fc:00 6433                       /lib/x86_64-linux-gnu/libnss_compat-2.15.so
7fc286342000-7fc286343000 r--p 00007000 fc:00 6433                       /lib/x86_64-linux-gnu/libnss_compat-2.15.so
7fc286343000-7fc286344000 rw-p 00008000 fc:00 6433                       /lib/x86_64-linux-gnu/libnss_compat-2.15.so
7fc286344000-7fc2867c2000 r--p 00000000 fc:00 531094                     /usr/lib/locale/locale-archive
7fc2867c2000-7fc286977000 r-xp 00000000 fc:00 6434                       /lib/x86_64-linux-gnu/libc-2.15.so
7fc286977000-7fc286b76000 ---p 001b5000 fc:00 6434                       /lib/x86_64-linux-gnu/libc-2.15.so
7fc286b76000-7fc286b7a000 r--p 001b4000 fc:00 6434                       /lib/x86_64-linux-gnu/libc-2.15.so
7fc286b7a000-7fc286b7c000 rw-p 001b8000 fc:00 6434                       /lib/x86_64-linux-gnu/libc-2.15.so
7fc286b7c000-7fc286b81000 rw-p 00000000 00:00 0
7fc286b81000-7fc286b83000 r-xp 00000000 fc:00 6432                       /lib/x86_64-linux-gnu/libdl-2.15.so
7fc286b83000-7fc286d83000 ---p 00002000 fc:00 6432                       /lib/x86_64-linux-gnu/libdl-2.15.so
7fc286d83000-7fc286d84000 r--p 00002000 fc:00 6432                       /lib/x86_64-linux-gnu/libdl-2.15.so
7fc286d84000-7fc286d85000 rw-p 00003000 fc:00 6432                       /lib/x86_64-linux-gnu/libdl-2.15.so
7fc286d85000-7fc286da9000 r-xp 00000000 fc:00 340                        /lib/x86_64-linux-gnu/libtinfo.so.5.9
7fc286da9000-7fc286fa8000 ---p 00024000 fc:00 340                        /lib/x86_64-linux-gnu/libtinfo.so.5.9
7fc286fa8000-7fc286fac000 r--p 00023000 fc:00 340                        /lib/x86_64-linux-gnu/libtinfo.so.5.9
7fc286fac000-7fc286fad000 rw-p 00027000 fc:00 340                        /lib/x86_64-linux-gnu/libtinfo.so.5.9
7fc286fad000-7fc286fcf000 r-xp 00000000 fc:00 6422                       /lib/x86_64-linux-gnu/ld-2.15.so
7fc2871b3000-7fc2871c1000 r--p 00000000 fc:00 265459                     /usr/share/locale-langpack/de/LC_MESSAGES/bash.mo
7fc2871c1000-7fc2871c4000 rw-p 00000000 00:00 0
7fc2871c6000-7fc2871cd000 r--s 00000000 fc:00 535727                     /usr/lib/x86_64-linux-gnu/gconv/gconv-modules.cache
7fc2871cd000-7fc2871cf000 rw-p 00000000 00:00 0
7fc2871cf000-7fc2871d0000 r--p 00022000 fc:00 6422                       /lib/x86_64-linux-gnu/ld-2.15.so
7fc2871d0000-7fc2871d2000 rw-p 00023000 fc:00 6422                       /lib/x86_64-linux-gnu/ld-2.15.so
7fff98beb000-7fff98c0c000 rw-p 00000000 00:00 0                          [stack]
7fff98d48000-7fff98d49000 r-xp 00000000 00:00 0                          [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]

The columns are:

• Address range of the block
• access permissions
• offset into the file, if block is a memory mapped file
• device number (of mapped file)
• inode (of mapped file)
• name of block or name of file (if mapped)

The tool pmap can display the same information in a more readable format. About identifying single blocks: "Details For The Hard Core Developer 4".

Tools

I've written a tool to read the maps of a java process and guess the role of the different blocks. The tools is committed here: javaJniMemUsage.pl. It runs intrusion less on a server with very limited prerequisites (only Perl and Linux).

javaJniMemUsage.pl [OPTIONS] PID|proc-maps-file
  OPTIONS
   -c - print output as CSV
   -h - print CSV header line before data line
  PID - process id of process to retrieve memory maps information.
  proc-maps-file - contains memory maps information. Can be directly /proc/PID/maps.

One can invoke the tool with a pid, in which case the tool will read /proc/PID/maps, or a file which contains a maps dump. Without any other parameters the tool will dump a human readable output.


Here is a sample output of a busy java application server:

7f2096bf9000 -      5066752 (   4M 852K), rw-p, 0,
7f20973b6000 -      5066752 (   4M 852K), rw-p, 0,
7f2097b73000 -      5066752 (   4M 852K), rw-p, 0,
7f2098330000 -      5066752 (   4M 852K), rw-p, 0,
7f2098aed000 -      5066752 (   4M 852K), rw-p, 0,
7f20bc2fc000 -      5066752 (   4M 852K), rw-p, 0,
7f20d8327000 -      5066752 (   4M 852K), rw-p, 0,
7f20f8327000 -      5066752 (   4M 852K), rw-p, 0,
7f21161fb000 -      2703360 (   2M 592K), rw-p, 0,
7f2116778000 -      2703360 (   2M 592K), rw-p, 0,
7f2116cf5000 -      2703360 (   2M 592K), rw-p, 0,
7f2117272000 -      2703360 (   2M 592K), rw-p, 0,
7f21177ef000 -      2703360 (   2M 592K), rw-p, 0,
7f2117d6c000 -      2703360 (   2M 592K), rw-p, 0,
7f211c551000 -      2703360 (   2M 592K), rw-p, 0,
7f211cce3000 -      2703360 (   2M 592K), rw-p, 0,
7f21205d6000 -         8192 (        8K), rw-p, 0,
7f21211ef000 -        12288 (       12K), ---p, 0,
7f21211f2000 -      2088960 (  1M 1016K), rw-p, 0, [stack:28219]
7f2121ed4000 -        16384 (       16K), rw-p, 0,
7f2122182000 -         4096 (        4K), rw-p, 0,
7f2122604000 -         8192 (        8K), rw-p, 0,
7f2122f6f000 -         8192 (        8K), rw-p, 0,
7f21236c6000 -        12288 (       12K), rw-p, 0,
7f2123b89000 -       151552 (      148K), rw-p, 0,
7f2128000000 -         4096 (        4K), r--p, 0,
7f212801f000 -      1540096 (   1M 480K), rw-p, 0,
7f2128d82000 -         4096 (        4K), ---p, 0,
7f2128d83000 -     10731520 (  10M 240K), rw-p, 0, [stack:28198]
7f212a058000 -         4096 (        4K), ---p, 0,
7f212a059000 -      1208320 (   1M 156K), rw-p, 0, [stack:28190]
7f212a180000 -       118784 (      116K), ---p, 0,
7f212a19d000 -       770048 (      752K), rw-p, 0,
7f212a259000 -      8003584 (   7M 648K), rw-p, 0,
7f212a9fb000 -        36864 (       36K), ---p, 0,
7f212aa04000 -       348160 (      340K), rw-p, 0,
7f212aa59000 -       159744 (      156K), rw-p, 0,
7f212aa80000 -       118784 (      116K), ---p, 0,
7f212aa9d000 -       770048 (      752K), rw-p, 0,
7f212ab59000 -      8003584 (   7M 648K), rw-p, 0,
7f212b2fb000 -        36864 (       36K), ---p, 0,
7f212b304000 -       348160 (      340K), rw-p, 0,
7f212b359000 -      3526656 (   3M 372K), rw-p, 0,
7f212b6b6000 -       667648 (      652K), ---p, 0,
7f212b759000 -         4096 (        4K), rw-p, 0,
7f212b75a000 -     17432576 (  16M 640K), rwxp, 0,
7f212c7fa000 -     32899072 (  31M 384K), rw-p, 0,
7f212f196000 -         8192 (        8K), rw-p, 0,
7f212ff6b000 -        86016 (       84K), rw-p, 0,
7f2130b39000 -       167936 (      164K), rw-p, 0,
7f2130ee7000 -        20480 (       20K), rw-p, 0,
7f213150c000 -        16384 (       16K), rw-p, 0,
7f2131747000 -       438272 (      428K), rw-p, 0,
7f21317b2000 -       512000 (      500K), rw-p, 0,
7f2131837000 -        12288 (       12K), ---p, 0,
7f213183a000 -      1060864 (    1M 12K), rw-p, 0, [stack:28189]
7f2131942000 -         4096 (        4K), rw-p, 0,
7f2131943000 -         4096 (        4K), r--p, 0,
7f2131944000 -         8192 (        8K), rw-p, 0,
7f2131948000 -         4096 (        4K), rw-p, 0,
7fff955d3000 -       135168 (      132K), rw-p, 0, [stack]
Java-Blocks =
       count=8
        addr=[660000000,664df0000,668650000,680000000,774220000,7755e0000,780000000,7eb830000]
         rss= 6G 108M 64K
         vsz= 6G 512M
sizeInMappedFiles =  142M 536K
sizeInSystemMappings =  8K
main-arena =  1G 528M 244K
stacks =
     1M
       count=8
         rss= 8M
         vsz= 8M 32K
  1016K
       count=72
         rss= 71M 448K
         vsz= 72M 288K
     8M
       count=179
         rss= 1G 408M
         vsz= 1G 408M 716K
libc arenas =
   128M
       count=18
        addr=[7f1f00000000,7f1f90000000,7f1fa8000000,7f1fb0000000,7f1fc8000000,7f1fd8000000,7f1fe0000000,7f1ff8000000,7f2000000000,7f2008000000,7f2010000000,7f2030000000,7f2048000000,7f2050000000,7f2058000000,7f2064000000,7f20dc000000,7f20fc000000]
         rss= 2G 192M 556K
         vsz= 2G 256M
    64M
       count=65
        addr=[7f1ef8000000,7f1f08000000,7f1f10000000,7f1f14000000,7f1f18000000,7f1f1c000000,7f1f20000000,7f1f28000000,7f1f2c000000,7f1f30000000,7f1f34000000,7f1f38000000,7f1f3c000000,7f1f40000000,7f1f44000000,7f1f48000000,7f1f4c000000,7f1f54000000,7f1f58000000,7f1f5c000000,7f1f60000000,7f1f64000000,7f1f6c000000,7f1f74000000,7f1f78000000,7f1f7c000000,7f1f80000000,7f1f84000000,7f1f88000000,7f1f8c000000,7f1f98000000,7f1f9c000000,7f1fa0000000,7f1fa4000000,7f1fb8000000,7f1fc0000000,7f1fd0000000,7f1fd4000000,7f1fe8000000,7f1ff0000000,7f1ff4000000,7f2018000000,7f201c000000,7f2020000000,7f2024000000,7f2028000000,7f202c000000,7f2038000000,7f203c000000,7f2040000000,7f2060000000,7f206c000000,7f2070000000,7f2084000000,7f20b8000000,7f20d4000000,7f20e4000000,7f20e8000000,7f20ec000000,7f20f4000000,7f2104000000,7f2108000000,7f2110000000,7f2118000000,7f2124000000]
         rss= 3G 861M 148K
         vsz= 4G 64M
unknown rss = 145M 616K, vsz =  146M 580K
sum rss = 15G 275M 28K, vsz = 16G 90M 356K

First it dumps a list of blocks it was not able to identify. (The format changes slightly. Instead of the end address, the size of the block is printed.) The size of this blocks is summed up at the bottom: "unknown rss". This should be a small number. After that, it dumps categories of blocks it did identify. Each category is grouped into paragraphs of same size. Each size paragraph contains the number of blocks found and the size sum occupied by those blocks. Size sum is always split into vsz (vss) and rss. vsz includes rss, this is why it will be always bigger. Some size paragraphs print also addresses of the identified blocks. They can be usually ignored. "sum rss" and "sum vsz" finally is the sum of all the blocks. They should be the same like reported by ps/top.

In the sample output before, we see that the 15GB rss are mainly used in this categories:

• Java takes 6GB, exactly as specified by java parameters (-Xmx6g).
• Thread stacks consume 1,5GB!
• And finally the native heaps consume 7,5GB split into 83 heaps and one main arena/heap.

Details For The Hard Core Developer

1. Rss includes the size of shared libraries mapped into memory. While this really uses physical memory, this memory is shared between processes using the same shared library. So if one process loades a 5MB shared library, rss for this process will be 5MB + the process ofwn stuff. If 10 processes load the same 5MB shared library, the rss for each process will be 5MB + the process stuff. But only 5MB of physical memory was really spent. So rss is not exactly physical memory size.
2. Even if the system grants "physical" memory to the process it does not waste the memory yet. Two processes could allocate each the size of the whole system memory (assumed there is enough swap space) without anything bad happening. The system splits the memory into pages. And only if a process starts to access the memory, the page where the access is inside is considered "dirty" and backed by physical memory.
3. This is necessary so libc can get a huge block from the system, without blocking memory which is not yet used. But why should we use libc and not just allocate memory by using mmap() instead? There are several reasons: 1. The memory returned by mmap() is aligned at page boundaries. The page size is usually 4kB. So if we allocate 10 bytes the rest of the page address space (4086 bytes) will be wasted. Since the system manages memory in pages this means real memory will be wasted. So we need libc to manage small memory blocks with smaller alignments. 2. There is a limited number of blocks which the system can return using mmap(). Since some processes use millions of memory blocks this would exhause this resource very quickly.
4. We can guess three types of memory blocks in Java programs. 1. the Java blocks, 2. libc heaps, 3. stacks. Java blocks are usually at the beginning of the list and are huge. Their size equals the specified block sizes (-Xmx, -XX:PermGenSpace). The size may be split into several blocks. Especially into two blocks where one has read/write access and the other no access permissions (this is the growing heap). libc heaps have a size of exactly 64MB (64*1024*1024MB) or a magnitude of that (128MB, 192MB, ...). Each heap block is also split in two blocks with different access permissions. If the heap is full, there is only one block. Stacks have also a noticeable size. They are usually a magnitude of exactly 1MB. 1MB and 8MB stacks have been those I've seen the most in Java programs. Stacks have something more special: stack blocks are always preceeded by a guarding block. The guarding block is the size of one page (4k) and has no access premissions. This is used to detect stack overflows. The guarding block preceeds the stack block because stacks grow from bigger addresses to smaller addresses. If the stack overflows, the code will access the address space of this block without access permissions.
5. Further deep detail reading: http://www.blackhat.com/presentations/bh-usa-07/Ferguson/Whitepaper/bh-usa-07-ferguson-WP.pdf

It’s not my code! I googled it.

Actually this blog post is not about Google. And it is even not about copying code. But it is indeed about code which I did not write. Since a couple days we use Sonar to check our code for coding style or conventions violations. Well this is not that new. We used to use Checkstyle, PMD, Findbugs already for a couple of years. But the switch to Sonar brought the heap of violations in our code up my mind again. Sonar says we have around 3000-5000 violations in our projects. Probably the most of them are eligible. But some of them are not:


Here you see some of the violations found in the Configuration class in the equals() method. Nearly each line has a violation. The problem is: equals() is a automatically generated method. Coding conventions violations in generated code are just useless. Generated code doesn’t has to be maintainable. It doesn’t has to be readable.

I thought about how to tell Sonar to ignore this code. One could use the //NOSONAR comment to make Sonar ignore lines. But you’d have to place it on every line. Or you could use

@SuppressWarnings("all")

but this would suppress all warnings, not only Sonar violations (reference).

Then I stumbled upon @Generated annotation which is part of Java since 1.6. Using this annotation, code generators could automatically mark generated code, making life easier for code analyzers and developers. So in a perfect world my Eclipse code generator would generate this method:

@Override
@Generated("Eclipse source generator")
public boolean equals(final Object obj) {
 if (this == obj) return true;
 if (obj == null) return false;
 if (getClass() != obj.getClass()) return false;
 final ConfigurationBase other = (ConfigurationBase) obj;
 if (autoRefreshDatabaseEnabled != other.autoRefreshDatabaseEnabled) return false;
 ....
}

and all code analyzers would magically ignore this method.

This idea was already picked up by the sonar team but sadly not yet implemented.