[jbosscache-issues] [JBoss JIRA] Created: (JBCACHE-1557) EvictionTimer thread going into endless loop when using LFUAlgorithm

[Guenther Demetz (JIRA)]

EvictionTimer thread going into endless loop when using LFUAlgorithm
--------------------------------------------------------------------

                 Key: JBCACHE-1557
                 URL: https://jira.jboss.org/jira/browse/JBCACHE-1557
             Project: JBoss Cache
          Issue Type: Bug
      Security Level: Public (Everyone can see)
          Components: Eviction
    Affects Versions: 3.2.1.GA
         Environment: Hibernate3.3.2GA using JBOSSCACHE3.2.1GA as second level cache implementation
Database: SQLServer2008
            Reporter: Guenther Demetz
            Assignee: Manik Surtani


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

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


Code:

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





Code:

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.

Code:

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();
      }	

N.B.: In other parts of the code, i.e BaseEvictionAlgorithm: line 406 the non-existance of the node is properly handled, see following logging outputs:

13:55:11,712 DEBUG BaseEvictionAlgorithm:384 - Removing node /com/wuerth/phoenix/Cis/bc/persistent/jpa/ConcreteAccountPeer/assAccount/COLL/com.wuerth.phoenix.Cis.bc.persistent.jpa.ConcreteAccountPeer.assAccount#32770 from eviction queue and attempting eviction
13:55:11,712 DEBUG BaseEvictionAlgorithm:406 - processRemoveNodes(): Can't find node associated with fqn: /com/wuerth/phoenix/Cis/bc/persistent/jpa/ConcreteAccountPeer/assAccount/COLL/com.wuerth.phoenix.Cis.bc.persistent.jpa.ConcreteAccountPeer.assAccount#32770Could have been evicted earlier. Will just continue.
 
regards
G.D.

-- 
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators: https://jira.jboss.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see: http://www.atlassian.com/software/jira