external/bsd/bind/dist/lib/dns/keytable.c

   1 /*      $NetBSD: keytable.c,v 1.1.1.3 2009/12/26 22:24:36 christos Exp $        */
   2
   3 /*
   4  * Copyright (C) 2004, 2005, 2007, 2009  Internet Systems Consortium, Inc. ("ISC")
   5  * Copyright (C) 2000, 2001  Internet Software Consortium.
   6  *
   7  * Permission to use, copy, modify, and/or distribute this software for any
   8  * purpose with or without fee is hereby granted, provided that the above
   9  * copyright notice and this permission notice appear in all copies.
  10  *
  11  * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
  12  * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
  13  * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
  14  * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
  15  * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
  16  * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  17  * PERFORMANCE OF THIS SOFTWARE.
  18  */
  19
  20 /* Id: keytable.c,v 1.39 2009/12/03 15:40:02 each Exp */
  21
  22 /*! \file */
  23
  24 #include <config.h>
  25
  26 #include <isc/mem.h>
  27 #include <isc/rwlock.h>
  28 #include <isc/string.h>         /* Required for HP/UX (and others?) */
  29 #include <isc/util.h>
  30
  31 #include <dns/keytable.h>
  32 #include <dns/fixedname.h>
  33 #include <dns/rbt.h>
  34 #include <dns/result.h>
  35
  36 static void
  37 free_keynode(void *node, void *arg) {
  38         dns_keynode_t *keynode = node;
  39         isc_mem_t *mctx = arg;
  40
  41         dns_keynode_detachall(mctx, &keynode);
  42 }
  43
  44 isc_result_t
  45 dns_keytable_create(isc_mem_t *mctx, dns_keytable_t **keytablep) {
  46         dns_keytable_t *keytable;
  47         isc_result_t result;
  48
  49         /*
  50          * Create a keytable.
  51          */
  52
  53         REQUIRE(keytablep != NULL && *keytablep == NULL);
  54
  55         keytable = isc_mem_get(mctx, sizeof(*keytable));
  56         if (keytable == NULL)
  57                 return (ISC_R_NOMEMORY);
  58
  59         keytable->table = NULL;
  60         result = dns_rbt_create(mctx, free_keynode, mctx, &keytable->table);
  61         if (result != ISC_R_SUCCESS)
  62                 goto cleanup_keytable;
  63
  64         result = isc_mutex_init(&keytable->lock);
  65         if (result != ISC_R_SUCCESS)
  66                 goto cleanup_rbt;
  67
  68         result = isc_rwlock_init(&keytable->rwlock, 0, 0);
  69         if (result != ISC_R_SUCCESS)
  70                 goto cleanup_lock;
  71
  72         keytable->mctx = mctx;
  73         keytable->active_nodes = 0;
  74         keytable->references = 1;
  75         keytable->magic = KEYTABLE_MAGIC;
  76         *keytablep = keytable;
  77
  78         return (ISC_R_SUCCESS);
  79
  80    cleanup_lock:
  81         DESTROYLOCK(&keytable->lock);
  82
  83    cleanup_rbt:
  84         dns_rbt_destroy(&keytable->table);
  85
  86    cleanup_keytable:
  87         isc_mem_put(mctx, keytable, sizeof(*keytable));
  88
  89         return (result);
  90 }
  91
  92 void
  93 dns_keytable_attach(dns_keytable_t *source, dns_keytable_t **targetp) {
  94
  95         /*
  96          * Attach *targetp to source.
  97          */
  98
  99         REQUIRE(VALID_KEYTABLE(source));
 100         REQUIRE(targetp != NULL && *targetp == NULL);
 101
 102         RWLOCK(&source->rwlock, isc_rwlocktype_write);
 103
 104         INSIST(source->references > 0);
 105         source->references++;
 106         INSIST(source->references != 0);
 107
 108         RWUNLOCK(&source->rwlock, isc_rwlocktype_write);
 109
 110         *targetp = source;
 111 }
 112
 113 void
 114 dns_keytable_detach(dns_keytable_t **keytablep) {
 115         isc_boolean_t destroy = ISC_FALSE;
 116         dns_keytable_t *keytable;
 117
 118         /*
 119          * Detach *keytablep from its keytable.
 120          */
 121
 122         REQUIRE(keytablep != NULL && VALID_KEYTABLE(*keytablep));
 123
 124         keytable = *keytablep;
 125
 126         RWLOCK(&keytable->rwlock, isc_rwlocktype_write);
 127
 128         INSIST(keytable->references > 0);
 129         keytable->references--;
 130         LOCK(&keytable->lock);
 131         if (keytable->references == 0 && keytable->active_nodes == 0)
 132                 destroy = ISC_TRUE;
 133         UNLOCK(&keytable->lock);
 134
 135         RWUNLOCK(&keytable->rwlock, isc_rwlocktype_write);
 136
 137         if (destroy) {
 138                 dns_rbt_destroy(&keytable->table);
 139                 isc_rwlock_destroy(&keytable->rwlock);
 140                 DESTROYLOCK(&keytable->lock);
 141                 keytable->magic = 0;
 142                 isc_mem_put(keytable->mctx, keytable, sizeof(*keytable));
 143         }
 144
 145         *keytablep = NULL;
 146 }
 147
 148 static isc_result_t
 149 insert(dns_keytable_t *keytable, isc_boolean_t managed,
 150        dns_name_t *keyname, dst_key_t **keyp)
 151 {
 152         isc_result_t result;
 153         dns_keynode_t *knode = NULL;
 154         dns_rbtnode_t *node;
 155
 156         REQUIRE(keyp == NULL || *keyp != NULL);
 157         REQUIRE(VALID_KEYTABLE(keytable));
 158
 159         result = dns_keynode_create(keytable->mctx, &knode);
 160         if (result != ISC_R_SUCCESS)
 161                 return (result);
 162
 163         knode->managed = managed;
 164
 165         RWLOCK(&keytable->rwlock, isc_rwlocktype_write);
 166
 167         node = NULL;
 168         result = dns_rbt_addnode(keytable->table, keyname, &node);
 169
 170         if (keyp != NULL) {
 171                 if (result == ISC_R_EXISTS) {
 172                         /* Key already in table? */
 173                         dns_keynode_t *k;
 174                         for (k = node->data; k != NULL; k = k->next) {
 175                                 if (k->key == NULL) {
 176                                         k->key = *keyp;
 177                                         break;
 178                                 }
 179                                 if (dst_key_compare(k->key, *keyp) == ISC_TRUE)
 180                                         break;
 181                         }
 182
 183                         if (k == NULL)
 184                                 result = ISC_R_SUCCESS;
 185                         else
 186                                 dst_key_free(keyp);
 187                 }
 188
 189                 if (result == ISC_R_SUCCESS) {
 190                         knode->key = *keyp;
 191                         knode->next = node->data;
 192                         *keyp = NULL;
 193                 }
 194         }
 195
 196         if (result == ISC_R_SUCCESS) {
 197                 node->data = knode;
 198                 knode = NULL;
 199         }
 200
 201         /* Key was already there?  That's the same as a success */
 202         if (result == ISC_R_EXISTS)
 203                 result = ISC_R_SUCCESS;
 204
 205         RWUNLOCK(&keytable->rwlock, isc_rwlocktype_write);
 206
 207         if (knode != NULL)
 208                 dns_keynode_detach(keytable->mctx, &knode);
 209
 210         return (result);
 211 }
 212
 213 isc_result_t
 214 dns_keytable_add(dns_keytable_t *keytable, isc_boolean_t managed,
 215                  dst_key_t **keyp)
 216 {
 217         REQUIRE(keyp != NULL && *keyp != NULL);
 218         return (insert(keytable, managed, dst_key_name(*keyp), keyp));
 219 }
 220
 221 isc_result_t
 222 dns_keytable_marksecure(dns_keytable_t *keytable, dns_name_t *name) {
 223         return (insert(keytable, ISC_TRUE, name, NULL));
 224 }
 225
 226 isc_result_t
 227 dns_keytable_delete(dns_keytable_t *keytable, dns_name_t *keyname) {
 228         isc_result_t result;
 229         dns_rbtnode_t *node = NULL;
 230
 231         REQUIRE(VALID_KEYTABLE(keytable));
 232         REQUIRE(keyname != NULL);
 233
 234         RWLOCK(&keytable->rwlock, isc_rwlocktype_write);
 235         result = dns_rbt_findnode(keytable->table, keyname, NULL, &node, NULL,
 236                                   DNS_RBTFIND_NOOPTIONS, NULL, NULL);
 237         if (result == ISC_R_SUCCESS) {
 238                 if (node->data != NULL)
 239                         result = dns_rbt_deletenode(keytable->table,
 240                                                     node, ISC_FALSE);
 241                 else
 242                         result = ISC_R_NOTFOUND;
 243         } else if (result == DNS_R_PARTIALMATCH)
 244                 result = ISC_R_NOTFOUND;
 245         RWUNLOCK(&keytable->rwlock, isc_rwlocktype_write);
 246
 247         return (result);
 248 }
 249
 250 isc_result_t
 251 dns_keytable_deletekeynode(dns_keytable_t *keytable, dst_key_t *dstkey) {
 252         isc_result_t result;
 253         dns_name_t *keyname;
 254         dns_rbtnode_t *node = NULL;
 255         dns_keynode_t *knode = NULL, **kprev = NULL;
 256
 257         REQUIRE(VALID_KEYTABLE(keytable));
 258         REQUIRE(dstkey != NULL);
 259
 260         keyname = dst_key_name(dstkey);
 261
 262         RWLOCK(&keytable->rwlock, isc_rwlocktype_write);
 263         result = dns_rbt_findnode(keytable->table, keyname, NULL, &node, NULL,
 264                                   DNS_RBTFIND_NOOPTIONS, NULL, NULL);
 265
 266         if (result == DNS_R_PARTIALMATCH)
 267                 result = ISC_R_NOTFOUND;
 268         if (result != ISC_R_SUCCESS)
 269                 goto finish;
 270
 271         if (node->data == NULL) {
 272                 result = ISC_R_NOTFOUND;
 273                 goto finish;
 274         }
 275
 276         knode = node->data;
 277         if (knode->next == NULL &&
 278             (knode->key == NULL ||
 279              dst_key_compare(knode->key, dstkey) == ISC_TRUE)) {
 280                 result = dns_rbt_deletenode(keytable->table, node, ISC_FALSE);
 281                 goto finish;
 282         }
 283
 284         kprev = (dns_keynode_t **)(void *)&node->data;
 285         while (knode != NULL) {
 286                 if (dst_key_compare(knode->key, dstkey) == ISC_TRUE)
 287                         break;
 288                 kprev = &knode->next;
 289                 knode = knode->next;
 290         }
 291
 292         if (knode != NULL) {
 293                 if (knode->key != NULL)
 294                         dst_key_free(&knode->key);
 295                 /*
 296                  * This is equivalent to:
 297                  * dns_keynode_attach(knode->next, &tmp);
 298                  * dns_keynode_detach(kprev);
 299                  * dns_keynode_attach(tmp, &kprev);
 300                  * dns_keynode_detach(&tmp);
 301                  */
 302                 *kprev = knode->next;
 303                 knode->next = NULL;
 304                 dns_keynode_detach(keytable->mctx, &knode);
 305         } else
 306                 result = DNS_R_PARTIALMATCH;
 307   finish:
 308         RWUNLOCK(&keytable->rwlock, isc_rwlocktype_write);
 309         return (result);
 310 }
 311
 312 isc_result_t
 313 dns_keytable_find(dns_keytable_t *keytable, dns_name_t *keyname,
 314                   dns_keynode_t **keynodep)
 315 {
 316         isc_result_t result;
 317         dns_rbtnode_t *node = NULL;
 318
 319         REQUIRE(VALID_KEYTABLE(keytable));
 320         REQUIRE(keyname != NULL);
 321         REQUIRE(keynodep != NULL && *keynodep == NULL);
 322
 323         RWLOCK(&keytable->rwlock, isc_rwlocktype_read);
 324         result = dns_rbt_findnode(keytable->table, keyname, NULL, &node, NULL,
 325                                   DNS_RBTFIND_NOOPTIONS, NULL, NULL);
 326         if (result == ISC_R_SUCCESS) {
 327                 if (node->data != NULL) {
 328                         LOCK(&keytable->lock);
 329                         keytable->active_nodes++;
 330                         UNLOCK(&keytable->lock);
 331                         dns_keynode_attach(node->data, keynodep);
 332                 } else
 333                         result = ISC_R_NOTFOUND;
 334         } else if (result == DNS_R_PARTIALMATCH)
 335                 result = ISC_R_NOTFOUND;
 336         RWUNLOCK(&keytable->rwlock, isc_rwlocktype_read);
 337
 338         return (result);
 339 }
 340
 341 isc_result_t
 342 dns_keytable_nextkeynode(dns_keytable_t *keytable, dns_keynode_t *keynode,
 343                          dns_keynode_t **nextnodep)
 344 {
 345         /*
 346          * Return the next key after 'keynode', regardless of
 347          * properties.
 348          */
 349
 350         REQUIRE(VALID_KEYTABLE(keytable));
 351         REQUIRE(VALID_KEYNODE(keynode));
 352         REQUIRE(nextnodep != NULL && *nextnodep == NULL);
 353
 354         if (keynode->next == NULL)
 355                 return (ISC_R_NOTFOUND);
 356
 357         dns_keynode_attach(keynode->next, nextnodep);
 358         LOCK(&keytable->lock);
 359         keytable->active_nodes++;
 360         UNLOCK(&keytable->lock);
 361
 362         return (ISC_R_SUCCESS);
 363 }
 364
 365 isc_result_t
 366 dns_keytable_findkeynode(dns_keytable_t *keytable, dns_name_t *name,
 367                          dns_secalg_t algorithm, dns_keytag_t tag,
 368                          dns_keynode_t **keynodep)
 369 {
 370         isc_result_t result;
 371         dns_keynode_t *knode;
 372         void *data;
 373
 374         /*
 375          * Search for a key named 'name', matching 'algorithm' and 'tag' in
 376          * 'keytable'.
 377          */
 378
 379         REQUIRE(VALID_KEYTABLE(keytable));
 380         REQUIRE(dns_name_isabsolute(name));
 381         REQUIRE(keynodep != NULL && *keynodep == NULL);
 382
 383         RWLOCK(&keytable->rwlock, isc_rwlocktype_read);
 384
 385         /*
 386          * Note we don't want the DNS_R_PARTIALMATCH from dns_rbt_findname()
 387          * as that indicates that 'name' was not found.
 388          *
 389          * DNS_R_PARTIALMATCH indicates that the name was found but we
 390          * didn't get a match on algorithm and key id arguments.
 391          */
 392         knode = NULL;
 393         data = NULL;
 394         result = dns_rbt_findname(keytable->table, name, 0, NULL, &data);
 395
 396         if (result == ISC_R_SUCCESS) {
 397                 INSIST(data != NULL);
 398                 for (knode = data; knode != NULL; knode = knode->next) {
 399                         if (knode->key == NULL) {
 400                                 knode = NULL;
 401                                 break;
 402                         }
 403                         if (algorithm == dst_key_alg(knode->key)
 404                             && tag == dst_key_id(knode->key))
 405                                 break;
 406                 }
 407                 if (knode != NULL) {
 408                         LOCK(&keytable->lock);
 409                         keytable->active_nodes++;
 410                         UNLOCK(&keytable->lock);
 411                         dns_keynode_attach(knode, keynodep);
 412                 } else
 413                         result = DNS_R_PARTIALMATCH;
 414         } else if (result == DNS_R_PARTIALMATCH)
 415                 result = ISC_R_NOTFOUND;
 416
 417         RWUNLOCK(&keytable->rwlock, isc_rwlocktype_read);
 418
 419         return (result);
 420 }
 421
 422 isc_result_t
 423 dns_keytable_findnextkeynode(dns_keytable_t *keytable, dns_keynode_t *keynode,
 424                              dns_keynode_t **nextnodep)
 425 {
 426         isc_result_t result;
 427         dns_keynode_t *knode;
 428
 429         /*
 430          * Search for the next key with the same properties as 'keynode' in
 431          * 'keytable'.
 432          */
 433
 434         REQUIRE(VALID_KEYTABLE(keytable));
 435         REQUIRE(VALID_KEYNODE(keynode));
 436         REQUIRE(nextnodep != NULL && *nextnodep == NULL);
 437
 438         for (knode = keynode->next; knode != NULL; knode = knode->next) {
 439                 if (knode->key == NULL) {
 440                         knode = NULL;
 441                         break;
 442                 }
 443                 if (dst_key_alg(keynode->key) == dst_key_alg(knode->key) &&
 444                     dst_key_id(keynode->key) == dst_key_id(knode->key))
 445                         break;
 446         }
 447         if (knode != NULL) {
 448                 LOCK(&keytable->lock);
 449                 keytable->active_nodes++;
 450                 UNLOCK(&keytable->lock);
 451                 result = ISC_R_SUCCESS;
 452                 dns_keynode_attach(knode, nextnodep);
 453         } else
 454                 result = ISC_R_NOTFOUND;
 455
 456         return (result);
 457 }
 458
 459 isc_result_t
 460 dns_keytable_finddeepestmatch(dns_keytable_t *keytable, dns_name_t *name,
 461                               dns_name_t *foundname)
 462 {
 463         isc_result_t result;
 464         void *data;
 465
 466         /*
 467          * Search for the deepest match in 'keytable'.
 468          */
 469
 470         REQUIRE(VALID_KEYTABLE(keytable));
 471         REQUIRE(dns_name_isabsolute(name));
 472         REQUIRE(foundname != NULL);
 473
 474         RWLOCK(&keytable->rwlock, isc_rwlocktype_read);
 475
 476         data = NULL;
 477         result = dns_rbt_findname(keytable->table, name, 0, foundname, &data);
 478
 479         if (result == ISC_R_SUCCESS || result == DNS_R_PARTIALMATCH)
 480                 result = ISC_R_SUCCESS;
 481
 482         RWUNLOCK(&keytable->rwlock, isc_rwlocktype_read);
 483
 484         return (result);
 485 }
 486
 487 void
 488 dns_keytable_attachkeynode(dns_keytable_t *keytable, dns_keynode_t *source,
 489                            dns_keynode_t **target)
 490 {
 491         /*
 492          * Give back a keynode found via dns_keytable_findkeynode().
 493          */
 494
 495         REQUIRE(VALID_KEYTABLE(keytable));
 496         REQUIRE(VALID_KEYNODE(source));
 497         REQUIRE(target != NULL && *target == NULL);
 498
 499         LOCK(&keytable->lock);
 500         keytable->active_nodes++;
 501         UNLOCK(&keytable->lock);
 502
 503         dns_keynode_attach(source, target);
 504 }
 505
 506 void
 507 dns_keytable_detachkeynode(dns_keytable_t *keytable, dns_keynode_t **keynodep)
 508 {
 509         /*
 510          * Give back a keynode found via dns_keytable_findkeynode().
 511          */
 512
 513         REQUIRE(VALID_KEYTABLE(keytable));
 514         REQUIRE(keynodep != NULL && VALID_KEYNODE(*keynodep));
 515
 516         LOCK(&keytable->lock);
 517         INSIST(keytable->active_nodes > 0);
 518         keytable->active_nodes--;
 519         UNLOCK(&keytable->lock);
 520
 521         dns_keynode_detach(keytable->mctx, keynodep);
 522 }
 523
 524 isc_result_t
 525 dns_keytable_issecuredomain(dns_keytable_t *keytable, dns_name_t *name,
 526                             isc_boolean_t *wantdnssecp)
 527 {
 528         isc_result_t result;
 529         void *data;
 530
 531         /*
 532          * Is 'name' at or beneath a trusted key?
 533          */
 534
 535         REQUIRE(VALID_KEYTABLE(keytable));
 536         REQUIRE(dns_name_isabsolute(name));
 537         REQUIRE(wantdnssecp != NULL);
 538
 539         RWLOCK(&keytable->rwlock, isc_rwlocktype_read);
 540
 541         data = NULL;
 542         result = dns_rbt_findname(keytable->table, name, 0, NULL, &data);
 543
 544         if (result == ISC_R_SUCCESS || result == DNS_R_PARTIALMATCH) {
 545                 INSIST(data != NULL);
 546                 *wantdnssecp = ISC_TRUE;
 547                 result = ISC_R_SUCCESS;
 548         } else if (result == ISC_R_NOTFOUND) {
 549                 *wantdnssecp = ISC_FALSE;
 550                 result = ISC_R_SUCCESS;
 551         }
 552
 553         RWUNLOCK(&keytable->rwlock, isc_rwlocktype_read);
 554
 555         return (result);
 556 }
 557
 558 dst_key_t *
 559 dns_keynode_key(dns_keynode_t *keynode) {
 560
 561         /*
 562          * Get the DST key associated with keynode.
 563          */
 564
 565         REQUIRE(VALID_KEYNODE(keynode));
 566
 567         return (keynode->key);
 568 }
 569
 570 isc_boolean_t
 571 dns_keynode_managed(dns_keynode_t *keynode) {
 572         /*
 573          * Is this a managed key?
 574          */
 575         REQUIRE(VALID_KEYNODE(keynode));
 576
 577         return (keynode->managed);
 578 }
 579
 580 isc_result_t
 581 dns_keynode_create(isc_mem_t *mctx, dns_keynode_t **target) {
 582         isc_result_t result;
 583         dns_keynode_t *knode = NULL;
 584
 585         REQUIRE(target != NULL && *target == NULL);
 586
 587         knode = isc_mem_get(mctx, sizeof(dns_keynode_t));
 588         if (knode == NULL)
 589                 return (ISC_R_NOMEMORY);
 590
 591         knode->magic = KEYNODE_MAGIC;
 592         knode->managed = ISC_FALSE;
 593         knode->key = NULL;
 594         knode->next = NULL;
 595
 596         result = isc_refcount_init(&knode->refcount, 1);
 597         if (result != ISC_R_SUCCESS)
 598                 return (result);
 599
 600         *target = knode;
 601         return (ISC_R_SUCCESS);
 602 }
 603
 604 void
 605 dns_keynode_attach(dns_keynode_t *source, dns_keynode_t **target) {
 606         REQUIRE(VALID_KEYNODE(source));
 607         isc_refcount_increment(&source->refcount, NULL);
 608         *target = source;
 609 }
 610
 611 void
 612 dns_keynode_detach(isc_mem_t *mctx, dns_keynode_t **keynode) {
 613         unsigned int refs;
 614         dns_keynode_t *node = *keynode;
 615         REQUIRE(VALID_KEYNODE(node));
 616         isc_refcount_decrement(&node->refcount, &refs);
 617         if (refs == 0) {
 618                 if (node->key != NULL)
 619                         dst_key_free(&node->key);
 620                 isc_refcount_destroy(&node->refcount);
 621                 isc_mem_put(mctx, node, sizeof(dns_keynode_t));
 622         }
 623         *keynode = NULL;
 624 }
 625
 626 void
 627 dns_keynode_detachall(isc_mem_t *mctx, dns_keynode_t **keynode) {
 628         dns_keynode_t *next = NULL, *node = *keynode;
 629         REQUIRE(VALID_KEYNODE(node));
 630         while (node != NULL) {
 631                 next = node->next;
 632                 dns_keynode_detach(mctx, &node);
 633                 node = next;
 634         }
 635         *keynode = NULL;
 636 }