0001: /*
0002: * <copyright>
0003: *
0004: * Copyright 2002-2004 BBNT Solutions, LLC
0005: * under sponsorship of the Defense Advanced Research Projects
0006: * Agency (DARPA).
0007: *
0008: * You can redistribute this software and/or modify it under the
0009: * terms of the Cougaar Open Source License as published on the
0010: * Cougaar Open Source Website (www.cougaar.org).
0011: *
0012: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
0013: * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
0014: * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
0015: * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
0016: * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
0017: * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
0018: * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
0019: * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
0020: * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
0021: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
0022: * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
0023: *
0024: * </copyright>
0025: */
0026:
0027: package org.cougaar.core.wp.resolver;
0028:
0029: import java.util.ArrayList;
0030: import java.util.Collections;
0031: import java.util.HashMap;
0032: import java.util.Iterator;
0033: import java.util.LinkedHashMap;
0034: import java.util.List;
0035: import java.util.Map;
0036: import java.util.Set;
0037: import org.cougaar.bootstrap.SystemProperties;
0038: import org.cougaar.core.component.Component;
0039: import org.cougaar.core.component.ServiceBroker;
0040: import org.cougaar.core.component.ServiceProvider;
0041: import org.cougaar.core.component.ServiceRevokedListener;
0042: import org.cougaar.core.service.LoggingService;
0043: import org.cougaar.core.service.ThreadService;
0044: import org.cougaar.core.service.wp.AddressEntry;
0045: import org.cougaar.core.service.wp.Request;
0046: import org.cougaar.core.service.wp.Response;
0047: import org.cougaar.core.thread.Schedulable;
0048: import org.cougaar.core.util.UID;
0049: import org.cougaar.core.wp.Parameters;
0050: import org.cougaar.core.wp.Timestamp;
0051: import org.cougaar.core.wp.bootstrap.Bundle;
0052: import org.cougaar.core.wp.bootstrap.HintService;
0053: import org.cougaar.util.GenericStateModelAdapter;
0054: import org.cougaar.util.UnaryPredicate;
0055:
0056: /**
0057: * This component is the white pages client-side cache.
0058: * <p>
0059: * Features:
0060: * <ul>
0061: * <li>Holds "get", "getAll", and "list" results</li>
0062: * <li>Allows the client to add bootstrapped cache "hints"</li>
0063: * <li>Holds both positive and negative results</li>
0064: * <li>Evicts expired and least-recently-used entries</li>
0065: * <li>Renews (in the background) recently-used entries that
0066: * will soon expire</li>
0067: * <li>Allows the client to flush and force-renewal entries
0068: * that are known to be stale</li>
0069: * <li>Upgrades "get" requests to "getAll" requests, to reduce
0070: * server traffic</li>
0071: * </ul>
0072: * <p>
0073: * The cache doesn't manage "bind/unbind" leases; that's the job of
0074: * the LeaseManager.
0075: */
0076: public class CacheManager extends GenericStateModelAdapter implements
0077: Component {
0078: // per-entry access history bits
0079: //
0080: // note that this bits are taken from the lower bits of the
0081: // "Entry.renewalTime", so no more than 10 bits (~1 second)
0082: // is recommended.
0083: private static final int DEFAULT_ACCESS_BITS = 8;
0084: private static final int ACCESS_BITS = SystemProperties.getInt(
0085: "org.cougaar.core.wp.resolver.accessBits",
0086: DEFAULT_ACCESS_BITS);
0087:
0088: // ratio of non-expired entries to evict if the cache is full
0089: // and doesn't contain expired entries
0090: private static final double EVICT_RATIO = (1.0 / 3.0);
0091:
0092: // RFE: timer-based prefetch
0093: //
0094: // use the ACCESS_BITS to check entries for late accesses
0095:
0096: private CacheConfig config;
0097:
0098: private ServiceBroker sb;
0099: private LoggingService logger;
0100: private ThreadService threadService;
0101:
0102: private LookupService lookupService;
0103:
0104: private final LookupService.Client myLookupClient = new LookupService.Client() {
0105: public void lookupAnswer(long baseTime, Map m) {
0106: CacheManager.this .lookupAnswer(baseTime, m);
0107: }
0108: };
0109:
0110: private CacheSP cacheSP;
0111: private HintSP hintSP;
0112:
0113: private final Object lock = new Object();
0114:
0115: // our cache
0116: //
0117: // this is a Map of Strings to Entry objects:
0118: // LRUMap<String, Entry>
0119: //
0120: // for keys starting with "." (list):
0121: // Entry data: Map<String, Set<String>>
0122: //
0123: // for keys starting with [a-zA-Z0-9] (get/getAll):
0124: // Entry data: Map<String, Map<String, AddressEntry>>
0125: //
0126: // note that pending requests are also placed in the cache,
0127: // as well as non-evictable hints, so the cache can't be
0128: // simply cleared to free up space.
0129: private LRUMap cache;
0130:
0131: //
0132: // clean the cache:
0133: //
0134:
0135: private Schedulable cleanCacheThread;
0136:
0137: //
0138: // timer-based prefetch
0139: //
0140:
0141: private Schedulable prefetchThread;
0142:
0143: public void setParameter(Object o) {
0144: configure(o);
0145: }
0146:
0147: public void setServiceBroker(ServiceBroker sb) {
0148: this .sb = sb;
0149: }
0150:
0151: public void setLoggingService(LoggingService logger) {
0152: this .logger = logger;
0153: }
0154:
0155: public void setThreadService(ThreadService threadService) {
0156: this .threadService = threadService;
0157: }
0158:
0159: private void configure(Object o) {
0160: if (config != null) {
0161: return;
0162: }
0163: config = new CacheConfig(o);
0164: }
0165:
0166: public void load() {
0167: super .load();
0168:
0169: configure(null);
0170:
0171: cache = new LRUMap(config.maxSize);
0172:
0173: // register for lookups
0174: lookupService = (LookupService) sb.getService(myLookupClient,
0175: LookupService.class, null);
0176: if (lookupService == null) {
0177: throw new RuntimeException("Unable to obtain LookupService");
0178: }
0179:
0180: // advertise our service
0181: cacheSP = new CacheSP();
0182: sb.addService(CacheService.class, cacheSP);
0183: hintSP = new HintSP();
0184: sb.addService(HintService.class, hintSP);
0185:
0186: if (0 < config.cleanPeriod) {
0187: // create expiration timer
0188: Runnable cleanCacheRunner = new Runnable() {
0189: public void run() {
0190: // assert (thread == cleanCacheThread);
0191: cleanCache();
0192: }
0193: };
0194: cleanCacheThread = threadService.getThread(this ,
0195: cleanCacheRunner,
0196: "White pages client cache cleaner");
0197: cleanCacheThread.schedule(config.cleanPeriod);
0198: }
0199:
0200: if (0 < config.prefetchPeriod) {
0201: // create prefetch timer
0202: Runnable prefetchRunner = new Runnable() {
0203: public void run() {
0204: // assert (thread == prefetchThread);
0205: prefetch();
0206: }
0207: };
0208: prefetchThread = threadService.getThread(this ,
0209: prefetchRunner, "White pages client prefetch");
0210: prefetchThread.schedule(config.prefetchPeriod);
0211: }
0212: }
0213:
0214: public void unload() {
0215: if (hintSP != null) {
0216: sb.revokeService(HintService.class, hintSP);
0217: hintSP = null;
0218: }
0219: if (cacheSP != null) {
0220: sb.revokeService(CacheService.class, cacheSP);
0221: cacheSP = null;
0222: }
0223: if (lookupService != null) {
0224: sb.releaseService(myLookupClient, LookupService.class,
0225: lookupService);
0226: lookupService = null;
0227: }
0228: if (threadService != null) {
0229: // halt our threads?
0230: sb.releaseService(this , ThreadService.class, threadService);
0231: threadService = null;
0232: }
0233: if (logger != null) {
0234: sb.releaseService(this , LoggingService.class, logger);
0235: logger = null;
0236: }
0237: super .unload();
0238: }
0239:
0240: private void setResult(Response res, Object result) {
0241: res.setResult(result);
0242: }
0243:
0244: //
0245: // look in the cache:
0246: //
0247:
0248: private void submit(Response res) {
0249: Request req = res.getRequest();
0250: boolean cacheOnly = req.hasOption(Request.CACHE_ONLY);
0251: if (req instanceof Request.Get) {
0252: Request.Get r = (Request.Get) req;
0253: String name = r.getName();
0254: String type = r.getType();
0255: get(res, name, type, cacheOnly);
0256: } else if (req instanceof Request.GetAll) {
0257: Request.GetAll r = (Request.GetAll) req;
0258: String name = r.getName();
0259: getAll(res, name, cacheOnly);
0260: } else if (req instanceof Request.List) {
0261: Request.List r = (Request.List) req;
0262: String suffix = r.getSuffix();
0263: list(res, suffix, cacheOnly);
0264: } else if (req instanceof Request.Flush) {
0265: Request.Flush r = (Request.Flush) req;
0266: String name = r.getName();
0267: long minAge = r.getMinimumAge();
0268: AddressEntry ae = r.getAddressEntry();
0269: boolean uncache = r.isUncache();
0270: boolean prefetch = r.isPrefetch();
0271: flush(res, name, minAge, ae, uncache, prefetch);
0272: } else if (req instanceof Request.Bind) {
0273: Request.Bind r = (Request.Bind) req;
0274: AddressEntry ae = r.getAddressEntry();
0275: boolean overwrite = r.isOverWrite();
0276: if (cacheOnly) {
0277: hint(res, ae, overwrite);
0278: } else {
0279: boolean renewal = r.isRenewal();
0280: bind(ae, renewal);
0281: }
0282: } else if (req instanceof Request.Unbind) {
0283: Request.Unbind r = (Request.Unbind) req;
0284: AddressEntry ae = r.getAddressEntry();
0285: if (cacheOnly) {
0286: unhint(res, ae);
0287: } else {
0288: unbind(ae);
0289: }
0290: } else {
0291: throw new IllegalArgumentException("Unknown action");
0292: }
0293: }
0294:
0295: private void getAll(Response res, String name, boolean cacheOnly) {
0296: get(res, name, null, cacheOnly);
0297: }
0298:
0299: private void list(Response res, String suffix, boolean cacheOnly) {
0300: get(res, suffix, null, cacheOnly);
0301: }
0302:
0303: private void get(Response res, String name, String type,
0304: boolean cacheOnly) {
0305: boolean hasResult;
0306: UID uid;
0307: Object result;
0308: boolean mustSend;
0309: synchronized (lock) {
0310: Entry e = (Entry) cache.get(name);
0311: boolean isHint = false;
0312: long now = System.currentTimeMillis();
0313: Object hint;
0314: if (e == null) {
0315: // not cached
0316: hasResult = false;
0317: uid = null;
0318: result = null;
0319: e = newEntry(now, (cacheOnly ? null : res));
0320: cache.put(name, e);
0321: mustSend = true;
0322: } else if (!e.hasExpired(now)) {
0323: // valid data
0324: hasResult = true;
0325: uid = e.getUID();
0326: result = e.getData();
0327: mustSend = e.noteAccess(now);
0328: } else if ((hint = e.getHint(type)) != null) {
0329: // found hint
0330: hasResult = true;
0331: uid = null;
0332: result = hint;
0333: isHint = true;
0334: mustSend = false;
0335: } else {
0336: // expired, maybe already pending
0337: hasResult = false;
0338: uid = (e.hasData() ? e.getUID() : null);
0339: result = null;
0340: mustSend = e.noteExpired(now, (cacheOnly ? null : res));
0341: }
0342:
0343: if (logger.isDetailEnabled()) {
0344: logger
0345: .detail("cache "
0346: + (hasResult ? ("HIT" + (mustSend ? (" (RENEW "
0347: + Timestamp.toString(e
0348: .getExpirationTime(),
0349: now) + ")")
0350: : (isHint ? " (HINT)" : "")))
0351: : ("MISS ("
0352: + (mustSend ? "SEND"
0353: : "PENDING") + ")"))
0354: + (cacheOnly ? " (CACHE_ONLY)" : "")
0355: + " for "
0356: + (name.charAt(0) == '.' ? ("list(suffix="
0357: + name + ")")
0358: : ("get"
0359: + (type == null ? "All"
0360: : "")
0361: + "(name="
0362: + name
0363: + (type == null ? ""
0364: : ", type="
0365: + type) + ")"))
0366: + (uid == null ? "" : " (uid=" + uid
0367: + ")"));
0368: }
0369: }
0370:
0371: if (hasResult || cacheOnly) {
0372:
0373: // cache hit
0374: setResult(res, result);
0375:
0376: }
0377:
0378: if (mustSend) {
0379: if (hasResult) {
0380: // this is a renewal, so it can be batched
0381: Map m = Collections.singletonMap(name, uid);
0382: lookupService.lookup(m);
0383: } else {
0384: // we should send this asap, but we can also include
0385: // any batched lookups
0386: Map m = Collections.singletonMap(name, uid);
0387: lookupService.lookup(m);
0388: }
0389: }
0390: }
0391:
0392: private void bind(AddressEntry ae, boolean renewal) {
0393: String name = ae.getName();
0394:
0395: // flush the cache entry if it conflicts with the
0396: // bind entry, to avoid local confusion
0397: synchronized (lock) {
0398: Entry e = (Entry) cache.get(name);
0399: boolean wasCached = false;
0400: boolean wasStale = false;
0401: long now = System.currentTimeMillis();
0402: if (e != null && !e.hasExpired(now)) {
0403: wasCached = true;
0404: Map m = (Map) e.getData();
0405: Object oldAE = (m == null ? (null) : m
0406: .get(ae.getType()));
0407: if (!ae.equals(oldAE)) {
0408: wasStale = true;
0409: if (e.flush(now)) {
0410: cache.remove(name);
0411: }
0412: }
0413: }
0414: if (logger.isDetailEnabled()) {
0415: logger.detail("bind"
0416: + ae
0417: + " "
0418: + (renewal ? "renewal " : "")
0419: + (wasCached ? ((wasStale ? "flushed"
0420: : "already matches")
0421: + " cache entry: " + e)
0422: : "was not cached"));
0423: }
0424: }
0425:
0426: // let the lease manager handle the batching
0427: }
0428:
0429: private void hint(Response res, AddressEntry ae, boolean overwrite) {
0430: String name = ae.getName();
0431: String type = ae.getType();
0432:
0433: boolean hasResult;
0434: Object result;
0435: List pendingGets = null;
0436: synchronized (lock) {
0437: Entry e = (Entry) cache.get(name);
0438: if (e == null) {
0439: // new hint
0440: Entry ewh = newEntryWithHints();
0441: cache.put(name, ewh);
0442: e = ewh;
0443: e.putHint(type, ae);
0444:
0445: if (logger.isInfoEnabled()) {
0446: logger.info("Added hint " + ae);
0447: }
0448: hasResult = false;
0449: result = null;
0450: } else {
0451: AddressEntry oldAE = (overwrite ? null : e
0452: .getHint(name));
0453: if (oldAE == null) {
0454: // new or replacement hint
0455: if (!e.hasHints()) {
0456: Entry ewh = newEntryWithHints(e);
0457: cache.put(name, ewh);
0458: e = ewh;
0459: }
0460: e.putHint(type, ae);
0461:
0462: if (logger.isInfoEnabled()) {
0463: logger.info("Added hint " + ae);
0464: }
0465: // find any pending "get" requests
0466: final String predType = type;
0467: UnaryPredicate pred = new UnaryPredicate() {
0468: public boolean execute(Object o) {
0469: if (!(o instanceof Response)) {
0470: return false;
0471: }
0472: Response pRes = (Response) o;
0473: Request pReq = pRes.getRequest();
0474: if (!(pReq instanceof Request.Get)) {
0475: return false;
0476: }
0477: Request.Get pGReq = (Request.Get) pReq;
0478: String pType = pGReq.getType();
0479: if (!predType.equals(pType)) {
0480: return false;
0481: }
0482: // our new hint can answer this request
0483: return true;
0484: }
0485: };
0486: pendingGets = e.takeMatchingResponses(pred);
0487: hasResult = false;
0488: result = null;
0489: } else {
0490: // conflicts
0491: hasResult = true;
0492: if (ae.equals(oldAE)) {
0493: // same as the current hint
0494: result = Boolean.TRUE;
0495: } else {
0496: // a conflicting hint is already in place
0497: result = oldAE;
0498: }
0499: }
0500: }
0501: }
0502:
0503: if (hasResult) {
0504: setResult(res, result);
0505: }
0506:
0507: // answer any pending requests that match this hint
0508: int nPendingGets = (pendingGets == null ? 0 : pendingGets
0509: .size());
0510: for (int i = 0; i < nPendingGets; i++) {
0511: Response pRes = (Response) pendingGets.get(i);
0512: if (logger.isInfoEnabled()) {
0513: logger.info("Setting result for get(" + name + ", "
0514: + type + ") to hint " + ae + " for request "
0515: + pRes);
0516: }
0517: setResult(pRes, ae);
0518: }
0519:
0520: // let the hint pass on to the bootstrappers,
0521: // since it stops at the lease manager
0522: }
0523:
0524: private void unhint(Response res, AddressEntry ae) {
0525: String name = ae.getName();
0526:
0527: boolean hasResult;
0528: Object result;
0529: synchronized (lock) {
0530: Entry e = (Entry) cache.get(name);
0531: if (e != null && e.hasHints()) {
0532: String type = ae.getType();
0533: AddressEntry oldAE = e.getHint(type);
0534: if (ae.equals(oldAE)) {
0535: if (!e.removeHint(type)) {
0536: // was hint-only, now nothing
0537: cache.remove(name);
0538: }
0539: hasResult = true;
0540: result = Boolean.TRUE;
0541: } else {
0542: hasResult = false;
0543: result = null;
0544: }
0545: } else {
0546: hasResult = false;
0547: result = null;
0548: }
0549: }
0550:
0551: if (hasResult) {
0552: setResult(res, result);
0553: if (logger.isInfoEnabled()) {
0554: logger.info("Removed hint " + ae);
0555: }
0556: }
0557: // let the hint pass on to the bootstrappers,
0558: // it stops at the lease manager
0559: }
0560:
0561: private void unbind(AddressEntry ae) {
0562: String name = ae.getName();
0563:
0564: // clear cache entry, just in case
0565: synchronized (lock) {
0566: Entry e = (Entry) cache.get(name);
0567: boolean wasCached = false;
0568: long now = System.currentTimeMillis();
0569: if (e != null && e.flush(now)) {
0570: wasCached = true;
0571: cache.remove(name);
0572: }
0573: if (logger.isDetailEnabled()) {
0574: logger.detail("unbind"
0575: + ae
0576: + " "
0577: + (wasCached ? ("flushed cache entry for "
0578: + name + ": " + e) : "was not cached"));
0579: }
0580: }
0581:
0582: // let the lease manager handle the batching
0583: }
0584:
0585: private void flush(Response res, String name, long minAge,
0586: AddressEntry ae, boolean uncache, boolean prefetch) {
0587:
0588: UID uid = null;
0589: Object result;
0590: boolean mustSend = false;
0591:
0592: synchronized (lock) {
0593: boolean wasCached = false;
0594: boolean isOldEnough = true;
0595:
0596: // find matching entry
0597: Entry e = (Entry) cache.get(name);
0598: long now = System.currentTimeMillis();
0599: if (e == null || e.hasExpired(now)) {
0600: // either no data or only hints
0601: isOldEnough = false;
0602: } else if (e.getDataAge(now) < minAge) {
0603: // not old enough yet
0604: } else {
0605: // valid old-enough data
0606: //
0607: // check to see if it matches the client's assertions,
0608: // to make this an atomic test/set
0609: if (ae == null) {
0610: // no assertions
0611: wasCached = true;
0612: } else {
0613: // match a single entry
0614: Map m = (Map) e.getData();
0615: String type = ae.getType();
0616: AddressEntry oldAE = (AddressEntry) m.get(type);
0617: wasCached = ae.equals(oldAE);
0618: }
0619: }
0620:
0621: if (wasCached) {
0622: // do the requested uncache/prefetch
0623: if (uncache) {
0624: if (e.flush(now)) {
0625: cache.remove(name);
0626: e = null;
0627: } else {
0628: }
0629: }
0630: if (prefetch) {
0631: if (e == null) {
0632: // let the "getAll" create it
0633: mustSend = true;
0634: } else {
0635: mustSend = e.renew(now);
0636: }
0637: uid = e.getUID();
0638: }
0639: }
0640:
0641: // the result is TRUE if we did something
0642: boolean b = (wasCached && (uncache || mustSend));
0643: result = Boolean.valueOf(b);
0644:
0645: if (logger.isDetailEnabled()) {
0646: logger
0647: .detail((uncache ? ("uncache" + (prefetch ? "+"
0648: : "")) : "")
0649: + (prefetch ? "prefetch" : "")
0650: + " "
0651: + name
0652: + " "
0653: + (wasCached ? ((0 < minAge ? "is over "
0654: + minAge + " millis old, "
0655: : "")
0656: + (ae == null ? ""
0657: : "matched the cache assertion "
0658: + ae + ", ")
0659: + (uncache ? "flushed entry data"
0660: : "") + (prefetch ? (mustSend ? "sending a new lookup"
0661: : "lookup already in progress")
0662: : ""))
0663: : ("is not " + (isOldEnough ? "over "
0664: + minAge
0665: + " millis old"
0666: : "in the cache"))));
0667: }
0668: }
0669:
0670: // this is a cache-only request
0671: setResult(res, result);
0672:
0673: if (mustSend) {
0674: // send a "getAll"
0675: // FIXME optimize, add delay, add UID support
0676: Map m = Collections.singletonMap(name, uid);
0677: lookupService.lookup(m);
0678: }
0679: }
0680:
0681: //
0682: // bootstrap entries into the cache:
0683: //
0684:
0685: private void add(String name, Bundle bundle) {
0686: long now = System.currentTimeMillis();
0687: UID uid = bundle.getUID();
0688: long ttd = bundle.getTTD();
0689: Object data = bundle.getEntries();
0690: if (data == null) {
0691: data = Collections.EMPTY_MAP;
0692: }
0693: Record r = new Record(uid, ttd, data);
0694: Map m = Collections.singletonMap(name, r);
0695: lookupAnswer(now, m, true);
0696: }
0697:
0698: private void remove(String name, Bundle bundle) {
0699: // TODO
0700: if (logger.isInfoEnabled()) {
0701: logger.info("Unsupported cache remove(" + name + ", "
0702: + bundle + ")" + ", just letting it time out...");
0703: }
0704: }
0705:
0706: //
0707: // callback for remote lookup answers:
0708: //
0709:
0710: private void lookupAnswer(long baseTime, Map m) {
0711: lookupAnswer(baseTime, m, false);
0712: }
0713:
0714: private void lookupAnswer(long baseTime, Map m, boolean create) {
0715: for (Iterator iter = m.entrySet().iterator(); iter.hasNext();) {
0716: Map.Entry me = (Map.Entry) iter.next();
0717: String name = (String) me.getKey();
0718: Object value = me.getValue();
0719: UID uid;
0720: long ttd;
0721: boolean hasData;
0722: Object data;
0723: if (value instanceof Record) {
0724: Record r = (Record) value;
0725: uid = r.getUID();
0726: ttd = r.getTTD();
0727: hasData = true;
0728: data = r.getData();
0729: } else if (value instanceof RecordIsValid) {
0730: RecordIsValid riv = (RecordIsValid) value;
0731: uid = riv.getUID();
0732: ttd = riv.getTTD();
0733: hasData = false;
0734: data = null;
0735: } else {
0736: throw new IllegalArgumentException(
0737: "Lookup callback map unexpected value: " + me);
0738: }
0739: gotAll(name, uid, baseTime, ttd, hasData, data, create);
0740: }
0741: }
0742:
0743: private void gotAll(String name, UID uid, long baseTime, long ttd,
0744: boolean hasData, Object data, boolean create) {
0745: List responses;
0746: synchronized (lock) {
0747: Entry e = (Entry) cache.get(name);
0748: if (create) {
0749: long now = System.currentTimeMillis();
0750: if (e == null) {
0751: e = newEntry(now, null);
0752: cache.put(name, e);
0753: }
0754: if (e.wasSent()) {
0755: if (uid != null && e.hasData()
0756: && e.getUID() != null
0757: && !uid.equals(e.getUID())) {
0758: if (logger.isInfoEnabled()) {
0759: logger.info("Avoiding \"UID mismatch\""
0760: + ", already sent " + name + "="
0761: + e.toString(now) + ", bootstrap "
0762: + name + "=(uid=" + uid + ", data="
0763: + data
0764: + "), overriding uid to null");
0765: }
0766: uid = null;
0767: }
0768: } else {
0769: e.setSendTime(now);
0770: }
0771: }
0772: if (e != null && e.wasSent()) {
0773: // set in cache, maybe force another lookup if !hasData
0774: responses = gotAll(e, name, uid, baseTime, ttd,
0775: hasData, data);
0776: // use the cached data instead of the passed data, since the
0777: // data will be null if !hasData.
0778: data = e.getData();
0779: } else {
0780: // we didn't as for this (!)
0781: //
0782: // The LookupService usually protects us against this, but
0783: // sometimes races can occur.
0784: responses = null;
0785: if (logger.isDebugEnabled()) {
0786: long now = System.currentTimeMillis();
0787: long ttl = baseTime + ttd;
0788: logger
0789: .debug("Ignoring a lookup result that we didn't send?"
0790: + " name="
0791: + name
0792: + " uid="
0793: + uid
0794: + " ttd="
0795: + ttd
0796: + " baseTime="
0797: + Timestamp.toString(baseTime, now)
0798: + " ttl="
0799: + Timestamp.toString(ttl, now)
0800: + " hasData="
0801: + hasData
0802: + " data="
0803: + (hasData ? data : null)
0804: + " entry=" + e);
0805: }
0806: }
0807: }
0808:
0809: int n = (responses == null ? 0 : responses.size());
0810: for (int i = 0; i < n; i++) {
0811: Response res = (Response) responses.get(i);
0812: setResult(res, data);
0813: }
0814: }
0815:
0816: private List gotAll(Entry e, String name, UID uid, long baseTime,
0817: long ttd, boolean hasData, Object data) {
0818:
0819: long now = System.currentTimeMillis();
0820:
0821: // clean up data
0822: if (hasData) {
0823: // this includes the full data
0824: if (data == null) {
0825: // this is a negative cache
0826: if (name.charAt(0) == '.') {
0827: data = Collections.EMPTY_SET;
0828: } else {
0829: data = Collections.EMPTY_MAP;
0830: }
0831: } else {
0832: // optionally check for immutable collection
0833: }
0834: if (e.hasHints()) {
0835: // merge in hints.
0836: //
0837: // this is necessary because a server might lack our hints,
0838: // so it could return null data and disable our hints.
0839: Map hints = e.getHints();
0840: Map mdata = (Map) data;
0841: boolean lacksHint = false;
0842: for (Iterator iter = hints.keySet().iterator(); iter
0843: .hasNext();) {
0844: Object key = iter.next();
0845: if (!mdata.containsKey(key)) {
0846: lacksHint = true;
0847: break;
0848: }
0849: }
0850: if (lacksHint) {
0851: Map m = new HashMap(hints);
0852: m.putAll(mdata);
0853: data = Collections.unmodifiableMap(m);
0854: if (logger.isDetailEnabled()) {
0855: logger.detail("merged " + name + " data "
0856: + mdata + " with our hints " + hints
0857: + " to create " + data);
0858: }
0859: // FIXME: if we alter our hints we should flush the data.
0860: }
0861: }
0862: } else {
0863: // this is a UID-based renewal
0864: //
0865: // make sure we still have the old data
0866: if (e.hasData() && (uid == null || uid.equals(e.getUID()))) {
0867: // the local data is up-to-date
0868: data = e.getData();
0869: } else {
0870: // we've cached the wrong data (?)
0871: //
0872: // send a new lookup
0873: // FIXME optimize, add delay, add UID support
0874: Map m = Collections.singletonMap(name, null);
0875: lookupService.lookup(m);
0876: return null;
0877: }
0878: }
0879:
0880: // take pending responses
0881: List responses = e.takeResponses();
0882:
0883: // set data
0884: e.setDataTime(now);
0885: e.setUID(uid);
0886: e.setData(data);
0887:
0888: // compute the ttl
0889: long ttl = baseTime + ttd;
0890: long maxTTL = now + config.maxTTD;
0891: if (maxTTL < ttl) {
0892: // reduce ttl if too long
0893: if (logger.isDebugEnabled()) {
0894: logger.debug("Reduce ttl from "
0895: + Timestamp.toString(ttl, now) + " to "
0896: + Timestamp.toString(maxTTL, now));
0897: }
0898: ttl = maxTTL;
0899: }
0900: long minTTL = now + config.minTTD;
0901: if (ttl < minTTL) {
0902: // increase ttl if it's too short
0903: if (logger.isDebugEnabled()) {
0904: logger.debug("Increasing ttl from "
0905: + Timestamp.toString(ttl, now) + " to "
0906: + Timestamp.toString(minTTL, now));
0907: }
0908: ttl = minTTL;
0909: }
0910:
0911: // set timestamps
0912: long expireTime = ttl;
0913: long timeLeft = expireTime - now;
0914: long sentTime = e.getSendTime();
0915: long rtt = now - sentTime;
0916: // FIXME
0917: long earlyBy = (rtt << 1);
0918: if ((timeLeft >> 1) < earlyBy) {
0919: // never more than half the lifetime
0920: earlyBy = timeLeft >> 1;
0921: } else if (earlyBy < (timeLeft >> 3)) {
0922: // never less than an eighth
0923: earlyBy = timeLeft >> 3;
0924: }
0925: long renewalTime = expireTime - earlyBy;
0926: if (renewalTime < now) {
0927: // never in the past!
0928: renewalTime = now;
0929: }
0930: e.setRenewalTime(renewalTime);
0931: e.setExpireTime(expireTime);
0932: // let the entry steal the lower bits
0933: renewalTime = e.getRenewalTime();
0934:
0935: if (logger.isDebugEnabled()) {
0936: boolean isList = (name.charAt(0) == '.');
0937: logger.debug("Caching "
0938: + (isList ? "list(suffix=" : "getAll(name=") + name
0939: + ", sent=" + Timestamp.toString(sentTime, now)
0940: + ", renew=" + Timestamp.toString(renewalTime, now)
0941: + ", expires="
0942: + Timestamp.toString(expireTime, now) + ", "
0943: + (isList ? "names=" : "entries=") + data + ")");
0944: }
0945:
0946: // return the pending responses
0947: return responses;
0948: }
0949:
0950: /**
0951: * This is old code that flushed the cache if a bind-ack
0952: * conflicted with the local cache.
0953: * <p>
0954: * This is dead code but we may revisit it in the future...
0955: * <p>
0956: * <pre>
0957: * bound(ae, ttl) == bound(ae, ae, ttl);
0958: * unbound(ae,ttl) == bound(ae, null, ttl);
0959: * </pre>
0960: * @param ae non-null if bind, otherwise should be oldAE
0961: */
0962: // private void bound(
0963: // AddressEntry oldAE,
0964: // AddressEntry ae,
0965: // long ttl) {
0966: // String name = oldAE.getName();
0967: // synchronized (lock) {
0968: // Entry e = (Entry) cache.get(name);
0969: // if (e == null) {
0970: // // no entry?
0971: // return;
0972: // }
0973: // long now = System.currentTimeMillis();
0974: // if (e.hasExpired(now)) {
0975: // // no data to patch
0976: // return;
0977: // }
0978: // if (e.canEvict(now, false)) {
0979: // // it's expired and no lookup is in progress
0980: // cache.remove(name);
0981: // return;
0982: // }
0983: // // patch the data
0984: // Map m = (Map) e.getData();
0985: // long oldTTL = e.getExpirationTime();
0986: // if (oldTTL < ttl) {
0987: // // keep the old ttl, swap in new data
0988: // //
0989: // // this may be a bit confusing, since the cache will contain
0990: // // a mix of server data and local bound overrides, but it's
0991: // // better than flushing the entry
0992: // Map newMap = new HashMap(m);
0993: // String type = oldAE.getType();
0994: // newMap.put(type, ae);
0995: // newMap = Collections.unmodifiableMap(newMap);
0996: // e.setData(newMap);
0997: // } else {
0998: // // unusual: the server has reduced the ttl!
0999: // //
1000: // // rather than patching the existing entry,
1001: // // we'll expire it immediately.
1002: // if (e.flush(now)) {
1003: // cache.remove(name);
1004: // }
1005: // }
1006: // }
1007: // }
1008: private void prefetch() {
1009: Map m = null;
1010: synchronized (lock) {
1011: // scan the cache, which is ordered from least-recently-used
1012: // to most-recently-used.
1013: //
1014: // renew entries that will expire soon.
1015: //
1016: // could optimize this by keeping a minTTL
1017: long now = System.currentTimeMillis();
1018: long nextTime = (now + config.prefetchPeriod);
1019: int n = cache.size();
1020: for (Iterator iter = cache.entrySet().iterator(); iter
1021: .hasNext();) {
1022: Map.Entry me = (Map.Entry) iter.next();
1023: Entry e = (Entry) me.getValue();
1024: if (!e.shouldPrefetch(nextTime, now)) {
1025: continue;
1026: }
1027: String name = (String) me.getKey();
1028: if (m == null) {
1029: m = new HashMap();
1030: }
1031: UID uid = (e.hasData() ? e.getUID() : null);
1032: if (logger.isDetailEnabled()) {
1033: if (m.isEmpty()) {
1034: logger.detail("prefetching cache[" + n + "] {");
1035: }
1036: logger
1037: .detail(" cache PREFETCH (RENEW "
1038: + Timestamp.toString(e
1039: .getExpirationTime(), now)
1040: + ") for "
1041: + (name.charAt(0) == '.' ? "list(suffix="
1042: : "getAll(name=")
1043: + name
1044: + ")"
1045: + (uid == null ? "" : " (uid="
1046: + uid + ")"));
1047: }
1048: m.put(name, uid);
1049: }
1050: if (m != null && logger.isDetailEnabled()) {
1051: logger.detail("}");
1052: logger.detail("prefetch " + m.size() + " of " + n
1053: + " entries");
1054: }
1055: }
1056:
1057: if (m != null) {
1058: lookupService.lookup(m);
1059: }
1060:
1061: // run me again later
1062: prefetchThread.schedule(config.prefetchPeriod);
1063: }
1064:
1065: // this is optional since the LRU will clean itself
1066: private void cleanCache() {
1067: synchronized (lock) {
1068: long now = System.currentTimeMillis();
1069:
1070: // remove expired entries
1071: removeExpiredEntries(now);
1072:
1073: // might as well debug our misses-table on the timer thread
1074: if (logger.isDebugEnabled()) {
1075: StringBuffer buf = new StringBuffer();
1076: buf
1077: .append("\n##### cache requests & hints ######################\n");
1078: boolean moreInfo = logger.isDetailEnabled();
1079: cacheToString(buf, moreInfo, moreInfo, now);
1080: buf
1081: .append("\n###################################################");
1082: String s = buf.toString();
1083: logger.debug(s);
1084: }
1085: }
1086:
1087: // run me again later
1088: cleanCacheThread.schedule(config.cleanPeriod);
1089: }
1090:
1091: private void cacheToString(StringBuffer buf, boolean showNormal,
1092: boolean showExpired, long now) {
1093: buf.append("Cache[").append(cache.size()).append("] {");
1094: int nNormal = 0;
1095: int nExpired = 0;
1096: for (Iterator iter = cache.entrySet().iterator(); iter
1097: .hasNext();) {
1098: Map.Entry me = (Map.Entry) iter.next();
1099: String name = (String) me.getKey();
1100: Entry e = (Entry) me.getValue();
1101: if (!showExpired && e.hasExpired(now)) {
1102: nExpired++;
1103: continue;
1104: }
1105: if (!showNormal && e.canEvict(now, false)) {
1106: nNormal++;
1107: continue;
1108: }
1109: buf.append("\n ").append(name).append(" --> ");
1110: buf.append(e.toString(now));
1111: }
1112: if (0 < nNormal) {
1113: buf.append("\n <skipping ").append(nNormal);
1114: buf.append(" normal (non-pending & non-hint) entries>");
1115: }
1116: if (0 < nExpired) {
1117: buf.append("\n <skipping ").append(nExpired);
1118: buf.append(" expired entries>");
1119: }
1120: buf.append("\n}");
1121: }
1122:
1123: private boolean evictLRU(Entry eldestE) {
1124: synchronized (cache) {
1125: if (cache.size() <= config.maxSize) {
1126: // still plenty of room
1127: return false;
1128: }
1129: long now = System.currentTimeMillis();
1130: // quick-check for an expired eldest
1131: if (eldestE != null && eldestE.canEvict(now, false)) {
1132: // remove the oldest entry
1133: if (logger.isDetailEnabled()) {
1134: logger.detail("evicting eldest: " + eldestE);
1135: }
1136: return true;
1137: }
1138: // remove expired entries
1139: if (removeExpiredEntries(now)) {
1140: // freed some expired entries
1141: //
1142: // must return false since we modified the map
1143: return false;
1144: }
1145: // okay, try removing non-expired entries
1146: if (evictEntries(now, EVICT_RATIO)) {
1147: // freed some non-expired entries
1148: //
1149: // must return false since we modified the map
1150: return false;
1151: }
1152: // oy, we can't remove any entries! This will be
1153: // slightly painful since every "put" may force
1154: // us to rescan the list. Hopefully this is rare
1155: // in practice.
1156: if (logger.isInfoEnabled()) {
1157: logger
1158: .info("Can't evict an entry from the cache["
1159: + cache.size()
1160: + "],"
1161: + " either due to pending requests or hints,"
1162: + " allowing the cache to exceed its maximum size "
1163: + config.maxSize);
1164: }
1165: return false;
1166: }
1167: }
1168:
1169: private boolean removeExpiredEntries(long now) {
1170: // scan the cache, which is ordered from least-recently-used
1171: // to most-recently-used.
1172: //
1173: // remove expired entries
1174: //
1175: // could optimize this by keeping a minTTL
1176: int n = cache.size();
1177: int nfreed = 0;
1178: for (Iterator iter = cache.entrySet().iterator(); iter
1179: .hasNext();) {
1180: Map.Entry me = (Map.Entry) iter.next();
1181: Entry e = (Entry) me.getValue();
1182: if (!e.canEvict(now, false)) {
1183: continue;
1184: }
1185: if (logger.isDetailEnabled()) {
1186: if (nfreed == 0) {
1187: logger.detail("cleaning cache[" + n + "] {");
1188: }
1189: String name = (String) me.getKey();
1190: logger.detail(" expired " + name + "=" + e);
1191: }
1192: ++nfreed;
1193: iter.remove();
1194: }
1195: if (0 < nfreed && logger.isDetailEnabled()) {
1196: logger.detail("}");
1197: logger.detail("removed " + nfreed + " of " + n
1198: + " expired entries");
1199: }
1200: return (0 < nfreed);
1201: }
1202:
1203: private boolean evictEntries(long now, double percent) {
1204: // evict a percent of the cache, even if the entries haven't
1205: // expired yet
1206: int n = cache.size();
1207: int nfreed = 0;
1208: int enoughFreed = (int) (percent * n);
1209: for (Iterator iter = cache.entrySet().iterator(); iter
1210: .hasNext();) {
1211: Map.Entry me = (Map.Entry) iter.next();
1212: Entry e = (Entry) me.getValue();
1213: if (!e.canEvict(now, true)) {
1214: continue;
1215: }
1216: if (logger.isDebugEnabled()) {
1217: if (nfreed == 0) {
1218: logger.debug("Evicting LRU entries[" + n + "] {");
1219: }
1220: String name = (String) me.getKey();
1221: logger
1222: .debug(" Evicting non-expired " + name + "="
1223: + e);
1224: }
1225: ++nfreed;
1226: iter.remove();
1227: if (enoughFreed <= nfreed) {
1228: // that's enough for now...
1229: break;
1230: }
1231: }
1232: if (0 < nfreed && logger.isDebugEnabled()) {
1233: logger.debug("}");
1234: logger.debug("Evicted " + nfreed + " of " + n
1235: + " expired entries");
1236: }
1237: return (0 < nfreed);
1238: }
1239:
1240: /** config options */
1241: private static class CacheConfig {
1242: public final long cleanPeriod;
1243: public final long prefetchPeriod;
1244: public final long minTTD;
1245: public final long maxTTD;
1246: public final int minSize;
1247: public final int initSize;
1248: public final int maxSize;
1249:
1250: public CacheConfig(Object o) {
1251: Parameters p = new Parameters(o,
1252: "org.cougaar.core.wp.resolver.cache.");
1253: cleanPeriod = p.getLong("cleanPeriod", 10000);
1254: prefetchPeriod = p.getLong("prefetchPeriod", 10000);
1255: minTTD = p.getLong("minTTD", 5000);
1256: maxTTD = p.getLong("maxTTD", 600000);
1257: minSize = p.getInt("minSize", 16);
1258: initSize = p.getInt("initSize", minSize);
1259: maxSize = p.getInt("maxSize", 2048);
1260: if (maxSize <= 0 || maxSize < minSize) {
1261: throw new RuntimeException("Invalid cache size (min="
1262: + minSize + ", max=" + maxSize + ")");
1263: }
1264: }
1265: }
1266:
1267: private Entry newEntry(long now, Response res) {
1268: Entry e = new Entry();
1269: e.newLookup(now, res);
1270: return e;
1271: }
1272:
1273: private Entry newEntryWithHints() {
1274: EntryWithHints ewh = new EntryWithHints();
1275: return ewh;
1276: }
1277:
1278: private Entry newEntryWithHints(Entry e) {
1279: EntryWithHints ewh = new EntryWithHints(e);
1280: return ewh;
1281: }
1282:
1283: static class Entry {
1284:
1285: protected long dataTime;
1286: protected long renewalTime;
1287: protected long expireTime;
1288: protected UID uid;
1289: protected Object data;
1290: protected List responses;
1291:
1292: /**
1293: * Initialize an entry, which must be sent.
1294: */
1295: public void newLookup(long now, Response res) {
1296: // assert (0 < now);
1297: dataTime = -1;
1298: uid = null;
1299: data = null;
1300: expireTime = -1;
1301: setSendTime(now);
1302: responses = (res == null ? Collections.EMPTY_LIST
1303: : Collections.singletonList(res));
1304: }
1305:
1306: /**
1307: * The time that the data was cached, or negative if there's
1308: * no cached data.
1309: */
1310: public void setDataTime(long now) {
1311: // assert (0 < now);
1312: dataTime = now;
1313: }
1314:
1315: public long getDataAge(long now) {
1316: // assert (0 < now);
1317: // assert (0 < dataTime);
1318: // assert (dataTime <= now);
1319: return (now - dataTime);
1320: }
1321:
1322: public long getDataTime() {
1323: // assert (0 < dataTime);
1324: return dataTime;
1325: }
1326:
1327: /** Most clients should use "hasExpired(now)" */
1328: public boolean hasData() {
1329: return (0 < dataTime);
1330: }
1331:
1332: /**
1333: * The UID of the cached data, which may be null.
1334: */
1335: public void setUID(UID uid) {
1336: this .uid = uid;
1337: }
1338:
1339: public UID getUID() {
1340: // assert (hasData());
1341: return uid;
1342: }
1343:
1344: /**
1345: * The cached data, which may be null.
1346: */
1347: public void setData(Object data) {
1348: this .data = data;
1349: }
1350:
1351: public Object getData() {
1352: // assert (hasData());
1353: return data;
1354: }
1355:
1356: /**
1357: * The expiration time for the data, or negative if there's
1358: * no cached data.
1359: */
1360: public void setExpireTime(long expireTime) {
1361: // assert (0 < expireTime);
1362: this .expireTime = expireTime;
1363: }
1364:
1365: public long getExpirationTime() {
1366: return expireTime;
1367: }
1368:
1369: /** @return false if there is valid data */
1370: public boolean hasExpired(long now) {
1371: // if there's no data then the expireTime is negative,
1372: // which is equivalent to saying it's expired.
1373: return (expireTime < now);
1374: }
1375:
1376: /**
1377: * The time that a pending lookup was sent.
1378: * <p>
1379: * This is stored as a negative renewalTime, since an
1380: * entry is either active (positive renewal) or pending.
1381: */
1382: private void setSendTime(long now) {
1383: // assert (0 <= renewalTime);
1384: // assert (0 < now);
1385: renewalTime = -now;
1386: }
1387:
1388: public long getSendTime() {
1389: // assert (renewalTime < 0);
1390: return -renewalTime;
1391: }
1392:
1393: public boolean wasSent() {
1394: return (renewalTime < 0);
1395: }
1396:
1397: /**
1398: * If an entry has data, this is the time after which a
1399: * prefetch lookup should be sent (to keep the data current).
1400: */
1401: public void setRenewalTime(long renewalTime) {
1402: // assert (0 < renewalTime);
1403: this .renewalTime = maskTime(renewalTime);
1404: }
1405:
1406: public long getRenewalTime() {
1407: // assert (0 < renewalTime);
1408: return maskTime(renewalTime);
1409: }
1410:
1411: private boolean shouldRenew(long now) {
1412: // assert (0 < now);
1413: // assert (!wasSent());
1414: //
1415: // no need to mask, since this is a simple comparison
1416: return (renewalTime < now);
1417: }
1418:
1419: /** @return true if a lookup should be sent */
1420: public boolean renew(long now) {
1421: // assert (0 < now);
1422: if (wasSent()) {
1423: // lookup already in progress
1424: return false;
1425: }
1426: // force early renewal
1427: setRenewalTime(now);
1428: // this will queue the "getAll"
1429: return true;
1430: }
1431:
1432: /** @return true if a lookup should be sent */
1433: public boolean noteAccess(long now) {
1434: // assert (0 < now);
1435: // assert (!hasExpired(now));
1436: recordAccess(now);
1437:
1438: if (!shouldRenew(now)) {
1439: // it's too early to prefetch
1440: return false;
1441: }
1442: if (wasSent()) {
1443: // already sent
1444: return false;
1445: }
1446: // send now
1447: setSendTime(now);
1448: return true;
1449: }
1450:
1451: /** @return true if a lookup should be sent */
1452: public boolean shouldPrefetch(long nextTime, long now) {
1453: // assert (0 < now);
1454: // assert (now <= nextTime);
1455: if (!shouldRenew(nextTime)) {
1456: // too early
1457: return false;
1458: }
1459: if (wasSent()) {
1460: // already sent
1461: return false;
1462: }
1463: if (!hasData()) {
1464: // lost the data?
1465: return false;
1466: }
1467: long ttd = (expireTime - dataTime);
1468: long halfTime = dataTime + (ttd >> 1);
1469: if (!wasAccessedAfter(halfTime)) {
1470: // no recent access
1471: return false;
1472: }
1473: // send now
1474: setSendTime(now);
1475: return true;
1476: }
1477:
1478: /** @return true if a lookup should be sent */
1479: public boolean noteExpired(long now, Response res) {
1480: // assert (0 < now);
1481: // assert (hasExpired(now));
1482: // assert (res != null);
1483: if (!wasSent()) {
1484: // just expired, send now
1485: //
1486: // keep uid+data
1487: //
1488: // assert (0 < now);
1489: setSendTime(now);
1490: responses = (res == null ? Collections.EMPTY_LIST
1491: : Collections.singletonList(res));
1492: return true;
1493: }
1494: if (res != null) {
1495: // add this response to the list
1496: int n = (responses == null ? 0 : responses.size());
1497: if (n == 0) {
1498: responses = Collections.singletonList(res);
1499: } else {
1500: if (n == 1) {
1501: List l = new ArrayList();
1502: Object o1 = responses.get(0);
1503: l.add(o1);
1504: responses = l;
1505: }
1506: responses.add(res);
1507: }
1508: }
1509: return false;
1510: }
1511:
1512: public boolean hasHints() {
1513: return false;
1514: }
1515:
1516: public AddressEntry getHint(String type) {
1517: return null;
1518: }
1519:
1520: public Map getHints() {
1521: return null;
1522: }
1523:
1524: public void putHint(String type, AddressEntry ae) {
1525: throw new RuntimeException("Not an EntryWithHints!");
1526: }
1527:
1528: public boolean removeHint(String type) {
1529: throw new RuntimeException("Not an EntryWithHints!");
1530: }
1531:
1532: /** @return true if this entry can be deleted */
1533: public boolean canEvict(long now, boolean force) {
1534: // assert (0 < now);
1535: if (!force && !hasExpired(now)) {
1536: // hasn't expired yet
1537: return false;
1538: }
1539: if (wasSent()) {
1540: // lookup in progress
1541: //
1542: // we could clear the uid+data now, to free up space,
1543: // but this risks invalidating the uid-based lookup
1544: return false;
1545: }
1546: if (hasHints()) {
1547: // hints keep the entry alive
1548: return false;
1549: }
1550: // okay to evict
1551: return true;
1552: }
1553:
1554: /** @return true if this entry should be deleted */
1555: public boolean flush(long now) {
1556: if (wasSent()) {
1557: // force expiration if not already expired
1558: if (!hasExpired(now)) {
1559: setExpireTime(now);
1560: }
1561: // keep uid+data
1562: // lookup in progress
1563: return false;
1564: }
1565: if (hasHints()) {
1566: if (hasData()) {
1567: // discard data, but can't evict hints
1568: dataTime = -1;
1569: uid = null;
1570: data = null;
1571: expireTime = -1;
1572: renewalTime = 0;
1573: responses = null;
1574: } else {
1575: // just hints, leave as-is
1576: }
1577: return false;
1578: }
1579: // normal entry, can dispose
1580: return true;
1581: }
1582:
1583: public List takeResponses() {
1584: List l = responses;
1585: responses = null;
1586: return l;
1587: }
1588:
1589: public List takeMatchingResponses(UnaryPredicate pred) {
1590: List ret = null;
1591: List l = responses;
1592: int n = (l == null ? 0 : l.size());
1593: for (int i = 0; i < n; i++) {
1594: Object oi = l.get(i);
1595: if (!pred.execute(oi)) {
1596: continue;
1597: }
1598: if (1 < n) {
1599: // at least one response remains
1600: l.remove(i);
1601: } else {
1602: // back to only hints
1603: dataTime = -1;
1604: uid = null;
1605: data = null;
1606: expireTime = -1;
1607: renewalTime = 0;
1608: responses = null;
1609: }
1610: --i;
1611: --n;
1612: if (ret == null) {
1613: ret = new ArrayList(3);
1614: }
1615: ret.add(oi);
1616: }
1617: return ret;
1618: }
1619:
1620: //
1621: // Use a couple bits to record access points over the
1622: // lifetime of the entry.
1623: //
1624: // For example, use 4 bits to record if there's been an
1625: // access during:
1626: // - the first 25% of the entry's life
1627: // - the second quarter
1628: // - the third quarter
1629: // - the last quarter
1630: // This is an inexpensive debugging tool and can be used
1631: // by a timer thread to periodically renew entries (e.g.
1632: // if used in the third or last quarter, renew towards the
1633: // end).
1634: //
1635: // We'll steal the lower bits from the renewalTime, since that's
1636: // a rough estimate of when to force a renewal. Of course, we
1637: // could dedicate a boolean[] or a separate int/long field.
1638: //
1639:
1640: private long maskTime(long t) {
1641: if (0 < ACCESS_BITS) {
1642: return maskBits(t);
1643: } else {
1644: return t;
1645: }
1646: }
1647:
1648: private void recordAccess(long now) {
1649: if (0 < ACCESS_BITS) {
1650: int i = findAccessBit(now);
1651: renewalTime = markBit(renewalTime, i);
1652: }
1653: }
1654:
1655: public boolean wasAccessedAfter(long t) {
1656: // assert (0 < t);
1657: if (0 < ACCESS_BITS) {
1658: int i = findAccessBit(t);
1659: for (; i < ACCESS_BITS; i++) {
1660: if (getBit(renewalTime, i)) {
1661: return true;
1662: }
1663: }
1664: return false;
1665: } else {
1666: // assume an access?
1667: return true;
1668: }
1669: }
1670:
1671: private String printAccessHistory(long now) {
1672: if (0 < ACCESS_BITS) {
1673: int i = findAccessBit(now);
1674: return " usage=[" + printBits(renewalTime, i) + "]";
1675: } else {
1676: return "";
1677: }
1678: }
1679:
1680: private int findAccessBit(long now) {
1681: long age = getDataAge(now);
1682: long ttl = expireTime - dataTime;
1683: double percent = ((double) age / ttl);
1684: int i = findBit(percent);
1685: return i;
1686: }
1687:
1688: private int findBit(double percent) {
1689: return (int) (ACCESS_BITS * percent);
1690: }
1691:
1692: private long maskBits(long t) {
1693: return (t & ~((1 << ACCESS_BITS) - 1));
1694: }
1695:
1696: private long markBit(long t, int i) {
1697: return (t | (1 << i));
1698: }
1699:
1700: private boolean getBit(long t, int i) {
1701: return ((t & (1 << i)) != 0);
1702: }
1703:
1704: private String printBits(long t, int n) {
1705: // output looks like "101101 ", where
1706: // "1" means bit is on
1707: // "0" means bit is off
1708: // " " means index is greater than n
1709: StringBuffer buf = new StringBuffer(ACCESS_BITS);
1710: int i = 0;
1711: for (; i <= n; i++) {
1712: boolean b = getBit(t, i);
1713: buf.append(b ? "1" : "0");
1714: }
1715: for (; i < ACCESS_BITS; i++) {
1716: buf.append(" ");
1717: }
1718: return buf.toString();
1719: }
1720:
1721: public String toString() {
1722: long now = System.currentTimeMillis();
1723: return toString(now);
1724: }
1725:
1726: public String toString(long now) {
1727: // assert (0 < now);
1728: boolean hasData = hasData();
1729: boolean isExpired = hasExpired(now);
1730: boolean showTimestamps = (!isExpired || (hasData && !hasHints()));
1731: boolean wasSent = wasSent();
1732:
1733: StringBuffer buf = new StringBuffer();
1734: buf.append("(");
1735: if (showTimestamps) {
1736: buf.append("cached=");
1737: buf.append(Timestamp.toString(dataTime, now));
1738: if (!wasSent) {
1739: buf.append(" renew=");
1740: buf.append(Timestamp
1741: .toString(getRenewalTime(), now));
1742: }
1743: buf.append(" expire");
1744: buf.append(isExpired ? "d" : "s");
1745: buf.append("=");
1746: buf.append(Timestamp.toString(expireTime, now));
1747: if (!wasSent) {
1748: long t = (isExpired ? (expireTime - 1) : now);
1749: buf.append(printAccessHistory(t));
1750: }
1751: buf.append(" ");
1752: }
1753: if (wasSent) {
1754: long sendTime = getSendTime();
1755: buf.append("sent");
1756: buf.append("=");
1757: buf.append(Timestamp.toString(sendTime, now));
1758: List l = responses;
1759: if (l == null) {
1760: l = Collections.EMPTY_LIST;
1761: }
1762: buf.append(" responses[");
1763: buf.append(l.size());
1764: buf.append("]: ");
1765: buf.append(l);
1766: }
1767: if (hasData) {
1768: buf.append(" uid=");
1769: buf.append(uid);
1770: buf.append(" data=");
1771: buf.append(data);
1772: }
1773: if (hasHints()) {
1774: buf.append(" hints[");
1775: Map m = getHints();
1776: buf.append(m.size());
1777: buf.append("]: ");
1778: buf.append(m);
1779: }
1780: buf.append(")");
1781:
1782: return buf.toString();
1783: }
1784: }
1785:
1786: static class EntryWithHints extends Entry {
1787:
1788: private static final Map NO_HINTS = Collections.EMPTY_MAP;
1789:
1790: private Map hints = NO_HINTS;
1791:
1792: public EntryWithHints() {
1793: this .dataTime = -1;
1794: this .uid = null;
1795: this .data = null;
1796: this .expireTime = -1;
1797: this .renewalTime = 0;
1798: this .responses = null;
1799: }
1800:
1801: public EntryWithHints(Entry e) {
1802: this .dataTime = e.dataTime;
1803: this .uid = e.uid;
1804: this .data = e.data;
1805: this .expireTime = e.expireTime;
1806: this .renewalTime = e.renewalTime;
1807: this .responses = e.responses;
1808: }
1809:
1810: public boolean hasHints() {
1811: return hints != NO_HINTS;
1812: }
1813:
1814: public AddressEntry getHint(String type) {
1815: if (type == null || hints == NO_HINTS) {
1816: return null;
1817: }
1818: return (AddressEntry) hints.get(type);
1819: }
1820:
1821: public Map getHints() {
1822: return hints;
1823: }
1824:
1825: public void putHint(String type, AddressEntry ae) {
1826: if (hints == NO_HINTS) {
1827: hints = new HashMap();
1828: }
1829: hints.put(type, ae);
1830: }
1831:
1832: public boolean removeHint(String type) {
1833: if (hints == NO_HINTS) {
1834: return data == null;
1835: } else {
1836: hints.remove(type);
1837: if (hints.isEmpty()) {
1838: hints = NO_HINTS;
1839: return data == null;
1840: } else {
1841: return false;
1842: }
1843: }
1844: }
1845: }
1846:
1847: class LRUMap extends LinkedHashMap {
1848: public LRUMap(int initialSize) {
1849: super (initialSize, 0.75f, true);
1850: }
1851:
1852: protected boolean removeEldestEntry(Map.Entry eldest) {
1853: Entry eldestE = (eldest == null ? (null) : ((Entry) eldest
1854: .getValue()));
1855: return evictLRU(eldestE);
1856: }
1857: }
1858:
1859: private class CacheSP implements ServiceProvider {
1860: private final CacheService cs = new CacheService() {
1861: public void submit(Response res) {
1862: CacheManager.this .submit(res);
1863: }
1864: };
1865:
1866: public Object getService(ServiceBroker sb, Object requestor,
1867: Class serviceClass) {
1868: if (!CacheService.class.isAssignableFrom(serviceClass)) {
1869: return null;
1870: }
1871: return cs;
1872: }
1873:
1874: public void releaseService(ServiceBroker sb, Object requestor,
1875: Class serviceClass, Object service) {
1876: }
1877: }
1878:
1879: private class HintSP implements ServiceProvider {
1880: private final HintService hs = new HintService() {
1881: public void add(String name, Bundle bundle) {
1882: CacheManager.this .add(name, bundle);
1883: }
1884:
1885: public void remove(String name, Bundle bundle) {
1886: CacheManager.this .remove(name, bundle);
1887: }
1888: };
1889:
1890: public Object getService(ServiceBroker sb, Object requestor,
1891: Class serviceClass) {
1892: if (!HintService.class.isAssignableFrom(serviceClass)) {
1893: return null;
1894: }
1895: return hs;
1896: }
1897:
1898: public void releaseService(ServiceBroker sb, Object requestor,
1899: Class serviceClass, Object service) {
1900: }
1901: }
1902: }
|