[infinispan-issues] [JBoss JIRA] (ISPN-1347) LIRS eviction not evicting correctly

[Jozef Vilkolak (Commented) (JIRA)]

    [ https://issues.jboss.org/browse/ISPN-1347?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12646796#comment-12646796 ] 

Jozef Vilkolak commented on ISPN-1347:
--------------------------------------

Two things that caught my eye when debugging my failing LIRS test : 

in LIRS
When adding a new entry when we need to evict the inStack method returns the wrong result since LIRSHashEntry gets instantiated pointing to self and not null like inStack expects

in Segment
shouldn't accessQueue be processed before every onEntryMiss?
a code snippet from the [BP-Wrapper document|http://www.cse.ohio-state.edu/hpcs/WWW/HTML/publications/abs09-1.html] to which I'm referring
{code:xml}
/* called upon a page miss */
void replacement_for_page_miss(Page *this_access) {
 Lock();
 for each page P in Queue[] {
  do what is specified by the replacement
   algorithm upon a hit on P;
 }
 do what is specified by the replacement
  algorithm upon a miss on ’this_access’;
 UnLock();
 Tail = 0;
}
{code}

                
> LIRS eviction not evicting correctly
> ------------------------------------
>
>                 Key: ISPN-1347
>                 URL: https://issues.jboss.org/browse/ISPN-1347
>             Project: Infinispan
>          Issue Type: Bug
>          Components: Eviction
>    Affects Versions: 5.0.0.FINAL
>            Reporter: Jozef Vilkolak
>            Assignee: Vladimir Blagojevic
>            Priority: Critical
>             Fix For: 5.0.2.FINAL, 5.1.0.BETA4, 5.1.0.FINAL
>
>         Attachments: 0088-Modified-LIRS-eviction-according-to-my-notes-on-Boun.patch, 0089-Changes-into-the-Segment-class-in-order-to-show-that.patch
>
>
> It seems LIRS eviction at this moment only evicts the first entry in the HIR queue and nothing else. I have written a test based on [this presentation|https://docs.google.com/viewer?a=v&q=cache:jcEF5qSkCo4J:www.ece.eng.wayne.edu/~sjiang/Projects/LIRS/sig02.ppt+lirs+algorithm&hl=cs&gl=cz&pid=bl&srcid=ADGEESjKS6wTMJZZEGG8I6G7pOh-Va1lkLS4-JIFK-86NPAi-uKGOy2hHcQA3xoHmDcek6j7jd5pEUuj_iLwU_oUN6dlFqRH9CN2YkHD46hBzFJ2UbHBPECnelAvbWZ4soE1c-7xdu-g&sig=AHIEtbRMUTRpEWGssf3i4CMDJvnnpJEdFA] located in the eviction-strategy module of [edg-functional-tests|https://svn.devel.redhat.com/repos/jboss-qa/edg/edg-functional-tests/trunk/] that is at the moment failing. 
> Upon closer examination I have found a couple of things I think may be the cause:
> * in infinispan.util.concurrent.BoundedConcurrentHashMap
> ** in execute() of the LIRS eviction if you have more items in the accessQueue and while processing you choose an item to be evicted it is added to the evicted Set. But if it is still in the accessQueue(and the operation was put) it gets proccesed but in the end still ends up evicted because it was not removed from the evicted set.
> ** in onEntryMiss of the LIRS eviction the very first if shouldn't first increment currentLIRSize because otherwise LIRSize is never full and therefore the LIRS algorithm never truly happens because execute() is never called that's why it only evicts from the HIR queue. It also causes the cache to be able to hold only maxEntries-1 entries. Also if (queue.size() < hirSizeLimit) condition is true the item should also be added to the stack in order to track its recency. And lastly I don't think onEntryMiss should be evicting elements because that way we can't track their recency. They will get eventually evicted by pruning.
> ** the function onEntryRemove should not in my opinion remove entries from the stack because otherwise there is no way to track recency of HIR-nonresident blocks. They will eventually get removed from the stack by pruning. It also seems this function gets called when clearing the cache instead of clear.
> * in Segment class 
> ** the remove operation makes entries behave as if they were just added as is already documented there with a TODO
> ** the get operation calls onEntryHit which can cause problems if get is used while servicing a put operation because it gets called twice
> If some of these things were design choices let me know so I will modify the test.

--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.jboss.org/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira