diff options
Diffstat (limited to 'src/org/xbill/DNS/Cache.java')
| -rw-r--r-- | src/org/xbill/DNS/Cache.java | 846 |
1 files changed, 846 insertions, 0 deletions
diff --git a/src/org/xbill/DNS/Cache.java b/src/org/xbill/DNS/Cache.java new file mode 100644 index 0000000..5497f45 --- /dev/null +++ b/src/org/xbill/DNS/Cache.java @@ -0,0 +1,846 @@ +// Copyright (c) 1999-2004 Brian Wellington (bwelling@xbill.org) + +package org.xbill.DNS; + +import java.io.*; +import java.util.*; + +/** + * A cache of DNS records. The cache obeys TTLs, so items are purged after + * their validity period is complete. Negative answers are cached, to + * avoid repeated failed DNS queries. The credibility of each RRset is + * maintained, so that more credible records replace less credible records, + * and lookups can specify the minimum credibility of data they are requesting. + * @see RRset + * @see Credibility + * + * @author Brian Wellington + */ + +public class Cache { + +private interface Element { + public boolean expired(); + public int compareCredibility(int cred); + public int getType(); +} + +private static int +limitExpire(long ttl, long maxttl) { + if (maxttl >= 0 && maxttl < ttl) + ttl = maxttl; + long expire = (System.currentTimeMillis() / 1000) + ttl; + if (expire < 0 || expire > Integer.MAX_VALUE) + return Integer.MAX_VALUE; + return (int)expire; +} + +private static class CacheRRset extends RRset implements Element { + private static final long serialVersionUID = 5971755205903597024L; + + int credibility; + int expire; + + public + CacheRRset(Record rec, int cred, long maxttl) { + super(); + this.credibility = cred; + this.expire = limitExpire(rec.getTTL(), maxttl); + addRR(rec); + } + + public + CacheRRset(RRset rrset, int cred, long maxttl) { + super(rrset); + this.credibility = cred; + this.expire = limitExpire(rrset.getTTL(), maxttl); + } + + public final boolean + expired() { + int now = (int)(System.currentTimeMillis() / 1000); + return (now >= expire); + } + + public final int + compareCredibility(int cred) { + return credibility - cred; + } + + public String + toString() { + StringBuffer sb = new StringBuffer(); + sb.append(super.toString()); + sb.append(" cl = "); + sb.append(credibility); + return sb.toString(); + } +} + +private static class NegativeElement implements Element { + int type; + Name name; + int credibility; + int expire; + + public + NegativeElement(Name name, int type, SOARecord soa, int cred, + long maxttl) + { + this.name = name; + this.type = type; + long cttl = 0; + if (soa != null) + cttl = soa.getMinimum(); + this.credibility = cred; + this.expire = limitExpire(cttl, maxttl); + } + + public int + getType() { + return type; + } + + public final boolean + expired() { + int now = (int)(System.currentTimeMillis() / 1000); + return (now >= expire); + } + + public final int + compareCredibility(int cred) { + return credibility - cred; + } + + public String + toString() { + StringBuffer sb = new StringBuffer(); + if (type == 0) + sb.append("NXDOMAIN " + name); + else + sb.append("NXRRSET " + name + " " + Type.string(type)); + sb.append(" cl = "); + sb.append(credibility); + return sb.toString(); + } +} + +private static class CacheMap extends LinkedHashMap { + private int maxsize = -1; + + CacheMap(int maxsize) { + super(16, (float) 0.75, true); + this.maxsize = maxsize; + } + + int + getMaxSize() { + return maxsize; + } + + void + setMaxSize(int maxsize) { + /* + * Note that this doesn't shrink the size of the map if + * the maximum size is lowered, but it should shrink as + * entries expire. + */ + this.maxsize = maxsize; + } + + protected boolean removeEldestEntry(Map.Entry eldest) { + return maxsize >= 0 && size() > maxsize; + } +} + +private CacheMap data; +private int maxncache = -1; +private int maxcache = -1; +private int dclass; + +private static final int defaultMaxEntries = 50000; + +/** + * Creates an empty Cache + * + * @param dclass The DNS class of this cache + * @see DClass + */ +public +Cache(int dclass) { + this.dclass = dclass; + data = new CacheMap(defaultMaxEntries); +} + +/** + * Creates an empty Cache for class IN. + * @see DClass + */ +public +Cache() { + this(DClass.IN); +} + +/** + * Creates a Cache which initially contains all records in the specified file. + */ +public +Cache(String file) throws IOException { + data = new CacheMap(defaultMaxEntries); + Master m = new Master(file); + Record record; + while ((record = m.nextRecord()) != null) + addRecord(record, Credibility.HINT, m); +} + +private synchronized Object +exactName(Name name) { + return data.get(name); +} + +private synchronized void +removeName(Name name) { + data.remove(name); +} + +private synchronized Element [] +allElements(Object types) { + if (types instanceof List) { + List typelist = (List) types; + int size = typelist.size(); + return (Element []) typelist.toArray(new Element[size]); + } else { + Element set = (Element) types; + return new Element[] {set}; + } +} + +private synchronized Element +oneElement(Name name, Object types, int type, int minCred) { + Element found = null; + + if (type == Type.ANY) + throw new IllegalArgumentException("oneElement(ANY)"); + if (types instanceof List) { + List list = (List) types; + for (int i = 0; i < list.size(); i++) { + Element set = (Element) list.get(i); + if (set.getType() == type) { + found = set; + break; + } + } + } else { + Element set = (Element) types; + if (set.getType() == type) + found = set; + } + if (found == null) + return null; + if (found.expired()) { + removeElement(name, type); + return null; + } + if (found.compareCredibility(minCred) < 0) + return null; + return found; +} + +private synchronized Element +findElement(Name name, int type, int minCred) { + Object types = exactName(name); + if (types == null) + return null; + return oneElement(name, types, type, minCred); +} + +private synchronized void +addElement(Name name, Element element) { + Object types = data.get(name); + if (types == null) { + data.put(name, element); + return; + } + int type = element.getType(); + if (types instanceof List) { + List list = (List) types; + for (int i = 0; i < list.size(); i++) { + Element elt = (Element) list.get(i); + if (elt.getType() == type) { + list.set(i, element); + return; + } + } + list.add(element); + } else { + Element elt = (Element) types; + if (elt.getType() == type) + data.put(name, element); + else { + LinkedList list = new LinkedList(); + list.add(elt); + list.add(element); + data.put(name, list); + } + } +} + +private synchronized void +removeElement(Name name, int type) { + Object types = data.get(name); + if (types == null) { + return; + } + if (types instanceof List) { + List list = (List) types; + for (int i = 0; i < list.size(); i++) { + Element elt = (Element) list.get(i); + if (elt.getType() == type) { + list.remove(i); + if (list.size() == 0) + data.remove(name); + return; + } + } + } else { + Element elt = (Element) types; + if (elt.getType() != type) + return; + data.remove(name); + } +} + +/** Empties the Cache. */ +public synchronized void +clearCache() { + data.clear(); +} + +/** + * Adds a record to the Cache. + * @param r The record to be added + * @param cred The credibility of the record + * @param o The source of the record (this could be a Message, for example) + * @see Record + */ +public synchronized void +addRecord(Record r, int cred, Object o) { + Name name = r.getName(); + int type = r.getRRsetType(); + if (!Type.isRR(type)) + return; + Element element = findElement(name, type, cred); + if (element == null) { + CacheRRset crrset = new CacheRRset(r, cred, maxcache); + addRRset(crrset, cred); + } else if (element.compareCredibility(cred) == 0) { + if (element instanceof CacheRRset) { + CacheRRset crrset = (CacheRRset) element; + crrset.addRR(r); + } + } +} + +/** + * Adds an RRset to the Cache. + * @param rrset The RRset to be added + * @param cred The credibility of these records + * @see RRset + */ +public synchronized void +addRRset(RRset rrset, int cred) { + long ttl = rrset.getTTL(); + Name name = rrset.getName(); + int type = rrset.getType(); + Element element = findElement(name, type, 0); + if (ttl == 0) { + if (element != null && element.compareCredibility(cred) <= 0) + removeElement(name, type); + } else { + if (element != null && element.compareCredibility(cred) <= 0) + element = null; + if (element == null) { + CacheRRset crrset; + if (rrset instanceof CacheRRset) + crrset = (CacheRRset) rrset; + else + crrset = new CacheRRset(rrset, cred, maxcache); + addElement(name, crrset); + } + } +} + +/** + * Adds a negative entry to the Cache. + * @param name The name of the negative entry + * @param type The type of the negative entry + * @param soa The SOA record to add to the negative cache entry, or null. + * The negative cache ttl is derived from the SOA. + * @param cred The credibility of the negative entry + */ +public synchronized void +addNegative(Name name, int type, SOARecord soa, int cred) { + long ttl = 0; + if (soa != null) + ttl = soa.getTTL(); + Element element = findElement(name, type, 0); + if (ttl == 0) { + if (element != null && element.compareCredibility(cred) <= 0) + removeElement(name, type); + } else { + if (element != null && element.compareCredibility(cred) <= 0) + element = null; + if (element == null) + addElement(name, new NegativeElement(name, type, + soa, cred, + maxncache)); + } +} + +/** + * Finds all matching sets or something that causes the lookup to stop. + */ +protected synchronized SetResponse +lookup(Name name, int type, int minCred) { + int labels; + int tlabels; + Element element; + Name tname; + Object types; + SetResponse sr; + + labels = name.labels(); + + for (tlabels = labels; tlabels >= 1; tlabels--) { + boolean isRoot = (tlabels == 1); + boolean isExact = (tlabels == labels); + + if (isRoot) + tname = Name.root; + else if (isExact) + tname = name; + else + tname = new Name(name, labels - tlabels); + + types = data.get(tname); + if (types == null) + continue; + + /* + * If this is the name, look for the actual type or a CNAME + * (unless it's an ANY query, where we return everything). + * Otherwise, look for a DNAME. + */ + if (isExact && type == Type.ANY) { + sr = new SetResponse(SetResponse.SUCCESSFUL); + Element [] elements = allElements(types); + int added = 0; + for (int i = 0; i < elements.length; i++) { + element = elements[i]; + if (element.expired()) { + removeElement(tname, element.getType()); + continue; + } + if (!(element instanceof CacheRRset)) + continue; + if (element.compareCredibility(minCred) < 0) + continue; + sr.addRRset((CacheRRset)element); + added++; + } + /* There were positive entries */ + if (added > 0) + return sr; + } else if (isExact) { + element = oneElement(tname, types, type, minCred); + if (element != null && + element instanceof CacheRRset) + { + sr = new SetResponse(SetResponse.SUCCESSFUL); + sr.addRRset((CacheRRset) element); + return sr; + } else if (element != null) { + sr = new SetResponse(SetResponse.NXRRSET); + return sr; + } + + element = oneElement(tname, types, Type.CNAME, minCred); + if (element != null && + element instanceof CacheRRset) + { + return new SetResponse(SetResponse.CNAME, + (CacheRRset) element); + } + } else { + element = oneElement(tname, types, Type.DNAME, minCred); + if (element != null && + element instanceof CacheRRset) + { + return new SetResponse(SetResponse.DNAME, + (CacheRRset) element); + } + } + + /* Look for an NS */ + element = oneElement(tname, types, Type.NS, minCred); + if (element != null && element instanceof CacheRRset) + return new SetResponse(SetResponse.DELEGATION, + (CacheRRset) element); + + /* Check for the special NXDOMAIN element. */ + if (isExact) { + element = oneElement(tname, types, 0, minCred); + if (element != null) + return SetResponse.ofType(SetResponse.NXDOMAIN); + } + + } + return SetResponse.ofType(SetResponse.UNKNOWN); +} + +/** + * Looks up Records in the Cache. This follows CNAMEs and handles negatively + * cached data. + * @param name The name to look up + * @param type The type to look up + * @param minCred The minimum acceptable credibility + * @return A SetResponse object + * @see SetResponse + * @see Credibility + */ +public SetResponse +lookupRecords(Name name, int type, int minCred) { + return lookup(name, type, minCred); +} + +private RRset [] +findRecords(Name name, int type, int minCred) { + SetResponse cr = lookupRecords(name, type, minCred); + if (cr.isSuccessful()) + return cr.answers(); + else + return null; +} + +/** + * Looks up credible Records in the Cache (a wrapper around lookupRecords). + * Unlike lookupRecords, this given no indication of why failure occurred. + * @param name The name to look up + * @param type The type to look up + * @return An array of RRsets, or null + * @see Credibility + */ +public RRset [] +findRecords(Name name, int type) { + return findRecords(name, type, Credibility.NORMAL); +} + +/** + * Looks up Records in the Cache (a wrapper around lookupRecords). Unlike + * lookupRecords, this given no indication of why failure occurred. + * @param name The name to look up + * @param type The type to look up + * @return An array of RRsets, or null + * @see Credibility + */ +public RRset [] +findAnyRecords(Name name, int type) { + return findRecords(name, type, Credibility.GLUE); +} + +private final int +getCred(int section, boolean isAuth) { + if (section == Section.ANSWER) { + if (isAuth) + return Credibility.AUTH_ANSWER; + else + return Credibility.NONAUTH_ANSWER; + } else if (section == Section.AUTHORITY) { + if (isAuth) + return Credibility.AUTH_AUTHORITY; + else + return Credibility.NONAUTH_AUTHORITY; + } else if (section == Section.ADDITIONAL) { + return Credibility.ADDITIONAL; + } else + throw new IllegalArgumentException("getCred: invalid section"); +} + +private static void +markAdditional(RRset rrset, Set names) { + Record first = rrset.first(); + if (first.getAdditionalName() == null) + return; + + Iterator it = rrset.rrs(); + while (it.hasNext()) { + Record r = (Record) it.next(); + Name name = r.getAdditionalName(); + if (name != null) + names.add(name); + } +} + +/** + * Adds all data from a Message into the Cache. Each record is added with + * the appropriate credibility, and negative answers are cached as such. + * @param in The Message to be added + * @return A SetResponse that reflects what would be returned from a cache + * lookup, or null if nothing useful could be cached from the message. + * @see Message + */ +public SetResponse +addMessage(Message in) { + boolean isAuth = in.getHeader().getFlag(Flags.AA); + Record question = in.getQuestion(); + Name qname; + Name curname; + int qtype; + int qclass; + int cred; + int rcode = in.getHeader().getRcode(); + boolean completed = false; + RRset [] answers, auth, addl; + SetResponse response = null; + boolean verbose = Options.check("verbosecache"); + HashSet additionalNames; + + if ((rcode != Rcode.NOERROR && rcode != Rcode.NXDOMAIN) || + question == null) + return null; + + qname = question.getName(); + qtype = question.getType(); + qclass = question.getDClass(); + + curname = qname; + + additionalNames = new HashSet(); + + answers = in.getSectionRRsets(Section.ANSWER); + for (int i = 0; i < answers.length; i++) { + if (answers[i].getDClass() != qclass) + continue; + int type = answers[i].getType(); + Name name = answers[i].getName(); + cred = getCred(Section.ANSWER, isAuth); + if ((type == qtype || qtype == Type.ANY) && + name.equals(curname)) + { + addRRset(answers[i], cred); + completed = true; + if (curname == qname) { + if (response == null) + response = new SetResponse( + SetResponse.SUCCESSFUL); + response.addRRset(answers[i]); + } + markAdditional(answers[i], additionalNames); + } else if (type == Type.CNAME && name.equals(curname)) { + CNAMERecord cname; + addRRset(answers[i], cred); + if (curname == qname) + response = new SetResponse(SetResponse.CNAME, + answers[i]); + cname = (CNAMERecord) answers[i].first(); + curname = cname.getTarget(); + } else if (type == Type.DNAME && curname.subdomain(name)) { + DNAMERecord dname; + addRRset(answers[i], cred); + if (curname == qname) + response = new SetResponse(SetResponse.DNAME, + answers[i]); + dname = (DNAMERecord) answers[i].first(); + try { + curname = curname.fromDNAME(dname); + } + catch (NameTooLongException e) { + break; + } + } + } + + auth = in.getSectionRRsets(Section.AUTHORITY); + RRset soa = null, ns = null; + for (int i = 0; i < auth.length; i++) { + if (auth[i].getType() == Type.SOA && + curname.subdomain(auth[i].getName())) + soa = auth[i]; + else if (auth[i].getType() == Type.NS && + curname.subdomain(auth[i].getName())) + ns = auth[i]; + } + if (!completed) { + /* This is a negative response or a referral. */ + int cachetype = (rcode == Rcode.NXDOMAIN) ? 0 : qtype; + if (rcode == Rcode.NXDOMAIN || soa != null || ns == null) { + /* Negative response */ + cred = getCred(Section.AUTHORITY, isAuth); + SOARecord soarec = null; + if (soa != null) + soarec = (SOARecord) soa.first(); + addNegative(curname, cachetype, soarec, cred); + if (response == null) { + int responseType; + if (rcode == Rcode.NXDOMAIN) + responseType = SetResponse.NXDOMAIN; + else + responseType = SetResponse.NXRRSET; + response = SetResponse.ofType(responseType); + } + /* DNSSEC records are not cached. */ + } else { + /* Referral response */ + cred = getCred(Section.AUTHORITY, isAuth); + addRRset(ns, cred); + markAdditional(ns, additionalNames); + if (response == null) + response = new SetResponse( + SetResponse.DELEGATION, + ns); + } + } else if (rcode == Rcode.NOERROR && ns != null) { + /* Cache the NS set from a positive response. */ + cred = getCred(Section.AUTHORITY, isAuth); + addRRset(ns, cred); + markAdditional(ns, additionalNames); + } + + addl = in.getSectionRRsets(Section.ADDITIONAL); + for (int i = 0; i < addl.length; i++) { + int type = addl[i].getType(); + if (type != Type.A && type != Type.AAAA && type != Type.A6) + continue; + Name name = addl[i].getName(); + if (!additionalNames.contains(name)) + continue; + cred = getCred(Section.ADDITIONAL, isAuth); + addRRset(addl[i], cred); + } + if (verbose) + System.out.println("addMessage: " + response); + return (response); +} + +/** + * Flushes an RRset from the cache + * @param name The name of the records to be flushed + * @param type The type of the records to be flushed + * @see RRset + */ +public void +flushSet(Name name, int type) { + removeElement(name, type); +} + +/** + * Flushes all RRsets with a given name from the cache + * @param name The name of the records to be flushed + * @see RRset + */ +public void +flushName(Name name) { + removeName(name); +} + +/** + * Sets the maximum length of time that a negative response will be stored + * in this Cache. A negative value disables this feature (that is, sets + * no limit). + */ +public void +setMaxNCache(int seconds) { + maxncache = seconds; +} + +/** + * Gets the maximum length of time that a negative response will be stored + * in this Cache. A negative value indicates no limit. + */ +public int +getMaxNCache() { + return maxncache; +} + +/** + * Sets the maximum length of time that records will be stored in this + * Cache. A negative value disables this feature (that is, sets no limit). + */ +public void +setMaxCache(int seconds) { + maxcache = seconds; +} + +/** + * Gets the maximum length of time that records will be stored + * in this Cache. A negative value indicates no limit. + */ +public int +getMaxCache() { + return maxcache; +} + +/** + * Gets the current number of entries in the Cache, where an entry consists + * of all records with a specific Name. + */ +public int +getSize() { + return data.size(); +} + +/** + * Gets the maximum number of entries in the Cache, where an entry consists + * of all records with a specific Name. A negative value is treated as an + * infinite limit. + */ +public int +getMaxEntries() { + return data.getMaxSize(); +} + +/** + * Sets the maximum number of entries in the Cache, where an entry consists + * of all records with a specific Name. A negative value is treated as an + * infinite limit. + * + * Note that setting this to a value lower than the current number + * of entries will not cause the Cache to shrink immediately. + * + * The default maximum number of entries is 50000. + * + * @param entries The maximum number of entries in the Cache. + */ +public void +setMaxEntries(int entries) { + data.setMaxSize(entries); +} + +/** + * Returns the DNS class of this cache. + */ +public int +getDClass() { + return dclass; +} + +/** + * Returns the contents of the Cache as a string. + */ +public String +toString() { + StringBuffer sb = new StringBuffer(); + synchronized (this) { + Iterator it = data.values().iterator(); + while (it.hasNext()) { + Element [] elements = allElements(it.next()); + for (int i = 0; i < elements.length; i++) { + sb.append(elements[i]); + sb.append("\n"); + } + } + } + return sb.toString(); +} + +} |