4 Replies Latest reply on Nov 17, 2009 2:46 PM by brian.stansberry

    Bug: Endless-loop in EvictionTimer thread when using LFUAlgo

    pb00067
    pb00067 Nov 16, 2009 6:23 AM

      Hi all, I like to notice a bug in JBoss-Cache but I don't know where is the right place to do it. Anyone can help ?

      The bug consist in the fact that at a certain point BaseEvictionAlgorithm#prune method never exits his loop (see code below) anymore because of evictionQueue.getFirstNodeEntry() always returning the same value. Debugging the code we saw that the actual bug stays in method
      LFUQueue#removeNodeEntry:
      This method don't handles correctly the case non- existance of the node:
      if ne == null, then neither removalQueue nor the evictionList is touched.
      This causes evictionQueue.getFirstNodeEntry() returning always the same result.


      BaseEvictionAlgorithm.java
...
protected void prune() throws EvictionException
 {
 NodeEntry entry;
 while ((entry = evictionQueue.getFirstNodeEntry()) != null) --> ENDLESS-LOOP
 {
 if (this.shouldEvictNode(entry))
 {
 this.evict(entry);
 }
 else
 {
 break;
 }
 }
 }




      LFUQueue.java:
 public void removeNodeEntry(NodeEntry entry)
 {
 NodeEntry ne = nodeMap.remove(entry.getFqn());
 if (ne != null)
 {
 // don't remove directly from the LinkedList otherwise we will incur a O(n) = n
 // performance penalty for every removal! In the prune method for LFU, we will iterate the LinkedList through ONCE
 // doing a single O(n) = n operation and removal. This is much preferred over running O(n) = n every single time
 // remove is called. There is also special logic in the getFirstNodeEntry that will know to check
 // the removalQueue before returning.
 this.removalQueue.add(ne);
/* if(!evictionList.remove(ne)) {
 throw new RuntimeException("");
 } */
 this.numElements -= ne.getNumberOfElements();
 }
 }



      Solution: following Else-block added in method LFUQueue#removeNodeEntry resolves the problem. 

      else { // ELSE BLOCK: bugfix: this prevents endless loop in BaseEvictionAlgorithm#prune method
 if(!evictionList.remove(entry))
 throw new RuntimeException("");
 this.removalQueue.add(entry);
 this.numElements -= entry.getNumberOfElements();
 }




      Background:Im using JBoss-cache 3.2.1 GA as 2L-cache for a Hibernate application.
      As Hibernate does not suggest LRU as algorhythm for 2L-cache, I use the LRU.


      regards
      G.D.

      • 4970 Views
      • Tags: