contrib/unbound/util/data/msgparse.c

   1 /*
   2  * util/data/msgparse.c - parse wireformat DNS messages.
   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  * \file
  37  * Routines for message parsing a packet buffer to a descriptive structure.
  38  */
  39 #include "config.h"
  40 #include <ldns/ldns.h>
  41 #include "util/data/msgparse.h"
  42 #include "util/data/dname.h"
  43 #include "util/data/packed_rrset.h"
  44 #include "util/storage/lookup3.h"
  45 #include "util/regional.h"
  46
  47 /** smart comparison of (compressed, valid) dnames from packet */
  48 static int
  49 smart_compare(ldns_buffer* pkt, uint8_t* dnow,
  50         uint8_t* dprfirst, uint8_t* dprlast)
  51 {
  52         if(LABEL_IS_PTR(*dnow)) {
  53                 /* ptr points to a previous dname */
  54                 uint8_t* p = ldns_buffer_at(pkt, PTR_OFFSET(dnow[0], dnow[1]));
  55                 if( p == dprfirst || p == dprlast )
  56                         return 0;
  57                 /* prev dname is also a ptr, both ptrs are the same. */
  58                 if(LABEL_IS_PTR(*dprlast) &&
  59                         dprlast[0] == dnow[0] && dprlast[1] == dnow[1])
  60                         return 0;
  61         }
  62         return dname_pkt_compare(pkt, dnow, dprlast);
  63 }
  64
  65 /**
  66  * Allocate new rrset in region, fill with data.
  67  */
  68 static struct rrset_parse*
  69 new_rrset(struct msg_parse* msg, uint8_t* dname, size_t dnamelen,
  70         uint16_t type, uint16_t dclass, hashvalue_t hash,
  71         uint32_t rrset_flags, ldns_pkt_section section,
  72         struct regional* region)
  73 {
  74         struct rrset_parse* p = regional_alloc(region, sizeof(*p));
  75         if(!p) return NULL;
  76         p->rrset_bucket_next = msg->hashtable[hash & (PARSE_TABLE_SIZE-1)];
  77         msg->hashtable[hash & (PARSE_TABLE_SIZE-1)] = p;
  78         p->rrset_all_next = 0;
  79         if(msg->rrset_last)
  80                 msg->rrset_last->rrset_all_next = p;
  81         else    msg->rrset_first = p;
  82         msg->rrset_last = p;
  83         p->hash = hash;
  84         p->section = section;
  85         p->dname = dname;
  86         p->dname_len = dnamelen;
  87         p->type = type;
  88         p->rrset_class = dclass;
  89         p->flags = rrset_flags;
  90         p->rr_count = 0;
  91         p->size = 0;
  92         p->rr_first = 0;
  93         p->rr_last = 0;
  94         p->rrsig_count = 0;
  95         p->rrsig_first = 0;
  96         p->rrsig_last = 0;
  97         return p;
  98 }
  99
 100 /** See if next rrset is nsec at zone apex */
 101 static int
 102 nsec_at_apex(ldns_buffer* pkt)
 103 {
 104         /* we are at ttl position in packet. */
 105         size_t pos = ldns_buffer_position(pkt);
 106         uint16_t rdatalen;
 107         if(ldns_buffer_remaining(pkt) < 7) /* ttl+len+root */
 108                 return 0; /* eek! */
 109         ldns_buffer_skip(pkt, 4); /* ttl */;
 110         rdatalen = ldns_buffer_read_u16(pkt);
 111         if(ldns_buffer_remaining(pkt) < rdatalen) {
 112                 ldns_buffer_set_position(pkt, pos);
 113                 return 0; /* parse error happens later */
 114         }
 115         /* must validate the nsec next domain name format */
 116         if(pkt_dname_len(pkt) == 0) {
 117                 ldns_buffer_set_position(pkt, pos);
 118                 return 0; /* parse error */
 119         }
 120
 121         /* see if SOA bit is set. */
 122         if(ldns_buffer_position(pkt) < pos+4+rdatalen) {
 123                 /* nsec type bitmap contains items */
 124                 uint8_t win, blen, bits;
 125                 /* need: windownum, bitmap len, firstbyte */
 126                 if(ldns_buffer_position(pkt)+3 > pos+4+rdatalen) {
 127                         ldns_buffer_set_position(pkt, pos);
 128                         return 0; /* malformed nsec */
 129                 }
 130                 win = ldns_buffer_read_u8(pkt);
 131                 blen = ldns_buffer_read_u8(pkt);
 132                 bits = ldns_buffer_read_u8(pkt);
 133                 /* 0window always first window. bitlen >=1 or parse
 134                    error really. bit 0x2 is SOA. */
 135                 if(win == 0 && blen >= 1 && (bits & 0x02)) {
 136                         ldns_buffer_set_position(pkt, pos);
 137                         return 1;
 138                 }
 139         }
 140
 141         ldns_buffer_set_position(pkt, pos);
 142         return 0;
 143 }
 144
 145 /** Calculate rrset flags */
 146 static uint32_t
 147 pkt_rrset_flags(ldns_buffer* pkt, uint16_t type, ldns_pkt_section sec)
 148 {
 149         uint32_t f = 0;
 150         if(type == LDNS_RR_TYPE_NSEC && nsec_at_apex(pkt)) {
 151                 f |= PACKED_RRSET_NSEC_AT_APEX;
 152         } else if(type == LDNS_RR_TYPE_SOA && sec == LDNS_SECTION_AUTHORITY) {
 153                 f |= PACKED_RRSET_SOA_NEG;
 154         }
 155         return f;
 156 }
 157
 158 hashvalue_t
 159 pkt_hash_rrset(ldns_buffer* pkt, uint8_t* dname, uint16_t type,
 160         uint16_t dclass, uint32_t rrset_flags)
 161 {
 162         /* note this MUST be identical to rrset_key_hash in packed_rrset.c */
 163         /* this routine handles compressed names */
 164         hashvalue_t h = 0xab;
 165         h = dname_pkt_hash(pkt, dname, h);
 166         h = hashlittle(&type, sizeof(type), h);         /* host order */
 167         h = hashlittle(&dclass, sizeof(dclass), h);     /* netw order */
 168         h = hashlittle(&rrset_flags, sizeof(uint32_t), h);
 169         return h;
 170 }
 171
 172 /** create partial dname hash for rrset hash */
 173 static hashvalue_t
 174 pkt_hash_rrset_first(ldns_buffer* pkt, uint8_t* dname)
 175 {
 176         /* works together with pkt_hash_rrset_rest */
 177         /* note this MUST be identical to rrset_key_hash in packed_rrset.c */
 178         /* this routine handles compressed names */
 179         hashvalue_t h = 0xab;
 180         h = dname_pkt_hash(pkt, dname, h);
 181         return h;
 182 }
 183
 184 /** create a rrset hash from a partial dname hash */
 185 static hashvalue_t
 186 pkt_hash_rrset_rest(hashvalue_t dname_h, uint16_t type, uint16_t dclass,
 187         uint32_t rrset_flags)
 188 {
 189         /* works together with pkt_hash_rrset_first */
 190         /* note this MUST be identical to rrset_key_hash in packed_rrset.c */
 191         hashvalue_t h;
 192         h = hashlittle(&type, sizeof(type), dname_h);   /* host order */
 193         h = hashlittle(&dclass, sizeof(dclass), h);     /* netw order */
 194         h = hashlittle(&rrset_flags, sizeof(uint32_t), h);
 195         return h;
 196 }
 197
 198 /** compare rrset_parse with data */
 199 static int
 200 rrset_parse_equals(struct rrset_parse* p, ldns_buffer* pkt, hashvalue_t h,
 201         uint32_t rrset_flags, uint8_t* dname, size_t dnamelen,
 202         uint16_t type, uint16_t dclass)
 203 {
 204         if(p->hash == h && p->dname_len == dnamelen && p->type == type &&
 205                 p->rrset_class == dclass && p->flags == rrset_flags &&
 206                 dname_pkt_compare(pkt, dname, p->dname) == 0)
 207                 return 1;
 208         return 0;
 209 }
 210
 211
 212 struct rrset_parse*
 213 msgparse_hashtable_lookup(struct msg_parse* msg, ldns_buffer* pkt,
 214         hashvalue_t h, uint32_t rrset_flags, uint8_t* dname, size_t dnamelen,
 215         uint16_t type, uint16_t dclass)
 216 {
 217         struct rrset_parse* p = msg->hashtable[h & (PARSE_TABLE_SIZE-1)];
 218         while(p) {
 219                 if(rrset_parse_equals(p, pkt, h, rrset_flags, dname, dnamelen,
 220                         type, dclass))
 221                         return p;
 222                 p = p->rrset_bucket_next;
 223         }
 224         return NULL;
 225 }
 226
 227 /** return type networkformat that rrsig in packet covers */
 228 static int
 229 pkt_rrsig_covered(ldns_buffer* pkt, uint8_t* here, uint16_t* type)
 230 {
 231         size_t pos = ldns_buffer_position(pkt);
 232         ldns_buffer_set_position(pkt, (size_t)(here-ldns_buffer_begin(pkt)));
 233         /* ttl + len + size of small rrsig(rootlabel, no signature) */
 234         if(ldns_buffer_remaining(pkt) < 4+2+19)
 235                 return 0;
 236         ldns_buffer_skip(pkt, 4); /* ttl */
 237         if(ldns_buffer_read_u16(pkt) < 19) /* too short */ {
 238                 ldns_buffer_set_position(pkt, pos);
 239                 return 0;
 240         }
 241         *type = ldns_buffer_read_u16(pkt);
 242         ldns_buffer_set_position(pkt, pos);
 243         return 1;
 244 }
 245
 246 /** true if covered type equals prevtype */
 247 static int
 248 pkt_rrsig_covered_equals(ldns_buffer* pkt, uint8_t* here, uint16_t type)
 249 {
 250         uint16_t t;
 251         if(pkt_rrsig_covered(pkt, here, &t) && t == type)
 252                 return 1;
 253         return 0;
 254 }
 255
 256 void
 257 msgparse_bucket_remove(struct msg_parse* msg, struct rrset_parse* rrset)
 258 {
 259         struct rrset_parse** p;
 260         p = &msg->hashtable[ rrset->hash & (PARSE_TABLE_SIZE-1) ];
 261         while(*p) {
 262                 if(*p == rrset) {
 263                         *p = rrset->rrset_bucket_next;
 264                         return;
 265                 }
 266                 p = &( (*p)->rrset_bucket_next );
 267         }
 268 }
 269
 270 /** change section of rrset from previous to current section */
 271 static void
 272 change_section(struct msg_parse* msg, struct rrset_parse* rrset,
 273         ldns_pkt_section section)
 274 {
 275         struct rrset_parse *p, *prev;
 276         /* remove from list */
 277         if(section == rrset->section)
 278                 return;
 279         p = msg->rrset_first;
 280         prev = 0;
 281         while(p) {
 282                 if(p == rrset) {
 283                         if(prev) prev->rrset_all_next = p->rrset_all_next;
 284                         else    msg->rrset_first = p->rrset_all_next;
 285                         if(msg->rrset_last == rrset)
 286                                 msg->rrset_last = prev;
 287                         break;
 288                 }
 289                 prev = p;
 290                 p = p->rrset_all_next;
 291         }
 292         /* remove from count */
 293         switch(rrset->section) {
 294                 case LDNS_SECTION_ANSWER: msg->an_rrsets--; break;
 295                 case LDNS_SECTION_AUTHORITY: msg->ns_rrsets--; break;
 296                 case LDNS_SECTION_ADDITIONAL: msg->ar_rrsets--; break;
 297                 default: log_assert(0);
 298         }
 299         /* insert at end of list */
 300         rrset->rrset_all_next = 0;
 301         if(msg->rrset_last)
 302                 msg->rrset_last->rrset_all_next = rrset;
 303         else    msg->rrset_first = rrset;
 304         msg->rrset_last = rrset;
 305         /* up count of new section */
 306         switch(section) {
 307                 case LDNS_SECTION_AUTHORITY: msg->ns_rrsets++; break;
 308                 case LDNS_SECTION_ADDITIONAL: msg->ar_rrsets++; break;
 309                 default: log_assert(0);
 310         }
 311         rrset->section = section;
 312 }
 313
 314 /** see if rrset of type RRSIG contains sig over given type */
 315 static int
 316 rrset_has_sigover(ldns_buffer* pkt, struct rrset_parse* rrset, uint16_t type,
 317         int* hasother)
 318 {
 319         int res = 0;
 320         struct rr_parse* rr = rrset->rr_first;
 321         log_assert( rrset->type == LDNS_RR_TYPE_RRSIG );
 322         while(rr) {
 323                 if(pkt_rrsig_covered_equals(pkt, rr->ttl_data, type))
 324                         res = 1;
 325                 else    *hasother = 1;
 326                 rr = rr->next;
 327         }
 328         return res;
 329 }
 330
 331 /** move rrsigs from sigset to dataset */
 332 static int
 333 moveover_rrsigs(ldns_buffer* pkt, struct regional* region,
 334         struct rrset_parse* sigset, struct rrset_parse* dataset, int duplicate)
 335 {
 336         struct rr_parse* sig = sigset->rr_first;
 337         struct rr_parse* prev = NULL;
 338         struct rr_parse* insert;
 339         struct rr_parse* nextsig;
 340         while(sig) {
 341                 nextsig = sig->next;
 342                 if(pkt_rrsig_covered_equals(pkt, sig->ttl_data,
 343                         dataset->type)) {
 344                         if(duplicate) {
 345                                 /* new */
 346                                 insert = (struct rr_parse*)regional_alloc(
 347                                         region, sizeof(struct rr_parse));
 348                                 if(!insert) return 0;
 349                                 insert->outside_packet = 0;
 350                                 insert->ttl_data = sig->ttl_data;
 351                                 insert->size = sig->size;
 352                                 /* prev not used */
 353                         } else {
 354                                 /* remove from sigset */
 355                                 if(prev) prev->next = sig->next;
 356                                 else    sigset->rr_first = sig->next;
 357                                 if(sigset->rr_last == sig)
 358                                         sigset->rr_last = prev;
 359                                 sigset->rr_count--;
 360                                 sigset->size -= sig->size;
 361                                 insert = sig;
 362                                 /* prev not changed */
 363                         }
 364                         /* add to dataset */
 365                         dataset->rrsig_count++;
 366                         insert->next = 0;
 367                         if(dataset->rrsig_last)
 368                                 dataset->rrsig_last->next = insert;
 369                         else    dataset->rrsig_first = insert;
 370                         dataset->rrsig_last = insert;
 371                         dataset->size += insert->size;
 372                 } else  {
 373                         prev = sig;
 374                 }
 375                 sig = nextsig;
 376         }
 377         return 1;
 378 }
 379
 380 /** change an rrsig rrset for use as data rrset */
 381 static struct rrset_parse*
 382 change_rrsig_rrset(struct rrset_parse* sigset, struct msg_parse* msg,
 383         ldns_buffer* pkt, uint16_t datatype, uint32_t rrset_flags,
 384         int hasother, ldns_pkt_section section, struct regional* region)
 385 {
 386         struct rrset_parse* dataset = sigset;
 387         hashvalue_t hash = pkt_hash_rrset(pkt, sigset->dname, datatype,
 388                 sigset->rrset_class, rrset_flags);
 389         log_assert( sigset->type == LDNS_RR_TYPE_RRSIG );
 390         log_assert( datatype != LDNS_RR_TYPE_RRSIG );
 391         if(hasother) {
 392                 /* need to make new rrset to hold data type */
 393                 dataset = new_rrset(msg, sigset->dname, sigset->dname_len,
 394                         datatype, sigset->rrset_class, hash, rrset_flags,
 395                         section, region);
 396                 if(!dataset)
 397                         return NULL;
 398                 switch(section) {
 399                         case LDNS_SECTION_ANSWER: msg->an_rrsets++; break;
 400                         case LDNS_SECTION_AUTHORITY: msg->ns_rrsets++; break;
 401                         case LDNS_SECTION_ADDITIONAL: msg->ar_rrsets++; break;
 402                         default: log_assert(0);
 403                 }
 404                 if(!moveover_rrsigs(pkt, region, sigset, dataset,
 405                         msg->qtype == LDNS_RR_TYPE_RRSIG ||
 406                         (msg->qtype == LDNS_RR_TYPE_ANY &&
 407                         section != LDNS_SECTION_ANSWER) ))
 408                         return NULL;
 409                 return dataset;
 410         }
 411         /* changeover the type of the rrset to data set */
 412         msgparse_bucket_remove(msg, dataset);
 413         /* insert into new hash bucket */
 414         dataset->rrset_bucket_next = msg->hashtable[hash&(PARSE_TABLE_SIZE-1)];
 415         msg->hashtable[hash&(PARSE_TABLE_SIZE-1)] = dataset;
 416         dataset->hash = hash;
 417         /* use section of data item for result */
 418         change_section(msg, dataset, section);
 419         dataset->type = datatype;
 420         dataset->flags = rrset_flags;
 421         dataset->rrsig_count += dataset->rr_count;
 422         dataset->rr_count = 0;
 423         /* move sigs to end of siglist */
 424         if(dataset->rrsig_last)
 425                 dataset->rrsig_last->next = dataset->rr_first;
 426         else    dataset->rrsig_first = dataset->rr_first;
 427         dataset->rrsig_last = dataset->rr_last;
 428         dataset->rr_first = 0;
 429         dataset->rr_last = 0;
 430         return dataset;
 431 }
 432
 433 /** Find rrset. If equal to previous it is fast. hash if not so.
 434  * @param msg: the message with hash table.
 435  * @param pkt: the packet in wireformat (needed for compression ptrs).
 436  * @param dname: pointer to start of dname (compressed) in packet.
 437  * @param dnamelen: uncompressed wirefmt length of dname.
 438  * @param type: type of current rr.
 439  * @param dclass: class of current rr.
 440  * @param hash: hash value is returned if the rrset could not be found.
 441  * @param rrset_flags: is returned if the rrset could not be found.
 442  * @param prev_dname_first: dname of last seen RR. First seen dname.
 443  * @param prev_dname_last: dname of last seen RR. Last seen dname.
 444  * @param prev_dnamelen: dname len of last seen RR.
 445  * @param prev_type: type of last seen RR.
 446  * @param prev_dclass: class of last seen RR.
 447  * @param rrset_prev: last seen RRset.
 448  * @param section: the current section in the packet.
 449  * @param region: used to allocate temporary parsing data.
 450  * @return 0 on out of memory.
 451  */
 452 static int
 453 find_rrset(struct msg_parse* msg, ldns_buffer* pkt, uint8_t* dname,
 454         size_t dnamelen, uint16_t type, uint16_t dclass, hashvalue_t* hash,
 455         uint32_t* rrset_flags,
 456         uint8_t** prev_dname_first, uint8_t** prev_dname_last,
 457         size_t* prev_dnamelen, uint16_t* prev_type,
 458         uint16_t* prev_dclass, struct rrset_parse** rrset_prev,
 459         ldns_pkt_section section, struct regional* region)
 460 {
 461         hashvalue_t dname_h = pkt_hash_rrset_first(pkt, dname);
 462         uint16_t covtype;
 463         if(*rrset_prev) {
 464                 /* check if equal to previous item */
 465                 if(type == *prev_type && dclass == *prev_dclass &&
 466                         dnamelen == *prev_dnamelen &&
 467                         smart_compare(pkt, dname, *prev_dname_first,
 468                                 *prev_dname_last) == 0 &&
 469                         type != LDNS_RR_TYPE_RRSIG) {
 470                         /* same as previous */
 471                         *prev_dname_last = dname;
 472                         return 1;
 473                 }
 474                 /* check if rrsig over previous item */
 475                 if(type == LDNS_RR_TYPE_RRSIG && dclass == *prev_dclass &&
 476                         pkt_rrsig_covered_equals(pkt, ldns_buffer_current(pkt),
 477                                 *prev_type) &&
 478                         smart_compare(pkt, dname, *prev_dname_first,
 479                                 *prev_dname_last) == 0) {
 480                         /* covers previous */
 481                         *prev_dname_last = dname;
 482                         return 1;
 483                 }
 484         }
 485         /* find by hashing and lookup in hashtable */
 486         *rrset_flags = pkt_rrset_flags(pkt, type, section);
 487
 488         /* if rrsig - try to lookup matching data set first */
 489         if(type == LDNS_RR_TYPE_RRSIG && pkt_rrsig_covered(pkt,
 490                 ldns_buffer_current(pkt), &covtype)) {
 491                 *hash = pkt_hash_rrset_rest(dname_h, covtype, dclass,
 492                         *rrset_flags);
 493                 *rrset_prev = msgparse_hashtable_lookup(msg, pkt, *hash,
 494                         *rrset_flags, dname, dnamelen, covtype, dclass);
 495                 if(!*rrset_prev && covtype == LDNS_RR_TYPE_NSEC) {
 496                         /* if NSEC try with NSEC apex bit twiddled */
 497                         *rrset_flags ^= PACKED_RRSET_NSEC_AT_APEX;
 498                         *hash = pkt_hash_rrset_rest(dname_h, covtype, dclass,
 499                                 *rrset_flags);
 500                         *rrset_prev = msgparse_hashtable_lookup(msg, pkt,
 501                                 *hash, *rrset_flags, dname, dnamelen, covtype,
 502                                 dclass);
 503                         if(!*rrset_prev) /* untwiddle if not found */
 504                                 *rrset_flags ^= PACKED_RRSET_NSEC_AT_APEX;
 505                 }
 506                 if(!*rrset_prev && covtype == LDNS_RR_TYPE_SOA) {
 507                         /* if SOA try with SOA neg flag twiddled */
 508                         *rrset_flags ^= PACKED_RRSET_SOA_NEG;
 509                         *hash = pkt_hash_rrset_rest(dname_h, covtype, dclass,
 510                                 *rrset_flags);
 511                         *rrset_prev = msgparse_hashtable_lookup(msg, pkt,
 512                                 *hash, *rrset_flags, dname, dnamelen, covtype,
 513                                 dclass);
 514                         if(!*rrset_prev) /* untwiddle if not found */
 515                                 *rrset_flags ^= PACKED_RRSET_SOA_NEG;
 516                 }
 517                 if(*rrset_prev) {
 518                         *prev_dname_first = (*rrset_prev)->dname;
 519                         *prev_dname_last = dname;
 520                         *prev_dnamelen = dnamelen;
 521                         *prev_type = covtype;
 522                         *prev_dclass = dclass;
 523                         return 1;
 524                 }
 525         }
 526         if(type != LDNS_RR_TYPE_RRSIG) {
 527                 int hasother = 0;
 528                 /* find matching rrsig */
 529                 *hash = pkt_hash_rrset_rest(dname_h, LDNS_RR_TYPE_RRSIG,
 530                         dclass, 0);
 531                 *rrset_prev = msgparse_hashtable_lookup(msg, pkt, *hash,
 532                         0, dname, dnamelen, LDNS_RR_TYPE_RRSIG,
 533                         dclass);
 534                 if(*rrset_prev && rrset_has_sigover(pkt, *rrset_prev, type,
 535                         &hasother)) {
 536                         /* yes! */
 537                         *prev_dname_first = (*rrset_prev)->dname;
 538                         *prev_dname_last = dname;
 539                         *prev_dnamelen = dnamelen;
 540                         *prev_type = type;
 541                         *prev_dclass = dclass;
 542                         *rrset_prev = change_rrsig_rrset(*rrset_prev, msg,
 543                                 pkt, type, *rrset_flags, hasother, section,
 544                                 region);
 545                         if(!*rrset_prev) return 0;
 546                         return 1;
 547                 }
 548         }
 549
 550         *hash = pkt_hash_rrset_rest(dname_h, type, dclass, *rrset_flags);
 551         *rrset_prev = msgparse_hashtable_lookup(msg, pkt, *hash, *rrset_flags,
 552                 dname, dnamelen, type, dclass);
 553         if(*rrset_prev)
 554                 *prev_dname_first = (*rrset_prev)->dname;
 555         else    *prev_dname_first = dname;
 556         *prev_dname_last = dname;
 557         *prev_dnamelen = dnamelen;
 558         *prev_type = type;
 559         *prev_dclass = dclass;
 560         return 1;
 561 }
 562
 563 /**
 564  * Parse query section.
 565  * @param pkt: packet, position at call must be at start of query section.
 566  *      at end position is after query section.
 567  * @param msg: store results here.
 568  * @return: 0 if OK, or rcode on error.
 569  */
 570 static int
 571 parse_query_section(ldns_buffer* pkt, struct msg_parse* msg)
 572 {
 573         if(msg->qdcount == 0)
 574                 return 0;
 575         if(msg->qdcount > 1)
 576                 return LDNS_RCODE_FORMERR;
 577         log_assert(msg->qdcount == 1);
 578         if(ldns_buffer_remaining(pkt) <= 0)
 579                 return LDNS_RCODE_FORMERR;
 580         msg->qname = ldns_buffer_current(pkt);
 581         if((msg->qname_len = pkt_dname_len(pkt)) == 0)
 582                 return LDNS_RCODE_FORMERR;
 583         if(ldns_buffer_remaining(pkt) < sizeof(uint16_t)*2)
 584                 return LDNS_RCODE_FORMERR;
 585         msg->qtype = ldns_buffer_read_u16(pkt);
 586         msg->qclass = ldns_buffer_read_u16(pkt);
 587         return 0;
 588 }
 589
 590 size_t
 591 get_rdf_size(ldns_rdf_type rdf)
 592 {
 593         switch(rdf) {
 594                 case LDNS_RDF_TYPE_CLASS:
 595                 case LDNS_RDF_TYPE_ALG:
 596                 case LDNS_RDF_TYPE_INT8:
 597                         return 1;
 598                         break;
 599                 case LDNS_RDF_TYPE_INT16:
 600                 case LDNS_RDF_TYPE_TYPE:
 601                 case LDNS_RDF_TYPE_CERT_ALG:
 602                         return 2;
 603                         break;
 604                 case LDNS_RDF_TYPE_INT32:
 605                 case LDNS_RDF_TYPE_TIME:
 606                 case LDNS_RDF_TYPE_A:
 607                 case LDNS_RDF_TYPE_PERIOD:
 608                         return 4;
 609                         break;
 610                 case LDNS_RDF_TYPE_TSIGTIME:
 611                         return 6;
 612                         break;
 613                 case LDNS_RDF_TYPE_AAAA:
 614                         return 16;
 615                         break;
 616                 default:
 617                         log_assert(false); /* add type above */
 618                         /* only types that appear before a domain  *
 619                          * name are needed. rest is simply copied. */
 620         }
 621         return 0;
 622 }
 623
 624 /** calculate the size of one rr */
 625 static int
 626 calc_size(ldns_buffer* pkt, uint16_t type, struct rr_parse* rr)
 627 {
 628         const ldns_rr_descriptor* desc;
 629         uint16_t pkt_len; /* length of rr inside the packet */
 630         rr->size = sizeof(uint16_t); /* the rdatalen */
 631         ldns_buffer_skip(pkt, 4); /* skip ttl */
 632         pkt_len = ldns_buffer_read_u16(pkt);
 633         if(ldns_buffer_remaining(pkt) < pkt_len)
 634                 return 0;
 635         desc = ldns_rr_descript(type);
 636         if(pkt_len > 0 && desc && desc->_dname_count > 0) {
 637                 int count = (int)desc->_dname_count;
 638                 int rdf = 0;
 639                 size_t len;
 640                 size_t oldpos;
 641                 /* skip first part. */
 642                 while(pkt_len > 0 && count) {
 643                         switch(desc->_wireformat[rdf]) {
 644                         case LDNS_RDF_TYPE_DNAME:
 645                                 /* decompress every domain name */
 646                                 oldpos = ldns_buffer_position(pkt);
 647                                 if((len = pkt_dname_len(pkt)) == 0)
 648                                         return 0; /* malformed dname */
 649                                 if(ldns_buffer_position(pkt)-oldpos > pkt_len)
 650                                         return 0; /* dname exceeds rdata */
 651                                 pkt_len -= ldns_buffer_position(pkt)-oldpos;
 652                                 rr->size += len;
 653                                 count--;
 654                                 len = 0;
 655                                 break;
 656                         case LDNS_RDF_TYPE_STR:
 657                                 if(pkt_len < 1) {
 658                                         /* NOTREACHED, due to 'while(>0)' */
 659                                         return 0; /* len byte exceeds rdata */
 660                                 }
 661                                 len = ldns_buffer_current(pkt)[0] + 1;
 662                                 break;
 663                         default:
 664                                 len = get_rdf_size(desc->_wireformat[rdf]);
 665                         }
 666                         if(len) {
 667                                 if(pkt_len < len)
 668                                         return 0; /* exceeds rdata */
 669                                 pkt_len -= len;
 670                                 ldns_buffer_skip(pkt, (ssize_t)len);
 671                                 rr->size += len;
 672                         }
 673                         rdf++;
 674                 }
 675         }
 676         /* remaining rdata */
 677         rr->size += pkt_len;
 678         ldns_buffer_skip(pkt, (ssize_t)pkt_len);
 679         return 1;
 680 }
 681
 682 /** skip rr ttl and rdata */
 683 static int
 684 skip_ttl_rdata(ldns_buffer* pkt)
 685 {
 686         uint16_t rdatalen;
 687         if(ldns_buffer_remaining(pkt) < 6) /* ttl + rdatalen */
 688                 return 0;
 689         ldns_buffer_skip(pkt, 4); /* ttl */
 690         rdatalen = ldns_buffer_read_u16(pkt);
 691         if(ldns_buffer_remaining(pkt) < rdatalen)
 692                 return 0;
 693         ldns_buffer_skip(pkt, (ssize_t)rdatalen);
 694         return 1;
 695 }
 696
 697 /** see if RRSIG is a duplicate of another */
 698 static int
 699 sig_is_double(ldns_buffer* pkt, struct rrset_parse* rrset, uint8_t* ttldata)
 700 {
 701         uint16_t rlen, siglen;
 702         size_t pos = ldns_buffer_position(pkt);
 703         struct rr_parse* sig;
 704         if(ldns_buffer_remaining(pkt) < 6)
 705                 return 0;
 706         ldns_buffer_skip(pkt, 4); /* ttl */
 707         rlen = ldns_buffer_read_u16(pkt);
 708         if(ldns_buffer_remaining(pkt) < rlen) {
 709                 ldns_buffer_set_position(pkt, pos);
 710                 return 0;
 711         }
 712         ldns_buffer_set_position(pkt, pos);
 713
 714         sig = rrset->rrsig_first;
 715         while(sig) {
 716                 /* check if rdatalen is same */
 717                 memmove(&siglen, sig->ttl_data+4, sizeof(siglen));
 718                 siglen = ntohs(siglen);
 719                 /* checks if data in packet is exactly the same, this means
 720                  * also dname in rdata is the same, but rrsig is not allowed
 721                  * to have compressed dnames anyway. If it is compressed anyway
 722                  * it will lead to duplicate rrs for qtype=RRSIG. (or ANY).
 723                  *
 724                  * Cannot use sig->size because size of the other one is not
 725                  * calculated yet.
 726                  */
 727                 if(siglen == rlen) {
 728                         if(siglen>0 && memcmp(sig->ttl_data+6, ttldata+6,
 729                                 siglen) == 0) {
 730                                 /* same! */
 731                                 return 1;
 732                         }
 733                 }
 734                 sig = sig->next;
 735         }
 736         return 0;
 737 }
 738
 739 /** Add rr (from packet here) to rrset, skips rr */
 740 static int
 741 add_rr_to_rrset(struct rrset_parse* rrset, ldns_buffer* pkt,
 742         struct msg_parse* msg, struct regional* region,
 743         ldns_pkt_section section, uint16_t type)
 744 {
 745         struct rr_parse* rr;
 746         /* check section of rrset. */
 747         if(rrset->section != section && type != LDNS_RR_TYPE_RRSIG &&
 748                 rrset->type != LDNS_RR_TYPE_RRSIG) {
 749                 /* silently drop it - we drop the last part, since
 750                  * trust in rr data depends on the section it is in.
 751                  * the less trustworthy part is discarded.
 752                  * also the last part is more likely to be incomplete.
 753                  * RFC 2181: must put RRset only once in response. */
 754                 /*
 755                 verbose(VERB_QUERY, "Packet contains rrset data in "
 756                         "multiple sections, dropped last part.");
 757                 log_buf(VERB_QUERY, "packet was", pkt);
 758                 */
 759                 /* forwards */
 760                 if(!skip_ttl_rdata(pkt))
 761                         return LDNS_RCODE_FORMERR;
 762                 return 0;
 763         }
 764
 765         if( (msg->qtype == LDNS_RR_TYPE_RRSIG ||
 766              msg->qtype == LDNS_RR_TYPE_ANY)
 767             && sig_is_double(pkt, rrset, ldns_buffer_current(pkt))) {
 768                 if(!skip_ttl_rdata(pkt))
 769                         return LDNS_RCODE_FORMERR;
 770                 return 0;
 771         }
 772
 773         /* create rr */
 774         if(!(rr = (struct rr_parse*)regional_alloc(region, sizeof(*rr))))
 775                 return LDNS_RCODE_SERVFAIL;
 776         rr->outside_packet = 0;
 777         rr->ttl_data = ldns_buffer_current(pkt);
 778         rr->next = 0;
 779         if(type == LDNS_RR_TYPE_RRSIG && rrset->type != LDNS_RR_TYPE_RRSIG) {
 780                 if(rrset->rrsig_last)
 781                         rrset->rrsig_last->next = rr;
 782                 else    rrset->rrsig_first = rr;
 783                 rrset->rrsig_last = rr;
 784                 rrset->rrsig_count++;
 785         } else {
 786                 if(rrset->rr_last)
 787                         rrset->rr_last->next = rr;
 788                 else    rrset->rr_first = rr;
 789                 rrset->rr_last = rr;
 790                 rrset->rr_count++;
 791         }
 792
 793         /* calc decompressed size */
 794         if(!calc_size(pkt, type, rr))
 795                 return LDNS_RCODE_FORMERR;
 796         rrset->size += rr->size;
 797
 798         return 0;
 799 }
 800
 801 /**
 802  * Parse packet RR section, for answer, authority and additional sections.
 803  * @param pkt: packet, position at call must be at start of section.
 804  *      at end position is after section.
 805  * @param msg: store results here.
 806  * @param region: how to alloc results.
 807  * @param section: section enum.
 808  * @param num_rrs: how many rrs are in the section.
 809  * @param num_rrsets: returns number of rrsets in the section.
 810  * @return: 0 if OK, or rcode on error.
 811  */
 812 static int
 813 parse_section(ldns_buffer* pkt, struct msg_parse* msg,
 814         struct regional* region, ldns_pkt_section section,
 815         uint16_t num_rrs, size_t* num_rrsets)
 816 {
 817         uint16_t i;
 818         uint8_t* dname, *prev_dname_f = NULL, *prev_dname_l = NULL;
 819         size_t dnamelen, prev_dnamelen = 0;
 820         uint16_t type, prev_type = 0;
 821         uint16_t dclass, prev_dclass = 0;
 822         uint32_t rrset_flags = 0;
 823         hashvalue_t hash = 0;
 824         struct rrset_parse* rrset = NULL;
 825         int r;
 826
 827         if(num_rrs == 0)
 828                 return 0;
 829         if(ldns_buffer_remaining(pkt) <= 0)
 830                 return LDNS_RCODE_FORMERR;
 831         for(i=0; i<num_rrs; i++) {
 832                 /* parse this RR. */
 833                 dname = ldns_buffer_current(pkt);
 834                 if((dnamelen = pkt_dname_len(pkt)) == 0)
 835                         return LDNS_RCODE_FORMERR;
 836                 if(ldns_buffer_remaining(pkt) < 10) /* type, class, ttl, len */
 837                         return LDNS_RCODE_FORMERR;
 838                 type = ldns_buffer_read_u16(pkt);
 839                 ldns_buffer_read(pkt, &dclass, sizeof(dclass));
 840
 841                 if(0) { /* debug show what is being parsed. */
 842                         if(type == LDNS_RR_TYPE_RRSIG) {
 843                                 uint16_t t;
 844                                 if(pkt_rrsig_covered(pkt,
 845                                         ldns_buffer_current(pkt), &t))
 846                                         fprintf(stderr, "parse of %s(%d) [%s(%d)]",
 847                                         ldns_rr_descript(type)?
 848                                         ldns_rr_descript(type)->_name: "??",
 849                                         (int)type,
 850                                         ldns_rr_descript(t)?
 851                                         ldns_rr_descript(t)->_name: "??",
 852                                         (int)t);
 853                         } else
 854                           fprintf(stderr, "parse of %s(%d)",
 855                                 ldns_rr_descript(type)?
 856                                 ldns_rr_descript(type)->_name: "??",
 857                                 (int)type);
 858                         fprintf(stderr, " %s(%d) ",
 859                                 ldns_lookup_by_id(ldns_rr_classes,
 860                                 (int)ntohs(dclass))?ldns_lookup_by_id(
 861                                 ldns_rr_classes, (int)ntohs(dclass))->name:
 862                                 "??", (int)ntohs(dclass));
 863                         dname_print(stderr, pkt, dname);
 864                         fprintf(stderr, "\n");
 865                 }
 866
 867                 /* see if it is part of an existing RR set */
 868                 if(!find_rrset(msg, pkt, dname, dnamelen, type, dclass, &hash,
 869                         &rrset_flags, &prev_dname_f, &prev_dname_l,
 870                         &prev_dnamelen, &prev_type, &prev_dclass, &rrset,
 871                         section, region))
 872                         return LDNS_RCODE_SERVFAIL;
 873                 if(!rrset) {
 874                         /* it is a new RR set. hash&flags already calculated.*/
 875                         (*num_rrsets)++;
 876                         rrset = new_rrset(msg, dname, dnamelen, type, dclass,
 877                                 hash, rrset_flags, section, region);
 878                         if(!rrset)
 879                                 return LDNS_RCODE_SERVFAIL;
 880                 }
 881                 else if(0)      {
 882                         fprintf(stderr, "is part of existing: ");
 883                         dname_print(stderr, pkt, rrset->dname);
 884                         fprintf(stderr, " type %s(%d)\n",
 885                                 ldns_rr_descript(rrset->type)?
 886                                 ldns_rr_descript(rrset->type)->_name: "??",
 887                                 (int)rrset->type);
 888                 }
 889                 /* add to rrset. */
 890                 if((r=add_rr_to_rrset(rrset, pkt, msg, region, section,
 891                         type)) != 0)
 892                         return r;
 893         }
 894         return 0;
 895 }
 896
 897 int
 898 parse_packet(ldns_buffer* pkt, struct msg_parse* msg, struct regional* region)
 899 {
 900         int ret;
 901         if(ldns_buffer_remaining(pkt) < LDNS_HEADER_SIZE)
 902                 return LDNS_RCODE_FORMERR;
 903         /* read the header */
 904         ldns_buffer_read(pkt, &msg->id, sizeof(uint16_t));
 905         msg->flags = ldns_buffer_read_u16(pkt);
 906         msg->qdcount = ldns_buffer_read_u16(pkt);
 907         msg->ancount = ldns_buffer_read_u16(pkt);
 908         msg->nscount = ldns_buffer_read_u16(pkt);
 909         msg->arcount = ldns_buffer_read_u16(pkt);
 910         if(msg->qdcount > 1)
 911                 return LDNS_RCODE_FORMERR;
 912         if((ret = parse_query_section(pkt, msg)) != 0)
 913                 return ret;
 914         if((ret = parse_section(pkt, msg, region, LDNS_SECTION_ANSWER,
 915                 msg->ancount, &msg->an_rrsets)) != 0)
 916                 return ret;
 917         if((ret = parse_section(pkt, msg, region, LDNS_SECTION_AUTHORITY,
 918                 msg->nscount, &msg->ns_rrsets)) != 0)
 919                 return ret;
 920         if(ldns_buffer_remaining(pkt) == 0 && msg->arcount == 1) {
 921                 /* BIND accepts leniently that an EDNS record is missing.
 922                  * so, we do too. */
 923         } else if((ret = parse_section(pkt, msg, region,
 924                 LDNS_SECTION_ADDITIONAL, msg->arcount, &msg->ar_rrsets)) != 0)
 925                 return ret;
 926         /* if(ldns_buffer_remaining(pkt) > 0) { */
 927                 /* there is spurious data at end of packet. ignore */
 928         /* } */
 929         msg->rrset_count = msg->an_rrsets + msg->ns_rrsets + msg->ar_rrsets;
 930         return 0;
 931 }
 932
 933 int
 934 parse_extract_edns(struct msg_parse* msg, struct edns_data* edns)
 935 {
 936         struct rrset_parse* rrset = msg->rrset_first;
 937         struct rrset_parse* prev = 0;
 938         struct rrset_parse* found = 0;
 939         struct rrset_parse* found_prev = 0;
 940         /* since the class encodes the UDP size, we cannot use hash table to
 941          * find the EDNS OPT record. Scan the packet. */
 942         while(rrset) {
 943                 if(rrset->type == LDNS_RR_TYPE_OPT) {
 944                         /* only one OPT RR allowed. */
 945                         if(found) return LDNS_RCODE_FORMERR;
 946                         /* found it! */
 947                         found_prev = prev;
 948                         found = rrset;
 949                 }
 950                 prev = rrset;
 951                 rrset = rrset->rrset_all_next;
 952         }
 953         if(!found) {
 954                 memset(edns, 0, sizeof(*edns));
 955                 edns->udp_size = 512;
 956                 return 0;
 957         }
 958         /* check the found RRset */
 959         /* most lenient check possible. ignore dname, use last opt */
 960         if(found->section != LDNS_SECTION_ADDITIONAL)
 961                 return LDNS_RCODE_FORMERR;
 962         if(found->rr_count == 0)
 963                 return LDNS_RCODE_FORMERR;
 964         if(0) { /* strict checking of dname and RRcount */
 965                 if(found->dname_len != 1 || !found->dname
 966                         || found->dname[0] != 0) return LDNS_RCODE_FORMERR;
 967                 if(found->rr_count != 1) return LDNS_RCODE_FORMERR;
 968         }
 969         log_assert(found->rr_first && found->rr_last);
 970
 971         /* remove from packet */
 972         if(found_prev)  found_prev->rrset_all_next = found->rrset_all_next;
 973         else    msg->rrset_first = found->rrset_all_next;
 974         if(found == msg->rrset_last)
 975                 msg->rrset_last = found_prev;
 976         msg->arcount --;
 977         msg->ar_rrsets --;
 978         msg->rrset_count --;
 979
 980         /* take the data ! */
 981         edns->edns_present = 1;
 982         edns->ext_rcode = found->rr_last->ttl_data[0];
 983         edns->edns_version = found->rr_last->ttl_data[1];
 984         edns->bits = ldns_read_uint16(&found->rr_last->ttl_data[2]);
 985         edns->udp_size = ntohs(found->rrset_class);
 986         /* ignore rdata and rrsigs */
 987         return 0;
 988 }
 989
 990 int
 991 parse_edns_from_pkt(ldns_buffer* pkt, struct edns_data* edns)
 992 {
 993         log_assert(LDNS_QDCOUNT(ldns_buffer_begin(pkt)) == 1);
 994         log_assert(LDNS_ANCOUNT(ldns_buffer_begin(pkt)) == 0);
 995         log_assert(LDNS_NSCOUNT(ldns_buffer_begin(pkt)) == 0);
 996         /* check edns section is present */
 997         if(LDNS_ARCOUNT(ldns_buffer_begin(pkt)) > 1) {
 998                 return LDNS_RCODE_FORMERR;
 999         }
1000         if(LDNS_ARCOUNT(ldns_buffer_begin(pkt)) == 0) {
1001                 memset(edns, 0, sizeof(*edns));
1002                 edns->udp_size = 512;
1003                 return 0;
1004         }
1005         /* domain name must be the root of length 1. */
1006         if(pkt_dname_len(pkt) != 1)
1007                 return LDNS_RCODE_FORMERR;
1008         if(ldns_buffer_remaining(pkt) < 10) /* type, class, ttl, rdatalen */
1009                 return LDNS_RCODE_FORMERR;
1010         if(ldns_buffer_read_u16(pkt) != LDNS_RR_TYPE_OPT)
1011                 return LDNS_RCODE_FORMERR;
1012         edns->edns_present = 1;
1013         edns->udp_size = ldns_buffer_read_u16(pkt); /* class is udp size */
1014         edns->ext_rcode = ldns_buffer_read_u8(pkt); /* ttl used for bits */
1015         edns->edns_version = ldns_buffer_read_u8(pkt);
1016         edns->bits = ldns_buffer_read_u16(pkt);
1017         /* ignore rdata and rrsigs */
1018         return 0;
1019 }