Clover coverage report -
Coverage timestamp: Thu Jul 5 2007 20:02:32 EDT
file stats: LOC: 532   Methods: 19
NCLOC: 349   Classes: 1
 
 Source file Conditionals Statements Methods TOTAL
BaseEvictionAlgorithm.java 56.8% 76.7% 89.5% 71.8%
coverage coverage
 1    /*
 2    * JBoss, the OpenSource J2EE webOS
 3    *
 4    * Distributable under LGPL license.
 5    * See terms of license at gnu.org.
 6    */
 7    package org.jboss.cache.eviction;
 8   
 9    import org.apache.commons.logging.Log;
 10    import org.apache.commons.logging.LogFactory;
 11    import org.jboss.cache.Fqn;
 12    import org.jboss.cache.Region;
 13    import org.jboss.cache.lock.TimeoutException;
 14   
 15    import java.util.concurrent.BlockingQueue;
 16    import java.util.concurrent.LinkedBlockingQueue;
 17    import java.util.concurrent.TimeUnit;
 18   
 19    /**
 20    * Abstract Event Processing Eviction Algorithm.
 21    * This class is used to implement basic event processing for Eviction Algorithms.
 22    * To extend this abstract class to make an Eviction Algorithm, implement the
 23    * abstract methods and a policy.
 24    *
 25    * @author Daniel Huang - dhuang@jboss.org 10/2005
 26    * @version $Revision: 1.23 $
 27    */
 28    public abstract class BaseEvictionAlgorithm implements EvictionAlgorithm
 29    {
 30    private static final Log log = LogFactory.getLog(BaseEvictionAlgorithm.class);
 31   
 32    /**
 33    * Mapped region.
 34    */
 35    protected Region region;
 36   
 37    /**
 38    * Contains Fqn instances.
 39    */
 40    protected BlockingQueue<Fqn> recycleQueue;
 41   
 42    /**
 43    * Contains NodeEntry instances.
 44    */
 45    protected EvictionQueue evictionQueue;
 46   
 47    /**
 48    * This method will create an EvictionQueue implementation and prepare it for use.
 49    *
 50    * @param region MarshRegion to setup an eviction queue for.
 51    * @return The created EvictionQueue to be used as the eviction queue for this algorithm.
 52    * @throws EvictionException
 53    * @see EvictionQueue
 54    */
 55    protected abstract EvictionQueue setupEvictionQueue(Region region) throws EvictionException;
 56   
 57    /**
 58    * This method will check whether the given node should be evicted or not.
 59    *
 60    * @param ne NodeEntry to test eviction for.
 61    * @return True if the given node should be evicted. False if the given node should not be evicted.
 62    */
 63    protected abstract boolean shouldEvictNode(NodeEntry ne);
 64   
 65  4205 protected BaseEvictionAlgorithm()
 66    {
 67  4205 recycleQueue = new LinkedBlockingQueue<Fqn>(500000);
 68    }
 69   
 70  273 protected void initialize(Region region) throws EvictionException
 71    {
 72  273 if (region == null)
 73  0 throw new IllegalArgumentException("region");
 74  273 this.region = region;
 75  273 evictionQueue = setupEvictionQueue(region);
 76  273 log.debug("initialized: " + this);
 77    }
 78   
 79    /**
 80    * Process the given region.
 81    * <p/>
 82    * Eviction Processing encompasses the following:
 83    * <p/>
 84    * - Add/Remove/Visit Nodes
 85    * - Prune according to Eviction Algorithm
 86    * - Empty/Retry the recycle queue of previously evicted but locked (during actual cache eviction) nodes.
 87    *
 88    * @param region Cache region to process for eviction.
 89    * @throws EvictionException
 90    */
 91  970 public void process(Region region) throws EvictionException
 92    {
 93  970 if (this.region == null)
 94    {
 95  273 this.initialize(region);
 96    }
 97   
 98  970 if (log.isTraceEnabled())
 99    {
 100  0 log.trace("process(): region: " + region.getFqn());
 101    }
 102   
 103  970 this.processQueues(region);
 104  970 this.emptyRecycleQueue();
 105  970 this.prune();
 106    }
 107   
 108  0 public void resetEvictionQueue(Region region)
 109    {
 110    }
 111   
 112    /**
 113    * Get the underlying EvictionQueue implementation.
 114    *
 115    * @return the EvictionQueue used by this algorithm
 116    * @see EvictionQueue
 117    */
 118  38290 public EvictionQueue getEvictionQueue()
 119    {
 120  38290 return this.evictionQueue;
 121    }
 122   
 123    /**
 124    * Event processing for Evict/Add/Visiting of nodes.
 125    * <p/>
 126    * - On AddEvents a new element is added into the eviction queue
 127    * - On RemoveEvents, the removed element is removed from the eviction queue.
 128    * - On VisitEvents, the visited node has its eviction statistics updated (idleTime, numberOfNodeVisists, etc..)
 129    *
 130    * @param region Cache region to process for eviction.
 131    * @throws EvictionException
 132    */
 133  881 protected void processQueues(Region region) throws EvictionException
 134    {
 135  881 EvictedEventNode node;
 136  881 int count = 0;
 137  ? while ((node = region.takeLastEventNode()) != null)
 138    {
 139  922928 Fqn fqn = node.getFqn();
 140   
 141  922928 count++;
 142  922928 switch (node.getEventType())
 143    {
 144  70585 case ADD_NODE_EVENT:
 145  70585 this.processAddedNodes(fqn,
 146    node.getElementDifference(),
 147    node.isResetElementCount());
 148  70585 break;
 149  11324 case REMOVE_NODE_EVENT:
 150  11324 this.processRemovedNodes(fqn);
 151  11324 break;
 152  624679 case VISIT_NODE_EVENT:
 153  624679 this.processVisitedNodes(fqn);
 154  624679 break;
 155  214574 case ADD_ELEMENT_EVENT:
 156  214574 this.processAddedElement(fqn);
 157  214574 break;
 158  1765 case REMOVE_ELEMENT_EVENT:
 159  1765 this.processRemovedElement(fqn);
 160  1765 break;
 161  1 case MARK_IN_USE_EVENT:
 162  1 this.processMarkInUseNodes(fqn, node.getInUseTimeout());
 163  1 break;
 164  0 case UNMARK_USE_EVENT:
 165  0 this.processUnmarkInUseNodes(fqn);
 166  0 break;
 167  0 default:
 168  0 throw new RuntimeException("Illegal Eviction Event type " + node.getEventType());
 169    }
 170    }
 171   
 172  881 if (log.isTraceEnabled())
 173    {
 174  0 log.trace("processed " + count + " node events in region: " + region.getFqn());
 175    }
 176   
 177    }
 178   
 179  48519 protected void evict(NodeEntry ne)
 180    {
 181    // NodeEntry ne = evictionQueue.getNodeEntry(fqn);
 182  48519 if (ne != null)
 183    {
 184  48519 evictionQueue.removeNodeEntry(ne);
 185  48519 if (!this.evictCacheNode(ne.getFqn()))
 186    {
 187  2 try
 188    {
 189  2 recycleQueue.put(ne.getFqn());
 190    }
 191    catch (InterruptedException e)
 192    {
 193  0 log.debug("InterruptedException", e);
 194    }
 195    }
 196    }
 197    }
 198   
 199    /**
 200    * Evict a node from cache.
 201    *
 202    * @param fqn node corresponds to this fqn
 203    * @return True if successful
 204    */
 205  96860 protected boolean evictCacheNode(Fqn fqn)
 206    {
 207  96860 if (log.isTraceEnabled())
 208    {
 209  0 log.trace("Attempting to evict cache node with fqn of " + fqn);
 210    }
 211   
 212  96860 EvictionPolicy policy = region.getEvictionPolicy();
 213  96860 try
 214    {
 215  96860 policy.evict(fqn);
 216    }
 217    catch (TimeoutException e)
 218    {
 219  0 log.warn("Eviction of " + fqn + " timed out, retrying later");
 220  0 log.debug(e, e);
 221  0 return false;
 222    }
 223    catch (Exception e)
 224    {
 225  3 log.error("Eviction of " + fqn + " failed", e);
 226  3 return false;
 227    }
 228   
 229  96857 if (log.isTraceEnabled())
 230    {
 231  0 log.trace("Eviction of cache node with fqn of " + fqn + " successful");
 232    }
 233   
 234  96857 return true;
 235    }
 236   
 237  1 protected void processMarkInUseNodes(Fqn fqn, long inUseTimeout) throws EvictionException
 238    {
 239  1 if (log.isTraceEnabled())
 240    {
 241  0 log.trace("Marking node " + fqn + " as in use with a usage timeout of " + inUseTimeout);
 242    }
 243   
 244  1 NodeEntry ne = evictionQueue.getNodeEntry(fqn);
 245  1 if (ne != null)
 246    {
 247  1 ne.setCurrentlyInUse(true, inUseTimeout);
 248    }
 249    }
 250   
 251  0 protected void processUnmarkInUseNodes(Fqn fqn) throws EvictionException
 252    {
 253  0 if (log.isTraceEnabled())
 254    {
 255  0 log.trace("Unmarking node " + fqn + " as in use");
 256    }
 257   
 258  0 NodeEntry ne = evictionQueue.getNodeEntry(fqn);
 259  0 if (ne != null)
 260    {
 261  0 ne.setCurrentlyInUse(false, 0);
 262    }
 263    }
 264   
 265  219469 protected void processAddedNodes(Fqn fqn, int numAddedElements, boolean resetElementCount) throws EvictionException
 266    {
 267  219469 if (log.isTraceEnabled())
 268    {
 269  0 log.trace("Adding node " + fqn + " with " + numAddedElements + " elements to eviction queue");
 270    }
 271   
 272  219469 NodeEntry ne = evictionQueue.getNodeEntry(fqn);
 273  219469 if (ne != null)
 274    {
 275  2605 ne.setModifiedTimeStamp(System.currentTimeMillis());
 276  2605 ne.setNumberOfNodeVisits(ne.getNumberOfNodeVisits() + 1);
 277  2605 if (resetElementCount)
 278    {
 279  0 ne.setNumberOfElements(numAddedElements);
 280    }
 281    else
 282    {
 283  2605 ne.setNumberOfElements(ne.getNumberOfElements() + numAddedElements);
 284    }
 285  2605 if (log.isTraceEnabled())
 286    {
 287  0 log.trace("Queue already contains " + ne.getFqn() + " processing it as visited");
 288    }
 289  2605 this.processVisitedNodes(ne.getFqn());
 290  2605 return;
 291    }
 292   
 293  216864 long stamp = System.currentTimeMillis();
 294  216864 ne = new NodeEntry(fqn);
 295  216864 ne.setModifiedTimeStamp(stamp);
 296  216864 ne.setNumberOfNodeVisits(1);
 297  216864 ne.setNumberOfElements(numAddedElements);
 298    // add it to the node map and eviction queue
 299    // if (evictionQueue.containsNodeEntry(ne))
 300    // {
 301    // if (log.isTraceEnabled())
 302    // {
 303    // log.trace("Queue already contains " + ne.getFqn() + " processing it as visited");
 304    // }
 305    // this.processVisitedNodes(ne.getFqn());
 306    // return;
 307    // }
 308   
 309  216864 evictionQueue.addNodeEntry(ne);
 310   
 311  216864 if (log.isTraceEnabled())
 312    {
 313  0 log.trace(ne.getFqn() + " added successfully to eviction queue");
 314    }
 315    }
 316   
 317    /**
 318    * Remove a node from cache.
 319    * <p/>
 320    * This method will remove the node from the eviction queue as well as
 321    * evict the node from cache.
 322    * <p/>
 323    * If a node cannot be removed from cache, this method will remove it from the eviction queue
 324    * and place the element into the recycleQueue. Each node in the recycle queue will get retried until
 325    * proper cache eviction has taken place.
 326    * <p/>
 327    * Because EvictionQueues are collections, when iterating them from an iterator, use iterator.remove()
 328    * to avoid ConcurrentModificationExceptions. Use the boolean parameter to indicate the calling context.
 329    *
 330    * @param fqn FQN of the removed node
 331    * @throws EvictionException
 332    */
 333  13329 protected void processRemovedNodes(Fqn fqn) throws EvictionException
 334    {
 335  13329 if (log.isTraceEnabled())
 336    {
 337  0 log.trace("Removing node " + fqn + " from eviction queue and attempting eviction");
 338    }
 339   
 340  13329 NodeEntry ne = evictionQueue.getNodeEntry(fqn);
 341  13329 if (ne != null)
 342    {
 343  12280 evictionQueue.removeNodeEntry(ne);
 344    }
 345    else
 346    {
 347  1049 if (log.isTraceEnabled())
 348    {
 349  0 log.trace("processRemoveNodes(): Can't find node associated with fqn: " + fqn
 350    + "Could have been evicted earlier. Will just continue.");
 351    }
 352  1049 return;
 353    }
 354   
 355  12280 if (log.isTraceEnabled())
 356    {
 357  0 log.trace(fqn + " removed from eviction queue");
 358    }
 359    }
 360   
 361    /**
 362    * Visit a node in cache.
 363    * <p/>
 364    * This method will update the numVisits and modifiedTimestamp properties of the Node.
 365    * These properties are used as statistics to determine eviction (LRU, LFU, MRU, etc..)
 366    * <p/>
 367    * *Note* that this method updates Node Entries by reference and does not put them back
 368    * into the queue. For some sorted collections, a remove, and a re-add is required to
 369    * maintain the sorted order of the elements.
 370    *
 371    * @param fqn FQN of the visited node.
 372    * @throws EvictionException
 373    */
 374  640434 protected void processVisitedNodes(Fqn fqn) throws EvictionException
 375    {
 376  640434 NodeEntry ne = evictionQueue.getNodeEntry(fqn);
 377  640434 if (ne == null)
 378    {
 379  4247 if (log.isDebugEnabled())
 380    {
 381  0 log.debug("Visiting node that was not added to eviction queues. Assuming that it has 1 element.");
 382    }
 383  4247 this.processAddedNodes(fqn, 1, false);
 384  4247 return;
 385    }
 386    // note this method will visit and modify the node statistics by reference!
 387    // if a collection is only guaranteed sort order by adding to the collection,
 388    // this implementation will not guarantee sort order.
 389  636187 ne.setNumberOfNodeVisits(ne.getNumberOfNodeVisits() + 1);
 390  636187 ne.setModifiedTimeStamp(System.currentTimeMillis());
 391    }
 392   
 393  1765 protected void processRemovedElement(Fqn fqn) throws EvictionException
 394    {
 395  1765 NodeEntry ne = evictionQueue.getNodeEntry(fqn);
 396   
 397  1765 if (ne == null)
 398    {
 399  1 if (log.isDebugEnabled())
 400    {
 401  0 log.debug("Removing element from " + fqn + " but eviction queue does not contain this node. " +
 402    "Ignoring removeElement event.");
 403    }
 404  1 return;
 405    }
 406   
 407  1764 ne.setNumberOfElements(ne.getNumberOfElements() - 1);
 408    // also treat it as a node visit.
 409  1764 ne.setNumberOfNodeVisits(ne.getNumberOfNodeVisits() + 1);
 410  1764 ne.setModifiedTimeStamp(System.currentTimeMillis());
 411    }
 412   
 413  250638 protected void processAddedElement(Fqn fqn) throws EvictionException
 414    {
 415  250638 NodeEntry ne = evictionQueue.getNodeEntry(fqn);
 416  250638 if (ne == null)
 417    {
 418  134582 if (log.isTraceEnabled())
 419    {
 420  0 log.trace("Adding element " + fqn + " for a node that doesn't exist yet. Process as an add.");
 421    }
 422  134582 this.processAddedNodes(fqn, 1, false);
 423  134582 return;
 424    }
 425   
 426  116056 ne.setNumberOfElements(ne.getNumberOfElements() + 1);
 427   
 428    // also treat it as a node visit.
 429  116056 ne.setNumberOfNodeVisits(ne.getNumberOfNodeVisits() + 1);
 430  116056 ne.setModifiedTimeStamp(System.currentTimeMillis());
 431    }
 432   
 433   
 434    /**
 435    * Empty the Recycle Queue.
 436    * <p/>
 437    * This method will go through the recycle queue and retry to evict the nodes from cache.
 438    *
 439    * @throws EvictionException
 440    */
 441  970 protected void emptyRecycleQueue() throws EvictionException
 442    {
 443  970 while (true)
 444    {
 445  970 Fqn fqn;
 446   
 447  970 try
 448    {
 449    //fqn = (Fqn) recycleQueue.take();
 450  970 fqn = recycleQueue.poll(0, TimeUnit.SECONDS);
 451    }
 452    catch (InterruptedException e)
 453    {
 454  0 log.debug(e, e);
 455  0 break;
 456    }
 457   
 458  970 if (fqn == null)
 459    {
 460  969 if (log.isTraceEnabled())
 461    {
 462  0 log.trace("Recycle queue is empty");
 463    }
 464  969 break;
 465    }
 466   
 467  1 if (log.isTraceEnabled())
 468    {
 469  0 log.trace("emptying recycle bin. Evict node " + fqn);
 470    }
 471   
 472    // Still doesn't work
 473  1 if (!evictCacheNode(fqn))
 474    {
 475  1 try
 476    {
 477  1 recycleQueue.put(fqn);
 478    }
 479    catch (InterruptedException e)
 480    {
 481  0 log.debug(e, e);
 482    }
 483  1 break;
 484    }
 485    }
 486    }
 487   
 488  48790 protected boolean isNodeInUseAndNotTimedOut(NodeEntry ne)
 489    {
 490  48790 if (ne.isCurrentlyInUse())
 491    {
 492  3 if (ne.getInUseTimeoutTimestamp() == 0)
 493    {
 494  3 return true;
 495    }
 496   
 497  0 if (System.currentTimeMillis() < ne.getInUseTimeoutTimestamp())
 498    {
 499  0 return true;
 500    }
 501    }
 502  48787 return false;
 503    }
 504   
 505  157 protected void prune() throws EvictionException
 506    {
 507  157 NodeEntry entry;
 508  ? while ((entry = evictionQueue.getFirstNodeEntry()) != null)
 509    {
 510  48578 if (this.shouldEvictNode(entry))
 511    {
 512  48519 this.evict(entry);
 513    }
 514    else
 515    {
 516  59 break;
 517    }
 518    }
 519    }
 520   
 521    /**
 522    * Returns debug information.
 523    */
 524  273 public String toString()
 525    {
 526  273 return super.toString() +
 527    " reqion=" + region.getFqn() +
 528    " recycle=" + recycleQueue.size() +
 529    " evict=" + evictionQueue.getNumberOfNodes();
 530    }
 531   
 532    }