From f48553bc2deef7be62ffb71cc1e951d2e0c29c6a Mon Sep 17 00:00:00 2001 From: Wouter Wijngaards Date: Wed, 25 Apr 2007 15:28:03 +0000 Subject: [PATCH] work on domain name compression. git-svn-id: file:///svn/unbound/trunk@257 be551aaa-1e26-0410-a405-d3ace91eadb9 --- Makefile.in | 10 +- doc/Changelog | 2 + testcode/pktview.c | 192 ++++++++++++++++++++++++++ testcode/readhex.c | 82 +++++++++++ testcode/readhex.h | 47 +++++++ testcode/unitmain.c | 9 ++ testcode/unitmsgparse.c | 66 ++++----- util/data/dname.c | 100 ++++++++++++++ util/data/dname.h | 19 +++ util/data/msgparse.c | 2 +- util/data/msgreply.c | 299 ++++++++++++++++++++++++++++++++++++++-- util/log.c | 2 +- 12 files changed, 771 insertions(+), 59 deletions(-) create mode 100644 testcode/pktview.c create mode 100644 testcode/readhex.c create mode 100644 testcode/readhex.h diff --git a/Makefile.in b/Makefile.in index 79ba56ca3..6a3208e45 100644 --- a/Makefile.in +++ b/Makefile.in @@ -53,7 +53,7 @@ INSTALL=$(srcdir)/install-sh COMMON_SRC=$(wildcard services/*.c util/*.c util/data/*.c util/storage/*.c) util/configparser.c util/configlexer.c testcode/checklocks.c COMMON_OBJ=$(addprefix $(BUILD),$(COMMON_SRC:.c=.o)) COMPAT_OBJ=$(addprefix $(BUILD)compat/,$(LIBOBJS)) -UNITTEST_SRC=$(wildcard testcode/unit*.c) $(COMMON_SRC) +UNITTEST_SRC=$(wildcard testcode/unit*.c) testcode/readhex.c $(COMMON_SRC) UNITTEST_OBJ=$(addprefix $(BUILD),$(UNITTEST_SRC:.c=.o)) $(COMPAT_OBJ) DAEMON_SRC=$(wildcard daemon/*.c) $(COMMON_SRC) DAEMON_OBJ=$(addprefix $(BUILD),$(DAEMON_SRC:.c=.o)) $(COMPAT_OBJ) @@ -61,6 +61,8 @@ TESTBOUND_SRC=testcode/testbound.c testcode/ldns-testpkts.c daemon/worker.c daem TESTBOUND_OBJ=$(addprefix $(BUILD),$(TESTBOUND_SRC:.c=.o)) $(COMPAT_OBJ) LOCKVERIFY_SRC=testcode/lock_verify.c $(COMMON_SRC) LOCKVERIFY_OBJ=$(addprefix $(BUILD),$(LOCKVERIFY_SRC:.c=.o)) $(COMPAT_OBJ) +PKTVIEW_SRC=testcode/pktview.c testcode/readhex.c $(COMMON_SRC) +PKTVIEW_OBJ=$(addprefix $(BUILD),$(PKTVIEW_SRC:.c=.o)) $(COMPAT_OBJ) ALL_SRC=$(COMMON_SRC) $(UNITTEST_SRC) $(DAEMON_SRC) $(TESTBOUND_SRC) $(LOCKVERIFY_SRC) ALL_OBJ=$(addprefix $(BUILD),$(ALL_SRC:.c=.o) $(addprefix compat/,$(LIBOBJS))) $(COMPAT_OBJ) @@ -75,7 +77,7 @@ $(BUILD)%.o: $(srcdir)/%.c .PHONY: clean realclean doc lint all -all: $(COMMON_OBJ) unbound unittest testbound lock-verify +all: $(COMMON_OBJ) unbound unittest testbound lock-verify pktview unbound: $(DAEMON_OBJ) $(INFO) Link $@ @@ -93,6 +95,10 @@ lock-verify: $(LOCKVERIFY_OBJ) $(INFO) Link $@ $Q$(LINK) -o $@ $^ $(LIBS) +pktview: $(PKTVIEW_OBJ) + $(INFO) Link $@ + $Q$(LINK) -o $@ $^ $(LIBS) + testcode/ldns-testpkts.c: $(ldnsdir)/examples/ldns-testpkts.c \ $(ldnsdir)/examples/ldns-testpkts.h cp $(ldnsdir)/examples/ldns-testpkts.c testcode/ldns-testpkts.c diff --git a/doc/Changelog b/doc/Changelog index c945cca40..612b48275 100644 --- a/doc/Changelog +++ b/doc/Changelog @@ -1,5 +1,7 @@ 25 April 2007: Wouter - prettier code; parse_rrset->type kept in host byte order. + - datatype used for hashvalue of converted rrsig structure. + - unit test compares edns section data too. 24 April 2007: Wouter - ttl per RR, for RRSIG rrsets and others. diff --git a/testcode/pktview.c b/testcode/pktview.c new file mode 100644 index 000000000..4c66ff2e3 --- /dev/null +++ b/testcode/pktview.c @@ -0,0 +1,192 @@ +/* + * testcode/pktview.c - debug program to disassemble a DNS packet. + * + * Copyright (c) 2007, NLnet Labs. All rights reserved. + * + * This software is open source. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * + * Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * + * Neither the name of the NLNET LABS nor the names of its contributors may + * be used to endorse or promote products derived from this software without + * specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED + * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +/** + * \file + * + * This program shows a dns packet wire format. + */ + +#include "config.h" +#include "util/log.h" +#include "util/data/dname.h" +#include "util/data/msgparse.h" +#include "testcode/unitmain.h" +#include "testcode/readhex.h" + +/** usage information for pktview */ +void usage(char* argv[]) +{ + printf("usage: %s\n", argv[0]); + printf("present hex packet on stdin.\n"); + exit(1); +} + +/** read hex input */ +void read_input(ldns_buffer* pkt, FILE* in) +{ + char buf[102400]; + char* np = buf; + while(fgets(np, (int)sizeof(buf) - (np-buf), in)) { + if(buf[0] == ';') /* comment */ + continue; + np = &np[strlen(np)]; + } + hex_to_buf(pkt, buf); +} + +/** analyze domain name in packet, possibly compressed. */ +void analyze_dname(ldns_buffer* pkt) +{ + size_t oldpos = ldns_buffer_position(pkt); + size_t len; + printf("[pos %d] dname: ", (int)oldpos); + dname_print(stdout, pkt, ldns_buffer_current(pkt)); + len = pkt_dname_len(pkt); + printf(" len=%d", (int)len); + if(ldns_buffer_position(pkt)-oldpos != len) + printf(" comprlen=%d\n", + (int)(ldns_buffer_position(pkt)-oldpos)); + else printf("\n"); +} + +/** analyze rdata in packet */ +void analyze_rdata(ldns_buffer*pkt, const ldns_rr_descriptor* desc, + uint16_t rdlen) +{ + int rdf = 0; + int count = (int)desc->_dname_count; + size_t len, oldpos; + while(rdlen > 0 && count) { + switch(desc->_wireformat[rdf]) { + case LDNS_RDF_TYPE_DNAME: + oldpos = ldns_buffer_position(pkt); + analyze_dname(pkt); + rdlen -= ldns_buffer_position(pkt)-oldpos; + count --; + len = 0; + break; + case LDNS_RDF_TYPE_STR: + len = ldns_buffer_current(pkt)[0] + 1; + break; + default: + len = get_rdf_size(desc->_wireformat[rdf]); + } + if(len) { + printf(" wf[%d]", (int)len); + ldns_buffer_skip(pkt, (ssize_t)len); + rdlen -= len; + } + rdf++; + } + if(rdlen) + printf(" remain[%d]\n", (int)rdlen); + else printf("\n"); + ldns_buffer_skip(pkt, (ssize_t)rdlen); +} + +/** analyze rr in packet. */ +void analyze_rr(ldns_buffer* pkt, int q) +{ + uint16_t type, dclass, len; + uint32_t ttl; + analyze_dname(pkt); + type = ldns_buffer_read_u16(pkt); + dclass = ldns_buffer_read_u16(pkt); + printf("type %s(%d)", ldns_rr_descript(type)? + ldns_rr_descript(type)->_name: "??" , (int)type); + printf(" class %s(%d) ", ldns_lookup_by_id(ldns_rr_classes, + (int)dclass)?ldns_lookup_by_id( ldns_rr_classes, + (int)dclass)->name:"??", (int)dclass); + if(q) { + printf("\n"); + } else { + ttl = ldns_buffer_read_u32(pkt); + printf(" ttl %d (0x%x)", ttl, ttl); + len = ldns_buffer_read_u16(pkt); + printf(" rdata len %d:\n", len); + if(ldns_rr_descript(type)) + analyze_rdata(pkt, ldns_rr_descript(type), len); + else ldns_buffer_skip(pkt, (ssize_t)len); + } +} + +/** analyse pkt */ +void analyze(ldns_buffer* pkt) +{ + uint16_t i, f, qd, an, ns, ar; + int rrnum = 0; + printf("packet length %d\n", (int)ldns_buffer_limit(pkt)); + if(ldns_buffer_limit(pkt) < 12) return; + + i = ldns_buffer_read_u16(pkt); + printf("id (hostorder): %d (0x%x)\n", i, i); + f = ldns_buffer_read_u16(pkt); + printf("flags: 0x%x\n", f); + qd = ldns_buffer_read_u16(pkt); + printf("qdcount: %d\n", qd); + an = ldns_buffer_read_u16(pkt); + printf("ancount: %d\n", an); + ns = ldns_buffer_read_u16(pkt); + printf("nscount: %d\n", ns); + ar = ldns_buffer_read_u16(pkt); + printf("arcount: %d\n", ar); + + printf(";-- query section\n"); + while(ldns_buffer_remaining(pkt) > 0) { + if(rrnum == qd) printf(";-- answer section\n"); + if(rrnum == qd+an) printf(";-- authority section\n"); + if(rrnum == qd+an+ns) printf(";-- additional section\n"); + printf("rr %d ", rrnum); + analyze_rr(pkt, rrnum < qd); + rrnum++; + } +} + +/** main program for pktview */ +int main(int argc, char* argv[]) +{ + ldns_buffer* pkt = ldns_buffer_new(65553); + if(argc != 1) { + usage(argv); + } + if(!pkt) fatal_exit("out of memory"); + + read_input(pkt, stdin); + analyze(pkt); + + ldns_buffer_free(pkt); + return 0; +} diff --git a/testcode/readhex.c b/testcode/readhex.c new file mode 100644 index 000000000..af9a77b8f --- /dev/null +++ b/testcode/readhex.c @@ -0,0 +1,82 @@ +/* + * testcode/readhex.c - read hex data. + * + * Copyright (c) 2007, NLnet Labs. All rights reserved. + * + * This software is open source. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * + * Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * + * Neither the name of the NLNET LABS nor the names of its contributors may + * be used to endorse or promote products derived from this software without + * specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED + * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + * + */ +/** + * \file + * Declarations useful for the unit tests. + */ +#include "config.h" +#include "testcode/readhex.h" +#include "util/log.h" + +/** skip whitespace */ +static void +skip_whites(const char** p) +{ + while(1) { + while(isspace(**p)) + (*p)++; + if(**p == ';') { + /* comment, skip until newline */ + while(**p && **p != '\n') + (*p)++; + if(**p == '\n') + (*p)++; + } else return; + } +} + +/** takes a hex string and puts into buffer */ +void hex_to_buf(ldns_buffer* pkt, const char* hex) +{ + const char* p = hex; + int val; + ldns_buffer_clear(pkt); + while(*p) { + skip_whites(&p); + if(ldns_buffer_position(pkt) == ldns_buffer_limit(pkt)) + fatal_exit("hex_to_buf: buffer too small"); + if(!isalnum(*p)) + break; + val = ldns_hexdigit_to_int(*p++) << 4; + skip_whites(&p); + log_assert(*p && isalnum(*p)); + val |= ldns_hexdigit_to_int(*p++); + ldns_buffer_write_u8(pkt, (uint8_t)val); + skip_whites(&p); + } + ldns_buffer_flip(pkt); +} + diff --git a/testcode/readhex.h b/testcode/readhex.h new file mode 100644 index 000000000..599bc4e6f --- /dev/null +++ b/testcode/readhex.h @@ -0,0 +1,47 @@ +/* + * testcode/readhex.h - read hex data. + * + * Copyright (c) 2007, NLnet Labs. All rights reserved. + * + * This software is open source. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * + * Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * + * Neither the name of the NLNET LABS nor the names of its contributors may + * be used to endorse or promote products derived from this software without + * specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED + * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + * + */ +/** + * \file + * Declarations useful for the unit tests. + */ + +#ifndef TESTCODE_READHEX_H +#define TESTCODE_READHEX_H + +/** helper to convert hex string to packet buffer */ +void hex_to_buf(ldns_buffer* pkt, const char* hex); + +#endif /* TESTCODE_READHEX_H */ diff --git a/testcode/unitmain.c b/testcode/unitmain.c index 68c3af23f..e6a85ede3 100644 --- a/testcode/unitmain.c +++ b/testcode/unitmain.c @@ -192,6 +192,13 @@ msgreply_test() unit_assert(query_dname_compare((uint8_t*)"\003abc\001Z", (uint8_t*)"\003abc\001a") == 1); + unit_assert(dname_count_labels((uint8_t*)"") == 1); + unit_assert(dname_count_labels((uint8_t*)"\003com") == 2); + unit_assert(dname_count_labels((uint8_t*)"\003org") == 2); + unit_assert(dname_count_labels((uint8_t*)"\007example\003com") == 3); + unit_assert(dname_count_labels((uint8_t*)"\003bla\007example\003com") + == 4); + ldns_buffer_free(buff); } @@ -211,11 +218,13 @@ main(int argc, char* argv[]) } printf("Start of %s unit test.\n", PACKAGE_STRING); checklock_start(); + if(0) { net_test(); alloc_test(); msgreply_test(); lruhash_test(); slabhash_test(); + } msgparse_test(); checklock_stop(); printf("%d checks ok.\n", testcount); diff --git a/testcode/unitmsgparse.c b/testcode/unitmsgparse.c index 69a80b845..e5925786f 100644 --- a/testcode/unitmsgparse.c +++ b/testcode/unitmsgparse.c @@ -47,52 +47,11 @@ #include "util/alloc.h" #include "util/region-allocator.h" #include "util/net_help.h" +#include "testcode/readhex.h" /** verbose message parse unit test */ static int vbmp = 0; -/** skip whitespace */ -static void -skip_whites(const char** p) -{ - while(1) { - while(isspace(**p)) - (*p)++; - if(**p == ';') { - /* comment, skip until newline */ - while(**p && **p != '\n') - (*p)++; - if(**p == '\n') - (*p)++; - } else return; - } -} - -/** takes a hex string and puts into buffer */ -static void hex_to_buf(ldns_buffer* pkt, const char* hex) -{ - const char* p = hex; - int val; - ldns_buffer_clear(pkt); - while(*p) { - skip_whites(&p); - if(ldns_buffer_position(pkt) == ldns_buffer_limit(pkt)) - fatal_exit("hex_to_buf: buffer too small"); - if(!isalnum(*p)) - break; - val = ldns_hexdigit_to_int(*p++) << 4; - skip_whites(&p); - log_assert(*p && isalnum(*p)); - val |= ldns_hexdigit_to_int(*p++); - ldns_buffer_write_u8(pkt, (uint8_t)val); - skip_whites(&p); - } - ldns_buffer_flip(pkt); - if(vbmp) { - printf("packet size %u\n", (unsigned)ldns_buffer_limit(pkt)); - } -} - /** match two rr lists */ static int match_list(ldns_rr_list* q, ldns_rr_list *p) @@ -122,6 +81,25 @@ match_list(ldns_rr_list* q, ldns_rr_list *p) return 1; } +/** match edns sections */ +static int +match_edns(ldns_pkt* q, ldns_pkt* p) +{ + if(ldns_pkt_edns_udp_size(q) != ldns_pkt_edns_udp_size(p)) + return 0; + if(ldns_pkt_edns_extended_rcode(q) != ldns_pkt_edns_extended_rcode(p)) + return 0; + if(ldns_pkt_edns_version(q) != ldns_pkt_edns_version(p)) + return 0; + if(ldns_pkt_edns_do(q) != ldns_pkt_edns_do(p)) + return 0; + if(ldns_pkt_edns_z(q) != ldns_pkt_edns_z(p)) + return 0; + if(ldns_rdf_compare(ldns_pkt_edns_data(q), ldns_pkt_edns_data(p)) != 0) + return 0; + return 1; +} + /** compare two booleans */ static int cmp_bool(int x, int y) @@ -172,6 +150,8 @@ match_all(ldns_pkt* q, ldns_pkt* p) { verbose(3, "allmatch: ns section different"); return 0;} if(!match_list(ldns_pkt_additional(q), ldns_pkt_additional(p))) { verbose(3, "allmatch: ar section different"); return 0;} + if(!match_edns(q, p)) + { verbose(3, "edns different."); return 0;} return 1; } @@ -388,7 +368,7 @@ testfromdrillfile(ldns_buffer* pkt, struct alloc_cache* alloc, /* ;-- is used to indicate a new message */ FILE* in = fopen(fname, "r"); char buf[102400]; - char *np = buf; + char* np = buf; if(!in) { perror("fname"); return; diff --git a/util/data/dname.c b/util/data/dname.c index 4b36730b0..32c644fde 100644 --- a/util/data/dname.c +++ b/util/data/dname.c @@ -333,3 +333,103 @@ void dname_print(FILE* out, ldns_buffer* pkt, uint8_t* dname) lablen = *dname++; } } + +int +dname_count_labels(uint8_t* dname) +{ + uint8_t lablen; + int labs = 1; + + lablen = *dname++; + while(lablen) { + labs++; + dname += lablen; + lablen = *dname++; + } + return labs; +} + +/** + * Compare labels in memory, lowercase while comparing. + * @param p1: label 1 + * @param p2: label 2 + * @param len: number of bytes to compare. + * @return: 0, -1, +1 comparison result. + */ +static int +memlowercmp(uint8_t* p1, uint8_t* p2, uint8_t len) +{ + while(len--) { + if(tolower((int)*p1++) != tolower((int)*p2++)) { + if(tolower((int)p1[-1]) < tolower((int)p2[-1])) + return -1; + return 1; + } + } + return 0; +} + + +int +dname_lab_cmp(uint8_t* d1, int labs1, uint8_t* d2, int labs2, int* mlabs) +{ + uint8_t len1, len2; + int atlabel = labs1; + int lastmlabs; + int lastdiff = 0; + int c; + /* first skip so that we compare same label. */ + if(labs1 > labs2) { + while(atlabel > labs2) { + len1 = *d1++; + d1 += len1; + atlabel--; + } + log_assert(atlabel == labs2); + } else if(labs1 < labs2) { + atlabel = labs2; + while(atlabel > labs1) { + len2 = *d2++; + d2 += len2; + atlabel--; + } + log_assert(atlabel == labs1); + } + lastmlabs = atlabel+1; + /* now at same label in d1 and d2, atlabel */ + /* www.example.com. */ + /* 4 3 2 1 atlabel number */ + /* repeat until at root label (which is always the same) */ + while(atlabel > 1) { + len1 = *d1++; + len2 = *d2++; + if(len1 != len2) { + log_assert(len1 != 0 && len2 != 0); + if(len1 com. */ + if(labs1 > labs2) + return 1; + else if(labs1 < labs2) + return -1; + } + return lastdiff; +} diff --git a/util/data/dname.h b/util/data/dname.h index 9633ce312..1a1a60d6d 100644 --- a/util/data/dname.h +++ b/util/data/dname.h @@ -126,4 +126,23 @@ void dname_pkt_copy(ldns_buffer* pkt, uint8_t* to, uint8_t* dname); */ void dname_print(FILE* out, ldns_buffer* pkt, uint8_t* dname); +/** + * Count the number of labels in an uncompressed dname in memory. + * @param dname: pointer to uncompressed dname. + * @return: count of labels, including root label, "com." has 2 labels. + */ +int dname_count_labels(uint8_t* dname); + +/** + * Compare dnames, sorted not canonical, but by label. + * Such that zone contents follows zone apex. + * @param d1: first dname. pointer to uncompressed wireformat. + * @param labs1: number of labels in first dname. + * @param d2: second dname. pointer to uncompressed wireformat. + * @param labs2: number of labels in second dname. + * @param mlabs: number of labels that matched exactly. + * @return: 0 for equal, -1 smaller, or +1 d1 larger than d2. + */ +int dname_lab_cmp(uint8_t* d1, int labs1, uint8_t* d2, int labs2, int* mlabs); + #endif /* UTIL_DATA_DNAME_H */ diff --git a/util/data/msgparse.c b/util/data/msgparse.c index 0b6a674c5..8154d9f7e 100644 --- a/util/data/msgparse.c +++ b/util/data/msgparse.c @@ -354,7 +354,7 @@ change_rrsig_rrset(struct rrset_parse* sigset, struct msg_parse* msg, int hasother, ldns_pkt_section section, region_type* region) { struct rrset_parse* dataset = sigset; - hashvalue_t hash = pkt_hash_rrset(pkt, sigset->dname, sigset->type, + hashvalue_t hash = pkt_hash_rrset(pkt, sigset->dname, datatype, sigset->rrset_class, rrset_flags); log_assert( sigset->type == LDNS_RR_TYPE_RRSIG ); log_assert( datatype != LDNS_RR_TYPE_RRSIG ); diff --git a/util/data/msgreply.c b/util/data/msgreply.c index ece8093a3..a8b9dbc1f 100644 --- a/util/data/msgreply.c +++ b/util/data/msgreply.c @@ -486,15 +486,209 @@ reply_info_answer(struct reply_info* rep, uint16_t qflags, ldns_buffer_flip(buffer); } +/** + * Data structure to help domain name compression in outgoing messages. + * A tree of dnames and their offsets in the packet is kept. + * It is kept sorted, not canonical, but by label at least, so that after + * a lookup of a name you know its closest match, and the parent from that + * closest match. These are possible compression targets. + * + * It is a binary tree, not a rbtree or balanced tree, as the effort + * of keeping it balanced probably outweighs usefulness (given typical + * DNS packet size). + */ +struct compress_tree_node { + /** left node in tree, all smaller to this */ + struct compress_tree_node* left; + /** right node in tree, all larger than this */ + struct compress_tree_node* right; + + /** the parent node - not for tree, but zone parent. One less label */ + struct compress_tree_node* parent; + /** the domain name for this node. Pointer to uncompressed memory. */ + uint8_t* dname; + /** number of labels in domain name, kept to help compare func. */ + int labs; + /** offset in packet that points to this dname */ + size_t offset; +}; + +/** + * Find domain name in tree, returns exact and closest match. + * @param tree: root of tree. + * @param dname: pointer to uncompressed dname. + * @param labs: number of labels in domain name. + * @param match: closest or exact match. + * guaranteed to be smaller or equal to the sought dname. + * can be null if the tree is empty. + * @param matchlabels: number of labels that match with closest match. + * can be zero is there is no match. + * @return: 0 if no exact match. + */ +static int +compress_tree_search(struct compress_tree_node* tree, uint8_t* dname, + int labs, struct compress_tree_node** match, int* matchlabels) +{ + int c, n, closen=0; + struct compress_tree_node* p = tree; + struct compress_tree_node* close = 0; + while(p) { + if((c = dname_lab_cmp(dname, labs, p->dname, p->labs, &n)) + == 0) { + *matchlabels = n; + *match = p; + return 1; + } + if(c<0) p = p->left; + else { + closen = n; + close = p; /* p->dname is smaller than dname */ + p = p->right; + } + } + *matchlabels = closen; + *match = close; + return 0; +} + +/** + * Lookup a domain name in compression tree. + * @param tree: root of tree (not the node with '.'). + * @param dname: pointer to uncompressed dname. + * @param labs: number of labels in domain name. + * @return: 0 if not found or compress treenode with best compression. + */ +static struct compress_tree_node* +compress_tree_lookup(struct compress_tree_node* tree, uint8_t* dname, + int labs) +{ + struct compress_tree_node* p; + int m; + if(labs <= 1) + return 0; /* do not compress root node */ + if(compress_tree_search(tree, dname, labs, &p, &m)) { + /* exact match */ + return p; + } + /* return some ancestor of p that compresses well. */ + if(m>1) { + /* www.example.com. (labs=4) matched foo.example.com.(labs=4) + * then matchcount = 3. need to go up. */ + while(p && p->labs > m) + p = p->parent; + return p; + } + return 0; +} + +/** + * Insert node into domain name compression tree. + * @param tree: root of tree (may be modified) + * @param dname: pointer to uncompressed dname (stored in tree). + * @param labs: number of labels in dname. + * @param offset: offset into packet for dname. + * @param region: how to allocate memory for new node. + * @return new node or 0 on malloc failure. + */ +static struct compress_tree_node* +compress_tree_insert(struct compress_tree_node** tree, uint8_t* dname, + int labs, size_t offset, region_type* region) +{ + int c, m; + struct compress_tree_node* p, **prev; + struct compress_tree_node* n = (struct compress_tree_node*) + region_alloc(region, sizeof(struct compress_tree_node)); + if(!n) return 0; + n->left = 0; + n->right = 0; + n->parent = 0; + n->dname = dname; + n->labs = labs; + n->offset = offset; + + /* find spot to insert it into */ + prev = tree; + p = *tree; + while(p) { + c = dname_lab_cmp(dname, labs, p->dname, p->labs, &m); + log_assert(c != 0); /* may not already be in tree */ + if(c==0) return p; + if(c<0) { + prev = &p->left; + p = p->left; + } else { + prev = &p->right; + p = p->right; + } + } + *prev = n; + return n; +} + +/** + * Store domain name and ancestors into compression tree. + * @param tree: root of tree (may be modified) + * @param dname: pointer to uncompressed dname (stored in tree). + * @param labs: number of labels in dname. + * @param offset: offset into packet for dname. + * @param region: how to allocate memory for new node. + * @param closest: match from previous lookup, used to compress dname. + * may be NULL if no previous match. + * if the tree has an ancestor of dname already, this must be it. + * @return: 0 on memory error. + */ +static int +compress_tree_store(struct compress_tree_node** tree, uint8_t* dname, + int labs, size_t offset, region_type* region, + struct compress_tree_node* closest) +{ + uint8_t lablen; + struct compress_tree_node** lastparentptr = 0; + struct compress_tree_node* newnode; + int uplabs = labs-1; /* does not store root in tree */ + if(closest) uplabs = labs - closest->labs; + log_assert(uplabs >= 0); + while(uplabs--) { + if(offset > 0x3fff) { /* largest valid compr. offset */ + if(lastparentptr) + *lastparentptr = closest; + return 1; /* compression pointer no longer useful */ + } + /* store dname, labs, offset */ + if(!(newnode = compress_tree_insert(tree, dname, labs, offset, + region))) { + if(lastparentptr) + *lastparentptr = closest; + return 0; + } + if(lastparentptr) + *lastparentptr = newnode; + lastparentptr = &newnode->parent; + + /* next label */ + lablen = *dname++; + dname += lablen; + offset += lablen+1; + labs--; + } + if(lastparentptr) + *lastparentptr = closest; + return 1; +} + + /** bake a new type-class-ttl value, or 0 on malloc error */ static uint32_t* bake_tcttl(int do_sig, region_type* region, - struct packed_rrset_key* rk, uint32_t ttl, uint32_t timenow) + struct packed_rrset_key* rk, uint32_t ttl, uint32_t timenow, + uint32_t* prevttl, uint32_t* prevtcttl) { /* type, class, ttl, type-class-ttl used for rrsigs. ttl used for data itself. */ uint32_t* t; + if(prevttl && *prevttl == ttl) + return prevtcttl; if(do_sig) { t = (uint32_t*)region_alloc(region, 2*sizeof(uint32_t)); if(!t) return 0; @@ -510,14 +704,76 @@ bake_tcttl(int do_sig, region_type* region, return t; } +/** bake dname iov */ +static int +bakedname(int dosig, struct compress_tree_node** tree, size_t* offset, + region_type* region, struct iovec* iov, struct packed_rrset_key* rk) +{ + /* see if this name can be compressed */ + struct compress_tree_node* p; + int labs = dname_count_labels(rk->dname); + size_t atset = *offset; + p = compress_tree_lookup(*tree, rk->dname, labs); + if(p) { + /* compress it */ + int labcopy = labs - p->labs; + size_t len = 0; + uint8_t lablen; + uint8_t* from = rk->dname; + uint16_t ptr; + uint8_t* dat = (uint8_t*)region_alloc(region, + sizeof(uint16_t)*2*dosig + rk->dname_len); + /* note: oversized memory allocation. */ + if(!dat) return 0; + iov->iov_base = dat; + /* copy the first couple of labels */ + while(labcopy--) { + lablen = *from++; + *dat++ = lablen; + memmove(dat, from, lablen); + len += lablen+1; + dat += lablen; + from += lablen; + } + /* insert compression ptr */ + ptr = 0xc000 | p->offset; + ptr = htons(ptr); + memmove(dat, &ptr, sizeof(ptr)); + len += sizeof(ptr); + dat += sizeof(ptr); + if(!dosig) { + /* add type and class */ + memmove(dat, &rk->dname[rk->dname_len], 4); + dat += 4; + len += 4; + } + log_assert(len <= sizeof(uint16_t)*2*dosig + rk->dname_len); + iov->iov_len = len; + *offset += len; + } else { + /* uncompressed */ + iov->iov_base = rk->dname; + if(dosig) + iov->iov_len = rk->dname_len; + else iov->iov_len = rk->dname_len + 4; + *offset += iov->iov_len; + } + + /* store this name for future compression */ + if(!compress_tree_store(tree, rk->dname, labs, atset, region, p)) + return 0; + return 1; +} + /** store rrset in iov vector */ static int packed_rrset_iov(struct ub_packed_rrset_key* key, struct iovec* iov, size_t max, uint16_t* num_rrs, uint32_t timenow, region_type* region, - size_t* used, int do_data, int do_sig) + size_t* used, int do_data, int do_sig, + struct compress_tree_node** tree, size_t* offset) { size_t i; - uint32_t* tcttl; + uint32_t* tcttl = 0; struct packed_rrset_data* data = (struct packed_rrset_data*) key->entry.data; if(do_data) { @@ -525,15 +781,22 @@ packed_rrset_iov(struct ub_packed_rrset_key* key, struct iovec* iov, for(i=0; icount; i++) { if(max - *used < 3) return 0; if(!(tcttl = bake_tcttl(0, region, &key->rk, - data->rr_ttl[i], timenow))) + data->rr_ttl[i], timenow, + i>0?&data->rr_ttl[i-1]:0, tcttl))) return 0; /* no compression of dnames yet */ + if(0) + if(!bakedname(0, tree, offset, region, &iov[*used], + &key->rk)) + return 0; iov[*used].iov_base = (void*)key->rk.dname; iov[*used].iov_len = key->rk.dname_len + 4; iov[*used+1].iov_base = (void*)tcttl; iov[*used+1].iov_len = sizeof(uint32_t); iov[*used+2].iov_base = (void*)data->rr_data[i]; iov[*used+2].iov_len = data->rr_len[i]; + *offset += iov[*used].iov_len + sizeof(uint32_t) + + data->rr_len[i]; *used += 3; } } @@ -543,7 +806,8 @@ packed_rrset_iov(struct ub_packed_rrset_key* key, struct iovec* iov, for(i=0; irrsig_count; i++) { if(max - *used < 3) return 0; if(!(tcttl = bake_tcttl(1, region, &key->rk, - data->rr_ttl[data->count+i], timenow))) + data->rr_ttl[data->count+i], timenow, + i>0?&data->rr_ttl[i-1]:0, tcttl))) return 0; /* no compression of dnames yet */ iov[*used].iov_base = (void*)key->rk.dname; @@ -563,23 +827,27 @@ packed_rrset_iov(struct ub_packed_rrset_key* key, struct iovec* iov, static int insert_section(struct reply_info* rep, size_t num_rrsets, uint16_t* num_rrs, struct iovec* iov, size_t max, size_t rrsets_before, - uint32_t timenow, region_type* region, size_t* used, int addit) + uint32_t timenow, region_type* region, size_t* used, int addit, + struct compress_tree_node** tree, size_t* offset) { size_t i; *num_rrs = 0; if(!addit) { for(i=0; irrsets[rrsets_before+i], iov, - max, num_rrs, timenow, region, used, 1, 1)) + max, num_rrs, timenow, region, used, 1, 1, + tree, offset)) return 0; } else { for(i=0; irrsets[rrsets_before+i], iov, - max, num_rrs, timenow, region, used, 1, 0)) + max, num_rrs, timenow, region, used, 1, 0, + tree, offset)) return 0; for(i=0; irrsets[rrsets_before+i], iov, - max, num_rrs, timenow, region, used, 0, 1)) + max, num_rrs, timenow, region, used, 0, 1, + tree, offset)) return 0; } *num_rrs = htons(*num_rrs); @@ -592,6 +860,8 @@ size_t reply_info_iov_regen(struct query_info* qinfo, struct reply_info* rep, { size_t used; uint16_t* hdr = (uint16_t*)region_alloc(region, sizeof(uint16_t)*6); + size_t offset = 0; + struct compress_tree_node* tree = 0; if(!hdr) return 0; if(max<1) return 0; hdr[0] = id; @@ -599,6 +869,7 @@ size_t reply_info_iov_regen(struct query_info* qinfo, struct reply_info* rep, iov[0].iov_base = (void*)&hdr[0]; iov[0].iov_len = sizeof(uint16_t)*6; hdr[2] = htons(rep->qdcount); + offset = sizeof(uint16_t)*6; used=1; /* insert query section */ @@ -609,29 +880,33 @@ size_t reply_info_iov_regen(struct query_info* qinfo, struct reply_info* rep, if(max-used < 3) return 0; iov[used].iov_base = (void*)qinfo->qname; iov[used].iov_len = qinfo->qnamesize; + if(!compress_tree_store(&tree, qinfo->qname, + dname_count_labels(qinfo->qname), offset, region, NULL)) + return 0; *qt = htons(qinfo->qtype); *qc = htons(qinfo->qclass); iov[used+1].iov_base = (void*)qt; iov[used+1].iov_len = sizeof(uint16_t); iov[used+2].iov_base = (void*)qc; iov[used+2].iov_len = sizeof(uint16_t); + offset += qinfo->qnamesize + sizeof(uint16_t)*2; used += 3; } /* insert answer section */ if(!insert_section(rep, rep->an_numrrsets, &hdr[3], iov, max, - 0, timenow, region, &used, 0)) + 0, timenow, region, &used, 0, &tree, &offset)) return 0; /* insert auth section */ if(!insert_section(rep, rep->ns_numrrsets, &hdr[4], iov, max, - rep->an_numrrsets, timenow, region, &used, 0)) + rep->an_numrrsets, timenow, region, &used, 0, &tree, &offset)) return 0; /* insert add section */ if(!insert_section(rep, rep->ar_numrrsets, &hdr[5], iov, max, rep->an_numrrsets + rep->ns_numrrsets, timenow, region, - &used, 1)) + &used, 1, &tree, &offset)) return 0; return used; diff --git a/util/log.c b/util/log.c index c9bfdd60a..9eb598d0c 100644 --- a/util/log.c +++ b/util/log.c @@ -44,7 +44,7 @@ #include #endif -enum verbosity_value verbosity = 0; +enum verbosity_value verbosity = 4; /** the file logged to. */ static FILE* logfile = 0; /** if key has been created */ -- 2.47.2