1 package org.apache.jcs.engine.memory.lru;
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 import java.io.IOException;
23 import java.io.Serializable;
24 import java.util.ArrayList;
25 import java.util.Iterator;
26 import java.util.Map;
27 import java.util.NoSuchElementException;
28
29 import org.apache.commons.logging.Log;
30 import org.apache.commons.logging.LogFactory;
31 import org.apache.jcs.engine.CacheConstants;
32 import org.apache.jcs.engine.CacheElement;
33 import org.apache.jcs.engine.behavior.ICacheElement;
34 import org.apache.jcs.engine.control.CompositeCache;
35 import org.apache.jcs.engine.control.group.GroupAttrName;
36 import org.apache.jcs.engine.control.group.GroupId;
37 import org.apache.jcs.engine.memory.AbstractMemoryCache;
38 import org.apache.jcs.engine.memory.util.MemoryElementDescriptor;
39 import org.apache.jcs.engine.stats.StatElement;
40 import org.apache.jcs.engine.stats.Stats;
41 import org.apache.jcs.engine.stats.behavior.IStatElement;
42 import org.apache.jcs.engine.stats.behavior.IStats;
43 import org.apache.jcs.utils.struct.DoubleLinkedList;
44
45 /***
46 * A fast reference management system. The least recently used items move to the end of the list and
47 * get spooled to disk if the cache hub is configured to use a disk cache. Most of the cache
48 * bottelnecks are in IO. There are no io bottlenecks here, it's all about processing power.
49 * <p>
50 * Even though there are only a few adjustments necessary to maintain the double linked list, we
51 * might want to find a more efficient memory manager for large cache regions.
52 * <p>
53 * The LRUMemoryCache is most efficient when the first element is selected. The smaller the region,
54 * the better the chance that this will be the case. < .04 ms per put, p3 866, 1/10 of that per get
55 * <p>
56 * @version $Id: LRUMemoryCache.java 536904 2007-05-10 16:03:42Z tv $
57 */
58 public class LRUMemoryCache
59 extends AbstractMemoryCache
60 {
61 /*** Don't change */
62 private static final long serialVersionUID = 6403738094136424201L;
63
64 /*** The logger. */
65 private final static Log log = LogFactory.getLog( LRUMemoryCache.class );
66
67 /*** thread-safe double linked list for lru */
68 private DoubleLinkedList list;
69
70 /*** number of hits */
71 private int hitCnt = 0;
72
73 /*** number of misses */
74 private int missCnt = 0;
75
76 /*** number of puts */
77 private int putCnt = 0;
78
79 /***
80 * For post reflection creation initialization.
81 * <p>
82 * @param hub
83 */
84 public synchronized void initialize( CompositeCache hub )
85 {
86 super.initialize( hub );
87 list = new DoubleLinkedList();
88 log.info( "initialized LRUMemoryCache for " + cacheName );
89 }
90
91 /***
92 * Puts an item to the cache. Removes any pre-existing entries of the same key from the linked
93 * list and adds this one first.
94 * <p>
95 * If the max size is reached, an element will be put to disk.
96 * <p>
97 * @param ce The cache element, or entry wrapper
98 * @exception IOException
99 */
100 public void update( ICacheElement ce )
101 throws IOException
102 {
103 putCnt++;
104
105
106
107 ce.getElementAttributes().setLastAccessTimeNow();
108 MemoryElementDescriptor old = null;
109 synchronized ( this )
110 {
111
112 addFirst( ce );
113
114 old = (MemoryElementDescriptor) map.put( ( (MemoryElementDescriptor) list.getFirst() ).ce.getKey(), list
115 .getFirst() );
116
117 if ( old != null && ( (MemoryElementDescriptor) list.getFirst() ).ce.getKey().equals( old.ce.getKey() ) )
118 {
119 list.remove( old );
120 }
121 }
122
123 int size = map.size();
124
125
126 if ( size < this.cattr.getMaxObjects() )
127 {
128 return;
129 }
130
131 if ( log.isDebugEnabled() )
132 {
133 log.debug( "In memory limit reached, spooling" );
134 }
135
136
137 int chunkSizeCorrected = Math.min( size, chunkSize );
138
139 if ( log.isDebugEnabled() )
140 {
141 log.debug( "About to spool to disk cache, map size: " + size + ", max objects: "
142 + this.cattr.getMaxObjects() + ", items to spool: " + chunkSizeCorrected );
143 }
144
145
146
147
148
149 for ( int i = 0; i < chunkSizeCorrected; i++ )
150 {
151 spoolLastElement();
152 }
153
154 if ( log.isDebugEnabled() )
155 {
156 log.debug( "update: After spool map size: " + map.size() + " linked list size = " + dumpCacheSize() );
157 }
158
159 }
160
161 /***
162 * This spools the last element in the LRU, if one exists.
163 * <p>
164 * @return ICacheElement if there was a last element, else null.
165 * @throws Error
166 */
167 protected ICacheElement spoolLastElement()
168 throws Error
169 {
170 ICacheElement toSpool = null;
171 synchronized ( this )
172 {
173 if ( list.getLast() != null )
174 {
175 toSpool = ( (MemoryElementDescriptor) list.getLast() ).ce;
176 if ( toSpool != null )
177 {
178 cache.spoolToDisk( ( (MemoryElementDescriptor) list.getLast() ).ce );
179 if ( !map.containsKey( ( (MemoryElementDescriptor) list.getLast() ).ce.getKey() ) )
180 {
181 log.error( "update: map does not contain key: "
182 + ( (MemoryElementDescriptor) list.getLast() ).ce.getKey() );
183 verifyCache();
184 }
185 if ( map.remove( ( (MemoryElementDescriptor) list.getLast() ).ce.getKey() ) == null )
186 {
187 log.warn( "update: remove failed for key: "
188 + ( (MemoryElementDescriptor) list.getLast() ).ce.getKey() );
189 verifyCache();
190 }
191 }
192 else
193 {
194 throw new Error( "update: last.ce is null!" );
195 }
196 list.removeLast();
197 }
198 else
199 {
200 verifyCache();
201 throw new Error( "update: last is null!" );
202 }
203
204
205
206 if ( map.size() != dumpCacheSize() )
207 {
208 log.warn( "update: After spool, size mismatch: map.size() = " + map.size() + ", linked list size = "
209 + dumpCacheSize() );
210 }
211 }
212 return toSpool;
213 }
214
215 /***
216 * This instructs the memory cache to remove the <i>numberToFree</i> according to its eviction
217 * policy. For example, the LRUMemoryCache will remove the <i>numberToFree</i> least recently
218 * used items. These will be spooled to disk if a disk auxiliary is available.
219 * <p>
220 * @param numberToFree
221 * @return the number that were removed. if you ask to free 5, but there are only 3, you will
222 * get 3.
223 * @throws IOException
224 */
225 public int freeElements( int numberToFree )
226 throws IOException
227 {
228 int freed = 0;
229 for ( ; freed < numberToFree; freed++ )
230 {
231 ICacheElement element = spoolLastElement();
232 if ( element == null )
233 {
234 break;
235 }
236 }
237 return freed;
238 }
239
240 /***
241 * Get an item from the cache without affecting its last access time or position.
242 * <p>
243 * @param key Identifies item to find
244 * @return Element matching key if found, or null
245 * @exception IOException
246 */
247 public ICacheElement getQuiet( Serializable key )
248 throws IOException
249 {
250 ICacheElement ce = null;
251
252 MemoryElementDescriptor me = (MemoryElementDescriptor) map.get( key );
253 if ( me != null )
254 {
255 if ( log.isDebugEnabled() )
256 {
257 log.debug( cacheName + ": LRUMemoryCache quiet hit for " + key );
258 }
259
260 ce = me.ce;
261 }
262 else if ( log.isDebugEnabled() )
263 {
264 log.debug( cacheName + ": LRUMemoryCache quiet miss for " + key );
265 }
266
267 return ce;
268 }
269
270 /***
271 * Get an item from the cache
272 * <p>
273 * @param key Identifies item to find
274 * @return ICacheElement if found, else null
275 * @exception IOException
276 */
277 public synchronized ICacheElement get( Serializable key )
278 throws IOException
279 {
280 ICacheElement ce = null;
281
282 if ( log.isDebugEnabled() )
283 {
284 log.debug( "getting item from cache " + cacheName + " for key " + key );
285 }
286
287 MemoryElementDescriptor me = (MemoryElementDescriptor) map.get( key );
288
289 if ( me != null )
290 {
291 hitCnt++;
292 if ( log.isDebugEnabled() )
293 {
294 log.debug( cacheName + ": LRUMemoryCache hit for " + key );
295 }
296
297 ce = me.ce;
298
299 ce.getElementAttributes().setLastAccessTimeNow();
300 list.makeFirst( me );
301 }
302 else
303 {
304 missCnt++;
305 if ( log.isDebugEnabled() )
306 {
307 log.debug( cacheName + ": LRUMemoryCache miss for " + key );
308 }
309 }
310
311 verifyCache();
312 return ce;
313 }
314
315 /***
316 * Removes an item from the cache. This method handles hierarchical removal. If the key is a
317 * String and ends with the CacheConstants.NAME_COMPONENT_DELIMITER, then all items with keys
318 * starting with the argument String will be removed.
319 * <p>
320 * @param key
321 * @return true if the removal was successful
322 * @exception IOException
323 */
324 public synchronized boolean remove( Serializable key )
325 throws IOException
326 {
327 if ( log.isDebugEnabled() )
328 {
329 log.debug( "removing item for key: " + key );
330 }
331
332 boolean removed = false;
333
334
335 if ( key instanceof String && ( (String) key ).endsWith( CacheConstants.NAME_COMPONENT_DELIMITER ) )
336 {
337
338 synchronized ( map )
339 {
340 for ( Iterator itr = map.entrySet().iterator(); itr.hasNext(); )
341 {
342 Map.Entry entry = (Map.Entry) itr.next();
343 Object k = entry.getKey();
344
345 if ( k instanceof String && ( (String) k ).startsWith( key.toString() ) )
346 {
347 list.remove( (MemoryElementDescriptor) entry.getValue() );
348
349 itr.remove();
350
351 removed = true;
352 }
353 }
354 }
355 }
356 else if ( key instanceof GroupId )
357 {
358
359 synchronized ( map )
360 {
361 for ( Iterator itr = map.entrySet().iterator(); itr.hasNext(); )
362 {
363 Map.Entry entry = (Map.Entry) itr.next();
364 Object k = entry.getKey();
365
366 if ( k instanceof GroupAttrName && ( (GroupAttrName) k ).groupId.equals( key ) )
367 {
368 itr.remove();
369
370 list.remove( (MemoryElementDescriptor) entry.getValue() );
371
372 removed = true;
373 }
374 }
375 }
376 }
377 else
378 {
379
380 MemoryElementDescriptor me = (MemoryElementDescriptor) map.remove( key );
381
382 if ( me != null )
383 {
384 list.remove( me );
385 removed = true;
386 }
387 }
388
389 return removed;
390 }
391
392 /***
393 * Remove all of the elements from both the Map and the linked list implementation. Overrides
394 * base class.
395 * <p>
396 * @throws IOException
397 */
398 public synchronized void removeAll()
399 throws IOException
400 {
401 map.clear();
402 list.removeAll();
403 }
404
405
406 /***
407 * iteration aid
408 */
409 public class IteratorWrapper
410 implements Iterator
411 {
412
413
414 private final Iterator i;
415
416 private IteratorWrapper( Map m )
417 {
418 i = m.entrySet().iterator();
419 }
420
421 public boolean hasNext()
422 {
423 return i.hasNext();
424 }
425
426 public Object next()
427 {
428 return new MapEntryWrapper( (Map.Entry) i.next() );
429 }
430
431 public void remove()
432 {
433 i.remove();
434 }
435
436 public boolean equals( Object o )
437 {
438 return i.equals( o );
439 }
440
441 public int hashCode()
442 {
443 return i.hashCode();
444 }
445 }
446
447 /***
448 * @author Aaron Smuts
449 */
450 public class MapEntryWrapper
451 implements Map.Entry
452 {
453 private final Map.Entry e;
454
455 private MapEntryWrapper( Map.Entry e )
456 {
457 this.e = e;
458 }
459
460 public boolean equals( Object o )
461 {
462 return e.equals( o );
463 }
464
465 public Object getKey()
466 {
467 return e.getKey();
468 }
469
470 public Object getValue()
471 {
472 return ( (MemoryElementDescriptor) e.getValue() ).ce;
473 }
474
475 public int hashCode()
476 {
477 return e.hashCode();
478 }
479
480 public Object setValue( Object value )
481 {
482 throw new UnsupportedOperationException( "Use normal cache methods"
483 + " to alter the contents of the cache." );
484 }
485 }
486
487 /***
488 * Gets the iterator attribute of the LRUMemoryCache object
489 * <p>
490 * @return The iterator value
491 */
492 public Iterator getIterator()
493 {
494 return new IteratorWrapper( map );
495 }
496
497 /***
498 * Get an Array of the keys for all elements in the memory cache
499 * @return An Object[]
500 */
501 public Object[] getKeyArray()
502 {
503
504 synchronized ( this )
505 {
506
507 return map.keySet().toArray();
508 }
509 }
510
511
512 /***
513 * Adds a new node to the end of the link list. Currently not used.
514 * <p>
515 * @param ce The feature to be added to the Last
516 */
517 protected void addLast( CacheElement ce )
518 {
519 MemoryElementDescriptor me = new MemoryElementDescriptor( ce );
520 list.addLast( me );
521 verifyCache( ce.getKey() );
522 }
523
524 /***
525 * Adds a new node to the start of the link list.
526 * <p>
527 * @param ce The feature to be added to the First
528 */
529 private synchronized void addFirst( ICacheElement ce )
530 {
531
532 MemoryElementDescriptor me = new MemoryElementDescriptor( ce );
533 list.addFirst( me );
534 return;
535 }
536
537
538
539 /***
540 * Dump the cache map for debugging.
541 */
542 public void dumpMap()
543 {
544 log.debug( "dumpingMap" );
545 for ( Iterator itr = map.entrySet().iterator(); itr.hasNext(); )
546 {
547 Map.Entry e = (Map.Entry) itr.next();
548 MemoryElementDescriptor me = (MemoryElementDescriptor) e.getValue();
549 log.debug( "dumpMap> key=" + e.getKey() + ", val=" + me.ce.getVal() );
550 }
551 }
552
553 /***
554 * Dump the cache entries from first to list for debugging.
555 */
556 public void dumpCacheEntries()
557 {
558 log.debug( "dumpingCacheEntries" );
559 for ( MemoryElementDescriptor me = (MemoryElementDescriptor) list.getFirst(); me != null; me = (MemoryElementDescriptor) me.next )
560 {
561 log.debug( "dumpCacheEntries> key=" + me.ce.getKey() + ", val=" + me.ce.getVal() );
562 }
563 }
564
565 /***
566 * Returns the size of the list.
567 * <p>
568 * @return the number of items in the map.
569 */
570 private int dumpCacheSize()
571 {
572 return list.size();
573 }
574
575 /***
576 * Checks to see if all the items that should be in the cache are. Checks consistency between
577 * List and map.
578 */
579 private void verifyCache()
580 {
581 if ( !log.isDebugEnabled() )
582 {
583 return;
584 }
585
586 boolean found = false;
587 log.debug( "verifycache[" + cacheName + "]: mapContains " + map.size() + " elements, linked list contains "
588 + dumpCacheSize() + " elements" );
589 log.debug( "verifycache: checking linked list by key " );
590 for ( MemoryElementDescriptor li = (MemoryElementDescriptor) list.getFirst(); li != null; li = (MemoryElementDescriptor) li.next )
591 {
592 Object key = li.ce.getKey();
593 if ( !map.containsKey( key ) )
594 {
595 log.error( "verifycache[" + cacheName + "]: map does not contain key : " + li.ce.getKey() );
596 log.error( "li.hashcode=" + li.ce.getKey().hashCode() );
597 log.error( "key class=" + key.getClass() );
598 log.error( "key hashcode=" + key.hashCode() );
599 log.error( "key toString=" + key.toString() );
600 if ( key instanceof GroupAttrName )
601 {
602 GroupAttrName name = (GroupAttrName) key;
603 log.error( "GroupID hashcode=" + name.groupId.hashCode() );
604 log.error( "GroupID.class=" + name.groupId.getClass() );
605 log.error( "AttrName hashcode=" + name.attrName.hashCode() );
606 log.error( "AttrName.class=" + name.attrName.getClass() );
607 }
608 dumpMap();
609 }
610 else if ( map.get( li.ce.getKey() ) == null )
611 {
612 log.error( "verifycache[" + cacheName + "]: linked list retrieval returned null for key: "
613 + li.ce.getKey() );
614 }
615 }
616
617 log.debug( "verifycache: checking linked list by value " );
618 for ( MemoryElementDescriptor li3 = (MemoryElementDescriptor) list.getFirst(); li3 != null; li3 = (MemoryElementDescriptor) li3.next )
619 {
620 if ( map.containsValue( li3 ) == false )
621 {
622 log.error( "verifycache[" + cacheName + "]: map does not contain value : " + li3 );
623 dumpMap();
624 }
625 }
626
627 log.debug( "verifycache: checking via keysets!" );
628 for ( Iterator itr2 = map.keySet().iterator(); itr2.hasNext(); )
629 {
630 found = false;
631 Serializable val = null;
632 try
633 {
634 val = (Serializable) itr2.next();
635 }
636 catch ( NoSuchElementException nse )
637 {
638 log.error( "verifycache: no such element exception" );
639 }
640
641 for ( MemoryElementDescriptor li2 = (MemoryElementDescriptor) list.getFirst(); li2 != null; li2 = (MemoryElementDescriptor) li2.next )
642 {
643 if ( val.equals( li2.ce.getKey() ) )
644 {
645 found = true;
646 break;
647 }
648 }
649 if ( !found )
650 {
651 log.error( "verifycache[" + cacheName + "]: key not found in list : " + val );
652 dumpCacheEntries();
653 if ( map.containsKey( val ) )
654 {
655 log.error( "verifycache: map contains key" );
656 }
657 else
658 {
659 log.error( "verifycache: map does NOT contain key, what the HECK!" );
660 }
661 }
662 }
663 }
664
665 /***
666 * Logs an error if an element that should be in the cache is not.
667 * <p>
668 * @param key
669 */
670 private void verifyCache( Serializable key )
671 {
672 if ( !log.isDebugEnabled() )
673 {
674 return;
675 }
676
677 boolean found = false;
678
679
680 for ( MemoryElementDescriptor li = (MemoryElementDescriptor) list.getFirst(); li != null; li = (MemoryElementDescriptor) li.next )
681 {
682 if ( li.ce.getKey() == key )
683 {
684 found = true;
685 log.debug( "verifycache(key) key match: " + key );
686 break;
687 }
688 }
689 if ( !found )
690 {
691 log.error( "verifycache(key)[" + cacheName + "], couldn't find key! : " + key );
692 }
693 }
694
695 /***
696 * This returns semi-structured information on the memory cache, such as the size, put count,
697 * hit count, and miss count.
698 * <p>
699 * @see org.apache.jcs.engine.memory.MemoryCache#getStatistics()
700 */
701 public synchronized IStats getStatistics()
702 {
703 IStats stats = new Stats();
704 stats.setTypeName( "LRU Memory Cache" );
705
706 ArrayList elems = new ArrayList();
707
708 IStatElement se = null;
709
710 se = new StatElement();
711 se.setName( "List Size" );
712 se.setData( "" + list.size() );
713 elems.add( se );
714
715 se = new StatElement();
716 se.setName( "Map Size" );
717 se.setData( "" + map.size() );
718 elems.add( se );
719
720 se = new StatElement();
721 se.setName( "Put Count" );
722 se.setData( "" + putCnt );
723 elems.add( se );
724
725 se = new StatElement();
726 se.setName( "Hit Count" );
727 se.setData( "" + hitCnt );
728 elems.add( se );
729
730 se = new StatElement();
731 se.setName( "Miss Count" );
732 se.setData( "" + missCnt );
733 elems.add( se );
734
735
736 IStatElement[] ses = (IStatElement[]) elems.toArray( new StatElement[0] );
737 stats.setStatElements( ses );
738
739
740
741
742 return stats;
743 }
744 }