contrib/bind-9.3/lib/dns/rdataset.c

   1 /*
   2  * Copyright (C) 2004, 2006  Internet Systems Consortium, Inc. ("ISC")
   3  * Copyright (C) 1999-2003  Internet Software Consortium.
   4  *
   5  * Permission to use, copy, modify, and distribute this software for any
   6  * purpose with or without fee is hereby granted, provided that the above
   7  * copyright notice and this permission notice appear in all copies.
   8  *
   9  * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
  10  * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
  11  * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
  12  * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
  13  * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
  14  * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  15  * PERFORMANCE OF THIS SOFTWARE.
  16  */
  17
  18 /* $Id: rdataset.c,v 1.58.2.2.2.12 2006/03/02 00:37:20 marka Exp $ */
  19
  20 #include <config.h>
  21
  22 #include <stdlib.h>
  23
  24 #include <isc/buffer.h>
  25 #include <isc/mem.h>
  26 #include <isc/random.h>
  27 #include <isc/util.h>
  28
  29 #include <dns/name.h>
  30 #include <dns/ncache.h>
  31 #include <dns/rdata.h>
  32 #include <dns/rdataset.h>
  33 #include <dns/compress.h>
  34
  35 void
  36 dns_rdataset_init(dns_rdataset_t *rdataset) {
  37
  38         /*
  39          * Make 'rdataset' a valid, disassociated rdataset.
  40          */
  41
  42         REQUIRE(rdataset != NULL);
  43
  44         rdataset->magic = DNS_RDATASET_MAGIC;
  45         rdataset->methods = NULL;
  46         ISC_LINK_INIT(rdataset, link);
  47         rdataset->rdclass = 0;
  48         rdataset->type = 0;
  49         rdataset->ttl = 0;
  50         rdataset->trust = 0;
  51         rdataset->covers = 0;
  52         rdataset->attributes = 0;
  53         rdataset->count = ISC_UINT32_MAX;
  54         rdataset->private1 = NULL;
  55         rdataset->private2 = NULL;
  56         rdataset->private3 = NULL;
  57         rdataset->privateuint4 = 0;
  58         rdataset->private5 = NULL;
  59         rdataset->private6 = NULL;
  60 }
  61
  62 void
  63 dns_rdataset_invalidate(dns_rdataset_t *rdataset) {
  64
  65         /*
  66          * Invalidate 'rdataset'.
  67          */
  68
  69         REQUIRE(DNS_RDATASET_VALID(rdataset));
  70         REQUIRE(rdataset->methods == NULL);
  71
  72         rdataset->magic = 0;
  73         ISC_LINK_INIT(rdataset, link);
  74         rdataset->rdclass = 0;
  75         rdataset->type = 0;
  76         rdataset->ttl = 0;
  77         rdataset->trust = 0;
  78         rdataset->covers = 0;
  79         rdataset->attributes = 0;
  80         rdataset->count = ISC_UINT32_MAX;
  81         rdataset->private1 = NULL;
  82         rdataset->private2 = NULL;
  83         rdataset->private3 = NULL;
  84         rdataset->privateuint4 = 0;
  85         rdataset->private5 = NULL;
  86 }
  87
  88 void
  89 dns_rdataset_disassociate(dns_rdataset_t *rdataset) {
  90
  91         /*
  92          * Disassociate 'rdataset' from its rdata, allowing it to be reused.
  93          */
  94
  95         REQUIRE(DNS_RDATASET_VALID(rdataset));
  96         REQUIRE(rdataset->methods != NULL);
  97
  98         (rdataset->methods->disassociate)(rdataset);
  99         rdataset->methods = NULL;
 100         ISC_LINK_INIT(rdataset, link);
 101         rdataset->rdclass = 0;
 102         rdataset->type = 0;
 103         rdataset->ttl = 0;
 104         rdataset->trust = 0;
 105         rdataset->covers = 0;
 106         rdataset->attributes = 0;
 107         rdataset->count = ISC_UINT32_MAX;
 108         rdataset->private1 = NULL;
 109         rdataset->private2 = NULL;
 110         rdataset->private3 = NULL;
 111         rdataset->privateuint4 = 0;
 112         rdataset->private5 = NULL;
 113         rdataset->private6 = NULL;
 114 }
 115
 116 isc_boolean_t
 117 dns_rdataset_isassociated(dns_rdataset_t *rdataset) {
 118         /*
 119          * Is 'rdataset' associated?
 120          */
 121
 122         REQUIRE(DNS_RDATASET_VALID(rdataset));
 123
 124         if (rdataset->methods != NULL)
 125                 return (ISC_TRUE);
 126
 127         return (ISC_FALSE);
 128 }
 129
 130 static void
 131 question_disassociate(dns_rdataset_t *rdataset) {
 132         UNUSED(rdataset);
 133 }
 134
 135 static isc_result_t
 136 question_cursor(dns_rdataset_t *rdataset) {
 137         UNUSED(rdataset);
 138
 139         return (ISC_R_NOMORE);
 140 }
 141
 142 static void
 143 question_current(dns_rdataset_t *rdataset, dns_rdata_t *rdata) {
 144         /*
 145          * This routine should never be called.
 146          */
 147         UNUSED(rdataset);
 148         UNUSED(rdata);
 149
 150         REQUIRE(0);
 151 }
 152
 153 static void
 154 question_clone(dns_rdataset_t *source, dns_rdataset_t *target) {
 155         *target = *source;
 156 }
 157
 158 static unsigned int
 159 question_count(dns_rdataset_t *rdataset) {
 160         /*
 161          * This routine should never be called.
 162          */
 163         UNUSED(rdataset);
 164         REQUIRE(0);
 165
 166         return (0);
 167 }
 168
 169 static dns_rdatasetmethods_t question_methods = {
 170         question_disassociate,
 171         question_cursor,
 172         question_cursor,
 173         question_current,
 174         question_clone,
 175         question_count,
 176         NULL,
 177         NULL
 178 };
 179
 180 void
 181 dns_rdataset_makequestion(dns_rdataset_t *rdataset, dns_rdataclass_t rdclass,
 182                           dns_rdatatype_t type)
 183 {
 184
 185         /*
 186          * Make 'rdataset' a valid, associated, question rdataset, with a
 187          * question class of 'rdclass' and type 'type'.
 188          */
 189
 190         REQUIRE(DNS_RDATASET_VALID(rdataset));
 191         REQUIRE(rdataset->methods == NULL);
 192
 193         rdataset->methods = &question_methods;
 194         rdataset->rdclass = rdclass;
 195         rdataset->type = type;
 196         rdataset->attributes |= DNS_RDATASETATTR_QUESTION;
 197 }
 198
 199 unsigned int
 200 dns_rdataset_count(dns_rdataset_t *rdataset) {
 201
 202         /*
 203          * Return the number of records in 'rdataset'.
 204          */
 205
 206         REQUIRE(DNS_RDATASET_VALID(rdataset));
 207         REQUIRE(rdataset->methods != NULL);
 208
 209         return ((rdataset->methods->count)(rdataset));
 210 }
 211
 212 void
 213 dns_rdataset_clone(dns_rdataset_t *source, dns_rdataset_t *target) {
 214
 215         /*
 216          * Make 'target' refer to the same rdataset as 'source'.
 217          */
 218
 219         REQUIRE(DNS_RDATASET_VALID(source));
 220         REQUIRE(source->methods != NULL);
 221         REQUIRE(DNS_RDATASET_VALID(target));
 222         REQUIRE(target->methods == NULL);
 223
 224         (source->methods->clone)(source, target);
 225 }
 226
 227 isc_result_t
 228 dns_rdataset_first(dns_rdataset_t *rdataset) {
 229
 230         /*
 231          * Move the rdata cursor to the first rdata in the rdataset (if any).
 232          */
 233
 234         REQUIRE(DNS_RDATASET_VALID(rdataset));
 235         REQUIRE(rdataset->methods != NULL);
 236
 237         return ((rdataset->methods->first)(rdataset));
 238 }
 239
 240 isc_result_t
 241 dns_rdataset_next(dns_rdataset_t *rdataset) {
 242
 243         /*
 244          * Move the rdata cursor to the next rdata in the rdataset (if any).
 245          */
 246
 247         REQUIRE(DNS_RDATASET_VALID(rdataset));
 248         REQUIRE(rdataset->methods != NULL);
 249
 250         return ((rdataset->methods->next)(rdataset));
 251 }
 252
 253 void
 254 dns_rdataset_current(dns_rdataset_t *rdataset, dns_rdata_t *rdata) {
 255
 256         /*
 257          * Make 'rdata' refer to the current rdata.
 258          */
 259
 260         REQUIRE(DNS_RDATASET_VALID(rdataset));
 261         REQUIRE(rdataset->methods != NULL);
 262
 263         (rdataset->methods->current)(rdataset, rdata);
 264 }
 265
 266 #define MAX_SHUFFLE     32
 267 #define WANT_FIXED(r)   (((r)->attributes & DNS_RDATASETATTR_FIXEDORDER) != 0)
 268 #define WANT_RANDOM(r)  (((r)->attributes & DNS_RDATASETATTR_RANDOMIZE) != 0)
 269
 270 struct towire_sort {
 271         int key;
 272         dns_rdata_t *rdata;
 273 };
 274
 275 static int
 276 towire_compare(const void *av, const void *bv) {
 277         const struct towire_sort *a = (const struct towire_sort *) av;
 278         const struct towire_sort *b = (const struct towire_sort *) bv;
 279         return (a->key - b->key);
 280 }
 281
 282 static isc_result_t
 283 towiresorted(dns_rdataset_t *rdataset, const dns_name_t *owner_name,
 284              dns_compress_t *cctx, isc_buffer_t *target,
 285              dns_rdatasetorderfunc_t order, const void *order_arg,
 286              isc_boolean_t partial, unsigned int options,
 287              unsigned int *countp, void **state)
 288 {
 289         dns_rdata_t rdata = DNS_RDATA_INIT;
 290         isc_region_t r;
 291         isc_result_t result;
 292         unsigned int i, count, added, choice;
 293         isc_buffer_t savedbuffer, rdlen, rrbuffer;
 294         unsigned int headlen;
 295         isc_boolean_t question = ISC_FALSE;
 296         isc_boolean_t shuffle = ISC_FALSE;
 297         dns_rdata_t *shuffled = NULL, shuffled_fixed[MAX_SHUFFLE];
 298         struct towire_sort *sorted = NULL, sorted_fixed[MAX_SHUFFLE];
 299
 300         UNUSED(state);
 301
 302         /*
 303          * Convert 'rdataset' to wire format, compressing names as specified
 304          * in cctx, and storing the result in 'target'.
 305          */
 306
 307         REQUIRE(DNS_RDATASET_VALID(rdataset));
 308         REQUIRE(countp != NULL);
 309         REQUIRE((order == NULL) == (order_arg == NULL));
 310         REQUIRE(cctx != NULL && cctx->mctx != NULL);
 311
 312         count = 0;
 313         if ((rdataset->attributes & DNS_RDATASETATTR_QUESTION) != 0) {
 314                 question = ISC_TRUE;
 315                 count = 1;
 316                 result = dns_rdataset_first(rdataset);
 317                 INSIST(result == ISC_R_NOMORE);
 318         } else if (rdataset->type == 0) {
 319                 /*
 320                  * This is a negative caching rdataset.
 321                  */
 322                 unsigned int ncache_opts = 0;
 323                 if ((options & DNS_RDATASETTOWIRE_OMITDNSSEC) != 0)
 324                         ncache_opts |= DNS_NCACHETOWIRE_OMITDNSSEC;
 325                 return (dns_ncache_towire(rdataset, cctx, target, ncache_opts,
 326                                           countp));
 327         } else {
 328                 count = (rdataset->methods->count)(rdataset);
 329                 result = dns_rdataset_first(rdataset);
 330                 if (result == ISC_R_NOMORE)
 331                         return (ISC_R_SUCCESS);
 332                 if (result != ISC_R_SUCCESS)
 333                         return (result);
 334         }
 335
 336         /*
 337          * Do we want to shuffle this anwer?
 338          */
 339         if (!question && count > 1 &&
 340             (!WANT_FIXED(rdataset) || order != NULL) &&
 341             rdataset->type != dns_rdatatype_rrsig)
 342                 shuffle = ISC_TRUE;
 343
 344         if (shuffle && count > MAX_SHUFFLE) {
 345                 shuffled = isc_mem_get(cctx->mctx, count * sizeof(*shuffled));
 346                 sorted = isc_mem_get(cctx->mctx, count * sizeof(*sorted));
 347                 if (shuffled == NULL || sorted == NULL)
 348                         shuffle = ISC_FALSE;
 349         } else {
 350                 shuffled = shuffled_fixed;
 351                 sorted = sorted_fixed;
 352         }
 353
 354         if (shuffle) {
 355                 /*
 356                  * First we get handles to all of the rdata.
 357                  */
 358                 i = 0;
 359                 do {
 360                         INSIST(i < count);
 361                         dns_rdata_init(&shuffled[i]);
 362                         dns_rdataset_current(rdataset, &shuffled[i]);
 363                         i++;
 364                         result = dns_rdataset_next(rdataset);
 365                 } while (result == ISC_R_SUCCESS);
 366                 if (result != ISC_R_NOMORE)
 367                         goto cleanup;
 368                 INSIST(i == count);
 369
 370                 /*
 371                  * Now we shuffle.
 372                  */
 373                 if (WANT_FIXED(rdataset)) {
 374                         /*
 375                          * 'Fixed' order.
 376                          */
 377                         INSIST(order != NULL);
 378                         for (i = 0; i < count; i++) {
 379                                 sorted[i].key = (*order)(&shuffled[i],
 380                                                          order_arg);
 381                                 sorted[i].rdata = &shuffled[i];
 382                         }
 383                 } else if (WANT_RANDOM(rdataset)) {
 384                         /*
 385                          * 'Random' order.
 386                          */
 387                         for (i = 0; i < count; i++) {
 388                                 dns_rdata_t rdata;
 389                                 isc_uint32_t val;
 390
 391                                 isc_random_get(&val);
 392                                 choice = i + (val % (count - i));
 393                                 rdata = shuffled[i];
 394                                 shuffled[i] = shuffled[choice];
 395                                 shuffled[choice] = rdata;
 396                                 if (order != NULL)
 397                                         sorted[i].key = (*order)(&shuffled[i],
 398                                                                  order_arg);
 399                                 else
 400                                         sorted[i].key = 0; /* Unused */
 401                                 sorted[i].rdata = &shuffled[i];
 402                         }
 403                 } else {
 404                         /*
 405                          * "Cyclic" order.
 406                          */
 407                         isc_uint32_t val;
 408                         unsigned int j;
 409
 410                         val = rdataset->count;
 411                         if (val == ISC_UINT32_MAX)
 412                                 isc_random_get(&val);
 413                         j = val % count;
 414                         for (i = 0; i < count; i++) {
 415                                 if (order != NULL)
 416                                         sorted[j].key = (*order)(&shuffled[i],
 417                                                                  order_arg);
 418                                 else
 419                                         sorted[j].key = 0; /* Unused */
 420                                 sorted[j].rdata = &shuffled[i];
 421                                 j++;
 422                                 if (j == count)
 423                                         j = 0; /* Wrap around. */
 424                         }
 425                 }
 426
 427                 /*
 428                  * Sorted order.
 429                  */
 430                 if (order != NULL)
 431                         qsort(sorted, count, sizeof(sorted[0]),
 432                               towire_compare);
 433         }
 434
 435         savedbuffer = *target;
 436         i = 0;
 437         added = 0;
 438
 439         do {
 440                 /*
 441                  * Copy out the name, type, class, ttl.
 442                  */
 443
 444                 rrbuffer = *target;
 445                 dns_compress_setmethods(cctx, DNS_COMPRESS_GLOBAL14);
 446                 result = dns_name_towire(owner_name, cctx, target);
 447                 if (result != ISC_R_SUCCESS)
 448                         goto rollback;
 449                 headlen = sizeof(dns_rdataclass_t) + sizeof(dns_rdatatype_t);
 450                 if (!question)
 451                         headlen += sizeof(dns_ttl_t)
 452                                 + 2;  /* XXX 2 for rdata len */
 453                 isc_buffer_availableregion(target, &r);
 454                 if (r.length < headlen) {
 455                         result = ISC_R_NOSPACE;
 456                         goto rollback;
 457                 }
 458                 isc_buffer_putuint16(target, rdataset->type);
 459                 isc_buffer_putuint16(target, rdataset->rdclass);
 460                 if (!question) {
 461                         isc_buffer_putuint32(target, rdataset->ttl);
 462
 463                         /*
 464                          * Save space for rdlen.
 465                          */
 466                         rdlen = *target;
 467                         isc_buffer_add(target, 2);
 468
 469                         /*
 470                          * Copy out the rdata
 471                          */
 472                         if (shuffle)
 473                                 rdata = *(sorted[i].rdata);
 474                         else {
 475                                 dns_rdata_reset(&rdata);
 476                                 dns_rdataset_current(rdataset, &rdata);
 477                         }
 478                         result = dns_rdata_towire(&rdata, cctx, target);
 479                         if (result != ISC_R_SUCCESS)
 480                                 goto rollback;
 481                         INSIST((target->used >= rdlen.used + 2) &&
 482                                (target->used - rdlen.used - 2 < 65536));
 483                         isc_buffer_putuint16(&rdlen,
 484                                              (isc_uint16_t)(target->used -
 485                                                             rdlen.used - 2));
 486                         added++;
 487                 }
 488
 489                 if (shuffle) {
 490                         i++;
 491                         if (i == count)
 492                                 result = ISC_R_NOMORE;
 493                         else
 494                                 result = ISC_R_SUCCESS;
 495                 } else {
 496                         result = dns_rdataset_next(rdataset);
 497                 }
 498         } while (result == ISC_R_SUCCESS);
 499
 500         if (result != ISC_R_NOMORE)
 501                 goto rollback;
 502
 503         *countp += count;
 504
 505         result = ISC_R_SUCCESS;
 506         goto cleanup;
 507
 508  rollback:
 509         if (partial && result == ISC_R_NOSPACE) {
 510                 INSIST(rrbuffer.used < 65536);
 511                 dns_compress_rollback(cctx, (isc_uint16_t)rrbuffer.used);
 512                 *countp += added;
 513                 *target = rrbuffer;
 514                 goto cleanup;
 515         }
 516         INSIST(savedbuffer.used < 65536);
 517         dns_compress_rollback(cctx, (isc_uint16_t)savedbuffer.used);
 518         *countp = 0;
 519         *target = savedbuffer;
 520
 521  cleanup:
 522         if (sorted != NULL && sorted != sorted_fixed)
 523                 isc_mem_put(cctx->mctx, sorted, count * sizeof(*sorted));
 524         if (shuffled != NULL && shuffled != shuffled_fixed)
 525                 isc_mem_put(cctx->mctx, shuffled, count * sizeof(*shuffled));
 526         return (result);
 527 }
 528
 529 isc_result_t
 530 dns_rdataset_towiresorted(dns_rdataset_t *rdataset,
 531                           const dns_name_t *owner_name,
 532                           dns_compress_t *cctx,
 533                           isc_buffer_t *target,
 534                           dns_rdatasetorderfunc_t order,
 535                           const void *order_arg,
 536                           unsigned int options,
 537                           unsigned int *countp)
 538 {
 539         return (towiresorted(rdataset, owner_name, cctx, target,
 540                              order, order_arg, ISC_FALSE, options,
 541                              countp, NULL));
 542 }
 543
 544 isc_result_t
 545 dns_rdataset_towirepartial(dns_rdataset_t *rdataset,
 546                            const dns_name_t *owner_name,
 547                            dns_compress_t *cctx,
 548                            isc_buffer_t *target,
 549                            dns_rdatasetorderfunc_t order,
 550                            const void *order_arg,
 551                            unsigned int options,
 552                            unsigned int *countp,
 553                            void **state)
 554 {
 555         REQUIRE(state == NULL); /* XXX remove when implemented */
 556         return (towiresorted(rdataset, owner_name, cctx, target,
 557                              order, order_arg, ISC_TRUE, options,
 558                              countp, state));
 559 }
 560
 561 isc_result_t
 562 dns_rdataset_towire(dns_rdataset_t *rdataset,
 563                     dns_name_t *owner_name,
 564                     dns_compress_t *cctx,
 565                     isc_buffer_t *target,
 566                     unsigned int options,
 567                     unsigned int *countp)
 568 {
 569         return (towiresorted(rdataset, owner_name, cctx, target,
 570                              NULL, NULL, ISC_FALSE, options, countp, NULL));
 571 }
 572
 573 isc_result_t
 574 dns_rdataset_additionaldata(dns_rdataset_t *rdataset,
 575                             dns_additionaldatafunc_t add, void *arg)
 576 {
 577         dns_rdata_t rdata = DNS_RDATA_INIT;
 578         isc_result_t result;
 579
 580         /*
 581          * For each rdata in rdataset, call 'add' for each name and type in the
 582          * rdata which is subject to additional section processing.
 583          */
 584
 585         REQUIRE(DNS_RDATASET_VALID(rdataset));
 586         REQUIRE((rdataset->attributes & DNS_RDATASETATTR_QUESTION) == 0);
 587
 588         result = dns_rdataset_first(rdataset);
 589         if (result != ISC_R_SUCCESS)
 590                 return (result);
 591
 592         do {
 593                 dns_rdataset_current(rdataset, &rdata);
 594                 result = dns_rdata_additionaldata(&rdata, add, arg);
 595                 if (result == ISC_R_SUCCESS)
 596                         result = dns_rdataset_next(rdataset);
 597                 dns_rdata_reset(&rdata);
 598         } while (result == ISC_R_SUCCESS);
 599
 600         if (result != ISC_R_NOMORE)
 601                 return (result);
 602
 603         return (ISC_R_SUCCESS);
 604 }
 605
 606 isc_result_t
 607 dns_rdataset_addnoqname(dns_rdataset_t *rdataset, dns_name_t *name) {
 608
 609         REQUIRE(DNS_RDATASET_VALID(rdataset));
 610         REQUIRE(rdataset->methods != NULL);
 611         if (rdataset->methods->addnoqname == NULL)
 612                 return (ISC_R_NOTIMPLEMENTED);
 613         return((rdataset->methods->addnoqname)(rdataset, name));
 614 }
 615
 616 isc_result_t
 617 dns_rdataset_getnoqname(dns_rdataset_t *rdataset, dns_name_t *name,
 618                         dns_rdataset_t *nsec, dns_rdataset_t *nsecsig)
 619 {
 620         REQUIRE(DNS_RDATASET_VALID(rdataset));
 621         REQUIRE(rdataset->methods != NULL);
 622
 623         if (rdataset->methods->getnoqname == NULL)
 624                 return (ISC_R_NOTIMPLEMENTED);
 625         return((rdataset->methods->getnoqname)(rdataset, name, nsec, nsecsig));
 626 }