001: // Copyright (c) 1999-2004 Brian Wellington (bwelling@xbill.org)
002:
003: package org.xbill.DNS;
004:
005: import java.io.*;
006: import java.util.*;
007:
008: /**
009: * A cache of DNS records. The cache obeys TTLs, so items are purged after
010: * their validity period is complete. Negative answers are cached, to
011: * avoid repeated failed DNS queries. The credibility of each RRset is
012: * maintained, so that more credible records replace less credible records,
013: * and lookups can specify the minimum credibility of data they are requesting.
014: * @see RRset
015: * @see Credibility
016: *
017: * @author Brian Wellington
018: */
019:
020: public class Cache {
021:
022: private interface Element {
023: public boolean expired();
024:
025: public int compareCredibility(int cred);
026:
027: public int getType();
028: }
029:
030: private static int limitExpire(long ttl, long maxttl) {
031: if (maxttl >= 0 && maxttl < ttl)
032: ttl = maxttl;
033: int expire = (int) ((System.currentTimeMillis() / 1000) + ttl);
034: if (expire < 0 || expire > Integer.MAX_VALUE)
035: return Integer.MAX_VALUE;
036: return expire;
037: }
038:
039: private static class CacheRRset extends RRset implements Element {
040: int credibility;
041: int expire;
042:
043: public CacheRRset(Record rec, int cred, long maxttl) {
044: super ();
045: this .credibility = cred;
046: this .expire = limitExpire(rec.getTTL(), maxttl);
047: addRR(rec);
048: }
049:
050: public CacheRRset(RRset rrset, int cred, long maxttl) {
051: super (rrset);
052: this .credibility = cred;
053: this .expire = limitExpire(rrset.getTTL(), maxttl);
054: }
055:
056: public final boolean expired() {
057: int now = (int) (System.currentTimeMillis() / 1000);
058: return (now >= expire);
059: }
060:
061: public final int compareCredibility(int cred) {
062: return credibility - cred;
063: }
064:
065: public String toString() {
066: StringBuffer sb = new StringBuffer();
067: sb.append(super .toString());
068: sb.append(" cl = ");
069: sb.append(credibility);
070: return sb.toString();
071: }
072: }
073:
074: private static class NegativeElement implements Element {
075: int type;
076: Name name;
077: SOARecord soa;
078: int credibility;
079: int expire;
080:
081: public NegativeElement(Name name, int type, SOARecord soa,
082: int cred, long maxttl) {
083: this .name = name;
084: this .type = type;
085: this .soa = soa;
086: long cttl = 0;
087: if (soa != null)
088: cttl = soa.getMinimum();
089: this .credibility = cred;
090: this .expire = limitExpire(cttl, maxttl);
091: }
092:
093: public int getType() {
094: return type;
095: }
096:
097: public final boolean expired() {
098: int now = (int) (System.currentTimeMillis() / 1000);
099: return (now >= expire);
100: }
101:
102: public final int compareCredibility(int cred) {
103: return credibility - cred;
104: }
105:
106: public String toString() {
107: StringBuffer sb = new StringBuffer();
108: if (type == 0)
109: sb.append("NXDOMAIN " + name);
110: else
111: sb.append("NXRRSET " + name + " " + Type.string(type));
112: sb.append(" cl = ");
113: sb.append(credibility);
114: return sb.toString();
115: }
116: }
117:
118: private static class CacheMap extends LinkedHashMap {
119: private int maxsize = -1;
120:
121: CacheMap(int maxsize) {
122: super (16, (float) 0.75, true);
123: this .maxsize = maxsize;
124: }
125:
126: int getMaxSize() {
127: return maxsize;
128: }
129:
130: void setMaxSize(int maxsize) {
131: /*
132: * Note that this doesn't shrink the size of the map if
133: * the maximum size is lowered, but it should shrink as
134: * entries expire.
135: */
136: this .maxsize = maxsize;
137: }
138:
139: protected boolean removeEldestEntry(Map.Entry eldest) {
140: return maxsize >= 0 && size() > maxsize;
141: }
142: }
143:
144: private CacheMap data;
145: private int maxncache = -1;
146: private int maxcache = -1;
147: private int dclass;
148:
149: private static final int defaultMaxEntries = 50000;
150:
151: /**
152: * Creates an empty Cache
153: *
154: * @param dclass The DNS class of this cache
155: * @see DClass
156: */
157: public Cache(int dclass) {
158: this .dclass = dclass;
159: data = new CacheMap(defaultMaxEntries);
160: }
161:
162: /**
163: * Creates an empty Cache for class IN.
164: * @see DClass
165: */
166: public Cache() {
167: this (DClass.IN);
168: }
169:
170: /**
171: * Creates a Cache which initially contains all records in the specified file.
172: */
173: public Cache(String file) throws IOException {
174: data = new CacheMap(defaultMaxEntries);
175: Master m = new Master(file);
176: Record record;
177: while ((record = m.nextRecord()) != null)
178: addRecord(record, Credibility.HINT, m);
179: }
180:
181: private synchronized Object exactName(Name name) {
182: return data.get(name);
183: }
184:
185: private synchronized void removeName(Name name) {
186: data.remove(name);
187: }
188:
189: private synchronized Element[] allElements(Object types) {
190: if (types instanceof List) {
191: List typelist = (List) types;
192: int size = typelist.size();
193: return (Element[]) typelist.toArray(new Element[size]);
194: } else {
195: Element set = (Element) types;
196: return new Element[] { set };
197: }
198: }
199:
200: private synchronized Element oneElement(Name name, Object types,
201: int type, int minCred) {
202: Element found = null;
203:
204: if (type == Type.ANY)
205: throw new IllegalArgumentException("oneElement(ANY)");
206: if (types instanceof List) {
207: List list = (List) types;
208: for (int i = 0; i < list.size(); i++) {
209: Element set = (Element) list.get(i);
210: if (set.getType() == type) {
211: found = set;
212: break;
213: }
214: }
215: } else {
216: Element set = (Element) types;
217: if (set.getType() == type)
218: found = set;
219: }
220: if (found == null)
221: return null;
222: if (found.expired()) {
223: removeElement(name, type);
224: return null;
225: }
226: if (found.compareCredibility(minCred) < 0)
227: return null;
228: return found;
229: }
230:
231: private synchronized Element findElement(Name name, int type,
232: int minCred) {
233: Object types = exactName(name);
234: if (types == null)
235: return null;
236: return oneElement(name, types, type, minCred);
237: }
238:
239: private synchronized void addElement(Name name, Element element) {
240: Object types = data.get(name);
241: if (types == null) {
242: data.put(name, element);
243: return;
244: }
245: int type = element.getType();
246: if (types instanceof List) {
247: List list = (List) types;
248: for (int i = 0; i < list.size(); i++) {
249: Element elt = (Element) list.get(i);
250: if (elt.getType() == type) {
251: list.set(i, element);
252: return;
253: }
254: }
255: list.add(element);
256: } else {
257: Element elt = (Element) types;
258: if (elt.getType() == type)
259: data.put(name, element);
260: else {
261: LinkedList list = new LinkedList();
262: list.add(elt);
263: list.add(element);
264: data.put(name, list);
265: }
266: }
267: }
268:
269: private synchronized void removeElement(Name name, int type) {
270: Object types = data.get(name);
271: if (types == null) {
272: return;
273: }
274: if (types instanceof List) {
275: List list = (List) types;
276: for (int i = 0; i < list.size(); i++) {
277: Element elt = (Element) list.get(i);
278: if (elt.getType() == type) {
279: list.remove(i);
280: if (list.size() == 0)
281: data.remove(name);
282: return;
283: }
284: }
285: } else {
286: Element elt = (Element) types;
287: if (elt.getType() != type)
288: return;
289: data.remove(name);
290: }
291: }
292:
293: /** Empties the Cache. */
294: public synchronized void clearCache() {
295: data.clear();
296: }
297:
298: /**
299: * Adds a record to the Cache.
300: * @param r The record to be added
301: * @param cred The credibility of the record
302: * @param o The source of the record (this could be a Message, for example)
303: * @see Record
304: */
305: public synchronized void addRecord(Record r, int cred, Object o) {
306: Name name = r.getName();
307: int type = r.getRRsetType();
308: if (!Type.isRR(type))
309: return;
310: Element element = findElement(name, type, cred);
311: if (element == null) {
312: CacheRRset crrset = new CacheRRset(r, cred, maxcache);
313: addRRset(crrset, cred);
314: } else if (element.compareCredibility(cred) == 0) {
315: if (element instanceof CacheRRset) {
316: CacheRRset crrset = (CacheRRset) element;
317: crrset.addRR(r);
318: }
319: }
320: }
321:
322: /**
323: * Adds an RRset to the Cache.
324: * @param rrset The RRset to be added
325: * @param cred The credibility of these records
326: * @see RRset
327: */
328: public synchronized void addRRset(RRset rrset, int cred) {
329: long ttl = rrset.getTTL();
330: Name name = rrset.getName();
331: int type = rrset.getType();
332: Element element = findElement(name, type, 0);
333: if (ttl == 0) {
334: if (element != null
335: && element.compareCredibility(cred) <= 0)
336: removeElement(name, type);
337: } else {
338: if (element != null
339: && element.compareCredibility(cred) <= 0)
340: element = null;
341: if (element == null) {
342: CacheRRset crrset;
343: if (rrset instanceof CacheRRset)
344: crrset = (CacheRRset) rrset;
345: else
346: crrset = new CacheRRset(rrset, cred, maxcache);
347: addElement(name, crrset);
348: }
349: }
350: }
351:
352: /**
353: * Adds a negative entry to the Cache.
354: * @param name The name of the negative entry
355: * @param type The type of the negative entry
356: * @param soa The SOA record to add to the negative cache entry, or null.
357: * The negative cache ttl is derived from the SOA.
358: * @param cred The credibility of the negative entry
359: */
360: public synchronized void addNegative(Name name, int type,
361: SOARecord soa, int cred) {
362: long ttl = 0;
363: if (soa != null)
364: ttl = soa.getTTL();
365: Element element = findElement(name, type, 0);
366: if (ttl == 0) {
367: if (element != null
368: && element.compareCredibility(cred) <= 0)
369: removeElement(name, type);
370: } else {
371: if (element != null
372: && element.compareCredibility(cred) <= 0)
373: element = null;
374: if (element == null)
375: addElement(name, new NegativeElement(name, type, soa,
376: cred, maxncache));
377: }
378: }
379:
380: /**
381: * Finds all matching sets or something that causes the lookup to stop.
382: */
383: protected synchronized SetResponse lookup(Name name, int type,
384: int minCred) {
385: int labels;
386: int tlabels;
387: Element element;
388: CacheRRset crrset;
389: Name tname;
390: Object types;
391: SetResponse sr;
392:
393: labels = name.labels();
394:
395: for (tlabels = labels; tlabels >= 1; tlabels--) {
396: boolean isRoot = (tlabels == 1);
397: boolean isExact = (tlabels == labels);
398:
399: if (isRoot)
400: tname = Name.root;
401: else if (isExact)
402: tname = name;
403: else
404: tname = new Name(name, labels - tlabels);
405:
406: types = data.get(tname);
407: if (types == null)
408: continue;
409:
410: /* If this is an ANY lookup, return everything. */
411: if (isExact && type == Type.ANY) {
412: sr = new SetResponse(SetResponse.SUCCESSFUL);
413: Element[] elements = allElements(types);
414: int added = 0;
415: for (int i = 0; i < elements.length; i++) {
416: element = elements[i];
417: if (element.expired()) {
418: removeElement(tname, element.getType());
419: continue;
420: }
421: if (!(element instanceof CacheRRset))
422: continue;
423: if (element.compareCredibility(minCred) < 0)
424: continue;
425: sr.addRRset((CacheRRset) element);
426: added++;
427: }
428: /* There were positive entries */
429: if (added > 0)
430: return sr;
431: }
432:
433: /*
434: * If this is the name, look for the actual type or a CNAME.
435: * Otherwise, look for a DNAME.
436: */
437: if (isExact) {
438: element = oneElement(tname, types, type, minCred);
439: if (element != null && element instanceof CacheRRset) {
440: sr = new SetResponse(SetResponse.SUCCESSFUL);
441: sr.addRRset((CacheRRset) element);
442: return sr;
443: } else if (element != null) {
444: sr = new SetResponse(SetResponse.NXRRSET);
445: return sr;
446: }
447:
448: element = oneElement(tname, types, Type.CNAME, minCred);
449: if (element != null && element instanceof CacheRRset) {
450: return new SetResponse(SetResponse.CNAME,
451: (CacheRRset) element);
452: }
453: } else {
454: element = oneElement(tname, types, Type.DNAME, minCred);
455: if (element != null && element instanceof CacheRRset) {
456: return new SetResponse(SetResponse.DNAME,
457: (CacheRRset) element);
458: }
459: }
460:
461: /* Look for an NS */
462: element = oneElement(tname, types, Type.NS, minCred);
463: if (element != null && element instanceof CacheRRset)
464: return new SetResponse(SetResponse.DELEGATION,
465: (CacheRRset) element);
466:
467: /* Check for the special NXDOMAIN element. */
468: if (isExact) {
469: element = oneElement(tname, types, 0, minCred);
470: if (element != null)
471: return SetResponse.ofType(SetResponse.NXDOMAIN);
472: }
473:
474: }
475: return SetResponse.ofType(SetResponse.UNKNOWN);
476: }
477:
478: /**
479: * Looks up Records in the Cache. This follows CNAMEs and handles negatively
480: * cached data.
481: * @param name The name to look up
482: * @param type The type to look up
483: * @param minCred The minimum acceptable credibility
484: * @return A SetResponse object
485: * @see SetResponse
486: * @see Credibility
487: */
488: public SetResponse lookupRecords(Name name, int type, int minCred) {
489: return lookup(name, type, minCred);
490: }
491:
492: private RRset[] findRecords(Name name, int type, int minCred) {
493: SetResponse cr = lookupRecords(name, type, minCred);
494: if (cr.isSuccessful())
495: return cr.answers();
496: else
497: return null;
498: }
499:
500: /**
501: * Looks up credible Records in the Cache (a wrapper around lookupRecords).
502: * Unlike lookupRecords, this given no indication of why failure occurred.
503: * @param name The name to look up
504: * @param type The type to look up
505: * @return An array of RRsets, or null
506: * @see Credibility
507: */
508: public RRset[] findRecords(Name name, int type) {
509: return findRecords(name, type, Credibility.NORMAL);
510: }
511:
512: /**
513: * Looks up Records in the Cache (a wrapper around lookupRecords). Unlike
514: * lookupRecords, this given no indication of why failure occurred.
515: * @param name The name to look up
516: * @param type The type to look up
517: * @return An array of RRsets, or null
518: * @see Credibility
519: */
520: public RRset[] findAnyRecords(Name name, int type) {
521: return findRecords(name, type, Credibility.GLUE);
522: }
523:
524: private final int getCred(int section, boolean isAuth) {
525: if (section == Section.ANSWER) {
526: if (isAuth)
527: return Credibility.AUTH_ANSWER;
528: else
529: return Credibility.NONAUTH_ANSWER;
530: } else if (section == Section.AUTHORITY) {
531: if (isAuth)
532: return Credibility.AUTH_AUTHORITY;
533: else
534: return Credibility.NONAUTH_AUTHORITY;
535: } else if (section == Section.ADDITIONAL) {
536: return Credibility.ADDITIONAL;
537: } else
538: throw new IllegalArgumentException(
539: "getCred: invalid section");
540: }
541:
542: private static void markAdditional(RRset rrset, Set names) {
543: Record first = rrset.first();
544: if (first.getAdditionalName() == null)
545: return;
546:
547: Iterator it = rrset.rrs();
548: while (it.hasNext()) {
549: Record r = (Record) it.next();
550: Name name = r.getAdditionalName();
551: if (name != null)
552: names.add(name);
553: }
554: }
555:
556: /**
557: * Adds all data from a Message into the Cache. Each record is added with
558: * the appropriate credibility, and negative answers are cached as such.
559: * @param in The Message to be added
560: * @return A SetResponse that reflects what would be returned from a cache
561: * lookup, or null if nothing useful could be cached from the message.
562: * @see Message
563: */
564: public SetResponse addMessage(Message in) {
565: boolean isAuth = in.getHeader().getFlag(Flags.AA);
566: Record question = in.getQuestion();
567: Name qname;
568: Name curname;
569: int qtype;
570: int qclass;
571: int cred;
572: int rcode = in.getHeader().getRcode();
573: boolean haveAnswer = false;
574: boolean completed = false;
575: RRset[] answers, auth, addl;
576: SetResponse response = null;
577: boolean verbose = Options.check("verbosecache");
578: HashSet additionalNames;
579:
580: if ((rcode != Rcode.NOERROR && rcode != Rcode.NXDOMAIN)
581: || question == null)
582: return null;
583:
584: qname = question.getName();
585: qtype = question.getType();
586: qclass = question.getDClass();
587:
588: curname = qname;
589:
590: additionalNames = new HashSet();
591:
592: answers = in.getSectionRRsets(Section.ANSWER);
593: for (int i = 0; i < answers.length; i++) {
594: if (answers[i].getDClass() != qclass)
595: continue;
596: int type = answers[i].getType();
597: Name name = answers[i].getName();
598: cred = getCred(Section.ANSWER, isAuth);
599: if ((type == qtype || qtype == Type.ANY)
600: && name.equals(curname)) {
601: addRRset(answers[i], cred);
602: completed = true;
603: haveAnswer = true;
604: if (curname == qname) {
605: if (response == null)
606: response = new SetResponse(
607: SetResponse.SUCCESSFUL);
608: response.addRRset(answers[i]);
609: }
610: markAdditional(answers[i], additionalNames);
611: } else if (type == Type.CNAME && name.equals(curname)) {
612: CNAMERecord cname;
613: addRRset(answers[i], cred);
614: if (curname == qname)
615: response = new SetResponse(SetResponse.CNAME,
616: answers[i]);
617: cname = (CNAMERecord) answers[i].first();
618: curname = cname.getTarget();
619: haveAnswer = true;
620: } else if (type == Type.DNAME && curname.subdomain(name)) {
621: DNAMERecord dname;
622: addRRset(answers[i], cred);
623: if (curname == qname)
624: response = new SetResponse(SetResponse.DNAME,
625: answers[i]);
626: dname = (DNAMERecord) answers[i].first();
627: try {
628: curname = curname.fromDNAME(dname);
629: } catch (NameTooLongException e) {
630: break;
631: }
632: haveAnswer = true;
633: }
634: }
635:
636: auth = in.getSectionRRsets(Section.AUTHORITY);
637: RRset soa = null, ns = null;
638: for (int i = 0; i < auth.length; i++) {
639: if (auth[i].getType() == Type.SOA
640: && curname.subdomain(auth[i].getName()))
641: soa = auth[i];
642: else if (auth[i].getType() == Type.NS
643: && curname.subdomain(auth[i].getName()))
644: ns = auth[i];
645: }
646: if (!completed) {
647: /* This is a negative response or a referral. */
648: int cachetype = (rcode == Rcode.NXDOMAIN) ? 0 : qtype;
649: if (soa != null || ns == null) {
650: /* Negative response */
651: cred = getCred(Section.AUTHORITY, isAuth);
652: SOARecord soarec = null;
653: if (soa != null)
654: soarec = (SOARecord) soa.first();
655: addNegative(curname, cachetype, soarec, cred);
656: if (response == null) {
657: int responseType;
658: if (rcode == Rcode.NXDOMAIN)
659: responseType = SetResponse.NXDOMAIN;
660: else
661: responseType = SetResponse.NXRRSET;
662: response = SetResponse.ofType(responseType);
663: }
664: /* NXT records are not cached yet. */
665: } else {
666: /* Referral response */
667: cred = getCred(Section.AUTHORITY, isAuth);
668: addRRset(ns, cred);
669: markAdditional(ns, additionalNames);
670: if (response == null)
671: response = new SetResponse(SetResponse.DELEGATION,
672: ns);
673: }
674: } else if (rcode == Rcode.NOERROR && ns != null) {
675: /* Cache the NS set from a positive response. */
676: cred = getCred(Section.AUTHORITY, isAuth);
677: addRRset(ns, cred);
678: markAdditional(ns, additionalNames);
679: }
680:
681: addl = in.getSectionRRsets(Section.ADDITIONAL);
682: for (int i = 0; i < addl.length; i++) {
683: int type = addl[i].getType();
684: if (type != Type.A && type != Type.AAAA && type != Type.A6)
685: continue;
686: Name name = addl[i].getName();
687: if (!additionalNames.contains(name))
688: continue;
689: cred = getCred(Section.ADDITIONAL, isAuth);
690: addRRset(addl[i], cred);
691: }
692: if (verbose)
693: System.out.println("addMessage: " + response);
694: return (response);
695: }
696:
697: /**
698: * Flushes an RRset from the cache
699: * @param name The name of the records to be flushed
700: * @param type The type of the records to be flushed
701: * @see RRset
702: */
703: public void flushSet(Name name, int type) {
704: removeElement(name, type);
705: }
706:
707: /**
708: * Flushes all RRsets with a given name from the cache
709: * @param name The name of the records to be flushed
710: * @see RRset
711: */
712: public void flushName(Name name) {
713: removeName(name);
714: }
715:
716: /**
717: * Sets the maximum length of time that a negative response will be stored
718: * in this Cache. A negative value disables this feature (that is, sets
719: * no limit).
720: */
721: public void setMaxNCache(int seconds) {
722: maxncache = seconds;
723: }
724:
725: /**
726: * Gets the maximum length of time that a negative response will be stored
727: * in this Cache. A negative value indicates no limit.
728: */
729: public int getMaxNCache() {
730: return maxncache;
731: }
732:
733: /**
734: * Sets the maximum length of time that records will be stored in this
735: * Cache. A negative value disables this feature (that is, sets no limit).
736: */
737: public void setMaxCache(int seconds) {
738: maxcache = seconds;
739: }
740:
741: /**
742: * Gets the maximum length of time that records will be stored
743: * in this Cache. A negative value indicates no limit.
744: */
745: public int getMaxCache() {
746: return maxcache;
747: }
748:
749: /**
750: * Gets the current number of entries in the Cache, where an entry consists
751: * of all records with a specific Name.
752: */
753: public int getSize() {
754: return data.size();
755: }
756:
757: /**
758: * Gets the maximum number of entries in the Cache, where an entry consists
759: * of all records with a specific Name. A negative value is treated as an
760: * infinite limit.
761: */
762: public int getMaxEntries() {
763: return data.getMaxSize();
764: }
765:
766: /**
767: * Sets the maximum number of entries in the Cache, where an entry consists
768: * of all records with a specific Name. A negative value is treated as an
769: * infinite limit.
770: *
771: * Note that setting this to a value lower than the current number
772: * of entries will not cause the Cache to shrink immediately.
773: *
774: * The default maximum number of entries is 50000.
775: *
776: * @param entries The maximum number of entries in the Cache.
777: */
778: public void setMaxEntries(int entries) {
779: data.setMaxSize(entries);
780: }
781:
782: /**
783: * Returns the DNS class of this cache.
784: */
785: public int getDClass() {
786: return dclass;
787: }
788:
789: /**
790: * Returns the contents of the Cache as a string.
791: */
792: public String toString() {
793: StringBuffer sb = new StringBuffer();
794: synchronized (this ) {
795: Iterator it = data.values().iterator();
796: while (it.hasNext()) {
797: Element[] elements = allElements(it.next());
798: for (int i = 0; i < elements.length; i++) {
799: sb.append(elements[i]);
800: sb.append("\n");
801: }
802: }
803: }
804: return sb.toString();
805: }
806:
807: }
|