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

[Galder Zamarreno (JIRA)]

     [ https://jira.jboss.org/jira/browse/JBCACHE-1557?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Galder Zamarreno updated JBCACHE-1557:
--------------------------------------

    Workaround Description: Use LRU.
                Workaround: [Workaround Exists]


> 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