contrib/unbound/util/data/packed_rrset.c

   1 /*
   2  * util/data/packed_rrset.c - data storage for a set of resource records.
   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 the data storage for RRsets.
  40  */
  41
  42 #include "config.h"
  43 #include <ldns/wire2host.h>
  44 #include "util/data/packed_rrset.h"
  45 #include "util/data/dname.h"
  46 #include "util/storage/lookup3.h"
  47 #include "util/log.h"
  48 #include "util/alloc.h"
  49 #include "util/regional.h"
  50 #include "util/net_help.h"
  51
  52 void
  53 ub_packed_rrset_parsedelete(struct ub_packed_rrset_key* pkey,
  54         struct alloc_cache* alloc)
  55 {
  56         if(!pkey)
  57                 return;
  58         if(pkey->entry.data)
  59                 free(pkey->entry.data);
  60         pkey->entry.data = NULL;
  61         if(pkey->rk.dname)
  62                 free(pkey->rk.dname);
  63         pkey->rk.dname = NULL;
  64         pkey->id = 0;
  65         alloc_special_release(alloc, pkey);
  66 }
  67
  68 size_t
  69 ub_rrset_sizefunc(void* key, void* data)
  70 {
  71         struct ub_packed_rrset_key* k = (struct ub_packed_rrset_key*)key;
  72         struct packed_rrset_data* d = (struct packed_rrset_data*)data;
  73         size_t s = sizeof(struct ub_packed_rrset_key) + k->rk.dname_len;
  74         s += packed_rrset_sizeof(d) + lock_get_mem(&k->entry.lock);
  75         return s;
  76 }
  77
  78 size_t
  79 packed_rrset_sizeof(struct packed_rrset_data* d)
  80 {
  81         size_t s;
  82         if(d->rrsig_count > 0) {
  83                 s = ((uint8_t*)d->rr_data[d->count+d->rrsig_count-1] -
  84                         (uint8_t*)d) + d->rr_len[d->count+d->rrsig_count-1];
  85         } else {
  86                 log_assert(d->count > 0);
  87                 s = ((uint8_t*)d->rr_data[d->count-1] - (uint8_t*)d) +
  88                         d->rr_len[d->count-1];
  89         }
  90         return s;
  91 }
  92
  93 int
  94 ub_rrset_compare(void* k1, void* k2)
  95 {
  96         struct ub_packed_rrset_key* key1 = (struct ub_packed_rrset_key*)k1;
  97         struct ub_packed_rrset_key* key2 = (struct ub_packed_rrset_key*)k2;
  98         int c;
  99         if(key1 == key2)
 100                 return 0;
 101         if(key1->rk.type != key2->rk.type) {
 102                 if(key1->rk.type < key2->rk.type)
 103                         return -1;
 104                 return 1;
 105         }
 106         if(key1->rk.dname_len != key2->rk.dname_len) {
 107                 if(key1->rk.dname_len < key2->rk.dname_len)
 108                         return -1;
 109                 return 1;
 110         }
 111         if((c=query_dname_compare(key1->rk.dname, key2->rk.dname)) != 0)
 112                 return c;
 113         if(key1->rk.rrset_class != key2->rk.rrset_class) {
 114                 if(key1->rk.rrset_class < key2->rk.rrset_class)
 115                         return -1;
 116                 return 1;
 117         }
 118         if(key1->rk.flags != key2->rk.flags) {
 119                 if(key1->rk.flags < key2->rk.flags)
 120                         return -1;
 121                 return 1;
 122         }
 123         return 0;
 124 }
 125
 126 void
 127 ub_rrset_key_delete(void* key, void* userdata)
 128 {
 129         struct ub_packed_rrset_key* k = (struct ub_packed_rrset_key*)key;
 130         struct alloc_cache* a = (struct alloc_cache*)userdata;
 131         k->id = 0;
 132         free(k->rk.dname);
 133         k->rk.dname = NULL;
 134         alloc_special_release(a, k);
 135 }
 136
 137 void
 138 rrset_data_delete(void* data, void* ATTR_UNUSED(userdata))
 139 {
 140         struct packed_rrset_data* d = (struct packed_rrset_data*)data;
 141         free(d);
 142 }
 143
 144 int
 145 rrsetdata_equal(struct packed_rrset_data* d1, struct packed_rrset_data* d2)
 146 {
 147         size_t i;
 148         size_t total;
 149         if(d1->count != d2->count || d1->rrsig_count != d2->rrsig_count)
 150                 return 0;
 151         total = d1->count + d1->rrsig_count;
 152         for(i=0; i<total; i++) {
 153                 if(d1->rr_len[i] != d2->rr_len[i])
 154                         return 0;
 155                 if(memcmp(d1->rr_data[i], d2->rr_data[i], d1->rr_len[i]) != 0)
 156                         return 0;
 157         }
 158         return 1;
 159 }
 160
 161 hashvalue_t
 162 rrset_key_hash(struct packed_rrset_key* key)
 163 {
 164         /* type is hashed in host order */
 165         uint16_t t = ntohs(key->type);
 166         /* Note this MUST be identical to pkt_hash_rrset in msgparse.c */
 167         /* this routine does not have a compressed name */
 168         hashvalue_t h = 0xab;
 169         h = dname_query_hash(key->dname, h);
 170         h = hashlittle(&t, sizeof(t), h);
 171         h = hashlittle(&key->rrset_class, sizeof(uint16_t), h);
 172         h = hashlittle(&key->flags, sizeof(uint32_t), h);
 173         return h;
 174 }
 175
 176 void
 177 packed_rrset_ptr_fixup(struct packed_rrset_data* data)
 178 {
 179         size_t i;
 180         size_t total = data->count + data->rrsig_count;
 181         uint8_t* nextrdata;
 182         /* fixup pointers in packed rrset data */
 183         data->rr_len = (size_t*)((uint8_t*)data +
 184                 sizeof(struct packed_rrset_data));
 185         data->rr_data = (uint8_t**)&(data->rr_len[total]);
 186         data->rr_ttl = (uint32_t*)&(data->rr_data[total]);
 187         nextrdata = (uint8_t*)&(data->rr_ttl[total]);
 188         for(i=0; i<total; i++) {
 189                 data->rr_data[i] = nextrdata;
 190                 nextrdata += data->rr_len[i];
 191         }
 192 }
 193
 194 void
 195 get_cname_target(struct ub_packed_rrset_key* rrset, uint8_t** dname,
 196         size_t* dname_len)
 197 {
 198         struct packed_rrset_data* d;
 199         size_t len;
 200         if(ntohs(rrset->rk.type) != LDNS_RR_TYPE_CNAME &&
 201                 ntohs(rrset->rk.type) != LDNS_RR_TYPE_DNAME)
 202                 return;
 203         d = (struct packed_rrset_data*)rrset->entry.data;
 204         if(d->count < 1)
 205                 return;
 206         if(d->rr_len[0] < 3) /* at least rdatalen + 0byte root label */
 207                 return;
 208         len = ldns_read_uint16(d->rr_data[0]);
 209         if(len != d->rr_len[0] - sizeof(uint16_t))
 210                 return;
 211         if(dname_valid(d->rr_data[0]+sizeof(uint16_t), len) != len)
 212                 return;
 213         *dname = d->rr_data[0]+sizeof(uint16_t);
 214         *dname_len = len;
 215 }
 216
 217 void
 218 packed_rrset_ttl_add(struct packed_rrset_data* data, uint32_t add)
 219 {
 220         size_t i;
 221         size_t total = data->count + data->rrsig_count;
 222         data->ttl += add;
 223         for(i=0; i<total; i++)
 224                 data->rr_ttl[i] += add;
 225 }
 226
 227 const char*
 228 rrset_trust_to_string(enum rrset_trust s)
 229 {
 230         switch(s) {
 231         case rrset_trust_none:          return "rrset_trust_none";
 232         case rrset_trust_add_noAA:      return "rrset_trust_add_noAA";
 233         case rrset_trust_auth_noAA:     return "rrset_trust_auth_noAA";
 234         case rrset_trust_add_AA:        return "rrset_trust_add_AA";
 235         case rrset_trust_nonauth_ans_AA:return "rrset_trust_nonauth_ans_AA";
 236         case rrset_trust_ans_noAA:      return "rrset_trust_ans_noAA";
 237         case rrset_trust_glue:          return "rrset_trust_glue";
 238         case rrset_trust_auth_AA:       return "rrset_trust_auth_AA";
 239         case rrset_trust_ans_AA:        return "rrset_trust_ans_AA";
 240         case rrset_trust_sec_noglue:    return "rrset_trust_sec_noglue";
 241         case rrset_trust_prim_noglue:   return "rrset_trust_prim_noglue";
 242         case rrset_trust_validated:     return "rrset_trust_validated";
 243         case rrset_trust_ultimate:      return "rrset_trust_ultimate";
 244         }
 245         return "unknown_rrset_trust_value";
 246 }
 247
 248 const char*
 249 sec_status_to_string(enum sec_status s)
 250 {
 251         switch(s) {
 252         case sec_status_unchecked:      return "sec_status_unchecked";
 253         case sec_status_bogus:          return "sec_status_bogus";
 254         case sec_status_indeterminate:  return "sec_status_indeterminate";
 255         case sec_status_insecure:       return "sec_status_insecure";
 256         case sec_status_secure:         return "sec_status_secure";
 257         }
 258         return "unknown_sec_status_value";
 259 }
 260
 261 void log_rrset_key(enum verbosity_value v, const char* str,
 262         struct ub_packed_rrset_key* rrset)
 263 {
 264         if(verbosity >= v)
 265                 log_nametypeclass(v, str, rrset->rk.dname,
 266                         ntohs(rrset->rk.type), ntohs(rrset->rk.rrset_class));
 267 }
 268
 269 uint32_t
 270 ub_packed_rrset_ttl(struct ub_packed_rrset_key* key)
 271 {
 272         struct packed_rrset_data* d = (struct packed_rrset_data*)key->
 273                 entry.data;
 274         return d->ttl;
 275 }
 276
 277 struct ub_packed_rrset_key*
 278 packed_rrset_copy_region(struct ub_packed_rrset_key* key,
 279         struct regional* region, uint32_t now)
 280 {
 281         struct ub_packed_rrset_key* ck = regional_alloc(region,
 282                 sizeof(struct ub_packed_rrset_key));
 283         struct packed_rrset_data* d;
 284         struct packed_rrset_data* data = (struct packed_rrset_data*)
 285                 key->entry.data;
 286         size_t dsize, i;
 287         if(!ck)
 288                 return NULL;
 289         ck->id = key->id;
 290         memset(&ck->entry, 0, sizeof(ck->entry));
 291         ck->entry.hash = key->entry.hash;
 292         ck->entry.key = ck;
 293         ck->rk = key->rk;
 294         ck->rk.dname = regional_alloc_init(region, key->rk.dname,
 295                 key->rk.dname_len);
 296         if(!ck->rk.dname)
 297                 return NULL;
 298         dsize = packed_rrset_sizeof(data);
 299         d = (struct packed_rrset_data*)regional_alloc_init(region, data, dsize);
 300         if(!d)
 301                 return NULL;
 302         ck->entry.data = d;
 303         packed_rrset_ptr_fixup(d);
 304         /* make TTLs relative - once per rrset */
 305         for(i=0; i<d->count + d->rrsig_count; i++) {
 306                 if(d->rr_ttl[i] < now)
 307                         d->rr_ttl[i] = 0;
 308                 else    d->rr_ttl[i] -= now;
 309         }
 310         if(d->ttl < now)
 311                 d->ttl = 0;
 312         else    d->ttl -= now;
 313         return ck;
 314 }
 315
 316 struct ub_packed_rrset_key*
 317 packed_rrset_copy_alloc(struct ub_packed_rrset_key* key,
 318         struct alloc_cache* alloc, uint32_t now)
 319 {
 320         struct packed_rrset_data* fd, *dd;
 321         struct ub_packed_rrset_key* dk = alloc_special_obtain(alloc);
 322         if(!dk) return NULL;
 323         fd = (struct packed_rrset_data*)key->entry.data;
 324         dk->entry.hash = key->entry.hash;
 325         dk->rk = key->rk;
 326         dk->rk.dname = (uint8_t*)memdup(key->rk.dname, key->rk.dname_len);
 327         if(!dk->rk.dname) {
 328                 alloc_special_release(alloc, dk);
 329                 return NULL;
 330         }
 331         dd = (struct packed_rrset_data*)memdup(fd, packed_rrset_sizeof(fd));
 332         if(!dd) {
 333                 free(dk->rk.dname);
 334                 alloc_special_release(alloc, dk);
 335                 return NULL;
 336         }
 337         packed_rrset_ptr_fixup(dd);
 338         dk->entry.data = (void*)dd;
 339         packed_rrset_ttl_add(dd, now);
 340         return dk;
 341 }
 342
 343 struct ub_packed_rrset_key*
 344 ub_packed_rrset_heap_key(ldns_rr_list* rrset)
 345 {
 346         struct ub_packed_rrset_key* k;
 347         ldns_rr* rr;
 348         if(!rrset)
 349                 return NULL;
 350         rr = ldns_rr_list_rr(rrset, 0);
 351         if(!rr)
 352                 return NULL;
 353         k = (struct ub_packed_rrset_key*)calloc(1, sizeof(*k));
 354         if(!k)
 355                 return NULL;
 356         k->rk.type = htons(ldns_rr_get_type(rr));
 357         k->rk.rrset_class = htons(ldns_rr_get_class(rr));
 358         k->rk.dname_len = ldns_rdf_size(ldns_rr_owner(rr));
 359         k->rk.dname = memdup(ldns_rdf_data(ldns_rr_owner(rr)),
 360                 ldns_rdf_size(ldns_rr_owner(rr)));
 361         if(!k->rk.dname) {
 362                 free(k);
 363                 return NULL;
 364         }
 365         return k;
 366 }
 367
 368 struct packed_rrset_data*
 369 packed_rrset_heap_data(ldns_rr_list* rrset)
 370 {
 371         struct packed_rrset_data* data;
 372         size_t count=0, rrsig_count=0, len=0, i, j, total;
 373         uint8_t* nextrdata;
 374         if(!rrset || ldns_rr_list_rr_count(rrset)==0)
 375                 return NULL;
 376         /* count sizes */
 377         for(i=0; i<ldns_rr_list_rr_count(rrset); i++) {
 378                 ldns_rr* rr = ldns_rr_list_rr(rrset, i);
 379                 if(ldns_rr_get_type(rr) == LDNS_RR_TYPE_RRSIG)
 380                         rrsig_count++;
 381                 else    count++;
 382                 for(j=0; j<ldns_rr_rd_count(rr); j++)
 383                         len += ldns_rdf_size(ldns_rr_rdf(rr, j));
 384                 len += 2; /* sizeof the rdlength */
 385         }
 386
 387         /* allocate */
 388         total = count + rrsig_count;
 389         len += sizeof(*data) + total*(sizeof(size_t) + sizeof(uint32_t) +
 390                 sizeof(uint8_t*));
 391         data = (struct packed_rrset_data*)calloc(1, len);
 392         if(!data)
 393                 return NULL;
 394
 395         /* fill it */
 396         data->ttl = ldns_rr_ttl(ldns_rr_list_rr(rrset, 0));
 397         data->count = count;
 398         data->rrsig_count = rrsig_count;
 399         data->rr_len = (size_t*)((uint8_t*)data +
 400                 sizeof(struct packed_rrset_data));
 401         data->rr_data = (uint8_t**)&(data->rr_len[total]);
 402         data->rr_ttl = (uint32_t*)&(data->rr_data[total]);
 403         nextrdata = (uint8_t*)&(data->rr_ttl[total]);
 404
 405         /* fill out len, ttl, fields */
 406         for(i=0; i<total; i++) {
 407                 ldns_rr* rr = ldns_rr_list_rr(rrset, i);
 408                 data->rr_ttl[i] = ldns_rr_ttl(rr);
 409                 if(data->rr_ttl[i] < data->ttl)
 410                         data->ttl = data->rr_ttl[i];
 411                 data->rr_len[i] = 2; /* the rdlength */
 412                 for(j=0; j<ldns_rr_rd_count(rr); j++)
 413                         data->rr_len[i] += ldns_rdf_size(ldns_rr_rdf(rr, j));
 414         }
 415
 416         /* fixup rest of ptrs */
 417         for(i=0; i<total; i++) {
 418                 data->rr_data[i] = nextrdata;
 419                 nextrdata += data->rr_len[i];
 420         }
 421
 422         /* copy data in there */
 423         for(i=0; i<total; i++) {
 424                 ldns_rr* rr = ldns_rr_list_rr(rrset, i);
 425                 uint16_t rdlen = htons(data->rr_len[i]-2);
 426                 size_t p = sizeof(rdlen);
 427                 memmove(data->rr_data[i], &rdlen, p);
 428                 for(j=0; j<ldns_rr_rd_count(rr); j++) {
 429                         ldns_rdf* rd = ldns_rr_rdf(rr, j);
 430                         memmove(data->rr_data[i]+p, ldns_rdf_data(rd),
 431                                 ldns_rdf_size(rd));
 432                         p += ldns_rdf_size(rd);
 433                 }
 434         }
 435
 436         if(data->rrsig_count && data->count == 0) {
 437                 data->count = data->rrsig_count; /* rrset type is RRSIG */
 438                 data->rrsig_count = 0;
 439         }
 440         return data;
 441 }
 442
 443 /** convert i'th rr to ldns_rr */
 444 static ldns_rr*
 445 torr(struct ub_packed_rrset_key* k, ldns_buffer* buf, size_t i)
 446 {
 447         struct packed_rrset_data* d = (struct packed_rrset_data*)k->entry.data;
 448         ldns_rr* rr = NULL;
 449         size_t pos = 0;
 450         ldns_status s;
 451         ldns_buffer_clear(buf);
 452         ldns_buffer_write(buf, k->rk.dname, k->rk.dname_len);
 453         if(i < d->count)
 454                 ldns_buffer_write(buf, &k->rk.type, sizeof(uint16_t));
 455         else    ldns_buffer_write_u16(buf, LDNS_RR_TYPE_RRSIG);
 456         ldns_buffer_write(buf, &k->rk.rrset_class, sizeof(uint16_t));
 457         ldns_buffer_write_u32(buf, d->rr_ttl[i]);
 458         ldns_buffer_write(buf, d->rr_data[i], d->rr_len[i]);
 459         ldns_buffer_flip(buf);
 460         s = ldns_wire2rr(&rr, ldns_buffer_begin(buf), ldns_buffer_limit(buf),
 461                 &pos, LDNS_SECTION_ANSWER);
 462         if(s == LDNS_STATUS_OK)
 463                 return rr;
 464         return NULL;
 465 }
 466
 467 ldns_rr_list*
 468 packed_rrset_to_rr_list(struct ub_packed_rrset_key* k, ldns_buffer* buf)
 469 {
 470         struct packed_rrset_data* d = (struct packed_rrset_data*)k->entry.data;
 471         ldns_rr_list* r = ldns_rr_list_new();
 472         size_t i;
 473         if(!r)
 474                 return NULL;
 475         for(i=0; i<d->count+d->rrsig_count; i++) {
 476                 ldns_rr* rr = torr(k, buf, i);
 477                 if(!rr) {
 478                         ldns_rr_list_deep_free(r);
 479                         return NULL;
 480                 }
 481                 if(!ldns_rr_list_push_rr(r, rr)) {
 482                         ldns_rr_free(rr);
 483                         ldns_rr_list_deep_free(r);
 484                         return NULL;
 485                 }
 486         }
 487         return r;
 488 }