contrib/unbound/util/data/msgencode.c

   1 /*
   2  * util/data/msgencode.c - Encode DNS messages, queries and replies.
   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 LIMITED
  25  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  26  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE
  27  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  28  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  29  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  30  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  31  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  32  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  33  * POSSIBILITY OF SUCH DAMAGE.
  34  */
  35
  36 /**
  37  * \file
  38  *
  39  * This file contains a routines to encode DNS messages.
  40  */
  41
  42 #include "config.h"
  43 #include <ldns/wire2host.h>
  44 #include "util/data/msgencode.h"
  45 #include "util/data/msgreply.h"
  46 #include "util/data/msgparse.h"
  47 #include "util/data/dname.h"
  48 #include "util/log.h"
  49 #include "util/regional.h"
  50 #include "util/net_help.h"
  51
  52 /** return code that means the function ran out of memory. negative so it does
  53  * not conflict with DNS rcodes. */
  54 #define RETVAL_OUTMEM   -2
  55 /** return code that means the data did not fit (completely) in the packet */
  56 #define RETVAL_TRUNC    -4
  57 /** return code that means all is peachy keen. Equal to DNS rcode NOERROR */
  58 #define RETVAL_OK       0
  59
  60 /**
  61  * Data structure to help domain name compression in outgoing messages.
  62  * A tree of dnames and their offsets in the packet is kept.
  63  * It is kept sorted, not canonical, but by label at least, so that after
  64  * a lookup of a name you know its closest match, and the parent from that
  65  * closest match. These are possible compression targets.
  66  *
  67  * It is a binary tree, not a rbtree or balanced tree, as the effort
  68  * of keeping it balanced probably outweighs usefulness (given typical
  69  * DNS packet size).
  70  */
  71 struct compress_tree_node {
  72         /** left node in tree, all smaller to this */
  73         struct compress_tree_node* left;
  74         /** right node in tree, all larger than this */
  75         struct compress_tree_node* right;
  76
  77         /** the parent node - not for tree, but zone parent. One less label */
  78         struct compress_tree_node* parent;
  79         /** the domain name for this node. Pointer to uncompressed memory. */
  80         uint8_t* dname;
  81         /** number of labels in domain name, kept to help compare func. */
  82         int labs;
  83         /** offset in packet that points to this dname */
  84         size_t offset;
  85 };
  86
  87 /**
  88  * Find domain name in tree, returns exact and closest match.
  89  * @param tree: root of tree.
  90  * @param dname: pointer to uncompressed dname.
  91  * @param labs: number of labels in domain name.
  92  * @param match: closest or exact match.
  93  *      guaranteed to be smaller or equal to the sought dname.
  94  *      can be null if the tree is empty.
  95  * @param matchlabels: number of labels that match with closest match.
  96  *      can be zero is there is no match.
  97  * @param insertpt: insert location for dname, if not found.
  98  * @return: 0 if no exact match.
  99  */
 100 static int
 101 compress_tree_search(struct compress_tree_node** tree, uint8_t* dname,
 102         int labs, struct compress_tree_node** match, int* matchlabels,
 103         struct compress_tree_node*** insertpt)
 104 {
 105         int c, n, closen=0;
 106         struct compress_tree_node* p = *tree;
 107         struct compress_tree_node* close = 0;
 108         struct compress_tree_node** prev = tree;
 109         while(p) {
 110                 if((c = dname_lab_cmp(dname, labs, p->dname, p->labs, &n))
 111                         == 0) {
 112                         *matchlabels = n;
 113                         *match = p;
 114                         return 1;
 115                 }
 116                 if(c<0) {
 117                         prev = &p->left;
 118                         p = p->left;
 119                 } else  {
 120                         closen = n;
 121                         close = p; /* p->dname is smaller than dname */
 122                         prev = &p->right;
 123                         p = p->right;
 124                 }
 125         }
 126         *insertpt = prev;
 127         *matchlabels = closen;
 128         *match = close;
 129         return 0;
 130 }
 131
 132 /**
 133  * Lookup a domain name in compression tree.
 134  * @param tree: root of tree (not the node with '.').
 135  * @param dname: pointer to uncompressed dname.
 136  * @param labs: number of labels in domain name.
 137  * @param insertpt: insert location for dname, if not found.
 138  * @return: 0 if not found or compress treenode with best compression.
 139  */
 140 static struct compress_tree_node*
 141 compress_tree_lookup(struct compress_tree_node** tree, uint8_t* dname,
 142         int labs, struct compress_tree_node*** insertpt)
 143 {
 144         struct compress_tree_node* p;
 145         int m;
 146         if(labs <= 1)
 147                 return 0; /* do not compress root node */
 148         if(compress_tree_search(tree, dname, labs, &p, &m, insertpt)) {
 149                 /* exact match */
 150                 return p;
 151         }
 152         /* return some ancestor of p that compresses well. */
 153         if(m>1) {
 154                 /* www.example.com. (labs=4) matched foo.example.com.(labs=4)
 155                  * then matchcount = 3. need to go up. */
 156                 while(p && p->labs > m)
 157                         p = p->parent;
 158                 return p;
 159         }
 160         return 0;
 161 }
 162
 163 /**
 164  * Create node for domain name compression tree.
 165  * @param dname: pointer to uncompressed dname (stored in tree).
 166  * @param labs: number of labels in dname.
 167  * @param offset: offset into packet for dname.
 168  * @param region: how to allocate memory for new node.
 169  * @return new node or 0 on malloc failure.
 170  */
 171 static struct compress_tree_node*
 172 compress_tree_newnode(uint8_t* dname, int labs, size_t offset,
 173         struct regional* region)
 174 {
 175         struct compress_tree_node* n = (struct compress_tree_node*)
 176                 regional_alloc(region, sizeof(struct compress_tree_node));
 177         if(!n) return 0;
 178         n->left = 0;
 179         n->right = 0;
 180         n->parent = 0;
 181         n->dname = dname;
 182         n->labs = labs;
 183         n->offset = offset;
 184         return n;
 185 }
 186
 187 /**
 188  * Store domain name and ancestors into compression tree.
 189  * @param dname: pointer to uncompressed dname (stored in tree).
 190  * @param labs: number of labels in dname.
 191  * @param offset: offset into packet for dname.
 192  * @param region: how to allocate memory for new node.
 193  * @param closest: match from previous lookup, used to compress dname.
 194  *      may be NULL if no previous match.
 195  *      if the tree has an ancestor of dname already, this must be it.
 196  * @param insertpt: where to insert the dname in tree.
 197  * @return: 0 on memory error.
 198  */
 199 static int
 200 compress_tree_store(uint8_t* dname, int labs, size_t offset,
 201         struct regional* region, struct compress_tree_node* closest,
 202         struct compress_tree_node** insertpt)
 203 {
 204         uint8_t lablen;
 205         struct compress_tree_node* newnode;
 206         struct compress_tree_node* prevnode = NULL;
 207         int uplabs = labs-1; /* does not store root in tree */
 208         if(closest) uplabs = labs - closest->labs;
 209         log_assert(uplabs >= 0);
 210         /* algorithms builds up a vine of dname-labels to hang into tree */
 211         while(uplabs--) {
 212                 if(offset > PTR_MAX_OFFSET) {
 213                         /* insertion failed, drop vine */
 214                         return 1; /* compression pointer no longer useful */
 215                 }
 216                 if(!(newnode = compress_tree_newnode(dname, labs, offset,
 217                         region))) {
 218                         /* insertion failed, drop vine */
 219                         return 0;
 220                 }
 221
 222                 if(prevnode) {
 223                         /* chain nodes together, last one has one label more,
 224                          * so is larger than newnode, thus goes right. */
 225                         newnode->right = prevnode;
 226                         prevnode->parent = newnode;
 227                 }
 228
 229                 /* next label */
 230                 lablen = *dname++;
 231                 dname += lablen;
 232                 offset += lablen+1;
 233                 prevnode = newnode;
 234                 labs--;
 235         }
 236         /* if we have a vine, hang the vine into the tree */
 237         if(prevnode) {
 238                 *insertpt = prevnode;
 239                 prevnode->parent = closest;
 240         }
 241         return 1;
 242 }
 243
 244 /** compress a domain name */
 245 static int
 246 write_compressed_dname(ldns_buffer* pkt, uint8_t* dname, int labs,
 247         struct compress_tree_node* p)
 248 {
 249         /* compress it */
 250         int labcopy = labs - p->labs;
 251         uint8_t lablen;
 252         uint16_t ptr;
 253
 254         if(labs == 1) {
 255                 /* write root label */
 256                 if(ldns_buffer_remaining(pkt) < 1)
 257                         return 0;
 258                 ldns_buffer_write_u8(pkt, 0);
 259                 return 1;
 260         }
 261
 262         /* copy the first couple of labels */
 263         while(labcopy--) {
 264                 lablen = *dname++;
 265                 if(ldns_buffer_remaining(pkt) < (size_t)lablen+1)
 266                         return 0;
 267                 ldns_buffer_write_u8(pkt, lablen);
 268                 ldns_buffer_write(pkt, dname, lablen);
 269                 dname += lablen;
 270         }
 271         /* insert compression ptr */
 272         if(ldns_buffer_remaining(pkt) < 2)
 273                 return 0;
 274         ptr = PTR_CREATE(p->offset);
 275         ldns_buffer_write_u16(pkt, ptr);
 276         return 1;
 277 }
 278
 279 /** compress owner name of RR, return RETVAL_OUTMEM RETVAL_TRUNC */
 280 static int
 281 compress_owner(struct ub_packed_rrset_key* key, ldns_buffer* pkt,
 282         struct regional* region, struct compress_tree_node** tree,
 283         size_t owner_pos, uint16_t* owner_ptr, int owner_labs)
 284 {
 285         struct compress_tree_node* p;
 286         struct compress_tree_node** insertpt;
 287         if(!*owner_ptr) {
 288                 /* compress first time dname */
 289                 if((p = compress_tree_lookup(tree, key->rk.dname,
 290                         owner_labs, &insertpt))) {
 291                         if(p->labs == owner_labs)
 292                                 /* avoid ptr chains, since some software is
 293                                  * not capable of decoding ptr after a ptr. */
 294                                 *owner_ptr = htons(PTR_CREATE(p->offset));
 295                         if(!write_compressed_dname(pkt, key->rk.dname,
 296                                 owner_labs, p))
 297                                 return RETVAL_TRUNC;
 298                         /* check if typeclass+4 ttl + rdatalen is available */
 299                         if(ldns_buffer_remaining(pkt) < 4+4+2)
 300                                 return RETVAL_TRUNC;
 301                 } else {
 302                         /* no compress */
 303                         if(ldns_buffer_remaining(pkt) < key->rk.dname_len+4+4+2)
 304                                 return RETVAL_TRUNC;
 305                         ldns_buffer_write(pkt, key->rk.dname,
 306                                 key->rk.dname_len);
 307                         if(owner_pos <= PTR_MAX_OFFSET)
 308                                 *owner_ptr = htons(PTR_CREATE(owner_pos));
 309                 }
 310                 if(!compress_tree_store(key->rk.dname, owner_labs,
 311                         owner_pos, region, p, insertpt))
 312                         return RETVAL_OUTMEM;
 313         } else {
 314                 /* always compress 2nd-further RRs in RRset */
 315                 if(owner_labs == 1) {
 316                         if(ldns_buffer_remaining(pkt) < 1+4+4+2)
 317                                 return RETVAL_TRUNC;
 318                         ldns_buffer_write_u8(pkt, 0);
 319                 } else {
 320                         if(ldns_buffer_remaining(pkt) < 2+4+4+2)
 321                                 return RETVAL_TRUNC;
 322                         ldns_buffer_write(pkt, owner_ptr, 2);
 323                 }
 324         }
 325         return RETVAL_OK;
 326 }
 327
 328 /** compress any domain name to the packet, return RETVAL_* */
 329 static int
 330 compress_any_dname(uint8_t* dname, ldns_buffer* pkt, int labs,
 331         struct regional* region, struct compress_tree_node** tree)
 332 {
 333         struct compress_tree_node* p;
 334         struct compress_tree_node** insertpt = NULL;
 335         size_t pos = ldns_buffer_position(pkt);
 336         if((p = compress_tree_lookup(tree, dname, labs, &insertpt))) {
 337                 if(!write_compressed_dname(pkt, dname, labs, p))
 338                         return RETVAL_TRUNC;
 339         } else {
 340                 if(!dname_buffer_write(pkt, dname))
 341                         return RETVAL_TRUNC;
 342         }
 343         if(!compress_tree_store(dname, labs, pos, region, p, insertpt))
 344                 return RETVAL_OUTMEM;
 345         return RETVAL_OK;
 346 }
 347
 348 /** return true if type needs domain name compression in rdata */
 349 static const ldns_rr_descriptor*
 350 type_rdata_compressable(struct ub_packed_rrset_key* key)
 351 {
 352         uint16_t t = ntohs(key->rk.type);
 353         if(ldns_rr_descript(t) &&
 354                 ldns_rr_descript(t)->_compress == LDNS_RR_COMPRESS)
 355                 return ldns_rr_descript(t);
 356         return 0;
 357 }
 358
 359 /** compress domain names in rdata, return RETVAL_* */
 360 static int
 361 compress_rdata(ldns_buffer* pkt, uint8_t* rdata, size_t todolen,
 362         struct regional* region, struct compress_tree_node** tree,
 363         const ldns_rr_descriptor* desc)
 364 {
 365         int labs, r, rdf = 0;
 366         size_t dname_len, len, pos = ldns_buffer_position(pkt);
 367         uint8_t count = desc->_dname_count;
 368
 369         ldns_buffer_skip(pkt, 2); /* rdata len fill in later */
 370         /* space for rdatalen checked for already */
 371         rdata += 2;
 372         todolen -= 2;
 373         while(todolen > 0 && count) {
 374                 switch(desc->_wireformat[rdf]) {
 375                 case LDNS_RDF_TYPE_DNAME:
 376                         labs = dname_count_size_labels(rdata, &dname_len);
 377                         if((r=compress_any_dname(rdata, pkt, labs, region,
 378                                 tree)) != RETVAL_OK)
 379                                 return r;
 380                         rdata += dname_len;
 381                         todolen -= dname_len;
 382                         count--;
 383                         len = 0;
 384                         break;
 385                 case LDNS_RDF_TYPE_STR:
 386                         len = *rdata + 1;
 387                         break;
 388                 default:
 389                         len = get_rdf_size(desc->_wireformat[rdf]);
 390                 }
 391                 if(len) {
 392                         /* copy over */
 393                         if(ldns_buffer_remaining(pkt) < len)
 394                                 return RETVAL_TRUNC;
 395                         ldns_buffer_write(pkt, rdata, len);
 396                         todolen -= len;
 397                         rdata += len;
 398                 }
 399                 rdf++;
 400         }
 401         /* copy remainder */
 402         if(todolen > 0) {
 403                 if(ldns_buffer_remaining(pkt) < todolen)
 404                         return RETVAL_TRUNC;
 405                 ldns_buffer_write(pkt, rdata, todolen);
 406         }
 407
 408         /* set rdata len */
 409         ldns_buffer_write_u16_at(pkt, pos, ldns_buffer_position(pkt)-pos-2);
 410         return RETVAL_OK;
 411 }
 412
 413 /** Returns true if RR type should be included */
 414 static int
 415 rrset_belongs_in_reply(ldns_pkt_section s, uint16_t rrtype, uint16_t qtype,
 416         int dnssec)
 417 {
 418         if(dnssec)
 419                 return 1;
 420         /* skip non DNSSEC types, except if directly queried for */
 421         if(s == LDNS_SECTION_ANSWER) {
 422                 if(qtype == LDNS_RR_TYPE_ANY || qtype == rrtype)
 423                         return 1;
 424         }
 425         /* check DNSSEC-ness */
 426         switch(rrtype) {
 427                 case LDNS_RR_TYPE_SIG:
 428                 case LDNS_RR_TYPE_KEY:
 429                 case LDNS_RR_TYPE_NXT:
 430                 case LDNS_RR_TYPE_DS:
 431                 case LDNS_RR_TYPE_RRSIG:
 432                 case LDNS_RR_TYPE_NSEC:
 433                 case LDNS_RR_TYPE_DNSKEY:
 434                 case LDNS_RR_TYPE_NSEC3:
 435                 case LDNS_RR_TYPE_NSEC3PARAMS:
 436                         return 0;
 437         }
 438         return 1;
 439 }
 440
 441 /** store rrset in buffer in wireformat, return RETVAL_* */
 442 static int
 443 packed_rrset_encode(struct ub_packed_rrset_key* key, ldns_buffer* pkt,
 444         uint16_t* num_rrs, uint32_t timenow, struct regional* region,
 445         int do_data, int do_sig, struct compress_tree_node** tree,
 446         ldns_pkt_section s, uint16_t qtype, int dnssec, size_t rr_offset)
 447 {
 448         size_t i, j, owner_pos;
 449         int r, owner_labs;
 450         uint16_t owner_ptr = 0;
 451         struct packed_rrset_data* data = (struct packed_rrset_data*)
 452                 key->entry.data;
 453
 454         /* does this RR type belong in the answer? */
 455         if(!rrset_belongs_in_reply(s, ntohs(key->rk.type), qtype, dnssec))
 456                 return RETVAL_OK;
 457
 458         owner_labs = dname_count_labels(key->rk.dname);
 459         owner_pos = ldns_buffer_position(pkt);
 460
 461         if(do_data) {
 462                 const ldns_rr_descriptor* c = type_rdata_compressable(key);
 463                 for(i=0; i<data->count; i++) {
 464                         /* rrset roundrobin */
 465                         j = (i + rr_offset) % data->count;
 466                         if((r=compress_owner(key, pkt, region, tree,
 467                                 owner_pos, &owner_ptr, owner_labs))
 468                                 != RETVAL_OK)
 469                                 return r;
 470                         ldns_buffer_write(pkt, &key->rk.type, 2);
 471                         ldns_buffer_write(pkt, &key->rk.rrset_class, 2);
 472                         if(data->rr_ttl[j] < timenow)
 473                                 ldns_buffer_write_u32(pkt, 0);
 474                         else    ldns_buffer_write_u32(pkt,
 475                                         data->rr_ttl[j]-timenow);
 476                         if(c) {
 477                                 if((r=compress_rdata(pkt, data->rr_data[j],
 478                                         data->rr_len[j], region, tree, c))
 479                                         != RETVAL_OK)
 480                                         return r;
 481                         } else {
 482                                 if(ldns_buffer_remaining(pkt) < data->rr_len[j])
 483                                         return RETVAL_TRUNC;
 484                                 ldns_buffer_write(pkt, data->rr_data[j],
 485                                         data->rr_len[j]);
 486                         }
 487                 }
 488         }
 489         /* insert rrsigs */
 490         if(do_sig && dnssec) {
 491                 size_t total = data->count+data->rrsig_count;
 492                 for(i=data->count; i<total; i++) {
 493                         if(owner_ptr && owner_labs != 1) {
 494                                 if(ldns_buffer_remaining(pkt) <
 495                                         2+4+4+data->rr_len[i])
 496                                         return RETVAL_TRUNC;
 497                                 ldns_buffer_write(pkt, &owner_ptr, 2);
 498                         } else {
 499                                 if((r=compress_any_dname(key->rk.dname,
 500                                         pkt, owner_labs, region, tree))
 501                                         != RETVAL_OK)
 502                                         return r;
 503                                 if(ldns_buffer_remaining(pkt) <
 504                                         4+4+data->rr_len[i])
 505                                         return RETVAL_TRUNC;
 506                         }
 507                         ldns_buffer_write_u16(pkt, LDNS_RR_TYPE_RRSIG);
 508                         ldns_buffer_write(pkt, &key->rk.rrset_class, 2);
 509                         if(data->rr_ttl[i] < timenow)
 510                                 ldns_buffer_write_u32(pkt, 0);
 511                         else    ldns_buffer_write_u32(pkt,
 512                                         data->rr_ttl[i]-timenow);
 513                         /* rrsig rdata cannot be compressed, perform 100+ byte
 514                          * memcopy. */
 515                         ldns_buffer_write(pkt, data->rr_data[i],
 516                                 data->rr_len[i]);
 517                 }
 518         }
 519         /* change rrnum only after we are sure it fits */
 520         if(do_data)
 521                 *num_rrs += data->count;
 522         if(do_sig && dnssec)
 523                 *num_rrs += data->rrsig_count;
 524
 525         return RETVAL_OK;
 526 }
 527
 528 /** store msg section in wireformat buffer, return RETVAL_* */
 529 static int
 530 insert_section(struct reply_info* rep, size_t num_rrsets, uint16_t* num_rrs,
 531         ldns_buffer* pkt, size_t rrsets_before, uint32_t timenow,
 532         struct regional* region, struct compress_tree_node** tree,
 533         ldns_pkt_section s, uint16_t qtype, int dnssec, size_t rr_offset)
 534 {
 535         int r;
 536         size_t i, setstart;
 537         *num_rrs = 0;
 538         if(s != LDNS_SECTION_ADDITIONAL) {
 539                 if(s == LDNS_SECTION_ANSWER && qtype == LDNS_RR_TYPE_ANY)
 540                         dnssec = 1; /* include all types in ANY answer */
 541                 for(i=0; i<num_rrsets; i++) {
 542                         setstart = ldns_buffer_position(pkt);
 543                         if((r=packed_rrset_encode(rep->rrsets[rrsets_before+i],
 544                                 pkt, num_rrs, timenow, region, 1, 1, tree,
 545                                 s, qtype, dnssec, rr_offset))
 546                                 != RETVAL_OK) {
 547                                 /* Bad, but if due to size must set TC bit */
 548                                 /* trim off the rrset neatly. */
 549                                 ldns_buffer_set_position(pkt, setstart);
 550                                 return r;
 551                         }
 552                 }
 553         } else {
 554                 for(i=0; i<num_rrsets; i++) {
 555                         setstart = ldns_buffer_position(pkt);
 556                         if((r=packed_rrset_encode(rep->rrsets[rrsets_before+i],
 557                                 pkt, num_rrs, timenow, region, 1, 0, tree,
 558                                 s, qtype, dnssec, rr_offset))
 559                                 != RETVAL_OK) {
 560                                 ldns_buffer_set_position(pkt, setstart);
 561                                 return r;
 562                         }
 563                 }
 564                 if(dnssec)
 565                   for(i=0; i<num_rrsets; i++) {
 566                         setstart = ldns_buffer_position(pkt);
 567                         if((r=packed_rrset_encode(rep->rrsets[rrsets_before+i],
 568                                 pkt, num_rrs, timenow, region, 0, 1, tree,
 569                                 s, qtype, dnssec, rr_offset))
 570                                 != RETVAL_OK) {
 571                                 ldns_buffer_set_position(pkt, setstart);
 572                                 return r;
 573                         }
 574                   }
 575         }
 576         return RETVAL_OK;
 577 }
 578
 579 /** store query section in wireformat buffer, return RETVAL */
 580 static int
 581 insert_query(struct query_info* qinfo, struct compress_tree_node** tree,
 582         ldns_buffer* buffer, struct regional* region)
 583 {
 584         if(ldns_buffer_remaining(buffer) <
 585                 qinfo->qname_len+sizeof(uint16_t)*2)
 586                 return RETVAL_TRUNC; /* buffer too small */
 587         /* the query is the first name inserted into the tree */
 588         if(!compress_tree_store(qinfo->qname,
 589                 dname_count_labels(qinfo->qname),
 590                 ldns_buffer_position(buffer), region, NULL, tree))
 591                 return RETVAL_OUTMEM;
 592         if(ldns_buffer_current(buffer) == qinfo->qname)
 593                 ldns_buffer_skip(buffer, (ssize_t)qinfo->qname_len);
 594         else    ldns_buffer_write(buffer, qinfo->qname, qinfo->qname_len);
 595         ldns_buffer_write_u16(buffer, qinfo->qtype);
 596         ldns_buffer_write_u16(buffer, qinfo->qclass);
 597         return RETVAL_OK;
 598 }
 599
 600 static int
 601 positive_answer(struct reply_info* rep, uint16_t qtype) {
 602         size_t i;
 603         if (FLAGS_GET_RCODE(rep->flags) != LDNS_RCODE_NOERROR)
 604                 return 0;
 605
 606         for(i=0;i<rep->an_numrrsets; i++) {
 607                 if(ntohs(rep->rrsets[i]->rk.type) == qtype) {
 608                         /* in case it is a wildcard with DNSSEC, there will
 609                          * be NSEC/NSEC3 records in the authority section
 610                          * that we cannot remove */
 611                         for(i=rep->an_numrrsets; i<rep->an_numrrsets+
 612                                 rep->ns_numrrsets; i++) {
 613                                 if(ntohs(rep->rrsets[i]->rk.type) ==
 614                                         LDNS_RR_TYPE_NSEC ||
 615                                    ntohs(rep->rrsets[i]->rk.type) ==
 616                                         LDNS_RR_TYPE_NSEC3)
 617                                         return 0;
 618                         }
 619                         return 1;
 620                 }
 621         }
 622         return 0;
 623 }
 624
 625 int
 626 reply_info_encode(struct query_info* qinfo, struct reply_info* rep,
 627         uint16_t id, uint16_t flags, ldns_buffer* buffer, uint32_t timenow,
 628         struct regional* region, uint16_t udpsize, int dnssec)
 629 {
 630         uint16_t ancount=0, nscount=0, arcount=0;
 631         struct compress_tree_node* tree = 0;
 632         int r;
 633         size_t rr_offset;
 634
 635         ldns_buffer_clear(buffer);
 636         if(udpsize < ldns_buffer_limit(buffer))
 637                 ldns_buffer_set_limit(buffer, udpsize);
 638         if(ldns_buffer_remaining(buffer) < LDNS_HEADER_SIZE)
 639                 return 0;
 640
 641         ldns_buffer_write(buffer, &id, sizeof(uint16_t));
 642         ldns_buffer_write_u16(buffer, flags);
 643         ldns_buffer_write_u16(buffer, rep->qdcount);
 644         /* set an, ns, ar counts to zero in case of small packets */
 645         ldns_buffer_write(buffer, "\000\000\000\000\000\000", 6);
 646
 647         /* insert query section */
 648         if(rep->qdcount) {
 649                 if((r=insert_query(qinfo, &tree, buffer, region)) !=
 650                         RETVAL_OK) {
 651                         if(r == RETVAL_TRUNC) {
 652                                 /* create truncated message */
 653                                 ldns_buffer_write_u16_at(buffer, 4, 0);
 654                                 LDNS_TC_SET(ldns_buffer_begin(buffer));
 655                                 ldns_buffer_flip(buffer);
 656                                 return 1;
 657                         }
 658                         return 0;
 659                 }
 660         }
 661         /* roundrobin offset. using query id for random number */
 662         rr_offset = RRSET_ROUNDROBIN?id:0;
 663
 664         /* insert answer section */
 665         if((r=insert_section(rep, rep->an_numrrsets, &ancount, buffer,
 666                 0, timenow, region, &tree, LDNS_SECTION_ANSWER, qinfo->qtype,
 667                 dnssec, rr_offset)) != RETVAL_OK) {
 668                 if(r == RETVAL_TRUNC) {
 669                         /* create truncated message */
 670                         ldns_buffer_write_u16_at(buffer, 6, ancount);
 671                         LDNS_TC_SET(ldns_buffer_begin(buffer));
 672                         ldns_buffer_flip(buffer);
 673                         return 1;
 674                 }
 675                 return 0;
 676         }
 677         ldns_buffer_write_u16_at(buffer, 6, ancount);
 678
 679         /* if response is positive answer, auth/add sections are not required */
 680         if( ! (MINIMAL_RESPONSES && positive_answer(rep, qinfo->qtype)) ) {
 681                 /* insert auth section */
 682                 if((r=insert_section(rep, rep->ns_numrrsets, &nscount, buffer,
 683                         rep->an_numrrsets, timenow, region, &tree,
 684                         LDNS_SECTION_AUTHORITY, qinfo->qtype,
 685                         dnssec, rr_offset)) != RETVAL_OK) {
 686                         if(r == RETVAL_TRUNC) {
 687                                 /* create truncated message */
 688                                 ldns_buffer_write_u16_at(buffer, 8, nscount);
 689                                 LDNS_TC_SET(ldns_buffer_begin(buffer));
 690                                 ldns_buffer_flip(buffer);
 691                                 return 1;
 692                         }
 693                         return 0;
 694                 }
 695                 ldns_buffer_write_u16_at(buffer, 8, nscount);
 696
 697                 /* insert add section */
 698                 if((r=insert_section(rep, rep->ar_numrrsets, &arcount, buffer,
 699                         rep->an_numrrsets + rep->ns_numrrsets, timenow, region,
 700                         &tree, LDNS_SECTION_ADDITIONAL, qinfo->qtype,
 701                         dnssec, rr_offset)) != RETVAL_OK) {
 702                         if(r == RETVAL_TRUNC) {
 703                                 /* no need to set TC bit, this is the additional */
 704                                 ldns_buffer_write_u16_at(buffer, 10, arcount);
 705                                 ldns_buffer_flip(buffer);
 706                                 return 1;
 707                         }
 708                         return 0;
 709                 }
 710                 ldns_buffer_write_u16_at(buffer, 10, arcount);
 711         } else {
 712                 ldns_buffer_write_u16_at(buffer, 8, nscount);
 713                 ldns_buffer_write_u16_at(buffer, 10, arcount);
 714         }
 715         ldns_buffer_flip(buffer);
 716         return 1;
 717 }
 718
 719 uint16_t
 720 calc_edns_field_size(struct edns_data* edns)
 721 {
 722         if(!edns || !edns->edns_present)
 723                 return 0;
 724         /* domain root '.' + type + class + ttl + rdatalen(=0) */
 725         return 1 + 2 + 2 + 4 + 2;
 726 }
 727
 728 void
 729 attach_edns_record(ldns_buffer* pkt, struct edns_data* edns)
 730 {
 731         size_t len;
 732         if(!edns || !edns->edns_present)
 733                 return;
 734         /* inc additional count */
 735         ldns_buffer_write_u16_at(pkt, 10,
 736                 ldns_buffer_read_u16_at(pkt, 10) + 1);
 737         len = ldns_buffer_limit(pkt);
 738         ldns_buffer_clear(pkt);
 739         ldns_buffer_set_position(pkt, len);
 740         /* write EDNS record */
 741         ldns_buffer_write_u8(pkt, 0); /* '.' label */
 742         ldns_buffer_write_u16(pkt, LDNS_RR_TYPE_OPT); /* type */
 743         ldns_buffer_write_u16(pkt, edns->udp_size); /* class */
 744         ldns_buffer_write_u8(pkt, edns->ext_rcode); /* ttl */
 745         ldns_buffer_write_u8(pkt, edns->edns_version);
 746         ldns_buffer_write_u16(pkt, edns->bits);
 747         ldns_buffer_write_u16(pkt, 0); /* rdatalen */
 748         ldns_buffer_flip(pkt);
 749 }
 750
 751 int
 752 reply_info_answer_encode(struct query_info* qinf, struct reply_info* rep,
 753         uint16_t id, uint16_t qflags, ldns_buffer* pkt, uint32_t timenow,
 754         int cached, struct regional* region, uint16_t udpsize,
 755         struct edns_data* edns, int dnssec, int secure)
 756 {
 757         uint16_t flags;
 758         int attach_edns = 1;
 759
 760         if(!cached || rep->authoritative) {
 761                 /* original flags, copy RD and CD bits from query. */
 762                 flags = rep->flags | (qflags & (BIT_RD|BIT_CD));
 763         } else {
 764                 /* remove AA bit, copy RD and CD bits from query. */
 765                 flags = (rep->flags & ~BIT_AA) | (qflags & (BIT_RD|BIT_CD));
 766         }
 767         if(secure && (dnssec || (qflags&BIT_AD)))
 768                 flags |= BIT_AD;
 769         log_assert(flags & BIT_QR); /* QR bit must be on in our replies */
 770         if(udpsize < LDNS_HEADER_SIZE)
 771                 return 0;
 772         if(udpsize < LDNS_HEADER_SIZE + calc_edns_field_size(edns)) {
 773                 /* packet too small to contain edns, omit it. */
 774                 attach_edns = 0;
 775         } else {
 776                 /* reserve space for edns record */
 777                 udpsize -= calc_edns_field_size(edns);
 778         }
 779
 780         if(!reply_info_encode(qinf, rep, id, flags, pkt, timenow, region,
 781                 udpsize, dnssec)) {
 782                 log_err("reply encode: out of memory");
 783                 return 0;
 784         }
 785         if(attach_edns)
 786                 attach_edns_record(pkt, edns);
 787         return 1;
 788 }
 789
 790 void
 791 qinfo_query_encode(ldns_buffer* pkt, struct query_info* qinfo)
 792 {
 793         uint16_t flags = 0; /* QUERY, NOERROR */
 794         ldns_buffer_clear(pkt);
 795         log_assert(ldns_buffer_remaining(pkt) >= 12+255+4/*max query*/);
 796         ldns_buffer_skip(pkt, 2); /* id done later */
 797         ldns_buffer_write_u16(pkt, flags);
 798         ldns_buffer_write_u16(pkt, 1); /* query count */
 799         ldns_buffer_write(pkt, "\000\000\000\000\000\000", 6); /* counts */
 800         ldns_buffer_write(pkt, qinfo->qname, qinfo->qname_len);
 801         ldns_buffer_write_u16(pkt, qinfo->qtype);
 802         ldns_buffer_write_u16(pkt, qinfo->qclass);
 803         ldns_buffer_flip(pkt);
 804 }
 805
 806 void
 807 error_encode(ldns_buffer* buf, int r, struct query_info* qinfo,
 808         uint16_t qid, uint16_t qflags, struct edns_data* edns)
 809 {
 810         uint16_t flags;
 811
 812         ldns_buffer_clear(buf);
 813         ldns_buffer_write(buf, &qid, sizeof(uint16_t));
 814         flags = (uint16_t)(BIT_QR | BIT_RA | r); /* QR and retcode*/
 815         flags |= (qflags & (BIT_RD|BIT_CD)); /* copy RD and CD bit */
 816         ldns_buffer_write_u16(buf, flags);
 817         if(qinfo) flags = 1;
 818         else    flags = 0;
 819         ldns_buffer_write_u16(buf, flags);
 820         flags = 0;
 821         ldns_buffer_write(buf, &flags, sizeof(uint16_t));
 822         ldns_buffer_write(buf, &flags, sizeof(uint16_t));
 823         ldns_buffer_write(buf, &flags, sizeof(uint16_t));
 824         if(qinfo) {
 825                 if(ldns_buffer_current(buf) == qinfo->qname)
 826                         ldns_buffer_skip(buf, (ssize_t)qinfo->qname_len);
 827                 else    ldns_buffer_write(buf, qinfo->qname, qinfo->qname_len);
 828                 ldns_buffer_write_u16(buf, qinfo->qtype);
 829                 ldns_buffer_write_u16(buf, qinfo->qclass);
 830         }
 831         ldns_buffer_flip(buf);
 832         if(edns) {
 833                 struct edns_data es = *edns;
 834                 es.edns_version = EDNS_ADVERTISED_VERSION;
 835                 es.udp_size = EDNS_ADVERTISED_SIZE;
 836                 es.ext_rcode = 0;
 837                 es.bits &= EDNS_DO;
 838                 if(ldns_buffer_limit(buf) + calc_edns_field_size(&es) >
 839                         edns->udp_size)
 840                         return;
 841                 attach_edns_record(buf, &es);
 842         }
 843 }