001package org.apache.commons.jcs.engine.memory; 002 003/* 004 * Licensed to the Apache Software Foundation (ASF) under one 005 * or more contributor license agreements. See the NOTICE file 006 * distributed with this work for additional information 007 * regarding copyright ownership. The ASF licenses this file 008 * to you under the Apache License, Version 2.0 (the 009 * "License"); you may not use this file except in compliance 010 * with the License. You may obtain a copy of the License at 011 * 012 * http://www.apache.org/licenses/LICENSE-2.0 013 * 014 * Unless required by applicable law or agreed to in writing, 015 * software distributed under the License is distributed on an 016 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 017 * KIND, either express or implied. See the License for the 018 * specific language governing permissions and limitations 019 * under the License. 020 */ 021 022import java.io.IOException; 023import java.util.Iterator; 024import java.util.LinkedHashSet; 025import java.util.List; 026import java.util.Map; 027import java.util.Set; 028import java.util.concurrent.ConcurrentHashMap; 029import java.util.concurrent.ConcurrentMap; 030 031import org.apache.commons.jcs.engine.CacheConstants; 032import org.apache.commons.jcs.engine.behavior.ICacheElement; 033import org.apache.commons.jcs.engine.control.CompositeCache; 034import org.apache.commons.jcs.engine.control.group.GroupAttrName; 035import org.apache.commons.jcs.engine.memory.util.MemoryElementDescriptor; 036import org.apache.commons.jcs.engine.stats.StatElement; 037import org.apache.commons.jcs.engine.stats.behavior.IStatElement; 038import org.apache.commons.jcs.engine.stats.behavior.IStats; 039import org.apache.commons.jcs.utils.struct.DoubleLinkedList; 040import org.apache.commons.logging.Log; 041import org.apache.commons.logging.LogFactory; 042 043/** 044 * This class contains methods that are common to memory caches using the double linked list, such 045 * as the LRU, MRU, FIFO, and LIFO caches. 046 * <p> 047 * Children can control the expiration algorithm by controlling the update and get. The last item in the list will be the one 048 * removed when the list fills. For instance LRU should more items to the front as they are used. FIFO should simply add new items 049 * to the front of the list. 050 */ 051public abstract class AbstractDoubleLinkedListMemoryCache<K, V> extends AbstractMemoryCache<K, V> 052{ 053 /** The logger. */ 054 private static final Log log = LogFactory.getLog(AbstractDoubleLinkedListMemoryCache.class); 055 056 /** thread-safe double linked list for lru */ 057 protected DoubleLinkedList<MemoryElementDescriptor<K, V>> list; // TODO privatise 058 059 /** 060 * For post reflection creation initialization. 061 * <p> 062 * 063 * @param hub 064 */ 065 @Override 066 public void initialize(CompositeCache<K, V> hub) 067 { 068 super.initialize(hub); 069 list = new DoubleLinkedList<MemoryElementDescriptor<K, V>>(); 070 log.info("initialized MemoryCache for " + getCacheName()); 071 } 072 073 /** 074 * This is called by super initialize. 075 * 076 * NOTE: should return a thread safe map 077 * 078 * <p> 079 * 080 * @return new ConcurrentHashMap() 081 */ 082 @Override 083 public ConcurrentMap<K, MemoryElementDescriptor<K, V>> createMap() 084 { 085 return new ConcurrentHashMap<K, MemoryElementDescriptor<K, V>>(); 086 } 087 088 /** 089 * Calls the abstract method updateList. 090 * <p> 091 * If the max size is reached, an element will be put to disk. 092 * <p> 093 * 094 * @param ce 095 * The cache element, or entry wrapper 096 * @throws IOException 097 */ 098 @Override 099 public final void update(ICacheElement<K, V> ce) throws IOException 100 { 101 putCnt.incrementAndGet(); 102 103 lock.lock(); 104 try 105 { 106 MemoryElementDescriptor<K, V> newNode = adjustListForUpdate(ce); 107 108 // this should be synchronized if we were not using a ConcurrentHashMap 109 final K key = newNode.getCacheElement().getKey(); 110 MemoryElementDescriptor<K, V> oldNode = map.put(key, newNode); 111 112 // If the node was the same as an existing node, remove it. 113 if (oldNode != null && key.equals(oldNode.getCacheElement().getKey())) 114 { 115 list.remove(oldNode); 116 } 117 } 118 finally 119 { 120 lock.unlock(); 121 } 122 123 // If we are over the max spool some 124 spoolIfNeeded(); 125 } 126 127 /** 128 * Children implement this to control the cache expiration algorithm 129 * <p> 130 * 131 * @param ce 132 * @return MemoryElementDescriptor the new node 133 * @throws IOException 134 */ 135 protected abstract MemoryElementDescriptor<K, V> adjustListForUpdate(ICacheElement<K, V> ce) throws IOException; 136 137 /** 138 * If the max size has been reached, spool. 139 * <p> 140 * 141 * @throws Error 142 */ 143 private void spoolIfNeeded() throws Error 144 { 145 int size = map.size(); 146 // If the element limit is reached, we need to spool 147 148 if (size <= this.getCacheAttributes().getMaxObjects()) 149 { 150 return; 151 } 152 153 if (log.isDebugEnabled()) 154 { 155 log.debug("In memory limit reached, spooling"); 156 } 157 158 // Write the last 'chunkSize' items to disk. 159 int chunkSizeCorrected = Math.min(size, chunkSize); 160 161 if (log.isDebugEnabled()) 162 { 163 log.debug("About to spool to disk cache, map size: " + size + ", max objects: " 164 + this.getCacheAttributes().getMaxObjects() + ", maximum items to spool: " + chunkSizeCorrected); 165 } 166 167 // The spool will put them in a disk event queue, so there is no 168 // need to pre-queue the queuing. This would be a bit wasteful 169 // and wouldn't save much time in this synchronous call. 170 lock.lock(); 171 172 try 173 { 174 for (int i = 0; i < chunkSizeCorrected; i++) 175 { 176 ICacheElement<K, V> lastElement = spoolLastElement(); 177 if (lastElement == null) 178 { 179 break; 180 } 181 } 182 183 // If this is out of the sync block it can detect a mismatch 184 // where there is none. 185 if (log.isDebugEnabled() && map.size() != list.size()) 186 { 187 log.debug("update: After spool, size mismatch: map.size() = " + map.size() + ", linked list size = " + list.size()); 188 } 189 } 190 finally 191 { 192 lock.unlock(); 193 } 194 195 if (log.isDebugEnabled()) 196 { 197 log.debug("update: After spool map size: " + map.size() + " linked list size = " + list.size()); 198 } 199 } 200 201 /** 202 * Get an item from the cache If the item is found, it is removed from the list and added first. 203 * <p> 204 * 205 * @param key 206 * Identifies item to find 207 * @return ICacheElement<K, V> if found, else null 208 * @throws IOException 209 */ 210 @Override 211 public final ICacheElement<K, V> get(K key) throws IOException 212 { 213 ICacheElement<K, V> ce = null; 214 215 if (log.isDebugEnabled()) 216 { 217 log.debug(getCacheName() + ": getting item for key " + key); 218 } 219 220 MemoryElementDescriptor<K, V> me = map.get(key); 221 222 if (me != null) 223 { 224 hitCnt.incrementAndGet(); 225 226 lock.lock(); 227 try 228 { 229 ce = me.getCacheElement(); 230 // ABSTRACT 231 adjustListForGet(me); 232 } 233 finally 234 { 235 lock.unlock(); 236 } 237 238 if (log.isDebugEnabled()) 239 { 240 log.debug(getCacheName() + ": LRUMemoryCache hit for " + key); 241 } 242 } 243 else 244 { 245 missCnt.incrementAndGet(); 246 247 if (log.isDebugEnabled()) 248 { 249 log.debug(getCacheName() + ": LRUMemoryCache miss for " + key); 250 } 251 } 252 253 if (log.isDebugEnabled()) 254 { 255 verifyCache(); 256 } 257 258 return ce; 259 } 260 261 /** 262 * Adjust the list as needed for a get. This allows children to control the algorithm 263 * <p> 264 * 265 * @param me 266 */ 267 protected abstract void adjustListForGet(MemoryElementDescriptor<K, V> me); 268 269 /** 270 * This instructs the memory cache to remove the <i>numberToFree</i> according to its eviction 271 * policy. For example, the LRUMemoryCache will remove the <i>numberToFree</i> least recently 272 * used items. These will be spooled to disk if a disk auxiliary is available. 273 * <p> 274 * 275 * @param numberToFree 276 * @return the number that were removed. if you ask to free 5, but there are only 3, you will 277 * get 3. 278 * @throws IOException 279 */ 280 @Override 281 public int freeElements(int numberToFree) throws IOException 282 { 283 int freed = 0; 284 285 lock.lock(); 286 287 try 288 { 289 for (; freed < numberToFree; freed++) 290 { 291 ICacheElement<K, V> element = spoolLastElement(); 292 if (element == null) 293 { 294 break; 295 } 296 } 297 } 298 finally 299 { 300 lock.unlock(); 301 } 302 303 return freed; 304 } 305 306 /** 307 * This spools the last element in the LRU, if one exists. 308 * <p> 309 * 310 * @return ICacheElement<K, V> if there was a last element, else null. 311 * @throws Error 312 */ 313 private ICacheElement<K, V> spoolLastElement() throws Error 314 { 315 ICacheElement<K, V> toSpool = null; 316 317 final MemoryElementDescriptor<K, V> last = list.getLast(); 318 if (last != null) 319 { 320 toSpool = last.getCacheElement(); 321 if (toSpool != null) 322 { 323 getCompositeCache().spoolToDisk(toSpool); 324 if (map.remove(toSpool.getKey()) == null) 325 { 326 log.warn("update: remove failed for key: " + toSpool.getKey()); 327 328 if (log.isDebugEnabled()) 329 { 330 verifyCache(); 331 } 332 } 333 } 334 else 335 { 336 throw new Error("update: last.ce is null!"); 337 } 338 339 list.remove(last); 340 } 341 342 return toSpool; 343 } 344 345 /** 346 * Removes an item from the cache. This method handles hierarchical removal. If the key is a 347 * String and ends with the CacheConstants.NAME_COMPONENT_DELIMITER, then all items with keys 348 * starting with the argument String will be removed. 349 * <p> 350 * 351 * @param key 352 * @return true if the removal was successful 353 * @throws IOException 354 */ 355 @Override 356 public boolean remove(K key) throws IOException 357 { 358 if (log.isDebugEnabled()) 359 { 360 log.debug("removing item for key: " + key); 361 } 362 363 boolean removed = false; 364 365 // handle partial removal 366 if (key instanceof String && ((String) key).endsWith(CacheConstants.NAME_COMPONENT_DELIMITER)) 367 { 368 // remove all keys of the same name hierarchy. 369 for (Iterator<Map.Entry<K, MemoryElementDescriptor<K, V>>> itr = map.entrySet().iterator(); itr.hasNext();) 370 { 371 Map.Entry<K, MemoryElementDescriptor<K, V>> entry = itr.next(); 372 K k = entry.getKey(); 373 374 if (k instanceof String && ((String) k).startsWith(key.toString())) 375 { 376 lock.lock(); 377 try 378 { 379 list.remove(entry.getValue()); 380 itr.remove(); 381 removed = true; 382 } 383 finally 384 { 385 lock.unlock(); 386 } 387 } 388 } 389 } 390 else if (key instanceof GroupAttrName && ((GroupAttrName<?>) key).attrName == null) 391 { 392 // remove all keys of the same name hierarchy. 393 for (Iterator<Map.Entry<K, MemoryElementDescriptor<K, V>>> itr = map.entrySet().iterator(); itr.hasNext();) 394 { 395 Map.Entry<K, MemoryElementDescriptor<K, V>> entry = itr.next(); 396 K k = entry.getKey(); 397 398 if (k instanceof GroupAttrName && ((GroupAttrName<?>) k).groupId.equals(((GroupAttrName<?>) key).groupId)) 399 { 400 lock.lock(); 401 try 402 { 403 list.remove(entry.getValue()); 404 itr.remove(); 405 removed = true; 406 } 407 finally 408 { 409 lock.unlock(); 410 } 411 } 412 } 413 } 414 else 415 { 416 // remove single item. 417 lock.lock(); 418 try 419 { 420 MemoryElementDescriptor<K, V> me = map.remove(key); 421 if (me != null) 422 { 423 list.remove(me); 424 removed = true; 425 } 426 } 427 finally 428 { 429 lock.unlock(); 430 } 431 } 432 433 return removed; 434 } 435 436 /** 437 * Remove all of the elements from both the Map and the linked list implementation. Overrides 438 * base class. 439 * <p> 440 * 441 * @throws IOException 442 */ 443 @Override 444 public void removeAll() throws IOException 445 { 446 lock.lock(); 447 try 448 { 449 list.removeAll(); 450 map.clear(); 451 } 452 finally 453 { 454 lock.unlock(); 455 } 456 } 457 458 // --------------------------- internal methods (linked list implementation) 459 /** 460 * Adds a new node to the start of the link list. 461 * <p> 462 * 463 * @param ce 464 * The feature to be added to the First 465 * @return MemoryElementDescriptor 466 */ 467 protected MemoryElementDescriptor<K, V> addFirst(ICacheElement<K, V> ce) 468 { 469 lock.lock(); 470 try 471 { 472 MemoryElementDescriptor<K, V> me = new MemoryElementDescriptor<K, V>(ce); 473 list.addFirst(me); 474 if ( log.isDebugEnabled() ) 475 { 476 verifyCache(ce.getKey()); 477 } 478 return me; 479 } 480 finally 481 { 482 lock.unlock(); 483 } 484 } 485 486 /** 487 * Adds a new node to the end of the link list. 488 * <p> 489 * 490 * @param ce 491 * The feature to be added to the First 492 * @return MemoryElementDescriptor 493 */ 494 protected MemoryElementDescriptor<K, V> addLast(ICacheElement<K, V> ce) 495 { 496 lock.lock(); 497 try 498 { 499 MemoryElementDescriptor<K, V> me = new MemoryElementDescriptor<K, V>(ce); 500 list.addLast(me); 501 if ( log.isDebugEnabled() ) 502 { 503 verifyCache(ce.getKey()); 504 } 505 return me; 506 } 507 finally 508 { 509 lock.unlock(); 510 } 511 } 512 513 // ---------------------------------------------------------- debug methods 514 515 /** 516 * Dump the cache entries from first to list for debugging. 517 */ 518 @SuppressWarnings("unchecked") 519 // No generics for public fields 520 private void dumpCacheEntries() 521 { 522 log.debug("dumpingCacheEntries"); 523 for (MemoryElementDescriptor<K, V> me = list.getFirst(); me != null; me = (MemoryElementDescriptor<K, V>) me.next) 524 { 525 log.debug("dumpCacheEntries> key=" + me.getCacheElement().getKey() + ", val=" + me.getCacheElement().getVal()); 526 } 527 } 528 529 /** 530 * Checks to see if all the items that should be in the cache are. Checks consistency between 531 * List and map. 532 */ 533 @SuppressWarnings("unchecked") 534 // No generics for public fields 535 private void verifyCache() 536 { 537 boolean found = false; 538 log.debug("verifycache[" + getCacheName() + "]: mapContains " + map.size() + " elements, linked list contains " 539 + list.size() + " elements"); 540 log.debug("verifycache: checking linked list by key "); 541 for (MemoryElementDescriptor<K, V> li = list.getFirst(); li != null; li = (MemoryElementDescriptor<K, V>) li.next) 542 { 543 K key = li.getCacheElement().getKey(); 544 if (!map.containsKey(key)) 545 { 546 log.error("verifycache[" + getCacheName() + "]: map does not contain key : " + key); 547 log.error("key class=" + key.getClass()); 548 log.error("key hashcode=" + key.hashCode()); 549 log.error("key toString=" + key.toString()); 550 if (key instanceof GroupAttrName) 551 { 552 GroupAttrName<?> name = (GroupAttrName<?>) key; 553 log.error("GroupID hashcode=" + name.groupId.hashCode()); 554 log.error("GroupID.class=" + name.groupId.getClass()); 555 log.error("AttrName hashcode=" + name.attrName.hashCode()); 556 log.error("AttrName.class=" + name.attrName.getClass()); 557 } 558 dumpMap(); 559 } 560 else if (map.get(key) == null) 561 { 562 log.error("verifycache[" + getCacheName() + "]: linked list retrieval returned null for key: " + key); 563 } 564 } 565 566 log.debug("verifycache: checking linked list by value "); 567 for (MemoryElementDescriptor<K, V> li3 = list.getFirst(); li3 != null; li3 = (MemoryElementDescriptor<K, V>) li3.next) 568 { 569 if (map.containsValue(li3) == false) 570 { 571 log.error("verifycache[" + getCacheName() + "]: map does not contain value : " + li3); 572 dumpMap(); 573 } 574 } 575 576 log.debug("verifycache: checking via keysets!"); 577 for (Object val : map.keySet()) 578 { 579 found = false; 580 581 for (MemoryElementDescriptor<K, V> li2 = list.getFirst(); li2 != null; li2 = (MemoryElementDescriptor<K, V>) li2.next) 582 { 583 if (val.equals(li2.getCacheElement().getKey())) 584 { 585 found = true; 586 break; 587 } 588 } 589 if (!found) 590 { 591 log.error("verifycache[" + getCacheName() + "]: key not found in list : " + val); 592 dumpCacheEntries(); 593 if (map.containsKey(val)) 594 { 595 log.error("verifycache: map contains key"); 596 } 597 else 598 { 599 log.error("verifycache: map does NOT contain key, what the HECK!"); 600 } 601 } 602 } 603 } 604 605 /** 606 * Logs an error if an element that should be in the cache is not. 607 * <p> 608 * 609 * @param key 610 */ 611 @SuppressWarnings("unchecked") 612 // No generics for public fields 613 private void verifyCache(K key) 614 { 615 boolean found = false; 616 617 // go through the linked list looking for the key 618 for (MemoryElementDescriptor<K, V> li = list.getFirst(); li != null; li = (MemoryElementDescriptor<K, V>) li.next) 619 { 620 if (li.getCacheElement().getKey() == key) 621 { 622 found = true; 623 log.debug("verifycache(key) key match: " + key); 624 break; 625 } 626 } 627 if (!found) 628 { 629 log.error("verifycache(key)[" + getCacheName() + "], couldn't find key! : " + key); 630 } 631 } 632 633 /** 634 * Get an Array of the keys for all elements in the memory cache 635 * 636 * @return An Object[] 637 */ 638 @Override 639 public Set<K> getKeySet() 640 { 641 return new LinkedHashSet<K>(map.keySet()); 642 } 643 644 /** 645 * This returns semi-structured information on the memory cache, such as the size, put count, 646 * hit count, and miss count. 647 * <p> 648 * 649 * @see org.apache.commons.jcs.engine.memory.behavior.IMemoryCache#getStatistics() 650 */ 651 @Override 652 public IStats getStatistics() 653 { 654 IStats stats = super.getStatistics(); 655 stats.setTypeName( /* add algorithm name */"Memory Cache"); 656 657 List<IStatElement<?>> elems = stats.getStatElements(); 658 659 elems.add(new StatElement<Integer>("List Size", Integer.valueOf(list.size()))); 660 661 return stats; 662 } 663}