contrib/unbound/validator/autotrust.c

   1 /*
   2  * validator/autotrust.c - RFC5011 trust anchor management for unbound.
   3  *
   4  * Copyright (c) 2009, 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  * Contains autotrust implementation. The implementation was taken from
  40  * the autotrust daemon (BSD licensed), written by Matthijs Mekking.
  41  * It was modified to fit into unbound. The state table process is the same.
  42  */
  43 #include "config.h"
  44 #include <ldns/ldns.h>
  45 #include "validator/autotrust.h"
  46 #include "validator/val_anchor.h"
  47 #include "validator/val_utils.h"
  48 #include "validator/val_sigcrypt.h"
  49 #include "util/data/dname.h"
  50 #include "util/data/packed_rrset.h"
  51 #include "util/log.h"
  52 #include "util/module.h"
  53 #include "util/net_help.h"
  54 #include "util/config_file.h"
  55 #include "util/regional.h"
  56 #include "util/random.h"
  57 #include "util/data/msgparse.h"
  58 #include "services/mesh.h"
  59 #include "services/cache/rrset.h"
  60 #include "validator/val_kcache.h"
  61
  62 /** number of times a key must be seen before it can become valid */
  63 #define MIN_PENDINGCOUNT 2
  64
  65 /** Event: Revoked */
  66 static void do_revoked(struct module_env* env, struct autr_ta* anchor, int* c);
  67
  68 struct autr_global_data* autr_global_create(void)
  69 {
  70         struct autr_global_data* global;
  71         global = (struct autr_global_data*)malloc(sizeof(*global));
  72         if(!global)
  73                 return NULL;
  74         rbtree_init(&global->probe, &probetree_cmp);
  75         return global;
  76 }
  77
  78 void autr_global_delete(struct autr_global_data* global)
  79 {
  80         if(!global)
  81                 return;
  82         /* elements deleted by parent */
  83         memset(global, 0, sizeof(*global));
  84         free(global);
  85 }
  86
  87 int probetree_cmp(const void* x, const void* y)
  88 {
  89         struct trust_anchor* a = (struct trust_anchor*)x;
  90         struct trust_anchor* b = (struct trust_anchor*)y;
  91         log_assert(a->autr && b->autr);
  92         if(a->autr->next_probe_time < b->autr->next_probe_time)
  93                 return -1;
  94         if(a->autr->next_probe_time > b->autr->next_probe_time)
  95                 return 1;
  96         /* time is equal, sort on trust point identity */
  97         return anchor_cmp(x, y);
  98 }
  99
 100 size_t
 101 autr_get_num_anchors(struct val_anchors* anchors)
 102 {
 103         size_t res = 0;
 104         if(!anchors)
 105                 return 0;
 106         lock_basic_lock(&anchors->lock);
 107         if(anchors->autr)
 108                 res = anchors->autr->probe.count;
 109         lock_basic_unlock(&anchors->lock);
 110         return res;
 111 }
 112
 113 /** Position in string */
 114 static int
 115 position_in_string(char *str, const char* sub)
 116 {
 117         char* pos = strstr(str, sub);
 118         if(pos)
 119                 return (int)(pos-str)+(int)strlen(sub);
 120         return -1;
 121 }
 122
 123 /** Debug routine to print pretty key information */
 124 static void
 125 verbose_key(struct autr_ta* ta, enum verbosity_value level,
 126         const char* format, ...) ATTR_FORMAT(printf, 3, 4);
 127
 128 /**
 129  * Implementation of debug pretty key print
 130  * @param ta: trust anchor key with DNSKEY data.
 131  * @param level: verbosity level to print at.
 132  * @param format: printf style format string.
 133  */
 134 static void
 135 verbose_key(struct autr_ta* ta, enum verbosity_value level,
 136         const char* format, ...)
 137 {
 138         va_list args;
 139         va_start(args, format);
 140         if(verbosity >= level) {
 141                 char* str = ldns_rdf2str(ldns_rr_owner(ta->rr));
 142                 int keytag = (int)ldns_calc_keytag(ta->rr);
 143                 char msg[MAXSYSLOGMSGLEN];
 144                 vsnprintf(msg, sizeof(msg), format, args);
 145                 verbose(level, "%s key %d %s", str?str:"??", keytag, msg);
 146                 free(str);
 147         }
 148         va_end(args);
 149 }
 150
 151 /**
 152  * Parse comments
 153  * @param str: to parse
 154  * @param ta: trust key autotrust metadata
 155  * @return false on failure.
 156  */
 157 static int
 158 parse_comments(char* str, struct autr_ta* ta)
 159 {
 160         int len = (int)strlen(str), pos = 0, timestamp = 0;
 161         char* comment = (char*) malloc(sizeof(char)*len+1);
 162         char* comments = comment;
 163         if(!comment) {
 164                 log_err("malloc failure in parse");
 165                 return 0;
 166         }
 167         /* skip over whitespace and data at start of line */
 168         while (*str != '\0' && *str != ';')
 169                 str++;
 170         if (*str == ';')
 171                 str++;
 172         /* copy comments */
 173         while (*str != '\0')
 174         {
 175                 *comments = *str;
 176                 comments++;
 177                 str++;
 178         }
 179         *comments = '\0';
 180
 181         comments = comment;
 182
 183         /* read state */
 184         pos = position_in_string(comments, "state=");
 185         if (pos >= (int) strlen(comments))
 186         {
 187                 log_err("parse error");
 188                 free(comment);
 189                 return 0;
 190         }
 191         if (pos <= 0)
 192                 ta->s = AUTR_STATE_VALID;
 193         else
 194         {
 195                 int s = (int) comments[pos] - '0';
 196                 switch(s)
 197                 {
 198                         case AUTR_STATE_START:
 199                         case AUTR_STATE_ADDPEND:
 200                         case AUTR_STATE_VALID:
 201                         case AUTR_STATE_MISSING:
 202                         case AUTR_STATE_REVOKED:
 203                         case AUTR_STATE_REMOVED:
 204                                 ta->s = s;
 205                                 break;
 206                         default:
 207                                 verbose_key(ta, VERB_OPS, "has undefined "
 208                                         "state, considered NewKey");
 209                                 ta->s = AUTR_STATE_START;
 210                                 break;
 211                 }
 212         }
 213         /* read pending count */
 214         pos = position_in_string(comments, "count=");
 215         if (pos >= (int) strlen(comments))
 216         {
 217                 log_err("parse error");
 218                 free(comment);
 219                 return 0;
 220         }
 221         if (pos <= 0)
 222                 ta->pending_count = 0;
 223         else
 224         {
 225                 comments += pos;
 226                 ta->pending_count = (uint8_t)atoi(comments);
 227         }
 228
 229         /* read last change */
 230         pos = position_in_string(comments, "lastchange=");
 231         if (pos >= (int) strlen(comments))
 232         {
 233                 log_err("parse error");
 234                 free(comment);
 235                 return 0;
 236         }
 237         if (pos >= 0)
 238         {
 239                 comments += pos;
 240                 timestamp = atoi(comments);
 241         }
 242         if (pos < 0 || !timestamp)
 243                 ta->last_change = 0;
 244         else
 245                 ta->last_change = (uint32_t)timestamp;
 246
 247         free(comment);
 248         return 1;
 249 }
 250
 251 /** Check if a line contains data (besides comments) */
 252 static int
 253 str_contains_data(char* str, char comment)
 254 {
 255         while (*str != '\0') {
 256                 if (*str == comment || *str == '\n')
 257                         return 0;
 258                 if (*str != ' ' && *str != '\t')
 259                         return 1;
 260                 str++;
 261         }
 262         return 0;
 263 }
 264
 265 /** Get DNSKEY flags */
 266 static int
 267 dnskey_flags(ldns_rr* rr)
 268 {
 269         if(ldns_rr_get_type(rr) != LDNS_RR_TYPE_DNSKEY)
 270                 return 0;
 271         return (int)ldns_read_uint16(ldns_rdf_data(ldns_rr_dnskey_flags(rr)));
 272 }
 273
 274
 275 /** Check if KSK DNSKEY */
 276 static int
 277 rr_is_dnskey_sep(ldns_rr* rr)
 278 {
 279         return (dnskey_flags(rr)&DNSKEY_BIT_SEP);
 280 }
 281
 282 /** Check if REVOKED DNSKEY */
 283 static int
 284 rr_is_dnskey_revoked(ldns_rr* rr)
 285 {
 286         return (dnskey_flags(rr)&LDNS_KEY_REVOKE_KEY);
 287 }
 288
 289 /** create ta */
 290 static struct autr_ta*
 291 autr_ta_create(ldns_rr* rr)
 292 {
 293         struct autr_ta* ta = (struct autr_ta*)calloc(1, sizeof(*ta));
 294         if(!ta) {
 295                 ldns_rr_free(rr);
 296                 return NULL;
 297         }
 298         ta->rr = rr;
 299         return ta;
 300 }
 301
 302 /** create tp */
 303 static struct trust_anchor*
 304 autr_tp_create(struct val_anchors* anchors, ldns_rdf* own, uint16_t dc)
 305 {
 306         struct trust_anchor* tp = (struct trust_anchor*)calloc(1, sizeof(*tp));
 307         if(!tp) return NULL;
 308         tp->name = memdup(ldns_rdf_data(own), ldns_rdf_size(own));
 309         if(!tp->name) {
 310                 free(tp);
 311                 return NULL;
 312         }
 313         tp->namelen = ldns_rdf_size(own);
 314         tp->namelabs = dname_count_labels(tp->name);
 315         tp->node.key = tp;
 316         tp->dclass = dc;
 317         tp->autr = (struct autr_point_data*)calloc(1, sizeof(*tp->autr));
 318         if(!tp->autr) {
 319                 free(tp->name);
 320                 free(tp);
 321                 return NULL;
 322         }
 323         tp->autr->pnode.key = tp;
 324
 325         lock_basic_lock(&anchors->lock);
 326         if(!rbtree_insert(anchors->tree, &tp->node)) {
 327                 lock_basic_unlock(&anchors->lock);
 328                 log_err("trust anchor presented twice");
 329                 free(tp->name);
 330                 free(tp->autr);
 331                 free(tp);
 332                 return NULL;
 333         }
 334         if(!rbtree_insert(&anchors->autr->probe, &tp->autr->pnode)) {
 335                 (void)rbtree_delete(anchors->tree, tp);
 336                 lock_basic_unlock(&anchors->lock);
 337                 log_err("trust anchor in probetree twice");
 338                 free(tp->name);
 339                 free(tp->autr);
 340                 free(tp);
 341                 return NULL;
 342         }
 343         lock_basic_unlock(&anchors->lock);
 344         lock_basic_init(&tp->lock);
 345         lock_protect(&tp->lock, tp, sizeof(*tp));
 346         lock_protect(&tp->lock, tp->autr, sizeof(*tp->autr));
 347         return tp;
 348 }
 349
 350 /** delete assembled rrsets */
 351 static void
 352 autr_rrset_delete(struct ub_packed_rrset_key* r)
 353 {
 354         if(r) {
 355                 free(r->rk.dname);
 356                 free(r->entry.data);
 357                 free(r);
 358         }
 359 }
 360
 361 void autr_point_delete(struct trust_anchor* tp)
 362 {
 363         if(!tp)
 364                 return;
 365         lock_unprotect(&tp->lock, tp);
 366         lock_unprotect(&tp->lock, tp->autr);
 367         lock_basic_destroy(&tp->lock);
 368         autr_rrset_delete(tp->ds_rrset);
 369         autr_rrset_delete(tp->dnskey_rrset);
 370         if(tp->autr) {
 371                 struct autr_ta* p = tp->autr->keys, *np;
 372                 while(p) {
 373                         np = p->next;
 374                         ldns_rr_free(p->rr);
 375                         free(p);
 376                         p = np;
 377                 }
 378                 free(tp->autr->file);
 379                 free(tp->autr);
 380         }
 381         free(tp->name);
 382         free(tp);
 383 }
 384
 385 /** find or add a new trust point for autotrust */
 386 static struct trust_anchor*
 387 find_add_tp(struct val_anchors* anchors, ldns_rr* rr)
 388 {
 389         struct trust_anchor* tp;
 390         ldns_rdf* own = ldns_rr_owner(rr);
 391         tp = anchor_find(anchors, ldns_rdf_data(own),
 392                 dname_count_labels(ldns_rdf_data(own)),
 393                 ldns_rdf_size(own), ldns_rr_get_class(rr));
 394         if(tp) {
 395                 if(!tp->autr) {
 396                         log_err("anchor cannot be with and without autotrust");
 397                         lock_basic_unlock(&tp->lock);
 398                         return NULL;
 399                 }
 400                 return tp;
 401         }
 402         tp = autr_tp_create(anchors, ldns_rr_owner(rr), ldns_rr_get_class(rr));
 403         lock_basic_lock(&tp->lock);
 404         return tp;
 405 }
 406
 407 /** Add trust anchor from RR */
 408 static struct autr_ta*
 409 add_trustanchor_frm_rr(struct val_anchors* anchors, ldns_rr* rr,
 410         struct trust_anchor** tp)
 411 {
 412         struct autr_ta* ta = autr_ta_create(rr);
 413         if(!ta)
 414                 return NULL;
 415         *tp = find_add_tp(anchors, rr);
 416         if(!*tp) {
 417                 ldns_rr_free(ta->rr);
 418                 free(ta);
 419                 return NULL;
 420         }
 421         /* add ta to tp */
 422         ta->next = (*tp)->autr->keys;
 423         (*tp)->autr->keys = ta;
 424         lock_basic_unlock(&(*tp)->lock);
 425         return ta;
 426 }
 427
 428 /**
 429  * Add new trust anchor from a string in file.
 430  * @param anchors: all anchors
 431  * @param str: string with anchor and comments, if any comments.
 432  * @param tp: trust point returned.
 433  * @param origin: what to use for @
 434  * @param prev: previous rr name
 435  * @param skip: if true, the result is NULL, but not an error, skip it.
 436  * @return new key in trust point.
 437  */
 438 static struct autr_ta*
 439 add_trustanchor_frm_str(struct val_anchors* anchors, char* str,
 440         struct trust_anchor** tp, ldns_rdf* origin, ldns_rdf** prev, int* skip)
 441 {
 442         ldns_rr* rr;
 443         ldns_status lstatus;
 444         if (!str_contains_data(str, ';')) {
 445                 *skip = 1;
 446                 return NULL; /* empty line */
 447         }
 448         if (LDNS_STATUS_OK !=
 449                 (lstatus = ldns_rr_new_frm_str(&rr, str, 0, origin, prev)))
 450         {
 451                 log_err("ldns error while converting string to RR: %s",
 452                         ldns_get_errorstr_by_id(lstatus));
 453                 return NULL;
 454         }
 455         if(ldns_rr_get_type(rr) != LDNS_RR_TYPE_DNSKEY &&
 456                 ldns_rr_get_type(rr) != LDNS_RR_TYPE_DS) {
 457                 ldns_rr_free(rr);
 458                 *skip = 1;
 459                 return NULL; /* only DS and DNSKEY allowed */
 460         }
 461         return add_trustanchor_frm_rr(anchors, rr, tp);
 462 }
 463
 464 /**
 465  * Load single anchor
 466  * @param anchors: all points.
 467  * @param str: comments line
 468  * @param fname: filename
 469  * @param origin: the $ORIGIN.
 470  * @param prev: passed to ldns.
 471  * @param skip: if true, the result is NULL, but not an error, skip it.
 472  * @return false on failure, otherwise the tp read.
 473  */
 474 static struct trust_anchor*
 475 load_trustanchor(struct val_anchors* anchors, char* str, const char* fname,
 476         ldns_rdf* origin, ldns_rdf** prev, int* skip)
 477 {
 478         struct autr_ta* ta = NULL;
 479         struct trust_anchor* tp = NULL;
 480
 481         ta = add_trustanchor_frm_str(anchors, str, &tp, origin, prev, skip);
 482         if(!ta)
 483                 return NULL;
 484         lock_basic_lock(&tp->lock);
 485         if(!parse_comments(str, ta)) {
 486                 lock_basic_unlock(&tp->lock);
 487                 return NULL;
 488         }
 489         if(!tp->autr->file) {
 490                 tp->autr->file = strdup(fname);
 491                 if(!tp->autr->file) {
 492                         lock_basic_unlock(&tp->lock);
 493                         log_err("malloc failure");
 494                         return NULL;
 495                 }
 496         }
 497         lock_basic_unlock(&tp->lock);
 498         return tp;
 499 }
 500
 501 /**
 502  * Assemble the trust anchors into DS and DNSKEY packed rrsets.
 503  * Uses only VALID and MISSING DNSKEYs.
 504  * Read the ldns_rrs and builds packed rrsets
 505  * @param tp: the trust point. Must be locked.
 506  * @return false on malloc failure.
 507  */
 508 static int
 509 autr_assemble(struct trust_anchor* tp)
 510 {
 511         ldns_rr_list* ds, *dnskey;
 512         struct autr_ta* ta;
 513         struct ub_packed_rrset_key* ubds=NULL, *ubdnskey=NULL;
 514
 515         ds = ldns_rr_list_new();
 516         dnskey = ldns_rr_list_new();
 517         if(!ds || !dnskey) {
 518                 ldns_rr_list_free(ds);
 519                 ldns_rr_list_free(dnskey);
 520                 return 0;
 521         }
 522         for(ta = tp->autr->keys; ta; ta = ta->next) {
 523                 if(ldns_rr_get_type(ta->rr) == LDNS_RR_TYPE_DS) {
 524                         if(!ldns_rr_list_push_rr(ds, ta->rr)) {
 525                                 ldns_rr_list_free(ds);
 526                                 ldns_rr_list_free(dnskey);
 527                                 return 0;
 528                         }
 529                 } else if(ta->s == AUTR_STATE_VALID ||
 530                         ta->s == AUTR_STATE_MISSING) {
 531                         if(!ldns_rr_list_push_rr(dnskey, ta->rr)) {
 532                                 ldns_rr_list_free(ds);
 533                                 ldns_rr_list_free(dnskey);
 534                                 return 0;
 535                         }
 536                 }
 537         }
 538
 539         /* make packed rrset keys - malloced with no ID number, they
 540          * are not in the cache */
 541         /* make packed rrset data (if there is a key) */
 542
 543         if(ldns_rr_list_rr_count(ds) > 0) {
 544                 ubds = ub_packed_rrset_heap_key(ds);
 545                 if(!ubds)
 546                         goto error_cleanup;
 547                 ubds->entry.data = packed_rrset_heap_data(ds);
 548                 if(!ubds->entry.data)
 549                         goto error_cleanup;
 550         }
 551         if(ldns_rr_list_rr_count(dnskey) > 0) {
 552                 ubdnskey = ub_packed_rrset_heap_key(dnskey);
 553                 if(!ubdnskey)
 554                         goto error_cleanup;
 555                 ubdnskey->entry.data = packed_rrset_heap_data(dnskey);
 556                 if(!ubdnskey->entry.data) {
 557                 error_cleanup:
 558                         autr_rrset_delete(ubds);
 559                         autr_rrset_delete(ubdnskey);
 560                         ldns_rr_list_free(ds);
 561                         ldns_rr_list_free(dnskey);
 562                         return 0;
 563                 }
 564         }
 565         /* we have prepared the new keys so nothing can go wrong any more.
 566          * And we are sure we cannot be left without trustanchor after
 567          * any errors. Put in the new keys and remove old ones. */
 568
 569         /* free the old data */
 570         autr_rrset_delete(tp->ds_rrset);
 571         autr_rrset_delete(tp->dnskey_rrset);
 572
 573         /* assign the data to replace the old */
 574         tp->ds_rrset = ubds;
 575         tp->dnskey_rrset = ubdnskey;
 576         tp->numDS = ldns_rr_list_rr_count(ds);
 577         tp->numDNSKEY = ldns_rr_list_rr_count(dnskey);
 578
 579         ldns_rr_list_free(ds);
 580         ldns_rr_list_free(dnskey);
 581         return 1;
 582 }
 583
 584 /** parse integer */
 585 static unsigned int
 586 parse_int(char* line, int* ret)
 587 {
 588         char *e;
 589         unsigned int x = (unsigned int)strtol(line, &e, 10);
 590         if(line == e) {
 591                 *ret = -1; /* parse error */
 592                 return 0;
 593         }
 594         *ret = 1; /* matched */
 595         return x;
 596 }
 597
 598 /** parse id sequence for anchor */
 599 static struct trust_anchor*
 600 parse_id(struct val_anchors* anchors, char* line)
 601 {
 602         struct trust_anchor *tp;
 603         int r;
 604         ldns_rdf* rdf;
 605         uint16_t dclass;
 606         /* read the owner name */
 607         char* next = strchr(line, ' ');
 608         if(!next)
 609                 return NULL;
 610         next[0] = 0;
 611         rdf = ldns_dname_new_frm_str(line);
 612         if(!rdf)
 613                 return NULL;
 614
 615         /* read the class */
 616         dclass = parse_int(next+1, &r);
 617         if(r == -1) {
 618                 ldns_rdf_deep_free(rdf);
 619                 return NULL;
 620         }
 621
 622         /* find the trust point */
 623         tp = autr_tp_create(anchors, rdf, dclass);
 624         ldns_rdf_deep_free(rdf);
 625         return tp;
 626 }
 627
 628 /**
 629  * Parse variable from trustanchor header
 630  * @param line: to parse
 631  * @param anchors: the anchor is added to this, if "id:" is seen.
 632  * @param anchor: the anchor as result value or previously returned anchor
 633  *      value to read the variable lines into.
 634  * @return: 0 no match, -1 failed syntax error, +1 success line read.
 635  *      +2 revoked trust anchor file.
 636  */
 637 static int
 638 parse_var_line(char* line, struct val_anchors* anchors,
 639         struct trust_anchor** anchor)
 640 {
 641         struct trust_anchor* tp = *anchor;
 642         int r = 0;
 643         if(strncmp(line, ";;id: ", 6) == 0) {
 644                 *anchor = parse_id(anchors, line+6);
 645                 if(!*anchor) return -1;
 646                 else return 1;
 647         } else if(strncmp(line, ";;REVOKED", 9) == 0) {
 648                 if(tp) {
 649                         log_err("REVOKED statement must be at start of file");
 650                         return -1;
 651                 }
 652                 return 2;
 653         } else if(strncmp(line, ";;last_queried: ", 16) == 0) {
 654                 if(!tp) return -1;
 655                 lock_basic_lock(&tp->lock);
 656                 tp->autr->last_queried = (time_t)parse_int(line+16, &r);
 657                 lock_basic_unlock(&tp->lock);
 658         } else if(strncmp(line, ";;last_success: ", 16) == 0) {
 659                 if(!tp) return -1;
 660                 lock_basic_lock(&tp->lock);
 661                 tp->autr->last_success = (time_t)parse_int(line+16, &r);
 662                 lock_basic_unlock(&tp->lock);
 663         } else if(strncmp(line, ";;next_probe_time: ", 19) == 0) {
 664                 if(!tp) return -1;
 665                 lock_basic_lock(&anchors->lock);
 666                 lock_basic_lock(&tp->lock);
 667                 (void)rbtree_delete(&anchors->autr->probe, tp);
 668                 tp->autr->next_probe_time = (time_t)parse_int(line+19, &r);
 669                 (void)rbtree_insert(&anchors->autr->probe, &tp->autr->pnode);
 670                 lock_basic_unlock(&tp->lock);
 671                 lock_basic_unlock(&anchors->lock);
 672         } else if(strncmp(line, ";;query_failed: ", 16) == 0) {
 673                 if(!tp) return -1;
 674                 lock_basic_lock(&tp->lock);
 675                 tp->autr->query_failed = (uint8_t)parse_int(line+16, &r);
 676                 lock_basic_unlock(&tp->lock);
 677         } else if(strncmp(line, ";;query_interval: ", 18) == 0) {
 678                 if(!tp) return -1;
 679                 lock_basic_lock(&tp->lock);
 680                 tp->autr->query_interval = (uint32_t)parse_int(line+18, &r);
 681                 lock_basic_unlock(&tp->lock);
 682         } else if(strncmp(line, ";;retry_time: ", 14) == 0) {
 683                 if(!tp) return -1;
 684                 lock_basic_lock(&tp->lock);
 685                 tp->autr->retry_time = (uint32_t)parse_int(line+14, &r);
 686                 lock_basic_unlock(&tp->lock);
 687         }
 688         return r;
 689 }
 690
 691 /** handle origin lines */
 692 static int
 693 handle_origin(char* line, ldns_rdf** origin)
 694 {
 695         while(isspace((int)*line))
 696                 line++;
 697         if(strncmp(line, "$ORIGIN", 7) != 0)
 698                 return 0;
 699         ldns_rdf_deep_free(*origin);
 700         line += 7;
 701         while(isspace((int)*line))
 702                 line++;
 703         *origin = ldns_dname_new_frm_str(line);
 704         if(!*origin)
 705                 log_warn("malloc failure or parse error in $ORIGIN");
 706         return 1;
 707 }
 708
 709 /** Read one line and put multiline RRs onto one line string */
 710 static int
 711 read_multiline(char* buf, size_t len, FILE* in, int* linenr)
 712 {
 713         char* pos = buf;
 714         size_t left = len;
 715         int depth = 0;
 716         buf[len-1] = 0;
 717         while(left > 0 && fgets(pos, (int)left, in) != NULL) {
 718                 size_t i, poslen = strlen(pos);
 719                 (*linenr)++;
 720
 721                 /* check what the new depth is after the line */
 722                 /* this routine cannot handle braces inside quotes,
 723                    say for TXT records, but this routine only has to read keys */
 724                 for(i=0; i<poslen; i++) {
 725                         if(pos[i] == '(') {
 726                                 depth++;
 727                         } else if(pos[i] == ')') {
 728                                 if(depth == 0) {
 729                                         log_err("mismatch: too many ')'");
 730                                         return -1;
 731                                 }
 732                                 depth--;
 733                         } else if(pos[i] == ';') {
 734                                 break;
 735                         }
 736                 }
 737
 738                 /* normal oneline or last line: keeps newline and comments */
 739                 if(depth == 0) {
 740                         return 1;
 741                 }
 742
 743                 /* more lines expected, snip off comments and newline */
 744                 if(poslen>0)
 745                         pos[poslen-1] = 0; /* strip newline */
 746                 if(strchr(pos, ';'))
 747                         strchr(pos, ';')[0] = 0; /* strip comments */
 748
 749                 /* move to paste other lines behind this one */
 750                 poslen = strlen(pos);
 751                 pos += poslen;
 752                 left -= poslen;
 753                 /* the newline is changed into a space */
 754                 if(left <= 2 /* space and eos */) {
 755                         log_err("line too long");
 756                         return -1;
 757                 }
 758                 pos[0] = ' ';
 759                 pos[1] = 0;
 760                 pos += 1;
 761                 left -= 1;
 762         }
 763         if(depth != 0) {
 764                 log_err("mismatch: too many '('");
 765                 return -1;
 766         }
 767         if(pos != buf)
 768                 return 1;
 769         return 0;
 770 }
 771
 772 int autr_read_file(struct val_anchors* anchors, const char* nm)
 773 {
 774         /* the file descriptor */
 775         FILE* fd;
 776         /* keep track of line numbers */
 777         int line_nr = 0;
 778         /* single line */
 779         char line[10240];
 780         /* trust point being read */
 781         struct trust_anchor *tp = NULL, *tp2;
 782         int r;
 783         /* for $ORIGIN parsing */
 784         ldns_rdf *origin=NULL, *prev=NULL;
 785
 786         if (!(fd = fopen(nm, "r"))) {
 787                 log_err("unable to open %s for reading: %s",
 788                         nm, strerror(errno));
 789                 return 0;
 790         }
 791         verbose(VERB_ALGO, "reading autotrust anchor file %s", nm);
 792         while ( (r=read_multiline(line, sizeof(line), fd, &line_nr)) != 0) {
 793                 if(r == -1 || (r = parse_var_line(line, anchors, &tp)) == -1) {
 794                         log_err("could not parse auto-trust-anchor-file "
 795                                 "%s line %d", nm, line_nr);
 796                         fclose(fd);
 797                         ldns_rdf_deep_free(origin);
 798                         ldns_rdf_deep_free(prev);
 799                         return 0;
 800                 } else if(r == 1) {
 801                         continue;
 802                 } else if(r == 2) {
 803                         log_warn("trust anchor %s has been revoked", nm);
 804                         fclose(fd);
 805                         ldns_rdf_deep_free(origin);
 806                         ldns_rdf_deep_free(prev);
 807                         return 1;
 808                 }
 809                 if (!str_contains_data(line, ';'))
 810                         continue; /* empty lines allowed */
 811                 if(handle_origin(line, &origin))
 812                         continue;
 813                 r = 0;
 814                 if(!(tp2=load_trustanchor(anchors, line, nm, origin, &prev,
 815                         &r))) {
 816                         if(!r) log_err("failed to load trust anchor from %s "
 817                                 "at line %i, skipping", nm, line_nr);
 818                         /* try to do the rest */
 819                         continue;
 820                 }
 821                 if(tp && tp != tp2) {
 822                         log_err("file %s has mismatching data inside: "
 823                                 "the file may only contain keys for one name, "
 824                                 "remove keys for other domain names", nm);
 825                         fclose(fd);
 826                         ldns_rdf_deep_free(origin);
 827                         ldns_rdf_deep_free(prev);
 828                         return 0;
 829                 }
 830                 tp = tp2;
 831         }
 832         fclose(fd);
 833         ldns_rdf_deep_free(origin);
 834         ldns_rdf_deep_free(prev);
 835         if(!tp) {
 836                 log_err("failed to read %s", nm);
 837                 return 0;
 838         }
 839
 840         /* now assemble the data into DNSKEY and DS packed rrsets */
 841         lock_basic_lock(&tp->lock);
 842         if(!autr_assemble(tp)) {
 843                 lock_basic_unlock(&tp->lock);
 844                 log_err("malloc failure assembling %s", nm);
 845                 return 0;
 846         }
 847         lock_basic_unlock(&tp->lock);
 848         return 1;
 849 }
 850
 851 /** string for a trustanchor state */
 852 static const char*
 853 trustanchor_state2str(autr_state_t s)
 854 {
 855         switch (s) {
 856                 case AUTR_STATE_START:       return "  START  ";
 857                 case AUTR_STATE_ADDPEND:     return " ADDPEND ";
 858                 case AUTR_STATE_VALID:       return "  VALID  ";
 859                 case AUTR_STATE_MISSING:     return " MISSING ";
 860                 case AUTR_STATE_REVOKED:     return " REVOKED ";
 861                 case AUTR_STATE_REMOVED:     return " REMOVED ";
 862         }
 863         return " UNKNOWN ";
 864 }
 865
 866 /** print ID to file */
 867 static int
 868 print_id(FILE* out, char* fname, struct module_env* env,
 869         uint8_t* nm, size_t nmlen, uint16_t dclass)
 870 {
 871         ldns_rdf rdf;
 872 #ifdef UNBOUND_DEBUG
 873         ldns_status s;
 874 #endif
 875
 876         memset(&rdf, 0, sizeof(rdf));
 877         ldns_rdf_set_data(&rdf, nm);
 878         ldns_rdf_set_size(&rdf, nmlen);
 879         ldns_rdf_set_type(&rdf, LDNS_RDF_TYPE_DNAME);
 880
 881         ldns_buffer_clear(env->scratch_buffer);
 882 #ifdef UNBOUND_DEBUG
 883         s =
 884 #endif
 885         ldns_rdf2buffer_str_dname(env->scratch_buffer, &rdf);
 886         log_assert(s == LDNS_STATUS_OK);
 887         ldns_buffer_write_u8(env->scratch_buffer, 0);
 888         ldns_buffer_flip(env->scratch_buffer);
 889         if(fprintf(out, ";;id: %s %d\n",
 890                 (char*)ldns_buffer_begin(env->scratch_buffer),
 891                 (int)dclass) < 0) {
 892                 log_err("could not write to %s: %s", fname, strerror(errno));
 893                 return 0;
 894         }
 895         return 1;
 896 }
 897
 898 static int
 899 autr_write_contents(FILE* out, char* fn, struct module_env* env,
 900         struct trust_anchor* tp)
 901 {
 902         char tmi[32];
 903         struct autr_ta* ta;
 904         char* str;
 905
 906         /* write pretty header */
 907         if(fprintf(out, "; autotrust trust anchor file\n") < 0) {
 908                 log_err("could not write to %s: %s", fn, strerror(errno));
 909                 return 0;
 910         }
 911         if(tp->autr->revoked) {
 912                 if(fprintf(out, ";;REVOKED\n") < 0 ||
 913                    fprintf(out, "; The zone has all keys revoked, and is\n"
 914                         "; considered as if it has no trust anchors.\n"
 915                         "; the remainder of the file is the last probe.\n"
 916                         "; to restart the trust anchor, overwrite this file.\n"
 917                         "; with one containing valid DNSKEYs or DSes.\n") < 0) {
 918                    log_err("could not write to %s: %s", fn, strerror(errno));
 919                    return 0;
 920                 }
 921         }
 922         if(!print_id(out, fn, env, tp->name, tp->namelen, tp->dclass)) {
 923                 return 0;
 924         }
 925         if(fprintf(out, ";;last_queried: %u ;;%s",
 926                 (unsigned int)tp->autr->last_queried,
 927                 ctime_r(&(tp->autr->last_queried), tmi)) < 0 ||
 928            fprintf(out, ";;last_success: %u ;;%s",
 929                 (unsigned int)tp->autr->last_success,
 930                 ctime_r(&(tp->autr->last_success), tmi)) < 0 ||
 931            fprintf(out, ";;next_probe_time: %u ;;%s",
 932                 (unsigned int)tp->autr->next_probe_time,
 933                 ctime_r(&(tp->autr->next_probe_time), tmi)) < 0 ||
 934            fprintf(out, ";;query_failed: %d\n", (int)tp->autr->query_failed)<0
 935            || fprintf(out, ";;query_interval: %d\n",
 936            (int)tp->autr->query_interval) < 0 ||
 937            fprintf(out, ";;retry_time: %d\n", (int)tp->autr->retry_time) < 0) {
 938                 log_err("could not write to %s: %s", fn, strerror(errno));
 939                 return 0;
 940         }
 941
 942         /* write anchors */
 943         for(ta=tp->autr->keys; ta; ta=ta->next) {
 944                 /* by default do not store START and REMOVED keys */
 945                 if(ta->s == AUTR_STATE_START)
 946                         continue;
 947                 if(ta->s == AUTR_STATE_REMOVED)
 948                         continue;
 949                 /* only store keys */
 950                 if(ldns_rr_get_type(ta->rr) != LDNS_RR_TYPE_DNSKEY)
 951                         continue;
 952                 str = ldns_rr2str(ta->rr);
 953                 if(!str || !str[0]) {
 954                         free(str);
 955                         log_err("malloc failure writing %s", fn);
 956                         return 0;
 957                 }
 958                 str[strlen(str)-1] = 0; /* remove newline */
 959                 if(fprintf(out, "%s ;;state=%d [%s] ;;count=%d "
 960                         ";;lastchange=%u ;;%s", str, (int)ta->s,
 961                         trustanchor_state2str(ta->s), (int)ta->pending_count,
 962                         (unsigned int)ta->last_change,
 963                         ctime_r(&(ta->last_change), tmi)) < 0) {
 964                    log_err("could not write to %s: %s", fn, strerror(errno));
 965                    free(str);
 966                    return 0;
 967                 }
 968                 free(str);
 969         }
 970         return 1;
 971 }
 972
 973 void autr_write_file(struct module_env* env, struct trust_anchor* tp)
 974 {
 975         FILE* out;
 976         char* fname = tp->autr->file;
 977         char tempf[2048];
 978         log_assert(tp->autr);
 979         /* unique name with pid number and thread number */
 980         snprintf(tempf, sizeof(tempf), "%s.%d-%d", fname, (int)getpid(),
 981                 env&&env->worker?*(int*)env->worker:0);
 982         verbose(VERB_ALGO, "autotrust: write to disk: %s", tempf);
 983         out = fopen(tempf, "w");
 984         if(!out) {
 985                 log_err("could not open autotrust file for writing, %s: %s",
 986                         tempf, strerror(errno));
 987                 return;
 988         }
 989         if(!autr_write_contents(out, tempf, env, tp)) {
 990                 /* failed to write contents (completely) */
 991                 fclose(out);
 992                 unlink(tempf);
 993                 log_err("could not completely write: %s", fname);
 994                 return;
 995         }
 996         /* success; overwrite actual file */
 997         fclose(out);
 998         verbose(VERB_ALGO, "autotrust: replaced %s", fname);
 999 #ifdef UB_ON_WINDOWS
1000         (void)unlink(fname); /* windows does not replace file with rename() */
1001 #endif
1002         if(rename(tempf, fname) < 0) {
1003                 log_err("rename(%s to %s): %s", tempf, fname, strerror(errno));
1004         }
1005 }
1006
1007 /**
1008  * Verify if dnskey works for trust point
1009  * @param env: environment (with time) for verification
1010  * @param ve: validator environment (with options) for verification.
1011  * @param tp: trust point to verify with
1012  * @param rrset: DNSKEY rrset to verify.
1013  * @return false on failure, true if verification successful.
1014  */
1015 static int
1016 verify_dnskey(struct module_env* env, struct val_env* ve,
1017         struct trust_anchor* tp, struct ub_packed_rrset_key* rrset)
1018 {
1019         char* reason = NULL;
1020         uint8_t sigalg[ALGO_NEEDS_MAX+1];
1021         int downprot = 1;
1022         enum sec_status sec = val_verify_DNSKEY_with_TA(env, ve, rrset,
1023                 tp->ds_rrset, tp->dnskey_rrset, downprot?sigalg:NULL, &reason);
1024         /* sigalg is ignored, it returns algorithms signalled to exist, but
1025          * in 5011 there are no other rrsets to check.  if downprot is
1026          * enabled, then it checks that the DNSKEY is signed with all
1027          * algorithms available in the trust store. */
1028         verbose(VERB_ALGO, "autotrust: validate DNSKEY with anchor: %s",
1029                 sec_status_to_string(sec));
1030         return sec == sec_status_secure;
1031 }
1032
1033 /** Find minimum expiration interval from signatures */
1034 static uint32_t
1035 min_expiry(struct module_env* env, ldns_rr_list* rrset)
1036 {
1037         size_t i;
1038         uint32_t t, r = 15 * 24 * 3600; /* 15 days max */
1039         for(i=0; i<ldns_rr_list_rr_count(rrset); i++) {
1040                 ldns_rr* rr = ldns_rr_list_rr(rrset, i);
1041                 if(ldns_rr_get_type(rr) != LDNS_RR_TYPE_RRSIG)
1042                         continue;
1043                 t = ldns_rdf2native_int32(ldns_rr_rrsig_expiration(rr));
1044                 if(t - *env->now > 0) {
1045                         t -= *env->now;
1046                         if(t < r)
1047                                 r = t;
1048                 }
1049         }
1050         return r;
1051 }
1052
1053 /** Is rr self-signed revoked key */
1054 static int
1055 rr_is_selfsigned_revoked(struct module_env* env, struct val_env* ve,
1056         struct ub_packed_rrset_key* dnskey_rrset, size_t i)
1057 {
1058         enum sec_status sec;
1059         char* reason = NULL;
1060         verbose(VERB_ALGO, "seen REVOKE flag, check self-signed, rr %d",
1061                 (int)i);
1062         /* no algorithm downgrade protection necessary, if it is selfsigned
1063          * revoked it can be removed. */
1064         sec = dnskey_verify_rrset(env, ve, dnskey_rrset, dnskey_rrset, i,
1065                 &reason);
1066         return (sec == sec_status_secure);
1067 }
1068
1069 /** Set fetched value */
1070 static void
1071 seen_trustanchor(struct autr_ta* ta, uint8_t seen)
1072 {
1073         ta->fetched = seen;
1074         if(ta->pending_count < 250) /* no numerical overflow, please */
1075                 ta->pending_count++;
1076 }
1077
1078 /** set revoked value */
1079 static void
1080 seen_revoked_trustanchor(struct autr_ta* ta, uint8_t revoked)
1081 {
1082         ta->revoked = revoked;
1083 }
1084
1085 /** revoke a trust anchor */
1086 static void
1087 revoke_dnskey(struct autr_ta* ta, int off)
1088 {
1089         ldns_rdf* rdf;
1090         uint16_t flags;
1091         log_assert(ta && ta->rr);
1092         if(ldns_rr_get_type(ta->rr) != LDNS_RR_TYPE_DNSKEY)
1093                 return;
1094         rdf = ldns_rr_dnskey_flags(ta->rr);
1095         flags = ldns_read_uint16(ldns_rdf_data(rdf));
1096
1097         if (off && (flags&LDNS_KEY_REVOKE_KEY))
1098                 flags ^= LDNS_KEY_REVOKE_KEY; /* flip */
1099         else
1100                 flags |= LDNS_KEY_REVOKE_KEY;
1101         ldns_write_uint16(ldns_rdf_data(rdf), flags);
1102 }
1103
1104 /** Compare two RR buffers skipping the REVOKED bit */
1105 static int
1106 ldns_rr_compare_wire_skip_revbit(ldns_buffer* rr1_buf, ldns_buffer* rr2_buf)
1107 {
1108         size_t rr1_len, rr2_len, min_len, i, offset;
1109         rr1_len = ldns_buffer_capacity(rr1_buf);
1110         rr2_len = ldns_buffer_capacity(rr2_buf);
1111         /* jump past dname (checked in earlier part) and especially past TTL */
1112         offset = 0;
1113         while (offset < rr1_len && *ldns_buffer_at(rr1_buf, offset) != 0)
1114                 offset += *ldns_buffer_at(rr1_buf, offset) + 1;
1115         /* jump to rdata section (PAST the rdata length field) */
1116         offset += 11; /* 0-dname-end + type + class + ttl + rdatalen */
1117         min_len = (rr1_len < rr2_len) ? rr1_len : rr2_len;
1118         /* compare RRs RDATA byte for byte. */
1119         for(i = offset; i < min_len; i++)
1120         {
1121                 uint8_t *rdf1, *rdf2;
1122                 rdf1 = ldns_buffer_at(rr1_buf, i);
1123                 rdf2 = ldns_buffer_at(rr2_buf, i);
1124                 if (i==(offset+1))
1125                 {
1126                         /* this is the second part of the flags field */
1127                         *rdf1 = *rdf1 | LDNS_KEY_REVOKE_KEY;
1128                         *rdf2 = *rdf2 | LDNS_KEY_REVOKE_KEY;
1129                 }
1130                 if (*rdf1 < *rdf2)      return -1;
1131                 else if (*rdf1 > *rdf2) return 1;
1132         }
1133         return 0;
1134 }
1135
1136 /** Compare two RRs skipping the REVOKED bit */
1137 static int
1138 ldns_rr_compare_skip_revbit(const ldns_rr* rr1, const ldns_rr* rr2, int* result)
1139 {
1140         size_t rr1_len, rr2_len;
1141         ldns_buffer* rr1_buf;
1142         ldns_buffer* rr2_buf;
1143
1144         *result = ldns_rr_compare_no_rdata(rr1, rr2);
1145         if (*result == 0)
1146         {
1147                 rr1_len = ldns_rr_uncompressed_size(rr1);
1148                 rr2_len = ldns_rr_uncompressed_size(rr2);
1149                 rr1_buf = ldns_buffer_new(rr1_len);
1150                 rr2_buf = ldns_buffer_new(rr2_len);
1151                 if(!rr1_buf || !rr2_buf) {
1152                         ldns_buffer_free(rr1_buf);
1153                         ldns_buffer_free(rr2_buf);
1154                         return 0;
1155                 }
1156                 if (ldns_rr2buffer_wire_canonical(rr1_buf, rr1,
1157                         LDNS_SECTION_ANY) != LDNS_STATUS_OK)
1158                 {
1159                         ldns_buffer_free(rr1_buf);
1160                         ldns_buffer_free(rr2_buf);
1161                         return 0;
1162                 }
1163                 if (ldns_rr2buffer_wire_canonical(rr2_buf, rr2,
1164                         LDNS_SECTION_ANY) != LDNS_STATUS_OK) {
1165                         ldns_buffer_free(rr1_buf);
1166                         ldns_buffer_free(rr2_buf);
1167                         return 0;
1168                 }
1169                 *result = ldns_rr_compare_wire_skip_revbit(rr1_buf, rr2_buf);
1170                 ldns_buffer_free(rr1_buf);
1171                 ldns_buffer_free(rr2_buf);
1172         }
1173         return 1;
1174 }
1175
1176
1177 /** compare two trust anchors */
1178 static int
1179 ta_compare(ldns_rr* a, ldns_rr* b, int* result)
1180 {
1181         if (!a && !b)   *result = 0;
1182         else if (!a)    *result = -1;
1183         else if (!b)    *result = 1;
1184         else if (ldns_rr_get_type(a) != ldns_rr_get_type(b))
1185                 *result = (int)ldns_rr_get_type(a) - (int)ldns_rr_get_type(b);
1186         else if (ldns_rr_get_type(a) == LDNS_RR_TYPE_DNSKEY) {
1187                 if(!ldns_rr_compare_skip_revbit(a, b, result))
1188                         return 0;
1189         }
1190         else if (ldns_rr_get_type(a) == LDNS_RR_TYPE_DS)
1191                 *result = ldns_rr_compare(a, b);
1192         else    *result = -1;
1193         return 1;
1194 }
1195
1196 /**
1197  * Find key
1198  * @param tp: to search in
1199  * @param rr: to look for
1200  * @param result: returns NULL or the ta key looked for.
1201  * @return false on malloc failure during search. if true examine result.
1202  */
1203 static int
1204 find_key(struct trust_anchor* tp, ldns_rr* rr, struct autr_ta** result)
1205 {
1206         struct autr_ta* ta;
1207         int ret;
1208         if(!tp || !rr)
1209                 return 0;
1210         for(ta=tp->autr->keys; ta; ta=ta->next) {
1211                 if(!ta_compare(ta->rr, rr, &ret))
1212                         return 0;
1213                 if(ret == 0) {
1214                         *result = ta;
1215                         return 1;
1216                 }
1217         }
1218         *result = NULL;
1219         return 1;
1220 }
1221
1222 /** add key and clone RR and tp already locked */
1223 static struct autr_ta*
1224 add_key(struct trust_anchor* tp, ldns_rr* rr)
1225 {
1226         ldns_rr* c;
1227         struct autr_ta* ta;
1228         c = ldns_rr_clone(rr);
1229         if(!c) return NULL;
1230         ta = autr_ta_create(c);
1231         if(!ta) {
1232                 ldns_rr_free(c);
1233                 return NULL;
1234         }
1235         /* link in, tp already locked */
1236         ta->next = tp->autr->keys;
1237         tp->autr->keys = ta;
1238         return ta;
1239 }
1240
1241 /** get TTL from DNSKEY rrset */
1242 static uint32_t
1243 key_ttl(struct ub_packed_rrset_key* k)
1244 {
1245         struct packed_rrset_data* d = (struct packed_rrset_data*)k->entry.data;
1246         return d->ttl;
1247 }
1248
1249 /** update the time values for the trustpoint */
1250 static void
1251 set_tp_times(struct trust_anchor* tp, uint32_t rrsig_exp_interval,
1252         uint32_t origttl, int* changed)
1253 {
1254         uint32_t x, qi = tp->autr->query_interval, rt = tp->autr->retry_time;
1255
1256         /* x = MIN(15days, ttl/2, expire/2) */
1257         x = 15 * 24 * 3600;
1258         if(origttl/2 < x)
1259                 x = origttl/2;
1260         if(rrsig_exp_interval/2 < x)
1261                 x = rrsig_exp_interval/2;
1262         /* MAX(1hr, x) */
1263         if(x < 3600)
1264                 tp->autr->query_interval = 3600;
1265         else    tp->autr->query_interval = x;
1266
1267         /* x= MIN(1day, ttl/10, expire/10) */
1268         x = 24 * 3600;
1269         if(origttl/10 < x)
1270                 x = origttl/10;
1271         if(rrsig_exp_interval/10 < x)
1272                 x = rrsig_exp_interval/10;
1273         /* MAX(1hr, x) */
1274         if(x < 3600)
1275                 tp->autr->retry_time = 3600;
1276         else    tp->autr->retry_time = x;
1277
1278         if(qi != tp->autr->query_interval || rt != tp->autr->retry_time) {
1279                 *changed = 1;
1280                 verbose(VERB_ALGO, "orig_ttl is %d", (int)origttl);
1281                 verbose(VERB_ALGO, "rrsig_exp_interval is %d",
1282                         (int)rrsig_exp_interval);
1283                 verbose(VERB_ALGO, "query_interval: %d, retry_time: %d",
1284                         (int)tp->autr->query_interval,
1285                         (int)tp->autr->retry_time);
1286         }
1287 }
1288
1289 /** init events to zero */
1290 static void
1291 init_events(struct trust_anchor* tp)
1292 {
1293         struct autr_ta* ta;
1294         for(ta=tp->autr->keys; ta; ta=ta->next) {
1295                 ta->fetched = 0;
1296         }
1297 }
1298
1299 /** check for revoked keys without trusting any other information */
1300 static void
1301 check_contains_revoked(struct module_env* env, struct val_env* ve,
1302         struct trust_anchor* tp, struct ub_packed_rrset_key* dnskey_rrset,
1303         int* changed)
1304 {
1305         ldns_rr_list* r = packed_rrset_to_rr_list(dnskey_rrset,
1306                 env->scratch_buffer);
1307         size_t i;
1308         if(!r) {
1309                 log_err("malloc failure");
1310                 return;
1311         }
1312         for(i=0; i<ldns_rr_list_rr_count(r); i++) {
1313                 ldns_rr* rr = ldns_rr_list_rr(r, i);
1314                 struct autr_ta* ta = NULL;
1315                 if(ldns_rr_get_type(rr) != LDNS_RR_TYPE_DNSKEY)
1316                         continue;
1317                 if(!rr_is_dnskey_sep(rr) || !rr_is_dnskey_revoked(rr))
1318                         continue; /* not a revoked KSK */
1319                 if(!find_key(tp, rr, &ta)) {
1320                         log_err("malloc failure");
1321                         continue; /* malloc fail in compare*/
1322                 }
1323                 if(!ta)
1324                         continue; /* key not found */
1325                 if(rr_is_selfsigned_revoked(env, ve, dnskey_rrset, i)) {
1326                         /* checked if there is an rrsig signed by this key. */
1327                         log_assert(dnskey_calc_keytag(dnskey_rrset, i) ==
1328                                 ldns_calc_keytag(rr)); /* checks conversion*/
1329                         verbose_key(ta, VERB_ALGO, "is self-signed revoked");
1330                         if(!ta->revoked)
1331                                 *changed = 1;
1332                         seen_revoked_trustanchor(ta, 1);
1333                         do_revoked(env, ta, changed);
1334                 }
1335         }
1336         ldns_rr_list_deep_free(r);
1337 }
1338
1339 /** See if a DNSKEY is verified by one of the DSes */
1340 static int
1341 key_matches_a_ds(struct module_env* env, struct val_env* ve,
1342         struct ub_packed_rrset_key* dnskey_rrset, size_t key_idx,
1343         struct ub_packed_rrset_key* ds_rrset)
1344 {
1345         struct packed_rrset_data* dd = (struct packed_rrset_data*)
1346                         ds_rrset->entry.data;
1347         size_t ds_idx, num = dd->count;
1348         int d = val_favorite_ds_algo(ds_rrset);
1349         char* reason = "";
1350         for(ds_idx=0; ds_idx<num; ds_idx++) {
1351                 if(!ds_digest_algo_is_supported(ds_rrset, ds_idx) ||
1352                         !ds_key_algo_is_supported(ds_rrset, ds_idx) ||
1353                         ds_get_digest_algo(ds_rrset, ds_idx) != d)
1354                         continue;
1355                 if(ds_get_key_algo(ds_rrset, ds_idx)
1356                    != dnskey_get_algo(dnskey_rrset, key_idx)
1357                    || dnskey_calc_keytag(dnskey_rrset, key_idx)
1358                    != ds_get_keytag(ds_rrset, ds_idx)) {
1359                         continue;
1360                 }
1361                 if(!ds_digest_match_dnskey(env, dnskey_rrset, key_idx,
1362                         ds_rrset, ds_idx)) {
1363                         verbose(VERB_ALGO, "DS match attempt failed");
1364                         continue;
1365                 }
1366                 if(dnskey_verify_rrset(env, ve, dnskey_rrset,
1367                         dnskey_rrset, key_idx, &reason) == sec_status_secure) {
1368                         return 1;
1369                 } else {
1370                         verbose(VERB_ALGO, "DS match failed because the key "
1371                                 "does not verify the keyset: %s", reason);
1372                 }
1373         }
1374         return 0;
1375 }
1376
1377 /** Set update events */
1378 static int
1379 update_events(struct module_env* env, struct val_env* ve,
1380         struct trust_anchor* tp, struct ub_packed_rrset_key* dnskey_rrset,
1381         int* changed)
1382 {
1383         ldns_rr_list* r = packed_rrset_to_rr_list(dnskey_rrset,
1384                 env->scratch_buffer);
1385         size_t i;
1386         if(!r)
1387                 return 0;
1388         init_events(tp);
1389         for(i=0; i<ldns_rr_list_rr_count(r); i++) {
1390                 ldns_rr* rr = ldns_rr_list_rr(r, i);
1391                 struct autr_ta* ta = NULL;
1392                 if(ldns_rr_get_type(rr) != LDNS_RR_TYPE_DNSKEY)
1393                         continue;
1394                 if(!rr_is_dnskey_sep(rr))
1395                         continue;
1396                 if(rr_is_dnskey_revoked(rr)) {
1397                         /* self-signed revoked keys already detected before,
1398                          * other revoked keys are not 'added' again */
1399                         continue;
1400                 }
1401                 /* is a key of this type supported?. Note rr_list and
1402                  * packed_rrset are in the same order. */
1403                 if(!dnskey_algo_is_supported(dnskey_rrset, i)) {
1404                         /* skip unknown algorithm key, it is useless to us */
1405                         log_nametypeclass(VERB_DETAIL, "trust point has "
1406                                 "unsupported algorithm at",
1407                                 tp->name, LDNS_RR_TYPE_DNSKEY, tp->dclass);
1408                         continue;
1409                 }
1410
1411                 /* is it new? if revocation bit set, find the unrevoked key */
1412                 if(!find_key(tp, rr, &ta)) {
1413                         ldns_rr_list_deep_free(r); /* malloc fail in compare*/
1414                         return 0;
1415                 }
1416                 if(!ta) {
1417                         ta = add_key(tp, rr);
1418                         *changed = 1;
1419                         /* first time seen, do we have DSes? if match: VALID */
1420                         if(ta && tp->ds_rrset && key_matches_a_ds(env, ve,
1421                                 dnskey_rrset, i, tp->ds_rrset)) {
1422                                 verbose_key(ta, VERB_ALGO, "verified by DS");
1423                                 ta->s = AUTR_STATE_VALID;
1424                         }
1425                 }
1426                 if(!ta) {
1427                         ldns_rr_list_deep_free(r);
1428                         return 0;
1429                 }
1430                 seen_trustanchor(ta, 1);
1431                 verbose_key(ta, VERB_ALGO, "in DNS response");
1432         }
1433         set_tp_times(tp, min_expiry(env, r), key_ttl(dnskey_rrset), changed);
1434         ldns_rr_list_deep_free(r);
1435         return 1;
1436 }
1437
1438 /**
1439  * Check if the holddown time has already exceeded
1440  * setting: add-holddown: add holddown timer
1441  * setting: del-holddown: del holddown timer
1442  * @param env: environment with current time
1443  * @param ta: trust anchor to check for.
1444  * @param holddown: the timer value
1445  * @return number of seconds the holddown has passed.
1446  */
1447 static int
1448 check_holddown(struct module_env* env, struct autr_ta* ta,
1449         unsigned int holddown)
1450 {
1451         unsigned int elapsed;
1452         if((unsigned)*env->now < (unsigned)ta->last_change) {
1453                 log_warn("time goes backwards. delaying key holddown");
1454                 return 0;
1455         }
1456         elapsed = (unsigned)*env->now - (unsigned)ta->last_change;
1457         if (elapsed > holddown) {
1458                 return (int) (elapsed-holddown);
1459         }
1460         verbose_key(ta, VERB_ALGO, "holddown time %d seconds to go",
1461                 (int) (holddown-elapsed));
1462         return 0;
1463 }
1464
1465
1466 /** Set last_change to now */
1467 static void
1468 reset_holddown(struct module_env* env, struct autr_ta* ta, int* changed)
1469 {
1470         ta->last_change = *env->now;
1471         *changed = 1;
1472 }
1473
1474 /** Set the state for this trust anchor */
1475 static void
1476 set_trustanchor_state(struct module_env* env, struct autr_ta* ta, int* changed,
1477         autr_state_t s)
1478 {
1479         verbose_key(ta, VERB_ALGO, "update: %s to %s",
1480                 trustanchor_state2str(ta->s), trustanchor_state2str(s));
1481         ta->s = s;
1482         reset_holddown(env, ta, changed);
1483 }
1484
1485
1486 /** Event: NewKey */
1487 static void
1488 do_newkey(struct module_env* env, struct autr_ta* anchor, int* c)
1489 {
1490         if (anchor->s == AUTR_STATE_START)
1491                 set_trustanchor_state(env, anchor, c, AUTR_STATE_ADDPEND);
1492 }
1493
1494 /** Event: AddTime */
1495 static void
1496 do_addtime(struct module_env* env, struct autr_ta* anchor, int* c)
1497 {
1498         /* This not according to RFC, this is 30 days, but the RFC demands
1499          * MAX(30days, TTL expire time of first DNSKEY set with this key),
1500          * The value may be too small if a very large TTL was used. */
1501         int exceeded = check_holddown(env, anchor, env->cfg->add_holddown);
1502         if (exceeded && anchor->s == AUTR_STATE_ADDPEND) {
1503                 verbose_key(anchor, VERB_ALGO, "add-holddown time exceeded "
1504                         "%d seconds ago, and pending-count %d", exceeded,
1505                         anchor->pending_count);
1506                 if(anchor->pending_count >= MIN_PENDINGCOUNT) {
1507                         set_trustanchor_state(env, anchor, c, AUTR_STATE_VALID);
1508                         anchor->pending_count = 0;
1509                         return;
1510                 }
1511                 verbose_key(anchor, VERB_ALGO, "add-holddown time sanity check "
1512                         "failed (pending count: %d)", anchor->pending_count);
1513         }
1514 }
1515
1516 /** Event: RemTime */
1517 static void
1518 do_remtime(struct module_env* env, struct autr_ta* anchor, int* c)
1519 {
1520         int exceeded = check_holddown(env, anchor, env->cfg->del_holddown);
1521         if(exceeded && anchor->s == AUTR_STATE_REVOKED) {
1522                 verbose_key(anchor, VERB_ALGO, "del-holddown time exceeded "
1523                         "%d seconds ago", exceeded);
1524                 set_trustanchor_state(env, anchor, c, AUTR_STATE_REMOVED);
1525         }
1526 }
1527
1528 /** Event: KeyRem */
1529 static void
1530 do_keyrem(struct module_env* env, struct autr_ta* anchor, int* c)
1531 {
1532         if(anchor->s == AUTR_STATE_ADDPEND) {
1533                 set_trustanchor_state(env, anchor, c, AUTR_STATE_START);
1534                 anchor->pending_count = 0;
1535         } else if(anchor->s == AUTR_STATE_VALID)
1536                 set_trustanchor_state(env, anchor, c, AUTR_STATE_MISSING);
1537 }
1538
1539 /** Event: KeyPres */
1540 static void
1541 do_keypres(struct module_env* env, struct autr_ta* anchor, int* c)
1542 {
1543         if(anchor->s == AUTR_STATE_MISSING)
1544                 set_trustanchor_state(env, anchor, c, AUTR_STATE_VALID);
1545 }
1546
1547 /* Event: Revoked */
1548 static void
1549 do_revoked(struct module_env* env, struct autr_ta* anchor, int* c)
1550 {
1551         if(anchor->s == AUTR_STATE_VALID || anchor->s == AUTR_STATE_MISSING) {
1552                 set_trustanchor_state(env, anchor, c, AUTR_STATE_REVOKED);
1553                 verbose_key(anchor, VERB_ALGO, "old id, prior to revocation");
1554                 revoke_dnskey(anchor, 0);
1555                 verbose_key(anchor, VERB_ALGO, "new id, after revocation");
1556         }
1557 }
1558
1559 /** Do statestable transition matrix for anchor */
1560 static void
1561 anchor_state_update(struct module_env* env, struct autr_ta* anchor, int* c)
1562 {
1563         log_assert(anchor);
1564         switch(anchor->s) {
1565         /* START */
1566         case AUTR_STATE_START:
1567                 /* NewKey: ADDPEND */
1568                 if (anchor->fetched)
1569                         do_newkey(env, anchor, c);
1570                 break;
1571         /* ADDPEND */
1572         case AUTR_STATE_ADDPEND:
1573                 /* KeyRem: START */
1574                 if (!anchor->fetched)
1575                         do_keyrem(env, anchor, c);
1576                 /* AddTime: VALID */
1577                 else    do_addtime(env, anchor, c);
1578                 break;
1579         /* VALID */
1580         case AUTR_STATE_VALID:
1581                 /* RevBit: REVOKED */
1582                 if (anchor->revoked)
1583                         do_revoked(env, anchor, c);
1584                 /* KeyRem: MISSING */
1585                 else if (!anchor->fetched)
1586                         do_keyrem(env, anchor, c);
1587                 else if(!anchor->last_change) {
1588                         verbose_key(anchor, VERB_ALGO, "first seen");
1589                         reset_holddown(env, anchor, c);
1590                 }
1591                 break;
1592         /* MISSING */
1593         case AUTR_STATE_MISSING:
1594                 /* RevBit: REVOKED */
1595                 if (anchor->revoked)
1596                         do_revoked(env, anchor, c);
1597                 /* KeyPres */
1598                 else if (anchor->fetched)
1599                         do_keypres(env, anchor, c);
1600                 break;
1601         /* REVOKED */
1602         case AUTR_STATE_REVOKED:
1603                 if (anchor->fetched)
1604                         reset_holddown(env, anchor, c);
1605                 /* RemTime: REMOVED */
1606                 else    do_remtime(env, anchor, c);
1607                 break;
1608         /* REMOVED */
1609         case AUTR_STATE_REMOVED:
1610         default:
1611                 break;
1612         }
1613 }
1614
1615 /** if ZSK init then trust KSKs */
1616 static int
1617 init_zsk_to_ksk(struct module_env* env, struct trust_anchor* tp, int* changed)
1618 {
1619         /* search for VALID ZSKs */
1620         struct autr_ta* anchor;
1621         int validzsk = 0;
1622         int validksk = 0;
1623         for(anchor = tp->autr->keys; anchor; anchor = anchor->next) {
1624                 /* last_change test makes sure it was manually configured */
1625                 if (ldns_rr_get_type(anchor->rr) == LDNS_RR_TYPE_DNSKEY &&
1626                         anchor->last_change == 0 &&
1627                         !rr_is_dnskey_sep(anchor->rr) &&
1628                         anchor->s == AUTR_STATE_VALID)
1629                         validzsk++;
1630         }
1631         if(validzsk == 0)
1632                 return 0;
1633         for(anchor = tp->autr->keys; anchor; anchor = anchor->next) {
1634                 if (rr_is_dnskey_sep(anchor->rr) &&
1635                         anchor->s == AUTR_STATE_ADDPEND) {
1636                         verbose_key(anchor, VERB_ALGO, "trust KSK from "
1637                                 "ZSK(config)");
1638                         set_trustanchor_state(env, anchor, changed,
1639                                 AUTR_STATE_VALID);
1640                         validksk++;
1641                 }
1642         }
1643         return validksk;
1644 }
1645
1646 /** Remove missing trustanchors so the list does not grow forever */
1647 static void
1648 remove_missing_trustanchors(struct module_env* env, struct trust_anchor* tp,
1649         int* changed)
1650 {
1651         struct autr_ta* anchor;
1652         int exceeded;
1653         int valid = 0;
1654         /* see if we have anchors that are valid */
1655         for(anchor = tp->autr->keys; anchor; anchor = anchor->next) {
1656                 /* Only do KSKs */
1657                 if (!rr_is_dnskey_sep(anchor->rr))
1658                         continue;
1659                 if (anchor->s == AUTR_STATE_VALID)
1660                         valid++;
1661         }
1662         /* if there are no SEP Valid anchors, see if we started out with
1663          * a ZSK (last-change=0) anchor, which is VALID and there are KSKs
1664          * now that can be made valid.  Do this immediately because there
1665          * is no guarantee that the ZSKs get announced long enough.  Usually
1666          * this is immediately after init with a ZSK trusted, unless the domain
1667          * was not advertising any KSKs at all.  In which case we perfectly
1668          * track the zero number of KSKs. */
1669         if(valid == 0) {
1670                 valid = init_zsk_to_ksk(env, tp, changed);
1671                 if(valid == 0)
1672                         return;
1673         }
1674
1675         for(anchor = tp->autr->keys; anchor; anchor = anchor->next) {
1676                 /* ignore ZSKs if newly added */
1677                 if(anchor->s == AUTR_STATE_START)
1678                         continue;
1679                 /* remove ZSKs if a KSK is present */
1680                 if (!rr_is_dnskey_sep(anchor->rr)) {
1681                         if(valid > 0) {
1682                                 verbose_key(anchor, VERB_ALGO, "remove ZSK "
1683                                         "[%d key(s) VALID]", valid);
1684                                 set_trustanchor_state(env, anchor, changed,
1685                                         AUTR_STATE_REMOVED);
1686                         }
1687                         continue;
1688                 }
1689                 /* Only do MISSING keys */
1690                 if (anchor->s != AUTR_STATE_MISSING)
1691                         continue;
1692                 if(env->cfg->keep_missing == 0)
1693                         continue; /* keep forever */
1694
1695                 exceeded = check_holddown(env, anchor, env->cfg->keep_missing);
1696                 /* If keep_missing has exceeded and we still have more than
1697                  * one valid KSK: remove missing trust anchor */
1698                 if (exceeded && valid > 0) {
1699                         verbose_key(anchor, VERB_ALGO, "keep-missing time "
1700                                 "exceeded %d seconds ago, [%d key(s) VALID]",
1701                                 exceeded, valid);
1702                         set_trustanchor_state(env, anchor, changed,
1703                                 AUTR_STATE_REMOVED);
1704                 }
1705         }
1706 }
1707
1708 /** Do the statetable from RFC5011 transition matrix */
1709 static int
1710 do_statetable(struct module_env* env, struct trust_anchor* tp, int* changed)
1711 {
1712         struct autr_ta* anchor;
1713         for(anchor = tp->autr->keys; anchor; anchor = anchor->next) {
1714                 /* Only do KSKs */
1715                 if(!rr_is_dnskey_sep(anchor->rr))
1716                         continue;
1717                 anchor_state_update(env, anchor, changed);
1718         }
1719         remove_missing_trustanchors(env, tp, changed);
1720         return 1;
1721 }
1722
1723 /** See if time alone makes ADDPEND to VALID transition */
1724 static void
1725 autr_holddown_exceed(struct module_env* env, struct trust_anchor* tp, int* c)
1726 {
1727         struct autr_ta* anchor;
1728         for(anchor = tp->autr->keys; anchor; anchor = anchor->next) {
1729                 if(rr_is_dnskey_sep(anchor->rr) &&
1730                         anchor->s == AUTR_STATE_ADDPEND)
1731                         do_addtime(env, anchor, c);
1732         }
1733 }
1734
1735 /** cleanup key list */
1736 static void
1737 autr_cleanup_keys(struct trust_anchor* tp)
1738 {
1739         struct autr_ta* p, **prevp;
1740         prevp = &tp->autr->keys;
1741         p = tp->autr->keys;
1742         while(p) {
1743                 /* do we want to remove this key? */
1744                 if(p->s == AUTR_STATE_START || p->s == AUTR_STATE_REMOVED ||
1745                         ldns_rr_get_type(p->rr) != LDNS_RR_TYPE_DNSKEY) {
1746                         struct autr_ta* np = p->next;
1747                         /* remove */
1748                         ldns_rr_free(p->rr);
1749                         free(p);
1750                         /* snip and go to next item */
1751                         *prevp = np;
1752                         p = np;
1753                         continue;
1754                 }
1755                 /* remove pending counts if no longer pending */
1756                 if(p->s != AUTR_STATE_ADDPEND)
1757                         p->pending_count = 0;
1758                 prevp = &p->next;
1759                 p = p->next;
1760         }
1761 }
1762
1763 /** calculate next probe time */
1764 static time_t
1765 calc_next_probe(struct module_env* env, uint32_t wait)
1766 {
1767         /* make it random, 90-100% */
1768         uint32_t rnd, rest;
1769         if(wait < 3600)
1770                 wait = 3600;
1771         rnd = wait/10;
1772         rest = wait-rnd;
1773         rnd = (uint32_t)ub_random_max(env->rnd, (long int)rnd);
1774         return (time_t)(*env->now + rest + rnd);
1775 }
1776
1777 /** what is first probe time (anchors must be locked) */
1778 static time_t
1779 wait_probe_time(struct val_anchors* anchors)
1780 {
1781         rbnode_t* t = rbtree_first(&anchors->autr->probe);
1782         if(t != RBTREE_NULL)
1783                 return ((struct trust_anchor*)t->key)->autr->next_probe_time;
1784         return 0;
1785 }
1786
1787 /** reset worker timer */
1788 static void
1789 reset_worker_timer(struct module_env* env)
1790 {
1791         struct timeval tv;
1792 #ifndef S_SPLINT_S
1793         uint32_t next = (uint32_t)wait_probe_time(env->anchors);
1794         /* in case this is libunbound, no timer */
1795         if(!env->probe_timer)
1796                 return;
1797         if(next > *env->now)
1798                 tv.tv_sec = (time_t)(next - *env->now);
1799         else    tv.tv_sec = 0;
1800 #endif
1801         tv.tv_usec = 0;
1802         comm_timer_set(env->probe_timer, &tv);
1803         verbose(VERB_ALGO, "scheduled next probe in %d sec", (int)tv.tv_sec);
1804 }
1805
1806 /** set next probe for trust anchor */
1807 static int
1808 set_next_probe(struct module_env* env, struct trust_anchor* tp,
1809         struct ub_packed_rrset_key* dnskey_rrset)
1810 {
1811         struct trust_anchor key, *tp2;
1812         time_t mold, mnew;
1813         /* use memory allocated in rrset for temporary name storage */
1814         key.node.key = &key;
1815         key.name = dnskey_rrset->rk.dname;
1816         key.namelen = dnskey_rrset->rk.dname_len;
1817         key.namelabs = dname_count_labels(key.name);
1818         key.dclass = tp->dclass;
1819         lock_basic_unlock(&tp->lock);
1820
1821         /* fetch tp again and lock anchors, so that we can modify the trees */
1822         lock_basic_lock(&env->anchors->lock);
1823         tp2 = (struct trust_anchor*)rbtree_search(env->anchors->tree, &key);
1824         if(!tp2) {
1825                 verbose(VERB_ALGO, "trustpoint was deleted in set_next_probe");
1826                 lock_basic_unlock(&env->anchors->lock);
1827                 return 0;
1828         }
1829         log_assert(tp == tp2);
1830         lock_basic_lock(&tp->lock);
1831
1832         /* schedule */
1833         mold = wait_probe_time(env->anchors);
1834         (void)rbtree_delete(&env->anchors->autr->probe, tp);
1835         tp->autr->next_probe_time = calc_next_probe(env,
1836                 tp->autr->query_interval);
1837         (void)rbtree_insert(&env->anchors->autr->probe, &tp->autr->pnode);
1838         mnew = wait_probe_time(env->anchors);
1839
1840         lock_basic_unlock(&env->anchors->lock);
1841         verbose(VERB_ALGO, "next probe set in %d seconds",
1842                 (int)tp->autr->next_probe_time - (int)*env->now);
1843         if(mold != mnew) {
1844                 reset_worker_timer(env);
1845         }
1846         return 1;
1847 }
1848
1849 /** Revoke and Delete a trust point */
1850 static void
1851 autr_tp_remove(struct module_env* env, struct trust_anchor* tp,
1852         struct ub_packed_rrset_key* dnskey_rrset)
1853 {
1854         struct trust_anchor* del_tp;
1855         struct trust_anchor key;
1856         struct autr_point_data pd;
1857         time_t mold, mnew;
1858
1859         log_nametypeclass(VERB_OPS, "trust point was revoked",
1860                 tp->name, LDNS_RR_TYPE_DNSKEY, tp->dclass);
1861         tp->autr->revoked = 1;
1862
1863         /* use space allocated for dnskey_rrset to save name of anchor */
1864         memset(&key, 0, sizeof(key));
1865         memset(&pd, 0, sizeof(pd));
1866         key.autr = &pd;
1867         key.node.key = &key;
1868         pd.pnode.key = &key;
1869         pd.next_probe_time = tp->autr->next_probe_time;
1870         key.name = dnskey_rrset->rk.dname;
1871         key.namelen = tp->namelen;
1872         key.namelabs = tp->namelabs;
1873         key.dclass = tp->dclass;
1874
1875         /* unlock */
1876         lock_basic_unlock(&tp->lock);
1877
1878         /* take from tree. It could be deleted by someone else,hence (void). */
1879         lock_basic_lock(&env->anchors->lock);
1880         del_tp = (struct trust_anchor*)rbtree_delete(env->anchors->tree, &key);
1881         mold = wait_probe_time(env->anchors);
1882         (void)rbtree_delete(&env->anchors->autr->probe, &key);
1883         mnew = wait_probe_time(env->anchors);
1884         anchors_init_parents_locked(env->anchors);
1885         lock_basic_unlock(&env->anchors->lock);
1886
1887         /* if !del_tp then the trust point is no longer present in the tree,
1888          * it was deleted by someone else, who will write the zonefile and
1889          * clean up the structure */
1890         if(del_tp) {
1891                 /* save on disk */
1892                 del_tp->autr->next_probe_time = 0; /* no more probing for it */
1893                 autr_write_file(env, del_tp);
1894
1895                 /* delete */
1896                 autr_point_delete(del_tp);
1897         }
1898         if(mold != mnew) {
1899                 reset_worker_timer(env);
1900         }
1901 }
1902
1903 int autr_process_prime(struct module_env* env, struct val_env* ve,
1904         struct trust_anchor* tp, struct ub_packed_rrset_key* dnskey_rrset)
1905 {
1906         int changed = 0;
1907         log_assert(tp && tp->autr);
1908         /* autotrust update trust anchors */
1909         /* the tp is locked, and stays locked unless it is deleted */
1910
1911         /* we could just catch the anchor here while another thread
1912          * is busy deleting it. Just unlock and let the other do its job */
1913         if(tp->autr->revoked) {
1914                 log_nametypeclass(VERB_ALGO, "autotrust not processed, "
1915                         "trust point revoked", tp->name,
1916                         LDNS_RR_TYPE_DNSKEY, tp->dclass);
1917                 lock_basic_unlock(&tp->lock);
1918                 return 0; /* it is revoked */
1919         }
1920
1921         /* query_dnskeys(): */
1922         tp->autr->last_queried = *env->now;
1923
1924         log_nametypeclass(VERB_ALGO, "autotrust process for",
1925                 tp->name, LDNS_RR_TYPE_DNSKEY, tp->dclass);
1926         /* see if time alone makes some keys valid */
1927         autr_holddown_exceed(env, tp, &changed);
1928         if(changed) {
1929                 verbose(VERB_ALGO, "autotrust: morekeys, reassemble");
1930                 if(!autr_assemble(tp)) {
1931                         log_err("malloc failure assembling autotrust keys");
1932                         return 1; /* unchanged */
1933                 }
1934         }
1935         /* did we get any data? */
1936         if(!dnskey_rrset) {
1937                 verbose(VERB_ALGO, "autotrust: no dnskey rrset");
1938                 /* no update of query_failed, because then we would have
1939                  * to write to disk. But we cannot because we maybe are
1940                  * still 'initialising' with DS records, that we cannot write
1941                  * in the full format (which only contains KSKs). */
1942                 return 1; /* trust point exists */
1943         }
1944         /* check for revoked keys to remove immediately */
1945         check_contains_revoked(env, ve, tp, dnskey_rrset, &changed);
1946         if(changed) {
1947                 verbose(VERB_ALGO, "autotrust: revokedkeys, reassemble");
1948                 if(!autr_assemble(tp)) {
1949                         log_err("malloc failure assembling autotrust keys");
1950                         return 1; /* unchanged */
1951                 }
1952                 if(!tp->ds_rrset && !tp->dnskey_rrset) {
1953                         /* no more keys, all are revoked */
1954                         /* this is a success for this probe attempt */
1955                         tp->autr->last_success = *env->now;
1956                         autr_tp_remove(env, tp, dnskey_rrset);
1957                         return 0; /* trust point removed */
1958                 }
1959         }
1960         /* verify the dnskey rrset and see if it is valid. */
1961         if(!verify_dnskey(env, ve, tp, dnskey_rrset)) {
1962                 verbose(VERB_ALGO, "autotrust: dnskey did not verify.");
1963                 /* only increase failure count if this is not the first prime,
1964                  * this means there was a previous succesful probe */
1965                 if(tp->autr->last_success) {
1966                         tp->autr->query_failed += 1;
1967                         autr_write_file(env, tp);
1968                 }
1969                 return 1; /* trust point exists */
1970         }
1971
1972         tp->autr->last_success = *env->now;
1973         tp->autr->query_failed = 0;
1974
1975         /* Add new trust anchors to the data structure
1976          * - note which trust anchors are seen this probe.
1977          * Set trustpoint query_interval and retry_time.
1978          * - find minimum rrsig expiration interval
1979          */
1980         if(!update_events(env, ve, tp, dnskey_rrset, &changed)) {
1981                 log_err("malloc failure in autotrust update_events. "
1982                         "trust point unchanged.");
1983                 return 1; /* trust point unchanged, so exists */
1984         }
1985
1986         /* - for every SEP key do the 5011 statetable.
1987          * - remove missing trustanchors (if veryold and we have new anchors).
1988          */
1989         if(!do_statetable(env, tp, &changed)) {
1990                 log_err("malloc failure in autotrust do_statetable. "
1991                         "trust point unchanged.");
1992                 return 1; /* trust point unchanged, so exists */
1993         }
1994
1995         autr_cleanup_keys(tp);
1996         if(!set_next_probe(env, tp, dnskey_rrset))
1997                 return 0; /* trust point does not exist */
1998         autr_write_file(env, tp);
1999         if(changed) {
2000                 verbose(VERB_ALGO, "autotrust: changed, reassemble");
2001                 if(!autr_assemble(tp)) {
2002                         log_err("malloc failure assembling autotrust keys");
2003                         return 1; /* unchanged */
2004                 }
2005                 if(!tp->ds_rrset && !tp->dnskey_rrset) {
2006                         /* no more keys, all are revoked */
2007                         autr_tp_remove(env, tp, dnskey_rrset);
2008                         return 0; /* trust point removed */
2009                 }
2010         } else verbose(VERB_ALGO, "autotrust: no changes");
2011
2012         return 1; /* trust point exists */
2013 }
2014
2015 /** debug print a trust anchor key */
2016 static void
2017 autr_debug_print_ta(struct autr_ta* ta)
2018 {
2019         char buf[32];
2020         char* str = ldns_rr2str(ta->rr);
2021         if(!str) {
2022                 log_info("out of memory in debug_print_ta");
2023                 return;
2024         }
2025         if(str && str[0]) str[strlen(str)-1]=0; /* remove newline */
2026         ctime_r(&ta->last_change, buf);
2027         if(buf[0]) buf[strlen(buf)-1]=0; /* remove newline */
2028         log_info("[%s] %s ;;state:%d ;;pending_count:%d%s%s last:%s",
2029                 trustanchor_state2str(ta->s), str, ta->s, ta->pending_count,
2030                 ta->fetched?" fetched":"", ta->revoked?" revoked":"", buf);
2031         free(str);
2032 }
2033
2034 /** debug print a trust point */
2035 static void
2036 autr_debug_print_tp(struct trust_anchor* tp)
2037 {
2038         struct autr_ta* ta;
2039         char buf[257];
2040         if(!tp->autr)
2041                 return;
2042         dname_str(tp->name, buf);
2043         log_info("trust point %s : %d", buf, (int)tp->dclass);
2044         log_info("assembled %d DS and %d DNSKEYs",
2045                 (int)tp->numDS, (int)tp->numDNSKEY);
2046         if(0) { /* turned off because it prints to stderr */
2047                 ldns_buffer* bf = ldns_buffer_new(70000);
2048                 ldns_rr_list* list;
2049                 if(tp->ds_rrset) {
2050                         list = packed_rrset_to_rr_list(tp->ds_rrset, bf);
2051                         ldns_rr_list_print(stderr, list);
2052                         ldns_rr_list_deep_free(list);
2053                 }
2054                 if(tp->dnskey_rrset) {
2055                         list = packed_rrset_to_rr_list(tp->dnskey_rrset, bf);
2056                         ldns_rr_list_print(stderr, list);
2057                         ldns_rr_list_deep_free(list);
2058                 }
2059                 ldns_buffer_free(bf);
2060         }
2061         log_info("file %s", tp->autr->file);
2062         ctime_r(&tp->autr->last_queried, buf);
2063         if(buf[0]) buf[strlen(buf)-1]=0; /* remove newline */
2064         log_info("last_queried: %u %s", (unsigned)tp->autr->last_queried, buf);
2065         ctime_r(&tp->autr->last_success, buf);
2066         if(buf[0]) buf[strlen(buf)-1]=0; /* remove newline */
2067         log_info("last_success: %u %s", (unsigned)tp->autr->last_success, buf);
2068         ctime_r(&tp->autr->next_probe_time, buf);
2069         if(buf[0]) buf[strlen(buf)-1]=0; /* remove newline */
2070         log_info("next_probe_time: %u %s", (unsigned)tp->autr->next_probe_time,
2071                 buf);
2072         log_info("query_interval: %u", (unsigned)tp->autr->query_interval);
2073         log_info("retry_time: %u", (unsigned)tp->autr->retry_time);
2074         log_info("query_failed: %u", (unsigned)tp->autr->query_failed);
2075
2076         for(ta=tp->autr->keys; ta; ta=ta->next) {
2077                 autr_debug_print_ta(ta);
2078         }
2079 }
2080
2081 void
2082 autr_debug_print(struct val_anchors* anchors)
2083 {
2084         struct trust_anchor* tp;
2085         lock_basic_lock(&anchors->lock);
2086         RBTREE_FOR(tp, struct trust_anchor*, anchors->tree) {
2087                 lock_basic_lock(&tp->lock);
2088                 autr_debug_print_tp(tp);
2089                 lock_basic_unlock(&tp->lock);
2090         }
2091         lock_basic_unlock(&anchors->lock);
2092 }
2093
2094 void probe_answer_cb(void* arg, int ATTR_UNUSED(rcode),
2095         ldns_buffer* ATTR_UNUSED(buf), enum sec_status ATTR_UNUSED(sec),
2096         char* ATTR_UNUSED(why_bogus))
2097 {
2098         /* retry was set before the query was done,
2099          * re-querytime is set when query succeeded, but that may not
2100          * have reset this timer because the query could have been
2101          * handled by another thread. In that case, this callback would
2102          * get called after the original timeout is done.
2103          * By not resetting the timer, it may probe more often, but not
2104          * less often.
2105          * Unless the new lookup resulted in smaller TTLs and thus smaller
2106          * timeout values. In that case one old TTL could be mistakenly done.
2107          */
2108         struct module_env* env = (struct module_env*)arg;
2109         verbose(VERB_ALGO, "autotrust probe answer cb");
2110         reset_worker_timer(env);
2111 }
2112
2113 /** probe a trust anchor DNSKEY and unlocks tp */
2114 static void
2115 probe_anchor(struct module_env* env, struct trust_anchor* tp)
2116 {
2117         struct query_info qinfo;
2118         uint16_t qflags = BIT_RD;
2119         struct edns_data edns;
2120         ldns_buffer* buf = env->scratch_buffer;
2121         qinfo.qname = regional_alloc_init(env->scratch, tp->name, tp->namelen);
2122         if(!qinfo.qname) {
2123                 log_err("out of memory making 5011 probe");
2124                 return;
2125         }
2126         qinfo.qname_len = tp->namelen;
2127         qinfo.qtype = LDNS_RR_TYPE_DNSKEY;
2128         qinfo.qclass = tp->dclass;
2129         log_query_info(VERB_ALGO, "autotrust probe", &qinfo);
2130         verbose(VERB_ALGO, "retry probe set in %d seconds",
2131                 (int)tp->autr->next_probe_time - (int)*env->now);
2132         edns.edns_present = 1;
2133         edns.ext_rcode = 0;
2134         edns.edns_version = 0;
2135         edns.bits = EDNS_DO;
2136         if(ldns_buffer_capacity(buf) < 65535)
2137                 edns.udp_size = (uint16_t)ldns_buffer_capacity(buf);
2138         else    edns.udp_size = 65535;
2139
2140         /* can't hold the lock while mesh_run is processing */
2141         lock_basic_unlock(&tp->lock);
2142
2143         /* delete the DNSKEY from rrset and key cache so an active probe
2144          * is done. First the rrset so another thread does not use it
2145          * to recreate the key entry in a race condition. */
2146         rrset_cache_remove(env->rrset_cache, qinfo.qname, qinfo.qname_len,
2147                 qinfo.qtype, qinfo.qclass, 0);
2148         key_cache_remove(env->key_cache, qinfo.qname, qinfo.qname_len,
2149                 qinfo.qclass);
2150
2151         if(!mesh_new_callback(env->mesh, &qinfo, qflags, &edns, buf, 0,
2152                 &probe_answer_cb, env)) {
2153                 log_err("out of memory making 5011 probe");
2154         }
2155 }
2156
2157 /** fetch first to-probe trust-anchor and lock it and set retrytime */
2158 static struct trust_anchor*
2159 todo_probe(struct module_env* env, uint32_t* next)
2160 {
2161         struct trust_anchor* tp;
2162         rbnode_t* el;
2163         /* get first one */
2164         lock_basic_lock(&env->anchors->lock);
2165         if( (el=rbtree_first(&env->anchors->autr->probe)) == RBTREE_NULL) {
2166                 /* in case of revoked anchors */
2167                 lock_basic_unlock(&env->anchors->lock);
2168                 return NULL;
2169         }
2170         tp = (struct trust_anchor*)el->key;
2171         lock_basic_lock(&tp->lock);
2172
2173         /* is it eligible? */
2174         if((uint32_t)tp->autr->next_probe_time > *env->now) {
2175                 /* no more to probe */
2176                 *next = (uint32_t)tp->autr->next_probe_time - *env->now;
2177                 lock_basic_unlock(&tp->lock);
2178                 lock_basic_unlock(&env->anchors->lock);
2179                 return NULL;
2180         }
2181
2182         /* reset its next probe time */
2183         (void)rbtree_delete(&env->anchors->autr->probe, tp);
2184         tp->autr->next_probe_time = calc_next_probe(env, tp->autr->retry_time);
2185         (void)rbtree_insert(&env->anchors->autr->probe, &tp->autr->pnode);
2186         lock_basic_unlock(&env->anchors->lock);
2187
2188         return tp;
2189 }
2190
2191 uint32_t
2192 autr_probe_timer(struct module_env* env)
2193 {
2194         struct trust_anchor* tp;
2195         uint32_t next_probe = 3600;
2196         int num = 0;
2197         verbose(VERB_ALGO, "autotrust probe timer callback");
2198         /* while there are still anchors to probe */
2199         while( (tp = todo_probe(env, &next_probe)) ) {
2200                 /* make a probe for this anchor */
2201                 probe_anchor(env, tp);
2202                 num++;
2203         }
2204         regional_free_all(env->scratch);
2205         if(num == 0)
2206                 return 0; /* no trust points to probe */
2207         verbose(VERB_ALGO, "autotrust probe timer %d callbacks done", num);
2208         return next_probe;
2209 }