dname.c revision 307729 
1/*
2 * util/data/dname.h - domain name handling
3 *
4 * Copyright (c) 2007, NLnet Labs. All rights reserved.
5 *
6 * This software is open source.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 *
12 * Redistributions of source code must retain the above copyright notice,
13 * this list of conditions and the following disclaimer.
14 *
15 * Redistributions in binary form must reproduce the above copyright notice,
16 * this list of conditions and the following disclaimer in the documentation
17 * and/or other materials provided with the distribution.
18 *
19 * Neither the name of the NLNET LABS nor the names of its contributors may
20 * be used to endorse or promote products derived from this software without
21 * specific prior written permission.
22 *
23 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
26 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
27 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
28 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
29 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
30 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
31 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
32 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
33 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34 */
35
36/**
37 * \file
38 *
39 * This file contains domain name handling functions.
40 */
41
42#include "config.h"
43#include <ctype.h>
44#include "util/data/dname.h"
45#include "util/data/msgparse.h"
46#include "util/log.h"
47#include "util/storage/lookup3.h"
48#include "sldns/sbuffer.h"
49
50/* determine length of a dname in buffer, no compression pointers allowed */
51size_t
52query_dname_len(sldns_buffer* query)
53{
54	size_t len = 0;
55	size_t labellen;
56	while(1) {
57		if(sldns_buffer_remaining(query) < 1)
58			return 0; /* parse error, need label len */
59		labellen = sldns_buffer_read_u8(query);
60		if(labellen&0xc0)
61			return 0; /* no compression allowed in queries */
62		len += labellen + 1;
63		if(len > LDNS_MAX_DOMAINLEN)
64			return 0; /* too long */
65		if(labellen == 0)
66			return len;
67		if(sldns_buffer_remaining(query) < labellen)
68			return 0; /* parse error, need content */
69		sldns_buffer_skip(query, (ssize_t)labellen);
70	}
71}
72
73size_t
74dname_valid(uint8_t* dname, size_t maxlen)
75{
76	size_t len = 0;
77	size_t labellen;
78	labellen = *dname++;
79	while(labellen) {
80		if(labellen&0xc0)
81			return 0; /* no compression ptrs allowed */
82		len += labellen + 1;
83		if(len >= LDNS_MAX_DOMAINLEN)
84			return 0; /* too long */
85		if(len > maxlen)
86			return 0; /* does not fit in memory allocation */
87		dname += labellen;
88		labellen = *dname++;
89	}
90	len += 1;
91	if(len > maxlen)
92		return 0; /* does not fit in memory allocation */
93	return len;
94}
95
96/** compare uncompressed, noncanonical, registers are hints for speed */
97int
98query_dname_compare(register uint8_t* d1, register uint8_t* d2)
99{
100	register uint8_t lab1, lab2;
101	log_assert(d1 && d2);
102	lab1 = *d1++;
103	lab2 = *d2++;
104	while( lab1 != 0 || lab2 != 0 ) {
105		/* compare label length */
106		/* if one dname ends, it has labellength 0 */
107		if(lab1 != lab2) {
108			if(lab1 < lab2)
109				return -1;
110			return 1;
111		}
112		log_assert(lab1 == lab2 && lab1 != 0);
113		/* compare lowercased labels. */
114		while(lab1--) {
115			/* compare bytes first for speed */
116			if(*d1 != *d2 &&
117				tolower((unsigned char)*d1) != tolower((unsigned char)*d2)) {
118				if(tolower((unsigned char)*d1) < tolower((unsigned char)*d2))
119					return -1;
120				return 1;
121			}
122			d1++;
123			d2++;
124		}
125		/* next pair of labels. */
126		lab1 = *d1++;
127		lab2 = *d2++;
128	}
129	return 0;
130}
131
132void
133query_dname_tolower(uint8_t* dname)
134{
135	/* the dname is stored uncompressed */
136	uint8_t labellen;
137	labellen = *dname;
138	while(labellen) {
139		dname++;
140		while(labellen--) {
141			*dname = (uint8_t)tolower((unsigned char)*dname);
142			dname++;
143		}
144		labellen = *dname;
145	}
146}
147
148void
149pkt_dname_tolower(sldns_buffer* pkt, uint8_t* dname)
150{
151	uint8_t lablen;
152	int count = 0;
153	if(dname >= sldns_buffer_end(pkt))
154		return;
155	lablen = *dname++;
156	while(lablen) {
157		if(LABEL_IS_PTR(lablen)) {
158			if((size_t)PTR_OFFSET(lablen, *dname)
159				>= sldns_buffer_limit(pkt))
160				return;
161			dname = sldns_buffer_at(pkt, PTR_OFFSET(lablen, *dname));
162			lablen = *dname++;
163			if(count++ > MAX_COMPRESS_PTRS)
164				return;
165			continue;
166		}
167		if(dname+lablen >= sldns_buffer_end(pkt))
168			return;
169		while(lablen--) {
170			*dname = (uint8_t)tolower((unsigned char)*dname);
171			dname++;
172		}
173		if(dname >= sldns_buffer_end(pkt))
174			return;
175		lablen = *dname++;
176	}
177}
178
179
180size_t
181pkt_dname_len(sldns_buffer* pkt)
182{
183	size_t len = 0;
184	int ptrcount = 0;
185	uint8_t labellen;
186	size_t endpos = 0;
187
188	/* read dname and determine length */
189	/* check compression pointers, loops, out of bounds */
190	while(1) {
191		/* read next label */
192		if(sldns_buffer_remaining(pkt) < 1)
193			return 0;
194		labellen = sldns_buffer_read_u8(pkt);
195		if(LABEL_IS_PTR(labellen)) {
196			/* compression ptr */
197			uint16_t ptr;
198			if(sldns_buffer_remaining(pkt) < 1)
199				return 0;
200			ptr = PTR_OFFSET(labellen, sldns_buffer_read_u8(pkt));
201			if(ptrcount++ > MAX_COMPRESS_PTRS)
202				return 0; /* loop! */
203			if(sldns_buffer_limit(pkt) <= ptr)
204				return 0; /* out of bounds! */
205			if(!endpos)
206				endpos = sldns_buffer_position(pkt);
207			sldns_buffer_set_position(pkt, ptr);
208		} else {
209			/* label contents */
210			if(labellen > 0x3f)
211				return 0; /* label too long */
212			len += 1 + labellen;
213			if(len > LDNS_MAX_DOMAINLEN)
214				return 0;
215			if(labellen == 0) {
216				/* end of dname */
217				break;
218			}
219			if(sldns_buffer_remaining(pkt) < labellen)
220				return 0;
221			sldns_buffer_skip(pkt, (ssize_t)labellen);
222		}
223	}
224	if(endpos)
225		sldns_buffer_set_position(pkt, endpos);
226
227	return len;
228}
229
230int
231dname_pkt_compare(sldns_buffer* pkt, uint8_t* d1, uint8_t* d2)
232{
233	uint8_t len1, len2;
234	log_assert(pkt && d1 && d2);
235	len1 = *d1++;
236	len2 = *d2++;
237	while( len1 != 0 || len2 != 0 ) {
238		/* resolve ptrs */
239		if(LABEL_IS_PTR(len1)) {
240			d1 = sldns_buffer_at(pkt, PTR_OFFSET(len1, *d1));
241			len1 = *d1++;
242			continue;
243		}
244		if(LABEL_IS_PTR(len2)) {
245			d2 = sldns_buffer_at(pkt, PTR_OFFSET(len2, *d2));
246			len2 = *d2++;
247			continue;
248		}
249		/* check label length */
250		log_assert(len1 <= LDNS_MAX_LABELLEN);
251		log_assert(len2 <= LDNS_MAX_LABELLEN);
252		if(len1 != len2) {
253			if(len1 < len2) return -1;
254			return 1;
255		}
256		log_assert(len1 == len2 && len1 != 0);
257		/* compare labels */
258		while(len1--) {
259			if(tolower((unsigned char)*d1) != tolower((unsigned char)*d2)) {
260				if(tolower((unsigned char)*d1) < tolower((unsigned char)*d2))
261					return -1;
262				return 1;
263			}
264			d1++;
265			d2++;
266		}
267		len1 = *d1++;
268		len2 = *d2++;
269	}
270	return 0;
271}
272
273hashvalue_t
274dname_query_hash(uint8_t* dname, hashvalue_t h)
275{
276	uint8_t labuf[LDNS_MAX_LABELLEN+1];
277	uint8_t lablen;
278	int i;
279
280	/* preserve case of query, make hash label by label */
281	lablen = *dname++;
282	while(lablen) {
283		log_assert(lablen <= LDNS_MAX_LABELLEN);
284		labuf[0] = lablen;
285		i=0;
286		while(lablen--) {
287			labuf[++i] = (uint8_t)tolower((unsigned char)*dname);
288			dname++;
289		}
290		h = hashlittle(labuf, labuf[0] + 1, h);
291		lablen = *dname++;
292	}
293
294	return h;
295}
296
297hashvalue_t
298dname_pkt_hash(sldns_buffer* pkt, uint8_t* dname, hashvalue_t h)
299{
300	uint8_t labuf[LDNS_MAX_LABELLEN+1];
301	uint8_t lablen;
302	int i;
303
304	/* preserve case of query, make hash label by label */
305	lablen = *dname++;
306	while(lablen) {
307		if(LABEL_IS_PTR(lablen)) {
308			/* follow pointer */
309			dname = sldns_buffer_at(pkt, PTR_OFFSET(lablen, *dname));
310			lablen = *dname++;
311			continue;
312		}
313		log_assert(lablen <= LDNS_MAX_LABELLEN);
314		labuf[0] = lablen;
315		i=0;
316		while(lablen--) {
317			labuf[++i] = (uint8_t)tolower((unsigned char)*dname);
318			dname++;
319		}
320		h = hashlittle(labuf, labuf[0] + 1, h);
321		lablen = *dname++;
322	}
323
324	return h;
325}
326
327void dname_pkt_copy(sldns_buffer* pkt, uint8_t* to, uint8_t* dname)
328{
329	/* copy over the dname and decompress it at the same time */
330	size_t len = 0;
331	uint8_t lablen;
332	lablen = *dname++;
333	while(lablen) {
334		if(LABEL_IS_PTR(lablen)) {
335			/* follow pointer */
336			dname = sldns_buffer_at(pkt, PTR_OFFSET(lablen, *dname));
337			lablen = *dname++;
338			continue;
339		}
340		log_assert(lablen <= LDNS_MAX_LABELLEN);
341		len += (size_t)lablen+1;
342		if(len >= LDNS_MAX_DOMAINLEN) {
343			*to = 0; /* end the result prematurely */
344			log_err("bad dname in dname_pkt_copy");
345			return;
346		}
347		*to++ = lablen;
348		memmove(to, dname, lablen);
349		dname += lablen;
350		to += lablen;
351		lablen = *dname++;
352	}
353	/* copy last \0 */
354	*to = 0;
355}
356
357void dname_print(FILE* out, struct sldns_buffer* pkt, uint8_t* dname)
358{
359	uint8_t lablen;
360	if(!out) out = stdout;
361	if(!dname) return;
362
363	lablen = *dname++;
364	if(!lablen)
365		fputc('.', out);
366	while(lablen) {
367		if(LABEL_IS_PTR(lablen)) {
368			/* follow pointer */
369			if(!pkt) {
370				fputs("??compressionptr??", out);
371				return;
372			}
373			dname = sldns_buffer_at(pkt, PTR_OFFSET(lablen, *dname));
374			lablen = *dname++;
375			continue;
376		}
377		if(lablen > LDNS_MAX_LABELLEN) {
378			fputs("??extendedlabel??", out);
379			return;
380		}
381		while(lablen--)
382			fputc((int)*dname++, out);
383		fputc('.', out);
384		lablen = *dname++;
385	}
386}
387
388int
389dname_count_labels(uint8_t* dname)
390{
391	uint8_t lablen;
392	int labs = 1;
393
394	lablen = *dname++;
395	while(lablen) {
396		labs++;
397		dname += lablen;
398		lablen = *dname++;
399	}
400	return labs;
401}
402
403int
404dname_count_size_labels(uint8_t* dname, size_t* size)
405{
406	uint8_t lablen;
407	int labs = 1;
408	size_t sz = 1;
409
410	lablen = *dname++;
411	while(lablen) {
412		labs++;
413		sz += lablen+1;
414		dname += lablen;
415		lablen = *dname++;
416	}
417	*size = sz;
418	return labs;
419}
420
421/**
422 * Compare labels in memory, lowercase while comparing.
423 * @param p1: label 1
424 * @param p2: label 2
425 * @param len: number of bytes to compare.
426 * @return: 0, -1, +1 comparison result.
427 */
428static int
429memlowercmp(uint8_t* p1, uint8_t* p2, uint8_t len)
430{
431	while(len--) {
432		if(*p1 != *p2 && tolower((unsigned char)*p1) != tolower((unsigned char)*p2)) {
433			if(tolower((unsigned char)*p1) < tolower((unsigned char)*p2))
434				return -1;
435			return 1;
436		}
437		p1++;
438		p2++;
439	}
440	return 0;
441}
442
443int
444dname_lab_cmp(uint8_t* d1, int labs1, uint8_t* d2, int labs2, int* mlabs)
445{
446	uint8_t len1, len2;
447	int atlabel = labs1;
448	int lastmlabs;
449	int lastdiff = 0;
450	/* first skip so that we compare same label. */
451	if(labs1 > labs2) {
452		while(atlabel > labs2) {
453			len1 = *d1++;
454			d1 += len1;
455			atlabel--;
456		}
457		log_assert(atlabel == labs2);
458	} else if(labs1 < labs2) {
459		atlabel = labs2;
460		while(atlabel > labs1) {
461			len2 = *d2++;
462			d2 += len2;
463			atlabel--;
464		}
465		log_assert(atlabel == labs1);
466	}
467	lastmlabs = atlabel+1;
468	/* now at same label in d1 and d2, atlabel */
469	/* www.example.com.                  */
470	/* 4   3       2  1   atlabel number */
471	/* repeat until at root label (which is always the same) */
472	while(atlabel > 1) {
473		len1 = *d1++;
474		len2 = *d2++;
475		if(len1 != len2) {
476			log_assert(len1 != 0 && len2 != 0);
477			if(len1<len2)
478				lastdiff = -1;
479			else	lastdiff = 1;
480			lastmlabs = atlabel;
481			d1 += len1;
482			d2 += len2;
483		} else {
484			/* memlowercmp is inlined here; or just like
485			 * if((c=memlowercmp(d1, d2, len1)) != 0) {
486			 *	lastdiff = c;
487			 *	lastmlabs = atlabel; } apart from d1++,d2++ */
488			while(len1) {
489				if(*d1 != *d2 && tolower((unsigned char)*d1)
490					!= tolower((unsigned char)*d2)) {
491					if(tolower((unsigned char)*d1) <
492						tolower((unsigned char)*d2)) {
493						lastdiff = -1;
494						lastmlabs = atlabel;
495						d1 += len1;
496						d2 += len1;
497						break;
498					}
499					lastdiff = 1;
500					lastmlabs = atlabel;
501					d1 += len1;
502					d2 += len1;
503					break; /* out of memlowercmp */
504				}
505				d1++;
506				d2++;
507				len1--;
508			}
509		}
510		atlabel--;
511	}
512	/* last difference atlabel number, so number of labels matching,
513	 * at the right side, is one less. */
514	*mlabs = lastmlabs-1;
515	if(lastdiff == 0) {
516		/* all labels compared were equal, check if one has more
517		 * labels, so that example.com. > com. */
518		if(labs1 > labs2)
519			return 1;
520		else if(labs1 < labs2)
521			return -1;
522	}
523	return lastdiff;
524}
525
526int
527dname_buffer_write(sldns_buffer* pkt, uint8_t* dname)
528{
529	uint8_t lablen;
530
531	if(sldns_buffer_remaining(pkt) < 1)
532		return 0;
533	lablen = *dname++;
534	sldns_buffer_write_u8(pkt, lablen);
535	while(lablen) {
536		if(sldns_buffer_remaining(pkt) < (size_t)lablen+1)
537			return 0;
538		sldns_buffer_write(pkt, dname, lablen);
539		dname += lablen;
540		lablen = *dname++;
541		sldns_buffer_write_u8(pkt, lablen);
542	}
543	return 1;
544}
545
546void dname_str(uint8_t* dname, char* str)
547{
548	size_t len = 0;
549	uint8_t lablen = 0;
550	char* s = str;
551	if(!dname || !*dname) {
552		*s++ = '.';
553		*s = 0;
554		return;
555	}
556	lablen = *dname++;
557	while(lablen) {
558		if(lablen > LDNS_MAX_LABELLEN) {
559			*s++ = '#';
560			*s = 0;
561			return;
562		}
563		len += lablen+1;
564		if(len >= LDNS_MAX_DOMAINLEN-1) {
565			*s++ = '&';
566			*s = 0;
567			return;
568		}
569		while(lablen--) {
570			if(isalnum((unsigned char)*dname)
571				|| *dname == '-' || *dname == '_'
572				|| *dname == '*')
573				*s++ = *(char*)dname++;
574			else	{
575				*s++ = '?';
576				dname++;
577			}
578		}
579		*s++ = '.';
580		lablen = *dname++;
581	}
582	*s = 0;
583}
584
585int
586dname_strict_subdomain(uint8_t* d1, int labs1, uint8_t* d2, int labs2)
587{
588	int m;
589	/* check subdomain: d1: www.example.com. and d2: example.com. */
590	if(labs2 >= labs1)
591		return 0;
592	if(dname_lab_cmp(d1, labs1, d2, labs2, &m) > 0) {
593		/* subdomain if all labels match */
594		return (m == labs2);
595	}
596	return 0;
597}
598
599int
600dname_strict_subdomain_c(uint8_t* d1, uint8_t* d2)
601{
602	return dname_strict_subdomain(d1, dname_count_labels(d1), d2,
603		dname_count_labels(d2));
604}
605
606int
607dname_subdomain_c(uint8_t* d1, uint8_t* d2)
608{
609	int m;
610	/* check subdomain: d1: www.example.com. and d2: example.com. */
611	/*  	or 	    d1: example.com. and d2: example.com. */
612	int labs1 = dname_count_labels(d1);
613	int labs2 = dname_count_labels(d2);
614	if(labs2 > labs1)
615		return 0;
616	if(dname_lab_cmp(d1, labs1, d2, labs2, &m) < 0) {
617		/* must have been example.com , www.example.com - wrong */
618		/* or otherwise different dnames */
619		return 0;
620	}
621	return (m == labs2);
622}
623
624int
625dname_is_root(uint8_t* dname)
626{
627	uint8_t len;
628	log_assert(dname);
629	len = dname[0];
630	log_assert(!LABEL_IS_PTR(len));
631	return (len == 0);
632}
633
634void
635dname_remove_label(uint8_t** dname, size_t* len)
636{
637	size_t lablen;
638	log_assert(dname && *dname && len);
639	lablen = (*dname)[0];
640	log_assert(!LABEL_IS_PTR(lablen));
641	log_assert(*len > lablen);
642	if(lablen == 0)
643		return; /* do not modify root label */
644	*len -= lablen+1;
645	*dname += lablen+1;
646}
647
648void
649dname_remove_labels(uint8_t** dname, size_t* len, int n)
650{
651	int i;
652	for(i=0; i<n; i++)
653		dname_remove_label(dname, len);
654}
655
656int
657dname_signame_label_count(uint8_t* dname)
658{
659	uint8_t lablen;
660	int count = 0;
661	if(!*dname)
662		return 0;
663	if(dname[0] == 1 && dname[1] == '*')
664		dname += 2;
665	lablen = dname[0];
666	while(lablen) {
667		count++;
668		dname += lablen;
669		dname += 1;
670		lablen = dname[0];
671	}
672	return count;
673}
674
675int
676dname_is_wild(uint8_t* dname)
677{
678	return (dname[0] == 1 && dname[1] == '*');
679}
680
681/**
682 * Compare labels in memory, lowercase while comparing.
683 * Returns canonical order for labels. If all is equal, the
684 * shortest is first.
685 *
686 * @param p1: label 1
687 * @param len1: length of label 1.
688 * @param p2: label 2
689 * @param len2: length of label 2.
690 * @return: 0, -1, +1 comparison result.
691 */
692static int
693memcanoncmp(uint8_t* p1, uint8_t len1, uint8_t* p2, uint8_t len2)
694{
695	uint8_t min = (len1<len2)?len1:len2;
696	int c = memlowercmp(p1, p2, min);
697	if(c != 0)
698		return c;
699	/* equal, see who is shortest */
700	if(len1 < len2)
701		return -1;
702	if(len1 > len2)
703		return 1;
704	return 0;
705}
706
707
708int
709dname_canon_lab_cmp(uint8_t* d1, int labs1, uint8_t* d2, int labs2, int* mlabs)
710{
711	/* like dname_lab_cmp, but with different label comparison,
712	 * empty character sorts before \000.
713	 * So   ylyly is before z. */
714	uint8_t len1, len2;
715	int atlabel = labs1;
716	int lastmlabs;
717	int lastdiff = 0;
718	int c;
719	/* first skip so that we compare same label. */
720	if(labs1 > labs2) {
721		while(atlabel > labs2) {
722			len1 = *d1++;
723			d1 += len1;
724			atlabel--;
725		}
726		log_assert(atlabel == labs2);
727	} else if(labs1 < labs2) {
728		atlabel = labs2;
729		while(atlabel > labs1) {
730			len2 = *d2++;
731			d2 += len2;
732			atlabel--;
733		}
734		log_assert(atlabel == labs1);
735	}
736	lastmlabs = atlabel+1;
737	/* now at same label in d1 and d2, atlabel */
738	/* www.example.com.                  */
739	/* 4   3       2  1   atlabel number */
740	/* repeat until at root label (which is always the same) */
741	while(atlabel > 1) {
742		len1 = *d1++;
743		len2 = *d2++;
744
745		if((c=memcanoncmp(d1, len1, d2, len2)) != 0) {
746			if(c<0)
747				lastdiff = -1;
748			else	lastdiff = 1;
749			lastmlabs = atlabel;
750		}
751
752		d1 += len1;
753		d2 += len2;
754		atlabel--;
755	}
756	/* last difference atlabel number, so number of labels matching,
757	 * at the right side, is one less. */
758	*mlabs = lastmlabs-1;
759	if(lastdiff == 0) {
760		/* all labels compared were equal, check if one has more
761		 * labels, so that example.com. > com. */
762		if(labs1 > labs2)
763			return 1;
764		else if(labs1 < labs2)
765			return -1;
766	}
767	return lastdiff;
768}
769
770int
771dname_canonical_compare(uint8_t* d1, uint8_t* d2)
772{
773	int labs1, labs2, m;
774	labs1 = dname_count_labels(d1);
775	labs2 = dname_count_labels(d2);
776	return dname_canon_lab_cmp(d1, labs1, d2, labs2, &m);
777}
778
779uint8_t* dname_get_shared_topdomain(uint8_t* d1, uint8_t* d2)
780{
781	int labs1, labs2, m;
782	size_t len = LDNS_MAX_DOMAINLEN;
783	labs1 = dname_count_labels(d1);
784	labs2 = dname_count_labels(d2);
785	(void)dname_lab_cmp(d1, labs1, d2, labs2, &m);
786	dname_remove_labels(&d1, &len, labs1-m);
787	return d1;
788}
789