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 } 489