OutOfMemory due to incorrect compareTo

Lesson learned from Defect

OutOfMemory due to incorrect implementation of compareTo

Recently, our application hit out of memory error. Through digging the heapdump generated, we quickly found the suspected class that may cause memory leak.

The class would put one item to TreeMap, and later remove it from the TreeMap when this item is finished.
We found that in the heapdump this TreeMap is huge, and this should not happen.

Add more logs to the class, and then we recreated this problem.
We found one strange thing, when after we put one item to TreeMap, later we remove it from the TreeMap, the treemap.remove(item.key) returns null, strange.

We wrote an example, which would put these items into the treemap, and then call contains(item.key), it returns false, en, very strange.
Then we debug the code, and found out that root cause.

See the code as below, have you seen the problem?
public class ClientID implements Serializable
public int compareTo(Object o)
{
   if (this == o)
    {
       return 0;
   }        
   if (o instanceof ClientID)
    {
       return (id - ((ClientID) o).id);
    }
   return -1;
}

In this code, it compares the two clients by subtracting their id(int).
But the id is a randomly-generated Hexadecimal int. If big negative number(a) subtracts another big negative number(b), a < b, it may overflow, and return a positive number.
So the compareTo method would return 1.

This would cause this item exists in the TreeMap, but TreeMap.contains/get can't find it.
The code should be changed like this:
public int compareTo(Object o)
{
   if (this == o)
    {
       return 0;
   }       
   if (o instanceof ClientID)
    {
           int thatClientId = ((ClientID) o).id;
           return (id == thatClientId) ? 0 : (id > thatClientId) ? 1 : -1;
    }
   return -1;
}

Except the fix above, we also change one TreeMap variable in the class to HashMap - as it doesn't need to be sorted by key, another TreeMap variable to TreeSet, as its key and value are same.

Lesson learned 1:
Ensure correct implementation of compareTo, equals, and hashcode.
In compareTo method, compare their value, not subtract them, this may cause overflow.
Be care of addition/subtraction and other operations of numbers, it may overflow.
Use correct data structure.

Lesson learned 2:
Recreate your problem.
Add more logs to help you recreate your problems.
Write example, prototype to verify your thoughts.
Think and list all possible reasons, order them by possibility, and the ease it can be tested and verified.
Then analyze one by one.
Post a Comment

Labels

Java (159) Lucene-Solr (110) Interview (61) All (58) J2SE (53) Algorithm (45) Soft Skills (36) Eclipse (34) Code Example (31) Linux (24) JavaScript (23) Spring (22) Windows (22) Web Development (20) Nutch2 (18) Tools (18) Bugs (17) Debug (16) Defects (14) Text Mining (14) J2EE (13) Network (13) Troubleshooting (12) PowerShell (11) Chrome (9) Design (9) How to (9) Learning code (9) Performance (9) UIMA (9) html (9) Http Client (8) Maven (8) Problem Solving (8) Security (8) bat (8) blogger (8) Big Data (7) Continuous Integration (7) Google (7) Guava (7) JSON (7) ANT (6) Coding Skills (6) Database (6) Scala (6) Shell (6) css (6) Algorithm Series (5) Cache (5) Dynamic Languages (5) IDE (5) Lesson Learned (5) Programmer Skills (5) Tips (5) adsense (5) xml (5) AIX (4) Code Quality (4) GAE (4) Git (4) Good Programming Practices (4) Jackson (4) Memory Usage (4) Miscs (4) OpenNLP (4) Project Managment (4) Spark (4) System Design (4) Testing (4) ads (4) regular-expression (4) Android (3) Apache Spark (3) Become a Better You (3) Concurrency (3) Eclipse RCP (3) English (3) Happy Hacking (3) IBM (3) J2SE Knowledge Series (3) JAX-RS (3) Jetty (3) Restful Web Service (3) Script (3) regex (3) seo (3) .Net (2) Android Studio (2) Apache (2) Apache Procrun (2) Architecture (2) Batch (2) Bit Operation (2) Build (2) Building Scalable Web Sites (2) C# (2) C/C++ (2) CSV (2) Career (2) Cassandra (2) Distributed (2) Fiddler (2) Firefox (2) Google Drive (2) Gson (2) How to Interview (2) Html Parser (2) Http (2) Image Tools (2) JQuery (2) Jersey (2) LDAP (2) Life (2) Logging (2) Python (2) Software Issues (2) Storage (2) Text Search (2) xml parser (2) AOP (1) Application Design (1) AspectJ (1) Chrome DevTools (1) Cloud (1) Codility (1) Data Mining (1) Data Structure (1) ExceptionUtils (1) Exif (1) Feature Request (1) FindBugs (1) Greasemonkey (1) HTML5 (1) Httpd (1) I18N (1) IBM Java Thread Dump Analyzer (1) JDK Source Code (1) JDK8 (1) JMX (1) Lazy Developer (1) Mac (1) Machine Learning (1) Mobile (1) My Plan for 2010 (1) Netbeans (1) Notes (1) Operating System (1) Perl (1) Problems (1) Product Architecture (1) Programming Life (1) Quality (1) Redhat (1) Redis (1) Review (1) RxJava (1) Solutions logs (1) Team Management (1) Thread Dump Analyzer (1) Visualization (1) boilerpipe (1) htm (1) ongoing (1) procrun (1) rss (1)

Popular Posts