001/*
002 * Copyright 2015-2018 the original author or authors
003 *
004 * This software is licensed under the Apache License, Version 2.0,
005 * the GNU Lesser General Public License version 2 or later ("LGPL")
006 * and the WTFPL.
007 * You may choose either license to govern your use of this software only
008 * upon the condition that you accept all of the terms of either
009 * the Apache License 2.0, the LGPL 2.1+ or the WTFPL.
010 */
011package org.minidns.cache;
012
013import java.util.LinkedHashMap;
014import java.util.Map.Entry;
015
016import org.minidns.DnsCache;
017import org.minidns.dnsmessage.DnsMessage;
018import org.minidns.dnsname.DnsName;
019import org.minidns.record.Data;
020import org.minidns.record.Record;
021
022/**
023 * LRU based DNSCache backed by a LinkedHashMap.
024 */
025public class LruCache extends DnsCache {
026
027    /**
028     * Internal miss count.
029     */
030    protected long missCount = 0L;
031
032    /**
033     * Internal expire count (subset of misses that was caused by expire).
034     */
035    protected long expireCount = 0L;
036
037    /**
038     * Internal hit count.
039     */
040    protected long hitCount = 0L;
041
042    /**
043     * The internal capacity of the backend cache.
044     */
045    protected int capacity;
046
047    /**
048     * The upper bound of the ttl. All longer TTLs will be capped by this ttl.
049     */
050    protected long maxTTL;
051
052    /**
053     * The backend cache.
054     */
055    protected LinkedHashMap<DnsMessage, DnsMessage> backend;
056
057    /**
058     * Create a new LRUCache with given capacity and upper bound ttl.
059     * @param capacity The internal capacity.
060     * @param maxTTL The upper bound for any ttl.
061     */
062    @SuppressWarnings("serial")
063    public LruCache(final int capacity, final long maxTTL) {
064        this.capacity = capacity;
065        this.maxTTL = maxTTL;
066        backend = new LinkedHashMap<DnsMessage, DnsMessage>(
067                Math.min(capacity + (capacity + 3) / 4 + 2, 11), 0.75f, true)
068            {
069                @Override
070                protected boolean removeEldestEntry(
071                        Entry<DnsMessage, DnsMessage> eldest) {
072                    return size() > capacity;
073                }
074            };
075    }
076
077    /**
078     * Create a new LRUCache with given capacity.
079     * @param capacity The capacity of this cache.
080     */
081    public LruCache(final int capacity) {
082        this(capacity, Long.MAX_VALUE);
083    }
084
085    public LruCache() {
086        this(DEFAULT_CACHE_SIZE);
087    }
088
089    @Override
090    protected synchronized void putNormalized(DnsMessage q, DnsMessage message) {
091        if (message.receiveTimestamp <= 0L) {
092            return;
093        }
094        backend.put(q, message);
095    }
096
097    @Override
098    protected synchronized DnsMessage getNormalized(DnsMessage q) {
099        DnsMessage message = backend.get(q);
100        if (message == null) {
101            missCount++;
102            return null;
103        }
104
105        long ttl = maxTTL;
106        // RFC 2181 ยง 5.2 says that all TTLs in a RRSet should be equal, if this isn't the case, then we assume the
107        // shortest TTL to be the effective one.
108        for (Record<? extends Data> r : message.answerSection) {
109            ttl = Math.min(ttl, r.ttl);
110        }
111
112        final long expiryDate = message.receiveTimestamp + (ttl * 1000);
113        final long now = System.currentTimeMillis();
114        if (expiryDate < now) {
115            missCount++;
116            expireCount++;
117            backend.remove(q);
118            return null;
119        } else {
120            hitCount++;
121            return message;
122        }
123    }
124
125    /**
126     * Clear all entries in this cache.
127     */
128    public synchronized void clear() {
129        backend.clear();
130        missCount = 0L;
131        hitCount = 0L;
132        expireCount = 0L;
133    }
134
135    /**
136     * Get the miss count of this cache which is the number of fruitless
137     * get calls since this cache was last resetted.
138     * @return The number of cache misses.
139     */
140    public long getMissCount() {
141        return missCount;
142    }
143
144    /**
145     * The number of expires (cache hits that have had a ttl to low to be
146     * retrieved).
147     * @return The expire count.
148     */
149    public long getExpireCount() {
150        return expireCount;
151    }
152
153    /**
154     * The cache hit count (all sucessful calls to get).
155     * @return The hit count.
156     */
157    public long getHitCount() {
158        return hitCount;
159    }
160
161    @Override
162    public String toString() {
163        return "LRUCache{usage=" + backend.size() + "/" + capacity + ", hits=" + hitCount + ", misses=" + missCount + ", expires=" + expireCount + "}";
164    }
165
166    @Override
167    public void offer(DnsMessage query, DnsMessage reply, DnsName knownAuthoritativeZone) {
168    }
169}